1169689Skan/* Copy propagation and SSA_NAME replacement support routines. 2169689Skan Copyright (C) 2004, 2005 Free Software Foundation, Inc. 3169689Skan 4169689SkanThis file is part of GCC. 5169689Skan 6169689SkanGCC is free software; you can redistribute it and/or modify 7169689Skanit under the terms of the GNU General Public License as published by 8169689Skanthe Free Software Foundation; either version 2, or (at your option) 9169689Skanany later version. 10169689Skan 11169689SkanGCC is distributed in the hope that it will be useful, 12169689Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 13169689SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14169689SkanGNU General Public License for more details. 15169689Skan 16169689SkanYou should have received a copy of the GNU General Public License 17169689Skanalong with GCC; see the file COPYING. If not, write to 18169689Skanthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 19169689SkanBoston, MA 02110-1301, USA. */ 20169689Skan 21169689Skan#include "config.h" 22169689Skan#include "system.h" 23169689Skan#include "coretypes.h" 24169689Skan#include "tm.h" 25169689Skan#include "tree.h" 26169689Skan#include "flags.h" 27169689Skan#include "rtl.h" 28169689Skan#include "tm_p.h" 29169689Skan#include "ggc.h" 30169689Skan#include "basic-block.h" 31169689Skan#include "output.h" 32169689Skan#include "expr.h" 33169689Skan#include "function.h" 34169689Skan#include "diagnostic.h" 35169689Skan#include "timevar.h" 36169689Skan#include "tree-dump.h" 37169689Skan#include "tree-flow.h" 38169689Skan#include "tree-pass.h" 39169689Skan#include "tree-ssa-propagate.h" 40169689Skan#include "langhooks.h" 41169689Skan 42169689Skan/* This file implements the copy propagation pass and provides a 43169689Skan handful of interfaces for performing const/copy propagation and 44169689Skan simple expression replacement which keep variable annotations 45169689Skan up-to-date. 46169689Skan 47169689Skan We require that for any copy operation where the RHS and LHS have 48169689Skan a non-null memory tag the memory tag be the same. It is OK 49169689Skan for one or both of the memory tags to be NULL. 50169689Skan 51169689Skan We also require tracking if a variable is dereferenced in a load or 52169689Skan store operation. 53169689Skan 54169689Skan We enforce these requirements by having all copy propagation and 55169689Skan replacements of one SSA_NAME with a different SSA_NAME to use the 56169689Skan APIs defined in this file. */ 57169689Skan 58169689Skan/* Return true if we may propagate ORIG into DEST, false otherwise. */ 59169689Skan 60169689Skanbool 61169689Skanmay_propagate_copy (tree dest, tree orig) 62169689Skan{ 63169689Skan tree type_d = TREE_TYPE (dest); 64169689Skan tree type_o = TREE_TYPE (orig); 65169689Skan 66169689Skan /* Do not copy between types for which we *do* need a conversion. */ 67169689Skan if (!tree_ssa_useless_type_conversion_1 (type_d, type_o)) 68169689Skan return false; 69169689Skan 70169689Skan /* FIXME. GIMPLE is allowing pointer assignments and comparisons of 71169689Skan pointers that have different alias sets. This means that these 72169689Skan pointers will have different memory tags associated to them. 73169689Skan 74169689Skan If we allow copy propagation in these cases, statements de-referencing 75169689Skan the new pointer will now have a reference to a different memory tag 76169689Skan with potentially incorrect SSA information. 77169689Skan 78169689Skan This was showing up in libjava/java/util/zip/ZipFile.java with code 79169689Skan like: 80169689Skan 81169689Skan struct java.io.BufferedInputStream *T.660; 82169689Skan struct java.io.BufferedInputStream *T.647; 83169689Skan struct java.io.InputStream *is; 84169689Skan struct java.io.InputStream *is.662; 85169689Skan [ ... ] 86169689Skan T.660 = T.647; 87169689Skan is = T.660; <-- This ought to be type-casted 88169689Skan is.662 = is; 89169689Skan 90169689Skan Also, f/name.c exposed a similar problem with a COND_EXPR predicate 91169689Skan that was causing DOM to generate and equivalence with two pointers of 92169689Skan alias-incompatible types: 93169689Skan 94169689Skan struct _ffename_space *n; 95169689Skan struct _ffename *ns; 96169689Skan [ ... ] 97169689Skan if (n == ns) 98169689Skan goto lab; 99169689Skan ... 100169689Skan lab: 101169689Skan return n; 102169689Skan 103169689Skan I think that GIMPLE should emit the appropriate type-casts. For the 104169689Skan time being, blocking copy-propagation in these cases is the safe thing 105169689Skan to do. */ 106169689Skan if (TREE_CODE (dest) == SSA_NAME 107169689Skan && TREE_CODE (orig) == SSA_NAME 108169689Skan && POINTER_TYPE_P (type_d) 109169689Skan && POINTER_TYPE_P (type_o)) 110169689Skan { 111169689Skan tree mt_dest = var_ann (SSA_NAME_VAR (dest))->symbol_mem_tag; 112169689Skan tree mt_orig = var_ann (SSA_NAME_VAR (orig))->symbol_mem_tag; 113169689Skan if (mt_dest && mt_orig && mt_dest != mt_orig) 114169689Skan return false; 115169689Skan else if (!lang_hooks.types_compatible_p (type_d, type_o)) 116169689Skan return false; 117169689Skan else if (get_alias_set (TREE_TYPE (type_d)) != 118169689Skan get_alias_set (TREE_TYPE (type_o))) 119169689Skan return false; 120169689Skan 121169689Skan /* Also verify flow-sensitive information is compatible. */ 122169689Skan if (SSA_NAME_PTR_INFO (orig) && SSA_NAME_PTR_INFO (dest)) 123169689Skan { 124169689Skan struct ptr_info_def *orig_ptr_info = SSA_NAME_PTR_INFO (orig); 125169689Skan struct ptr_info_def *dest_ptr_info = SSA_NAME_PTR_INFO (dest); 126169689Skan 127169689Skan if (orig_ptr_info->name_mem_tag 128169689Skan && dest_ptr_info->name_mem_tag 129169689Skan && orig_ptr_info->pt_vars 130169689Skan && dest_ptr_info->pt_vars 131169689Skan && !bitmap_intersect_p (dest_ptr_info->pt_vars, 132169689Skan orig_ptr_info->pt_vars)) 133169689Skan return false; 134169689Skan } 135169689Skan } 136169689Skan 137169689Skan /* If the destination is a SSA_NAME for a virtual operand, then we have 138169689Skan some special cases to handle. */ 139169689Skan if (TREE_CODE (dest) == SSA_NAME && !is_gimple_reg (dest)) 140169689Skan { 141169689Skan /* If both operands are SSA_NAMEs referring to virtual operands, then 142169689Skan we can always propagate. */ 143169689Skan if (TREE_CODE (orig) == SSA_NAME 144169689Skan && !is_gimple_reg (orig)) 145169689Skan return true; 146169689Skan 147169689Skan /* We have a "copy" from something like a constant into a virtual 148169689Skan operand. Reject these. */ 149169689Skan return false; 150169689Skan } 151169689Skan 152169689Skan /* If ORIG flows in from an abnormal edge, it cannot be propagated. */ 153169689Skan if (TREE_CODE (orig) == SSA_NAME 154169689Skan && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig)) 155169689Skan return false; 156169689Skan 157169689Skan /* If DEST is an SSA_NAME that flows from an abnormal edge, then it 158169689Skan cannot be replaced. */ 159169689Skan if (TREE_CODE (dest) == SSA_NAME 160169689Skan && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (dest)) 161169689Skan return false; 162169689Skan 163169689Skan /* Anything else is OK. */ 164169689Skan return true; 165169689Skan} 166169689Skan 167169689Skan/* Similarly, but we know that we're propagating into an ASM_EXPR. */ 168169689Skan 169169689Skanbool 170169689Skanmay_propagate_copy_into_asm (tree dest) 171169689Skan{ 172169689Skan /* Hard register operands of asms are special. Do not bypass. */ 173169689Skan return !(TREE_CODE (dest) == SSA_NAME 174169689Skan && TREE_CODE (SSA_NAME_VAR (dest)) == VAR_DECL 175169689Skan && DECL_HARD_REGISTER (SSA_NAME_VAR (dest))); 176169689Skan} 177169689Skan 178169689Skan 179169689Skan/* Given two SSA_NAMEs pointers ORIG and NEW such that we are copy 180169689Skan propagating NEW into ORIG, consolidate aliasing information so that 181169689Skan they both share the same memory tags. */ 182169689Skan 183169689Skanvoid 184169689Skanmerge_alias_info (tree orig, tree new) 185169689Skan{ 186169689Skan tree new_sym = SSA_NAME_VAR (new); 187169689Skan tree orig_sym = SSA_NAME_VAR (orig); 188169689Skan var_ann_t new_ann = var_ann (new_sym); 189169689Skan var_ann_t orig_ann = var_ann (orig_sym); 190169689Skan 191169689Skan gcc_assert (POINTER_TYPE_P (TREE_TYPE (orig))); 192169689Skan gcc_assert (POINTER_TYPE_P (TREE_TYPE (new))); 193169689Skan 194169689Skan#if defined ENABLE_CHECKING 195169689Skan gcc_assert (lang_hooks.types_compatible_p (TREE_TYPE (orig), 196169689Skan TREE_TYPE (new))); 197169689Skan 198169689Skan /* If the pointed-to alias sets are different, these two pointers 199169689Skan would never have the same memory tag. In this case, NEW should 200169689Skan not have been propagated into ORIG. */ 201169689Skan gcc_assert (get_alias_set (TREE_TYPE (TREE_TYPE (new_sym))) 202169689Skan == get_alias_set (TREE_TYPE (TREE_TYPE (orig_sym)))); 203169689Skan#endif 204169689Skan 205169689Skan /* Synchronize the symbol tags. If both pointers had a tag and they 206169689Skan are different, then something has gone wrong. Symbol tags can 207169689Skan always be merged because they are flow insensitive, all the SSA 208169689Skan names of the same base DECL share the same symbol tag. */ 209169689Skan if (new_ann->symbol_mem_tag == NULL_TREE) 210169689Skan new_ann->symbol_mem_tag = orig_ann->symbol_mem_tag; 211169689Skan else if (orig_ann->symbol_mem_tag == NULL_TREE) 212169689Skan orig_ann->symbol_mem_tag = new_ann->symbol_mem_tag; 213169689Skan else 214169689Skan gcc_assert (new_ann->symbol_mem_tag == orig_ann->symbol_mem_tag); 215169689Skan 216169689Skan /* Check that flow-sensitive information is compatible. Notice that 217169689Skan we may not merge flow-sensitive information here. This function 218169689Skan is called when propagating equivalences dictated by the IL, like 219169689Skan a copy operation P_i = Q_j, and from equivalences dictated by 220169689Skan control-flow, like if (P_i == Q_j). 221169689Skan 222169689Skan In the former case, P_i and Q_j are equivalent in every block 223169689Skan dominated by the assignment, so their flow-sensitive information 224169689Skan is always the same. However, in the latter case, the pointers 225169689Skan P_i and Q_j are only equivalent in one of the sub-graphs out of 226169689Skan the predicate, so their flow-sensitive information is not the 227169689Skan same in every block dominated by the predicate. 228169689Skan 229169689Skan Since we cannot distinguish one case from another in this 230169689Skan function, we can only make sure that if P_i and Q_j have 231169689Skan flow-sensitive information, they should be compatible. */ 232169689Skan if (SSA_NAME_PTR_INFO (orig) && SSA_NAME_PTR_INFO (new)) 233169689Skan { 234169689Skan struct ptr_info_def *orig_ptr_info = SSA_NAME_PTR_INFO (orig); 235169689Skan struct ptr_info_def *new_ptr_info = SSA_NAME_PTR_INFO (new); 236169689Skan 237169689Skan /* Note that pointer NEW and ORIG may actually have different 238169689Skan pointed-to variables (e.g., PR 18291 represented in 239169689Skan testsuite/gcc.c-torture/compile/pr18291.c). However, since 240169689Skan NEW is being copy-propagated into ORIG, it must always be 241169689Skan true that the pointed-to set for pointer NEW is the same, or 242169689Skan a subset, of the pointed-to set for pointer ORIG. If this 243169689Skan isn't the case, we shouldn't have been able to do the 244169689Skan propagation of NEW into ORIG. */ 245169689Skan if (orig_ptr_info->name_mem_tag 246169689Skan && new_ptr_info->name_mem_tag 247169689Skan && orig_ptr_info->pt_vars 248169689Skan && new_ptr_info->pt_vars) 249169689Skan gcc_assert (bitmap_intersect_p (new_ptr_info->pt_vars, 250169689Skan orig_ptr_info->pt_vars)); 251169689Skan } 252169689Skan} 253169689Skan 254169689Skan 255169689Skan/* Common code for propagate_value and replace_exp. 256169689Skan 257169689Skan Replace use operand OP_P with VAL. FOR_PROPAGATION indicates if the 258169689Skan replacement is done to propagate a value or not. */ 259169689Skan 260169689Skanstatic void 261169689Skanreplace_exp_1 (use_operand_p op_p, tree val, 262169689Skan bool for_propagation ATTRIBUTE_UNUSED) 263169689Skan{ 264169689Skan tree op = USE_FROM_PTR (op_p); 265169689Skan 266169689Skan#if defined ENABLE_CHECKING 267169689Skan gcc_assert (!(for_propagation 268169689Skan && TREE_CODE (op) == SSA_NAME 269169689Skan && TREE_CODE (val) == SSA_NAME 270169689Skan && !may_propagate_copy (op, val))); 271169689Skan#endif 272169689Skan 273169689Skan if (TREE_CODE (val) == SSA_NAME) 274169689Skan { 275169689Skan if (TREE_CODE (op) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (op))) 276169689Skan merge_alias_info (op, val); 277169689Skan SET_USE (op_p, val); 278169689Skan } 279169689Skan else 280169689Skan SET_USE (op_p, unsave_expr_now (val)); 281169689Skan} 282169689Skan 283169689Skan 284169689Skan/* Propagate the value VAL (assumed to be a constant or another SSA_NAME) 285169689Skan into the operand pointed to by OP_P. 286169689Skan 287169689Skan Use this version for const/copy propagation as it will perform additional 288169689Skan checks to ensure validity of the const/copy propagation. */ 289169689Skan 290169689Skanvoid 291169689Skanpropagate_value (use_operand_p op_p, tree val) 292169689Skan{ 293169689Skan replace_exp_1 (op_p, val, true); 294169689Skan} 295169689Skan 296169689Skan 297169689Skan/* Propagate the value VAL (assumed to be a constant or another SSA_NAME) 298169689Skan into the tree pointed to by OP_P. 299169689Skan 300169689Skan Use this version for const/copy propagation when SSA operands are not 301169689Skan available. It will perform the additional checks to ensure validity of 302169689Skan the const/copy propagation, but will not update any operand information. 303169689Skan Be sure to mark the stmt as modified. */ 304169689Skan 305169689Skanvoid 306169689Skanpropagate_tree_value (tree *op_p, tree val) 307169689Skan{ 308169689Skan#if defined ENABLE_CHECKING 309169689Skan gcc_assert (!(TREE_CODE (val) == SSA_NAME 310169689Skan && TREE_CODE (*op_p) == SSA_NAME 311169689Skan && !may_propagate_copy (*op_p, val))); 312169689Skan#endif 313169689Skan 314169689Skan if (TREE_CODE (val) == SSA_NAME) 315169689Skan { 316169689Skan if (TREE_CODE (*op_p) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (*op_p))) 317169689Skan merge_alias_info (*op_p, val); 318169689Skan *op_p = val; 319169689Skan } 320169689Skan else 321169689Skan *op_p = unsave_expr_now (val); 322169689Skan} 323169689Skan 324169689Skan 325169689Skan/* Replace *OP_P with value VAL (assumed to be a constant or another SSA_NAME). 326169689Skan 327169689Skan Use this version when not const/copy propagating values. For example, 328169689Skan PRE uses this version when building expressions as they would appear 329169689Skan in specific blocks taking into account actions of PHI nodes. */ 330169689Skan 331169689Skanvoid 332169689Skanreplace_exp (use_operand_p op_p, tree val) 333169689Skan{ 334169689Skan replace_exp_1 (op_p, val, false); 335169689Skan} 336169689Skan 337169689Skan 338169689Skan/*--------------------------------------------------------------------------- 339169689Skan Copy propagation 340169689Skan---------------------------------------------------------------------------*/ 341169689Skan/* During propagation, we keep chains of variables that are copies of 342169689Skan one another. If variable X_i is a copy of X_j and X_j is a copy of 343169689Skan X_k, COPY_OF will contain: 344169689Skan 345169689Skan COPY_OF[i].VALUE = X_j 346169689Skan COPY_OF[j].VALUE = X_k 347169689Skan COPY_OF[k].VALUE = X_k 348169689Skan 349169689Skan After propagation, the copy-of value for each variable X_i is 350169689Skan converted into the final value by walking the copy-of chains and 351169689Skan updating COPY_OF[i].VALUE to be the last element of the chain. */ 352169689Skanstatic prop_value_t *copy_of; 353169689Skan 354169689Skan/* Used in set_copy_of_val to determine if the last link of a copy-of 355169689Skan chain has changed. */ 356169689Skanstatic tree *cached_last_copy_of; 357169689Skan 358169689Skan/* True if we are doing copy propagation on loads and stores. */ 359169689Skanstatic bool do_store_copy_prop; 360169689Skan 361169689Skan 362169689Skan/* Return true if this statement may generate a useful copy. */ 363169689Skan 364169689Skanstatic bool 365169689Skanstmt_may_generate_copy (tree stmt) 366169689Skan{ 367169689Skan tree lhs, rhs; 368169689Skan stmt_ann_t ann; 369169689Skan 370169689Skan if (TREE_CODE (stmt) == PHI_NODE) 371169689Skan return !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (stmt)); 372169689Skan 373169689Skan if (TREE_CODE (stmt) != MODIFY_EXPR) 374169689Skan return false; 375169689Skan 376169689Skan lhs = TREE_OPERAND (stmt, 0); 377169689Skan rhs = TREE_OPERAND (stmt, 1); 378169689Skan ann = stmt_ann (stmt); 379169689Skan 380169689Skan /* If the statement has volatile operands, it won't generate a 381169689Skan useful copy. */ 382169689Skan if (ann->has_volatile_ops) 383169689Skan return false; 384169689Skan 385169689Skan /* If we are not doing store copy-prop, statements with loads and/or 386169689Skan stores will never generate a useful copy. */ 387169689Skan if (!do_store_copy_prop 388169689Skan && !ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) 389169689Skan return false; 390169689Skan 391169689Skan /* Otherwise, the only statements that generate useful copies are 392169689Skan assignments whose RHS is just an SSA name that doesn't flow 393169689Skan through abnormal edges. */ 394169689Skan return (do_store_copy_prop 395169689Skan && TREE_CODE (lhs) == SSA_NAME) 396169689Skan || (TREE_CODE (rhs) == SSA_NAME 397169689Skan && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs)); 398169689Skan} 399169689Skan 400169689Skan 401169689Skan/* Return the copy-of value for VAR. */ 402169689Skan 403169689Skanstatic inline prop_value_t * 404169689Skanget_copy_of_val (tree var) 405169689Skan{ 406169689Skan prop_value_t *val = ©_of[SSA_NAME_VERSION (var)]; 407169689Skan 408169689Skan if (val->value == NULL_TREE 409169689Skan && !stmt_may_generate_copy (SSA_NAME_DEF_STMT (var))) 410169689Skan { 411169689Skan /* If the variable will never generate a useful copy relation, 412169689Skan make it its own copy. */ 413169689Skan val->value = var; 414169689Skan val->mem_ref = NULL_TREE; 415169689Skan } 416169689Skan 417169689Skan return val; 418169689Skan} 419169689Skan 420169689Skan 421169689Skan/* Return last link in the copy-of chain for VAR. */ 422169689Skan 423169689Skanstatic tree 424169689Skanget_last_copy_of (tree var) 425169689Skan{ 426169689Skan tree last; 427169689Skan int i; 428169689Skan 429169689Skan /* Traverse COPY_OF starting at VAR until we get to the last 430169689Skan link in the chain. Since it is possible to have cycles in PHI 431169689Skan nodes, the copy-of chain may also contain cycles. 432169689Skan 433169689Skan To avoid infinite loops and to avoid traversing lengthy copy-of 434169689Skan chains, we artificially limit the maximum number of chains we are 435169689Skan willing to traverse. 436169689Skan 437169689Skan The value 5 was taken from a compiler and runtime library 438169689Skan bootstrap and a mixture of C and C++ code from various sources. 439169689Skan More than 82% of all copy-of chains were shorter than 5 links. */ 440169689Skan#define LIMIT 5 441169689Skan 442169689Skan last = var; 443169689Skan for (i = 0; i < LIMIT; i++) 444169689Skan { 445169689Skan tree copy = copy_of[SSA_NAME_VERSION (last)].value; 446169689Skan if (copy == NULL_TREE || copy == last) 447169689Skan break; 448169689Skan last = copy; 449169689Skan } 450169689Skan 451169689Skan /* If we have reached the limit, then we are either in a copy-of 452169689Skan cycle or the copy-of chain is too long. In this case, just 453169689Skan return VAR so that it is not considered a copy of anything. */ 454169689Skan return (i < LIMIT ? last : var); 455169689Skan} 456169689Skan 457169689Skan 458169689Skan/* Set FIRST to be the first variable in the copy-of chain for DEST. 459169689Skan If DEST's copy-of value or its copy-of chain has changed, return 460169689Skan true. 461169689Skan 462169689Skan MEM_REF is the memory reference where FIRST is stored. This is 463169689Skan used when DEST is a non-register and we are copy propagating loads 464169689Skan and stores. */ 465169689Skan 466169689Skanstatic inline bool 467169689Skanset_copy_of_val (tree dest, tree first, tree mem_ref) 468169689Skan{ 469169689Skan unsigned int dest_ver = SSA_NAME_VERSION (dest); 470169689Skan tree old_first, old_last, new_last; 471169689Skan 472169689Skan /* Set FIRST to be the first link in COPY_OF[DEST]. If that 473169689Skan changed, return true. */ 474169689Skan old_first = copy_of[dest_ver].value; 475169689Skan copy_of[dest_ver].value = first; 476169689Skan copy_of[dest_ver].mem_ref = mem_ref; 477169689Skan 478169689Skan if (old_first != first) 479169689Skan return true; 480169689Skan 481169689Skan /* If FIRST and OLD_FIRST are the same, we need to check whether the 482169689Skan copy-of chain starting at FIRST ends in a different variable. If 483169689Skan the copy-of chain starting at FIRST ends up in a different 484169689Skan variable than the last cached value we had for DEST, then return 485169689Skan true because DEST is now a copy of a different variable. 486169689Skan 487169689Skan This test is necessary because even though the first link in the 488169689Skan copy-of chain may not have changed, if any of the variables in 489169689Skan the copy-of chain changed its final value, DEST will now be the 490169689Skan copy of a different variable, so we have to do another round of 491169689Skan propagation for everything that depends on DEST. */ 492169689Skan old_last = cached_last_copy_of[dest_ver]; 493169689Skan new_last = get_last_copy_of (dest); 494169689Skan cached_last_copy_of[dest_ver] = new_last; 495169689Skan 496169689Skan return (old_last != new_last); 497169689Skan} 498169689Skan 499169689Skan 500169689Skan/* Dump the copy-of value for variable VAR to FILE. */ 501169689Skan 502169689Skanstatic void 503169689Skandump_copy_of (FILE *file, tree var) 504169689Skan{ 505169689Skan tree val; 506169689Skan sbitmap visited; 507169689Skan 508169689Skan print_generic_expr (file, var, dump_flags); 509169689Skan 510169689Skan if (TREE_CODE (var) != SSA_NAME) 511169689Skan return; 512169689Skan 513169689Skan visited = sbitmap_alloc (num_ssa_names); 514169689Skan sbitmap_zero (visited); 515169689Skan SET_BIT (visited, SSA_NAME_VERSION (var)); 516169689Skan 517169689Skan fprintf (file, " copy-of chain: "); 518169689Skan 519169689Skan val = var; 520169689Skan print_generic_expr (file, val, 0); 521169689Skan fprintf (file, " "); 522169689Skan while (copy_of[SSA_NAME_VERSION (val)].value) 523169689Skan { 524169689Skan fprintf (file, "-> "); 525169689Skan val = copy_of[SSA_NAME_VERSION (val)].value; 526169689Skan print_generic_expr (file, val, 0); 527169689Skan fprintf (file, " "); 528169689Skan if (TEST_BIT (visited, SSA_NAME_VERSION (val))) 529169689Skan break; 530169689Skan SET_BIT (visited, SSA_NAME_VERSION (val)); 531169689Skan } 532169689Skan 533169689Skan val = get_copy_of_val (var)->value; 534169689Skan if (val == NULL_TREE) 535169689Skan fprintf (file, "[UNDEFINED]"); 536169689Skan else if (val != var) 537169689Skan fprintf (file, "[COPY]"); 538169689Skan else 539169689Skan fprintf (file, "[NOT A COPY]"); 540169689Skan 541169689Skan sbitmap_free (visited); 542169689Skan} 543169689Skan 544169689Skan 545169689Skan/* Evaluate the RHS of STMT. If it produces a valid copy, set the LHS 546169689Skan value and store the LHS into *RESULT_P. If STMT generates more 547169689Skan than one name (i.e., STMT is an aliased store), it is enough to 548169689Skan store the first name in the V_MAY_DEF list into *RESULT_P. After 549169689Skan all, the names generated will be VUSEd in the same statements. */ 550169689Skan 551169689Skanstatic enum ssa_prop_result 552169689Skancopy_prop_visit_assignment (tree stmt, tree *result_p) 553169689Skan{ 554169689Skan tree lhs, rhs; 555169689Skan prop_value_t *rhs_val; 556169689Skan 557169689Skan lhs = TREE_OPERAND (stmt, 0); 558169689Skan rhs = TREE_OPERAND (stmt, 1); 559169689Skan 560169689Skan gcc_assert (TREE_CODE (rhs) == SSA_NAME); 561169689Skan 562169689Skan rhs_val = get_copy_of_val (rhs); 563169689Skan 564169689Skan if (TREE_CODE (lhs) == SSA_NAME) 565169689Skan { 566169689Skan /* Straight copy between two SSA names. First, make sure that 567169689Skan we can propagate the RHS into uses of LHS. */ 568169689Skan if (!may_propagate_copy (lhs, rhs)) 569169689Skan return SSA_PROP_VARYING; 570169689Skan 571169689Skan /* Notice that in the case of assignments, we make the LHS be a 572169689Skan copy of RHS's value, not of RHS itself. This avoids keeping 573169689Skan unnecessary copy-of chains (assignments cannot be in a cycle 574169689Skan like PHI nodes), speeding up the propagation process. 575169689Skan This is different from what we do in copy_prop_visit_phi_node. 576169689Skan In those cases, we are interested in the copy-of chains. */ 577169689Skan *result_p = lhs; 578169689Skan if (set_copy_of_val (*result_p, rhs_val->value, rhs_val->mem_ref)) 579169689Skan return SSA_PROP_INTERESTING; 580169689Skan else 581169689Skan return SSA_PROP_NOT_INTERESTING; 582169689Skan } 583169689Skan else if (stmt_makes_single_store (stmt)) 584169689Skan { 585169689Skan /* Otherwise, set the names in V_MAY_DEF/V_MUST_DEF operands 586169689Skan to be a copy of RHS. */ 587169689Skan ssa_op_iter i; 588169689Skan tree vdef; 589169689Skan bool changed; 590169689Skan 591169689Skan /* This should only be executed when doing store copy-prop. */ 592169689Skan gcc_assert (do_store_copy_prop); 593169689Skan 594169689Skan /* Set the value of every VDEF to RHS_VAL. */ 595169689Skan changed = false; 596169689Skan FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, i, SSA_OP_VIRTUAL_DEFS) 597169689Skan changed |= set_copy_of_val (vdef, rhs_val->value, lhs); 598169689Skan 599169689Skan /* Note that for propagation purposes, we are only interested in 600169689Skan visiting statements that load the exact same memory reference 601169689Skan stored here. Those statements will have the exact same list 602169689Skan of virtual uses, so it is enough to set the output of this 603169689Skan statement to be its first virtual definition. */ 604169689Skan *result_p = first_vdef (stmt); 605169689Skan 606169689Skan if (changed) 607169689Skan return SSA_PROP_INTERESTING; 608169689Skan else 609169689Skan return SSA_PROP_NOT_INTERESTING; 610169689Skan } 611169689Skan 612169689Skan 613169689Skan return SSA_PROP_VARYING; 614169689Skan} 615169689Skan 616169689Skan 617169689Skan/* Visit the COND_EXPR STMT. Return SSA_PROP_INTERESTING 618169689Skan if it can determine which edge will be taken. Otherwise, return 619169689Skan SSA_PROP_VARYING. */ 620169689Skan 621169689Skanstatic enum ssa_prop_result 622169689Skancopy_prop_visit_cond_stmt (tree stmt, edge *taken_edge_p) 623169689Skan{ 624169689Skan enum ssa_prop_result retval; 625169689Skan tree cond; 626169689Skan 627169689Skan cond = COND_EXPR_COND (stmt); 628169689Skan retval = SSA_PROP_VARYING; 629169689Skan 630169689Skan /* The only conditionals that we may be able to compute statically 631169689Skan are predicates involving two SSA_NAMEs. */ 632169689Skan if (COMPARISON_CLASS_P (cond) 633169689Skan && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME 634169689Skan && TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME) 635169689Skan { 636169689Skan tree op0 = get_last_copy_of (TREE_OPERAND (cond, 0)); 637169689Skan tree op1 = get_last_copy_of (TREE_OPERAND (cond, 1)); 638169689Skan 639169689Skan /* See if we can determine the predicate's value. */ 640169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 641169689Skan { 642169689Skan fprintf (dump_file, "Trying to determine truth value of "); 643169689Skan fprintf (dump_file, "predicate "); 644169689Skan print_generic_stmt (dump_file, cond, 0); 645169689Skan } 646169689Skan 647169689Skan /* We can fold COND and get a useful result only when we have 648169689Skan the same SSA_NAME on both sides of a comparison operator. */ 649169689Skan if (op0 == op1) 650169689Skan { 651169689Skan tree folded_cond = fold_binary (TREE_CODE (cond), boolean_type_node, 652169689Skan op0, op1); 653169689Skan if (folded_cond) 654169689Skan { 655169689Skan basic_block bb = bb_for_stmt (stmt); 656169689Skan *taken_edge_p = find_taken_edge (bb, folded_cond); 657169689Skan if (*taken_edge_p) 658169689Skan retval = SSA_PROP_INTERESTING; 659169689Skan } 660169689Skan } 661169689Skan } 662169689Skan 663169689Skan if (dump_file && (dump_flags & TDF_DETAILS) && *taken_edge_p) 664169689Skan fprintf (dump_file, "\nConditional will always take edge %d->%d\n", 665169689Skan (*taken_edge_p)->src->index, (*taken_edge_p)->dest->index); 666169689Skan 667169689Skan return retval; 668169689Skan} 669169689Skan 670169689Skan 671169689Skan/* Evaluate statement STMT. If the statement produces a new output 672169689Skan value, return SSA_PROP_INTERESTING and store the SSA_NAME holding 673169689Skan the new value in *RESULT_P. 674169689Skan 675169689Skan If STMT is a conditional branch and we can determine its truth 676169689Skan value, set *TAKEN_EDGE_P accordingly. 677169689Skan 678169689Skan If the new value produced by STMT is varying, return 679169689Skan SSA_PROP_VARYING. */ 680169689Skan 681169689Skanstatic enum ssa_prop_result 682169689Skancopy_prop_visit_stmt (tree stmt, edge *taken_edge_p, tree *result_p) 683169689Skan{ 684169689Skan enum ssa_prop_result retval; 685169689Skan 686169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 687169689Skan { 688169689Skan fprintf (dump_file, "\nVisiting statement:\n"); 689169689Skan print_generic_stmt (dump_file, stmt, dump_flags); 690169689Skan fprintf (dump_file, "\n"); 691169689Skan } 692169689Skan 693169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR 694169689Skan && TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME 695169689Skan && (do_store_copy_prop 696169689Skan || TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME)) 697169689Skan { 698169689Skan /* If the statement is a copy assignment, evaluate its RHS to 699169689Skan see if the lattice value of its output has changed. */ 700169689Skan retval = copy_prop_visit_assignment (stmt, result_p); 701169689Skan } 702169689Skan else if (TREE_CODE (stmt) == MODIFY_EXPR 703169689Skan && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME 704169689Skan && do_store_copy_prop 705169689Skan && stmt_makes_single_load (stmt)) 706169689Skan { 707169689Skan /* If the statement is a copy assignment with a memory load 708169689Skan on the RHS, see if we know the value of this load and 709169689Skan update the lattice accordingly. */ 710169689Skan prop_value_t *val = get_value_loaded_by (stmt, copy_of); 711169689Skan if (val 712169689Skan && val->mem_ref 713169689Skan && is_gimple_reg (val->value) 714169689Skan && operand_equal_p (val->mem_ref, TREE_OPERAND (stmt, 1), 0)) 715169689Skan { 716169689Skan bool changed; 717169689Skan changed = set_copy_of_val (TREE_OPERAND (stmt, 0), 718169689Skan val->value, val->mem_ref); 719169689Skan if (changed) 720169689Skan { 721169689Skan *result_p = TREE_OPERAND (stmt, 0); 722169689Skan retval = SSA_PROP_INTERESTING; 723169689Skan } 724169689Skan else 725169689Skan retval = SSA_PROP_NOT_INTERESTING; 726169689Skan } 727169689Skan else 728169689Skan retval = SSA_PROP_VARYING; 729169689Skan } 730169689Skan else if (TREE_CODE (stmt) == COND_EXPR) 731169689Skan { 732169689Skan /* See if we can determine which edge goes out of a conditional 733169689Skan jump. */ 734169689Skan retval = copy_prop_visit_cond_stmt (stmt, taken_edge_p); 735169689Skan } 736169689Skan else 737169689Skan retval = SSA_PROP_VARYING; 738169689Skan 739169689Skan if (retval == SSA_PROP_VARYING) 740169689Skan { 741169689Skan tree def; 742169689Skan ssa_op_iter i; 743169689Skan 744169689Skan /* Any other kind of statement is not interesting for constant 745169689Skan propagation and, therefore, not worth simulating. */ 746169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 747169689Skan fprintf (dump_file, "No interesting values produced.\n"); 748169689Skan 749169689Skan /* The assignment is not a copy operation. Don't visit this 750169689Skan statement again and mark all the definitions in the statement 751169689Skan to be copies of nothing. */ 752169689Skan FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_ALL_DEFS) 753169689Skan set_copy_of_val (def, def, NULL_TREE); 754169689Skan } 755169689Skan 756169689Skan return retval; 757169689Skan} 758169689Skan 759169689Skan 760169689Skan/* Visit PHI node PHI. If all the arguments produce the same value, 761169689Skan set it to be the value of the LHS of PHI. */ 762169689Skan 763169689Skanstatic enum ssa_prop_result 764169689Skancopy_prop_visit_phi_node (tree phi) 765169689Skan{ 766169689Skan enum ssa_prop_result retval; 767169689Skan int i; 768169689Skan tree lhs; 769169689Skan prop_value_t phi_val = { 0, NULL_TREE, NULL_TREE }; 770169689Skan 771169689Skan lhs = PHI_RESULT (phi); 772169689Skan 773169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 774169689Skan { 775169689Skan fprintf (dump_file, "\nVisiting PHI node: "); 776169689Skan print_generic_expr (dump_file, phi, dump_flags); 777169689Skan fprintf (dump_file, "\n\n"); 778169689Skan } 779169689Skan 780169689Skan for (i = 0; i < PHI_NUM_ARGS (phi); i++) 781169689Skan { 782169689Skan prop_value_t *arg_val; 783169689Skan tree arg = PHI_ARG_DEF (phi, i); 784169689Skan edge e = PHI_ARG_EDGE (phi, i); 785169689Skan 786169689Skan /* We don't care about values flowing through non-executable 787169689Skan edges. */ 788169689Skan if (!(e->flags & EDGE_EXECUTABLE)) 789169689Skan continue; 790169689Skan 791169689Skan /* Constants in the argument list never generate a useful copy. 792169689Skan Similarly, names that flow through abnormal edges cannot be 793169689Skan used to derive copies. */ 794169689Skan if (TREE_CODE (arg) != SSA_NAME || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg)) 795169689Skan { 796169689Skan phi_val.value = lhs; 797169689Skan break; 798169689Skan } 799169689Skan 800169689Skan /* Avoid copy propagation from an inner into an outer loop. 801169689Skan Otherwise, this may move loop variant variables outside of 802169689Skan their loops and prevent coalescing opportunities. If the 803169689Skan value was loop invariant, it will be hoisted by LICM and 804169689Skan exposed for copy propagation. */ 805169689Skan if (loop_depth_of_name (arg) > loop_depth_of_name (lhs)) 806169689Skan { 807169689Skan phi_val.value = lhs; 808169689Skan break; 809169689Skan } 810169689Skan 811169689Skan /* If the LHS appears in the argument list, ignore it. It is 812169689Skan irrelevant as a copy. */ 813169689Skan if (arg == lhs || get_last_copy_of (arg) == lhs) 814169689Skan continue; 815169689Skan 816169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 817169689Skan { 818169689Skan fprintf (dump_file, "\tArgument #%d: ", i); 819169689Skan dump_copy_of (dump_file, arg); 820169689Skan fprintf (dump_file, "\n"); 821169689Skan } 822169689Skan 823169689Skan arg_val = get_copy_of_val (arg); 824169689Skan 825169689Skan /* If the LHS didn't have a value yet, make it a copy of the 826169689Skan first argument we find. Notice that while we make the LHS be 827169689Skan a copy of the argument itself, we take the memory reference 828169689Skan from the argument's value so that we can compare it to the 829169689Skan memory reference of all the other arguments. */ 830169689Skan if (phi_val.value == NULL_TREE) 831169689Skan { 832169689Skan phi_val.value = arg; 833169689Skan phi_val.mem_ref = arg_val->mem_ref; 834169689Skan continue; 835169689Skan } 836169689Skan 837169689Skan /* If PHI_VAL and ARG don't have a common copy-of chain, then 838169689Skan this PHI node cannot be a copy operation. Also, if we are 839169689Skan copy propagating stores and these two arguments came from 840169689Skan different memory references, they cannot be considered 841169689Skan copies. */ 842169689Skan if (get_last_copy_of (phi_val.value) != get_last_copy_of (arg) 843169689Skan || (do_store_copy_prop 844169689Skan && phi_val.mem_ref 845169689Skan && arg_val->mem_ref 846169689Skan && simple_cst_equal (phi_val.mem_ref, arg_val->mem_ref) != 1)) 847169689Skan { 848169689Skan phi_val.value = lhs; 849169689Skan break; 850169689Skan } 851169689Skan } 852169689Skan 853169689Skan if (phi_val.value && set_copy_of_val (lhs, phi_val.value, phi_val.mem_ref)) 854169689Skan retval = (phi_val.value != lhs) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING; 855169689Skan else 856169689Skan retval = SSA_PROP_NOT_INTERESTING; 857169689Skan 858169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 859169689Skan { 860169689Skan fprintf (dump_file, "\nPHI node "); 861169689Skan dump_copy_of (dump_file, lhs); 862169689Skan fprintf (dump_file, "\nTelling the propagator to "); 863169689Skan if (retval == SSA_PROP_INTERESTING) 864169689Skan fprintf (dump_file, "add SSA edges out of this PHI and continue."); 865169689Skan else if (retval == SSA_PROP_VARYING) 866169689Skan fprintf (dump_file, "add SSA edges out of this PHI and never visit again."); 867169689Skan else 868169689Skan fprintf (dump_file, "do nothing with SSA edges and keep iterating."); 869169689Skan fprintf (dump_file, "\n\n"); 870169689Skan } 871169689Skan 872169689Skan return retval; 873169689Skan} 874169689Skan 875169689Skan 876169689Skan/* Initialize structures used for copy propagation. PHIS_ONLY is true 877169689Skan if we should only consider PHI nodes as generating copy propagation 878169689Skan opportunities. */ 879169689Skan 880169689Skanstatic void 881169689Skaninit_copy_prop (void) 882169689Skan{ 883169689Skan basic_block bb; 884169689Skan 885169689Skan copy_of = XNEWVEC (prop_value_t, num_ssa_names); 886169689Skan memset (copy_of, 0, num_ssa_names * sizeof (*copy_of)); 887169689Skan 888169689Skan cached_last_copy_of = XNEWVEC (tree, num_ssa_names); 889169689Skan memset (cached_last_copy_of, 0, num_ssa_names * sizeof (*cached_last_copy_of)); 890169689Skan 891169689Skan FOR_EACH_BB (bb) 892169689Skan { 893169689Skan block_stmt_iterator si; 894169689Skan tree phi, def; 895169689Skan int depth = bb->loop_depth; 896169689Skan 897169689Skan for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) 898169689Skan { 899169689Skan tree stmt = bsi_stmt (si); 900169689Skan ssa_op_iter iter; 901169689Skan 902169689Skan /* The only statements that we care about are those that may 903169689Skan generate useful copies. We also need to mark conditional 904169689Skan jumps so that their outgoing edges are added to the work 905169689Skan lists of the propagator. 906169689Skan 907169689Skan Avoid copy propagation from an inner into an outer loop. 908169689Skan Otherwise, this may move loop variant variables outside of 909169689Skan their loops and prevent coalescing opportunities. If the 910169689Skan value was loop invariant, it will be hoisted by LICM and 911169689Skan exposed for copy propagation. */ 912169689Skan if (stmt_ends_bb_p (stmt)) 913169689Skan DONT_SIMULATE_AGAIN (stmt) = false; 914169689Skan else if (stmt_may_generate_copy (stmt) 915169689Skan && loop_depth_of_name (TREE_OPERAND (stmt, 1)) <= depth) 916169689Skan DONT_SIMULATE_AGAIN (stmt) = false; 917169689Skan else 918169689Skan DONT_SIMULATE_AGAIN (stmt) = true; 919169689Skan 920169689Skan /* Mark all the outputs of this statement as not being 921169689Skan the copy of anything. */ 922169689Skan FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) 923169689Skan if (DONT_SIMULATE_AGAIN (stmt)) 924169689Skan set_copy_of_val (def, def, NULL_TREE); 925169689Skan else 926169689Skan cached_last_copy_of[SSA_NAME_VERSION (def)] = def; 927169689Skan } 928169689Skan 929169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 930169689Skan { 931169689Skan def = PHI_RESULT (phi); 932169689Skan if (!do_store_copy_prop && !is_gimple_reg (def)) 933169689Skan DONT_SIMULATE_AGAIN (phi) = true; 934169689Skan else 935169689Skan DONT_SIMULATE_AGAIN (phi) = false; 936169689Skan 937169689Skan if (DONT_SIMULATE_AGAIN (phi)) 938169689Skan set_copy_of_val (def, def, NULL_TREE); 939169689Skan else 940169689Skan cached_last_copy_of[SSA_NAME_VERSION (def)] = def; 941169689Skan } 942169689Skan } 943169689Skan} 944169689Skan 945169689Skan 946169689Skan/* Deallocate memory used in copy propagation and do final 947169689Skan substitution. */ 948169689Skan 949169689Skanstatic void 950169689Skanfini_copy_prop (void) 951169689Skan{ 952169689Skan size_t i; 953169689Skan prop_value_t *tmp; 954169689Skan 955169689Skan /* Set the final copy-of value for each variable by traversing the 956169689Skan copy-of chains. */ 957169689Skan tmp = XNEWVEC (prop_value_t, num_ssa_names); 958169689Skan memset (tmp, 0, num_ssa_names * sizeof (*tmp)); 959169689Skan for (i = 1; i < num_ssa_names; i++) 960169689Skan { 961169689Skan tree var = ssa_name (i); 962169689Skan if (var && copy_of[i].value && copy_of[i].value != var) 963169689Skan tmp[i].value = get_last_copy_of (var); 964169689Skan } 965169689Skan 966169689Skan substitute_and_fold (tmp, false); 967169689Skan 968169689Skan free (cached_last_copy_of); 969169689Skan free (copy_of); 970169689Skan free (tmp); 971169689Skan} 972169689Skan 973169689Skan 974169689Skan/* Main entry point to the copy propagator. 975169689Skan 976169689Skan PHIS_ONLY is true if we should only consider PHI nodes as generating 977169689Skan copy propagation opportunities. 978169689Skan 979169689Skan The algorithm propagates the value COPY-OF using ssa_propagate. For 980169689Skan every variable X_i, COPY-OF(X_i) indicates which variable is X_i created 981169689Skan from. The following example shows how the algorithm proceeds at a 982169689Skan high level: 983169689Skan 984169689Skan 1 a_24 = x_1 985169689Skan 2 a_2 = PHI <a_24, x_1> 986169689Skan 3 a_5 = PHI <a_2> 987169689Skan 4 x_1 = PHI <x_298, a_5, a_2> 988169689Skan 989169689Skan The end result should be that a_2, a_5, a_24 and x_1 are a copy of 990169689Skan x_298. Propagation proceeds as follows. 991169689Skan 992169689Skan Visit #1: a_24 is copy-of x_1. Value changed. 993169689Skan Visit #2: a_2 is copy-of x_1. Value changed. 994169689Skan Visit #3: a_5 is copy-of x_1. Value changed. 995169689Skan Visit #4: x_1 is copy-of x_298. Value changed. 996169689Skan Visit #1: a_24 is copy-of x_298. Value changed. 997169689Skan Visit #2: a_2 is copy-of x_298. Value changed. 998169689Skan Visit #3: a_5 is copy-of x_298. Value changed. 999169689Skan Visit #4: x_1 is copy-of x_298. Stable state reached. 1000169689Skan 1001169689Skan When visiting PHI nodes, we only consider arguments that flow 1002169689Skan through edges marked executable by the propagation engine. So, 1003169689Skan when visiting statement #2 for the first time, we will only look at 1004169689Skan the first argument (a_24) and optimistically assume that its value 1005169689Skan is the copy of a_24 (x_1). 1006169689Skan 1007169689Skan The problem with this approach is that it may fail to discover copy 1008169689Skan relations in PHI cycles. Instead of propagating copy-of 1009169689Skan values, we actually propagate copy-of chains. For instance: 1010169689Skan 1011169689Skan A_3 = B_1; 1012169689Skan C_9 = A_3; 1013169689Skan D_4 = C_9; 1014169689Skan X_i = D_4; 1015169689Skan 1016169689Skan In this code fragment, COPY-OF (X_i) = { D_4, C_9, A_3, B_1 }. 1017169689Skan Obviously, we are only really interested in the last value of the 1018169689Skan chain, however the propagator needs to access the copy-of chain 1019169689Skan when visiting PHI nodes. 1020169689Skan 1021169689Skan To represent the copy-of chain, we use the array COPY_CHAINS, which 1022169689Skan holds the first link in the copy-of chain for every variable. 1023169689Skan If variable X_i is a copy of X_j, which in turn is a copy of X_k, 1024169689Skan the array will contain: 1025169689Skan 1026169689Skan COPY_CHAINS[i] = X_j 1027169689Skan COPY_CHAINS[j] = X_k 1028169689Skan COPY_CHAINS[k] = X_k 1029169689Skan 1030169689Skan Keeping copy-of chains instead of copy-of values directly becomes 1031169689Skan important when visiting PHI nodes. Suppose that we had the 1032169689Skan following PHI cycle, such that x_52 is already considered a copy of 1033169689Skan x_53: 1034169689Skan 1035169689Skan 1 x_54 = PHI <x_53, x_52> 1036169689Skan 2 x_53 = PHI <x_898, x_54> 1037169689Skan 1038169689Skan Visit #1: x_54 is copy-of x_53 (because x_52 is copy-of x_53) 1039169689Skan Visit #2: x_53 is copy-of x_898 (because x_54 is a copy of x_53, 1040169689Skan so it is considered irrelevant 1041169689Skan as a copy). 1042169689Skan Visit #1: x_54 is copy-of nothing (x_53 is a copy-of x_898 and 1043169689Skan x_52 is a copy of x_53, so 1044169689Skan they don't match) 1045169689Skan Visit #2: x_53 is copy-of nothing 1046169689Skan 1047169689Skan This problem is avoided by keeping a chain of copies, instead of 1048169689Skan the final copy-of value. Propagation will now only keep the first 1049169689Skan element of a variable's copy-of chain. When visiting PHI nodes, 1050169689Skan arguments are considered equal if their copy-of chains end in the 1051169689Skan same variable. So, as long as their copy-of chains overlap, we 1052169689Skan know that they will be a copy of the same variable, regardless of 1053169689Skan which variable that may be). 1054169689Skan 1055169689Skan Propagation would then proceed as follows (the notation a -> b 1056169689Skan means that a is a copy-of b): 1057169689Skan 1058169689Skan Visit #1: x_54 = PHI <x_53, x_52> 1059169689Skan x_53 -> x_53 1060169689Skan x_52 -> x_53 1061169689Skan Result: x_54 -> x_53. Value changed. Add SSA edges. 1062169689Skan 1063169689Skan Visit #1: x_53 = PHI <x_898, x_54> 1064169689Skan x_898 -> x_898 1065169689Skan x_54 -> x_53 1066169689Skan Result: x_53 -> x_898. Value changed. Add SSA edges. 1067169689Skan 1068169689Skan Visit #2: x_54 = PHI <x_53, x_52> 1069169689Skan x_53 -> x_898 1070169689Skan x_52 -> x_53 -> x_898 1071169689Skan Result: x_54 -> x_898. Value changed. Add SSA edges. 1072169689Skan 1073169689Skan Visit #2: x_53 = PHI <x_898, x_54> 1074169689Skan x_898 -> x_898 1075169689Skan x_54 -> x_898 1076169689Skan Result: x_53 -> x_898. Value didn't change. Stable state 1077169689Skan 1078169689Skan Once the propagator stabilizes, we end up with the desired result 1079169689Skan x_53 and x_54 are both copies of x_898. */ 1080169689Skan 1081169689Skanstatic void 1082169689Skanexecute_copy_prop (bool store_copy_prop) 1083169689Skan{ 1084169689Skan do_store_copy_prop = store_copy_prop; 1085169689Skan init_copy_prop (); 1086169689Skan ssa_propagate (copy_prop_visit_stmt, copy_prop_visit_phi_node); 1087169689Skan fini_copy_prop (); 1088169689Skan} 1089169689Skan 1090169689Skan 1091169689Skanstatic bool 1092169689Skangate_copy_prop (void) 1093169689Skan{ 1094169689Skan return flag_tree_copy_prop != 0; 1095169689Skan} 1096169689Skan 1097169689Skanstatic unsigned int 1098169689Skando_copy_prop (void) 1099169689Skan{ 1100169689Skan execute_copy_prop (false); 1101169689Skan return 0; 1102169689Skan} 1103169689Skan 1104169689Skanstruct tree_opt_pass pass_copy_prop = 1105169689Skan{ 1106169689Skan "copyprop", /* name */ 1107169689Skan gate_copy_prop, /* gate */ 1108169689Skan do_copy_prop, /* execute */ 1109169689Skan NULL, /* sub */ 1110169689Skan NULL, /* next */ 1111169689Skan 0, /* static_pass_number */ 1112169689Skan TV_TREE_COPY_PROP, /* tv_id */ 1113169689Skan PROP_ssa | PROP_alias | PROP_cfg, /* properties_required */ 1114169689Skan 0, /* properties_provided */ 1115169689Skan 0, /* properties_destroyed */ 1116169689Skan 0, /* todo_flags_start */ 1117169689Skan TODO_cleanup_cfg 1118169689Skan | TODO_dump_func 1119169689Skan | TODO_ggc_collect 1120169689Skan | TODO_verify_ssa 1121169689Skan | TODO_update_ssa, /* todo_flags_finish */ 1122169689Skan 0 /* letter */ 1123169689Skan}; 1124169689Skan 1125169689Skanstatic bool 1126169689Skangate_store_copy_prop (void) 1127169689Skan{ 1128169689Skan /* STORE-COPY-PROP is enabled only with -ftree-store-copy-prop, but 1129169689Skan when -fno-tree-store-copy-prop is specified, we should run 1130169689Skan regular COPY-PROP. That's why the pass is enabled with either 1131169689Skan flag. */ 1132169689Skan return flag_tree_store_copy_prop != 0 || flag_tree_copy_prop != 0; 1133169689Skan} 1134169689Skan 1135169689Skanstatic unsigned int 1136169689Skanstore_copy_prop (void) 1137169689Skan{ 1138169689Skan /* If STORE-COPY-PROP is not enabled, we just run regular COPY-PROP. */ 1139169689Skan execute_copy_prop (flag_tree_store_copy_prop != 0); 1140169689Skan return 0; 1141169689Skan} 1142169689Skan 1143169689Skanstruct tree_opt_pass pass_store_copy_prop = 1144169689Skan{ 1145169689Skan "store_copyprop", /* name */ 1146169689Skan gate_store_copy_prop, /* gate */ 1147169689Skan store_copy_prop, /* execute */ 1148169689Skan NULL, /* sub */ 1149169689Skan NULL, /* next */ 1150169689Skan 0, /* static_pass_number */ 1151169689Skan TV_TREE_STORE_COPY_PROP, /* tv_id */ 1152169689Skan PROP_ssa | PROP_alias | PROP_cfg, /* properties_required */ 1153169689Skan 0, /* properties_provided */ 1154169689Skan 0, /* properties_destroyed */ 1155169689Skan 0, /* todo_flags_start */ 1156169689Skan TODO_dump_func 1157169689Skan | TODO_cleanup_cfg 1158169689Skan | TODO_ggc_collect 1159169689Skan | TODO_verify_ssa 1160169689Skan | TODO_update_ssa, /* todo_flags_finish */ 1161169689Skan 0 /* letter */ 1162169689Skan}; 1163