1169689Skan/* Conditional constant propagation pass for the GNU compiler. 2169689Skan Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007 3169689Skan Free Software Foundation, Inc. 4169689Skan Adapted from original RTL SSA-CCP by Daniel Berlin <dberlin@dberlin.org> 5169689Skan Adapted to GIMPLE trees by Diego Novillo <dnovillo@redhat.com> 6169689Skan 7169689SkanThis file is part of GCC. 8169689Skan 9169689SkanGCC is free software; you can redistribute it and/or modify it 10169689Skanunder the terms of the GNU General Public License as published by the 11169689SkanFree Software Foundation; either version 2, or (at your option) any 12169689Skanlater version. 13169689Skan 14169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT 15169689SkanANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 16169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 17169689Skanfor more details. 18169689Skan 19169689SkanYou should have received a copy of the GNU General Public License 20169689Skanalong with GCC; see the file COPYING. If not, write to the Free 21169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 22169689Skan02110-1301, USA. */ 23169689Skan 24169689Skan/* Conditional constant propagation (CCP) is based on the SSA 25169689Skan propagation engine (tree-ssa-propagate.c). Constant assignments of 26169689Skan the form VAR = CST are propagated from the assignments into uses of 27169689Skan VAR, which in turn may generate new constants. The simulation uses 28169689Skan a four level lattice to keep track of constant values associated 29169689Skan with SSA names. Given an SSA name V_i, it may take one of the 30169689Skan following values: 31169689Skan 32169689Skan UNINITIALIZED -> This is the default starting value. V_i 33169689Skan has not been processed yet. 34169689Skan 35169689Skan UNDEFINED -> V_i is a local variable whose definition 36169689Skan has not been processed yet. Therefore we 37169689Skan don't yet know if its value is a constant 38169689Skan or not. 39169689Skan 40169689Skan CONSTANT -> V_i has been found to hold a constant 41169689Skan value C. 42169689Skan 43169689Skan VARYING -> V_i cannot take a constant value, or if it 44169689Skan does, it is not possible to determine it 45169689Skan at compile time. 46169689Skan 47169689Skan The core of SSA-CCP is in ccp_visit_stmt and ccp_visit_phi_node: 48169689Skan 49169689Skan 1- In ccp_visit_stmt, we are interested in assignments whose RHS 50169689Skan evaluates into a constant and conditional jumps whose predicate 51169689Skan evaluates into a boolean true or false. When an assignment of 52169689Skan the form V_i = CONST is found, V_i's lattice value is set to 53169689Skan CONSTANT and CONST is associated with it. This causes the 54169689Skan propagation engine to add all the SSA edges coming out the 55169689Skan assignment into the worklists, so that statements that use V_i 56169689Skan can be visited. 57169689Skan 58169689Skan If the statement is a conditional with a constant predicate, we 59169689Skan mark the outgoing edges as executable or not executable 60169689Skan depending on the predicate's value. This is then used when 61169689Skan visiting PHI nodes to know when a PHI argument can be ignored. 62169689Skan 63169689Skan 64169689Skan 2- In ccp_visit_phi_node, if all the PHI arguments evaluate to the 65169689Skan same constant C, then the LHS of the PHI is set to C. This 66169689Skan evaluation is known as the "meet operation". Since one of the 67169689Skan goals of this evaluation is to optimistically return constant 68169689Skan values as often as possible, it uses two main short cuts: 69169689Skan 70169689Skan - If an argument is flowing in through a non-executable edge, it 71169689Skan is ignored. This is useful in cases like this: 72169689Skan 73169689Skan if (PRED) 74169689Skan a_9 = 3; 75169689Skan else 76169689Skan a_10 = 100; 77169689Skan a_11 = PHI (a_9, a_10) 78169689Skan 79169689Skan If PRED is known to always evaluate to false, then we can 80169689Skan assume that a_11 will always take its value from a_10, meaning 81169689Skan that instead of consider it VARYING (a_9 and a_10 have 82169689Skan different values), we can consider it CONSTANT 100. 83169689Skan 84169689Skan - If an argument has an UNDEFINED value, then it does not affect 85169689Skan the outcome of the meet operation. If a variable V_i has an 86169689Skan UNDEFINED value, it means that either its defining statement 87169689Skan hasn't been visited yet or V_i has no defining statement, in 88169689Skan which case the original symbol 'V' is being used 89169689Skan uninitialized. Since 'V' is a local variable, the compiler 90169689Skan may assume any initial value for it. 91169689Skan 92169689Skan 93169689Skan After propagation, every variable V_i that ends up with a lattice 94169689Skan value of CONSTANT will have the associated constant value in the 95169689Skan array CONST_VAL[i].VALUE. That is fed into substitute_and_fold for 96169689Skan final substitution and folding. 97169689Skan 98169689Skan 99169689Skan Constant propagation in stores and loads (STORE-CCP) 100169689Skan ---------------------------------------------------- 101169689Skan 102169689Skan While CCP has all the logic to propagate constants in GIMPLE 103169689Skan registers, it is missing the ability to associate constants with 104169689Skan stores and loads (i.e., pointer dereferences, structures and 105169689Skan global/aliased variables). We don't keep loads and stores in 106169689Skan SSA, but we do build a factored use-def web for them (in the 107169689Skan virtual operands). 108169689Skan 109169689Skan For instance, consider the following code fragment: 110169689Skan 111169689Skan struct A a; 112169689Skan const int B = 42; 113169689Skan 114169689Skan void foo (int i) 115169689Skan { 116169689Skan if (i > 10) 117169689Skan a.a = 42; 118169689Skan else 119169689Skan { 120169689Skan a.b = 21; 121169689Skan a.a = a.b + 21; 122169689Skan } 123169689Skan 124169689Skan if (a.a != B) 125169689Skan never_executed (); 126169689Skan } 127169689Skan 128169689Skan We should be able to deduce that the predicate 'a.a != B' is always 129169689Skan false. To achieve this, we associate constant values to the SSA 130169689Skan names in the V_MAY_DEF and V_MUST_DEF operands for each store. 131169689Skan Additionally, since we also glob partial loads/stores with the base 132169689Skan symbol, we also keep track of the memory reference where the 133169689Skan constant value was stored (in the MEM_REF field of PROP_VALUE_T). 134169689Skan For instance, 135169689Skan 136169689Skan # a_5 = V_MAY_DEF <a_4> 137169689Skan a.a = 2; 138169689Skan 139169689Skan # VUSE <a_5> 140169689Skan x_3 = a.b; 141169689Skan 142169689Skan In the example above, CCP will associate value '2' with 'a_5', but 143169689Skan it would be wrong to replace the load from 'a.b' with '2', because 144169689Skan '2' had been stored into a.a. 145169689Skan 146169689Skan To support STORE-CCP, it is necessary to add a new value to the 147169689Skan constant propagation lattice. When evaluating a load for a memory 148169689Skan reference we can no longer assume a value of UNDEFINED if we 149169689Skan haven't seen a preceding store to the same memory location. 150169689Skan Consider, for instance global variables: 151169689Skan 152169689Skan int A; 153169689Skan 154169689Skan foo (int i) 155169689Skan { 156169689Skan if (i_3 > 10) 157169689Skan A_4 = 3; 158169689Skan # A_5 = PHI (A_4, A_2); 159169689Skan 160169689Skan # VUSE <A_5> 161169689Skan A.0_6 = A; 162169689Skan 163169689Skan return A.0_6; 164169689Skan } 165169689Skan 166169689Skan The value of A_2 cannot be assumed to be UNDEFINED, as it may have 167169689Skan been defined outside of foo. If we were to assume it UNDEFINED, we 168169689Skan would erroneously optimize the above into 'return 3;'. Therefore, 169169689Skan when doing STORE-CCP, we introduce a fifth lattice value 170169689Skan (UNKNOWN_VAL), which overrides any other value when computing the 171169689Skan meet operation in PHI nodes. 172169689Skan 173169689Skan Though STORE-CCP is not too expensive, it does have to do more work 174169689Skan than regular CCP, so it is only enabled at -O2. Both regular CCP 175169689Skan and STORE-CCP use the exact same algorithm. The only distinction 176169689Skan is that when doing STORE-CCP, the boolean variable DO_STORE_CCP is 177169689Skan set to true. This affects the evaluation of statements and PHI 178169689Skan nodes. 179169689Skan 180169689Skan References: 181169689Skan 182169689Skan Constant propagation with conditional branches, 183169689Skan Wegman and Zadeck, ACM TOPLAS 13(2):181-210. 184169689Skan 185169689Skan Building an Optimizing Compiler, 186169689Skan Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9. 187169689Skan 188169689Skan Advanced Compiler Design and Implementation, 189169689Skan Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */ 190169689Skan 191169689Skan#include "config.h" 192169689Skan#include "system.h" 193169689Skan#include "coretypes.h" 194169689Skan#include "tm.h" 195169689Skan#include "tree.h" 196169689Skan#include "flags.h" 197169689Skan#include "rtl.h" 198169689Skan#include "tm_p.h" 199169689Skan#include "ggc.h" 200169689Skan#include "basic-block.h" 201169689Skan#include "output.h" 202169689Skan#include "expr.h" 203169689Skan#include "function.h" 204169689Skan#include "diagnostic.h" 205169689Skan#include "timevar.h" 206169689Skan#include "tree-dump.h" 207169689Skan#include "tree-flow.h" 208169689Skan#include "tree-pass.h" 209169689Skan#include "tree-ssa-propagate.h" 210169689Skan#include "langhooks.h" 211169689Skan#include "target.h" 212169689Skan#include "toplev.h" 213169689Skan 214169689Skan 215169689Skan/* Possible lattice values. */ 216169689Skantypedef enum 217169689Skan{ 218169689Skan UNINITIALIZED = 0, 219169689Skan UNDEFINED, 220169689Skan UNKNOWN_VAL, 221169689Skan CONSTANT, 222169689Skan VARYING 223169689Skan} ccp_lattice_t; 224169689Skan 225169689Skan/* Array of propagated constant values. After propagation, 226169689Skan CONST_VAL[I].VALUE holds the constant value for SSA_NAME(I). If 227169689Skan the constant is held in an SSA name representing a memory store 228169689Skan (i.e., a V_MAY_DEF or V_MUST_DEF), CONST_VAL[I].MEM_REF will 229169689Skan contain the actual memory reference used to store (i.e., the LHS of 230169689Skan the assignment doing the store). */ 231169689Skanstatic prop_value_t *const_val; 232169689Skan 233169689Skan/* True if we are also propagating constants in stores and loads. */ 234169689Skanstatic bool do_store_ccp; 235169689Skan 236169689Skan/* Dump constant propagation value VAL to file OUTF prefixed by PREFIX. */ 237169689Skan 238169689Skanstatic void 239169689Skandump_lattice_value (FILE *outf, const char *prefix, prop_value_t val) 240169689Skan{ 241169689Skan switch (val.lattice_val) 242169689Skan { 243169689Skan case UNINITIALIZED: 244169689Skan fprintf (outf, "%sUNINITIALIZED", prefix); 245169689Skan break; 246169689Skan case UNDEFINED: 247169689Skan fprintf (outf, "%sUNDEFINED", prefix); 248169689Skan break; 249169689Skan case VARYING: 250169689Skan fprintf (outf, "%sVARYING", prefix); 251169689Skan break; 252169689Skan case UNKNOWN_VAL: 253169689Skan fprintf (outf, "%sUNKNOWN_VAL", prefix); 254169689Skan break; 255169689Skan case CONSTANT: 256169689Skan fprintf (outf, "%sCONSTANT ", prefix); 257169689Skan print_generic_expr (outf, val.value, dump_flags); 258169689Skan break; 259169689Skan default: 260169689Skan gcc_unreachable (); 261169689Skan } 262169689Skan} 263169689Skan 264169689Skan 265169689Skan/* Print lattice value VAL to stderr. */ 266169689Skan 267169689Skanvoid debug_lattice_value (prop_value_t val); 268169689Skan 269169689Skanvoid 270169689Skandebug_lattice_value (prop_value_t val) 271169689Skan{ 272169689Skan dump_lattice_value (stderr, "", val); 273169689Skan fprintf (stderr, "\n"); 274169689Skan} 275169689Skan 276169689Skan 277169689Skan/* The regular is_gimple_min_invariant does a shallow test of the object. 278169689Skan It assumes that full gimplification has happened, or will happen on the 279169689Skan object. For a value coming from DECL_INITIAL, this is not true, so we 280169689Skan have to be more strict ourselves. */ 281169689Skan 282169689Skanstatic bool 283169689Skanccp_decl_initial_min_invariant (tree t) 284169689Skan{ 285169689Skan if (!is_gimple_min_invariant (t)) 286169689Skan return false; 287169689Skan if (TREE_CODE (t) == ADDR_EXPR) 288169689Skan { 289169689Skan /* Inline and unroll is_gimple_addressable. */ 290169689Skan while (1) 291169689Skan { 292169689Skan t = TREE_OPERAND (t, 0); 293169689Skan if (is_gimple_id (t)) 294169689Skan return true; 295169689Skan if (!handled_component_p (t)) 296169689Skan return false; 297169689Skan } 298169689Skan } 299169689Skan return true; 300169689Skan} 301169689Skan 302169689Skan 303169689Skan/* Compute a default value for variable VAR and store it in the 304169689Skan CONST_VAL array. The following rules are used to get default 305169689Skan values: 306169689Skan 307169689Skan 1- Global and static variables that are declared constant are 308169689Skan considered CONSTANT. 309169689Skan 310169689Skan 2- Any other value is considered UNDEFINED. This is useful when 311169689Skan considering PHI nodes. PHI arguments that are undefined do not 312169689Skan change the constant value of the PHI node, which allows for more 313169689Skan constants to be propagated. 314169689Skan 315169689Skan 3- If SSA_NAME_VALUE is set and it is a constant, its value is 316169689Skan used. 317169689Skan 318169689Skan 4- Variables defined by statements other than assignments and PHI 319169689Skan nodes are considered VARYING. 320169689Skan 321169689Skan 5- Variables that are not GIMPLE registers are considered 322169689Skan UNKNOWN_VAL, which is really a stronger version of UNDEFINED. 323169689Skan It's used to avoid the short circuit evaluation implied by 324169689Skan UNDEFINED in ccp_lattice_meet. */ 325169689Skan 326169689Skanstatic prop_value_t 327169689Skanget_default_value (tree var) 328169689Skan{ 329169689Skan tree sym = SSA_NAME_VAR (var); 330169689Skan prop_value_t val = { UNINITIALIZED, NULL_TREE, NULL_TREE }; 331169689Skan 332169689Skan if (!do_store_ccp && !is_gimple_reg (var)) 333169689Skan { 334169689Skan /* Short circuit for regular CCP. We are not interested in any 335169689Skan non-register when DO_STORE_CCP is false. */ 336169689Skan val.lattice_val = VARYING; 337169689Skan } 338169689Skan else if (SSA_NAME_VALUE (var) 339169689Skan && is_gimple_min_invariant (SSA_NAME_VALUE (var))) 340169689Skan { 341169689Skan val.lattice_val = CONSTANT; 342169689Skan val.value = SSA_NAME_VALUE (var); 343169689Skan } 344169689Skan else if (TREE_STATIC (sym) 345169689Skan && TREE_READONLY (sym) 346169689Skan && !MTAG_P (sym) 347169689Skan && DECL_INITIAL (sym) 348169689Skan && ccp_decl_initial_min_invariant (DECL_INITIAL (sym))) 349169689Skan { 350169689Skan /* Globals and static variables declared 'const' take their 351169689Skan initial value. */ 352169689Skan val.lattice_val = CONSTANT; 353169689Skan val.value = DECL_INITIAL (sym); 354169689Skan val.mem_ref = sym; 355169689Skan } 356169689Skan else 357169689Skan { 358169689Skan tree stmt = SSA_NAME_DEF_STMT (var); 359169689Skan 360169689Skan if (IS_EMPTY_STMT (stmt)) 361169689Skan { 362169689Skan /* Variables defined by an empty statement are those used 363169689Skan before being initialized. If VAR is a local variable, we 364169689Skan can assume initially that it is UNDEFINED. If we are 365169689Skan doing STORE-CCP, function arguments and non-register 366169689Skan variables are initially UNKNOWN_VAL, because we cannot 367169689Skan discard the value incoming from outside of this function 368169689Skan (see ccp_lattice_meet for details). */ 369169689Skan if (is_gimple_reg (sym) && TREE_CODE (sym) != PARM_DECL) 370169689Skan val.lattice_val = UNDEFINED; 371169689Skan else if (do_store_ccp) 372169689Skan val.lattice_val = UNKNOWN_VAL; 373169689Skan else 374169689Skan val.lattice_val = VARYING; 375169689Skan } 376169689Skan else if (TREE_CODE (stmt) == MODIFY_EXPR 377169689Skan || TREE_CODE (stmt) == PHI_NODE) 378169689Skan { 379169689Skan /* Any other variable defined by an assignment or a PHI node 380169689Skan is considered UNDEFINED (or UNKNOWN_VAL if VAR is not a 381169689Skan GIMPLE register). */ 382169689Skan val.lattice_val = is_gimple_reg (sym) ? UNDEFINED : UNKNOWN_VAL; 383169689Skan } 384169689Skan else 385169689Skan { 386169689Skan /* Otherwise, VAR will never take on a constant value. */ 387169689Skan val.lattice_val = VARYING; 388169689Skan } 389169689Skan } 390169689Skan 391169689Skan return val; 392169689Skan} 393169689Skan 394169689Skan 395169689Skan/* Get the constant value associated with variable VAR. If 396169689Skan MAY_USE_DEFAULT_P is true, call get_default_value on variables that 397169689Skan have the lattice value UNINITIALIZED. */ 398169689Skan 399169689Skanstatic prop_value_t * 400169689Skanget_value (tree var, bool may_use_default_p) 401169689Skan{ 402169689Skan prop_value_t *val = &const_val[SSA_NAME_VERSION (var)]; 403169689Skan if (may_use_default_p && val->lattice_val == UNINITIALIZED) 404169689Skan *val = get_default_value (var); 405169689Skan 406169689Skan return val; 407169689Skan} 408169689Skan 409169689Skan 410169689Skan/* Set the value for variable VAR to NEW_VAL. Return true if the new 411169689Skan value is different from VAR's previous value. */ 412169689Skan 413169689Skanstatic bool 414169689Skanset_lattice_value (tree var, prop_value_t new_val) 415169689Skan{ 416169689Skan prop_value_t *old_val = get_value (var, false); 417169689Skan 418169689Skan /* Lattice transitions must always be monotonically increasing in 419169689Skan value. We allow two exceptions: 420169689Skan 421169689Skan 1- If *OLD_VAL and NEW_VAL are the same, return false to 422169689Skan inform the caller that this was a non-transition. 423169689Skan 424169689Skan 2- If we are doing store-ccp (i.e., DOING_STORE_CCP is true), 425169689Skan allow CONSTANT->UNKNOWN_VAL. The UNKNOWN_VAL state is a 426169689Skan special type of UNDEFINED state which prevents the short 427169689Skan circuit evaluation of PHI arguments (see ccp_visit_phi_node 428169689Skan and ccp_lattice_meet). */ 429169689Skan gcc_assert (old_val->lattice_val <= new_val.lattice_val 430169689Skan || (old_val->lattice_val == new_val.lattice_val 431169689Skan && old_val->value == new_val.value 432169689Skan && old_val->mem_ref == new_val.mem_ref) 433169689Skan || (do_store_ccp 434169689Skan && old_val->lattice_val == CONSTANT 435169689Skan && new_val.lattice_val == UNKNOWN_VAL)); 436169689Skan 437169689Skan if (old_val->lattice_val != new_val.lattice_val) 438169689Skan { 439169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 440169689Skan { 441169689Skan dump_lattice_value (dump_file, "Lattice value changed to ", new_val); 442169689Skan fprintf (dump_file, ". %sdding SSA edges to worklist.\n", 443169689Skan new_val.lattice_val != UNDEFINED ? "A" : "Not a"); 444169689Skan } 445169689Skan 446169689Skan *old_val = new_val; 447169689Skan 448169689Skan /* Transitions UNINITIALIZED -> UNDEFINED are never interesting 449169689Skan for propagation purposes. In these cases return false to 450169689Skan avoid doing useless work. */ 451169689Skan return (new_val.lattice_val != UNDEFINED); 452169689Skan } 453169689Skan 454169689Skan return false; 455169689Skan} 456169689Skan 457169689Skan 458169689Skan/* Return the likely CCP lattice value for STMT. 459169689Skan 460169689Skan If STMT has no operands, then return CONSTANT. 461169689Skan 462169689Skan Else if any operands of STMT are undefined, then return UNDEFINED. 463169689Skan 464169689Skan Else if any operands of STMT are constants, then return CONSTANT. 465169689Skan 466169689Skan Else return VARYING. */ 467169689Skan 468169689Skanstatic ccp_lattice_t 469169689Skanlikely_value (tree stmt) 470169689Skan{ 471169689Skan bool found_constant; 472169689Skan stmt_ann_t ann; 473169689Skan tree use; 474169689Skan ssa_op_iter iter; 475169689Skan 476169689Skan ann = stmt_ann (stmt); 477169689Skan 478169689Skan /* If the statement has volatile operands, it won't fold to a 479169689Skan constant value. */ 480169689Skan if (ann->has_volatile_ops) 481169689Skan return VARYING; 482169689Skan 483169689Skan /* If we are not doing store-ccp, statements with loads 484169689Skan and/or stores will never fold into a constant. */ 485169689Skan if (!do_store_ccp 486169689Skan && !ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) 487169689Skan return VARYING; 488169689Skan 489169689Skan 490169689Skan /* A CALL_EXPR is assumed to be varying. NOTE: This may be overly 491169689Skan conservative, in the presence of const and pure calls. */ 492169689Skan if (get_call_expr_in (stmt) != NULL_TREE) 493169689Skan return VARYING; 494169689Skan 495169689Skan /* Anything other than assignments and conditional jumps are not 496169689Skan interesting for CCP. */ 497169689Skan if (TREE_CODE (stmt) != MODIFY_EXPR 498169689Skan && TREE_CODE (stmt) != COND_EXPR 499169689Skan && TREE_CODE (stmt) != SWITCH_EXPR) 500169689Skan return VARYING; 501169689Skan 502169689Skan if (is_gimple_min_invariant (get_rhs (stmt))) 503169689Skan return CONSTANT; 504169689Skan 505169689Skan found_constant = false; 506169689Skan FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE|SSA_OP_VUSE) 507169689Skan { 508169689Skan prop_value_t *val = get_value (use, true); 509169689Skan 510169689Skan if (val->lattice_val == VARYING) 511169689Skan return VARYING; 512169689Skan 513169689Skan if (val->lattice_val == UNKNOWN_VAL) 514169689Skan { 515169689Skan /* UNKNOWN_VAL is invalid when not doing STORE-CCP. */ 516169689Skan gcc_assert (do_store_ccp); 517169689Skan return UNKNOWN_VAL; 518169689Skan } 519169689Skan 520169689Skan if (val->lattice_val == CONSTANT) 521169689Skan found_constant = true; 522169689Skan } 523169689Skan 524169689Skan if (found_constant 525169689Skan || ZERO_SSA_OPERANDS (stmt, SSA_OP_USE) 526169689Skan || ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE)) 527169689Skan return CONSTANT; 528169689Skan 529169689Skan return UNDEFINED; 530169689Skan} 531169689Skan 532169689Skan 533169689Skan/* Initialize local data structures for CCP. */ 534169689Skan 535169689Skanstatic void 536169689Skanccp_initialize (void) 537169689Skan{ 538169689Skan basic_block bb; 539169689Skan 540169689Skan const_val = XNEWVEC (prop_value_t, num_ssa_names); 541169689Skan memset (const_val, 0, num_ssa_names * sizeof (*const_val)); 542169689Skan 543169689Skan /* Initialize simulation flags for PHI nodes and statements. */ 544169689Skan FOR_EACH_BB (bb) 545169689Skan { 546169689Skan block_stmt_iterator i; 547169689Skan 548169689Skan for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i)) 549169689Skan { 550169689Skan bool is_varying = false; 551169689Skan tree stmt = bsi_stmt (i); 552169689Skan 553169689Skan if (likely_value (stmt) == VARYING) 554169689Skan 555169689Skan { 556169689Skan tree def; 557169689Skan ssa_op_iter iter; 558169689Skan 559169689Skan /* If the statement will not produce a constant, mark 560169689Skan all its outputs VARYING. */ 561169689Skan FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) 562169689Skan get_value (def, false)->lattice_val = VARYING; 563169689Skan 564169689Skan /* Never mark conditional jumps with DONT_SIMULATE_AGAIN, 565169689Skan otherwise the propagator will never add the outgoing 566169689Skan control edges. */ 567169689Skan if (TREE_CODE (stmt) != COND_EXPR 568169689Skan && TREE_CODE (stmt) != SWITCH_EXPR) 569169689Skan is_varying = true; 570169689Skan } 571169689Skan 572169689Skan DONT_SIMULATE_AGAIN (stmt) = is_varying; 573169689Skan } 574169689Skan } 575169689Skan 576169689Skan /* Now process PHI nodes. */ 577169689Skan FOR_EACH_BB (bb) 578169689Skan { 579169689Skan tree phi; 580169689Skan 581169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 582169689Skan { 583169689Skan int i; 584169689Skan tree arg; 585169689Skan prop_value_t *val = get_value (PHI_RESULT (phi), false); 586169689Skan 587169689Skan for (i = 0; i < PHI_NUM_ARGS (phi); i++) 588169689Skan { 589169689Skan arg = PHI_ARG_DEF (phi, i); 590169689Skan 591169689Skan if (TREE_CODE (arg) == SSA_NAME 592169689Skan && get_value (arg, false)->lattice_val == VARYING) 593169689Skan { 594169689Skan val->lattice_val = VARYING; 595169689Skan break; 596169689Skan } 597169689Skan } 598169689Skan 599169689Skan DONT_SIMULATE_AGAIN (phi) = (val->lattice_val == VARYING); 600169689Skan } 601169689Skan } 602169689Skan} 603169689Skan 604169689Skan 605169689Skan/* Do final substitution of propagated values, cleanup the flowgraph and 606169689Skan free allocated storage. */ 607169689Skan 608169689Skanstatic void 609169689Skanccp_finalize (void) 610169689Skan{ 611169689Skan /* Perform substitutions based on the known constant values. */ 612169689Skan substitute_and_fold (const_val, false); 613169689Skan 614169689Skan free (const_val); 615169689Skan} 616169689Skan 617169689Skan 618169689Skan/* Compute the meet operator between *VAL1 and *VAL2. Store the result 619169689Skan in VAL1. 620169689Skan 621169689Skan any M UNDEFINED = any 622169689Skan any M UNKNOWN_VAL = UNKNOWN_VAL 623169689Skan any M VARYING = VARYING 624169689Skan Ci M Cj = Ci if (i == j) 625169689Skan Ci M Cj = VARYING if (i != j) 626169689Skan 627169689Skan Lattice values UNKNOWN_VAL and UNDEFINED are similar but have 628169689Skan different semantics at PHI nodes. Both values imply that we don't 629169689Skan know whether the variable is constant or not. However, UNKNOWN_VAL 630169689Skan values override all others. For instance, suppose that A is a 631169689Skan global variable: 632169689Skan 633169689Skan +------+ 634169689Skan | | 635169689Skan | / \ 636169689Skan | / \ 637169689Skan | | A_1 = 4 638169689Skan | \ / 639169689Skan | \ / 640169689Skan | A_3 = PHI (A_2, A_1) 641169689Skan | ... = A_3 642169689Skan | | 643169689Skan +----+ 644169689Skan 645169689Skan If the edge into A_2 is not executable, the first visit to A_3 will 646169689Skan yield the constant 4. But the second visit to A_3 will be with A_2 647169689Skan in state UNKNOWN_VAL. We can no longer conclude that A_3 is 4 648169689Skan because A_2 may have been set in another function. If we had used 649169689Skan the lattice value UNDEFINED, we would have had wrongly concluded 650169689Skan that A_3 is 4. */ 651169689Skan 652169689Skan 653169689Skanstatic void 654169689Skanccp_lattice_meet (prop_value_t *val1, prop_value_t *val2) 655169689Skan{ 656169689Skan if (val1->lattice_val == UNDEFINED) 657169689Skan { 658169689Skan /* UNDEFINED M any = any */ 659169689Skan *val1 = *val2; 660169689Skan } 661169689Skan else if (val2->lattice_val == UNDEFINED) 662169689Skan { 663169689Skan /* any M UNDEFINED = any 664169689Skan Nothing to do. VAL1 already contains the value we want. */ 665169689Skan ; 666169689Skan } 667169689Skan else if (val1->lattice_val == UNKNOWN_VAL 668169689Skan || val2->lattice_val == UNKNOWN_VAL) 669169689Skan { 670169689Skan /* UNKNOWN_VAL values are invalid if we are not doing STORE-CCP. */ 671169689Skan gcc_assert (do_store_ccp); 672169689Skan 673169689Skan /* any M UNKNOWN_VAL = UNKNOWN_VAL. */ 674169689Skan val1->lattice_val = UNKNOWN_VAL; 675169689Skan val1->value = NULL_TREE; 676169689Skan val1->mem_ref = NULL_TREE; 677169689Skan } 678169689Skan else if (val1->lattice_val == VARYING 679169689Skan || val2->lattice_val == VARYING) 680169689Skan { 681169689Skan /* any M VARYING = VARYING. */ 682169689Skan val1->lattice_val = VARYING; 683169689Skan val1->value = NULL_TREE; 684169689Skan val1->mem_ref = NULL_TREE; 685169689Skan } 686169689Skan else if (val1->lattice_val == CONSTANT 687169689Skan && val2->lattice_val == CONSTANT 688169689Skan && simple_cst_equal (val1->value, val2->value) == 1 689169689Skan && (!do_store_ccp 690169689Skan || (val1->mem_ref && val2->mem_ref 691169689Skan && operand_equal_p (val1->mem_ref, val2->mem_ref, 0)))) 692169689Skan { 693169689Skan /* Ci M Cj = Ci if (i == j) 694169689Skan Ci M Cj = VARYING if (i != j) 695169689Skan 696169689Skan If these two values come from memory stores, make sure that 697169689Skan they come from the same memory reference. */ 698169689Skan val1->lattice_val = CONSTANT; 699169689Skan val1->value = val1->value; 700169689Skan val1->mem_ref = val1->mem_ref; 701169689Skan } 702169689Skan else 703169689Skan { 704169689Skan /* Any other combination is VARYING. */ 705169689Skan val1->lattice_val = VARYING; 706169689Skan val1->value = NULL_TREE; 707169689Skan val1->mem_ref = NULL_TREE; 708169689Skan } 709169689Skan} 710169689Skan 711169689Skan 712169689Skan/* Loop through the PHI_NODE's parameters for BLOCK and compare their 713169689Skan lattice values to determine PHI_NODE's lattice value. The value of a 714169689Skan PHI node is determined calling ccp_lattice_meet with all the arguments 715169689Skan of the PHI node that are incoming via executable edges. */ 716169689Skan 717169689Skanstatic enum ssa_prop_result 718169689Skanccp_visit_phi_node (tree phi) 719169689Skan{ 720169689Skan int i; 721169689Skan prop_value_t *old_val, new_val; 722169689Skan 723169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 724169689Skan { 725169689Skan fprintf (dump_file, "\nVisiting PHI node: "); 726169689Skan print_generic_expr (dump_file, phi, dump_flags); 727169689Skan } 728169689Skan 729169689Skan old_val = get_value (PHI_RESULT (phi), false); 730169689Skan switch (old_val->lattice_val) 731169689Skan { 732169689Skan case VARYING: 733169689Skan return SSA_PROP_VARYING; 734169689Skan 735169689Skan case CONSTANT: 736169689Skan new_val = *old_val; 737169689Skan break; 738169689Skan 739169689Skan case UNKNOWN_VAL: 740169689Skan /* To avoid the default value of UNKNOWN_VAL overriding 741169689Skan that of its possible constant arguments, temporarily 742169689Skan set the PHI node's default lattice value to be 743169689Skan UNDEFINED. If the PHI node's old value was UNKNOWN_VAL and 744169689Skan the new value is UNDEFINED, then we prevent the invalid 745169689Skan transition by not calling set_lattice_value. */ 746169689Skan gcc_assert (do_store_ccp); 747169689Skan 748169689Skan /* FALLTHRU */ 749169689Skan 750169689Skan case UNDEFINED: 751169689Skan case UNINITIALIZED: 752169689Skan new_val.lattice_val = UNDEFINED; 753169689Skan new_val.value = NULL_TREE; 754169689Skan new_val.mem_ref = NULL_TREE; 755169689Skan break; 756169689Skan 757169689Skan default: 758169689Skan gcc_unreachable (); 759169689Skan } 760169689Skan 761169689Skan for (i = 0; i < PHI_NUM_ARGS (phi); i++) 762169689Skan { 763169689Skan /* Compute the meet operator over all the PHI arguments flowing 764169689Skan through executable edges. */ 765169689Skan edge e = PHI_ARG_EDGE (phi, i); 766169689Skan 767169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 768169689Skan { 769169689Skan fprintf (dump_file, 770169689Skan "\n Argument #%d (%d -> %d %sexecutable)\n", 771169689Skan i, e->src->index, e->dest->index, 772169689Skan (e->flags & EDGE_EXECUTABLE) ? "" : "not "); 773169689Skan } 774169689Skan 775169689Skan /* If the incoming edge is executable, Compute the meet operator for 776169689Skan the existing value of the PHI node and the current PHI argument. */ 777169689Skan if (e->flags & EDGE_EXECUTABLE) 778169689Skan { 779169689Skan tree arg = PHI_ARG_DEF (phi, i); 780169689Skan prop_value_t arg_val; 781169689Skan 782169689Skan if (is_gimple_min_invariant (arg)) 783169689Skan { 784169689Skan arg_val.lattice_val = CONSTANT; 785169689Skan arg_val.value = arg; 786169689Skan arg_val.mem_ref = NULL_TREE; 787169689Skan } 788169689Skan else 789169689Skan arg_val = *(get_value (arg, true)); 790169689Skan 791169689Skan ccp_lattice_meet (&new_val, &arg_val); 792169689Skan 793169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 794169689Skan { 795169689Skan fprintf (dump_file, "\t"); 796169689Skan print_generic_expr (dump_file, arg, dump_flags); 797169689Skan dump_lattice_value (dump_file, "\tValue: ", arg_val); 798169689Skan fprintf (dump_file, "\n"); 799169689Skan } 800169689Skan 801169689Skan if (new_val.lattice_val == VARYING) 802169689Skan break; 803169689Skan } 804169689Skan } 805169689Skan 806169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 807169689Skan { 808169689Skan dump_lattice_value (dump_file, "\n PHI node value: ", new_val); 809169689Skan fprintf (dump_file, "\n\n"); 810169689Skan } 811169689Skan 812169689Skan /* Check for an invalid change from UNKNOWN_VAL to UNDEFINED. */ 813169689Skan if (do_store_ccp 814169689Skan && old_val->lattice_val == UNKNOWN_VAL 815169689Skan && new_val.lattice_val == UNDEFINED) 816169689Skan return SSA_PROP_NOT_INTERESTING; 817169689Skan 818169689Skan /* Otherwise, make the transition to the new value. */ 819169689Skan if (set_lattice_value (PHI_RESULT (phi), new_val)) 820169689Skan { 821169689Skan if (new_val.lattice_val == VARYING) 822169689Skan return SSA_PROP_VARYING; 823169689Skan else 824169689Skan return SSA_PROP_INTERESTING; 825169689Skan } 826169689Skan else 827169689Skan return SSA_PROP_NOT_INTERESTING; 828169689Skan} 829169689Skan 830169689Skan 831169689Skan/* CCP specific front-end to the non-destructive constant folding 832169689Skan routines. 833169689Skan 834169689Skan Attempt to simplify the RHS of STMT knowing that one or more 835169689Skan operands are constants. 836169689Skan 837169689Skan If simplification is possible, return the simplified RHS, 838169689Skan otherwise return the original RHS. */ 839169689Skan 840169689Skanstatic tree 841169689Skanccp_fold (tree stmt) 842169689Skan{ 843169689Skan tree rhs = get_rhs (stmt); 844169689Skan enum tree_code code = TREE_CODE (rhs); 845169689Skan enum tree_code_class kind = TREE_CODE_CLASS (code); 846169689Skan tree retval = NULL_TREE; 847169689Skan 848169689Skan if (TREE_CODE (rhs) == SSA_NAME) 849169689Skan { 850169689Skan /* If the RHS is an SSA_NAME, return its known constant value, 851169689Skan if any. */ 852169689Skan return get_value (rhs, true)->value; 853169689Skan } 854169689Skan else if (do_store_ccp && stmt_makes_single_load (stmt)) 855169689Skan { 856169689Skan /* If the RHS is a memory load, see if the VUSEs associated with 857169689Skan it are a valid constant for that memory load. */ 858169689Skan prop_value_t *val = get_value_loaded_by (stmt, const_val); 859169689Skan if (val && val->mem_ref) 860169689Skan { 861169689Skan if (operand_equal_p (val->mem_ref, rhs, 0)) 862169689Skan return val->value; 863169689Skan 864169689Skan /* If RHS is extracting REALPART_EXPR or IMAGPART_EXPR of a 865169689Skan complex type with a known constant value, return it. */ 866169689Skan if ((TREE_CODE (rhs) == REALPART_EXPR 867169689Skan || TREE_CODE (rhs) == IMAGPART_EXPR) 868169689Skan && operand_equal_p (val->mem_ref, TREE_OPERAND (rhs, 0), 0)) 869169689Skan return fold_build1 (TREE_CODE (rhs), TREE_TYPE (rhs), val->value); 870169689Skan } 871169689Skan return NULL_TREE; 872169689Skan } 873169689Skan 874169689Skan /* Unary operators. Note that we know the single operand must 875169689Skan be a constant. So this should almost always return a 876169689Skan simplified RHS. */ 877169689Skan if (kind == tcc_unary) 878169689Skan { 879169689Skan /* Handle unary operators which can appear in GIMPLE form. */ 880169689Skan tree op0 = TREE_OPERAND (rhs, 0); 881169689Skan 882169689Skan /* Simplify the operand down to a constant. */ 883169689Skan if (TREE_CODE (op0) == SSA_NAME) 884169689Skan { 885169689Skan prop_value_t *val = get_value (op0, true); 886169689Skan if (val->lattice_val == CONSTANT) 887169689Skan op0 = get_value (op0, true)->value; 888169689Skan } 889169689Skan 890169689Skan if ((code == NOP_EXPR || code == CONVERT_EXPR) 891169689Skan && tree_ssa_useless_type_conversion_1 (TREE_TYPE (rhs), 892169689Skan TREE_TYPE (op0))) 893169689Skan return op0; 894169689Skan return fold_unary (code, TREE_TYPE (rhs), op0); 895169689Skan } 896169689Skan 897169689Skan /* Binary and comparison operators. We know one or both of the 898169689Skan operands are constants. */ 899169689Skan else if (kind == tcc_binary 900169689Skan || kind == tcc_comparison 901169689Skan || code == TRUTH_AND_EXPR 902169689Skan || code == TRUTH_OR_EXPR 903169689Skan || code == TRUTH_XOR_EXPR) 904169689Skan { 905169689Skan /* Handle binary and comparison operators that can appear in 906169689Skan GIMPLE form. */ 907169689Skan tree op0 = TREE_OPERAND (rhs, 0); 908169689Skan tree op1 = TREE_OPERAND (rhs, 1); 909169689Skan 910169689Skan /* Simplify the operands down to constants when appropriate. */ 911169689Skan if (TREE_CODE (op0) == SSA_NAME) 912169689Skan { 913169689Skan prop_value_t *val = get_value (op0, true); 914169689Skan if (val->lattice_val == CONSTANT) 915169689Skan op0 = val->value; 916169689Skan } 917169689Skan 918169689Skan if (TREE_CODE (op1) == SSA_NAME) 919169689Skan { 920169689Skan prop_value_t *val = get_value (op1, true); 921169689Skan if (val->lattice_val == CONSTANT) 922169689Skan op1 = val->value; 923169689Skan } 924169689Skan 925169689Skan return fold_binary (code, TREE_TYPE (rhs), op0, op1); 926169689Skan } 927169689Skan 928169689Skan /* We may be able to fold away calls to builtin functions if their 929169689Skan arguments are constants. */ 930169689Skan else if (code == CALL_EXPR 931169689Skan && TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR 932169689Skan && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0)) 933169689Skan == FUNCTION_DECL) 934169689Skan && DECL_BUILT_IN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0))) 935169689Skan { 936169689Skan if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_USE)) 937169689Skan { 938169689Skan tree *orig, var; 939169689Skan tree fndecl, arglist; 940169689Skan size_t i = 0; 941169689Skan ssa_op_iter iter; 942169689Skan use_operand_p var_p; 943169689Skan 944169689Skan /* Preserve the original values of every operand. */ 945169689Skan orig = XNEWVEC (tree, NUM_SSA_OPERANDS (stmt, SSA_OP_USE)); 946169689Skan FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE) 947169689Skan orig[i++] = var; 948169689Skan 949169689Skan /* Substitute operands with their values and try to fold. */ 950169689Skan replace_uses_in (stmt, NULL, const_val); 951169689Skan fndecl = get_callee_fndecl (rhs); 952169689Skan arglist = TREE_OPERAND (rhs, 1); 953169689Skan retval = fold_builtin (fndecl, arglist, false); 954169689Skan 955169689Skan /* Restore operands to their original form. */ 956169689Skan i = 0; 957169689Skan FOR_EACH_SSA_USE_OPERAND (var_p, stmt, iter, SSA_OP_USE) 958169689Skan SET_USE (var_p, orig[i++]); 959169689Skan free (orig); 960169689Skan } 961169689Skan } 962169689Skan else 963169689Skan return rhs; 964169689Skan 965169689Skan /* If we got a simplified form, see if we need to convert its type. */ 966169689Skan if (retval) 967169689Skan return fold_convert (TREE_TYPE (rhs), retval); 968169689Skan 969169689Skan /* No simplification was possible. */ 970169689Skan return rhs; 971169689Skan} 972169689Skan 973169689Skan 974169689Skan/* Return the tree representing the element referenced by T if T is an 975169689Skan ARRAY_REF or COMPONENT_REF into constant aggregates. Return 976169689Skan NULL_TREE otherwise. */ 977169689Skan 978169689Skanstatic tree 979169689Skanfold_const_aggregate_ref (tree t) 980169689Skan{ 981169689Skan prop_value_t *value; 982169689Skan tree base, ctor, idx, field; 983169689Skan unsigned HOST_WIDE_INT cnt; 984169689Skan tree cfield, cval; 985169689Skan 986169689Skan switch (TREE_CODE (t)) 987169689Skan { 988169689Skan case ARRAY_REF: 989169689Skan /* Get a CONSTRUCTOR. If BASE is a VAR_DECL, get its 990169689Skan DECL_INITIAL. If BASE is a nested reference into another 991169689Skan ARRAY_REF or COMPONENT_REF, make a recursive call to resolve 992169689Skan the inner reference. */ 993169689Skan base = TREE_OPERAND (t, 0); 994169689Skan switch (TREE_CODE (base)) 995169689Skan { 996169689Skan case VAR_DECL: 997169689Skan if (!TREE_READONLY (base) 998169689Skan || TREE_CODE (TREE_TYPE (base)) != ARRAY_TYPE 999169689Skan || !targetm.binds_local_p (base)) 1000169689Skan return NULL_TREE; 1001169689Skan 1002169689Skan ctor = DECL_INITIAL (base); 1003169689Skan break; 1004169689Skan 1005169689Skan case ARRAY_REF: 1006169689Skan case COMPONENT_REF: 1007169689Skan ctor = fold_const_aggregate_ref (base); 1008169689Skan break; 1009169689Skan 1010169689Skan default: 1011169689Skan return NULL_TREE; 1012169689Skan } 1013169689Skan 1014169689Skan if (ctor == NULL_TREE 1015169689Skan || (TREE_CODE (ctor) != CONSTRUCTOR 1016169689Skan && TREE_CODE (ctor) != STRING_CST) 1017169689Skan || !TREE_STATIC (ctor)) 1018169689Skan return NULL_TREE; 1019169689Skan 1020169689Skan /* Get the index. If we have an SSA_NAME, try to resolve it 1021169689Skan with the current lattice value for the SSA_NAME. */ 1022169689Skan idx = TREE_OPERAND (t, 1); 1023169689Skan switch (TREE_CODE (idx)) 1024169689Skan { 1025169689Skan case SSA_NAME: 1026169689Skan if ((value = get_value (idx, true)) 1027169689Skan && value->lattice_val == CONSTANT 1028169689Skan && TREE_CODE (value->value) == INTEGER_CST) 1029169689Skan idx = value->value; 1030169689Skan else 1031169689Skan return NULL_TREE; 1032169689Skan break; 1033169689Skan 1034169689Skan case INTEGER_CST: 1035169689Skan break; 1036169689Skan 1037169689Skan default: 1038169689Skan return NULL_TREE; 1039169689Skan } 1040169689Skan 1041169689Skan /* Fold read from constant string. */ 1042169689Skan if (TREE_CODE (ctor) == STRING_CST) 1043169689Skan { 1044169689Skan if ((TYPE_MODE (TREE_TYPE (t)) 1045169689Skan == TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor)))) 1046169689Skan && (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor)))) 1047169689Skan == MODE_INT) 1048169689Skan && GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor)))) == 1 1049169689Skan && compare_tree_int (idx, TREE_STRING_LENGTH (ctor)) < 0) 1050169689Skan return build_int_cst (TREE_TYPE (t), (TREE_STRING_POINTER (ctor) 1051169689Skan [TREE_INT_CST_LOW (idx)])); 1052169689Skan return NULL_TREE; 1053169689Skan } 1054169689Skan 1055169689Skan /* Whoo-hoo! I'll fold ya baby. Yeah! */ 1056169689Skan FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval) 1057169689Skan if (tree_int_cst_equal (cfield, idx)) 1058169689Skan return cval; 1059169689Skan break; 1060169689Skan 1061169689Skan case COMPONENT_REF: 1062169689Skan /* Get a CONSTRUCTOR. If BASE is a VAR_DECL, get its 1063169689Skan DECL_INITIAL. If BASE is a nested reference into another 1064169689Skan ARRAY_REF or COMPONENT_REF, make a recursive call to resolve 1065169689Skan the inner reference. */ 1066169689Skan base = TREE_OPERAND (t, 0); 1067169689Skan switch (TREE_CODE (base)) 1068169689Skan { 1069169689Skan case VAR_DECL: 1070169689Skan if (!TREE_READONLY (base) 1071169689Skan || TREE_CODE (TREE_TYPE (base)) != RECORD_TYPE 1072169689Skan || !targetm.binds_local_p (base)) 1073169689Skan return NULL_TREE; 1074169689Skan 1075169689Skan ctor = DECL_INITIAL (base); 1076169689Skan break; 1077169689Skan 1078169689Skan case ARRAY_REF: 1079169689Skan case COMPONENT_REF: 1080169689Skan ctor = fold_const_aggregate_ref (base); 1081169689Skan break; 1082169689Skan 1083169689Skan default: 1084169689Skan return NULL_TREE; 1085169689Skan } 1086169689Skan 1087169689Skan if (ctor == NULL_TREE 1088169689Skan || TREE_CODE (ctor) != CONSTRUCTOR 1089169689Skan || !TREE_STATIC (ctor)) 1090169689Skan return NULL_TREE; 1091169689Skan 1092169689Skan field = TREE_OPERAND (t, 1); 1093169689Skan 1094169689Skan FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval) 1095169689Skan if (cfield == field 1096169689Skan /* FIXME: Handle bit-fields. */ 1097169689Skan && ! DECL_BIT_FIELD (cfield)) 1098169689Skan return cval; 1099169689Skan break; 1100169689Skan 1101169689Skan case REALPART_EXPR: 1102169689Skan case IMAGPART_EXPR: 1103169689Skan { 1104169689Skan tree c = fold_const_aggregate_ref (TREE_OPERAND (t, 0)); 1105169689Skan if (c && TREE_CODE (c) == COMPLEX_CST) 1106169689Skan return fold_build1 (TREE_CODE (t), TREE_TYPE (t), c); 1107169689Skan break; 1108169689Skan } 1109169689Skan 1110169689Skan default: 1111169689Skan break; 1112169689Skan } 1113169689Skan 1114169689Skan return NULL_TREE; 1115169689Skan} 1116169689Skan 1117169689Skan/* Evaluate statement STMT. */ 1118169689Skan 1119169689Skanstatic prop_value_t 1120169689Skanevaluate_stmt (tree stmt) 1121169689Skan{ 1122169689Skan prop_value_t val; 1123169689Skan tree simplified = NULL_TREE; 1124169689Skan ccp_lattice_t likelyvalue = likely_value (stmt); 1125169689Skan bool is_constant; 1126169689Skan 1127169689Skan val.mem_ref = NULL_TREE; 1128169689Skan 1129169689Skan fold_defer_overflow_warnings (); 1130169689Skan 1131169689Skan /* If the statement is likely to have a CONSTANT result, then try 1132169689Skan to fold the statement to determine the constant value. */ 1133169689Skan if (likelyvalue == CONSTANT) 1134169689Skan simplified = ccp_fold (stmt); 1135169689Skan /* If the statement is likely to have a VARYING result, then do not 1136169689Skan bother folding the statement. */ 1137169689Skan if (likelyvalue == VARYING) 1138169689Skan simplified = get_rhs (stmt); 1139169689Skan /* If the statement is an ARRAY_REF or COMPONENT_REF into constant 1140169689Skan aggregates, extract the referenced constant. Otherwise the 1141169689Skan statement is likely to have an UNDEFINED value, and there will be 1142169689Skan nothing to do. Note that fold_const_aggregate_ref returns 1143169689Skan NULL_TREE if the first case does not match. */ 1144169689Skan else if (!simplified) 1145169689Skan simplified = fold_const_aggregate_ref (get_rhs (stmt)); 1146169689Skan 1147169689Skan is_constant = simplified && is_gimple_min_invariant (simplified); 1148169689Skan 1149169689Skan fold_undefer_overflow_warnings (is_constant, stmt, 0); 1150169689Skan 1151169689Skan if (is_constant) 1152169689Skan { 1153169689Skan /* The statement produced a constant value. */ 1154169689Skan val.lattice_val = CONSTANT; 1155169689Skan val.value = simplified; 1156169689Skan } 1157169689Skan else 1158169689Skan { 1159169689Skan /* The statement produced a nonconstant value. If the statement 1160169689Skan had UNDEFINED operands, then the result of the statement 1161169689Skan should be UNDEFINED. Otherwise, the statement is VARYING. */ 1162169689Skan if (likelyvalue == UNDEFINED || likelyvalue == UNKNOWN_VAL) 1163169689Skan val.lattice_val = likelyvalue; 1164169689Skan else 1165169689Skan val.lattice_val = VARYING; 1166169689Skan 1167169689Skan val.value = NULL_TREE; 1168169689Skan } 1169169689Skan 1170169689Skan return val; 1171169689Skan} 1172169689Skan 1173169689Skan 1174169689Skan/* Visit the assignment statement STMT. Set the value of its LHS to the 1175169689Skan value computed by the RHS and store LHS in *OUTPUT_P. If STMT 1176169689Skan creates virtual definitions, set the value of each new name to that 1177169689Skan of the RHS (if we can derive a constant out of the RHS). */ 1178169689Skan 1179169689Skanstatic enum ssa_prop_result 1180169689Skanvisit_assignment (tree stmt, tree *output_p) 1181169689Skan{ 1182169689Skan prop_value_t val; 1183169689Skan tree lhs, rhs; 1184169689Skan enum ssa_prop_result retval; 1185169689Skan 1186169689Skan lhs = TREE_OPERAND (stmt, 0); 1187169689Skan rhs = TREE_OPERAND (stmt, 1); 1188169689Skan 1189169689Skan if (TREE_CODE (rhs) == SSA_NAME) 1190169689Skan { 1191169689Skan /* For a simple copy operation, we copy the lattice values. */ 1192169689Skan prop_value_t *nval = get_value (rhs, true); 1193169689Skan val = *nval; 1194169689Skan } 1195169689Skan else if (do_store_ccp && stmt_makes_single_load (stmt)) 1196169689Skan { 1197169689Skan /* Same as above, but the RHS is not a gimple register and yet 1198169689Skan has a known VUSE. If STMT is loading from the same memory 1199169689Skan location that created the SSA_NAMEs for the virtual operands, 1200169689Skan we can propagate the value on the RHS. */ 1201169689Skan prop_value_t *nval = get_value_loaded_by (stmt, const_val); 1202169689Skan 1203169689Skan if (nval && nval->mem_ref 1204169689Skan && operand_equal_p (nval->mem_ref, rhs, 0)) 1205169689Skan val = *nval; 1206169689Skan else 1207169689Skan val = evaluate_stmt (stmt); 1208169689Skan } 1209169689Skan else 1210169689Skan /* Evaluate the statement. */ 1211169689Skan val = evaluate_stmt (stmt); 1212169689Skan 1213169689Skan /* If the original LHS was a VIEW_CONVERT_EXPR, modify the constant 1214169689Skan value to be a VIEW_CONVERT_EXPR of the old constant value. 1215169689Skan 1216169689Skan ??? Also, if this was a definition of a bitfield, we need to widen 1217169689Skan the constant value into the type of the destination variable. This 1218169689Skan should not be necessary if GCC represented bitfields properly. */ 1219169689Skan { 1220169689Skan tree orig_lhs = TREE_OPERAND (stmt, 0); 1221169689Skan 1222169689Skan if (TREE_CODE (orig_lhs) == VIEW_CONVERT_EXPR 1223169689Skan && val.lattice_val == CONSTANT) 1224169689Skan { 1225169689Skan tree w = fold_unary (VIEW_CONVERT_EXPR, 1226169689Skan TREE_TYPE (TREE_OPERAND (orig_lhs, 0)), 1227169689Skan val.value); 1228169689Skan 1229169689Skan orig_lhs = TREE_OPERAND (orig_lhs, 0); 1230169689Skan if (w && is_gimple_min_invariant (w)) 1231169689Skan val.value = w; 1232169689Skan else 1233169689Skan { 1234169689Skan val.lattice_val = VARYING; 1235169689Skan val.value = NULL; 1236169689Skan } 1237169689Skan } 1238169689Skan 1239169689Skan if (val.lattice_val == CONSTANT 1240169689Skan && TREE_CODE (orig_lhs) == COMPONENT_REF 1241169689Skan && DECL_BIT_FIELD (TREE_OPERAND (orig_lhs, 1))) 1242169689Skan { 1243169689Skan tree w = widen_bitfield (val.value, TREE_OPERAND (orig_lhs, 1), 1244169689Skan orig_lhs); 1245169689Skan 1246169689Skan if (w && is_gimple_min_invariant (w)) 1247169689Skan val.value = w; 1248169689Skan else 1249169689Skan { 1250169689Skan val.lattice_val = VARYING; 1251169689Skan val.value = NULL_TREE; 1252169689Skan val.mem_ref = NULL_TREE; 1253169689Skan } 1254169689Skan } 1255169689Skan } 1256169689Skan 1257169689Skan retval = SSA_PROP_NOT_INTERESTING; 1258169689Skan 1259169689Skan /* Set the lattice value of the statement's output. */ 1260169689Skan if (TREE_CODE (lhs) == SSA_NAME) 1261169689Skan { 1262169689Skan /* If STMT is an assignment to an SSA_NAME, we only have one 1263169689Skan value to set. */ 1264169689Skan if (set_lattice_value (lhs, val)) 1265169689Skan { 1266169689Skan *output_p = lhs; 1267169689Skan if (val.lattice_val == VARYING) 1268169689Skan retval = SSA_PROP_VARYING; 1269169689Skan else 1270169689Skan retval = SSA_PROP_INTERESTING; 1271169689Skan } 1272169689Skan } 1273169689Skan else if (do_store_ccp && stmt_makes_single_store (stmt)) 1274169689Skan { 1275169689Skan /* Otherwise, set the names in V_MAY_DEF/V_MUST_DEF operands 1276169689Skan to the new constant value and mark the LHS as the memory 1277169689Skan reference associated with VAL. */ 1278169689Skan ssa_op_iter i; 1279169689Skan tree vdef; 1280169689Skan bool changed; 1281169689Skan 1282169689Skan /* Stores cannot take on an UNDEFINED value. */ 1283169689Skan if (val.lattice_val == UNDEFINED) 1284169689Skan val.lattice_val = UNKNOWN_VAL; 1285169689Skan 1286169689Skan /* Mark VAL as stored in the LHS of this assignment. */ 1287169689Skan val.mem_ref = lhs; 1288169689Skan 1289169689Skan /* Set the value of every VDEF to VAL. */ 1290169689Skan changed = false; 1291169689Skan FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, i, SSA_OP_VIRTUAL_DEFS) 1292169689Skan changed |= set_lattice_value (vdef, val); 1293169689Skan 1294169689Skan /* Note that for propagation purposes, we are only interested in 1295169689Skan visiting statements that load the exact same memory reference 1296169689Skan stored here. Those statements will have the exact same list 1297169689Skan of virtual uses, so it is enough to set the output of this 1298169689Skan statement to be its first virtual definition. */ 1299169689Skan *output_p = first_vdef (stmt); 1300169689Skan if (changed) 1301169689Skan { 1302169689Skan if (val.lattice_val == VARYING) 1303169689Skan retval = SSA_PROP_VARYING; 1304169689Skan else 1305169689Skan retval = SSA_PROP_INTERESTING; 1306169689Skan } 1307169689Skan } 1308169689Skan 1309169689Skan return retval; 1310169689Skan} 1311169689Skan 1312169689Skan 1313169689Skan/* Visit the conditional statement STMT. Return SSA_PROP_INTERESTING 1314169689Skan if it can determine which edge will be taken. Otherwise, return 1315169689Skan SSA_PROP_VARYING. */ 1316169689Skan 1317169689Skanstatic enum ssa_prop_result 1318169689Skanvisit_cond_stmt (tree stmt, edge *taken_edge_p) 1319169689Skan{ 1320169689Skan prop_value_t val; 1321169689Skan basic_block block; 1322169689Skan 1323169689Skan block = bb_for_stmt (stmt); 1324169689Skan val = evaluate_stmt (stmt); 1325169689Skan 1326169689Skan /* Find which edge out of the conditional block will be taken and add it 1327169689Skan to the worklist. If no single edge can be determined statically, 1328169689Skan return SSA_PROP_VARYING to feed all the outgoing edges to the 1329169689Skan propagation engine. */ 1330169689Skan *taken_edge_p = val.value ? find_taken_edge (block, val.value) : 0; 1331169689Skan if (*taken_edge_p) 1332169689Skan return SSA_PROP_INTERESTING; 1333169689Skan else 1334169689Skan return SSA_PROP_VARYING; 1335169689Skan} 1336169689Skan 1337169689Skan 1338169689Skan/* Evaluate statement STMT. If the statement produces an output value and 1339169689Skan its evaluation changes the lattice value of its output, return 1340169689Skan SSA_PROP_INTERESTING and set *OUTPUT_P to the SSA_NAME holding the 1341169689Skan output value. 1342169689Skan 1343169689Skan If STMT is a conditional branch and we can determine its truth 1344169689Skan value, set *TAKEN_EDGE_P accordingly. If STMT produces a varying 1345169689Skan value, return SSA_PROP_VARYING. */ 1346169689Skan 1347169689Skanstatic enum ssa_prop_result 1348169689Skanccp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p) 1349169689Skan{ 1350169689Skan tree def; 1351169689Skan ssa_op_iter iter; 1352169689Skan 1353169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1354169689Skan { 1355169689Skan fprintf (dump_file, "\nVisiting statement:\n"); 1356169689Skan print_generic_stmt (dump_file, stmt, dump_flags); 1357169689Skan fprintf (dump_file, "\n"); 1358169689Skan } 1359169689Skan 1360169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR) 1361169689Skan { 1362169689Skan /* If the statement is an assignment that produces a single 1363169689Skan output value, evaluate its RHS to see if the lattice value of 1364169689Skan its output has changed. */ 1365169689Skan return visit_assignment (stmt, output_p); 1366169689Skan } 1367169689Skan else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR) 1368169689Skan { 1369169689Skan /* If STMT is a conditional branch, see if we can determine 1370169689Skan which branch will be taken. */ 1371169689Skan return visit_cond_stmt (stmt, taken_edge_p); 1372169689Skan } 1373169689Skan 1374169689Skan /* Any other kind of statement is not interesting for constant 1375169689Skan propagation and, therefore, not worth simulating. */ 1376169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1377169689Skan fprintf (dump_file, "No interesting values produced. Marked VARYING.\n"); 1378169689Skan 1379169689Skan /* Definitions made by statements other than assignments to 1380169689Skan SSA_NAMEs represent unknown modifications to their outputs. 1381169689Skan Mark them VARYING. */ 1382169689Skan FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) 1383169689Skan { 1384169689Skan prop_value_t v = { VARYING, NULL_TREE, NULL_TREE }; 1385169689Skan set_lattice_value (def, v); 1386169689Skan } 1387169689Skan 1388169689Skan return SSA_PROP_VARYING; 1389169689Skan} 1390169689Skan 1391169689Skan 1392169689Skan/* Main entry point for SSA Conditional Constant Propagation. */ 1393169689Skan 1394169689Skanstatic void 1395169689Skanexecute_ssa_ccp (bool store_ccp) 1396169689Skan{ 1397169689Skan do_store_ccp = store_ccp; 1398169689Skan ccp_initialize (); 1399169689Skan ssa_propagate (ccp_visit_stmt, ccp_visit_phi_node); 1400169689Skan ccp_finalize (); 1401169689Skan} 1402169689Skan 1403169689Skan 1404169689Skanstatic unsigned int 1405169689Skando_ssa_ccp (void) 1406169689Skan{ 1407169689Skan execute_ssa_ccp (false); 1408169689Skan return 0; 1409169689Skan} 1410169689Skan 1411169689Skan 1412169689Skanstatic bool 1413169689Skangate_ccp (void) 1414169689Skan{ 1415169689Skan return flag_tree_ccp != 0; 1416169689Skan} 1417169689Skan 1418169689Skan 1419169689Skanstruct tree_opt_pass pass_ccp = 1420169689Skan{ 1421169689Skan "ccp", /* name */ 1422169689Skan gate_ccp, /* gate */ 1423169689Skan do_ssa_ccp, /* execute */ 1424169689Skan NULL, /* sub */ 1425169689Skan NULL, /* next */ 1426169689Skan 0, /* static_pass_number */ 1427169689Skan TV_TREE_CCP, /* tv_id */ 1428169689Skan PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 1429169689Skan 0, /* properties_provided */ 1430169689Skan PROP_smt_usage, /* properties_destroyed */ 1431169689Skan 0, /* todo_flags_start */ 1432169689Skan TODO_cleanup_cfg | TODO_dump_func | TODO_update_ssa 1433169689Skan | TODO_ggc_collect | TODO_verify_ssa 1434169689Skan | TODO_verify_stmts | TODO_update_smt_usage, /* todo_flags_finish */ 1435169689Skan 0 /* letter */ 1436169689Skan}; 1437169689Skan 1438169689Skan 1439169689Skanstatic unsigned int 1440169689Skando_ssa_store_ccp (void) 1441169689Skan{ 1442169689Skan /* If STORE-CCP is not enabled, we just run regular CCP. */ 1443169689Skan execute_ssa_ccp (flag_tree_store_ccp != 0); 1444169689Skan return 0; 1445169689Skan} 1446169689Skan 1447169689Skanstatic bool 1448169689Skangate_store_ccp (void) 1449169689Skan{ 1450169689Skan /* STORE-CCP is enabled only with -ftree-store-ccp, but when 1451169689Skan -fno-tree-store-ccp is specified, we should run regular CCP. 1452169689Skan That's why the pass is enabled with either flag. */ 1453169689Skan return flag_tree_store_ccp != 0 || flag_tree_ccp != 0; 1454169689Skan} 1455169689Skan 1456169689Skan 1457169689Skanstruct tree_opt_pass pass_store_ccp = 1458169689Skan{ 1459169689Skan "store_ccp", /* name */ 1460169689Skan gate_store_ccp, /* gate */ 1461169689Skan do_ssa_store_ccp, /* execute */ 1462169689Skan NULL, /* sub */ 1463169689Skan NULL, /* next */ 1464169689Skan 0, /* static_pass_number */ 1465169689Skan TV_TREE_STORE_CCP, /* tv_id */ 1466169689Skan PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 1467169689Skan 0, /* properties_provided */ 1468169689Skan PROP_smt_usage, /* properties_destroyed */ 1469169689Skan 0, /* todo_flags_start */ 1470169689Skan TODO_dump_func | TODO_update_ssa 1471169689Skan | TODO_ggc_collect | TODO_verify_ssa 1472169689Skan | TODO_cleanup_cfg 1473169689Skan | TODO_verify_stmts | TODO_update_smt_usage, /* todo_flags_finish */ 1474169689Skan 0 /* letter */ 1475169689Skan}; 1476169689Skan 1477169689Skan/* Given a constant value VAL for bitfield FIELD, and a destination 1478169689Skan variable VAR, return VAL appropriately widened to fit into VAR. If 1479169689Skan FIELD is wider than HOST_WIDE_INT, NULL is returned. */ 1480169689Skan 1481169689Skantree 1482169689Skanwiden_bitfield (tree val, tree field, tree var) 1483169689Skan{ 1484169689Skan unsigned HOST_WIDE_INT var_size, field_size; 1485169689Skan tree wide_val; 1486169689Skan unsigned HOST_WIDE_INT mask; 1487169689Skan unsigned int i; 1488169689Skan 1489169689Skan /* We can only do this if the size of the type and field and VAL are 1490169689Skan all constants representable in HOST_WIDE_INT. */ 1491169689Skan if (!host_integerp (TYPE_SIZE (TREE_TYPE (var)), 1) 1492169689Skan || !host_integerp (DECL_SIZE (field), 1) 1493169689Skan || !host_integerp (val, 0)) 1494169689Skan return NULL_TREE; 1495169689Skan 1496169689Skan var_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (var)), 1); 1497169689Skan field_size = tree_low_cst (DECL_SIZE (field), 1); 1498169689Skan 1499169689Skan /* Give up if either the bitfield or the variable are too wide. */ 1500169689Skan if (field_size > HOST_BITS_PER_WIDE_INT || var_size > HOST_BITS_PER_WIDE_INT) 1501169689Skan return NULL_TREE; 1502169689Skan 1503169689Skan gcc_assert (var_size >= field_size); 1504169689Skan 1505169689Skan /* If the sign bit of the value is not set or the field's type is unsigned, 1506169689Skan just mask off the high order bits of the value. */ 1507169689Skan if (DECL_UNSIGNED (field) 1508169689Skan || !(tree_low_cst (val, 0) & (((HOST_WIDE_INT)1) << (field_size - 1)))) 1509169689Skan { 1510169689Skan /* Zero extension. Build a mask with the lower 'field_size' bits 1511169689Skan set and a BIT_AND_EXPR node to clear the high order bits of 1512169689Skan the value. */ 1513169689Skan for (i = 0, mask = 0; i < field_size; i++) 1514169689Skan mask |= ((HOST_WIDE_INT) 1) << i; 1515169689Skan 1516169689Skan wide_val = fold_build2 (BIT_AND_EXPR, TREE_TYPE (var), val, 1517169689Skan build_int_cst (TREE_TYPE (var), mask)); 1518169689Skan } 1519169689Skan else 1520169689Skan { 1521169689Skan /* Sign extension. Create a mask with the upper 'field_size' 1522169689Skan bits set and a BIT_IOR_EXPR to set the high order bits of the 1523169689Skan value. */ 1524169689Skan for (i = 0, mask = 0; i < (var_size - field_size); i++) 1525169689Skan mask |= ((HOST_WIDE_INT) 1) << (var_size - i - 1); 1526169689Skan 1527169689Skan wide_val = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (var), val, 1528169689Skan build_int_cst (TREE_TYPE (var), mask)); 1529169689Skan } 1530169689Skan 1531169689Skan return wide_val; 1532169689Skan} 1533169689Skan 1534169689Skan 1535169689Skan/* A subroutine of fold_stmt_r. Attempts to fold *(A+O) to A[X]. 1536169689Skan BASE is an array type. OFFSET is a byte displacement. ORIG_TYPE 1537169689Skan is the desired result type. */ 1538169689Skan 1539169689Skanstatic tree 1540169689Skanmaybe_fold_offset_to_array_ref (tree base, tree offset, tree orig_type) 1541169689Skan{ 1542169689Skan tree min_idx, idx, elt_offset = integer_zero_node; 1543169689Skan tree array_type, elt_type, elt_size; 1544169689Skan 1545169689Skan /* If BASE is an ARRAY_REF, we can pick up another offset (this time 1546169689Skan measured in units of the size of elements type) from that ARRAY_REF). 1547169689Skan We can't do anything if either is variable. 1548169689Skan 1549169689Skan The case we handle here is *(&A[N]+O). */ 1550169689Skan if (TREE_CODE (base) == ARRAY_REF) 1551169689Skan { 1552169689Skan tree low_bound = array_ref_low_bound (base); 1553169689Skan 1554169689Skan elt_offset = TREE_OPERAND (base, 1); 1555169689Skan if (TREE_CODE (low_bound) != INTEGER_CST 1556169689Skan || TREE_CODE (elt_offset) != INTEGER_CST) 1557169689Skan return NULL_TREE; 1558169689Skan 1559169689Skan elt_offset = int_const_binop (MINUS_EXPR, elt_offset, low_bound, 0); 1560169689Skan base = TREE_OPERAND (base, 0); 1561169689Skan } 1562169689Skan 1563169689Skan /* Ignore stupid user tricks of indexing non-array variables. */ 1564169689Skan array_type = TREE_TYPE (base); 1565169689Skan if (TREE_CODE (array_type) != ARRAY_TYPE) 1566169689Skan return NULL_TREE; 1567169689Skan elt_type = TREE_TYPE (array_type); 1568169689Skan if (!lang_hooks.types_compatible_p (orig_type, elt_type)) 1569169689Skan return NULL_TREE; 1570169689Skan 1571169689Skan /* If OFFSET and ELT_OFFSET are zero, we don't care about the size of the 1572169689Skan element type (so we can use the alignment if it's not constant). 1573169689Skan Otherwise, compute the offset as an index by using a division. If the 1574169689Skan division isn't exact, then don't do anything. */ 1575169689Skan elt_size = TYPE_SIZE_UNIT (elt_type); 1576169689Skan if (integer_zerop (offset)) 1577169689Skan { 1578169689Skan if (TREE_CODE (elt_size) != INTEGER_CST) 1579169689Skan elt_size = size_int (TYPE_ALIGN (elt_type)); 1580169689Skan 1581169689Skan idx = integer_zero_node; 1582169689Skan } 1583169689Skan else 1584169689Skan { 1585169689Skan unsigned HOST_WIDE_INT lquo, lrem; 1586169689Skan HOST_WIDE_INT hquo, hrem; 1587169689Skan 1588169689Skan if (TREE_CODE (elt_size) != INTEGER_CST 1589169689Skan || div_and_round_double (TRUNC_DIV_EXPR, 1, 1590169689Skan TREE_INT_CST_LOW (offset), 1591169689Skan TREE_INT_CST_HIGH (offset), 1592169689Skan TREE_INT_CST_LOW (elt_size), 1593169689Skan TREE_INT_CST_HIGH (elt_size), 1594169689Skan &lquo, &hquo, &lrem, &hrem) 1595169689Skan || lrem || hrem) 1596169689Skan return NULL_TREE; 1597169689Skan 1598169689Skan idx = build_int_cst_wide (NULL_TREE, lquo, hquo); 1599169689Skan } 1600169689Skan 1601169689Skan /* Assume the low bound is zero. If there is a domain type, get the 1602169689Skan low bound, if any, convert the index into that type, and add the 1603169689Skan low bound. */ 1604169689Skan min_idx = integer_zero_node; 1605169689Skan if (TYPE_DOMAIN (array_type)) 1606169689Skan { 1607169689Skan if (TYPE_MIN_VALUE (TYPE_DOMAIN (array_type))) 1608169689Skan min_idx = TYPE_MIN_VALUE (TYPE_DOMAIN (array_type)); 1609169689Skan else 1610169689Skan min_idx = fold_convert (TYPE_DOMAIN (array_type), min_idx); 1611169689Skan 1612169689Skan if (TREE_CODE (min_idx) != INTEGER_CST) 1613169689Skan return NULL_TREE; 1614169689Skan 1615169689Skan idx = fold_convert (TYPE_DOMAIN (array_type), idx); 1616169689Skan elt_offset = fold_convert (TYPE_DOMAIN (array_type), elt_offset); 1617169689Skan } 1618169689Skan 1619169689Skan if (!integer_zerop (min_idx)) 1620169689Skan idx = int_const_binop (PLUS_EXPR, idx, min_idx, 0); 1621169689Skan if (!integer_zerop (elt_offset)) 1622169689Skan idx = int_const_binop (PLUS_EXPR, idx, elt_offset, 0); 1623169689Skan 1624237406Spfg return build4 (ARRAY_REF, orig_type, base, idx, NULL_TREE, NULL_TREE); 1625169689Skan} 1626169689Skan 1627169689Skan 1628169689Skan/* A subroutine of fold_stmt_r. Attempts to fold *(S+O) to S.X. 1629169689Skan BASE is a record type. OFFSET is a byte displacement. ORIG_TYPE 1630169689Skan is the desired result type. */ 1631169689Skan/* ??? This doesn't handle class inheritance. */ 1632169689Skan 1633169689Skanstatic tree 1634169689Skanmaybe_fold_offset_to_component_ref (tree record_type, tree base, tree offset, 1635169689Skan tree orig_type, bool base_is_ptr) 1636169689Skan{ 1637169689Skan tree f, t, field_type, tail_array_field, field_offset; 1638169689Skan 1639169689Skan if (TREE_CODE (record_type) != RECORD_TYPE 1640169689Skan && TREE_CODE (record_type) != UNION_TYPE 1641169689Skan && TREE_CODE (record_type) != QUAL_UNION_TYPE) 1642169689Skan return NULL_TREE; 1643169689Skan 1644169689Skan /* Short-circuit silly cases. */ 1645169689Skan if (lang_hooks.types_compatible_p (record_type, orig_type)) 1646169689Skan return NULL_TREE; 1647169689Skan 1648169689Skan tail_array_field = NULL_TREE; 1649169689Skan for (f = TYPE_FIELDS (record_type); f ; f = TREE_CHAIN (f)) 1650169689Skan { 1651169689Skan int cmp; 1652169689Skan 1653169689Skan if (TREE_CODE (f) != FIELD_DECL) 1654169689Skan continue; 1655169689Skan if (DECL_BIT_FIELD (f)) 1656169689Skan continue; 1657169689Skan 1658169689Skan field_offset = byte_position (f); 1659169689Skan if (TREE_CODE (field_offset) != INTEGER_CST) 1660169689Skan continue; 1661169689Skan 1662169689Skan /* ??? Java creates "interesting" fields for representing base classes. 1663169689Skan They have no name, and have no context. With no context, we get into 1664169689Skan trouble with nonoverlapping_component_refs_p. Skip them. */ 1665169689Skan if (!DECL_FIELD_CONTEXT (f)) 1666169689Skan continue; 1667169689Skan 1668169689Skan /* The previous array field isn't at the end. */ 1669169689Skan tail_array_field = NULL_TREE; 1670169689Skan 1671169689Skan /* Check to see if this offset overlaps with the field. */ 1672169689Skan cmp = tree_int_cst_compare (field_offset, offset); 1673169689Skan if (cmp > 0) 1674169689Skan continue; 1675169689Skan 1676169689Skan field_type = TREE_TYPE (f); 1677169689Skan 1678169689Skan /* Here we exactly match the offset being checked. If the types match, 1679169689Skan then we can return that field. */ 1680169689Skan if (cmp == 0 1681169689Skan && lang_hooks.types_compatible_p (orig_type, field_type)) 1682169689Skan { 1683169689Skan if (base_is_ptr) 1684169689Skan base = build1 (INDIRECT_REF, record_type, base); 1685169689Skan t = build3 (COMPONENT_REF, field_type, base, f, NULL_TREE); 1686169689Skan return t; 1687169689Skan } 1688169689Skan 1689169689Skan /* Don't care about offsets into the middle of scalars. */ 1690169689Skan if (!AGGREGATE_TYPE_P (field_type)) 1691169689Skan continue; 1692169689Skan 1693169689Skan /* Check for array at the end of the struct. This is often 1694169689Skan used as for flexible array members. We should be able to 1695169689Skan turn this into an array access anyway. */ 1696169689Skan if (TREE_CODE (field_type) == ARRAY_TYPE) 1697169689Skan tail_array_field = f; 1698169689Skan 1699169689Skan /* Check the end of the field against the offset. */ 1700169689Skan if (!DECL_SIZE_UNIT (f) 1701169689Skan || TREE_CODE (DECL_SIZE_UNIT (f)) != INTEGER_CST) 1702169689Skan continue; 1703169689Skan t = int_const_binop (MINUS_EXPR, offset, field_offset, 1); 1704169689Skan if (!tree_int_cst_lt (t, DECL_SIZE_UNIT (f))) 1705169689Skan continue; 1706169689Skan 1707169689Skan /* If we matched, then set offset to the displacement into 1708169689Skan this field. */ 1709169689Skan offset = t; 1710169689Skan goto found; 1711169689Skan } 1712169689Skan 1713169689Skan if (!tail_array_field) 1714169689Skan return NULL_TREE; 1715169689Skan 1716169689Skan f = tail_array_field; 1717169689Skan field_type = TREE_TYPE (f); 1718169689Skan offset = int_const_binop (MINUS_EXPR, offset, byte_position (f), 1); 1719169689Skan 1720169689Skan found: 1721169689Skan /* If we get here, we've got an aggregate field, and a possibly 1722169689Skan nonzero offset into them. Recurse and hope for a valid match. */ 1723169689Skan if (base_is_ptr) 1724169689Skan base = build1 (INDIRECT_REF, record_type, base); 1725169689Skan base = build3 (COMPONENT_REF, field_type, base, f, NULL_TREE); 1726169689Skan 1727169689Skan t = maybe_fold_offset_to_array_ref (base, offset, orig_type); 1728169689Skan if (t) 1729169689Skan return t; 1730169689Skan return maybe_fold_offset_to_component_ref (field_type, base, offset, 1731169689Skan orig_type, false); 1732169689Skan} 1733169689Skan 1734169689Skan 1735169689Skan/* A subroutine of fold_stmt_r. Attempt to simplify *(BASE+OFFSET). 1736169689Skan Return the simplified expression, or NULL if nothing could be done. */ 1737169689Skan 1738169689Skanstatic tree 1739169689Skanmaybe_fold_stmt_indirect (tree expr, tree base, tree offset) 1740169689Skan{ 1741169689Skan tree t; 1742169689Skan 1743169689Skan /* We may well have constructed a double-nested PLUS_EXPR via multiple 1744169689Skan substitutions. Fold that down to one. Remove NON_LVALUE_EXPRs that 1745169689Skan are sometimes added. */ 1746169689Skan base = fold (base); 1747169689Skan STRIP_TYPE_NOPS (base); 1748169689Skan TREE_OPERAND (expr, 0) = base; 1749169689Skan 1750169689Skan /* One possibility is that the address reduces to a string constant. */ 1751169689Skan t = fold_read_from_constant_string (expr); 1752169689Skan if (t) 1753169689Skan return t; 1754169689Skan 1755169689Skan /* Add in any offset from a PLUS_EXPR. */ 1756169689Skan if (TREE_CODE (base) == PLUS_EXPR) 1757169689Skan { 1758169689Skan tree offset2; 1759169689Skan 1760169689Skan offset2 = TREE_OPERAND (base, 1); 1761169689Skan if (TREE_CODE (offset2) != INTEGER_CST) 1762169689Skan return NULL_TREE; 1763169689Skan base = TREE_OPERAND (base, 0); 1764169689Skan 1765169689Skan offset = int_const_binop (PLUS_EXPR, offset, offset2, 1); 1766169689Skan } 1767169689Skan 1768169689Skan if (TREE_CODE (base) == ADDR_EXPR) 1769169689Skan { 1770169689Skan /* Strip the ADDR_EXPR. */ 1771169689Skan base = TREE_OPERAND (base, 0); 1772169689Skan 1773169689Skan /* Fold away CONST_DECL to its value, if the type is scalar. */ 1774169689Skan if (TREE_CODE (base) == CONST_DECL 1775169689Skan && ccp_decl_initial_min_invariant (DECL_INITIAL (base))) 1776169689Skan return DECL_INITIAL (base); 1777169689Skan 1778169689Skan /* Try folding *(&B+O) to B[X]. */ 1779169689Skan t = maybe_fold_offset_to_array_ref (base, offset, TREE_TYPE (expr)); 1780169689Skan if (t) 1781169689Skan return t; 1782169689Skan 1783169689Skan /* Try folding *(&B+O) to B.X. */ 1784169689Skan t = maybe_fold_offset_to_component_ref (TREE_TYPE (base), base, offset, 1785169689Skan TREE_TYPE (expr), false); 1786169689Skan if (t) 1787169689Skan return t; 1788169689Skan 1789169689Skan /* Fold *&B to B. We can only do this if EXPR is the same type 1790169689Skan as BASE. We can't do this if EXPR is the element type of an array 1791169689Skan and BASE is the array. */ 1792169689Skan if (integer_zerop (offset) 1793169689Skan && lang_hooks.types_compatible_p (TREE_TYPE (base), 1794169689Skan TREE_TYPE (expr))) 1795169689Skan return base; 1796169689Skan } 1797169689Skan else 1798169689Skan { 1799169689Skan /* We can get here for out-of-range string constant accesses, 1800169689Skan such as "_"[3]. Bail out of the entire substitution search 1801169689Skan and arrange for the entire statement to be replaced by a 1802169689Skan call to __builtin_trap. In all likelihood this will all be 1803169689Skan constant-folded away, but in the meantime we can't leave with 1804169689Skan something that get_expr_operands can't understand. */ 1805169689Skan 1806169689Skan t = base; 1807169689Skan STRIP_NOPS (t); 1808169689Skan if (TREE_CODE (t) == ADDR_EXPR 1809169689Skan && TREE_CODE (TREE_OPERAND (t, 0)) == STRING_CST) 1810169689Skan { 1811169689Skan /* FIXME: Except that this causes problems elsewhere with dead 1812169689Skan code not being deleted, and we die in the rtl expanders 1813169689Skan because we failed to remove some ssa_name. In the meantime, 1814169689Skan just return zero. */ 1815169689Skan /* FIXME2: This condition should be signaled by 1816169689Skan fold_read_from_constant_string directly, rather than 1817169689Skan re-checking for it here. */ 1818169689Skan return integer_zero_node; 1819169689Skan } 1820169689Skan 1821169689Skan /* Try folding *(B+O) to B->X. Still an improvement. */ 1822169689Skan if (POINTER_TYPE_P (TREE_TYPE (base))) 1823169689Skan { 1824169689Skan t = maybe_fold_offset_to_component_ref (TREE_TYPE (TREE_TYPE (base)), 1825169689Skan base, offset, 1826169689Skan TREE_TYPE (expr), true); 1827169689Skan if (t) 1828169689Skan return t; 1829169689Skan } 1830169689Skan } 1831169689Skan 1832169689Skan /* Otherwise we had an offset that we could not simplify. */ 1833169689Skan return NULL_TREE; 1834169689Skan} 1835169689Skan 1836169689Skan 1837169689Skan/* A subroutine of fold_stmt_r. EXPR is a PLUS_EXPR. 1838169689Skan 1839169689Skan A quaint feature extant in our address arithmetic is that there 1840169689Skan can be hidden type changes here. The type of the result need 1841169689Skan not be the same as the type of the input pointer. 1842169689Skan 1843169689Skan What we're after here is an expression of the form 1844169689Skan (T *)(&array + const) 1845169689Skan where the cast doesn't actually exist, but is implicit in the 1846169689Skan type of the PLUS_EXPR. We'd like to turn this into 1847169689Skan &array[x] 1848169689Skan which may be able to propagate further. */ 1849169689Skan 1850169689Skanstatic tree 1851169689Skanmaybe_fold_stmt_addition (tree expr) 1852169689Skan{ 1853169689Skan tree op0 = TREE_OPERAND (expr, 0); 1854169689Skan tree op1 = TREE_OPERAND (expr, 1); 1855169689Skan tree ptr_type = TREE_TYPE (expr); 1856169689Skan tree ptd_type; 1857169689Skan tree t; 1858169689Skan bool subtract = (TREE_CODE (expr) == MINUS_EXPR); 1859169689Skan 1860169689Skan /* We're only interested in pointer arithmetic. */ 1861169689Skan if (!POINTER_TYPE_P (ptr_type)) 1862169689Skan return NULL_TREE; 1863169689Skan /* Canonicalize the integral operand to op1. */ 1864169689Skan if (INTEGRAL_TYPE_P (TREE_TYPE (op0))) 1865169689Skan { 1866169689Skan if (subtract) 1867169689Skan return NULL_TREE; 1868169689Skan t = op0, op0 = op1, op1 = t; 1869169689Skan } 1870169689Skan /* It had better be a constant. */ 1871169689Skan if (TREE_CODE (op1) != INTEGER_CST) 1872169689Skan return NULL_TREE; 1873169689Skan /* The first operand should be an ADDR_EXPR. */ 1874169689Skan if (TREE_CODE (op0) != ADDR_EXPR) 1875169689Skan return NULL_TREE; 1876169689Skan op0 = TREE_OPERAND (op0, 0); 1877169689Skan 1878169689Skan /* If the first operand is an ARRAY_REF, expand it so that we can fold 1879169689Skan the offset into it. */ 1880169689Skan while (TREE_CODE (op0) == ARRAY_REF) 1881169689Skan { 1882169689Skan tree array_obj = TREE_OPERAND (op0, 0); 1883169689Skan tree array_idx = TREE_OPERAND (op0, 1); 1884169689Skan tree elt_type = TREE_TYPE (op0); 1885169689Skan tree elt_size = TYPE_SIZE_UNIT (elt_type); 1886169689Skan tree min_idx; 1887169689Skan 1888169689Skan if (TREE_CODE (array_idx) != INTEGER_CST) 1889169689Skan break; 1890169689Skan if (TREE_CODE (elt_size) != INTEGER_CST) 1891169689Skan break; 1892169689Skan 1893169689Skan /* Un-bias the index by the min index of the array type. */ 1894169689Skan min_idx = TYPE_DOMAIN (TREE_TYPE (array_obj)); 1895169689Skan if (min_idx) 1896169689Skan { 1897169689Skan min_idx = TYPE_MIN_VALUE (min_idx); 1898169689Skan if (min_idx) 1899169689Skan { 1900169689Skan if (TREE_CODE (min_idx) != INTEGER_CST) 1901169689Skan break; 1902169689Skan 1903169689Skan array_idx = fold_convert (TREE_TYPE (min_idx), array_idx); 1904169689Skan if (!integer_zerop (min_idx)) 1905169689Skan array_idx = int_const_binop (MINUS_EXPR, array_idx, 1906169689Skan min_idx, 0); 1907169689Skan } 1908169689Skan } 1909169689Skan 1910169689Skan /* Convert the index to a byte offset. */ 1911169689Skan array_idx = fold_convert (sizetype, array_idx); 1912169689Skan array_idx = int_const_binop (MULT_EXPR, array_idx, elt_size, 0); 1913169689Skan 1914169689Skan /* Update the operands for the next round, or for folding. */ 1915169689Skan /* If we're manipulating unsigned types, then folding into negative 1916169689Skan values can produce incorrect results. Particularly if the type 1917169689Skan is smaller than the width of the pointer. */ 1918169689Skan if (subtract 1919169689Skan && TYPE_UNSIGNED (TREE_TYPE (op1)) 1920169689Skan && tree_int_cst_lt (array_idx, op1)) 1921169689Skan return NULL; 1922169689Skan op1 = int_const_binop (subtract ? MINUS_EXPR : PLUS_EXPR, 1923169689Skan array_idx, op1, 0); 1924169689Skan subtract = false; 1925169689Skan op0 = array_obj; 1926169689Skan } 1927169689Skan 1928169689Skan /* If we weren't able to fold the subtraction into another array reference, 1929169689Skan canonicalize the integer for passing to the array and component ref 1930169689Skan simplification functions. */ 1931169689Skan if (subtract) 1932169689Skan { 1933169689Skan if (TYPE_UNSIGNED (TREE_TYPE (op1))) 1934169689Skan return NULL; 1935169689Skan op1 = fold_unary (NEGATE_EXPR, TREE_TYPE (op1), op1); 1936169689Skan /* ??? In theory fold should always produce another integer. */ 1937169689Skan if (op1 == NULL || TREE_CODE (op1) != INTEGER_CST) 1938169689Skan return NULL; 1939169689Skan } 1940169689Skan 1941169689Skan ptd_type = TREE_TYPE (ptr_type); 1942169689Skan 1943169689Skan /* At which point we can try some of the same things as for indirects. */ 1944169689Skan t = maybe_fold_offset_to_array_ref (op0, op1, ptd_type); 1945169689Skan if (!t) 1946169689Skan t = maybe_fold_offset_to_component_ref (TREE_TYPE (op0), op0, op1, 1947169689Skan ptd_type, false); 1948169689Skan if (t) 1949169689Skan t = build1 (ADDR_EXPR, ptr_type, t); 1950169689Skan 1951169689Skan return t; 1952169689Skan} 1953169689Skan 1954169689Skan/* For passing state through walk_tree into fold_stmt_r and its 1955169689Skan children. */ 1956169689Skan 1957169689Skanstruct fold_stmt_r_data 1958169689Skan{ 1959169689Skan tree stmt; 1960169689Skan bool *changed_p; 1961169689Skan bool *inside_addr_expr_p; 1962169689Skan}; 1963169689Skan 1964169689Skan/* Subroutine of fold_stmt called via walk_tree. We perform several 1965169689Skan simplifications of EXPR_P, mostly having to do with pointer arithmetic. */ 1966169689Skan 1967169689Skanstatic tree 1968169689Skanfold_stmt_r (tree *expr_p, int *walk_subtrees, void *data) 1969169689Skan{ 1970169689Skan struct fold_stmt_r_data *fold_stmt_r_data = (struct fold_stmt_r_data *) data; 1971169689Skan bool *inside_addr_expr_p = fold_stmt_r_data->inside_addr_expr_p; 1972169689Skan bool *changed_p = fold_stmt_r_data->changed_p; 1973169689Skan tree expr = *expr_p, t; 1974169689Skan 1975169689Skan /* ??? It'd be nice if walk_tree had a pre-order option. */ 1976169689Skan switch (TREE_CODE (expr)) 1977169689Skan { 1978169689Skan case INDIRECT_REF: 1979169689Skan t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL); 1980169689Skan if (t) 1981169689Skan return t; 1982169689Skan *walk_subtrees = 0; 1983169689Skan 1984169689Skan t = maybe_fold_stmt_indirect (expr, TREE_OPERAND (expr, 0), 1985169689Skan integer_zero_node); 1986169689Skan break; 1987169689Skan 1988169689Skan /* ??? Could handle more ARRAY_REFs here, as a variant of INDIRECT_REF. 1989169689Skan We'd only want to bother decomposing an existing ARRAY_REF if 1990169689Skan the base array is found to have another offset contained within. 1991169689Skan Otherwise we'd be wasting time. */ 1992169689Skan case ARRAY_REF: 1993169689Skan /* If we are not processing expressions found within an 1994169689Skan ADDR_EXPR, then we can fold constant array references. */ 1995169689Skan if (!*inside_addr_expr_p) 1996169689Skan t = fold_read_from_constant_string (expr); 1997169689Skan else 1998169689Skan t = NULL; 1999169689Skan break; 2000169689Skan 2001169689Skan case ADDR_EXPR: 2002169689Skan *inside_addr_expr_p = true; 2003169689Skan t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL); 2004169689Skan *inside_addr_expr_p = false; 2005169689Skan if (t) 2006169689Skan return t; 2007169689Skan *walk_subtrees = 0; 2008169689Skan 2009169689Skan /* Set TREE_INVARIANT properly so that the value is properly 2010169689Skan considered constant, and so gets propagated as expected. */ 2011169689Skan if (*changed_p) 2012169689Skan recompute_tree_invariant_for_addr_expr (expr); 2013169689Skan return NULL_TREE; 2014169689Skan 2015169689Skan case PLUS_EXPR: 2016169689Skan case MINUS_EXPR: 2017169689Skan t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL); 2018169689Skan if (t) 2019169689Skan return t; 2020169689Skan t = walk_tree (&TREE_OPERAND (expr, 1), fold_stmt_r, data, NULL); 2021169689Skan if (t) 2022169689Skan return t; 2023169689Skan *walk_subtrees = 0; 2024169689Skan 2025169689Skan t = maybe_fold_stmt_addition (expr); 2026169689Skan break; 2027169689Skan 2028169689Skan case COMPONENT_REF: 2029169689Skan t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL); 2030169689Skan if (t) 2031169689Skan return t; 2032169689Skan *walk_subtrees = 0; 2033169689Skan 2034169689Skan /* Make sure the FIELD_DECL is actually a field in the type on the lhs. 2035169689Skan We've already checked that the records are compatible, so we should 2036169689Skan come up with a set of compatible fields. */ 2037169689Skan { 2038169689Skan tree expr_record = TREE_TYPE (TREE_OPERAND (expr, 0)); 2039169689Skan tree expr_field = TREE_OPERAND (expr, 1); 2040169689Skan 2041169689Skan if (DECL_FIELD_CONTEXT (expr_field) != TYPE_MAIN_VARIANT (expr_record)) 2042169689Skan { 2043169689Skan expr_field = find_compatible_field (expr_record, expr_field); 2044169689Skan TREE_OPERAND (expr, 1) = expr_field; 2045169689Skan } 2046169689Skan } 2047169689Skan break; 2048169689Skan 2049169689Skan case TARGET_MEM_REF: 2050169689Skan t = maybe_fold_tmr (expr); 2051169689Skan break; 2052169689Skan 2053169689Skan case COND_EXPR: 2054169689Skan if (COMPARISON_CLASS_P (TREE_OPERAND (expr, 0))) 2055169689Skan { 2056169689Skan tree op0 = TREE_OPERAND (expr, 0); 2057169689Skan tree tem; 2058169689Skan bool set; 2059169689Skan 2060169689Skan fold_defer_overflow_warnings (); 2061169689Skan tem = fold_binary (TREE_CODE (op0), TREE_TYPE (op0), 2062169689Skan TREE_OPERAND (op0, 0), 2063169689Skan TREE_OPERAND (op0, 1)); 2064169689Skan set = tem && is_gimple_condexpr (tem); 2065169689Skan fold_undefer_overflow_warnings (set, fold_stmt_r_data->stmt, 0); 2066169689Skan if (set) 2067169689Skan TREE_OPERAND (expr, 0) = tem; 2068169689Skan t = expr; 2069169689Skan break; 2070169689Skan } 2071169689Skan 2072169689Skan default: 2073169689Skan return NULL_TREE; 2074169689Skan } 2075169689Skan 2076169689Skan if (t) 2077169689Skan { 2078169689Skan *expr_p = t; 2079169689Skan *changed_p = true; 2080169689Skan } 2081169689Skan 2082169689Skan return NULL_TREE; 2083169689Skan} 2084169689Skan 2085169689Skan 2086169689Skan/* Return the string length, maximum string length or maximum value of 2087169689Skan ARG in LENGTH. 2088169689Skan If ARG is an SSA name variable, follow its use-def chains. If LENGTH 2089169689Skan is not NULL and, for TYPE == 0, its value is not equal to the length 2090169689Skan we determine or if we are unable to determine the length or value, 2091169689Skan return false. VISITED is a bitmap of visited variables. 2092169689Skan TYPE is 0 if string length should be returned, 1 for maximum string 2093169689Skan length and 2 for maximum value ARG can have. */ 2094169689Skan 2095169689Skanstatic bool 2096169689Skanget_maxval_strlen (tree arg, tree *length, bitmap visited, int type) 2097169689Skan{ 2098169689Skan tree var, def_stmt, val; 2099169689Skan 2100169689Skan if (TREE_CODE (arg) != SSA_NAME) 2101169689Skan { 2102169689Skan if (type == 2) 2103169689Skan { 2104169689Skan val = arg; 2105169689Skan if (TREE_CODE (val) != INTEGER_CST 2106169689Skan || tree_int_cst_sgn (val) < 0) 2107169689Skan return false; 2108169689Skan } 2109169689Skan else 2110169689Skan val = c_strlen (arg, 1); 2111169689Skan if (!val) 2112169689Skan return false; 2113169689Skan 2114169689Skan if (*length) 2115169689Skan { 2116169689Skan if (type > 0) 2117169689Skan { 2118169689Skan if (TREE_CODE (*length) != INTEGER_CST 2119169689Skan || TREE_CODE (val) != INTEGER_CST) 2120169689Skan return false; 2121169689Skan 2122169689Skan if (tree_int_cst_lt (*length, val)) 2123169689Skan *length = val; 2124169689Skan return true; 2125169689Skan } 2126169689Skan else if (simple_cst_equal (val, *length) != 1) 2127169689Skan return false; 2128169689Skan } 2129169689Skan 2130169689Skan *length = val; 2131169689Skan return true; 2132169689Skan } 2133169689Skan 2134169689Skan /* If we were already here, break the infinite cycle. */ 2135169689Skan if (bitmap_bit_p (visited, SSA_NAME_VERSION (arg))) 2136169689Skan return true; 2137169689Skan bitmap_set_bit (visited, SSA_NAME_VERSION (arg)); 2138169689Skan 2139169689Skan var = arg; 2140169689Skan def_stmt = SSA_NAME_DEF_STMT (var); 2141169689Skan 2142169689Skan switch (TREE_CODE (def_stmt)) 2143169689Skan { 2144169689Skan case MODIFY_EXPR: 2145169689Skan { 2146169689Skan tree rhs; 2147169689Skan 2148169689Skan /* The RHS of the statement defining VAR must either have a 2149169689Skan constant length or come from another SSA_NAME with a constant 2150169689Skan length. */ 2151169689Skan rhs = TREE_OPERAND (def_stmt, 1); 2152169689Skan STRIP_NOPS (rhs); 2153169689Skan return get_maxval_strlen (rhs, length, visited, type); 2154169689Skan } 2155169689Skan 2156169689Skan case PHI_NODE: 2157169689Skan { 2158169689Skan /* All the arguments of the PHI node must have the same constant 2159169689Skan length. */ 2160169689Skan int i; 2161169689Skan 2162169689Skan for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++) 2163169689Skan { 2164169689Skan tree arg = PHI_ARG_DEF (def_stmt, i); 2165169689Skan 2166169689Skan /* If this PHI has itself as an argument, we cannot 2167169689Skan determine the string length of this argument. However, 2168169689Skan if we can find a constant string length for the other 2169169689Skan PHI args then we can still be sure that this is a 2170169689Skan constant string length. So be optimistic and just 2171169689Skan continue with the next argument. */ 2172169689Skan if (arg == PHI_RESULT (def_stmt)) 2173169689Skan continue; 2174169689Skan 2175169689Skan if (!get_maxval_strlen (arg, length, visited, type)) 2176169689Skan return false; 2177169689Skan } 2178169689Skan 2179169689Skan return true; 2180169689Skan } 2181169689Skan 2182169689Skan default: 2183169689Skan break; 2184169689Skan } 2185169689Skan 2186169689Skan 2187169689Skan return false; 2188169689Skan} 2189169689Skan 2190169689Skan 2191169689Skan/* Fold builtin call FN in statement STMT. If it cannot be folded into a 2192169689Skan constant, return NULL_TREE. Otherwise, return its constant value. */ 2193169689Skan 2194169689Skanstatic tree 2195169689Skanccp_fold_builtin (tree stmt, tree fn) 2196169689Skan{ 2197169689Skan tree result, val[3]; 2198169689Skan tree callee, arglist, a; 2199169689Skan int arg_mask, i, type; 2200169689Skan bitmap visited; 2201169689Skan bool ignore; 2202169689Skan 2203169689Skan ignore = TREE_CODE (stmt) != MODIFY_EXPR; 2204169689Skan 2205169689Skan /* First try the generic builtin folder. If that succeeds, return the 2206169689Skan result directly. */ 2207169689Skan callee = get_callee_fndecl (fn); 2208169689Skan arglist = TREE_OPERAND (fn, 1); 2209169689Skan result = fold_builtin (callee, arglist, ignore); 2210169689Skan if (result) 2211169689Skan { 2212169689Skan if (ignore) 2213169689Skan STRIP_NOPS (result); 2214169689Skan return result; 2215169689Skan } 2216169689Skan 2217169689Skan /* Ignore MD builtins. */ 2218169689Skan if (DECL_BUILT_IN_CLASS (callee) == BUILT_IN_MD) 2219169689Skan return NULL_TREE; 2220169689Skan 2221169689Skan /* If the builtin could not be folded, and it has no argument list, 2222169689Skan we're done. */ 2223169689Skan if (!arglist) 2224169689Skan return NULL_TREE; 2225169689Skan 2226169689Skan /* Limit the work only for builtins we know how to simplify. */ 2227169689Skan switch (DECL_FUNCTION_CODE (callee)) 2228169689Skan { 2229169689Skan case BUILT_IN_STRLEN: 2230169689Skan case BUILT_IN_FPUTS: 2231169689Skan case BUILT_IN_FPUTS_UNLOCKED: 2232169689Skan arg_mask = 1; 2233169689Skan type = 0; 2234169689Skan break; 2235169689Skan case BUILT_IN_STRCPY: 2236169689Skan case BUILT_IN_STRNCPY: 2237169689Skan arg_mask = 2; 2238169689Skan type = 0; 2239169689Skan break; 2240169689Skan case BUILT_IN_MEMCPY_CHK: 2241169689Skan case BUILT_IN_MEMPCPY_CHK: 2242169689Skan case BUILT_IN_MEMMOVE_CHK: 2243169689Skan case BUILT_IN_MEMSET_CHK: 2244169689Skan case BUILT_IN_STRNCPY_CHK: 2245169689Skan arg_mask = 4; 2246169689Skan type = 2; 2247169689Skan break; 2248169689Skan case BUILT_IN_STRCPY_CHK: 2249169689Skan case BUILT_IN_STPCPY_CHK: 2250169689Skan arg_mask = 2; 2251169689Skan type = 1; 2252169689Skan break; 2253169689Skan case BUILT_IN_SNPRINTF_CHK: 2254169689Skan case BUILT_IN_VSNPRINTF_CHK: 2255169689Skan arg_mask = 2; 2256169689Skan type = 2; 2257169689Skan break; 2258169689Skan default: 2259169689Skan return NULL_TREE; 2260169689Skan } 2261169689Skan 2262169689Skan /* Try to use the dataflow information gathered by the CCP process. */ 2263169689Skan visited = BITMAP_ALLOC (NULL); 2264169689Skan 2265169689Skan memset (val, 0, sizeof (val)); 2266169689Skan for (i = 0, a = arglist; 2267169689Skan arg_mask; 2268169689Skan i++, arg_mask >>= 1, a = TREE_CHAIN (a)) 2269169689Skan if (arg_mask & 1) 2270169689Skan { 2271169689Skan bitmap_clear (visited); 2272169689Skan if (!get_maxval_strlen (TREE_VALUE (a), &val[i], visited, type)) 2273169689Skan val[i] = NULL_TREE; 2274169689Skan } 2275169689Skan 2276169689Skan BITMAP_FREE (visited); 2277169689Skan 2278169689Skan result = NULL_TREE; 2279169689Skan switch (DECL_FUNCTION_CODE (callee)) 2280169689Skan { 2281169689Skan case BUILT_IN_STRLEN: 2282169689Skan if (val[0]) 2283169689Skan { 2284169689Skan tree new = fold_convert (TREE_TYPE (fn), val[0]); 2285169689Skan 2286169689Skan /* If the result is not a valid gimple value, or not a cast 2287169689Skan of a valid gimple value, then we can not use the result. */ 2288169689Skan if (is_gimple_val (new) 2289169689Skan || (is_gimple_cast (new) 2290169689Skan && is_gimple_val (TREE_OPERAND (new, 0)))) 2291169689Skan return new; 2292169689Skan } 2293169689Skan break; 2294169689Skan 2295169689Skan case BUILT_IN_STRCPY: 2296169689Skan if (val[1] && is_gimple_val (val[1])) 2297169689Skan result = fold_builtin_strcpy (callee, arglist, val[1]); 2298169689Skan break; 2299169689Skan 2300169689Skan case BUILT_IN_STRNCPY: 2301169689Skan if (val[1] && is_gimple_val (val[1])) 2302169689Skan result = fold_builtin_strncpy (callee, arglist, val[1]); 2303169689Skan break; 2304169689Skan 2305169689Skan case BUILT_IN_FPUTS: 2306169689Skan result = fold_builtin_fputs (arglist, 2307169689Skan TREE_CODE (stmt) != MODIFY_EXPR, 0, 2308169689Skan val[0]); 2309169689Skan break; 2310169689Skan 2311169689Skan case BUILT_IN_FPUTS_UNLOCKED: 2312169689Skan result = fold_builtin_fputs (arglist, 2313169689Skan TREE_CODE (stmt) != MODIFY_EXPR, 1, 2314169689Skan val[0]); 2315169689Skan break; 2316169689Skan 2317169689Skan case BUILT_IN_MEMCPY_CHK: 2318169689Skan case BUILT_IN_MEMPCPY_CHK: 2319169689Skan case BUILT_IN_MEMMOVE_CHK: 2320169689Skan case BUILT_IN_MEMSET_CHK: 2321169689Skan if (val[2] && is_gimple_val (val[2])) 2322169689Skan result = fold_builtin_memory_chk (callee, arglist, val[2], ignore, 2323169689Skan DECL_FUNCTION_CODE (callee)); 2324169689Skan break; 2325169689Skan 2326169689Skan case BUILT_IN_STRCPY_CHK: 2327169689Skan case BUILT_IN_STPCPY_CHK: 2328169689Skan if (val[1] && is_gimple_val (val[1])) 2329169689Skan result = fold_builtin_stxcpy_chk (callee, arglist, val[1], ignore, 2330169689Skan DECL_FUNCTION_CODE (callee)); 2331169689Skan break; 2332169689Skan 2333169689Skan case BUILT_IN_STRNCPY_CHK: 2334169689Skan if (val[2] && is_gimple_val (val[2])) 2335169689Skan result = fold_builtin_strncpy_chk (arglist, val[2]); 2336169689Skan break; 2337169689Skan 2338169689Skan case BUILT_IN_SNPRINTF_CHK: 2339169689Skan case BUILT_IN_VSNPRINTF_CHK: 2340169689Skan if (val[1] && is_gimple_val (val[1])) 2341169689Skan result = fold_builtin_snprintf_chk (arglist, val[1], 2342169689Skan DECL_FUNCTION_CODE (callee)); 2343169689Skan break; 2344169689Skan 2345169689Skan default: 2346169689Skan gcc_unreachable (); 2347169689Skan } 2348169689Skan 2349169689Skan if (result && ignore) 2350169689Skan result = fold_ignored_result (result); 2351169689Skan return result; 2352169689Skan} 2353169689Skan 2354169689Skan 2355169689Skan/* Fold the statement pointed to by STMT_P. In some cases, this function may 2356169689Skan replace the whole statement with a new one. Returns true iff folding 2357169689Skan makes any changes. */ 2358169689Skan 2359169689Skanbool 2360169689Skanfold_stmt (tree *stmt_p) 2361169689Skan{ 2362169689Skan tree rhs, result, stmt; 2363169689Skan struct fold_stmt_r_data fold_stmt_r_data; 2364169689Skan bool changed = false; 2365169689Skan bool inside_addr_expr = false; 2366169689Skan 2367169689Skan stmt = *stmt_p; 2368169689Skan 2369169689Skan fold_stmt_r_data.stmt = stmt; 2370169689Skan fold_stmt_r_data.changed_p = &changed; 2371169689Skan fold_stmt_r_data.inside_addr_expr_p = &inside_addr_expr; 2372169689Skan 2373169689Skan /* If we replaced constants and the statement makes pointer dereferences, 2374169689Skan then we may need to fold instances of *&VAR into VAR, etc. */ 2375169689Skan if (walk_tree (stmt_p, fold_stmt_r, &fold_stmt_r_data, NULL)) 2376169689Skan { 2377169689Skan *stmt_p 2378169689Skan = build_function_call_expr (implicit_built_in_decls[BUILT_IN_TRAP], 2379169689Skan NULL); 2380169689Skan return true; 2381169689Skan } 2382169689Skan 2383169689Skan rhs = get_rhs (stmt); 2384169689Skan if (!rhs) 2385169689Skan return changed; 2386169689Skan result = NULL_TREE; 2387169689Skan 2388169689Skan if (TREE_CODE (rhs) == CALL_EXPR) 2389169689Skan { 2390169689Skan tree callee; 2391169689Skan 2392169689Skan /* Check for builtins that CCP can handle using information not 2393169689Skan available in the generic fold routines. */ 2394169689Skan callee = get_callee_fndecl (rhs); 2395169689Skan if (callee && DECL_BUILT_IN (callee)) 2396169689Skan result = ccp_fold_builtin (stmt, rhs); 2397169689Skan else 2398169689Skan { 2399169689Skan /* Check for resolvable OBJ_TYPE_REF. The only sorts we can resolve 2400169689Skan here are when we've propagated the address of a decl into the 2401169689Skan object slot. */ 2402169689Skan /* ??? Should perhaps do this in fold proper. However, doing it 2403169689Skan there requires that we create a new CALL_EXPR, and that requires 2404169689Skan copying EH region info to the new node. Easier to just do it 2405169689Skan here where we can just smash the call operand. Also 2406169689Skan CALL_EXPR_RETURN_SLOT_OPT needs to be handled correctly and 2407169689Skan copied, fold_ternary does not have not information. */ 2408169689Skan callee = TREE_OPERAND (rhs, 0); 2409169689Skan if (TREE_CODE (callee) == OBJ_TYPE_REF 2410169689Skan && lang_hooks.fold_obj_type_ref 2411169689Skan && TREE_CODE (OBJ_TYPE_REF_OBJECT (callee)) == ADDR_EXPR 2412169689Skan && DECL_P (TREE_OPERAND 2413169689Skan (OBJ_TYPE_REF_OBJECT (callee), 0))) 2414169689Skan { 2415169689Skan tree t; 2416169689Skan 2417169689Skan /* ??? Caution: Broken ADDR_EXPR semantics means that 2418169689Skan looking at the type of the operand of the addr_expr 2419169689Skan can yield an array type. See silly exception in 2420169689Skan check_pointer_types_r. */ 2421169689Skan 2422169689Skan t = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (callee))); 2423169689Skan t = lang_hooks.fold_obj_type_ref (callee, t); 2424169689Skan if (t) 2425169689Skan { 2426169689Skan TREE_OPERAND (rhs, 0) = t; 2427169689Skan changed = true; 2428169689Skan } 2429169689Skan } 2430169689Skan } 2431169689Skan } 2432169689Skan 2433169689Skan /* If we couldn't fold the RHS, hand over to the generic fold routines. */ 2434169689Skan if (result == NULL_TREE) 2435169689Skan result = fold (rhs); 2436169689Skan 2437169689Skan /* Strip away useless type conversions. Both the NON_LVALUE_EXPR that 2438169689Skan may have been added by fold, and "useless" type conversions that might 2439169689Skan now be apparent due to propagation. */ 2440169689Skan STRIP_USELESS_TYPE_CONVERSION (result); 2441169689Skan 2442169689Skan if (result != rhs) 2443169689Skan changed |= set_rhs (stmt_p, result); 2444169689Skan 2445169689Skan return changed; 2446169689Skan} 2447169689Skan 2448169689Skan/* Perform the minimal folding on statement STMT. Only operations like 2449169689Skan *&x created by constant propagation are handled. The statement cannot 2450169689Skan be replaced with a new one. */ 2451169689Skan 2452169689Skanbool 2453169689Skanfold_stmt_inplace (tree stmt) 2454169689Skan{ 2455169689Skan tree old_stmt = stmt, rhs, new_rhs; 2456169689Skan struct fold_stmt_r_data fold_stmt_r_data; 2457169689Skan bool changed = false; 2458169689Skan bool inside_addr_expr = false; 2459169689Skan 2460169689Skan fold_stmt_r_data.stmt = stmt; 2461169689Skan fold_stmt_r_data.changed_p = &changed; 2462169689Skan fold_stmt_r_data.inside_addr_expr_p = &inside_addr_expr; 2463169689Skan 2464169689Skan walk_tree (&stmt, fold_stmt_r, &fold_stmt_r_data, NULL); 2465169689Skan gcc_assert (stmt == old_stmt); 2466169689Skan 2467169689Skan rhs = get_rhs (stmt); 2468169689Skan if (!rhs || rhs == stmt) 2469169689Skan return changed; 2470169689Skan 2471169689Skan new_rhs = fold (rhs); 2472169689Skan STRIP_USELESS_TYPE_CONVERSION (new_rhs); 2473169689Skan if (new_rhs == rhs) 2474169689Skan return changed; 2475169689Skan 2476169689Skan changed |= set_rhs (&stmt, new_rhs); 2477169689Skan gcc_assert (stmt == old_stmt); 2478169689Skan 2479169689Skan return changed; 2480169689Skan} 2481169689Skan 2482169689Skan/* Convert EXPR into a GIMPLE value suitable for substitution on the 2483169689Skan RHS of an assignment. Insert the necessary statements before 2484169689Skan iterator *SI_P. */ 2485169689Skan 2486169689Skanstatic tree 2487169689Skanconvert_to_gimple_builtin (block_stmt_iterator *si_p, tree expr) 2488169689Skan{ 2489169689Skan tree_stmt_iterator ti; 2490169689Skan tree stmt = bsi_stmt (*si_p); 2491169689Skan tree tmp, stmts = NULL; 2492169689Skan 2493169689Skan push_gimplify_context (); 2494169689Skan tmp = get_initialized_tmp_var (expr, &stmts, NULL); 2495169689Skan pop_gimplify_context (NULL); 2496169689Skan 2497169689Skan if (EXPR_HAS_LOCATION (stmt)) 2498169689Skan annotate_all_with_locus (&stmts, EXPR_LOCATION (stmt)); 2499169689Skan 2500169689Skan /* The replacement can expose previously unreferenced variables. */ 2501169689Skan for (ti = tsi_start (stmts); !tsi_end_p (ti); tsi_next (&ti)) 2502169689Skan { 2503169689Skan tree new_stmt = tsi_stmt (ti); 2504169689Skan find_new_referenced_vars (tsi_stmt_ptr (ti)); 2505169689Skan bsi_insert_before (si_p, new_stmt, BSI_NEW_STMT); 2506169689Skan mark_new_vars_to_rename (bsi_stmt (*si_p)); 2507169689Skan bsi_next (si_p); 2508169689Skan } 2509169689Skan 2510169689Skan return tmp; 2511169689Skan} 2512169689Skan 2513169689Skan 2514169689Skan/* A simple pass that attempts to fold all builtin functions. This pass 2515169689Skan is run after we've propagated as many constants as we can. */ 2516169689Skan 2517169689Skanstatic unsigned int 2518169689Skanexecute_fold_all_builtins (void) 2519169689Skan{ 2520169689Skan bool cfg_changed = false; 2521169689Skan basic_block bb; 2522169689Skan FOR_EACH_BB (bb) 2523169689Skan { 2524169689Skan block_stmt_iterator i; 2525169689Skan for (i = bsi_start (bb); !bsi_end_p (i); ) 2526169689Skan { 2527169689Skan tree *stmtp = bsi_stmt_ptr (i); 2528169689Skan tree old_stmt = *stmtp; 2529169689Skan tree call = get_rhs (*stmtp); 2530169689Skan tree callee, result; 2531169689Skan enum built_in_function fcode; 2532169689Skan 2533169689Skan if (!call || TREE_CODE (call) != CALL_EXPR) 2534169689Skan { 2535169689Skan bsi_next (&i); 2536169689Skan continue; 2537169689Skan } 2538169689Skan callee = get_callee_fndecl (call); 2539169689Skan if (!callee || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL) 2540169689Skan { 2541169689Skan bsi_next (&i); 2542169689Skan continue; 2543169689Skan } 2544169689Skan fcode = DECL_FUNCTION_CODE (callee); 2545169689Skan 2546169689Skan result = ccp_fold_builtin (*stmtp, call); 2547169689Skan if (!result) 2548169689Skan switch (DECL_FUNCTION_CODE (callee)) 2549169689Skan { 2550169689Skan case BUILT_IN_CONSTANT_P: 2551169689Skan /* Resolve __builtin_constant_p. If it hasn't been 2552169689Skan folded to integer_one_node by now, it's fairly 2553169689Skan certain that the value simply isn't constant. */ 2554169689Skan result = integer_zero_node; 2555169689Skan break; 2556169689Skan 2557169689Skan default: 2558169689Skan bsi_next (&i); 2559169689Skan continue; 2560169689Skan } 2561169689Skan 2562169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2563169689Skan { 2564169689Skan fprintf (dump_file, "Simplified\n "); 2565169689Skan print_generic_stmt (dump_file, *stmtp, dump_flags); 2566169689Skan } 2567169689Skan 2568169689Skan if (!set_rhs (stmtp, result)) 2569169689Skan { 2570169689Skan result = convert_to_gimple_builtin (&i, result); 2571169689Skan if (result) 2572169689Skan { 2573169689Skan bool ok = set_rhs (stmtp, result); 2574169689Skan 2575169689Skan gcc_assert (ok); 2576169689Skan } 2577169689Skan } 2578169689Skan mark_new_vars_to_rename (*stmtp); 2579169689Skan if (maybe_clean_or_replace_eh_stmt (old_stmt, *stmtp) 2580169689Skan && tree_purge_dead_eh_edges (bb)) 2581169689Skan cfg_changed = true; 2582169689Skan 2583169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2584169689Skan { 2585169689Skan fprintf (dump_file, "to\n "); 2586169689Skan print_generic_stmt (dump_file, *stmtp, dump_flags); 2587169689Skan fprintf (dump_file, "\n"); 2588169689Skan } 2589169689Skan 2590169689Skan /* Retry the same statement if it changed into another 2591169689Skan builtin, there might be new opportunities now. */ 2592169689Skan call = get_rhs (*stmtp); 2593169689Skan if (!call || TREE_CODE (call) != CALL_EXPR) 2594169689Skan { 2595169689Skan bsi_next (&i); 2596169689Skan continue; 2597169689Skan } 2598169689Skan callee = get_callee_fndecl (call); 2599169689Skan if (!callee 2600169689Skan || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL 2601169689Skan || DECL_FUNCTION_CODE (callee) == fcode) 2602169689Skan bsi_next (&i); 2603169689Skan } 2604169689Skan } 2605169689Skan 2606169689Skan /* Delete unreachable blocks. */ 2607169689Skan if (cfg_changed) 2608169689Skan cleanup_tree_cfg (); 2609169689Skan return 0; 2610169689Skan} 2611169689Skan 2612169689Skan 2613169689Skanstruct tree_opt_pass pass_fold_builtins = 2614169689Skan{ 2615169689Skan "fab", /* name */ 2616169689Skan NULL, /* gate */ 2617169689Skan execute_fold_all_builtins, /* execute */ 2618169689Skan NULL, /* sub */ 2619169689Skan NULL, /* next */ 2620169689Skan 0, /* static_pass_number */ 2621169689Skan 0, /* tv_id */ 2622169689Skan PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 2623169689Skan 0, /* properties_provided */ 2624169689Skan 0, /* properties_destroyed */ 2625169689Skan 0, /* todo_flags_start */ 2626169689Skan TODO_dump_func 2627169689Skan | TODO_verify_ssa 2628169689Skan | TODO_update_ssa, /* todo_flags_finish */ 2629169689Skan 0 /* letter */ 2630169689Skan}; 2631