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