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