1169689Skan/* Routines for discovering and unpropagating edge equivalences. 2169689Skan Copyright (C) 2005 Free Software Foundation, Inc. 3169689Skan 4169689SkanThis file is part of GCC. 5169689Skan 6169689SkanGCC is free software; you can redistribute it and/or modify 7169689Skanit under the terms of the GNU General Public License as published by 8169689Skanthe Free Software Foundation; either version 2, or (at your option) 9169689Skanany later version. 10169689Skan 11169689SkanGCC is distributed in the hope that it will be useful, 12169689Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 13169689SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14169689SkanGNU General Public License for more details. 15169689Skan 16169689SkanYou should have received a copy of the GNU General Public License 17169689Skanalong with GCC; see the file COPYING. If not, write to 18169689Skanthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 19169689SkanBoston, MA 02110-1301, USA. */ 20169689Skan 21169689Skan#include "config.h" 22169689Skan#include "system.h" 23169689Skan#include "coretypes.h" 24169689Skan#include "tm.h" 25169689Skan#include "tree.h" 26169689Skan#include "flags.h" 27169689Skan#include "rtl.h" 28169689Skan#include "tm_p.h" 29169689Skan#include "ggc.h" 30169689Skan#include "basic-block.h" 31169689Skan#include "output.h" 32169689Skan#include "expr.h" 33169689Skan#include "function.h" 34169689Skan#include "diagnostic.h" 35169689Skan#include "timevar.h" 36169689Skan#include "tree-dump.h" 37169689Skan#include "tree-flow.h" 38169689Skan#include "domwalk.h" 39169689Skan#include "real.h" 40169689Skan#include "tree-pass.h" 41169689Skan#include "tree-ssa-propagate.h" 42169689Skan#include "langhooks.h" 43169689Skan 44169689Skan/* The basic structure describing an equivalency created by traversing 45169689Skan an edge. Traversing the edge effectively means that we can assume 46169689Skan that we've seen an assignment LHS = RHS. */ 47169689Skanstruct edge_equivalency 48169689Skan{ 49169689Skan tree rhs; 50169689Skan tree lhs; 51169689Skan}; 52169689Skan 53169689Skan/* This routine finds and records edge equivalences for every edge 54169689Skan in the CFG. 55169689Skan 56169689Skan When complete, each edge that creates an equivalency will have an 57169689Skan EDGE_EQUIVALENCY structure hanging off the edge's AUX field. 58169689Skan The caller is responsible for freeing the AUX fields. */ 59169689Skan 60169689Skanstatic void 61169689Skanassociate_equivalences_with_edges (void) 62169689Skan{ 63169689Skan basic_block bb; 64169689Skan 65169689Skan /* Walk over each block. If the block ends with a control statement, 66169689Skan then it might create a useful equivalence. */ 67169689Skan FOR_EACH_BB (bb) 68169689Skan { 69169689Skan block_stmt_iterator bsi = bsi_last (bb); 70169689Skan tree stmt; 71169689Skan 72169689Skan /* If the block does not end with a COND_EXPR or SWITCH_EXPR 73169689Skan then there is nothing to do. */ 74169689Skan if (bsi_end_p (bsi)) 75169689Skan continue; 76169689Skan 77169689Skan stmt = bsi_stmt (bsi); 78169689Skan 79169689Skan if (!stmt) 80169689Skan continue; 81169689Skan 82169689Skan /* A COND_EXPR may create an equivalency in a variety of different 83169689Skan ways. */ 84169689Skan if (TREE_CODE (stmt) == COND_EXPR) 85169689Skan { 86169689Skan tree cond = COND_EXPR_COND (stmt); 87169689Skan edge true_edge; 88169689Skan edge false_edge; 89169689Skan struct edge_equivalency *equivalency; 90169689Skan 91169689Skan extract_true_false_edges_from_block (bb, &true_edge, &false_edge); 92169689Skan 93169689Skan /* If the conditional is a single variable 'X', record 'X = 1' 94169689Skan for the true edge and 'X = 0' on the false edge. */ 95169689Skan if (TREE_CODE (cond) == SSA_NAME 96169689Skan && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond)) 97169689Skan { 98169689Skan equivalency = XNEW (struct edge_equivalency); 99169689Skan equivalency->rhs = constant_boolean_node (1, TREE_TYPE (cond)); 100169689Skan equivalency->lhs = cond; 101169689Skan true_edge->aux = equivalency; 102169689Skan 103169689Skan equivalency = XNEW (struct edge_equivalency); 104169689Skan equivalency->rhs = constant_boolean_node (0, TREE_TYPE (cond)); 105169689Skan equivalency->lhs = cond; 106169689Skan false_edge->aux = equivalency; 107169689Skan } 108169689Skan /* Equality tests may create one or two equivalences. */ 109169689Skan else if (TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR) 110169689Skan { 111169689Skan tree op0 = TREE_OPERAND (cond, 0); 112169689Skan tree op1 = TREE_OPERAND (cond, 1); 113169689Skan 114169689Skan /* Special case comparing booleans against a constant as we 115169689Skan know the value of OP0 on both arms of the branch. i.e., we 116169689Skan can record an equivalence for OP0 rather than COND. */ 117169689Skan if (TREE_CODE (op0) == SSA_NAME 118169689Skan && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0) 119169689Skan && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE 120169689Skan && is_gimple_min_invariant (op1)) 121169689Skan { 122169689Skan if (TREE_CODE (cond) == EQ_EXPR) 123169689Skan { 124169689Skan equivalency = XNEW (struct edge_equivalency); 125169689Skan equivalency->lhs = op0; 126169689Skan equivalency->rhs = (integer_zerop (op1) 127169689Skan ? boolean_false_node 128169689Skan : boolean_true_node); 129169689Skan true_edge->aux = equivalency; 130169689Skan 131169689Skan equivalency = XNEW (struct edge_equivalency); 132169689Skan equivalency->lhs = op0; 133169689Skan equivalency->rhs = (integer_zerop (op1) 134169689Skan ? boolean_true_node 135169689Skan : boolean_false_node); 136169689Skan false_edge->aux = equivalency; 137169689Skan } 138169689Skan else 139169689Skan { 140169689Skan equivalency = XNEW (struct edge_equivalency); 141169689Skan equivalency->lhs = op0; 142169689Skan equivalency->rhs = (integer_zerop (op1) 143169689Skan ? boolean_true_node 144169689Skan : boolean_false_node); 145169689Skan true_edge->aux = equivalency; 146169689Skan 147169689Skan equivalency = XNEW (struct edge_equivalency); 148169689Skan equivalency->lhs = op0; 149169689Skan equivalency->rhs = (integer_zerop (op1) 150169689Skan ? boolean_false_node 151169689Skan : boolean_true_node); 152169689Skan false_edge->aux = equivalency; 153169689Skan } 154169689Skan } 155169689Skan 156169689Skan if (TREE_CODE (op0) == SSA_NAME 157169689Skan && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0) 158169689Skan && (is_gimple_min_invariant (op1) 159169689Skan || (TREE_CODE (op1) == SSA_NAME 160169689Skan && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1)))) 161169689Skan { 162169689Skan /* For IEEE, -0.0 == 0.0, so we don't necessarily know 163169689Skan the sign of a variable compared against zero. If 164169689Skan we're honoring signed zeros, then we cannot record 165169689Skan this value unless we know that the value is nonzero. */ 166169689Skan if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op0))) 167169689Skan && (TREE_CODE (op1) != REAL_CST 168169689Skan || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (op1)))) 169169689Skan continue; 170169689Skan 171169689Skan equivalency = XNEW (struct edge_equivalency); 172169689Skan equivalency->lhs = op0; 173169689Skan equivalency->rhs = op1; 174169689Skan if (TREE_CODE (cond) == EQ_EXPR) 175169689Skan true_edge->aux = equivalency; 176169689Skan else 177169689Skan false_edge->aux = equivalency; 178169689Skan 179169689Skan } 180169689Skan } 181169689Skan 182169689Skan /* ??? TRUTH_NOT_EXPR can create an equivalence too. */ 183169689Skan } 184169689Skan 185169689Skan /* For a SWITCH_EXPR, a case label which represents a single 186169689Skan value and which is the only case label which reaches the 187169689Skan target block creates an equivalence. */ 188169689Skan if (TREE_CODE (stmt) == SWITCH_EXPR) 189169689Skan { 190169689Skan tree cond = SWITCH_COND (stmt); 191169689Skan 192169689Skan if (TREE_CODE (cond) == SSA_NAME 193169689Skan && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond)) 194169689Skan { 195169689Skan tree labels = SWITCH_LABELS (stmt); 196169689Skan int i, n_labels = TREE_VEC_LENGTH (labels); 197169689Skan tree *info = XCNEWVEC (tree, n_basic_blocks); 198169689Skan 199169689Skan /* Walk over the case label vector. Record blocks 200169689Skan which are reached by a single case label which represents 201169689Skan a single value. */ 202169689Skan for (i = 0; i < n_labels; i++) 203169689Skan { 204169689Skan tree label = TREE_VEC_ELT (labels, i); 205169689Skan basic_block bb = label_to_block (CASE_LABEL (label)); 206169689Skan 207169689Skan 208169689Skan if (CASE_HIGH (label) 209169689Skan || !CASE_LOW (label) 210169689Skan || info[bb->index]) 211169689Skan info[bb->index] = error_mark_node; 212169689Skan else 213169689Skan info[bb->index] = label; 214169689Skan } 215169689Skan 216169689Skan /* Now walk over the blocks to determine which ones were 217169689Skan marked as being reached by a useful case label. */ 218169689Skan for (i = 0; i < n_basic_blocks; i++) 219169689Skan { 220169689Skan tree node = info[i]; 221169689Skan 222169689Skan if (node != NULL 223169689Skan && node != error_mark_node) 224169689Skan { 225169689Skan tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node)); 226169689Skan struct edge_equivalency *equivalency; 227169689Skan 228169689Skan /* Record an equivalency on the edge from BB to basic 229169689Skan block I. */ 230169689Skan equivalency = XNEW (struct edge_equivalency); 231169689Skan equivalency->rhs = x; 232169689Skan equivalency->lhs = cond; 233169689Skan find_edge (bb, BASIC_BLOCK (i))->aux = equivalency; 234169689Skan } 235169689Skan } 236169689Skan free (info); 237169689Skan } 238169689Skan } 239169689Skan 240169689Skan } 241169689Skan} 242169689Skan 243169689Skan 244169689Skan/* Translating out of SSA sometimes requires inserting copies and 245169689Skan constant initializations on edges to eliminate PHI nodes. 246169689Skan 247169689Skan In some cases those copies and constant initializations are 248169689Skan redundant because the target already has the value on the 249169689Skan RHS of the assignment. 250169689Skan 251169689Skan We previously tried to catch these cases after translating 252169689Skan out of SSA form. However, that code often missed cases. Worse 253169689Skan yet, the cases it missed were also often missed by the RTL 254169689Skan optimizers. Thus the resulting code had redundant instructions. 255169689Skan 256169689Skan This pass attempts to detect these situations before translating 257169689Skan out of SSA form. 258169689Skan 259169689Skan The key concept that this pass is built upon is that these 260169689Skan redundant copies and constant initializations often occur 261169689Skan due to constant/copy propagating equivalences resulting from 262169689Skan COND_EXPRs and SWITCH_EXPRs. 263169689Skan 264169689Skan We want to do those propagations as they can sometimes allow 265169689Skan the SSA optimizers to do a better job. However, in the cases 266169689Skan where such propagations do not result in further optimization, 267169689Skan we would like to "undo" the propagation to avoid the redundant 268169689Skan copies and constant initializations. 269169689Skan 270169689Skan This pass works by first associating equivalences with edges in 271169689Skan the CFG. For example, the edge leading from a SWITCH_EXPR to 272169689Skan its associated CASE_LABEL will have an equivalency between 273169689Skan SWITCH_COND and the value in the case label. 274169689Skan 275169689Skan Once we have found the edge equivalences, we proceed to walk 276169689Skan the CFG in dominator order. As we traverse edges we record 277169689Skan equivalences associated with those edges we traverse. 278169689Skan 279169689Skan When we encounter a PHI node, we walk its arguments to see if we 280169689Skan have an equivalence for the PHI argument. If so, then we replace 281169689Skan the argument. 282169689Skan 283169689Skan Equivalences are looked up based on their value (think of it as 284169689Skan the RHS of an assignment). A value may be an SSA_NAME or an 285169689Skan invariant. We may have several SSA_NAMEs with the same value, 286169689Skan so with each value we have a list of SSA_NAMEs that have the 287169689Skan same value. */ 288169689Skan 289169689Skan/* As we enter each block we record the value for any edge equivalency 290169689Skan leading to this block. If no such edge equivalency exists, then we 291169689Skan record NULL. These equivalences are live until we leave the dominator 292169689Skan subtree rooted at the block where we record the equivalency. */ 293169689Skanstatic VEC(tree,heap) *equiv_stack; 294169689Skan 295169689Skan/* Global hash table implementing a mapping from invariant values 296169689Skan to a list of SSA_NAMEs which have the same value. We might be 297169689Skan able to reuse tree-vn for this code. */ 298169689Skanstatic htab_t equiv; 299169689Skan 300169689Skan/* Main structure for recording equivalences into our hash table. */ 301169689Skanstruct equiv_hash_elt 302169689Skan{ 303169689Skan /* The value/key of this entry. */ 304169689Skan tree value; 305169689Skan 306169689Skan /* List of SSA_NAMEs which have the same value/key. */ 307169689Skan VEC(tree,heap) *equivalences; 308169689Skan}; 309169689Skan 310169689Skanstatic void uncprop_initialize_block (struct dom_walk_data *, basic_block); 311169689Skanstatic void uncprop_finalize_block (struct dom_walk_data *, basic_block); 312169689Skanstatic void uncprop_into_successor_phis (struct dom_walk_data *, basic_block); 313169689Skan 314169689Skan/* Hashing and equality routines for the hash table. */ 315169689Skan 316169689Skanstatic hashval_t 317169689Skanequiv_hash (const void *p) 318169689Skan{ 319169689Skan tree value = ((struct equiv_hash_elt *)p)->value; 320169689Skan return iterative_hash_expr (value, 0); 321169689Skan} 322169689Skan 323169689Skanstatic int 324169689Skanequiv_eq (const void *p1, const void *p2) 325169689Skan{ 326169689Skan tree value1 = ((struct equiv_hash_elt *)p1)->value; 327169689Skan tree value2 = ((struct equiv_hash_elt *)p2)->value; 328169689Skan 329169689Skan return operand_equal_p (value1, value2, 0); 330169689Skan} 331169689Skan 332169689Skan/* Free an instance of equiv_hash_elt. */ 333169689Skan 334169689Skanstatic void 335169689Skanequiv_free (void *p) 336169689Skan{ 337169689Skan struct equiv_hash_elt *elt = (struct equiv_hash_elt *) p; 338169689Skan VEC_free (tree, heap, elt->equivalences); 339169689Skan free (elt); 340169689Skan} 341169689Skan 342169689Skan/* Remove the most recently recorded equivalency for VALUE. */ 343169689Skan 344169689Skanstatic void 345169689Skanremove_equivalence (tree value) 346169689Skan{ 347169689Skan struct equiv_hash_elt equiv_hash_elt, *equiv_hash_elt_p; 348169689Skan void **slot; 349169689Skan 350169689Skan equiv_hash_elt.value = value; 351169689Skan equiv_hash_elt.equivalences = NULL; 352169689Skan 353169689Skan slot = htab_find_slot (equiv, &equiv_hash_elt, NO_INSERT); 354169689Skan 355169689Skan equiv_hash_elt_p = (struct equiv_hash_elt *) *slot; 356169689Skan VEC_pop (tree, equiv_hash_elt_p->equivalences); 357169689Skan} 358169689Skan 359169689Skan/* Record EQUIVALENCE = VALUE into our hash table. */ 360169689Skan 361169689Skanstatic void 362169689Skanrecord_equiv (tree value, tree equivalence) 363169689Skan{ 364169689Skan struct equiv_hash_elt *equiv_hash_elt; 365169689Skan void **slot; 366169689Skan 367169689Skan equiv_hash_elt = XNEW (struct equiv_hash_elt); 368169689Skan equiv_hash_elt->value = value; 369169689Skan equiv_hash_elt->equivalences = NULL; 370169689Skan 371169689Skan slot = htab_find_slot (equiv, equiv_hash_elt, INSERT); 372169689Skan 373169689Skan if (*slot == NULL) 374169689Skan *slot = (void *) equiv_hash_elt; 375169689Skan else 376169689Skan free (equiv_hash_elt); 377169689Skan 378169689Skan equiv_hash_elt = (struct equiv_hash_elt *) *slot; 379169689Skan 380169689Skan VEC_safe_push (tree, heap, equiv_hash_elt->equivalences, equivalence); 381169689Skan} 382169689Skan 383169689Skan/* Main driver for un-cprop. */ 384169689Skan 385169689Skanstatic unsigned int 386169689Skantree_ssa_uncprop (void) 387169689Skan{ 388169689Skan struct dom_walk_data walk_data; 389169689Skan basic_block bb; 390169689Skan 391169689Skan associate_equivalences_with_edges (); 392169689Skan 393169689Skan /* Create our global data structures. */ 394169689Skan equiv = htab_create (1024, equiv_hash, equiv_eq, equiv_free); 395169689Skan equiv_stack = VEC_alloc (tree, heap, 2); 396169689Skan 397169689Skan /* We're going to do a dominator walk, so ensure that we have 398169689Skan dominance information. */ 399169689Skan calculate_dominance_info (CDI_DOMINATORS); 400169689Skan 401169689Skan /* Setup callbacks for the generic dominator tree walker. */ 402169689Skan walk_data.walk_stmts_backward = false; 403169689Skan walk_data.dom_direction = CDI_DOMINATORS; 404169689Skan walk_data.initialize_block_local_data = NULL; 405169689Skan walk_data.before_dom_children_before_stmts = uncprop_initialize_block; 406169689Skan walk_data.before_dom_children_walk_stmts = NULL; 407169689Skan walk_data.before_dom_children_after_stmts = uncprop_into_successor_phis; 408169689Skan walk_data.after_dom_children_before_stmts = NULL; 409169689Skan walk_data.after_dom_children_walk_stmts = NULL; 410169689Skan walk_data.after_dom_children_after_stmts = uncprop_finalize_block; 411169689Skan walk_data.global_data = NULL; 412169689Skan walk_data.block_local_data_size = 0; 413169689Skan walk_data.interesting_blocks = NULL; 414169689Skan 415169689Skan /* Now initialize the dominator walker. */ 416169689Skan init_walk_dominator_tree (&walk_data); 417169689Skan 418169689Skan /* Recursively walk the dominator tree undoing unprofitable 419169689Skan constant/copy propagations. */ 420169689Skan walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR); 421169689Skan 422169689Skan /* Finalize and clean up. */ 423169689Skan fini_walk_dominator_tree (&walk_data); 424169689Skan 425169689Skan /* EQUIV_STACK should already be empty at this point, so we just 426169689Skan need to empty elements out of the hash table, free EQUIV_STACK, 427169689Skan and cleanup the AUX field on the edges. */ 428169689Skan htab_delete (equiv); 429169689Skan VEC_free (tree, heap, equiv_stack); 430169689Skan FOR_EACH_BB (bb) 431169689Skan { 432169689Skan edge e; 433169689Skan edge_iterator ei; 434169689Skan 435169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 436169689Skan { 437169689Skan if (e->aux) 438169689Skan { 439169689Skan free (e->aux); 440169689Skan e->aux = NULL; 441169689Skan } 442169689Skan } 443169689Skan } 444169689Skan return 0; 445169689Skan} 446169689Skan 447169689Skan 448169689Skan/* We have finished processing the dominator children of BB, perform 449169689Skan any finalization actions in preparation for leaving this node in 450169689Skan the dominator tree. */ 451169689Skan 452169689Skanstatic void 453169689Skanuncprop_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, 454169689Skan basic_block bb ATTRIBUTE_UNUSED) 455169689Skan{ 456169689Skan /* Pop the topmost value off the equiv stack. */ 457169689Skan tree value = VEC_pop (tree, equiv_stack); 458169689Skan 459169689Skan /* If that value was non-null, then pop the topmost equivalency off 460169689Skan its equivalency stack. */ 461169689Skan if (value != NULL) 462169689Skan remove_equivalence (value); 463169689Skan} 464169689Skan 465169689Skan/* Unpropagate values from PHI nodes in successor blocks of BB. */ 466169689Skan 467169689Skanstatic void 468169689Skanuncprop_into_successor_phis (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, 469169689Skan basic_block bb) 470169689Skan{ 471169689Skan edge e; 472169689Skan edge_iterator ei; 473169689Skan 474169689Skan /* For each successor edge, first temporarily record any equivalence 475169689Skan on that edge. Then unpropagate values in any PHI nodes at the 476169689Skan destination of the edge. Then remove the temporary equivalence. */ 477169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 478169689Skan { 479169689Skan tree phi = phi_nodes (e->dest); 480169689Skan 481169689Skan /* If there are no PHI nodes in this destination, then there is 482169689Skan no sense in recording any equivalences. */ 483169689Skan if (!phi) 484169689Skan continue; 485169689Skan 486169689Skan /* Record any equivalency associated with E. */ 487169689Skan if (e->aux) 488169689Skan { 489169689Skan struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux; 490169689Skan record_equiv (equiv->rhs, equiv->lhs); 491169689Skan } 492169689Skan 493169689Skan /* Walk over the PHI nodes, unpropagating values. */ 494169689Skan for ( ; phi; phi = PHI_CHAIN (phi)) 495169689Skan { 496169689Skan /* Sigh. We'll have more efficient access to this one day. */ 497169689Skan tree arg = PHI_ARG_DEF (phi, e->dest_idx); 498169689Skan struct equiv_hash_elt equiv_hash_elt; 499169689Skan void **slot; 500169689Skan 501169689Skan /* If the argument is not an invariant, or refers to the same 502169689Skan underlying variable as the PHI result, then there's no 503169689Skan point in un-propagating the argument. */ 504169689Skan if (!is_gimple_min_invariant (arg) 505169689Skan && SSA_NAME_VAR (arg) != SSA_NAME_VAR (PHI_RESULT (phi))) 506169689Skan continue; 507169689Skan 508169689Skan /* Lookup this argument's value in the hash table. */ 509169689Skan equiv_hash_elt.value = arg; 510169689Skan equiv_hash_elt.equivalences = NULL; 511169689Skan slot = htab_find_slot (equiv, &equiv_hash_elt, NO_INSERT); 512169689Skan 513169689Skan if (slot) 514169689Skan { 515169689Skan struct equiv_hash_elt *elt = (struct equiv_hash_elt *) *slot; 516169689Skan int j; 517169689Skan 518169689Skan /* Walk every equivalence with the same value. If we find 519169689Skan one with the same underlying variable as the PHI result, 520169689Skan then replace the value in the argument with its equivalent 521169689Skan SSA_NAME. Use the most recent equivalence as hopefully 522169689Skan that results in shortest lifetimes. */ 523169689Skan for (j = VEC_length (tree, elt->equivalences) - 1; j >= 0; j--) 524169689Skan { 525169689Skan tree equiv = VEC_index (tree, elt->equivalences, j); 526169689Skan 527169689Skan if (SSA_NAME_VAR (equiv) == SSA_NAME_VAR (PHI_RESULT (phi))) 528169689Skan { 529169689Skan SET_PHI_ARG_DEF (phi, e->dest_idx, equiv); 530169689Skan break; 531169689Skan } 532169689Skan } 533169689Skan } 534169689Skan } 535169689Skan 536169689Skan /* If we had an equivalence associated with this edge, remove it. */ 537169689Skan if (e->aux) 538169689Skan { 539169689Skan struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux; 540169689Skan remove_equivalence (equiv->rhs); 541169689Skan } 542169689Skan } 543169689Skan} 544169689Skan 545169689Skan/* Ignoring loop backedges, if BB has precisely one incoming edge then 546169689Skan return that edge. Otherwise return NULL. */ 547169689Skanstatic edge 548169689Skansingle_incoming_edge_ignoring_loop_edges (basic_block bb) 549169689Skan{ 550169689Skan edge retval = NULL; 551169689Skan edge e; 552169689Skan edge_iterator ei; 553169689Skan 554169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 555169689Skan { 556169689Skan /* A loop back edge can be identified by the destination of 557169689Skan the edge dominating the source of the edge. */ 558169689Skan if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest)) 559169689Skan continue; 560169689Skan 561169689Skan /* If we have already seen a non-loop edge, then we must have 562169689Skan multiple incoming non-loop edges and thus we return NULL. */ 563169689Skan if (retval) 564169689Skan return NULL; 565169689Skan 566169689Skan /* This is the first non-loop incoming edge we have found. Record 567169689Skan it. */ 568169689Skan retval = e; 569169689Skan } 570169689Skan 571169689Skan return retval; 572169689Skan} 573169689Skan 574169689Skanstatic void 575169689Skanuncprop_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, 576169689Skan basic_block bb) 577169689Skan{ 578169689Skan basic_block parent; 579169689Skan edge e; 580169689Skan bool recorded = false; 581169689Skan 582169689Skan /* If this block is dominated by a single incoming edge and that edge 583169689Skan has an equivalency, then record the equivalency and push the 584169689Skan VALUE onto EQUIV_STACK. Else push a NULL entry on EQUIV_STACK. */ 585169689Skan parent = get_immediate_dominator (CDI_DOMINATORS, bb); 586169689Skan if (parent) 587169689Skan { 588169689Skan e = single_incoming_edge_ignoring_loop_edges (bb); 589169689Skan 590169689Skan if (e && e->src == parent && e->aux) 591169689Skan { 592169689Skan struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux; 593169689Skan 594169689Skan record_equiv (equiv->rhs, equiv->lhs); 595169689Skan VEC_safe_push (tree, heap, equiv_stack, equiv->rhs); 596169689Skan recorded = true; 597169689Skan } 598169689Skan } 599169689Skan 600169689Skan if (!recorded) 601169689Skan VEC_safe_push (tree, heap, equiv_stack, NULL_TREE); 602169689Skan} 603169689Skan 604169689Skanstatic bool 605169689Skangate_uncprop (void) 606169689Skan{ 607169689Skan return flag_tree_dom != 0; 608169689Skan} 609169689Skan 610169689Skanstruct tree_opt_pass pass_uncprop = 611169689Skan{ 612169689Skan "uncprop", /* name */ 613169689Skan gate_uncprop, /* gate */ 614169689Skan tree_ssa_uncprop, /* execute */ 615169689Skan NULL, /* sub */ 616169689Skan NULL, /* next */ 617169689Skan 0, /* static_pass_number */ 618169689Skan TV_TREE_SSA_UNCPROP, /* tv_id */ 619169689Skan PROP_cfg | PROP_ssa, /* properties_required */ 620169689Skan 0, /* properties_provided */ 621169689Skan 0, /* properties_destroyed */ 622169689Skan 0, /* todo_flags_start */ 623169689Skan TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */ 624169689Skan 0 /* letter */ 625169689Skan}; 626