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