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))->type_mem_tag; 112 tree mt_orig = var_ann (SSA_NAME_VAR (orig))->type_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 type tags. If both pointers had a tag and they 206 are different, then something has gone wrong. Type tags can 207 always be merged because they are flow insensitive, all the SSA 208 names of the same base DECL share the same type tag. */ 209 if (new_ann->type_mem_tag == NULL_TREE) 210 new_ann->type_mem_tag = orig_ann->type_mem_tag; 211 else if (orig_ann->type_mem_tag == NULL_TREE) 212 orig_ann->type_mem_tag = new_ann->type_mem_tag; 213 else 214 gcc_assert (new_ann->type_mem_tag == orig_ann->type_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 TREE_CODE (rhs) == SSA_NAME && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs); 395} 396 397 398/* Return the copy-of value for VAR. */ 399 400static inline prop_value_t * 401get_copy_of_val (tree var) 402{ 403 prop_value_t *val = ©_of[SSA_NAME_VERSION (var)]; 404 405 if (val->value == NULL_TREE 406 && !stmt_may_generate_copy (SSA_NAME_DEF_STMT (var))) 407 { 408 /* If the variable will never generate a useful copy relation, 409 make it its own copy. */ 410 val->value = var; 411 val->mem_ref = NULL_TREE; 412 } 413 414 return val; 415} 416 417 418/* Return last link in the copy-of chain for VAR. */ 419 420static tree 421get_last_copy_of (tree var) 422{ 423 tree last; 424 int i; 425 426 /* Traverse COPY_OF starting at VAR until we get to the last 427 link in the chain. Since it is possible to have cycles in PHI 428 nodes, the copy-of chain may also contain cycles. 429 430 To avoid infinite loops and to avoid traversing lengthy copy-of 431 chains, we artificially limit the maximum number of chains we are 432 willing to traverse. 433 434 The value 5 was taken from a compiler and runtime library 435 bootstrap and a mixture of C and C++ code from various sources. 436 More than 82% of all copy-of chains were shorter than 5 links. */ 437#define LIMIT 5 438 439 last = var; 440 for (i = 0; i < LIMIT; i++) 441 { 442 tree copy = copy_of[SSA_NAME_VERSION (last)].value; 443 if (copy == NULL_TREE || copy == last) 444 break; 445 last = copy; 446 } 447 448 /* If we have reached the limit, then we are either in a copy-of 449 cycle or the copy-of chain is too long. In this case, just 450 return VAR so that it is not considered a copy of anything. */ 451 return (i < LIMIT ? last : var); 452} 453 454 455/* Set FIRST to be the first variable in the copy-of chain for DEST. 456 If DEST's copy-of value or its copy-of chain has changed, return 457 true. 458 459 MEM_REF is the memory reference where FIRST is stored. This is 460 used when DEST is a non-register and we are copy propagating loads 461 and stores. */ 462 463static inline bool 464set_copy_of_val (tree dest, tree first, tree mem_ref) 465{ 466 unsigned int dest_ver = SSA_NAME_VERSION (dest); 467 tree old_first, old_last, new_last; 468 469 /* Set FIRST to be the first link in COPY_OF[DEST]. If that 470 changed, return true. */ 471 old_first = copy_of[dest_ver].value; 472 copy_of[dest_ver].value = first; 473 copy_of[dest_ver].mem_ref = mem_ref; 474 475 if (old_first != first) 476 return true; 477 478 /* If FIRST and OLD_FIRST are the same, we need to check whether the 479 copy-of chain starting at FIRST ends in a different variable. If 480 the copy-of chain starting at FIRST ends up in a different 481 variable than the last cached value we had for DEST, then return 482 true because DEST is now a copy of a different variable. 483 484 This test is necessary because even though the first link in the 485 copy-of chain may not have changed, if any of the variables in 486 the copy-of chain changed its final value, DEST will now be the 487 copy of a different variable, so we have to do another round of 488 propagation for everything that depends on DEST. */ 489 old_last = cached_last_copy_of[dest_ver]; 490 new_last = get_last_copy_of (dest); 491 cached_last_copy_of[dest_ver] = new_last; 492 493 return (old_last != new_last); 494} 495 496 497/* Dump the copy-of value for variable VAR to DUMP_FILE. */ 498 499static void 500dump_copy_of (FILE *dump_file, tree var) 501{ 502 tree val; 503 sbitmap visited; 504 505 print_generic_expr (dump_file, var, dump_flags); 506 507 if (TREE_CODE (var) != SSA_NAME) 508 return; 509 510 visited = sbitmap_alloc (num_ssa_names); 511 sbitmap_zero (visited); 512 SET_BIT (visited, SSA_NAME_VERSION (var)); 513 514 fprintf (dump_file, " copy-of chain: "); 515 516 val = var; 517 print_generic_expr (dump_file, val, 0); 518 fprintf (dump_file, " "); 519 while (copy_of[SSA_NAME_VERSION (val)].value) 520 { 521 fprintf (dump_file, "-> "); 522 val = copy_of[SSA_NAME_VERSION (val)].value; 523 print_generic_expr (dump_file, val, 0); 524 fprintf (dump_file, " "); 525 if (TEST_BIT (visited, SSA_NAME_VERSION (val))) 526 break; 527 SET_BIT (visited, SSA_NAME_VERSION (val)); 528 } 529 530 val = get_copy_of_val (var)->value; 531 if (val == NULL_TREE) 532 fprintf (dump_file, "[UNDEFINED]"); 533 else if (val != var) 534 fprintf (dump_file, "[COPY]"); 535 else 536 fprintf (dump_file, "[NOT A COPY]"); 537 538 sbitmap_free (visited); 539} 540 541 542/* Evaluate the RHS of STMT. If it produces a valid copy, set the LHS 543 value and store the LHS into *RESULT_P. If STMT generates more 544 than one name (i.e., STMT is an aliased store), it is enough to 545 store the first name in the V_MAY_DEF list into *RESULT_P. After 546 all, the names generated will be VUSEd in the same statements. */ 547 548static enum ssa_prop_result 549copy_prop_visit_assignment (tree stmt, tree *result_p) 550{ 551 tree lhs, rhs; 552 prop_value_t *rhs_val; 553 554 lhs = TREE_OPERAND (stmt, 0); 555 rhs = TREE_OPERAND (stmt, 1); 556 557 gcc_assert (TREE_CODE (rhs) == SSA_NAME); 558 559 rhs_val = get_copy_of_val (rhs); 560 561 if (TREE_CODE (lhs) == SSA_NAME) 562 { 563 /* Straight copy between two SSA names. First, make sure that 564 we can propagate the RHS into uses of LHS. */ 565 if (!may_propagate_copy (lhs, rhs)) 566 return SSA_PROP_VARYING; 567 568 /* Notice that in the case of assignments, we make the LHS be a 569 copy of RHS's value, not of RHS itself. This avoids keeping 570 unnecessary copy-of chains (assignments cannot be in a cycle 571 like PHI nodes), speeding up the propagation process. 572 This is different from what we do in copy_prop_visit_phi_node. 573 In those cases, we are interested in the copy-of chains. */ 574 *result_p = lhs; 575 if (set_copy_of_val (*result_p, rhs_val->value, rhs_val->mem_ref)) 576 return SSA_PROP_INTERESTING; 577 else 578 return SSA_PROP_NOT_INTERESTING; 579 } 580 else if (stmt_makes_single_store (stmt)) 581 { 582 /* Otherwise, set the names in V_MAY_DEF/V_MUST_DEF operands 583 to be a copy of RHS. */ 584 ssa_op_iter i; 585 tree vdef; 586 bool changed; 587 588 /* This should only be executed when doing store copy-prop. */ 589 gcc_assert (do_store_copy_prop); 590 591 /* Set the value of every VDEF to RHS_VAL. */ 592 changed = false; 593 FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, i, SSA_OP_VIRTUAL_DEFS) 594 changed |= set_copy_of_val (vdef, rhs_val->value, lhs); 595 596 /* Note that for propagation purposes, we are only interested in 597 visiting statements that load the exact same memory reference 598 stored here. Those statements will have the exact same list 599 of virtual uses, so it is enough to set the output of this 600 statement to be its first virtual definition. */ 601 *result_p = first_vdef (stmt); 602 603 if (changed) 604 return SSA_PROP_INTERESTING; 605 else 606 return SSA_PROP_NOT_INTERESTING; 607 } 608 609 610 return SSA_PROP_VARYING; 611} 612 613 614/* Visit the COND_EXPR STMT. Return SSA_PROP_INTERESTING 615 if it can determine which edge will be taken. Otherwise, return 616 SSA_PROP_VARYING. */ 617 618static enum ssa_prop_result 619copy_prop_visit_cond_stmt (tree stmt, edge *taken_edge_p) 620{ 621 enum ssa_prop_result retval; 622 tree cond; 623 624 cond = COND_EXPR_COND (stmt); 625 retval = SSA_PROP_VARYING; 626 627 /* The only conditionals that we may be able to compute statically 628 are predicates involving two SSA_NAMEs. */ 629 if (COMPARISON_CLASS_P (cond) 630 && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME 631 && TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME) 632 { 633 tree op0 = get_last_copy_of (TREE_OPERAND (cond, 0)); 634 tree op1 = get_last_copy_of (TREE_OPERAND (cond, 1)); 635 636 /* See if we can determine the predicate's value. */ 637 if (dump_file && (dump_flags & TDF_DETAILS)) 638 { 639 fprintf (dump_file, "Trying to determine truth value of "); 640 fprintf (dump_file, "predicate "); 641 print_generic_stmt (dump_file, cond, 0); 642 } 643 644 /* We can fold COND and get a useful result only when we have 645 the same SSA_NAME on both sides of a comparison operator. */ 646 if (op0 == op1) 647 { 648 tree folded_cond = fold_binary (TREE_CODE (cond), boolean_type_node, 649 op0, op1); 650 if (folded_cond) 651 { 652 basic_block bb = bb_for_stmt (stmt); 653 *taken_edge_p = find_taken_edge (bb, folded_cond); 654 if (*taken_edge_p) 655 retval = SSA_PROP_INTERESTING; 656 } 657 } 658 } 659 660 if (dump_file && (dump_flags & TDF_DETAILS) && *taken_edge_p) 661 fprintf (dump_file, "\nConditional will always take edge %d->%d\n", 662 (*taken_edge_p)->src->index, (*taken_edge_p)->dest->index); 663 664 return retval; 665} 666 667 668/* Evaluate statement STMT. If the statement produces a new output 669 value, return SSA_PROP_INTERESTING and store the SSA_NAME holding 670 the new value in *RESULT_P. 671 672 If STMT is a conditional branch and we can determine its truth 673 value, set *TAKEN_EDGE_P accordingly. 674 675 If the new value produced by STMT is varying, return 676 SSA_PROP_VARYING. */ 677 678static enum ssa_prop_result 679copy_prop_visit_stmt (tree stmt, edge *taken_edge_p, tree *result_p) 680{ 681 enum ssa_prop_result retval; 682 683 if (dump_file && (dump_flags & TDF_DETAILS)) 684 { 685 fprintf (dump_file, "\nVisiting statement:\n"); 686 print_generic_stmt (dump_file, stmt, dump_flags); 687 fprintf (dump_file, "\n"); 688 } 689 690 if (TREE_CODE (stmt) == MODIFY_EXPR 691 && TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME 692 && (do_store_copy_prop 693 || TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME)) 694 { 695 /* If the statement is a copy assignment, evaluate its RHS to 696 see if the lattice value of its output has changed. */ 697 retval = copy_prop_visit_assignment (stmt, result_p); 698 } 699 else if (TREE_CODE (stmt) == COND_EXPR) 700 { 701 /* See if we can determine which edge goes out of a conditional 702 jump. */ 703 retval = copy_prop_visit_cond_stmt (stmt, taken_edge_p); 704 } 705 else 706 retval = SSA_PROP_VARYING; 707 708 if (retval == SSA_PROP_VARYING) 709 { 710 tree def; 711 ssa_op_iter i; 712 713 /* Any other kind of statement is not interesting for constant 714 propagation and, therefore, not worth simulating. */ 715 if (dump_file && (dump_flags & TDF_DETAILS)) 716 fprintf (dump_file, "No interesting values produced.\n"); 717 718 /* The assignment is not a copy operation. Don't visit this 719 statement again and mark all the definitions in the statement 720 to be copies of nothing. */ 721 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_ALL_DEFS) 722 set_copy_of_val (def, def, NULL_TREE); 723 } 724 725 return retval; 726} 727 728 729/* Visit PHI node PHI. If all the arguments produce the same value, 730 set it to be the value of the LHS of PHI. */ 731 732static enum ssa_prop_result 733copy_prop_visit_phi_node (tree phi) 734{ 735 enum ssa_prop_result retval; 736 int i; 737 tree lhs; 738 prop_value_t phi_val = { 0, NULL_TREE, NULL_TREE }; 739 740 lhs = PHI_RESULT (phi); 741 742 if (dump_file && (dump_flags & TDF_DETAILS)) 743 { 744 fprintf (dump_file, "\nVisiting PHI node: "); 745 print_generic_expr (dump_file, phi, dump_flags); 746 fprintf (dump_file, "\n\n"); 747 } 748 749 for (i = 0; i < PHI_NUM_ARGS (phi); i++) 750 { 751 prop_value_t *arg_val; 752 tree arg = PHI_ARG_DEF (phi, i); 753 edge e = PHI_ARG_EDGE (phi, i); 754 755 /* We don't care about values flowing through non-executable 756 edges. */ 757 if (!(e->flags & EDGE_EXECUTABLE)) 758 continue; 759 760 /* Constants in the argument list never generate a useful copy. 761 Similarly, names that flow through abnormal edges cannot be 762 used to derive copies. */ 763 if (TREE_CODE (arg) != SSA_NAME || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg)) 764 { 765 phi_val.value = lhs; 766 break; 767 } 768 769 /* Avoid copy propagation from an inner into an outer loop. 770 Otherwise, this may move loop variant variables outside of 771 their loops and prevent coalescing opportunities. If the 772 value was loop invariant, it will be hoisted by LICM and 773 exposed for copy propagation. */ 774 if (loop_depth_of_name (arg) > loop_depth_of_name (lhs)) 775 { 776 phi_val.value = lhs; 777 break; 778 } 779 780 /* If the LHS appears in the argument list, ignore it. It is 781 irrelevant as a copy. */ 782 if (arg == lhs || get_last_copy_of (arg) == lhs) 783 continue; 784 785 if (dump_file && (dump_flags & TDF_DETAILS)) 786 { 787 fprintf (dump_file, "\tArgument #%d: ", i); 788 dump_copy_of (dump_file, arg); 789 fprintf (dump_file, "\n"); 790 } 791 792 arg_val = get_copy_of_val (arg); 793 794 /* If the LHS didn't have a value yet, make it a copy of the 795 first argument we find. Notice that while we make the LHS be 796 a copy of the argument itself, we take the memory reference 797 from the argument's value so that we can compare it to the 798 memory reference of all the other arguments. */ 799 if (phi_val.value == NULL_TREE) 800 { 801 phi_val.value = arg; 802 phi_val.mem_ref = arg_val->mem_ref; 803 continue; 804 } 805 806 /* If PHI_VAL and ARG don't have a common copy-of chain, then 807 this PHI node cannot be a copy operation. Also, if we are 808 copy propagating stores and these two arguments came from 809 different memory references, they cannot be considered 810 copies. */ 811 if (get_last_copy_of (phi_val.value) != get_last_copy_of (arg) 812 || (do_store_copy_prop 813 && phi_val.mem_ref 814 && arg_val->mem_ref 815 && simple_cst_equal (phi_val.mem_ref, arg_val->mem_ref) != 1)) 816 { 817 phi_val.value = lhs; 818 break; 819 } 820 } 821 822 if (phi_val.value && set_copy_of_val (lhs, phi_val.value, phi_val.mem_ref)) 823 retval = (phi_val.value != lhs) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING; 824 else 825 retval = SSA_PROP_NOT_INTERESTING; 826 827 if (dump_file && (dump_flags & TDF_DETAILS)) 828 { 829 fprintf (dump_file, "\nPHI node "); 830 dump_copy_of (dump_file, lhs); 831 fprintf (dump_file, "\nTelling the propagator to "); 832 if (retval == SSA_PROP_INTERESTING) 833 fprintf (dump_file, "add SSA edges out of this PHI and continue."); 834 else if (retval == SSA_PROP_VARYING) 835 fprintf (dump_file, "add SSA edges out of this PHI and never visit again."); 836 else 837 fprintf (dump_file, "do nothing with SSA edges and keep iterating."); 838 fprintf (dump_file, "\n\n"); 839 } 840 841 return retval; 842} 843 844 845/* Initialize structures used for copy propagation. PHIS_ONLY is true 846 if we should only consider PHI nodes as generating copy propagation 847 opportunities. */ 848 849static void 850init_copy_prop (bool phis_only) 851{ 852 basic_block bb; 853 854 copy_of = xmalloc (num_ssa_names * sizeof (*copy_of)); 855 memset (copy_of, 0, num_ssa_names * sizeof (*copy_of)); 856 857 cached_last_copy_of = xmalloc (num_ssa_names * sizeof (*cached_last_copy_of)); 858 memset (cached_last_copy_of, 0, num_ssa_names * sizeof (*cached_last_copy_of)); 859 860 FOR_EACH_BB (bb) 861 { 862 block_stmt_iterator si; 863 tree phi, def; 864 int depth = bb->loop_depth; 865 866 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) 867 { 868 tree stmt = bsi_stmt (si); 869 ssa_op_iter iter; 870 871 /* The only statements that we care about are those that may 872 generate useful copies. We also need to mark conditional 873 jumps so that their outgoing edges are added to the work 874 lists of the propagator. 875 876 Avoid copy propagation from an inner into an outer loop. 877 Otherwise, this may move loop variant variables outside of 878 their loops and prevent coalescing opportunities. If the 879 value was loop invariant, it will be hoisted by LICM and 880 exposed for copy propagation. */ 881 if (stmt_ends_bb_p (stmt)) 882 DONT_SIMULATE_AGAIN (stmt) = false; 883 else if (!phis_only && stmt_may_generate_copy (stmt) 884 && loop_depth_of_name (TREE_OPERAND (stmt, 1)) <= depth) 885 DONT_SIMULATE_AGAIN (stmt) = false; 886 else 887 DONT_SIMULATE_AGAIN (stmt) = true; 888 889 /* Mark all the outputs of this statement as not being 890 the copy of anything. */ 891 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) 892 if (DONT_SIMULATE_AGAIN (stmt)) 893 set_copy_of_val (def, def, NULL_TREE); 894 else 895 cached_last_copy_of[SSA_NAME_VERSION (def)] = def; 896 } 897 898 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 899 { 900 def = PHI_RESULT (phi); 901 if (!do_store_copy_prop && !is_gimple_reg (def)) 902 DONT_SIMULATE_AGAIN (phi) = true; 903 else 904 DONT_SIMULATE_AGAIN (phi) = false; 905 906 if (DONT_SIMULATE_AGAIN (phi)) 907 set_copy_of_val (def, def, NULL_TREE); 908 else 909 cached_last_copy_of[SSA_NAME_VERSION (def)] = def; 910 } 911 } 912} 913 914 915/* Deallocate memory used in copy propagation and do final 916 substitution. */ 917 918static void 919fini_copy_prop (void) 920{ 921 size_t i; 922 prop_value_t *tmp; 923 924 /* Set the final copy-of value for each variable by traversing the 925 copy-of chains. */ 926 tmp = xmalloc (num_ssa_names * sizeof (*tmp)); 927 memset (tmp, 0, num_ssa_names * sizeof (*tmp)); 928 for (i = 1; i < num_ssa_names; i++) 929 { 930 tree var = ssa_name (i); 931 if (var && copy_of[i].value && copy_of[i].value != var) 932 tmp[i].value = get_last_copy_of (var); 933 } 934 935 substitute_and_fold (tmp, false); 936 937 free (cached_last_copy_of); 938 free (copy_of); 939 free (tmp); 940} 941 942 943/* Main entry point to the copy propagator. 944 945 PHIS_ONLY is true if we should only consider PHI nodes as generating 946 copy propagation opportunities. 947 948 The algorithm propagates the value COPY-OF using ssa_propagate. For 949 every variable X_i, COPY-OF(X_i) indicates which variable is X_i created 950 from. The following example shows how the algorithm proceeds at a 951 high level: 952 953 1 a_24 = x_1 954 2 a_2 = PHI <a_24, x_1> 955 3 a_5 = PHI <a_2> 956 4 x_1 = PHI <x_298, a_5, a_2> 957 958 The end result should be that a_2, a_5, a_24 and x_1 are a copy of 959 x_298. Propagation proceeds as follows. 960 961 Visit #1: a_24 is copy-of x_1. Value changed. 962 Visit #2: a_2 is copy-of x_1. Value changed. 963 Visit #3: a_5 is copy-of x_1. Value changed. 964 Visit #4: x_1 is copy-of x_298. Value changed. 965 Visit #1: a_24 is copy-of x_298. Value changed. 966 Visit #2: a_2 is copy-of x_298. Value changed. 967 Visit #3: a_5 is copy-of x_298. Value changed. 968 Visit #4: x_1 is copy-of x_298. Stable state reached. 969 970 When visiting PHI nodes, we only consider arguments that flow 971 through edges marked executable by the propagation engine. So, 972 when visiting statement #2 for the first time, we will only look at 973 the first argument (a_24) and optimistically assume that its value 974 is the copy of a_24 (x_1). 975 976 The problem with this approach is that it may fail to discover copy 977 relations in PHI cycles. Instead of propagating copy-of 978 values, we actually propagate copy-of chains. For instance: 979 980 A_3 = B_1; 981 C_9 = A_3; 982 D_4 = C_9; 983 X_i = D_4; 984 985 In this code fragment, COPY-OF (X_i) = { D_4, C_9, A_3, B_1 }. 986 Obviously, we are only really interested in the last value of the 987 chain, however the propagator needs to access the copy-of chain 988 when visiting PHI nodes. 989 990 To represent the copy-of chain, we use the array COPY_CHAINS, which 991 holds the first link in the copy-of chain for every variable. 992 If variable X_i is a copy of X_j, which in turn is a copy of X_k, 993 the array will contain: 994 995 COPY_CHAINS[i] = X_j 996 COPY_CHAINS[j] = X_k 997 COPY_CHAINS[k] = X_k 998 999 Keeping copy-of chains instead of copy-of values directly becomes 1000 important when visiting PHI nodes. Suppose that we had the 1001 following PHI cycle, such that x_52 is already considered a copy of 1002 x_53: 1003 1004 1 x_54 = PHI <x_53, x_52> 1005 2 x_53 = PHI <x_898, x_54> 1006 1007 Visit #1: x_54 is copy-of x_53 (because x_52 is copy-of x_53) 1008 Visit #2: x_53 is copy-of x_898 (because x_54 is a copy of x_53, 1009 so it is considered irrelevant 1010 as a copy). 1011 Visit #1: x_54 is copy-of nothing (x_53 is a copy-of x_898 and 1012 x_52 is a copy of x_53, so 1013 they don't match) 1014 Visit #2: x_53 is copy-of nothing 1015 1016 This problem is avoided by keeping a chain of copies, instead of 1017 the final copy-of value. Propagation will now only keep the first 1018 element of a variable's copy-of chain. When visiting PHI nodes, 1019 arguments are considered equal if their copy-of chains end in the 1020 same variable. So, as long as their copy-of chains overlap, we 1021 know that they will be a copy of the same variable, regardless of 1022 which variable that may be). 1023 1024 Propagation would then proceed as follows (the notation a -> b 1025 means that a is a copy-of b): 1026 1027 Visit #1: x_54 = PHI <x_53, x_52> 1028 x_53 -> x_53 1029 x_52 -> x_53 1030 Result: x_54 -> x_53. Value changed. Add SSA edges. 1031 1032 Visit #1: x_53 = PHI <x_898, x_54> 1033 x_898 -> x_898 1034 x_54 -> x_53 1035 Result: x_53 -> x_898. Value changed. Add SSA edges. 1036 1037 Visit #2: x_54 = PHI <x_53, x_52> 1038 x_53 -> x_898 1039 x_52 -> x_53 -> x_898 1040 Result: x_54 -> x_898. Value changed. Add SSA edges. 1041 1042 Visit #2: x_53 = PHI <x_898, x_54> 1043 x_898 -> x_898 1044 x_54 -> x_898 1045 Result: x_53 -> x_898. Value didn't change. Stable state 1046 1047 Once the propagator stabilizes, we end up with the desired result 1048 x_53 and x_54 are both copies of x_898. */ 1049 1050static void 1051execute_copy_prop (bool store_copy_prop, bool phis_only) 1052{ 1053 do_store_copy_prop = store_copy_prop; 1054 init_copy_prop (phis_only); 1055 ssa_propagate (copy_prop_visit_stmt, copy_prop_visit_phi_node); 1056 fini_copy_prop (); 1057} 1058 1059 1060static bool 1061gate_copy_prop (void) 1062{ 1063 return flag_tree_copy_prop != 0; 1064} 1065 1066static void 1067do_copy_prop (void) 1068{ 1069 execute_copy_prop (false, false); 1070} 1071 1072struct tree_opt_pass pass_copy_prop = 1073{ 1074 "copyprop", /* name */ 1075 gate_copy_prop, /* gate */ 1076 do_copy_prop, /* execute */ 1077 NULL, /* sub */ 1078 NULL, /* next */ 1079 0, /* static_pass_number */ 1080 TV_TREE_COPY_PROP, /* tv_id */ 1081 PROP_ssa | PROP_alias | PROP_cfg, /* properties_required */ 1082 0, /* properties_provided */ 1083 0, /* properties_destroyed */ 1084 0, /* todo_flags_start */ 1085 TODO_cleanup_cfg 1086 | TODO_dump_func 1087 | TODO_ggc_collect 1088 | TODO_verify_ssa 1089 | TODO_update_ssa, /* todo_flags_finish */ 1090 0 /* letter */ 1091}; 1092 1093 1094static void 1095do_phi_only_copy_prop (void) 1096{ 1097 execute_copy_prop (false, true); 1098} 1099 1100struct tree_opt_pass pass_phi_only_copy_prop = 1101{ 1102 "phionlycopyprop", /* name */ 1103 gate_copy_prop, /* gate */ 1104 do_phi_only_copy_prop, /* execute */ 1105 NULL, /* sub */ 1106 NULL, /* next */ 1107 0, /* static_pass_number */ 1108 TV_TREE_COPY_PROP, /* tv_id */ 1109 PROP_ssa | PROP_alias | PROP_cfg, /* properties_required */ 1110 0, /* properties_provided */ 1111 0, /* properties_destroyed */ 1112 0, /* todo_flags_start */ 1113 TODO_cleanup_cfg 1114 | TODO_dump_func 1115 | TODO_ggc_collect 1116 | TODO_verify_ssa 1117 | TODO_update_ssa, /* todo_flags_finish */ 1118 0 /* letter */ 1119}; 1120 1121 1122static bool 1123gate_store_copy_prop (void) 1124{ 1125 /* STORE-COPY-PROP is enabled only with -ftree-store-copy-prop, but 1126 when -fno-tree-store-copy-prop is specified, we should run 1127 regular COPY-PROP. That's why the pass is enabled with either 1128 flag. */ 1129 return flag_tree_store_copy_prop != 0 || flag_tree_copy_prop != 0; 1130} 1131 1132static void 1133store_copy_prop (void) 1134{ 1135 /* If STORE-COPY-PROP is not enabled, we just run regular COPY-PROP. */ 1136 execute_copy_prop (flag_tree_store_copy_prop != 0, false); 1137} 1138 1139struct tree_opt_pass pass_store_copy_prop = 1140{ 1141 "store_copyprop", /* name */ 1142 gate_store_copy_prop, /* gate */ 1143 store_copy_prop, /* execute */ 1144 NULL, /* sub */ 1145 NULL, /* next */ 1146 0, /* static_pass_number */ 1147 TV_TREE_STORE_COPY_PROP, /* tv_id */ 1148 PROP_ssa | PROP_alias | PROP_cfg, /* properties_required */ 1149 0, /* properties_provided */ 1150 0, /* properties_destroyed */ 1151 0, /* todo_flags_start */ 1152 TODO_dump_func 1153 | TODO_cleanup_cfg 1154 | TODO_ggc_collect 1155 | TODO_verify_ssa 1156 | TODO_update_ssa, /* todo_flags_finish */ 1157 0 /* letter */ 1158}; 1159