1/* Routines for discovering and unpropagating edge equivalences. 2 Copyright (C) 2005-2015 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify 7it under the terms of the GNU General Public License as published by 8the Free Software Foundation; either version 3, or (at your option) 9any later version. 10 11GCC is distributed in the hope that it will be useful, 12but WITHOUT ANY WARRANTY; without even the implied warranty of 13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14GNU General Public License for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING3. If not see 18<http://www.gnu.org/licenses/>. */ 19 20#include "config.h" 21#include "system.h" 22#include "coretypes.h" 23#include "tm.h" 24#include "hash-set.h" 25#include "machmode.h" 26#include "vec.h" 27#include "double-int.h" 28#include "input.h" 29#include "alias.h" 30#include "symtab.h" 31#include "wide-int.h" 32#include "inchash.h" 33#include "real.h" 34#include "tree.h" 35#include "fold-const.h" 36#include "stor-layout.h" 37#include "flags.h" 38#include "tm_p.h" 39#include "predict.h" 40#include "hard-reg-set.h" 41#include "input.h" 42#include "function.h" 43#include "dominance.h" 44#include "cfg.h" 45#include "cfganal.h" 46#include "basic-block.h" 47#include "hash-table.h" 48#include "hash-map.h" 49#include "tree-ssa-alias.h" 50#include "internal-fn.h" 51#include "gimple-expr.h" 52#include "is-a.h" 53#include "gimple.h" 54#include "gimple-iterator.h" 55#include "gimple-ssa.h" 56#include "tree-cfg.h" 57#include "tree-phinodes.h" 58#include "ssa-iterators.h" 59#include "domwalk.h" 60#include "tree-pass.h" 61#include "tree-ssa-propagate.h" 62 63/* The basic structure describing an equivalency created by traversing 64 an edge. Traversing the edge effectively means that we can assume 65 that we've seen an assignment LHS = RHS. */ 66struct edge_equivalency 67{ 68 tree rhs; 69 tree lhs; 70}; 71 72/* This routine finds and records edge equivalences for every edge 73 in the CFG. 74 75 When complete, each edge that creates an equivalency will have an 76 EDGE_EQUIVALENCY structure hanging off the edge's AUX field. 77 The caller is responsible for freeing the AUX fields. */ 78 79static void 80associate_equivalences_with_edges (void) 81{ 82 basic_block bb; 83 84 /* Walk over each block. If the block ends with a control statement, 85 then it might create a useful equivalence. */ 86 FOR_EACH_BB_FN (bb, cfun) 87 { 88 gimple_stmt_iterator gsi = gsi_last_bb (bb); 89 gimple stmt; 90 91 /* If the block does not end with a COND_EXPR or SWITCH_EXPR 92 then there is nothing to do. */ 93 if (gsi_end_p (gsi)) 94 continue; 95 96 stmt = gsi_stmt (gsi); 97 98 if (!stmt) 99 continue; 100 101 /* A COND_EXPR may create an equivalency in a variety of different 102 ways. */ 103 if (gimple_code (stmt) == GIMPLE_COND) 104 { 105 edge true_edge; 106 edge false_edge; 107 struct edge_equivalency *equivalency; 108 enum tree_code code = gimple_cond_code (stmt); 109 110 extract_true_false_edges_from_block (bb, &true_edge, &false_edge); 111 112 /* Equality tests may create one or two equivalences. */ 113 if (code == EQ_EXPR || code == NE_EXPR) 114 { 115 tree op0 = gimple_cond_lhs (stmt); 116 tree op1 = gimple_cond_rhs (stmt); 117 118 /* Special case comparing booleans against a constant as we 119 know the value of OP0 on both arms of the branch. i.e., we 120 can record an equivalence for OP0 rather than COND. */ 121 if (TREE_CODE (op0) == SSA_NAME 122 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0) 123 && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE 124 && is_gimple_min_invariant (op1)) 125 { 126 if (code == EQ_EXPR) 127 { 128 equivalency = XNEW (struct edge_equivalency); 129 equivalency->lhs = op0; 130 equivalency->rhs = (integer_zerop (op1) 131 ? boolean_false_node 132 : boolean_true_node); 133 true_edge->aux = equivalency; 134 135 equivalency = XNEW (struct edge_equivalency); 136 equivalency->lhs = op0; 137 equivalency->rhs = (integer_zerop (op1) 138 ? boolean_true_node 139 : boolean_false_node); 140 false_edge->aux = equivalency; 141 } 142 else 143 { 144 equivalency = XNEW (struct edge_equivalency); 145 equivalency->lhs = op0; 146 equivalency->rhs = (integer_zerop (op1) 147 ? boolean_true_node 148 : boolean_false_node); 149 true_edge->aux = equivalency; 150 151 equivalency = XNEW (struct edge_equivalency); 152 equivalency->lhs = op0; 153 equivalency->rhs = (integer_zerop (op1) 154 ? boolean_false_node 155 : boolean_true_node); 156 false_edge->aux = equivalency; 157 } 158 } 159 160 else if (TREE_CODE (op0) == SSA_NAME 161 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0) 162 && (is_gimple_min_invariant (op1) 163 || (TREE_CODE (op1) == SSA_NAME 164 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1)))) 165 { 166 /* For IEEE, -0.0 == 0.0, so we don't necessarily know 167 the sign of a variable compared against zero. If 168 we're honoring signed zeros, then we cannot record 169 this value unless we know that the value is nonzero. */ 170 if (HONOR_SIGNED_ZEROS (op0) 171 && (TREE_CODE (op1) != REAL_CST 172 || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (op1)))) 173 continue; 174 175 equivalency = XNEW (struct edge_equivalency); 176 equivalency->lhs = op0; 177 equivalency->rhs = op1; 178 if (code == EQ_EXPR) 179 true_edge->aux = equivalency; 180 else 181 false_edge->aux = equivalency; 182 183 } 184 } 185 186 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */ 187 } 188 189 /* For a SWITCH_EXPR, a case label which represents a single 190 value and which is the only case label which reaches the 191 target block creates an equivalence. */ 192 else if (gimple_code (stmt) == GIMPLE_SWITCH) 193 { 194 gswitch *switch_stmt = as_a <gswitch *> (stmt); 195 tree cond = gimple_switch_index (switch_stmt); 196 197 if (TREE_CODE (cond) == SSA_NAME 198 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond)) 199 { 200 int i, n_labels = gimple_switch_num_labels (switch_stmt); 201 tree *info = XCNEWVEC (tree, last_basic_block_for_fn (cfun)); 202 203 /* Walk over the case label vector. Record blocks 204 which are reached by a single case label which represents 205 a single value. */ 206 for (i = 0; i < n_labels; i++) 207 { 208 tree label = gimple_switch_label (switch_stmt, i); 209 basic_block bb = label_to_block (CASE_LABEL (label)); 210 211 if (CASE_HIGH (label) 212 || !CASE_LOW (label) 213 || info[bb->index]) 214 info[bb->index] = error_mark_node; 215 else 216 info[bb->index] = label; 217 } 218 219 /* Now walk over the blocks to determine which ones were 220 marked as being reached by a useful case label. */ 221 for (i = 0; i < n_basic_blocks_for_fn (cfun); i++) 222 { 223 tree node = info[i]; 224 225 if (node != NULL 226 && node != error_mark_node) 227 { 228 tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node)); 229 struct edge_equivalency *equivalency; 230 231 /* Record an equivalency on the edge from BB to basic 232 block I. */ 233 equivalency = XNEW (struct edge_equivalency); 234 equivalency->rhs = x; 235 equivalency->lhs = cond; 236 find_edge (bb, BASIC_BLOCK_FOR_FN (cfun, i))->aux = 237 equivalency; 238 } 239 } 240 free (info); 241 } 242 } 243 244 } 245} 246 247 248/* Translating out of SSA sometimes requires inserting copies and 249 constant initializations on edges to eliminate PHI nodes. 250 251 In some cases those copies and constant initializations are 252 redundant because the target already has the value on the 253 RHS of the assignment. 254 255 We previously tried to catch these cases after translating 256 out of SSA form. However, that code often missed cases. Worse 257 yet, the cases it missed were also often missed by the RTL 258 optimizers. Thus the resulting code had redundant instructions. 259 260 This pass attempts to detect these situations before translating 261 out of SSA form. 262 263 The key concept that this pass is built upon is that these 264 redundant copies and constant initializations often occur 265 due to constant/copy propagating equivalences resulting from 266 COND_EXPRs and SWITCH_EXPRs. 267 268 We want to do those propagations as they can sometimes allow 269 the SSA optimizers to do a better job. However, in the cases 270 where such propagations do not result in further optimization, 271 we would like to "undo" the propagation to avoid the redundant 272 copies and constant initializations. 273 274 This pass works by first associating equivalences with edges in 275 the CFG. For example, the edge leading from a SWITCH_EXPR to 276 its associated CASE_LABEL will have an equivalency between 277 SWITCH_COND and the value in the case label. 278 279 Once we have found the edge equivalences, we proceed to walk 280 the CFG in dominator order. As we traverse edges we record 281 equivalences associated with those edges we traverse. 282 283 When we encounter a PHI node, we walk its arguments to see if we 284 have an equivalence for the PHI argument. If so, then we replace 285 the argument. 286 287 Equivalences are looked up based on their value (think of it as 288 the RHS of an assignment). A value may be an SSA_NAME or an 289 invariant. We may have several SSA_NAMEs with the same value, 290 so with each value we have a list of SSA_NAMEs that have the 291 same value. */ 292 293 294/* Main structure for recording equivalences into our hash table. */ 295struct equiv_hash_elt 296{ 297 /* The value/key of this entry. */ 298 tree value; 299 300 /* List of SSA_NAMEs which have the same value/key. */ 301 vec<tree> equivalences; 302}; 303 304/* Value to ssa name equivalence hashtable helpers. */ 305 306struct val_ssa_equiv_hash_traits : default_hashmap_traits 307{ 308 static inline hashval_t hash (tree); 309 static inline bool equal_keys (tree, tree); 310 template<typename T> static inline void remove (T &); 311}; 312 313inline hashval_t 314val_ssa_equiv_hash_traits::hash (tree value) 315{ 316 return iterative_hash_expr (value, 0); 317} 318 319inline bool 320val_ssa_equiv_hash_traits::equal_keys (tree value1, tree value2) 321{ 322 return operand_equal_p (value1, value2, 0); 323} 324 325/* Free an instance of equiv_hash_elt. */ 326 327template<typename T> 328inline void 329val_ssa_equiv_hash_traits::remove (T &elt) 330{ 331 elt.m_value.release (); 332} 333 334/* Global hash table implementing a mapping from invariant values 335 to a list of SSA_NAMEs which have the same value. We might be 336 able to reuse tree-vn for this code. */ 337static hash_map<tree, vec<tree>, val_ssa_equiv_hash_traits> *val_ssa_equiv; 338 339static void uncprop_into_successor_phis (basic_block); 340 341/* Remove the most recently recorded equivalency for VALUE. */ 342 343static void 344remove_equivalence (tree value) 345{ 346 val_ssa_equiv->get (value)->pop (); 347} 348 349/* Record EQUIVALENCE = VALUE into our hash table. */ 350 351static void 352record_equiv (tree value, tree equivalence) 353{ 354 val_ssa_equiv->get_or_insert (value).safe_push (equivalence); 355} 356 357class uncprop_dom_walker : public dom_walker 358{ 359public: 360 uncprop_dom_walker (cdi_direction direction) : dom_walker (direction) {} 361 362 virtual void before_dom_children (basic_block); 363 virtual void after_dom_children (basic_block); 364 365private: 366 367 /* As we enter each block we record the value for any edge equivalency 368 leading to this block. If no such edge equivalency exists, then we 369 record NULL. These equivalences are live until we leave the dominator 370 subtree rooted at the block where we record the equivalency. */ 371 auto_vec<tree, 2> m_equiv_stack; 372}; 373 374/* We have finished processing the dominator children of BB, perform 375 any finalization actions in preparation for leaving this node in 376 the dominator tree. */ 377 378void 379uncprop_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED) 380{ 381 /* Pop the topmost value off the equiv stack. */ 382 tree value = m_equiv_stack.pop (); 383 384 /* If that value was non-null, then pop the topmost equivalency off 385 its equivalency stack. */ 386 if (value != NULL) 387 remove_equivalence (value); 388} 389 390/* Unpropagate values from PHI nodes in successor blocks of BB. */ 391 392static void 393uncprop_into_successor_phis (basic_block bb) 394{ 395 edge e; 396 edge_iterator ei; 397 398 /* For each successor edge, first temporarily record any equivalence 399 on that edge. Then unpropagate values in any PHI nodes at the 400 destination of the edge. Then remove the temporary equivalence. */ 401 FOR_EACH_EDGE (e, ei, bb->succs) 402 { 403 gimple_seq phis = phi_nodes (e->dest); 404 gimple_stmt_iterator gsi; 405 406 /* If there are no PHI nodes in this destination, then there is 407 no sense in recording any equivalences. */ 408 if (gimple_seq_empty_p (phis)) 409 continue; 410 411 /* Record any equivalency associated with E. */ 412 if (e->aux) 413 { 414 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux; 415 record_equiv (equiv->rhs, equiv->lhs); 416 } 417 418 /* Walk over the PHI nodes, unpropagating values. */ 419 for (gsi = gsi_start (phis) ; !gsi_end_p (gsi); gsi_next (&gsi)) 420 { 421 gimple phi = gsi_stmt (gsi); 422 tree arg = PHI_ARG_DEF (phi, e->dest_idx); 423 tree res = PHI_RESULT (phi); 424 425 /* If the argument is not an invariant and can be potentially 426 coalesced with the result, then there's no point in 427 un-propagating the argument. */ 428 if (!is_gimple_min_invariant (arg) 429 && gimple_can_coalesce_p (arg, res)) 430 continue; 431 432 /* Lookup this argument's value in the hash table. */ 433 vec<tree> *equivalences = val_ssa_equiv->get (arg); 434 if (equivalences) 435 { 436 /* Walk every equivalence with the same value. If we find 437 one that can potentially coalesce with the PHI rsult, 438 then replace the value in the argument with its equivalent 439 SSA_NAME. Use the most recent equivalence as hopefully 440 that results in shortest lifetimes. */ 441 for (int j = equivalences->length () - 1; j >= 0; j--) 442 { 443 tree equiv = (*equivalences)[j]; 444 445 if (gimple_can_coalesce_p (equiv, res)) 446 { 447 SET_PHI_ARG_DEF (phi, e->dest_idx, equiv); 448 break; 449 } 450 } 451 } 452 } 453 454 /* If we had an equivalence associated with this edge, remove it. */ 455 if (e->aux) 456 { 457 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux; 458 remove_equivalence (equiv->rhs); 459 } 460 } 461} 462 463/* Ignoring loop backedges, if BB has precisely one incoming edge then 464 return that edge. Otherwise return NULL. */ 465static edge 466single_incoming_edge_ignoring_loop_edges (basic_block bb) 467{ 468 edge retval = NULL; 469 edge e; 470 edge_iterator ei; 471 472 FOR_EACH_EDGE (e, ei, bb->preds) 473 { 474 /* A loop back edge can be identified by the destination of 475 the edge dominating the source of the edge. */ 476 if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest)) 477 continue; 478 479 /* If we have already seen a non-loop edge, then we must have 480 multiple incoming non-loop edges and thus we return NULL. */ 481 if (retval) 482 return NULL; 483 484 /* This is the first non-loop incoming edge we have found. Record 485 it. */ 486 retval = e; 487 } 488 489 return retval; 490} 491 492void 493uncprop_dom_walker::before_dom_children (basic_block bb) 494{ 495 basic_block parent; 496 edge e; 497 bool recorded = false; 498 499 /* If this block is dominated by a single incoming edge and that edge 500 has an equivalency, then record the equivalency and push the 501 VALUE onto EQUIV_STACK. Else push a NULL entry on EQUIV_STACK. */ 502 parent = get_immediate_dominator (CDI_DOMINATORS, bb); 503 if (parent) 504 { 505 e = single_incoming_edge_ignoring_loop_edges (bb); 506 507 if (e && e->src == parent && e->aux) 508 { 509 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux; 510 511 record_equiv (equiv->rhs, equiv->lhs); 512 m_equiv_stack.safe_push (equiv->rhs); 513 recorded = true; 514 } 515 } 516 517 if (!recorded) 518 m_equiv_stack.safe_push (NULL_TREE); 519 520 uncprop_into_successor_phis (bb); 521} 522 523namespace { 524 525const pass_data pass_data_uncprop = 526{ 527 GIMPLE_PASS, /* type */ 528 "uncprop", /* name */ 529 OPTGROUP_NONE, /* optinfo_flags */ 530 TV_TREE_SSA_UNCPROP, /* tv_id */ 531 ( PROP_cfg | PROP_ssa ), /* properties_required */ 532 0, /* properties_provided */ 533 0, /* properties_destroyed */ 534 0, /* todo_flags_start */ 535 0, /* todo_flags_finish */ 536}; 537 538class pass_uncprop : public gimple_opt_pass 539{ 540public: 541 pass_uncprop (gcc::context *ctxt) 542 : gimple_opt_pass (pass_data_uncprop, ctxt) 543 {} 544 545 /* opt_pass methods: */ 546 opt_pass * clone () { return new pass_uncprop (m_ctxt); } 547 virtual bool gate (function *) { return flag_tree_dom != 0; } 548 virtual unsigned int execute (function *); 549 550}; // class pass_uncprop 551 552unsigned int 553pass_uncprop::execute (function *fun) 554{ 555 basic_block bb; 556 557 associate_equivalences_with_edges (); 558 559 /* Create our global data structures. */ 560 val_ssa_equiv 561 = new hash_map<tree, vec<tree>, val_ssa_equiv_hash_traits> (1024); 562 563 /* We're going to do a dominator walk, so ensure that we have 564 dominance information. */ 565 calculate_dominance_info (CDI_DOMINATORS); 566 567 /* Recursively walk the dominator tree undoing unprofitable 568 constant/copy propagations. */ 569 uncprop_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr); 570 571 /* we just need to empty elements out of the hash table, and cleanup the 572 AUX field on the edges. */ 573 delete val_ssa_equiv; 574 val_ssa_equiv = NULL; 575 FOR_EACH_BB_FN (bb, fun) 576 { 577 edge e; 578 edge_iterator ei; 579 580 FOR_EACH_EDGE (e, ei, bb->succs) 581 { 582 if (e->aux) 583 { 584 free (e->aux); 585 e->aux = NULL; 586 } 587 } 588 } 589 return 0; 590} 591 592} // anon namespace 593 594gimple_opt_pass * 595make_pass_uncprop (gcc::context *ctxt) 596{ 597 return new pass_uncprop (ctxt); 598} 599