1/* Copy propagation and SSA_NAME replacement support routines. 2 Copyright (C) 2004, 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 "tree-pass.h" 39#include "tree-ssa-propagate.h" 40#include "langhooks.h" 41 42/* This file implements the copy propagation pass and provides a 43 handful of interfaces for performing const/copy propagation and 44 simple expression replacement which keep variable annotations 45 up-to-date. 46 47 We require that for any copy operation where the RHS and LHS have 48 a non-null memory tag the memory tag be the same. It is OK 49 for one or both of the memory tags to be NULL. 50 51 We also require tracking if a variable is dereferenced in a load or 52 store operation. 53 54 We enforce these requirements by having all copy propagation and 55 replacements of one SSA_NAME with a different SSA_NAME to use the 56 APIs defined in this file. */ 57 58/* Return true if we may propagate ORIG into DEST, false otherwise. */ 59 60bool 61may_propagate_copy (tree dest, tree orig) 62{ 63 tree type_d = TREE_TYPE (dest); 64 tree type_o = TREE_TYPE (orig); 65 66 /* Do not copy between types for which we *do* need a conversion. */ 67 if (!tree_ssa_useless_type_conversion_1 (type_d, type_o)) 68 return false; 69 70 /* FIXME. GIMPLE is allowing pointer assignments and comparisons of 71 pointers that have different alias sets. This means that these 72 pointers will have different memory tags associated to them. 73 74 If we allow copy propagation in these cases, statements de-referencing 75 the new pointer will now have a reference to a different memory tag 76 with potentially incorrect SSA information. 77 78 This was showing up in libjava/java/util/zip/ZipFile.java with code 79 like: 80 81 struct java.io.BufferedInputStream *T.660; 82 struct java.io.BufferedInputStream *T.647; 83 struct java.io.InputStream *is; 84 struct java.io.InputStream *is.662; 85 [ ... ] 86 T.660 = T.647; 87 is = T.660; <-- This ought to be type-casted 88 is.662 = is; 89 90 Also, f/name.c exposed a similar problem with a COND_EXPR predicate 91 that was causing DOM to generate and equivalence with two pointers of 92 alias-incompatible types: 93 94 struct _ffename_space *n; 95 struct _ffename *ns; 96 [ ... ] 97 if (n == ns) 98 goto lab; 99 ... 100 lab: 101 return n; 102 103 I think that GIMPLE should emit the appropriate type-casts. For the 104 time being, blocking copy-propagation in these cases is the safe thing 105 to do. */ 106 if (TREE_CODE (dest) == SSA_NAME 107 && TREE_CODE (orig) == SSA_NAME 108 && POINTER_TYPE_P (type_d) 109 && POINTER_TYPE_P (type_o)) 110 { 111 tree mt_dest = var_ann (SSA_NAME_VAR (dest))->symbol_mem_tag; 112 tree mt_orig = var_ann (SSA_NAME_VAR (orig))->symbol_mem_tag; 113 if (mt_dest && mt_orig && mt_dest != mt_orig) 114 return false; 115 else if (!lang_hooks.types_compatible_p (type_d, type_o)) 116 return false; 117 else if (get_alias_set (TREE_TYPE (type_d)) != 118 get_alias_set (TREE_TYPE (type_o))) 119 return false; 120 121 /* Also verify flow-sensitive information is compatible. */ 122 if (SSA_NAME_PTR_INFO (orig) && SSA_NAME_PTR_INFO (dest)) 123 { 124 struct ptr_info_def *orig_ptr_info = SSA_NAME_PTR_INFO (orig); 125 struct ptr_info_def *dest_ptr_info = SSA_NAME_PTR_INFO (dest); 126 127 if (orig_ptr_info->name_mem_tag 128 && dest_ptr_info->name_mem_tag 129 && orig_ptr_info->pt_vars 130 && dest_ptr_info->pt_vars 131 && !bitmap_intersect_p (dest_ptr_info->pt_vars, 132 orig_ptr_info->pt_vars)) 133 return false; 134 } 135 } 136 137 /* If the destination is a SSA_NAME for a virtual operand, then we have 138 some special cases to handle. */ 139 if (TREE_CODE (dest) == SSA_NAME && !is_gimple_reg (dest)) 140 { 141 /* If both operands are SSA_NAMEs referring to virtual operands, then 142 we can always propagate. */ 143 if (TREE_CODE (orig) == SSA_NAME 144 && !is_gimple_reg (orig)) 145 return true; 146 147 /* We have a "copy" from something like a constant into a virtual 148 operand. Reject these. */ 149 return false; 150 } 151 152 /* If ORIG flows in from an abnormal edge, it cannot be propagated. */ 153 if (TREE_CODE (orig) == SSA_NAME 154 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig)) 155 return false; 156 157 /* If DEST is an SSA_NAME that flows from an abnormal edge, then it 158 cannot be replaced. */ 159 if (TREE_CODE (dest) == SSA_NAME 160 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (dest)) 161 return false; 162 163 /* Anything else is OK. */ 164 return true; 165} 166 167/* Similarly, but we know that we're propagating into an ASM_EXPR. */ 168 169bool 170may_propagate_copy_into_asm (tree dest) 171{ 172 /* Hard register operands of asms are special. Do not bypass. */ 173 return !(TREE_CODE (dest) == SSA_NAME 174 && TREE_CODE (SSA_NAME_VAR (dest)) == VAR_DECL 175 && DECL_HARD_REGISTER (SSA_NAME_VAR (dest))); 176} 177 178 179/* Given two SSA_NAMEs pointers ORIG and NEW such that we are copy 180 propagating NEW into ORIG, consolidate aliasing information so that 181 they both share the same memory tags. */ 182 183void 184merge_alias_info (tree orig, tree new) 185{ 186 tree new_sym = SSA_NAME_VAR (new); 187 tree orig_sym = SSA_NAME_VAR (orig); 188 var_ann_t new_ann = var_ann (new_sym); 189 var_ann_t orig_ann = var_ann (orig_sym); 190 191 gcc_assert (POINTER_TYPE_P (TREE_TYPE (orig))); 192 gcc_assert (POINTER_TYPE_P (TREE_TYPE (new))); 193 194#if defined ENABLE_CHECKING 195 gcc_assert (lang_hooks.types_compatible_p (TREE_TYPE (orig), 196 TREE_TYPE (new))); 197 198 /* If the pointed-to alias sets are different, these two pointers 199 would never have the same memory tag. In this case, NEW should 200 not have been propagated into ORIG. */ 201 gcc_assert (get_alias_set (TREE_TYPE (TREE_TYPE (new_sym))) 202 == get_alias_set (TREE_TYPE (TREE_TYPE (orig_sym)))); 203#endif 204 205 /* Synchronize the symbol tags. If both pointers had a tag and they 206 are different, then something has gone wrong. Symbol tags can 207 always be merged because they are flow insensitive, all the SSA 208 names of the same base DECL share the same symbol tag. */ 209 if (new_ann->symbol_mem_tag == NULL_TREE) 210 new_ann->symbol_mem_tag = orig_ann->symbol_mem_tag; 211 else if (orig_ann->symbol_mem_tag == NULL_TREE) 212 orig_ann->symbol_mem_tag = new_ann->symbol_mem_tag; 213 else 214 gcc_assert (new_ann->symbol_mem_tag == orig_ann->symbol_mem_tag); 215 216 /* Check that flow-sensitive information is compatible. Notice that 217 we may not merge flow-sensitive information here. This function 218 is called when propagating equivalences dictated by the IL, like 219 a copy operation P_i = Q_j, and from equivalences dictated by 220 control-flow, like if (P_i == Q_j). 221 222 In the former case, P_i and Q_j are equivalent in every block 223 dominated by the assignment, so their flow-sensitive information 224 is always the same. However, in the latter case, the pointers 225 P_i and Q_j are only equivalent in one of the sub-graphs out of 226 the predicate, so their flow-sensitive information is not the 227 same in every block dominated by the predicate. 228 229 Since we cannot distinguish one case from another in this 230 function, we can only make sure that if P_i and Q_j have 231 flow-sensitive information, they should be compatible. */ 232 if (SSA_NAME_PTR_INFO (orig) && SSA_NAME_PTR_INFO (new)) 233 { 234 struct ptr_info_def *orig_ptr_info = SSA_NAME_PTR_INFO (orig); 235 struct ptr_info_def *new_ptr_info = SSA_NAME_PTR_INFO (new); 236 237 /* Note that pointer NEW and ORIG may actually have different 238 pointed-to variables (e.g., PR 18291 represented in 239 testsuite/gcc.c-torture/compile/pr18291.c). However, since 240 NEW is being copy-propagated into ORIG, it must always be 241 true that the pointed-to set for pointer NEW is the same, or 242 a subset, of the pointed-to set for pointer ORIG. If this 243 isn't the case, we shouldn't have been able to do the 244 propagation of NEW into ORIG. */ 245 if (orig_ptr_info->name_mem_tag 246 && new_ptr_info->name_mem_tag 247 && orig_ptr_info->pt_vars 248 && new_ptr_info->pt_vars) 249 gcc_assert (bitmap_intersect_p (new_ptr_info->pt_vars, 250 orig_ptr_info->pt_vars)); 251 } 252} 253 254 255/* Common code for propagate_value and replace_exp. 256 257 Replace use operand OP_P with VAL. FOR_PROPAGATION indicates if the 258 replacement is done to propagate a value or not. */ 259 260static void 261replace_exp_1 (use_operand_p op_p, tree val, 262 bool for_propagation ATTRIBUTE_UNUSED) 263{ 264 tree op = USE_FROM_PTR (op_p); 265 266#if defined ENABLE_CHECKING 267 gcc_assert (!(for_propagation 268 && TREE_CODE (op) == SSA_NAME 269 && TREE_CODE (val) == SSA_NAME 270 && !may_propagate_copy (op, val))); 271#endif 272 273 if (TREE_CODE (val) == SSA_NAME) 274 { 275 if (TREE_CODE (op) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (op))) 276 merge_alias_info (op, val); 277 SET_USE (op_p, val); 278 } 279 else 280 SET_USE (op_p, unsave_expr_now (val)); 281} 282 283 284/* Propagate the value VAL (assumed to be a constant or another SSA_NAME) 285 into the operand pointed to by OP_P. 286 287 Use this version for const/copy propagation as it will perform additional 288 checks to ensure validity of the const/copy propagation. */ 289 290void 291propagate_value (use_operand_p op_p, tree val) 292{ 293 replace_exp_1 (op_p, val, true); 294} 295 296 297/* Propagate the value VAL (assumed to be a constant or another SSA_NAME) 298 into the tree pointed to by OP_P. 299 300 Use this version for const/copy propagation when SSA operands are not 301 available. It will perform the additional checks to ensure validity of 302 the const/copy propagation, but will not update any operand information. 303 Be sure to mark the stmt as modified. */ 304 305void 306propagate_tree_value (tree *op_p, tree val) 307{ 308#if defined ENABLE_CHECKING 309 gcc_assert (!(TREE_CODE (val) == SSA_NAME 310 && TREE_CODE (*op_p) == SSA_NAME 311 && !may_propagate_copy (*op_p, val))); 312#endif 313 314 if (TREE_CODE (val) == SSA_NAME) 315 { 316 if (TREE_CODE (*op_p) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (*op_p))) 317 merge_alias_info (*op_p, val); 318 *op_p = val; 319 } 320 else 321 *op_p = unsave_expr_now (val); 322} 323 324 325/* Replace *OP_P with value VAL (assumed to be a constant or another SSA_NAME). 326 327 Use this version when not const/copy propagating values. For example, 328 PRE uses this version when building expressions as they would appear 329 in specific blocks taking into account actions of PHI nodes. */ 330 331void 332replace_exp (use_operand_p op_p, tree val) 333{ 334 replace_exp_1 (op_p, val, false); 335} 336 337 338/*--------------------------------------------------------------------------- 339 Copy propagation 340---------------------------------------------------------------------------*/ 341/* During propagation, we keep chains of variables that are copies of 342 one another. If variable X_i is a copy of X_j and X_j is a copy of 343 X_k, COPY_OF will contain: 344 345 COPY_OF[i].VALUE = X_j 346 COPY_OF[j].VALUE = X_k 347 COPY_OF[k].VALUE = X_k 348 349 After propagation, the copy-of value for each variable X_i is 350 converted into the final value by walking the copy-of chains and 351 updating COPY_OF[i].VALUE to be the last element of the chain. */ 352static prop_value_t *copy_of; 353 354/* Used in set_copy_of_val to determine if the last link of a copy-of 355 chain has changed. */ 356static tree *cached_last_copy_of; 357 358/* True if we are doing copy propagation on loads and stores. */ 359static bool do_store_copy_prop; 360 361 362/* Return true if this statement may generate a useful copy. */ 363 364static bool 365stmt_may_generate_copy (tree stmt) 366{ 367 tree lhs, rhs; 368 stmt_ann_t ann; 369 370 if (TREE_CODE (stmt) == PHI_NODE) 371 return !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (stmt)); 372 373 if (TREE_CODE (stmt) != MODIFY_EXPR) 374 return false; 375 376 lhs = TREE_OPERAND (stmt, 0); 377 rhs = TREE_OPERAND (stmt, 1); 378 ann = stmt_ann (stmt); 379 380 /* If the statement has volatile operands, it won't generate a 381 useful copy. */ 382 if (ann->has_volatile_ops) 383 return false; 384 385 /* If we are not doing store copy-prop, statements with loads and/or 386 stores will never generate a useful copy. */ 387 if (!do_store_copy_prop 388 && !ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) 389 return false; 390 391 /* Otherwise, the only statements that generate useful copies are 392 assignments whose RHS is just an SSA name that doesn't flow 393 through abnormal edges. */ 394 return (do_store_copy_prop 395 && TREE_CODE (lhs) == SSA_NAME) 396 || (TREE_CODE (rhs) == SSA_NAME 397 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs)); 398} 399 400 401/* Return the copy-of value for VAR. */ 402 403static inline prop_value_t * 404get_copy_of_val (tree var) 405{ 406 prop_value_t *val = ©_of[SSA_NAME_VERSION (var)]; 407 408 if (val->value == NULL_TREE 409 && !stmt_may_generate_copy (SSA_NAME_DEF_STMT (var))) 410 { 411 /* If the variable will never generate a useful copy relation, 412 make it its own copy. */ 413 val->value = var; 414 val->mem_ref = NULL_TREE; 415 } 416 417 return val; 418} 419 420 421/* Return last link in the copy-of chain for VAR. */ 422 423static tree 424get_last_copy_of (tree var) 425{ 426 tree last; 427 int i; 428 429 /* Traverse COPY_OF starting at VAR until we get to the last 430 link in the chain. Since it is possible to have cycles in PHI 431 nodes, the copy-of chain may also contain cycles. 432 433 To avoid infinite loops and to avoid traversing lengthy copy-of 434 chains, we artificially limit the maximum number of chains we are 435 willing to traverse. 436 437 The value 5 was taken from a compiler and runtime library 438 bootstrap and a mixture of C and C++ code from various sources. 439 More than 82% of all copy-of chains were shorter than 5 links. */ 440#define LIMIT 5 441 442 last = var; 443 for (i = 0; i < LIMIT; i++) 444 { 445 tree copy = copy_of[SSA_NAME_VERSION (last)].value; 446 if (copy == NULL_TREE || copy == last) 447 break; 448 last = copy; 449 } 450 451 /* If we have reached the limit, then we are either in a copy-of 452 cycle or the copy-of chain is too long. In this case, just 453 return VAR so that it is not considered a copy of anything. */ 454 return (i < LIMIT ? last : var); 455} 456 457 458/* Set FIRST to be the first variable in the copy-of chain for DEST. 459 If DEST's copy-of value or its copy-of chain has changed, return 460 true. 461 462 MEM_REF is the memory reference where FIRST is stored. This is 463 used when DEST is a non-register and we are copy propagating loads 464 and stores. */ 465 466static inline bool 467set_copy_of_val (tree dest, tree first, tree mem_ref) 468{ 469 unsigned int dest_ver = SSA_NAME_VERSION (dest); 470 tree old_first, old_last, new_last; 471 472 /* Set FIRST to be the first link in COPY_OF[DEST]. If that 473 changed, return true. */ 474 old_first = copy_of[dest_ver].value; 475 copy_of[dest_ver].value = first; 476 copy_of[dest_ver].mem_ref = mem_ref; 477 478 if (old_first != first) 479 return true; 480 481 /* If FIRST and OLD_FIRST are the same, we need to check whether the 482 copy-of chain starting at FIRST ends in a different variable. If 483 the copy-of chain starting at FIRST ends up in a different 484 variable than the last cached value we had for DEST, then return 485 true because DEST is now a copy of a different variable. 486 487 This test is necessary because even though the first link in the 488 copy-of chain may not have changed, if any of the variables in 489 the copy-of chain changed its final value, DEST will now be the 490 copy of a different variable, so we have to do another round of 491 propagation for everything that depends on DEST. */ 492 old_last = cached_last_copy_of[dest_ver]; 493 new_last = get_last_copy_of (dest); 494 cached_last_copy_of[dest_ver] = new_last; 495 496 return (old_last != new_last); 497} 498 499 500/* Dump the copy-of value for variable VAR to FILE. */ 501 502static void 503dump_copy_of (FILE *file, tree var) 504{ 505 tree val; 506 sbitmap visited; 507 508 print_generic_expr (file, var, dump_flags); 509 510 if (TREE_CODE (var) != SSA_NAME) 511 return; 512 513 visited = sbitmap_alloc (num_ssa_names); 514 sbitmap_zero (visited); 515 SET_BIT (visited, SSA_NAME_VERSION (var)); 516 517 fprintf (file, " copy-of chain: "); 518 519 val = var; 520 print_generic_expr (file, val, 0); 521 fprintf (file, " "); 522 while (copy_of[SSA_NAME_VERSION (val)].value) 523 { 524 fprintf (file, "-> "); 525 val = copy_of[SSA_NAME_VERSION (val)].value; 526 print_generic_expr (file, val, 0); 527 fprintf (file, " "); 528 if (TEST_BIT (visited, SSA_NAME_VERSION (val))) 529 break; 530 SET_BIT (visited, SSA_NAME_VERSION (val)); 531 } 532 533 val = get_copy_of_val (var)->value; 534 if (val == NULL_TREE) 535 fprintf (file, "[UNDEFINED]"); 536 else if (val != var) 537 fprintf (file, "[COPY]"); 538 else 539 fprintf (file, "[NOT A COPY]"); 540 541 sbitmap_free (visited); 542} 543 544 545/* Evaluate the RHS of STMT. If it produces a valid copy, set the LHS 546 value and store the LHS into *RESULT_P. If STMT generates more 547 than one name (i.e., STMT is an aliased store), it is enough to 548 store the first name in the V_MAY_DEF list into *RESULT_P. After 549 all, the names generated will be VUSEd in the same statements. */ 550 551static enum ssa_prop_result 552copy_prop_visit_assignment (tree stmt, tree *result_p) 553{ 554 tree lhs, rhs; 555 prop_value_t *rhs_val; 556 557 lhs = TREE_OPERAND (stmt, 0); 558 rhs = TREE_OPERAND (stmt, 1); 559 560 gcc_assert (TREE_CODE (rhs) == SSA_NAME); 561 562 rhs_val = get_copy_of_val (rhs); 563 564 if (TREE_CODE (lhs) == SSA_NAME) 565 { 566 /* Straight copy between two SSA names. First, make sure that 567 we can propagate the RHS into uses of LHS. */ 568 if (!may_propagate_copy (lhs, rhs)) 569 return SSA_PROP_VARYING; 570 571 /* Notice that in the case of assignments, we make the LHS be a 572 copy of RHS's value, not of RHS itself. This avoids keeping 573 unnecessary copy-of chains (assignments cannot be in a cycle 574 like PHI nodes), speeding up the propagation process. 575 This is different from what we do in copy_prop_visit_phi_node. 576 In those cases, we are interested in the copy-of chains. */ 577 *result_p = lhs; 578 if (set_copy_of_val (*result_p, rhs_val->value, rhs_val->mem_ref)) 579 return SSA_PROP_INTERESTING; 580 else 581 return SSA_PROP_NOT_INTERESTING; 582 } 583 else if (stmt_makes_single_store (stmt)) 584 { 585 /* Otherwise, set the names in V_MAY_DEF/V_MUST_DEF operands 586 to be a copy of RHS. */ 587 ssa_op_iter i; 588 tree vdef; 589 bool changed; 590 591 /* This should only be executed when doing store copy-prop. */ 592 gcc_assert (do_store_copy_prop); 593 594 /* Set the value of every VDEF to RHS_VAL. */ 595 changed = false; 596 FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, i, SSA_OP_VIRTUAL_DEFS) 597 changed |= set_copy_of_val (vdef, rhs_val->value, lhs); 598 599 /* Note that for propagation purposes, we are only interested in 600 visiting statements that load the exact same memory reference 601 stored here. Those statements will have the exact same list 602 of virtual uses, so it is enough to set the output of this 603 statement to be its first virtual definition. */ 604 *result_p = first_vdef (stmt); 605 606 if (changed) 607 return SSA_PROP_INTERESTING; 608 else 609 return SSA_PROP_NOT_INTERESTING; 610 } 611 612 613 return SSA_PROP_VARYING; 614} 615 616 617/* Visit the COND_EXPR STMT. Return SSA_PROP_INTERESTING 618 if it can determine which edge will be taken. Otherwise, return 619 SSA_PROP_VARYING. */ 620 621static enum ssa_prop_result 622copy_prop_visit_cond_stmt (tree stmt, edge *taken_edge_p) 623{ 624 enum ssa_prop_result retval; 625 tree cond; 626 627 cond = COND_EXPR_COND (stmt); 628 retval = SSA_PROP_VARYING; 629 630 /* The only conditionals that we may be able to compute statically 631 are predicates involving two SSA_NAMEs. */ 632 if (COMPARISON_CLASS_P (cond) 633 && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME 634 && TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME) 635 { 636 tree op0 = get_last_copy_of (TREE_OPERAND (cond, 0)); 637 tree op1 = get_last_copy_of (TREE_OPERAND (cond, 1)); 638 639 /* See if we can determine the predicate's value. */ 640 if (dump_file && (dump_flags & TDF_DETAILS)) 641 { 642 fprintf (dump_file, "Trying to determine truth value of "); 643 fprintf (dump_file, "predicate "); 644 print_generic_stmt (dump_file, cond, 0); 645 } 646 647 /* We can fold COND and get a useful result only when we have 648 the same SSA_NAME on both sides of a comparison operator. */ 649 if (op0 == op1) 650 { 651 tree folded_cond = fold_binary (TREE_CODE (cond), boolean_type_node, 652 op0, op1); 653 if (folded_cond) 654 { 655 basic_block bb = bb_for_stmt (stmt); 656 *taken_edge_p = find_taken_edge (bb, folded_cond); 657 if (*taken_edge_p) 658 retval = SSA_PROP_INTERESTING; 659 } 660 } 661 } 662 663 if (dump_file && (dump_flags & TDF_DETAILS) && *taken_edge_p) 664 fprintf (dump_file, "\nConditional will always take edge %d->%d\n", 665 (*taken_edge_p)->src->index, (*taken_edge_p)->dest->index); 666 667 return retval; 668} 669 670 671/* Evaluate statement STMT. If the statement produces a new output 672 value, return SSA_PROP_INTERESTING and store the SSA_NAME holding 673 the new value in *RESULT_P. 674 675 If STMT is a conditional branch and we can determine its truth 676 value, set *TAKEN_EDGE_P accordingly. 677 678 If the new value produced by STMT is varying, return 679 SSA_PROP_VARYING. */ 680 681static enum ssa_prop_result 682copy_prop_visit_stmt (tree stmt, edge *taken_edge_p, tree *result_p) 683{ 684 enum ssa_prop_result retval; 685 686 if (dump_file && (dump_flags & TDF_DETAILS)) 687 { 688 fprintf (dump_file, "\nVisiting statement:\n"); 689 print_generic_stmt (dump_file, stmt, dump_flags); 690 fprintf (dump_file, "\n"); 691 } 692 693 if (TREE_CODE (stmt) == MODIFY_EXPR 694 && TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME 695 && (do_store_copy_prop 696 || TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME)) 697 { 698 /* If the statement is a copy assignment, evaluate its RHS to 699 see if the lattice value of its output has changed. */ 700 retval = copy_prop_visit_assignment (stmt, result_p); 701 } 702 else if (TREE_CODE (stmt) == MODIFY_EXPR 703 && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME 704 && do_store_copy_prop 705 && stmt_makes_single_load (stmt)) 706 { 707 /* If the statement is a copy assignment with a memory load 708 on the RHS, see if we know the value of this load and 709 update the lattice accordingly. */ 710 prop_value_t *val = get_value_loaded_by (stmt, copy_of); 711 if (val 712 && val->mem_ref 713 && is_gimple_reg (val->value) 714 && operand_equal_p (val->mem_ref, TREE_OPERAND (stmt, 1), 0)) 715 { 716 bool changed; 717 changed = set_copy_of_val (TREE_OPERAND (stmt, 0), 718 val->value, val->mem_ref); 719 if (changed) 720 { 721 *result_p = TREE_OPERAND (stmt, 0); 722 retval = SSA_PROP_INTERESTING; 723 } 724 else 725 retval = SSA_PROP_NOT_INTERESTING; 726 } 727 else 728 retval = SSA_PROP_VARYING; 729 } 730 else if (TREE_CODE (stmt) == COND_EXPR) 731 { 732 /* See if we can determine which edge goes out of a conditional 733 jump. */ 734 retval = copy_prop_visit_cond_stmt (stmt, taken_edge_p); 735 } 736 else 737 retval = SSA_PROP_VARYING; 738 739 if (retval == SSA_PROP_VARYING) 740 { 741 tree def; 742 ssa_op_iter i; 743 744 /* Any other kind of statement is not interesting for constant 745 propagation and, therefore, not worth simulating. */ 746 if (dump_file && (dump_flags & TDF_DETAILS)) 747 fprintf (dump_file, "No interesting values produced.\n"); 748 749 /* The assignment is not a copy operation. Don't visit this 750 statement again and mark all the definitions in the statement 751 to be copies of nothing. */ 752 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_ALL_DEFS) 753 set_copy_of_val (def, def, NULL_TREE); 754 } 755 756 return retval; 757} 758 759 760/* Visit PHI node PHI. If all the arguments produce the same value, 761 set it to be the value of the LHS of PHI. */ 762 763static enum ssa_prop_result 764copy_prop_visit_phi_node (tree phi) 765{ 766 enum ssa_prop_result retval; 767 int i; 768 tree lhs; 769 prop_value_t phi_val = { 0, NULL_TREE, NULL_TREE }; 770 771 lhs = PHI_RESULT (phi); 772 773 if (dump_file && (dump_flags & TDF_DETAILS)) 774 { 775 fprintf (dump_file, "\nVisiting PHI node: "); 776 print_generic_expr (dump_file, phi, dump_flags); 777 fprintf (dump_file, "\n\n"); 778 } 779 780 for (i = 0; i < PHI_NUM_ARGS (phi); i++) 781 { 782 prop_value_t *arg_val; 783 tree arg = PHI_ARG_DEF (phi, i); 784 edge e = PHI_ARG_EDGE (phi, i); 785 786 /* We don't care about values flowing through non-executable 787 edges. */ 788 if (!(e->flags & EDGE_EXECUTABLE)) 789 continue; 790 791 /* Constants in the argument list never generate a useful copy. 792 Similarly, names that flow through abnormal edges cannot be 793 used to derive copies. */ 794 if (TREE_CODE (arg) != SSA_NAME || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg)) 795 { 796 phi_val.value = lhs; 797 break; 798 } 799 800 /* Avoid copy propagation from an inner into an outer loop. 801 Otherwise, this may move loop variant variables outside of 802 their loops and prevent coalescing opportunities. If the 803 value was loop invariant, it will be hoisted by LICM and 804 exposed for copy propagation. */ 805 if (loop_depth_of_name (arg) > loop_depth_of_name (lhs)) 806 { 807 phi_val.value = lhs; 808 break; 809 } 810 811 /* If the LHS appears in the argument list, ignore it. It is 812 irrelevant as a copy. */ 813 if (arg == lhs || get_last_copy_of (arg) == lhs) 814 continue; 815 816 if (dump_file && (dump_flags & TDF_DETAILS)) 817 { 818 fprintf (dump_file, "\tArgument #%d: ", i); 819 dump_copy_of (dump_file, arg); 820 fprintf (dump_file, "\n"); 821 } 822 823 arg_val = get_copy_of_val (arg); 824 825 /* If the LHS didn't have a value yet, make it a copy of the 826 first argument we find. Notice that while we make the LHS be 827 a copy of the argument itself, we take the memory reference 828 from the argument's value so that we can compare it to the 829 memory reference of all the other arguments. */ 830 if (phi_val.value == NULL_TREE) 831 { 832 phi_val.value = arg; 833 phi_val.mem_ref = arg_val->mem_ref; 834 continue; 835 } 836 837 /* If PHI_VAL and ARG don't have a common copy-of chain, then 838 this PHI node cannot be a copy operation. Also, if we are 839 copy propagating stores and these two arguments came from 840 different memory references, they cannot be considered 841 copies. */ 842 if (get_last_copy_of (phi_val.value) != get_last_copy_of (arg) 843 || (do_store_copy_prop 844 && phi_val.mem_ref 845 && arg_val->mem_ref 846 && simple_cst_equal (phi_val.mem_ref, arg_val->mem_ref) != 1)) 847 { 848 phi_val.value = lhs; 849 break; 850 } 851 } 852 853 if (phi_val.value && set_copy_of_val (lhs, phi_val.value, phi_val.mem_ref)) 854 retval = (phi_val.value != lhs) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING; 855 else 856 retval = SSA_PROP_NOT_INTERESTING; 857 858 if (dump_file && (dump_flags & TDF_DETAILS)) 859 { 860 fprintf (dump_file, "\nPHI node "); 861 dump_copy_of (dump_file, lhs); 862 fprintf (dump_file, "\nTelling the propagator to "); 863 if (retval == SSA_PROP_INTERESTING) 864 fprintf (dump_file, "add SSA edges out of this PHI and continue."); 865 else if (retval == SSA_PROP_VARYING) 866 fprintf (dump_file, "add SSA edges out of this PHI and never visit again."); 867 else 868 fprintf (dump_file, "do nothing with SSA edges and keep iterating."); 869 fprintf (dump_file, "\n\n"); 870 } 871 872 return retval; 873} 874 875 876/* Initialize structures used for copy propagation. PHIS_ONLY is true 877 if we should only consider PHI nodes as generating copy propagation 878 opportunities. */ 879 880static void 881init_copy_prop (void) 882{ 883 basic_block bb; 884 885 copy_of = XNEWVEC (prop_value_t, num_ssa_names); 886 memset (copy_of, 0, num_ssa_names * sizeof (*copy_of)); 887 888 cached_last_copy_of = XNEWVEC (tree, num_ssa_names); 889 memset (cached_last_copy_of, 0, num_ssa_names * sizeof (*cached_last_copy_of)); 890 891 FOR_EACH_BB (bb) 892 { 893 block_stmt_iterator si; 894 tree phi, def; 895 int depth = bb->loop_depth; 896 897 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) 898 { 899 tree stmt = bsi_stmt (si); 900 ssa_op_iter iter; 901 902 /* The only statements that we care about are those that may 903 generate useful copies. We also need to mark conditional 904 jumps so that their outgoing edges are added to the work 905 lists of the propagator. 906 907 Avoid copy propagation from an inner into an outer loop. 908 Otherwise, this may move loop variant variables outside of 909 their loops and prevent coalescing opportunities. If the 910 value was loop invariant, it will be hoisted by LICM and 911 exposed for copy propagation. */ 912 if (stmt_ends_bb_p (stmt)) 913 DONT_SIMULATE_AGAIN (stmt) = false; 914 else if (stmt_may_generate_copy (stmt) 915 && loop_depth_of_name (TREE_OPERAND (stmt, 1)) <= depth) 916 DONT_SIMULATE_AGAIN (stmt) = false; 917 else 918 DONT_SIMULATE_AGAIN (stmt) = true; 919 920 /* Mark all the outputs of this statement as not being 921 the copy of anything. */ 922 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) 923 if (DONT_SIMULATE_AGAIN (stmt)) 924 set_copy_of_val (def, def, NULL_TREE); 925 else 926 cached_last_copy_of[SSA_NAME_VERSION (def)] = def; 927 } 928 929 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 930 { 931 def = PHI_RESULT (phi); 932 if (!do_store_copy_prop && !is_gimple_reg (def)) 933 DONT_SIMULATE_AGAIN (phi) = true; 934 else 935 DONT_SIMULATE_AGAIN (phi) = false; 936 937 if (DONT_SIMULATE_AGAIN (phi)) 938 set_copy_of_val (def, def, NULL_TREE); 939 else 940 cached_last_copy_of[SSA_NAME_VERSION (def)] = def; 941 } 942 } 943} 944 945 946/* Deallocate memory used in copy propagation and do final 947 substitution. */ 948 949static void 950fini_copy_prop (void) 951{ 952 size_t i; 953 prop_value_t *tmp; 954 955 /* Set the final copy-of value for each variable by traversing the 956 copy-of chains. */ 957 tmp = XNEWVEC (prop_value_t, num_ssa_names); 958 memset (tmp, 0, num_ssa_names * sizeof (*tmp)); 959 for (i = 1; i < num_ssa_names; i++) 960 { 961 tree var = ssa_name (i); 962 if (var && copy_of[i].value && copy_of[i].value != var) 963 tmp[i].value = get_last_copy_of (var); 964 } 965 966 substitute_and_fold (tmp, false); 967 968 free (cached_last_copy_of); 969 free (copy_of); 970 free (tmp); 971} 972 973 974/* Main entry point to the copy propagator. 975 976 PHIS_ONLY is true if we should only consider PHI nodes as generating 977 copy propagation opportunities. 978 979 The algorithm propagates the value COPY-OF using ssa_propagate. For 980 every variable X_i, COPY-OF(X_i) indicates which variable is X_i created 981 from. The following example shows how the algorithm proceeds at a 982 high level: 983 984 1 a_24 = x_1 985 2 a_2 = PHI <a_24, x_1> 986 3 a_5 = PHI <a_2> 987 4 x_1 = PHI <x_298, a_5, a_2> 988 989 The end result should be that a_2, a_5, a_24 and x_1 are a copy of 990 x_298. Propagation proceeds as follows. 991 992 Visit #1: a_24 is copy-of x_1. Value changed. 993 Visit #2: a_2 is copy-of x_1. Value changed. 994 Visit #3: a_5 is copy-of x_1. Value changed. 995 Visit #4: x_1 is copy-of x_298. Value changed. 996 Visit #1: a_24 is copy-of x_298. Value changed. 997 Visit #2: a_2 is copy-of x_298. Value changed. 998 Visit #3: a_5 is copy-of x_298. Value changed. 999 Visit #4: x_1 is copy-of x_298. Stable state reached. 1000 1001 When visiting PHI nodes, we only consider arguments that flow 1002 through edges marked executable by the propagation engine. So, 1003 when visiting statement #2 for the first time, we will only look at 1004 the first argument (a_24) and optimistically assume that its value 1005 is the copy of a_24 (x_1). 1006 1007 The problem with this approach is that it may fail to discover copy 1008 relations in PHI cycles. Instead of propagating copy-of 1009 values, we actually propagate copy-of chains. For instance: 1010 1011 A_3 = B_1; 1012 C_9 = A_3; 1013 D_4 = C_9; 1014 X_i = D_4; 1015 1016 In this code fragment, COPY-OF (X_i) = { D_4, C_9, A_3, B_1 }. 1017 Obviously, we are only really interested in the last value of the 1018 chain, however the propagator needs to access the copy-of chain 1019 when visiting PHI nodes. 1020 1021 To represent the copy-of chain, we use the array COPY_CHAINS, which 1022 holds the first link in the copy-of chain for every variable. 1023 If variable X_i is a copy of X_j, which in turn is a copy of X_k, 1024 the array will contain: 1025 1026 COPY_CHAINS[i] = X_j 1027 COPY_CHAINS[j] = X_k 1028 COPY_CHAINS[k] = X_k 1029 1030 Keeping copy-of chains instead of copy-of values directly becomes 1031 important when visiting PHI nodes. Suppose that we had the 1032 following PHI cycle, such that x_52 is already considered a copy of 1033 x_53: 1034 1035 1 x_54 = PHI <x_53, x_52> 1036 2 x_53 = PHI <x_898, x_54> 1037 1038 Visit #1: x_54 is copy-of x_53 (because x_52 is copy-of x_53) 1039 Visit #2: x_53 is copy-of x_898 (because x_54 is a copy of x_53, 1040 so it is considered irrelevant 1041 as a copy). 1042 Visit #1: x_54 is copy-of nothing (x_53 is a copy-of x_898 and 1043 x_52 is a copy of x_53, so 1044 they don't match) 1045 Visit #2: x_53 is copy-of nothing 1046 1047 This problem is avoided by keeping a chain of copies, instead of 1048 the final copy-of value. Propagation will now only keep the first 1049 element of a variable's copy-of chain. When visiting PHI nodes, 1050 arguments are considered equal if their copy-of chains end in the 1051 same variable. So, as long as their copy-of chains overlap, we 1052 know that they will be a copy of the same variable, regardless of 1053 which variable that may be). 1054 1055 Propagation would then proceed as follows (the notation a -> b 1056 means that a is a copy-of b): 1057 1058 Visit #1: x_54 = PHI <x_53, x_52> 1059 x_53 -> x_53 1060 x_52 -> x_53 1061 Result: x_54 -> x_53. Value changed. Add SSA edges. 1062 1063 Visit #1: x_53 = PHI <x_898, x_54> 1064 x_898 -> x_898 1065 x_54 -> x_53 1066 Result: x_53 -> x_898. Value changed. Add SSA edges. 1067 1068 Visit #2: x_54 = PHI <x_53, x_52> 1069 x_53 -> x_898 1070 x_52 -> x_53 -> x_898 1071 Result: x_54 -> x_898. Value changed. Add SSA edges. 1072 1073 Visit #2: x_53 = PHI <x_898, x_54> 1074 x_898 -> x_898 1075 x_54 -> x_898 1076 Result: x_53 -> x_898. Value didn't change. Stable state 1077 1078 Once the propagator stabilizes, we end up with the desired result 1079 x_53 and x_54 are both copies of x_898. */ 1080 1081static void 1082execute_copy_prop (bool store_copy_prop) 1083{ 1084 do_store_copy_prop = store_copy_prop; 1085 init_copy_prop (); 1086 ssa_propagate (copy_prop_visit_stmt, copy_prop_visit_phi_node); 1087 fini_copy_prop (); 1088} 1089 1090 1091static bool 1092gate_copy_prop (void) 1093{ 1094 return flag_tree_copy_prop != 0; 1095} 1096 1097static unsigned int 1098do_copy_prop (void) 1099{ 1100 execute_copy_prop (false); 1101 return 0; 1102} 1103 1104struct tree_opt_pass pass_copy_prop = 1105{ 1106 "copyprop", /* name */ 1107 gate_copy_prop, /* gate */ 1108 do_copy_prop, /* execute */ 1109 NULL, /* sub */ 1110 NULL, /* next */ 1111 0, /* static_pass_number */ 1112 TV_TREE_COPY_PROP, /* tv_id */ 1113 PROP_ssa | PROP_alias | PROP_cfg, /* properties_required */ 1114 0, /* properties_provided */ 1115 0, /* properties_destroyed */ 1116 0, /* todo_flags_start */ 1117 TODO_cleanup_cfg 1118 | TODO_dump_func 1119 | TODO_ggc_collect 1120 | TODO_verify_ssa 1121 | TODO_update_ssa, /* todo_flags_finish */ 1122 0 /* letter */ 1123}; 1124 1125static bool 1126gate_store_copy_prop (void) 1127{ 1128 /* STORE-COPY-PROP is enabled only with -ftree-store-copy-prop, but 1129 when -fno-tree-store-copy-prop is specified, we should run 1130 regular COPY-PROP. That's why the pass is enabled with either 1131 flag. */ 1132 return flag_tree_store_copy_prop != 0 || flag_tree_copy_prop != 0; 1133} 1134 1135static unsigned int 1136store_copy_prop (void) 1137{ 1138 /* If STORE-COPY-PROP is not enabled, we just run regular COPY-PROP. */ 1139 execute_copy_prop (flag_tree_store_copy_prop != 0); 1140 return 0; 1141} 1142 1143struct tree_opt_pass pass_store_copy_prop = 1144{ 1145 "store_copyprop", /* name */ 1146 gate_store_copy_prop, /* gate */ 1147 store_copy_prop, /* execute */ 1148 NULL, /* sub */ 1149 NULL, /* next */ 1150 0, /* static_pass_number */ 1151 TV_TREE_STORE_COPY_PROP, /* tv_id */ 1152 PROP_ssa | PROP_alias | PROP_cfg, /* properties_required */ 1153 0, /* properties_provided */ 1154 0, /* properties_destroyed */ 1155 0, /* todo_flags_start */ 1156 TODO_dump_func 1157 | TODO_cleanup_cfg 1158 | TODO_ggc_collect 1159 | TODO_verify_ssa 1160 | TODO_update_ssa, /* todo_flags_finish */ 1161 0 /* letter */ 1162}; 1163