X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-ssa-ccp.c;h=6816dafd6c1b24c9d0489bf701c218a95b35a839;hb=aff6b8e2844233bb221f10575b29eaa2841d033a;hp=70b91f26520179f36eba86e1e6fa34c75ce09741;hpb=72648a0ea58cf7f9a75b070cb5a83d2a7c24c1a9;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-ssa-ccp.c b/gcc/tree-ssa-ccp.c index 70b91f26520..6816dafd6c1 100644 --- a/gcc/tree-ssa-ccp.c +++ b/gcc/tree-ssa-ccp.c @@ -1,5 +1,6 @@ /* Conditional constant propagation pass for the GNU compiler. - Copyright (C) 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc. + Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005 + Free Software Foundation, Inc. Adapted from original RTL SSA-CCP by Daniel Berlin Adapted to GIMPLE trees by Diego Novillo @@ -20,7 +21,161 @@ along with GCC; see the file COPYING. If not, write to the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ -/* Conditional constant propagation. +/* Conditional constant propagation (CCP) is based on the SSA + propagation engine (tree-ssa-propagate.c). Constant assignments of + the form VAR = CST are propagated from the assignments into uses of + VAR, which in turn may generate new constants. The simulation uses + a four level lattice to keep track of constant values associated + with SSA names. Given an SSA name V_i, it may take one of the + following values: + + UNINITIALIZED -> This is the default starting value. V_i + has not been processed yet. + + UNDEFINED -> V_i is a local variable whose definition + has not been processed yet. Therefore we + don't yet know if its value is a constant + or not. + + CONSTANT -> V_i has been found to hold a constant + value C. + + VARYING -> V_i cannot take a constant value, or if it + does, it is not possible to determine it + at compile time. + + The core of SSA-CCP is in ccp_visit_stmt and ccp_visit_phi_node: + + 1- In ccp_visit_stmt, we are interested in assignments whose RHS + evaluates into a constant and conditional jumps whose predicate + evaluates into a boolean true or false. When an assignment of + the form V_i = CONST is found, V_i's lattice value is set to + CONSTANT and CONST is associated with it. This causes the + propagation engine to add all the SSA edges coming out the + assignment into the worklists, so that statements that use V_i + can be visited. + + If the statement is a conditional with a constant predicate, we + mark the outgoing edges as executable or not executable + depending on the predicate's value. This is then used when + visiting PHI nodes to know when a PHI argument can be ignored. + + + 2- In ccp_visit_phi_node, if all the PHI arguments evaluate to the + same constant C, then the LHS of the PHI is set to C. This + evaluation is known as the "meet operation". Since one of the + goals of this evaluation is to optimistically return constant + values as often as possible, it uses two main short cuts: + + - If an argument is flowing in through a non-executable edge, it + is ignored. This is useful in cases like this: + + if (PRED) + a_9 = 3; + else + a_10 = 100; + a_11 = PHI (a_9, a_10) + + If PRED is known to always evaluate to false, then we can + assume that a_11 will always take its value from a_10, meaning + that instead of consider it VARYING (a_9 and a_10 have + different values), we can consider it CONSTANT 100. + + - If an argument has an UNDEFINED value, then it does not affect + the outcome of the meet operation. If a variable V_i has an + UNDEFINED value, it means that either its defining statement + hasn't been visited yet or V_i has no defining statement, in + which case the original symbol 'V' is being used + uninitialized. Since 'V' is a local variable, the compiler + may assume any initial value for it. + + + After propagation, every variable V_i that ends up with a lattice + value of CONSTANT will have the associated constant value in the + array CONST_VAL[i].VALUE. That is fed into substitute_and_fold for + final substitution and folding. + + + Constant propagation in stores and loads (STORE-CCP) + ---------------------------------------------------- + + While CCP has all the logic to propagate constants in GIMPLE + registers, it is missing the ability to associate constants with + stores and loads (i.e., pointer dereferences, structures and + global/aliased variables). We don't keep loads and stores in + SSA, but we do build a factored use-def web for them (in the + virtual operands). + + For instance, consider the following code fragment: + + struct A a; + const int B = 42; + + void foo (int i) + { + if (i > 10) + a.a = 42; + else + { + a.b = 21; + a.a = a.b + 21; + } + + if (a.a != B) + never_executed (); + } + + We should be able to deduce that the predicate 'a.a != B' is always + false. To achieve this, we associate constant values to the SSA + names in the V_MAY_DEF and V_MUST_DEF operands for each store. + Additionally, since we also glob partial loads/stores with the base + symbol, we also keep track of the memory reference where the + constant value was stored (in the MEM_REF field of PROP_VALUE_T). + For instance, + + # a_5 = V_MAY_DEF + a.a = 2; + + # VUSE + x_3 = a.b; + + In the example above, CCP will associate value '2' with 'a_5', but + it would be wrong to replace the load from 'a.b' with '2', because + '2' had been stored into a.a. + + To support STORE-CCP, it is necessary to add a new value to the + constant propagation lattice. When evaluating a load for a memory + reference we can no longer assume a value of UNDEFINED if we + haven't seen a preceding store to the same memory location. + Consider, for instance global variables: + + int A; + + foo (int i) + { + if (i_3 > 10) + A_4 = 3; + # A_5 = PHI (A_4, A_2); + + # VUSE + A.0_6 = A; + + return A.0_6; + } + + The value of A_2 cannot be assumed to be UNDEFINED, as it may have + been defined outside of foo. If we were to assume it UNDEFINED, we + would erroneously optimize the above into 'return 3;'. Therefore, + when doing STORE-CCP, we introduce a fifth lattice value + (UNKNOWN_VAL), which overrides any other value when computing the + meet operation in PHI nodes. + + Though STORE-CCP is not too expensive, it does have to do more work + than regular CCP, so it is only enabled at -O2. Both regular CCP + and STORE-CCP use the exact same algorithm. The only distinction + is that when doing STORE-CCP, the boolean variable DO_STORE_CCP is + set to true. This affects the evaluation of statements and PHI + nodes. References: @@ -37,26 +192,23 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "system.h" #include "coretypes.h" #include "tm.h" -#include "errors.h" -#include "ggc.h" #include "tree.h" -#include "langhooks.h" - -/* These RTL headers are needed for basic-block.h. */ +#include "flags.h" #include "rtl.h" #include "tm_p.h" -#include "hard-reg-set.h" +#include "ggc.h" #include "basic-block.h" - +#include "output.h" +#include "expr.h" +#include "function.h" #include "diagnostic.h" -#include "tree-inline.h" -#include "tree-flow.h" -#include "tree-gimple.h" +#include "timevar.h" #include "tree-dump.h" +#include "tree-flow.h" #include "tree-pass.h" -#include "timevar.h" -#include "expr.h" -#include "flags.h" +#include "tree-ssa-propagate.h" +#include "langhooks.h" +#include "target.h" /* Possible lattice values. */ @@ -64,755 +216,590 @@ typedef enum { UNINITIALIZED = 0, UNDEFINED, + UNKNOWN_VAL, CONSTANT, VARYING -} latticevalue; +} ccp_lattice_t; + +/* Array of propagated constant values. After propagation, + CONST_VAL[I].VALUE holds the constant value for SSA_NAME(I). If + the constant is held in an SSA name representing a memory store + (i.e., a V_MAY_DEF or V_MUST_DEF), CONST_VAL[I].MEM_REF will + contain the actual memory reference used to store (i.e., the LHS of + the assignment doing the store). */ +static prop_value_t *const_val; + +/* True if we are also propagating constants in stores and loads. */ +static bool do_store_ccp; -/* Use the TREE_VISITED bitflag to mark statements and PHI nodes that have - been deemed VARYING and shouldn't be simulated again. */ -#define DONT_SIMULATE_AGAIN(T) TREE_VISITED (T) +/* Dump constant propagation value VAL to file OUTF prefixed by PREFIX. */ -/* Main structure for CCP. Contains the lattice value and, if it's a - constant, the constant value. */ -typedef struct +static void +dump_lattice_value (FILE *outf, const char *prefix, prop_value_t val) { - latticevalue lattice_val; - tree const_val; -} value; + switch (val.lattice_val) + { + case UNINITIALIZED: + fprintf (outf, "%sUNINITIALIZED", prefix); + break; + case UNDEFINED: + fprintf (outf, "%sUNDEFINED", prefix); + break; + case VARYING: + fprintf (outf, "%sVARYING", prefix); + break; + case UNKNOWN_VAL: + fprintf (outf, "%sUNKNOWN_VAL", prefix); + break; + case CONSTANT: + fprintf (outf, "%sCONSTANT ", prefix); + print_generic_expr (outf, val.value, dump_flags); + break; + default: + gcc_unreachable (); + } +} -/* A bitmap to keep track of executable blocks in the CFG. */ -static sbitmap executable_blocks; -/* Array of control flow edges on the worklist. */ -static GTY(()) varray_type cfg_blocks = NULL; +/* Print lattice value VAL to stderr. */ -static unsigned int cfg_blocks_num = 0; -static int cfg_blocks_tail; -static int cfg_blocks_head; +void debug_lattice_value (prop_value_t val); -static sbitmap bb_in_list; +void +debug_lattice_value (prop_value_t val) +{ + dump_lattice_value (stderr, "", val); + fprintf (stderr, "\n"); +} -/* This is used to track the current value of each variable. */ -static value *value_vector; -/* Worklist of SSA edges which will need reexamination as their definition - has changed. SSA edges are def-use edges in the SSA web. For each - edge, we store the definition statement or PHI node D. The destination - nodes that need to be visited are accessed using immediate_uses - (D). */ -static GTY(()) varray_type ssa_edges; +/* Compute a default value for variable VAR and store it in the + CONST_VAL array. The following rules are used to get default + values: -/* Identical to SSA_EDGES. For performance reasons, the list of SSA - edges is split into two. One contains all SSA edges who need to be - reexamined because their lattice value changed to varying (this - worklist), and the other contains all other SSA edges to be - reexamined (ssa_edges). - - Since most values in the program are varying, the ideal situation - is to move them to that lattice value as quickly as possible. - Thus, it doesn't make sense to process any other type of lattice - value until all varying values are propagated fully, which is one - thing using the varying worklist achieves. In addition, if you - don't use a separate worklist for varying edges, you end up with - situations where lattice values move from - undefined->constant->varying instead of undefined->varying. -*/ -static GTY(()) varray_type varying_ssa_edges; - - -static void initialize (void); -static void finalize (void); -static void visit_phi_node (tree); -static tree ccp_fold (tree); -static value cp_lattice_meet (value, value); -static void visit_stmt (tree); -static void visit_cond_stmt (tree); -static void visit_assignment (tree); -static void add_var_to_ssa_edges_worklist (tree, value); -static void add_outgoing_control_edges (basic_block); -static void add_control_edge (edge); -static void def_to_varying (tree); -static void set_lattice_value (tree, value); -static void simulate_block (basic_block); -static void simulate_stmt (tree); -static void substitute_and_fold (void); -static value evaluate_stmt (tree); -static void dump_lattice_value (FILE *, const char *, value); -static bool replace_uses_in (tree, bool *); -static latticevalue likely_value (tree); -static tree get_rhs (tree); -static bool set_rhs (tree *, tree); -static value *get_value (tree); -static value get_default_value (tree); -static tree ccp_fold_builtin (tree, tree); -static bool get_strlen (tree, tree *, bitmap); -static inline bool cfg_blocks_empty_p (void); -static void cfg_blocks_add (basic_block); -static basic_block cfg_blocks_get (void); -static bool need_imm_uses_for (tree var); - -/* Process an SSA edge worklist. WORKLIST is the SSA edge worklist to - drain. This pops statements off the given WORKLIST and processes - them until there are no more statements on WORKLIST. */ + 1- Global and static variables that are declared constant are + considered CONSTANT. -static void -process_ssa_edge_worklist (varray_type *worklist) -{ - /* Drain the entire worklist. */ - while (VARRAY_ACTIVE_SIZE (*worklist) > 0) - { - /* Pull the statement to simulate off the worklist. */ - tree stmt = VARRAY_TOP_TREE (*worklist); - stmt_ann_t ann = stmt_ann (stmt); - VARRAY_POP (*worklist); - - /* visit_stmt can "cancel" reevaluation of some statements. - If it does, then in_ccp_worklist will be zero. */ - if (ann->in_ccp_worklist) - { - ann->in_ccp_worklist = 0; - simulate_stmt (stmt); - } - } -} - -/* Main entry point for SSA Conditional Constant Propagation. FNDECL is - the declaration for the function to optimize. - - On exit, VARS_TO_RENAME will contain the symbols that have been exposed by - the propagation of ADDR_EXPR expressions into pointer dereferences and need - to be renamed into SSA. + 2- Any other value is considered UNDEFINED. This is useful when + considering PHI nodes. PHI arguments that are undefined do not + change the constant value of the PHI node, which allows for more + constants to be propagated. - PHASE indicates which dump file from the DUMP_FILES array to use when - dumping debugging information. */ + 3- If SSA_NAME_VALUE is set and it is a constant, its value is + used. -static void -tree_ssa_ccp (void) + 4- Variables defined by statements other than assignments and PHI + nodes are considered VARYING. + + 5- Variables that are not GIMPLE registers are considered + UNKNOWN_VAL, which is really a stronger version of UNDEFINED. + It's used to avoid the short circuit evaluation implied by + UNDEFINED in ccp_lattice_meet. */ + +static prop_value_t +get_default_value (tree var) { - initialize (); + tree sym = SSA_NAME_VAR (var); + prop_value_t val = { UNINITIALIZED, NULL_TREE, NULL_TREE }; - /* Iterate until the worklists are empty. */ - while (!cfg_blocks_empty_p () - || VARRAY_ACTIVE_SIZE (ssa_edges) > 0 - || VARRAY_ACTIVE_SIZE (varying_ssa_edges) > 0) + if (!do_store_ccp && !is_gimple_reg (var)) + { + /* Short circuit for regular CCP. We are not interested in any + non-register when DO_STORE_CCP is false. */ + val.lattice_val = VARYING; + } + else if (SSA_NAME_VALUE (var) + && is_gimple_min_invariant (SSA_NAME_VALUE (var))) + { + val.lattice_val = CONSTANT; + val.value = SSA_NAME_VALUE (var); + } + else if (TREE_STATIC (sym) + && TREE_READONLY (sym) + && DECL_INITIAL (sym) + && is_gimple_min_invariant (DECL_INITIAL (sym))) + { + /* Globals and static variables declared 'const' take their + initial value. */ + val.lattice_val = CONSTANT; + val.value = DECL_INITIAL (sym); + val.mem_ref = sym; + } + else { - if (!cfg_blocks_empty_p ()) + tree stmt = SSA_NAME_DEF_STMT (var); + + if (IS_EMPTY_STMT (stmt)) + { + /* Variables defined by an empty statement are those used + before being initialized. If VAR is a local variable, we + can assume initially that it is UNDEFINED. If we are + doing STORE-CCP, function arguments and non-register + variables are initially UNKNOWN_VAL, because we cannot + discard the value incoming from outside of this function + (see ccp_lattice_meet for details). */ + if (is_gimple_reg (sym) && TREE_CODE (sym) != PARM_DECL) + val.lattice_val = UNDEFINED; + else if (do_store_ccp) + val.lattice_val = UNKNOWN_VAL; + else + val.lattice_val = VARYING; + } + else if (TREE_CODE (stmt) == MODIFY_EXPR + || TREE_CODE (stmt) == PHI_NODE) { - /* Pull the next block to simulate off the worklist. */ - basic_block dest_block = cfg_blocks_get (); - simulate_block (dest_block); + /* Any other variable defined by an assignment or a PHI node + is considered UNDEFINED (or UNKNOWN_VAL if VAR is not a + GIMPLE register). */ + val.lattice_val = is_gimple_reg (sym) ? UNDEFINED : UNKNOWN_VAL; + } + else + { + /* Otherwise, VAR will never take on a constant value. */ + val.lattice_val = VARYING; } - - /* In order to move things to varying as quickly as - possible,process the VARYING_SSA_EDGES worklist first. */ - process_ssa_edge_worklist (&varying_ssa_edges); - - /* Now process the SSA_EDGES worklist. */ - process_ssa_edge_worklist (&ssa_edges); } - /* Now perform substitutions based on the known constant values. */ - substitute_and_fold (); + return val; +} - /* Now cleanup any unreachable code. */ - cleanup_tree_cfg (); - /* Free allocated memory. */ - finalize (); +/* Get the constant value associated with variable VAR. If + MAY_USE_DEFAULT_P is true, call get_default_value on variables that + have the lattice value UNINITIALIZED. */ - /* Debugging dumps. */ - if (dump_file && (dump_flags & TDF_DETAILS)) - { - dump_referenced_vars (dump_file); - fprintf (dump_file, "\n\n"); - } +static prop_value_t * +get_value (tree var, bool may_use_default_p) +{ + prop_value_t *val = &const_val[SSA_NAME_VERSION (var)]; + if (may_use_default_p && val->lattice_val == UNINITIALIZED) + *val = get_default_value (var); + + return val; } + +/* Set the value for variable VAR to NEW_VAL. Return true if the new + value is different from VAR's previous value. */ + static bool -gate_ccp (void) +set_lattice_value (tree var, prop_value_t new_val) { - return flag_tree_ccp != 0; -} + prop_value_t *old_val = get_value (var, false); + + /* Lattice transitions must always be monotonically increasing in + value. We allow two exceptions: + + 1- If *OLD_VAL and NEW_VAL are the same, return false to + inform the caller that this was a non-transition. + + 2- If we are doing store-ccp (i.e., DOING_STORE_CCP is true), + allow CONSTANT->UNKNOWN_VAL. The UNKNOWN_VAL state is a + special type of UNDEFINED state which prevents the short + circuit evaluation of PHI arguments (see ccp_visit_phi_node + and ccp_lattice_meet). */ + gcc_assert (old_val->lattice_val <= new_val.lattice_val + || (old_val->lattice_val == new_val.lattice_val + && old_val->value == new_val.value + && old_val->mem_ref == new_val.mem_ref) + || (do_store_ccp + && old_val->lattice_val == CONSTANT + && new_val.lattice_val == UNKNOWN_VAL)); + + if (old_val->lattice_val != new_val.lattice_val) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + dump_lattice_value (dump_file, "Lattice value changed to ", new_val); + fprintf (dump_file, ". %sdding SSA edges to worklist.\n", + new_val.lattice_val != UNDEFINED ? "A" : "Not a"); + } -struct tree_opt_pass pass_ccp = -{ - "ccp", /* name */ - gate_ccp, /* gate */ - tree_ssa_ccp, /* execute */ - NULL, /* sub */ - NULL, /* next */ - 0, /* static_pass_number */ - TV_TREE_CCP, /* tv_id */ - PROP_cfg | PROP_ssa, /* properties_required */ - 0, /* properties_provided */ - 0, /* properties_destroyed */ - 0, /* todo_flags_start */ - TODO_dump_func | TODO_rename_vars - | TODO_ggc_collect | TODO_verify_ssa - | TODO_verify_stmts /* todo_flags_finish */ -}; + *old_val = new_val; + /* Transitions UNINITIALIZED -> UNDEFINED are never interesting + for propagation purposes. In these cases return false to + avoid doing useless work. */ + return (new_val.lattice_val != UNDEFINED); + } -/* Get the constant value associated with variable VAR. */ + return false; +} -static value * -get_value (tree var) -{ - value *val; -#if defined ENABLE_CHECKING - if (TREE_CODE (var) != SSA_NAME) - abort (); -#endif +/* Return the likely CCP lattice value for STMT. - val = &value_vector[SSA_NAME_VERSION (var)]; - if (val->lattice_val == UNINITIALIZED) - *val = get_default_value (var); + If STMT has no operands, then return CONSTANT. - return val; -} + Else if any operands of STMT are undefined, then return UNDEFINED. + Else if any operands of STMT are constants, then return CONSTANT. -/* Simulate the execution of BLOCK. Evaluate the statement associated - with each variable reference inside the block. */ + Else return VARYING. */ -static void -simulate_block (basic_block block) +static ccp_lattice_t +likely_value (tree stmt) { - tree phi; + bool found_constant; + stmt_ann_t ann; + tree use; + ssa_op_iter iter; - /* There is nothing to do for the exit block. */ - if (block == EXIT_BLOCK_PTR) - return; + ann = stmt_ann (stmt); - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "\nSimulating block %d\n", block->index); + /* If the statement has volatile operands, it won't fold to a + constant value. */ + if (ann->has_volatile_ops) + return VARYING; - /* Always simulate PHI nodes, even if we have simulated this block - before. */ - for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi)) - visit_phi_node (phi); + /* If we are not doing store-ccp, statements with loads + and/or stores will never fold into a constant. */ + if (!do_store_ccp + && (ann->makes_aliased_stores + || ann->makes_aliased_loads + || !ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))) + return VARYING; - /* If this is the first time we've simulated this block, then we - must simulate each of its statements. */ - if (!TEST_BIT (executable_blocks, block->index)) - { - block_stmt_iterator j; - unsigned int normal_edge_count; - edge e, normal_edge; - - /* Note that we have simulated this block. */ - SET_BIT (executable_blocks, block->index); - - for (j = bsi_start (block); !bsi_end_p (j); bsi_next (&j)) - visit_stmt (bsi_stmt (j)); - - /* We can not predict when abnormal edges will be executed, so - once a block is considered executable, we consider any - outgoing abnormal edges as executable. - - At the same time, if this block has only one successor that is - reached by non-abnormal edges, then add that successor to the - worklist. */ - normal_edge_count = 0; - normal_edge = NULL; - for (e = block->succ; e; e = e->succ_next) - { - if (e->flags & EDGE_ABNORMAL) - { - add_control_edge (e); - } - else - { - normal_edge_count++; - normal_edge = e; - } - } - if (normal_edge_count == 1) - add_control_edge (normal_edge); - } -} + /* A CALL_EXPR is assumed to be varying. NOTE: This may be overly + conservative, in the presence of const and pure calls. */ + if (get_call_expr_in (stmt) != NULL_TREE) + return VARYING; + /* Anything other than assignments and conditional jumps are not + interesting for CCP. */ + if (TREE_CODE (stmt) != MODIFY_EXPR + && TREE_CODE (stmt) != COND_EXPR + && TREE_CODE (stmt) != SWITCH_EXPR) + return VARYING; -/* Follow the def-use edges for statement DEF_STMT and simulate all the - statements reached by it. */ + found_constant = false; + FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE|SSA_OP_VUSE) + { + prop_value_t *val = get_value (use, true); -static void -simulate_stmt (tree use_stmt) -{ - basic_block use_bb = bb_for_stmt (use_stmt); + if (val->lattice_val == VARYING) + return VARYING; - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "\nSimulating statement (from ssa_edges): "); - print_generic_stmt (dump_file, use_stmt, dump_flags); - } + if (val->lattice_val == UNKNOWN_VAL) + { + /* UNKNOWN_VAL is invalid when not doing STORE-CCP. */ + gcc_assert (do_store_ccp); + return UNKNOWN_VAL; + } - if (TREE_CODE (use_stmt) == PHI_NODE) - { - /* PHI nodes are always visited, regardless of whether or not the - destination block is executable. */ - visit_phi_node (use_stmt); - } - else if (TEST_BIT (executable_blocks, use_bb->index)) - { - /* Otherwise, visit the statement containing the use reached by - DEF, only if the destination block is marked executable. */ - visit_stmt (use_stmt); + if (val->lattice_val == CONSTANT) + found_constant = true; } + + if (found_constant + || ZERO_SSA_OPERANDS (stmt, SSA_OP_USE) + || ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE)) + return CONSTANT; + + return UNDEFINED; } -/* Perform final substitution and folding. After this pass the program - should still be in SSA form. */ +/* Initialize local data structures for CCP. */ static void -substitute_and_fold (void) +ccp_initialize (void) { basic_block bb; - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, - "\nSubstituing constants and folding statements\n\n"); + const_val = xmalloc (num_ssa_names * sizeof (*const_val)); + memset (const_val, 0, num_ssa_names * sizeof (*const_val)); - /* Substitute constants in every statement of every basic block. */ + /* Initialize simulation flags for PHI nodes and statements. */ FOR_EACH_BB (bb) { block_stmt_iterator i; - tree phi; - - /* Propagate our known constants into PHI nodes. */ - for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) - { - int i; - for (i = 0; i < PHI_NUM_ARGS (phi); i++) - { - value *new_val; - use_operand_p orig_p = PHI_ARG_DEF_PTR (phi, i); - tree orig = USE_FROM_PTR (orig_p); + for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i)) + { + bool is_varying = false; + tree stmt = bsi_stmt (i); - if (! SSA_VAR_P (orig)) - break; + if (likely_value (stmt) == VARYING) - new_val = get_value (orig); - if (new_val->lattice_val == CONSTANT - && may_propagate_copy (orig, new_val->const_val)) - SET_USE (orig_p, new_val->const_val); + { + tree def; + ssa_op_iter iter; + + /* If the statement will not produce a constant, mark + all its outputs VARYING. */ + FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) + get_value (def, false)->lattice_val = VARYING; + + /* Never mark conditional jumps with DONT_SIMULATE_AGAIN, + otherwise the propagator will never add the outgoing + control edges. */ + if (TREE_CODE (stmt) != COND_EXPR + && TREE_CODE (stmt) != SWITCH_EXPR) + is_varying = true; } + + DONT_SIMULATE_AGAIN (stmt) = is_varying; } + } - for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i)) - { - bool replaced_address; - tree stmt = bsi_stmt (i); + /* Now process PHI nodes. */ + FOR_EACH_BB (bb) + { + tree phi; - /* Skip statements that have been folded already. */ - if (stmt_modified_p (stmt) || !is_exec_stmt (stmt)) - continue; + for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) + { + int i; + tree arg; + prop_value_t *val = get_value (PHI_RESULT (phi), false); - /* Replace the statement with its folded version and mark it - folded. */ - if (dump_file && (dump_flags & TDF_DETAILS)) + for (i = 0; i < PHI_NUM_ARGS (phi); i++) { - fprintf (dump_file, "Line %d: replaced ", get_lineno (stmt)); - print_generic_stmt (dump_file, stmt, TDF_SLIM); - } + arg = PHI_ARG_DEF (phi, i); - if (replace_uses_in (stmt, &replaced_address)) - { - bool changed = fold_stmt (bsi_stmt_ptr (i)); - stmt = bsi_stmt(i); - modify_stmt (stmt); - /* If we folded a builtin function, we'll likely - need to rename VDEFs. */ - if (replaced_address || changed) + if (TREE_CODE (arg) == SSA_NAME + && get_value (arg, false)->lattice_val == VARYING) { - mark_new_vars_to_rename (stmt, vars_to_rename); - if (maybe_clean_eh_stmt (stmt)) - tree_purge_dead_eh_edges (bb); + val->lattice_val = VARYING; + break; } } - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, " with "); - print_generic_stmt (dump_file, stmt, TDF_SLIM); - fprintf (dump_file, "\n"); - } + DONT_SIMULATE_AGAIN (phi) = (val->lattice_val == VARYING); } } } -/* Loop through the PHI_NODE's parameters for BLOCK and compare their - lattice values to determine PHI_NODE's lattice value. The value of a - PHI node is determined calling cp_lattice_meet() with all the arguments - of the PHI node that are incoming via executable edges. */ +/* Do final substitution of propagated values, cleanup the flowgraph and + free allocated storage. */ static void -visit_phi_node (tree phi) +ccp_finalize (void) { - bool short_circuit = 0; - value phi_val, *curr_val; - int i; - - /* If the PHI node has already been deemed to be VARYING, don't simulate - it again. */ - if (DONT_SIMULATE_AGAIN (phi)) - return; - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "\nVisiting PHI node: "); - print_generic_expr (dump_file, phi, dump_flags); - } - - curr_val = get_value (PHI_RESULT (phi)); - switch (curr_val->lattice_val) - { - case VARYING: - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "\n Shortcircuit. Default of VARYING."); - short_circuit = 1; - break; + /* Perform substitutions based on the known constant values. */ + substitute_and_fold (const_val, false); - case CONSTANT: - phi_val = *curr_val; - break; + free (const_val); +} - case UNDEFINED: - case UNINITIALIZED: - phi_val.lattice_val = UNDEFINED; - phi_val.const_val = NULL_TREE; - break; - default: - abort (); - } +/* Compute the meet operator between *VAL1 and *VAL2. Store the result + in VAL1. + + any M UNDEFINED = any + any M UNKNOWN_VAL = UNKNOWN_VAL + any M VARYING = VARYING + Ci M Cj = Ci if (i == j) + Ci M Cj = VARYING if (i != j) + + Lattice values UNKNOWN_VAL and UNDEFINED are similar but have + different semantics at PHI nodes. Both values imply that we don't + know whether the variable is constant or not. However, UNKNOWN_VAL + values override all others. For instance, suppose that A is a + global variable: + + +------+ + | | + | / \ + | / \ + | | A_1 = 4 + | \ / + | \ / + | A_3 = PHI (A_2, A_1) + | ... = A_3 + | | + +----+ + + If the edge into A_2 is not executable, the first visit to A_3 will + yield the constant 4. But the second visit to A_3 will be with A_2 + in state UNKNOWN_VAL. We can no longer conclude that A_3 is 4 + because A_2 may have been set in another function. If we had used + the lattice value UNDEFINED, we would have had wrongly concluded + that A_3 is 4. */ + - /* If the variable is volatile or the variable is never referenced in a - real operand, then consider the PHI node VARYING. */ - if (short_circuit || TREE_THIS_VOLATILE (SSA_NAME_VAR (PHI_RESULT (phi)))) +static void +ccp_lattice_meet (prop_value_t *val1, prop_value_t *val2) +{ + if (val1->lattice_val == UNDEFINED) { - phi_val.lattice_val = VARYING; - phi_val.const_val = NULL; + /* UNDEFINED M any = any */ + *val1 = *val2; } - else - for (i = 0; i < PHI_NUM_ARGS (phi); i++) - { - /* Compute the meet operator over all the PHI arguments. */ - edge e = PHI_ARG_EDGE (phi, i); - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, - "\n Argument #%d (%d -> %d %sexecutable)\n", - i, e->src->index, e->dest->index, - (e->flags & EDGE_EXECUTABLE) ? "" : "not "); - } - - /* If the incoming edge is executable, Compute the meet operator for - the existing value of the PHI node and the current PHI argument. */ - if (e->flags & EDGE_EXECUTABLE) - { - tree rdef = PHI_ARG_DEF (phi, i); - value *rdef_val, val; - - if (is_gimple_min_invariant (rdef)) - { - val.lattice_val = CONSTANT; - val.const_val = rdef; - rdef_val = &val; - } - else - rdef_val = get_value (rdef); - - phi_val = cp_lattice_meet (phi_val, *rdef_val); - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "\t"); - print_generic_expr (dump_file, rdef, dump_flags); - dump_lattice_value (dump_file, "\tValue: ", *rdef_val); - fprintf (dump_file, "\n"); - } - - if (phi_val.lattice_val == VARYING) - break; - } - } - - if (dump_file && (dump_flags & TDF_DETAILS)) + else if (val2->lattice_val == UNDEFINED) { - dump_lattice_value (dump_file, "\n PHI node value: ", phi_val); - fprintf (dump_file, "\n\n"); + /* any M UNDEFINED = any + Nothing to do. VAL1 already contains the value we want. */ + ; } + else if (val1->lattice_val == UNKNOWN_VAL + || val2->lattice_val == UNKNOWN_VAL) + { + /* UNKNOWN_VAL values are invalid if we are not doing STORE-CCP. */ + gcc_assert (do_store_ccp); - set_lattice_value (PHI_RESULT (phi), phi_val); - if (phi_val.lattice_val == VARYING) - DONT_SIMULATE_AGAIN (phi) = 1; -} - - -/* Compute the meet operator between VAL1 and VAL2: - - any M UNDEFINED = any - any M VARYING = VARYING - Ci M Cj = Ci if (i == j) - Ci M Cj = VARYING if (i != j) */ -static value -cp_lattice_meet (value val1, value val2) -{ - value result; - - /* any M UNDEFINED = any. */ - if (val1.lattice_val == UNDEFINED) - return val2; - else if (val2.lattice_val == UNDEFINED) - return val1; - - /* any M VARYING = VARYING. */ - if (val1.lattice_val == VARYING || val2.lattice_val == VARYING) + /* any M UNKNOWN_VAL = UNKNOWN_VAL. */ + val1->lattice_val = UNKNOWN_VAL; + val1->value = NULL_TREE; + val1->mem_ref = NULL_TREE; + } + else if (val1->lattice_val == VARYING + || val2->lattice_val == VARYING) { - result.lattice_val = VARYING; - result.const_val = NULL_TREE; - return result; + /* any M VARYING = VARYING. */ + val1->lattice_val = VARYING; + val1->value = NULL_TREE; + val1->mem_ref = NULL_TREE; } - - /* Ci M Cj = Ci if (i == j) - Ci M Cj = VARYING if (i != j) */ - if (simple_cst_equal (val1.const_val, val2.const_val) == 1) + else if (val1->lattice_val == CONSTANT + && val2->lattice_val == CONSTANT + && simple_cst_equal (val1->value, val2->value) == 1 + && (!do_store_ccp + || simple_cst_equal (val1->mem_ref, val2->mem_ref) == 1)) { - result.lattice_val = CONSTANT; - result.const_val = val1.const_val; + /* Ci M Cj = Ci if (i == j) + Ci M Cj = VARYING if (i != j) + + If these two values come from memory stores, make sure that + they come from the same memory reference. */ + val1->lattice_val = CONSTANT; + val1->value = val1->value; + val1->mem_ref = val1->mem_ref; } else { - result.lattice_val = VARYING; - result.const_val = NULL_TREE; + /* Any other combination is VARYING. */ + val1->lattice_val = VARYING; + val1->value = NULL_TREE; + val1->mem_ref = NULL_TREE; } - - return result; } -/* Evaluate statement STMT. If the statement produces an output value and - its evaluation changes the lattice value of its output, do the following: - - - If the statement is an assignment, add all the SSA edges starting at - this definition. - - - If the statement is a conditional branch: - . If the statement evaluates to non-constant, add all edges to - worklist. - . If the statement is constant, add the edge executed as the - result of the branch. */ +/* Loop through the PHI_NODE's parameters for BLOCK and compare their + lattice values to determine PHI_NODE's lattice value. The value of a + PHI node is determined calling ccp_lattice_meet with all the arguments + of the PHI node that are incoming via executable edges. */ -static void -visit_stmt (tree stmt) +static enum ssa_prop_result +ccp_visit_phi_node (tree phi) { - size_t i; - stmt_ann_t ann; - def_optype defs; - v_may_def_optype v_may_defs; - v_must_def_optype v_must_defs; - - /* If the statement has already been deemed to be VARYING, don't simulate - it again. */ - if (DONT_SIMULATE_AGAIN (stmt)) - return; + int i; + prop_value_t *old_val, new_val; if (dump_file && (dump_flags & TDF_DETAILS)) { - fprintf (dump_file, "\nVisiting statement: "); - print_generic_stmt (dump_file, stmt, TDF_SLIM); - fprintf (dump_file, "\n"); - } - - ann = stmt_ann (stmt); - - /* If this statement is already in the worklist then "cancel" it. The - reevaluation implied by the worklist entry will produce the same - value we generate here and thus reevaluating it again from the - worklist is pointless. */ - if (ann->in_ccp_worklist) - ann->in_ccp_worklist = 0; - - /* Now examine the statement. If the statement is an assignment that - produces a single output value, evaluate its RHS to see if the lattice - value of its output has changed. */ - if (TREE_CODE (stmt) == MODIFY_EXPR - && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME) - visit_assignment (stmt); - - /* Definitions made by statements other than assignments to SSA_NAMEs - represent unknown modifications to their outputs. Mark them VARYING. */ - else if (NUM_DEFS (defs = DEF_OPS (ann)) != 0) - { - DONT_SIMULATE_AGAIN (stmt) = 1; - for (i = 0; i < NUM_DEFS (defs); i++) - { - tree def = DEF_OP (defs, i); - def_to_varying (def); - } + fprintf (dump_file, "\nVisiting PHI node: "); + print_generic_expr (dump_file, phi, dump_flags); } - /* If STMT is a conditional branch, see if we can determine which branch - will be taken. */ - else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR) - visit_cond_stmt (stmt); - - /* Any other kind of statement is not interesting for constant - propagation and, therefore, not worth simulating. */ - else + old_val = get_value (PHI_RESULT (phi), false); + switch (old_val->lattice_val) { - DONT_SIMULATE_AGAIN (stmt) = 1; - - /* If STMT is a computed goto, then mark all the output edges - executable. */ - if (computed_goto_p (stmt)) - add_outgoing_control_edges (bb_for_stmt (stmt)); - } - - /* Mark all V_MAY_DEF operands VARYING. */ - v_may_defs = V_MAY_DEF_OPS (ann); - for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++) - def_to_varying (V_MAY_DEF_RESULT (v_may_defs, i)); - - /* Mark all V_MUST_DEF operands VARYING. */ - v_must_defs = V_MUST_DEF_OPS (ann); - for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++) - def_to_varying (V_MUST_DEF_OP (v_must_defs, i)); -} + case VARYING: + return SSA_PROP_VARYING; + case CONSTANT: + new_val = *old_val; + break; -/* Visit the assignment statement STMT. Set the value of its LHS to the - value computed by the RHS. */ + case UNKNOWN_VAL: + /* To avoid the default value of UNKNOWN_VAL overriding + that of its possible constant arguments, temporarily + set the PHI node's default lattice value to be + UNDEFINED. If the PHI node's old value was UNKNOWN_VAL and + the new value is UNDEFINED, then we prevent the invalid + transition by not calling set_lattice_value. */ + gcc_assert (do_store_ccp); -static void -visit_assignment (tree stmt) -{ - value val; - tree lhs, rhs; + /* FALLTHRU */ - lhs = TREE_OPERAND (stmt, 0); - rhs = TREE_OPERAND (stmt, 1); + case UNDEFINED: + case UNINITIALIZED: + new_val.lattice_val = UNDEFINED; + new_val.value = NULL_TREE; + new_val.mem_ref = NULL_TREE; + break; - if (TREE_THIS_VOLATILE (SSA_NAME_VAR (lhs))) - { - /* Volatile variables are always VARYING. */ - val.lattice_val = VARYING; - val.const_val = NULL_TREE; - } - else if (TREE_CODE (rhs) == SSA_NAME) - { - /* For a simple copy operation, we copy the lattice values. */ - value *nval = get_value (rhs); - val = *nval; - } - else - { - /* Evaluate the statement. */ - val = evaluate_stmt (stmt); + default: + gcc_unreachable (); } - /* FIXME: Hack. If this was a definition of a bitfield, we need to widen - the constant value into the type of the destination variable. This - should not be necessary if GCC represented bitfields properly. */ - { - tree lhs = TREE_OPERAND (stmt, 0); - if (val.lattice_val == CONSTANT - && TREE_CODE (lhs) == COMPONENT_REF - && DECL_BIT_FIELD (TREE_OPERAND (lhs, 1))) - { - tree w = widen_bitfield (val.const_val, TREE_OPERAND (lhs, 1), lhs); + for (i = 0; i < PHI_NUM_ARGS (phi); i++) + { + /* Compute the meet operator over all the PHI arguments flowing + through executable edges. */ + edge e = PHI_ARG_EDGE (phi, i); - if (w && is_gimple_min_invariant (w)) - val.const_val = w; - else - { - val.lattice_val = VARYING; - val.const_val = NULL; - } - } - } + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, + "\n Argument #%d (%d -> %d %sexecutable)\n", + i, e->src->index, e->dest->index, + (e->flags & EDGE_EXECUTABLE) ? "" : "not "); + } - /* Set the lattice value of the statement's output. */ - set_lattice_value (lhs, val); - if (val.lattice_val == VARYING) - DONT_SIMULATE_AGAIN (stmt) = 1; -} + /* If the incoming edge is executable, Compute the meet operator for + the existing value of the PHI node and the current PHI argument. */ + if (e->flags & EDGE_EXECUTABLE) + { + tree arg = PHI_ARG_DEF (phi, i); + prop_value_t arg_val; + if (is_gimple_min_invariant (arg)) + { + arg_val.lattice_val = CONSTANT; + arg_val.value = arg; + arg_val.mem_ref = NULL_TREE; + } + else + arg_val = *(get_value (arg, true)); -/* Visit the conditional statement STMT. If it evaluates to a constant value, - mark outgoing edges appropriately. */ + ccp_lattice_meet (&new_val, &arg_val); -static void -visit_cond_stmt (tree stmt) -{ - edge e; - value val; - basic_block block; + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "\t"); + print_generic_expr (dump_file, arg, dump_flags); + dump_lattice_value (dump_file, "\tValue: ", arg_val); + fprintf (dump_file, "\n"); + } - block = bb_for_stmt (stmt); - val = evaluate_stmt (stmt); + if (new_val.lattice_val == VARYING) + break; + } + } - /* Find which edge out of the conditional block will be taken and add it - to the worklist. If no single edge can be determined statically, add - all outgoing edges from BLOCK. */ - e = find_taken_edge (block, val.const_val); - if (e) - add_control_edge (e); - else + if (dump_file && (dump_flags & TDF_DETAILS)) { - DONT_SIMULATE_AGAIN (stmt) = 1; - add_outgoing_control_edges (block); + dump_lattice_value (dump_file, "\n PHI node value: ", new_val); + fprintf (dump_file, "\n\n"); } -} - - -/* Add all the edges coming out of BB to the control flow worklist. */ - -static void -add_outgoing_control_edges (basic_block bb) -{ - edge e; - - for (e = bb->succ; e; e = e->succ_next) - add_control_edge (e); -} + /* Check for an invalid change from UNKNOWN_VAL to UNDEFINED. */ + if (do_store_ccp + && old_val->lattice_val == UNKNOWN_VAL + && new_val.lattice_val == UNDEFINED) + return SSA_PROP_NOT_INTERESTING; -/* Add edge E to the control flow worklist. */ - -static void -add_control_edge (edge e) -{ - basic_block bb = e->dest; - if (bb == EXIT_BLOCK_PTR) - return; - - /* If the edge had already been executed, skip it. */ - if (e->flags & EDGE_EXECUTABLE) - return; - - e->flags |= EDGE_EXECUTABLE; - - /* If the block is already in the list, we're done. */ - if (TEST_BIT (bb_in_list, bb->index)) - return; - - cfg_blocks_add (bb); - - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "Adding Destination of edge (%d -> %d) to worklist\n\n", - e->src->index, e->dest->index); + /* Otherwise, make the transition to the new value. */ + if (set_lattice_value (PHI_RESULT (phi), new_val)) + { + if (new_val.lattice_val == VARYING) + return SSA_PROP_VARYING; + else + return SSA_PROP_INTERESTING; + } + else + return SSA_PROP_NOT_INTERESTING; } -/* CCP specific front-end to the non-destructive constant folding routines. +/* CCP specific front-end to the non-destructive constant folding + routines. Attempt to simplify the RHS of STMT knowing that one or more operands are constants. @@ -825,18 +812,30 @@ ccp_fold (tree stmt) { tree rhs = get_rhs (stmt); enum tree_code code = TREE_CODE (rhs); - int kind = TREE_CODE_CLASS (code); + enum tree_code_class kind = TREE_CODE_CLASS (code); tree retval = NULL_TREE; - /* If the RHS is just a variable, then that variable must now have - a constant value that we can return directly. */ if (TREE_CODE (rhs) == SSA_NAME) - return get_value (rhs)->const_val; + { + /* If the RHS is an SSA_NAME, return its known constant value, + if any. */ + return get_value (rhs, true)->value; + } + else if (do_store_ccp && stmt_makes_single_load (stmt)) + { + /* If the RHS is a memory load, see if the VUSEs associated with + it are a valid constant for that memory load. */ + prop_value_t *val = get_value_loaded_by (stmt, const_val); + if (val && simple_cst_equal (val->mem_ref, rhs) == 1) + return val->value; + else + return NULL_TREE; + } /* Unary operators. Note that we know the single operand must be a constant. So this should almost always return a simplified RHS. */ - if (kind == '1') + if (kind == tcc_unary) { /* Handle unary operators which can appear in GIMPLE form. */ tree op0 = TREE_OPERAND (rhs, 0); @@ -844,40 +843,18 @@ ccp_fold (tree stmt) /* Simplify the operand down to a constant. */ if (TREE_CODE (op0) == SSA_NAME) { - value *val = get_value (op0); + prop_value_t *val = get_value (op0, true); if (val->lattice_val == CONSTANT) - op0 = get_value (op0)->const_val; + op0 = get_value (op0, true)->value; } - retval = nondestructive_fold_unary_to_constant (code, - TREE_TYPE (rhs), - op0); - - /* If we folded, but did not create an invariant, then we can not - use this expression. */ - if (retval && ! is_gimple_min_invariant (retval)) - return NULL; - - /* If we could not fold the expression, but the arguments are all - constants and gimple values, then build and return the new - expression. - - In some cases the new expression is still something we can - use as a replacement for an argument. This happens with - NOP conversions of types for example. - - In other cases the new expression can not be used as a - replacement for an argument (as it would create non-gimple - code). But the new expression can still be used to derive - other constants. */ - if (! retval && is_gimple_min_invariant (op0)) - return build1 (code, TREE_TYPE (rhs), op0); + return fold_unary (code, TREE_TYPE (rhs), op0); } /* Binary and comparison operators. We know one or both of the operands are constants. */ - else if (kind == '2' - || kind == '<' + else if (kind == tcc_binary + || kind == tcc_comparison || code == TRUTH_AND_EXPR || code == TRUTH_OR_EXPR || code == TRUTH_XOR_EXPR) @@ -890,43 +867,19 @@ ccp_fold (tree stmt) /* Simplify the operands down to constants when appropriate. */ if (TREE_CODE (op0) == SSA_NAME) { - value *val = get_value (op0); + prop_value_t *val = get_value (op0, true); if (val->lattice_val == CONSTANT) - op0 = val->const_val; + op0 = val->value; } if (TREE_CODE (op1) == SSA_NAME) { - value *val = get_value (op1); + prop_value_t *val = get_value (op1, true); if (val->lattice_val == CONSTANT) - op1 = val->const_val; + op1 = val->value; } - retval = nondestructive_fold_binary_to_constant (code, - TREE_TYPE (rhs), - op0, op1); - - /* If we folded, but did not create an invariant, then we can not - use this expression. */ - if (retval && ! is_gimple_min_invariant (retval)) - return NULL; - - /* If we could not fold the expression, but the arguments are all - constants and gimple values, then build and return the new - expression. - - In some cases the new expression is still something we can - use as a replacement for an argument. This happens with - NOP conversions of types for example. - - In other cases the new expression can not be used as a - replacement for an argument (as it would create non-gimple - code). But the new expression can still be used to derive - other constants. */ - if (! retval - && is_gimple_min_invariant (op0) - && is_gimple_min_invariant (op1)) - return build (code, TREE_TYPE (rhs), op0, op1); + return fold_binary (code, TREE_TYPE (rhs), op0, op1); } /* We may be able to fold away calls to builtin functions if their @@ -937,24 +890,29 @@ ccp_fold (tree stmt) == FUNCTION_DECL) && DECL_BUILT_IN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0))) { - use_optype uses = STMT_USE_OPS (stmt); - if (NUM_USES (uses) != 0) + if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_USE)) { - tree *orig; - size_t i; + tree *orig, var; + tree fndecl, arglist; + size_t i = 0; + ssa_op_iter iter; + use_operand_p var_p; /* Preserve the original values of every operand. */ - orig = xmalloc (sizeof (tree) * NUM_USES (uses)); - for (i = 0; i < NUM_USES (uses); i++) - orig[i] = USE_OP (uses, i); + orig = xmalloc (sizeof (tree) * NUM_SSA_OPERANDS (stmt, SSA_OP_USE)); + FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE) + orig[i++] = var; /* Substitute operands with their values and try to fold. */ - replace_uses_in (stmt, NULL); - retval = fold_builtin (rhs); + replace_uses_in (stmt, NULL, const_val); + fndecl = get_callee_fndecl (rhs); + arglist = TREE_OPERAND (rhs, 1); + retval = fold_builtin (fndecl, arglist, false); /* Restore operands to their original form. */ - for (i = 0; i < NUM_USES (uses); i++) - SET_USE_OP (uses, i, orig[i]); + i = 0; + FOR_EACH_SSA_USE_OPERAND (var_p, stmt, iter, SSA_OP_USE) + SET_USE (var_p, orig[i++]); free (orig); } } @@ -963,27 +921,144 @@ ccp_fold (tree stmt) /* If we got a simplified form, see if we need to convert its type. */ if (retval) - { - if (TREE_TYPE (retval) != TREE_TYPE (rhs)) - retval = fold_convert (TREE_TYPE (rhs), retval); - - if (TREE_TYPE (retval) == TREE_TYPE (rhs)) - return retval; - } + return fold_convert (TREE_TYPE (rhs), retval); /* No simplification was possible. */ return rhs; } +/* Return the tree representing the element referenced by T if T is an + ARRAY_REF or COMPONENT_REF into constant aggregates. Return + NULL_TREE otherwise. */ + +static tree +fold_const_aggregate_ref (tree t) +{ + prop_value_t *value; + tree base, ctor, idx, field, elt; + + switch (TREE_CODE (t)) + { + case ARRAY_REF: + /* Get a CONSTRUCTOR. If BASE is a VAR_DECL, get its + DECL_INITIAL. If BASE is a nested reference into another + ARRAY_REF or COMPONENT_REF, make a recursive call to resolve + the inner reference. */ + base = TREE_OPERAND (t, 0); + switch (TREE_CODE (base)) + { + case VAR_DECL: + if (!TREE_READONLY (base) + || TREE_CODE (TREE_TYPE (base)) != ARRAY_TYPE + || !targetm.binds_local_p (base)) + return NULL_TREE; + + ctor = DECL_INITIAL (base); + break; + + case ARRAY_REF: + case COMPONENT_REF: + ctor = fold_const_aggregate_ref (base); + break; + + default: + return NULL_TREE; + } + + if (ctor == NULL_TREE + || TREE_CODE (ctor) != CONSTRUCTOR + || !TREE_STATIC (ctor)) + return NULL_TREE; + + /* Get the index. If we have an SSA_NAME, try to resolve it + with the current lattice value for the SSA_NAME. */ + idx = TREE_OPERAND (t, 1); + switch (TREE_CODE (idx)) + { + case SSA_NAME: + if ((value = get_value (idx, true)) + && value->lattice_val == CONSTANT + && TREE_CODE (value->value) == INTEGER_CST) + idx = value->value; + else + return NULL_TREE; + break; + + case INTEGER_CST: + break; + + default: + return NULL_TREE; + } + + /* Whoo-hoo! I'll fold ya baby. Yeah! */ + for (elt = CONSTRUCTOR_ELTS (ctor); + (elt && !tree_int_cst_equal (TREE_PURPOSE (elt), idx)); + elt = TREE_CHAIN (elt)) + ; + + if (elt) + return TREE_VALUE (elt); + break; + + case COMPONENT_REF: + /* Get a CONSTRUCTOR. If BASE is a VAR_DECL, get its + DECL_INITIAL. If BASE is a nested reference into another + ARRAY_REF or COMPONENT_REF, make a recursive call to resolve + the inner reference. */ + base = TREE_OPERAND (t, 0); + switch (TREE_CODE (base)) + { + case VAR_DECL: + if (!TREE_READONLY (base) + || TREE_CODE (TREE_TYPE (base)) != RECORD_TYPE + || !targetm.binds_local_p (base)) + return NULL_TREE; + + ctor = DECL_INITIAL (base); + break; + + case ARRAY_REF: + case COMPONENT_REF: + ctor = fold_const_aggregate_ref (base); + break; + + default: + return NULL_TREE; + } + + if (ctor == NULL_TREE + || TREE_CODE (ctor) != CONSTRUCTOR + || !TREE_STATIC (ctor)) + return NULL_TREE; + + field = TREE_OPERAND (t, 1); + + for (elt = CONSTRUCTOR_ELTS (ctor); elt; elt = TREE_CHAIN (elt)) + if (TREE_PURPOSE (elt) == field + /* FIXME: Handle bit-fields. */ + && ! DECL_BIT_FIELD (TREE_PURPOSE (elt))) + return TREE_VALUE (elt); + break; + + default: + break; + } + + return NULL_TREE; +} + /* Evaluate statement STMT. */ -static value +static prop_value_t evaluate_stmt (tree stmt) { - value val; + prop_value_t val; tree simplified; - latticevalue likelyvalue = likely_value (stmt); + ccp_lattice_t likelyvalue = likely_value (stmt); + + val.mem_ref = NULL_TREE; /* If the statement is likely to have a CONSTANT result, then try to fold the statement to determine the constant value. */ @@ -993,507 +1068,391 @@ evaluate_stmt (tree stmt) bother folding the statement. */ else if (likelyvalue == VARYING) simplified = get_rhs (stmt); - /* Otherwise the statement is likely to have an UNDEFINED value and - there will be nothing to do. */ + /* If the statement is an ARRAY_REF or COMPONENT_REF into constant + aggregates, extract the referenced constant. Otherwise the + statement is likely to have an UNDEFINED value, and there will be + nothing to do. Note that fold_const_aggregate_ref returns + NULL_TREE if the first case does not match. */ else - simplified = NULL_TREE; + simplified = fold_const_aggregate_ref (get_rhs (stmt)); if (simplified && is_gimple_min_invariant (simplified)) { /* The statement produced a constant value. */ val.lattice_val = CONSTANT; - val.const_val = simplified; + val.value = simplified; } else { /* The statement produced a nonconstant value. If the statement - had undefined operands, then the result of the statement should - be undefined. Else the result of the statement is VARYING. */ - val.lattice_val = (likelyvalue == UNDEFINED ? UNDEFINED : VARYING); - val.const_val = NULL_TREE; + had UNDEFINED operands, then the result of the statement + should be UNDEFINED. Otherwise, the statement is VARYING. */ + val.lattice_val = (likelyvalue == UNDEFINED) ? UNDEFINED : VARYING; + val.value = NULL_TREE; } return val; } -/* Debugging dumps. */ - -static void -dump_lattice_value (FILE *outf, const char *prefix, value val) -{ - switch (val.lattice_val) - { - case UNDEFINED: - fprintf (outf, "%sUNDEFINED", prefix); - break; - case VARYING: - fprintf (outf, "%sVARYING", prefix); - break; - case CONSTANT: - fprintf (outf, "%sCONSTANT ", prefix); - print_generic_expr (outf, val.const_val, dump_flags); - break; - default: - abort (); - } -} - -/* Given a constant value VAL for bitfield FIELD, and a destination - variable VAR, return VAL appropriately widened to fit into VAR. If - FIELD is wider than HOST_WIDE_INT, NULL is returned. */ +/* Visit the assignment statement STMT. Set the value of its LHS to the + value computed by the RHS and store LHS in *OUTPUT_P. If STMT + creates virtual definitions, set the value of each new name to that + of the RHS (if we can derive a constant out of the RHS). */ -tree -widen_bitfield (tree val, tree field, tree var) +static enum ssa_prop_result +visit_assignment (tree stmt, tree *output_p) { - unsigned HOST_WIDE_INT var_size, field_size; - tree wide_val; - unsigned HOST_WIDE_INT mask; - unsigned int i; - - /* We can only do this if the size of the type and field and VAL are - all constants representable in HOST_WIDE_INT. */ - if (!host_integerp (TYPE_SIZE (TREE_TYPE (var)), 1) - || !host_integerp (DECL_SIZE (field), 1) - || !host_integerp (val, 0)) - return NULL_TREE; - - var_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (var)), 1); - field_size = tree_low_cst (DECL_SIZE (field), 1); - - /* Give up if either the bitfield or the variable are too wide. */ - if (field_size > HOST_BITS_PER_WIDE_INT || var_size > HOST_BITS_PER_WIDE_INT) - return NULL_TREE; + prop_value_t val; + tree lhs, rhs; + enum ssa_prop_result retval; -#if defined ENABLE_CHECKING - if (var_size < field_size) - abort (); -#endif + lhs = TREE_OPERAND (stmt, 0); + rhs = TREE_OPERAND (stmt, 1); - /* If the sign bit of the value is not set or the field's type is unsigned, - just mask off the high order bits of the value. */ - if (DECL_UNSIGNED (field) - || !(tree_low_cst (val, 0) & (((HOST_WIDE_INT)1) << (field_size - 1)))) + if (TREE_CODE (rhs) == SSA_NAME) { - /* Zero extension. Build a mask with the lower 'field_size' bits - set and a BIT_AND_EXPR node to clear the high order bits of - the value. */ - for (i = 0, mask = 0; i < field_size; i++) - mask |= ((HOST_WIDE_INT) 1) << i; - - wide_val = build (BIT_AND_EXPR, TREE_TYPE (var), val, - fold_convert (TREE_TYPE (var), build_int_2 (mask, 0))); + /* For a simple copy operation, we copy the lattice values. */ + prop_value_t *nval = get_value (rhs, true); + val = *nval; } - else + else if (do_store_ccp && stmt_makes_single_load (stmt)) { - /* Sign extension. Create a mask with the upper 'field_size' - bits set and a BIT_IOR_EXPR to set the high order bits of the - value. */ - for (i = 0, mask = 0; i < (var_size - field_size); i++) - mask |= ((HOST_WIDE_INT) 1) << (var_size - i - 1); + /* Same as above, but the RHS is not a gimple register and yet + has a known VUSE. If STMT is loading from the same memory + location that created the SSA_NAMEs for the virtual operands, + we can propagate the value on the RHS. */ + prop_value_t *nval = get_value_loaded_by (stmt, const_val); - wide_val = build (BIT_IOR_EXPR, TREE_TYPE (var), val, - fold_convert (TREE_TYPE (var), build_int_2 (mask, 0))); + if (nval && simple_cst_equal (nval->mem_ref, rhs) == 1) + val = *nval; + else + val = evaluate_stmt (stmt); } + else + /* Evaluate the statement. */ + val = evaluate_stmt (stmt); - return fold (wide_val); -} - - -/* Function indicating whether we ought to include information for 'var' - when calculating immediate uses. */ - -static bool -need_imm_uses_for (tree var) -{ - return get_value (var)->lattice_val != VARYING; -} - - -/* Initialize local data structures and worklists for CCP. */ + /* If the original LHS was a VIEW_CONVERT_EXPR, modify the constant + value to be a VIEW_CONVERT_EXPR of the old constant value. -static void -initialize (void) -{ - edge e; - basic_block bb; - sbitmap virtual_var; + ??? Also, if this was a definition of a bitfield, we need to widen + the constant value into the type of the destination variable. This + should not be necessary if GCC represented bitfields properly. */ + { + tree orig_lhs = TREE_OPERAND (stmt, 0); - /* Worklists of SSA edges. */ - VARRAY_TREE_INIT (ssa_edges, 20, "ssa_edges"); - VARRAY_TREE_INIT (varying_ssa_edges, 20, "varying_ssa_edges"); + if (TREE_CODE (orig_lhs) == VIEW_CONVERT_EXPR + && val.lattice_val == CONSTANT) + { + tree w = fold (build1 (VIEW_CONVERT_EXPR, + TREE_TYPE (TREE_OPERAND (orig_lhs, 0)), + val.value)); - executable_blocks = sbitmap_alloc (last_basic_block); - sbitmap_zero (executable_blocks); + orig_lhs = TREE_OPERAND (orig_lhs, 0); + if (w && is_gimple_min_invariant (w)) + val.value = w; + else + { + val.lattice_val = VARYING; + val.value = NULL; + } + } - bb_in_list = sbitmap_alloc (last_basic_block); - sbitmap_zero (bb_in_list); + if (val.lattice_val == CONSTANT + && TREE_CODE (orig_lhs) == COMPONENT_REF + && DECL_BIT_FIELD (TREE_OPERAND (orig_lhs, 1))) + { + tree w = widen_bitfield (val.value, TREE_OPERAND (orig_lhs, 1), + orig_lhs); - value_vector = (value *) xmalloc (num_ssa_names * sizeof (value)); - memset (value_vector, 0, num_ssa_names * sizeof (value)); + if (w && is_gimple_min_invariant (w)) + val.value = w; + else + { + val.lattice_val = VARYING; + val.value = NULL_TREE; + val.mem_ref = NULL_TREE; + } + } + } - /* 1 if ssa variable is used in a virtual variable context. */ - virtual_var = sbitmap_alloc (num_ssa_names); - sbitmap_zero (virtual_var); + retval = SSA_PROP_NOT_INTERESTING; - /* Initialize default values and simulation flags for PHI nodes, statements - and edges. */ - FOR_EACH_BB (bb) + /* Set the lattice value of the statement's output. */ + if (TREE_CODE (lhs) == SSA_NAME) { - block_stmt_iterator i; - tree stmt; - stmt_ann_t ann; - def_optype defs; - v_may_def_optype v_may_defs; - v_must_def_optype v_must_defs; - size_t x; - int vary; - - /* Get the default value for each definition. */ - for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i)) - { - vary = 0; - stmt = bsi_stmt (i); - get_stmt_operands (stmt); - ann = stmt_ann (stmt); - defs = DEF_OPS (ann); - for (x = 0; x < NUM_DEFS (defs); x++) - { - tree def = DEF_OP (defs, x); - if (get_value (def)->lattice_val == VARYING) - vary = 1; - } - DONT_SIMULATE_AGAIN (stmt) = vary; - - /* Mark all V_MAY_DEF operands VARYING. */ - v_may_defs = V_MAY_DEF_OPS (ann); - for (x = 0; x < NUM_V_MAY_DEFS (v_may_defs); x++) - { - tree res = V_MAY_DEF_RESULT (v_may_defs, x); - get_value (res)->lattice_val = VARYING; - SET_BIT (virtual_var, SSA_NAME_VERSION (res)); - } - - /* Mark all V_MUST_DEF operands VARYING. */ - v_must_defs = V_MUST_DEF_OPS (ann); - for (x = 0; x < NUM_V_MUST_DEFS (v_must_defs); x++) - { - tree v_must_def = V_MUST_DEF_OP (v_must_defs, x); - get_value (v_must_def)->lattice_val = VARYING; - SET_BIT (virtual_var, SSA_NAME_VERSION (v_must_def)); - } + /* If STMT is an assignment to an SSA_NAME, we only have one + value to set. */ + if (set_lattice_value (lhs, val)) + { + *output_p = lhs; + if (val.lattice_val == VARYING) + retval = SSA_PROP_VARYING; + else + retval = SSA_PROP_INTERESTING; } - - for (e = bb->succ; e; e = e->succ_next) - e->flags &= ~EDGE_EXECUTABLE; } - - /* Now process PHI nodes. */ - FOR_EACH_BB (bb) + else if (do_store_ccp && stmt_makes_single_store (stmt)) { - tree phi, var; - int x; - for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) - { - value *val; - val = get_value (PHI_RESULT (phi)); - if (val->lattice_val != VARYING) - { - for (x = 0; x < PHI_NUM_ARGS (phi); x++) - { - var = PHI_ARG_DEF (phi, x); - /* If one argument is virtual, the result is virtual, and - therefore varying. */ - if (TREE_CODE (var) == SSA_NAME) - { - if (TEST_BIT (virtual_var, SSA_NAME_VERSION (var))) - { - val->lattice_val = VARYING; - SET_BIT (virtual_var, - SSA_NAME_VERSION (PHI_RESULT (phi))); - break; - } - } - } - } - DONT_SIMULATE_AGAIN (phi) = ((val->lattice_val == VARYING) ? 1 : 0); - } - } + /* Otherwise, set the names in V_MAY_DEF/V_MUST_DEF operands + to the new constant value and mark the LHS as the memory + reference associated with VAL. */ + ssa_op_iter i; + tree vdef; + bool changed; - sbitmap_free (virtual_var); - /* Compute immediate uses for variables we care about. */ - compute_immediate_uses (TDFA_USE_OPS, need_imm_uses_for); + /* Stores cannot take on an UNDEFINED value. */ + if (val.lattice_val == UNDEFINED) + val.lattice_val = UNKNOWN_VAL; - if (dump_file && (dump_flags & TDF_DETAILS)) - dump_immediate_uses (dump_file); - - VARRAY_BB_INIT (cfg_blocks, 20, "cfg_blocks"); + /* Mark VAL as stored in the LHS of this assignment. */ + val.mem_ref = lhs; - /* Seed the algorithm by adding the successors of the entry block to the - edge worklist. */ - for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next) - { - if (e->dest != EXIT_BLOCK_PTR) - { - e->flags |= EDGE_EXECUTABLE; - cfg_blocks_add (e->dest); + /* Set the value of every VDEF to VAL. */ + changed = false; + FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, i, SSA_OP_VIRTUAL_DEFS) + changed |= set_lattice_value (vdef, val); + + /* Note that for propagation purposes, we are only interested in + visiting statements that load the exact same memory reference + stored here. Those statements will have the exact same list + of virtual uses, so it is enough to set the output of this + statement to be its first virtual definition. */ + *output_p = first_vdef (stmt); + if (changed) + { + if (val.lattice_val == VARYING) + retval = SSA_PROP_VARYING; + else + retval = SSA_PROP_INTERESTING; } } -} - -/* Free allocated storage. */ - -static void -finalize (void) -{ - ssa_edges = NULL; - varying_ssa_edges = NULL; - cfg_blocks = NULL; - free (value_vector); - sbitmap_free (bb_in_list); - sbitmap_free (executable_blocks); - free_df (); + return retval; } -/* Is the block worklist empty. */ - -static inline bool -cfg_blocks_empty_p (void) -{ - return (cfg_blocks_num == 0); -} -/* Add a basic block to the worklist. */ +/* Visit the conditional statement STMT. Return SSA_PROP_INTERESTING + if it can determine which edge will be taken. Otherwise, return + SSA_PROP_VARYING. */ -static void -cfg_blocks_add (basic_block bb) +static enum ssa_prop_result +visit_cond_stmt (tree stmt, edge *taken_edge_p) { - if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR) - return; + prop_value_t val; + basic_block block; - if (TEST_BIT (bb_in_list, bb->index)) - return; + block = bb_for_stmt (stmt); + val = evaluate_stmt (stmt); - if (cfg_blocks_empty_p ()) - { - cfg_blocks_tail = cfg_blocks_head = 0; - cfg_blocks_num = 1; - } - else - { - cfg_blocks_num++; - if (cfg_blocks_num > VARRAY_SIZE (cfg_blocks)) - { - /* We have to grow the array now. Adjust to queue to occupy the - full space of the original array. */ - cfg_blocks_tail = VARRAY_SIZE (cfg_blocks); - cfg_blocks_head = 0; - VARRAY_GROW (cfg_blocks, 2 * VARRAY_SIZE (cfg_blocks)); - } - else - cfg_blocks_tail = (cfg_blocks_tail + 1) % VARRAY_SIZE (cfg_blocks); - } - VARRAY_BB (cfg_blocks, cfg_blocks_tail) = bb; - SET_BIT (bb_in_list, bb->index); + /* Find which edge out of the conditional block will be taken and add it + to the worklist. If no single edge can be determined statically, + return SSA_PROP_VARYING to feed all the outgoing edges to the + propagation engine. */ + *taken_edge_p = val.value ? find_taken_edge (block, val.value) : 0; + if (*taken_edge_p) + return SSA_PROP_INTERESTING; + else + return SSA_PROP_VARYING; } -/* Remove a block from the worklist. */ - -static basic_block -cfg_blocks_get (void) -{ - basic_block bb; - - bb = VARRAY_BB (cfg_blocks, cfg_blocks_head); - -#ifdef ENABLE_CHECKING - if (cfg_blocks_empty_p () || !bb) - abort (); -#endif - - cfg_blocks_head = (cfg_blocks_head + 1) % VARRAY_SIZE (cfg_blocks); - --cfg_blocks_num; - RESET_BIT (bb_in_list, bb->index); - return bb; -} +/* Evaluate statement STMT. If the statement produces an output value and + its evaluation changes the lattice value of its output, return + SSA_PROP_INTERESTING and set *OUTPUT_P to the SSA_NAME holding the + output value. + + If STMT is a conditional branch and we can determine its truth + value, set *TAKEN_EDGE_P accordingly. If STMT produces a varying + value, return SSA_PROP_VARYING. */ -/* We have just defined a new value for VAR. Add all immediate uses - of VAR to the ssa_edges or varying_ssa_edges worklist. */ -static void -add_var_to_ssa_edges_worklist (tree var, value val) +static enum ssa_prop_result +ccp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p) { - tree stmt = SSA_NAME_DEF_STMT (var); - dataflow_t df = get_immediate_uses (stmt); - int num_uses = num_immediate_uses (df); - int i; + tree def; + ssa_op_iter iter; - for (i = 0; i < num_uses; i++) + if (dump_file && (dump_flags & TDF_DETAILS)) { - tree use = immediate_use (df, i); + fprintf (dump_file, "\nVisiting statement:\n"); + print_generic_stmt (dump_file, stmt, dump_flags); + fprintf (dump_file, "\n"); + } - if (!DONT_SIMULATE_AGAIN (use)) - { - stmt_ann_t ann = stmt_ann (use); - if (ann->in_ccp_worklist == 0) - { - ann->in_ccp_worklist = 1; - if (val.lattice_val == VARYING) - VARRAY_PUSH_TREE (varying_ssa_edges, use); - else - VARRAY_PUSH_TREE (ssa_edges, use); - } - } + if (TREE_CODE (stmt) == MODIFY_EXPR) + { + /* If the statement is an assignment that produces a single + output value, evaluate its RHS to see if the lattice value of + its output has changed. */ + return visit_assignment (stmt, output_p); + } + else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR) + { + /* If STMT is a conditional branch, see if we can determine + which branch will be taken. */ + return visit_cond_stmt (stmt, taken_edge_p); } -} -/* Set the lattice value for the variable VAR to VARYING. */ + /* Any other kind of statement is not interesting for constant + propagation and, therefore, not worth simulating. */ + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "No interesting values produced. Marked VARYING.\n"); -static void -def_to_varying (tree var) -{ - value val; - val.lattice_val = VARYING; - val.const_val = NULL_TREE; - set_lattice_value (var, val); -} + /* Definitions made by statements other than assignments to + SSA_NAMEs represent unknown modifications to their outputs. + Mark them VARYING. */ + FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) + { + prop_value_t v = { VARYING, NULL_TREE, NULL_TREE }; + set_lattice_value (def, v); + } -/* Set the lattice value for variable VAR to VAL. */ + return SSA_PROP_VARYING; +} -static void -set_lattice_value (tree var, value val) -{ - value *old = get_value (var); -#ifdef ENABLE_CHECKING - if (val.lattice_val == UNDEFINED) - { - /* CONSTANT->UNDEFINED is never a valid state transition. */ - if (old->lattice_val == CONSTANT) - abort (); - - /* VARYING->UNDEFINED is generally not a valid state transition, - except for values which are initialized to VARYING. */ - if (old->lattice_val == VARYING - && get_default_value (var).lattice_val != VARYING) - abort (); - } - else if (val.lattice_val == CONSTANT) - { - /* VARYING -> CONSTANT is an invalid state transition, except - for objects which start off in a VARYING state. */ - if (old->lattice_val == VARYING - && get_default_value (var).lattice_val != VARYING) - abort (); - } -#endif +/* Main entry point for SSA Conditional Constant Propagation. */ - /* If the constant for VAR has changed, then this VAR is really varying. */ - if (old->lattice_val == CONSTANT && val.lattice_val == CONSTANT - && !simple_cst_equal (old->const_val, val.const_val)) - { - val.lattice_val = VARYING; - val.const_val = NULL_TREE; - } +static void +execute_ssa_ccp (bool store_ccp) +{ + do_store_ccp = store_ccp; + ccp_initialize (); + ssa_propagate (ccp_visit_stmt, ccp_visit_phi_node); + ccp_finalize (); +} - if (old->lattice_val != val.lattice_val) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - { - dump_lattice_value (dump_file, - "Lattice value changed to ", val); - fprintf (dump_file, ". Adding definition to SSA edges.\n"); - } - add_var_to_ssa_edges_worklist (var, val); - *old = val; - } +static void +do_ssa_ccp (void) +{ + execute_ssa_ccp (false); } -/* Replace USE references in statement STMT with their immediate reaching - definition. Return true if at least one reference was replaced. If - REPLACED_ADDRESSES_P is given, it will be set to true if an address - constant was replaced. */ static bool -replace_uses_in (tree stmt, bool *replaced_addresses_p) +gate_ccp (void) { - bool replaced = false; - use_optype uses; - size_t i; - - if (replaced_addresses_p) - *replaced_addresses_p = false; + return flag_tree_ccp != 0; +} - get_stmt_operands (stmt); - uses = STMT_USE_OPS (stmt); - for (i = 0; i < NUM_USES (uses); i++) - { - use_operand_p use = USE_OP_PTR (uses, i); - value *val = get_value (USE_FROM_PTR (use)); +struct tree_opt_pass pass_ccp = +{ + "ccp", /* name */ + gate_ccp, /* gate */ + do_ssa_ccp, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_TREE_CCP, /* tv_id */ + PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_cleanup_cfg | TODO_dump_func | TODO_update_ssa + | TODO_ggc_collect | TODO_verify_ssa + | TODO_verify_stmts, /* todo_flags_finish */ + 0 /* letter */ +}; - if (val->lattice_val == CONSTANT) - { - SET_USE (use, val->const_val); - replaced = true; - if (POINTER_TYPE_P (TREE_TYPE (USE_FROM_PTR (use))) - && replaced_addresses_p) - *replaced_addresses_p = true; - } - } - return replaced; +static void +do_ssa_store_ccp (void) +{ + /* If STORE-CCP is not enabled, we just run regular CCP. */ + execute_ssa_ccp (flag_tree_store_ccp != 0); } -/* Return the likely latticevalue for STMT. - - If STMT has no operands, then return CONSTANT. +static bool +gate_store_ccp (void) +{ + /* STORE-CCP is enabled only with -ftree-store-ccp, but when + -fno-tree-store-ccp is specified, we should run regular CCP. + That's why the pass is enabled with either flag. */ + return flag_tree_store_ccp != 0 || flag_tree_ccp != 0; +} - Else if any operands of STMT are undefined, then return UNDEFINED. - Else if any operands of STMT are constants, then return CONSTANT. +struct tree_opt_pass pass_store_ccp = +{ + "store_ccp", /* name */ + gate_store_ccp, /* gate */ + do_ssa_store_ccp, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_TREE_STORE_CCP, /* tv_id */ + PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func | TODO_update_ssa + | TODO_ggc_collect | TODO_verify_ssa + | TODO_cleanup_cfg + | TODO_verify_stmts, /* todo_flags_finish */ + 0 /* letter */ +}; - Else return VARYING. */ +/* Given a constant value VAL for bitfield FIELD, and a destination + variable VAR, return VAL appropriately widened to fit into VAR. If + FIELD is wider than HOST_WIDE_INT, NULL is returned. */ -static latticevalue -likely_value (tree stmt) +tree +widen_bitfield (tree val, tree field, tree var) { - use_optype uses; - size_t i; - int found_constant = 0; - stmt_ann_t ann; + unsigned HOST_WIDE_INT var_size, field_size; + tree wide_val; + unsigned HOST_WIDE_INT mask; + unsigned int i; - /* If the statement makes aliased loads or has volatile operands, it - won't fold to a constant value. */ - ann = stmt_ann (stmt); - if (ann->makes_aliased_loads || ann->has_volatile_ops) - return VARYING; + /* We can only do this if the size of the type and field and VAL are + all constants representable in HOST_WIDE_INT. */ + if (!host_integerp (TYPE_SIZE (TREE_TYPE (var)), 1) + || !host_integerp (DECL_SIZE (field), 1) + || !host_integerp (val, 0)) + return NULL_TREE; - /* A CALL_EXPR is assumed to be varying. This may be overly conservative, - in the presence of const and pure calls. */ - if (get_call_expr_in (stmt) != NULL_TREE) - return VARYING; + var_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (var)), 1); + field_size = tree_low_cst (DECL_SIZE (field), 1); + + /* Give up if either the bitfield or the variable are too wide. */ + if (field_size > HOST_BITS_PER_WIDE_INT || var_size > HOST_BITS_PER_WIDE_INT) + return NULL_TREE; - get_stmt_operands (stmt); + gcc_assert (var_size >= field_size); - uses = USE_OPS (ann); - for (i = 0; i < NUM_USES (uses); i++) + /* If the sign bit of the value is not set or the field's type is unsigned, + just mask off the high order bits of the value. */ + if (DECL_UNSIGNED (field) + || !(tree_low_cst (val, 0) & (((HOST_WIDE_INT)1) << (field_size - 1)))) { - tree use = USE_OP (uses, i); - value *val = get_value (use); + /* Zero extension. Build a mask with the lower 'field_size' bits + set and a BIT_AND_EXPR node to clear the high order bits of + the value. */ + for (i = 0, mask = 0; i < field_size; i++) + mask |= ((HOST_WIDE_INT) 1) << i; - if (val->lattice_val == UNDEFINED) - return UNDEFINED; + wide_val = build2 (BIT_AND_EXPR, TREE_TYPE (var), val, + build_int_cst (TREE_TYPE (var), mask)); + } + else + { + /* Sign extension. Create a mask with the upper 'field_size' + bits set and a BIT_IOR_EXPR to set the high order bits of the + value. */ + for (i = 0, mask = 0; i < (var_size - field_size); i++) + mask |= ((HOST_WIDE_INT) 1) << (var_size - i - 1); - if (val->lattice_val == CONSTANT) - found_constant = 1; + wide_val = build2 (BIT_IOR_EXPR, TREE_TYPE (var), val, + build_int_cst (TREE_TYPE (var), mask)); } - return ((found_constant || !uses) ? CONSTANT : VARYING); + return fold (wide_val); } + /* A subroutine of fold_stmt_r. Attempts to fold *(A+O) to A[X]. BASE is an array type. OFFSET is a byte displacement. ORIG_TYPE is the desired result type. */ @@ -1557,7 +1516,7 @@ maybe_fold_offset_to_array_ref (tree base, tree offset, tree orig_type) || lrem || hrem) return NULL_TREE; - idx = build_int_2_wide (lquo, hquo); + idx = build_int_cst_wide (NULL_TREE, lquo, hquo); } /* Assume the low bound is zero. If there is a domain type, get the @@ -1585,9 +1544,10 @@ maybe_fold_offset_to_array_ref (tree base, tree offset, tree orig_type) return build (ARRAY_REF, orig_type, base, idx, min_idx, size_int (tree_low_cst (elt_size, 1) - / (TYPE_ALIGN (elt_type) / BITS_PER_UNIT))); + / (TYPE_ALIGN_UNIT (elt_type)))); } + /* A subroutine of fold_stmt_r. Attempts to fold *(S+O) to S.X. BASE is a record type. OFFSET is a byte displacement. ORIG_TYPE is the desired result type. */ @@ -1597,7 +1557,7 @@ static tree maybe_fold_offset_to_component_ref (tree record_type, tree base, tree offset, tree orig_type, bool base_is_ptr) { - tree f, t, field_type, tail_array_field; + tree f, t, field_type, tail_array_field, field_offset; if (TREE_CODE (record_type) != RECORD_TYPE && TREE_CODE (record_type) != UNION_TYPE @@ -1617,7 +1577,9 @@ maybe_fold_offset_to_component_ref (tree record_type, tree base, tree offset, continue; if (DECL_BIT_FIELD (f)) continue; - if (TREE_CODE (DECL_FIELD_OFFSET (f)) != INTEGER_CST) + + field_offset = byte_position (f); + if (TREE_CODE (field_offset) != INTEGER_CST) continue; /* ??? Java creates "interesting" fields for representing base classes. @@ -1630,50 +1592,44 @@ maybe_fold_offset_to_component_ref (tree record_type, tree base, tree offset, tail_array_field = NULL_TREE; /* Check to see if this offset overlaps with the field. */ - cmp = tree_int_cst_compare (DECL_FIELD_OFFSET (f), offset); + cmp = tree_int_cst_compare (field_offset, offset); if (cmp > 0) continue; field_type = TREE_TYPE (f); - if (cmp < 0) - { - /* Don't care about offsets into the middle of scalars. */ - if (!AGGREGATE_TYPE_P (field_type)) - continue; - - /* Check for array at the end of the struct. This is often - used as for flexible array members. We should be able to - turn this into an array access anyway. */ - if (TREE_CODE (field_type) == ARRAY_TYPE) - tail_array_field = f; - - /* Check the end of the field against the offset. */ - if (!DECL_SIZE_UNIT (f) - || TREE_CODE (DECL_SIZE_UNIT (f)) != INTEGER_CST) - continue; - t = int_const_binop (MINUS_EXPR, offset, DECL_FIELD_OFFSET (f), 1); - if (!tree_int_cst_lt (t, DECL_SIZE_UNIT (f))) - continue; - - /* If we matched, then set offset to the displacement into - this field. */ - offset = t; - } /* Here we exactly match the offset being checked. If the types match, then we can return that field. */ - else if (lang_hooks.types_compatible_p (orig_type, field_type)) + if (cmp == 0 + && lang_hooks.types_compatible_p (orig_type, field_type)) { if (base_is_ptr) base = build1 (INDIRECT_REF, record_type, base); t = build (COMPONENT_REF, field_type, base, f, NULL_TREE); return t; } + + /* Don't care about offsets into the middle of scalars. */ + if (!AGGREGATE_TYPE_P (field_type)) + continue; - /* Don't care about type-punning of scalars. */ - else if (!AGGREGATE_TYPE_P (field_type)) - return NULL_TREE; + /* Check for array at the end of the struct. This is often + used as for flexible array members. We should be able to + turn this into an array access anyway. */ + if (TREE_CODE (field_type) == ARRAY_TYPE) + tail_array_field = f; + + /* Check the end of the field against the offset. */ + if (!DECL_SIZE_UNIT (f) + || TREE_CODE (DECL_SIZE_UNIT (f)) != INTEGER_CST) + continue; + t = int_const_binop (MINUS_EXPR, offset, field_offset, 1); + if (!tree_int_cst_lt (t, DECL_SIZE_UNIT (f))) + continue; + /* If we matched, then set offset to the displacement into + this field. */ + offset = t; goto found; } @@ -1682,6 +1638,7 @@ maybe_fold_offset_to_component_ref (tree record_type, tree base, tree offset, f = tail_array_field; field_type = TREE_TYPE (f); + offset = int_const_binop (MINUS_EXPR, offset, byte_position (f), 1); found: /* If we get here, we've got an aggregate field, and a possibly @@ -1697,6 +1654,7 @@ maybe_fold_offset_to_component_ref (tree record_type, tree base, tree offset, orig_type, false); } + /* A subroutine of fold_stmt_r. Attempt to simplify *(BASE+OFFSET). Return the simplified expression, or NULL if nothing could be done. */ @@ -1709,7 +1667,7 @@ maybe_fold_stmt_indirect (tree expr, tree base, tree offset) substitutions. Fold that down to one. Remove NON_LVALUE_EXPRs that are sometimes added. */ base = fold (base); - STRIP_NOPS (base); + STRIP_TYPE_NOPS (base); TREE_OPERAND (expr, 0) = base; /* One possibility is that the address reduces to a string constant. */ @@ -1735,6 +1693,11 @@ maybe_fold_stmt_indirect (tree expr, tree base, tree offset) /* Strip the ADDR_EXPR. */ base = TREE_OPERAND (base, 0); + /* Fold away CONST_DECL to its value, if the type is scalar. */ + if (TREE_CODE (base) == CONST_DECL + && is_gimple_min_invariant (DECL_INITIAL (base))) + return DECL_INITIAL (base); + /* Try folding *(&B+O) to B[X]. */ t = maybe_fold_offset_to_array_ref (base, offset, TREE_TYPE (expr)); if (t) @@ -1759,7 +1722,7 @@ maybe_fold_stmt_indirect (tree expr, tree base, tree offset) /* We can get here for out-of-range string constant accesses, such as "_"[3]. Bail out of the entire substitution search and arrange for the entire statement to be replaced by a - call to __builtin_trap. In all likelyhood this will all be + call to __builtin_trap. In all likelihood this will all be constant-folded away, but in the meantime we can't leave with something that get_expr_operands can't understand. */ @@ -1769,7 +1732,7 @@ maybe_fold_stmt_indirect (tree expr, tree base, tree offset) && TREE_CODE (TREE_OPERAND (t, 0)) == STRING_CST) { /* FIXME: Except that this causes problems elsewhere with dead - code not being deleted, and we abort in the rtl expanders + code not being deleted, and we die in the rtl expanders because we failed to remove some ssa_name. In the meantime, just return zero. */ /* FIXME2: This condition should be signaled by @@ -1793,6 +1756,7 @@ maybe_fold_stmt_indirect (tree expr, tree base, tree offset) return NULL_TREE; } + /* A subroutine of fold_stmt_r. EXPR is a PLUS_EXPR. A quaint feature extant in our address arithmetic is that there @@ -1968,38 +1932,23 @@ fold_stmt_r (tree *expr_p, int *walk_subtrees, void *data) return t; *walk_subtrees = 0; - /* Make sure the FIELD_DECL is actually a field in the type on - the lhs. In cases with IMA it is possible that it came - from another, equivalent type at this point. We have - already checked the equivalence in this case. - Match on type plus offset, to allow for unnamed fields. - We won't necessarily get the corresponding field for - unions; this is believed to be harmless. */ - - if ((current_file_decl && TREE_CHAIN (current_file_decl)) - && (DECL_FIELD_CONTEXT (TREE_OPERAND (expr, 1)) != - TREE_TYPE (TREE_OPERAND (expr, 0)))) - { - tree f; - tree orig_field = TREE_OPERAND (expr, 1); - tree orig_type = TREE_TYPE (orig_field); - for (f = TYPE_FIELDS (TREE_TYPE (TREE_OPERAND (expr, 0))); - f; f = TREE_CHAIN (f)) - { - if (lang_hooks.types_compatible_p (TREE_TYPE (f), orig_type) - && tree_int_cst_compare (DECL_FIELD_BIT_OFFSET (f), - DECL_FIELD_BIT_OFFSET (orig_field)) - == 0 - && tree_int_cst_compare (DECL_FIELD_OFFSET (f), - DECL_FIELD_OFFSET (orig_field)) - == 0) - { - TREE_OPERAND (expr, 1) = f; - break; - } - } - /* Fall through is an error; it will be detected in tree-sra. */ - } + /* Make sure the FIELD_DECL is actually a field in the type on the lhs. + We've already checked that the records are compatible, so we should + come up with a set of compatible fields. */ + { + tree expr_record = TREE_TYPE (TREE_OPERAND (expr, 0)); + tree expr_field = TREE_OPERAND (expr, 1); + + if (DECL_FIELD_CONTEXT (expr_field) != TYPE_MAIN_VARIANT (expr_record)) + { + expr_field = find_compatible_field (expr_record, expr_field); + TREE_OPERAND (expr, 1) = expr_field; + } + } + break; + + case TARGET_MEM_REF: + t = maybe_fold_tmr (expr); break; default: @@ -2015,269 +1964,98 @@ fold_stmt_r (tree *expr_p, int *walk_subtrees, void *data) return NULL_TREE; } -/* Fold the statement pointed by STMT_P. In some cases, this function may - replace the whole statement with a new one. Returns true iff folding - makes any changes. */ - -bool -fold_stmt (tree *stmt_p) -{ - tree rhs, result, stmt; - bool changed = false; - - stmt = *stmt_p; - - /* If we replaced constants and the statement makes pointer dereferences, - then we may need to fold instances of *&VAR into VAR, etc. */ - if (walk_tree (stmt_p, fold_stmt_r, &changed, NULL)) - { - *stmt_p - = build_function_call_expr (implicit_built_in_decls[BUILT_IN_TRAP], - NULL); - return true; - } - - rhs = get_rhs (stmt); - if (!rhs) - return changed; - result = NULL_TREE; - - if (TREE_CODE (rhs) == CALL_EXPR) - { - tree callee; - - /* Check for builtins that CCP can handle using information not - available in the generic fold routines. */ - callee = get_callee_fndecl (rhs); - if (callee && DECL_BUILT_IN (callee)) - result = ccp_fold_builtin (stmt, rhs); - else - { - /* Check for resolvable OBJ_TYPE_REF. The only sorts we can resolve - here are when we've propagated the address of a decl into the - object slot. */ - /* ??? Should perhaps do this in fold proper. However, doing it - there requires that we create a new CALL_EXPR, and that requires - copying EH region info to the new node. Easier to just do it - here where we can just smash the call operand. */ - callee = TREE_OPERAND (rhs, 0); - if (TREE_CODE (callee) == OBJ_TYPE_REF - && lang_hooks.fold_obj_type_ref - && TREE_CODE (OBJ_TYPE_REF_OBJECT (callee)) == ADDR_EXPR - && DECL_P (TREE_OPERAND (OBJ_TYPE_REF_OBJECT (callee), 0))) - { - tree t; - - t = TREE_TYPE (TREE_OPERAND (OBJ_TYPE_REF_OBJECT (callee), 0)); - t = lang_hooks.fold_obj_type_ref (callee, t); - if (t) - { - TREE_OPERAND (rhs, 0) = t; - changed = true; - } - } - } - } - - /* If we couldn't fold the RHS, hand over to the generic fold routines. */ - if (result == NULL_TREE) - result = fold (rhs); - - /* Strip away useless type conversions. Both the NON_LVALUE_EXPR that - may have been added by fold, and "useless" type conversions that might - now be apparent due to propagation. */ - STRIP_USELESS_TYPE_CONVERSION (result); - - if (result != rhs) - changed |= set_rhs (stmt_p, result); - - return changed; -} - -/* Get the main expression from statement STMT. */ - -static tree -get_rhs (tree stmt) -{ - enum tree_code code = TREE_CODE (stmt); - - if (code == MODIFY_EXPR) - return TREE_OPERAND (stmt, 1); - if (code == COND_EXPR) - return COND_EXPR_COND (stmt); - else if (code == SWITCH_EXPR) - return SWITCH_COND (stmt); - else if (code == RETURN_EXPR) - { - if (!TREE_OPERAND (stmt, 0)) - return NULL_TREE; - if (TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR) - return TREE_OPERAND (TREE_OPERAND (stmt, 0), 1); - else - return TREE_OPERAND (stmt, 0); - } - else if (code == GOTO_EXPR) - return GOTO_DESTINATION (stmt); - else if (code == LABEL_EXPR) - return LABEL_EXPR_LABEL (stmt); - else - return stmt; -} - -/* Set the main expression of *STMT_P to EXPR. */ +/* Return the string length of ARG in LENGTH. If ARG is an SSA name variable, + follow its use-def chains. If LENGTH is not NULL and its value is not + equal to the length we determine, or if we are unable to determine the + length, return false. VISITED is a bitmap of visited variables. */ static bool -set_rhs (tree *stmt_p, tree expr) +get_strlen (tree arg, tree *length, bitmap visited) { - tree stmt = *stmt_p; - enum tree_code code = TREE_CODE (expr); - - /* Verify the constant folded result is valid gimple. */ - if (TREE_CODE_CLASS (code) == '2') + tree var, def_stmt, val; + + if (TREE_CODE (arg) != SSA_NAME) { - if (!is_gimple_val (TREE_OPERAND (expr, 0)) - || !is_gimple_val (TREE_OPERAND (expr, 1))) + val = c_strlen (arg, 1); + if (!val) return false; - } - else if (TREE_CODE_CLASS (code) == '1') - { - if (!is_gimple_val (TREE_OPERAND (expr, 0))) + + if (*length && simple_cst_equal (val, *length) != 1) return false; - } - code = TREE_CODE (stmt); - if (code == MODIFY_EXPR) - TREE_OPERAND (stmt, 1) = expr; - else if (code == COND_EXPR) - COND_EXPR_COND (stmt) = expr; - else if (code == SWITCH_EXPR) - SWITCH_COND (stmt) = expr; - else if (code == RETURN_EXPR) - { - if (TREE_OPERAND (stmt, 0) - && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR) - TREE_OPERAND (TREE_OPERAND (stmt, 0), 1) = expr; - else - TREE_OPERAND (stmt, 0) = expr; + *length = val; + return true; } - else if (code == GOTO_EXPR) - GOTO_DESTINATION (stmt) = expr; - else if (code == LABEL_EXPR) - LABEL_EXPR_LABEL (stmt) = expr; - else + + /* If we were already here, break the infinite cycle. */ + if (bitmap_bit_p (visited, SSA_NAME_VERSION (arg))) + return true; + bitmap_set_bit (visited, SSA_NAME_VERSION (arg)); + + var = arg; + def_stmt = SSA_NAME_DEF_STMT (var); + + switch (TREE_CODE (def_stmt)) { - /* Replace the whole statement with EXPR. If EXPR has no side - effects, then replace *STMT_P with an empty statement. */ - stmt_ann_t ann = stmt_ann (stmt); - *stmt_p = TREE_SIDE_EFFECTS (expr) ? expr : build_empty_stmt (); - (*stmt_p)->common.ann = (tree_ann_t) ann; + case MODIFY_EXPR: + { + tree len, rhs; + + /* The RHS of the statement defining VAR must either have a + constant length or come from another SSA_NAME with a constant + length. */ + rhs = TREE_OPERAND (def_stmt, 1); + STRIP_NOPS (rhs); + if (TREE_CODE (rhs) == SSA_NAME) + return get_strlen (rhs, length, visited); - if (TREE_SIDE_EFFECTS (expr)) - { - def_optype defs; - v_may_def_optype v_may_defs; - v_must_def_optype v_must_defs; - size_t i; - - /* Fix all the SSA_NAMEs created by *STMT_P to point to its new - replacement. */ - defs = DEF_OPS (ann); - for (i = 0; i < NUM_DEFS (defs); i++) + /* See if the RHS is a constant length. */ + len = c_strlen (rhs, 1); + if (len) { - tree var = DEF_OP (defs, i); - if (TREE_CODE (var) == SSA_NAME) - SSA_NAME_DEF_STMT (var) = *stmt_p; - } + if (*length && simple_cst_equal (len, *length) != 1) + return false; - v_may_defs = V_MAY_DEF_OPS (ann); - for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++) - { - tree var = V_MAY_DEF_RESULT (v_may_defs, i); - if (TREE_CODE (var) == SSA_NAME) - SSA_NAME_DEF_STMT (var) = *stmt_p; - } - - v_must_defs = V_MUST_DEF_OPS (ann); - for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++) - { - tree var = V_MUST_DEF_OP (v_must_defs, i); - if (TREE_CODE (var) == SSA_NAME) - SSA_NAME_DEF_STMT (var) = *stmt_p; + *length = len; + return true; } - } - } - - return true; -} - - -/* Return a default value for variable VAR using the following rules: - - 1- Global and static variables are considered VARYING, unless they are - declared const. - 2- Function arguments are considered VARYING. - - 3- Any other value is considered UNDEFINED. This is useful when - considering PHI nodes. PHI arguments that are undefined do not - change the constant value of the PHI node, which allows for more - constants to be propagated. */ + break; + } -static value -get_default_value (tree var) -{ - value val; - tree sym; + case PHI_NODE: + { + /* All the arguments of the PHI node must have the same constant + length. */ + int i; - if (TREE_CODE (var) == SSA_NAME) - sym = SSA_NAME_VAR (var); - else - { -#ifdef ENABLE_CHECKING - if (!DECL_P (var)) - abort (); -#endif - sym = var; - } + for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++) + { + tree arg = PHI_ARG_DEF (def_stmt, i); - val.lattice_val = UNDEFINED; - val.const_val = NULL_TREE; + /* If this PHI has itself as an argument, we cannot + determine the string length of this argument. However, + if we can find a constant string length for the other + PHI args then we can still be sure that this is a + constant string length. So be optimistic and just + continue with the next argument. */ + if (arg == PHI_RESULT (def_stmt)) + continue; - if (TREE_CODE (sym) == PARM_DECL || TREE_THIS_VOLATILE (sym)) - { - /* Function arguments and volatile variables are considered VARYING. */ - val.lattice_val = VARYING; - } - else if (decl_function_context (sym) != current_function_decl - || TREE_STATIC (sym)) - { - /* Globals and static variables are considered VARYING, unless they - are declared 'const'. */ - val.lattice_val = VARYING; + if (!get_strlen (arg, length, visited)) + return false; + } - if (TREE_READONLY (sym) - && DECL_INITIAL (sym) - && is_gimple_min_invariant (DECL_INITIAL (sym))) - { - val.lattice_val = CONSTANT; - val.const_val = DECL_INITIAL (sym); + return true; } - } - else - { - enum tree_code code; - tree stmt = SSA_NAME_DEF_STMT (var); - if (!IS_EMPTY_STMT (stmt)) - { - code = TREE_CODE (stmt); - if (code != MODIFY_EXPR && code != PHI_NODE) - val.lattice_val = VARYING; - } + default: + break; } - return val; + + return false; } @@ -2288,20 +2066,28 @@ static tree ccp_fold_builtin (tree stmt, tree fn) { tree result, strlen_val[2]; - tree arglist = TREE_OPERAND (fn, 1), a; - tree callee = get_callee_fndecl (fn); - bitmap visited; + tree callee, arglist, a; int strlen_arg, i; + bitmap visited; + bool ignore; - /* Ignore MD builtins. */ - if (DECL_BUILT_IN_CLASS (callee) == BUILT_IN_MD) - return NULL_TREE; + ignore = TREE_CODE (stmt) != MODIFY_EXPR; /* First try the generic builtin folder. If that succeeds, return the result directly. */ - result = fold_builtin (fn); + callee = get_callee_fndecl (fn); + arglist = TREE_OPERAND (fn, 1); + result = fold_builtin (callee, arglist, ignore); if (result) + { + if (ignore) + STRIP_NOPS (result); return result; + } + + /* Ignore MD builtins. */ + if (DECL_BUILT_IN_CLASS (callee) == BUILT_IN_MD) + return NULL_TREE; /* If the builtin could not be folded, and it has no argument list, we're done. */ @@ -2325,7 +2111,7 @@ ccp_fold_builtin (tree stmt, tree fn) } /* Try to use the dataflow information gathered by the CCP process. */ - visited = BITMAP_XMALLOC (); + visited = BITMAP_ALLOC (NULL); memset (strlen_val, 0, sizeof (strlen_val)); for (i = 0, a = arglist; @@ -2338,18 +2124,15 @@ ccp_fold_builtin (tree stmt, tree fn) strlen_val[i] = NULL_TREE; } - BITMAP_XFREE (visited); + BITMAP_FREE (visited); - /* FIXME. All this code looks dangerous in the sense that it might - create non-gimple expressions. */ + result = NULL_TREE; switch (DECL_FUNCTION_CODE (callee)) { case BUILT_IN_STRLEN: - /* Convert from the internal "sizetype" type to "size_t". */ - if (strlen_val[0] - && size_type_node) + if (strlen_val[0]) { - tree new = convert (size_type_node, strlen_val[0]); + tree new = fold_convert (TREE_TYPE (fn), strlen_val[0]); /* If the result is not a valid gimple value, or not a cast of a valid gimple value, then we can not use the result. */ @@ -2357,135 +2140,200 @@ ccp_fold_builtin (tree stmt, tree fn) || (is_gimple_cast (new) && is_gimple_val (TREE_OPERAND (new, 0)))) return new; - else - return NULL_TREE; } - return strlen_val[0]; + break; + case BUILT_IN_STRCPY: - if (strlen_val[1] - && is_gimple_val (strlen_val[1])) - return simplify_builtin_strcpy (arglist, strlen_val[1]); + if (strlen_val[1] && is_gimple_val (strlen_val[1])) + { + tree fndecl = get_callee_fndecl (fn); + tree arglist = TREE_OPERAND (fn, 1); + result = fold_builtin_strcpy (fndecl, arglist, strlen_val[1]); + } + break; + case BUILT_IN_STRNCPY: - if (strlen_val[1] - && is_gimple_val (strlen_val[1])) - return simplify_builtin_strncpy (arglist, strlen_val[1]); + if (strlen_val[1] && is_gimple_val (strlen_val[1])) + { + tree fndecl = get_callee_fndecl (fn); + tree arglist = TREE_OPERAND (fn, 1); + result = fold_builtin_strncpy (fndecl, arglist, strlen_val[1]); + } + break; + case BUILT_IN_FPUTS: - return simplify_builtin_fputs (arglist, - TREE_CODE (stmt) != MODIFY_EXPR, 0, - strlen_val[0]); + result = fold_builtin_fputs (arglist, + TREE_CODE (stmt) != MODIFY_EXPR, 0, + strlen_val[0]); + break; + case BUILT_IN_FPUTS_UNLOCKED: - return simplify_builtin_fputs (arglist, - TREE_CODE (stmt) != MODIFY_EXPR, 1, - strlen_val[0]); + result = fold_builtin_fputs (arglist, + TREE_CODE (stmt) != MODIFY_EXPR, 1, + strlen_val[0]); + break; default: - abort (); + gcc_unreachable (); } - return NULL_TREE; + if (result && ignore) + result = fold_ignored_result (result); + return result; } -/* Return the string length of ARG in LENGTH. If ARG is an SSA name variable, - follow its use-def chains. If LENGTH is not NULL and its value is not - equal to the length we determine, or if we are unable to determine the - length, return false. VISITED is a bitmap of visited variables. */ +/* Fold the statement pointed by STMT_P. In some cases, this function may + replace the whole statement with a new one. Returns true iff folding + makes any changes. */ -static bool -get_strlen (tree arg, tree *length, bitmap visited) +bool +fold_stmt (tree *stmt_p) { - tree var, def_stmt, val; - - if (TREE_CODE (arg) != SSA_NAME) - { - val = c_strlen (arg, 1); - if (!val) - return false; + tree rhs, result, stmt; + bool changed = false; - if (*length && simple_cst_equal (val, *length) != 1) - return false; + stmt = *stmt_p; - *length = val; + /* If we replaced constants and the statement makes pointer dereferences, + then we may need to fold instances of *&VAR into VAR, etc. */ + if (walk_tree (stmt_p, fold_stmt_r, &changed, NULL)) + { + *stmt_p + = build_function_call_expr (implicit_built_in_decls[BUILT_IN_TRAP], + NULL); return true; } - /* If we were already here, break the infinite cycle. */ - if (bitmap_bit_p (visited, SSA_NAME_VERSION (arg))) - return true; - bitmap_set_bit (visited, SSA_NAME_VERSION (arg)); - - var = arg; - def_stmt = SSA_NAME_DEF_STMT (var); + rhs = get_rhs (stmt); + if (!rhs) + return changed; + result = NULL_TREE; - switch (TREE_CODE (def_stmt)) + if (TREE_CODE (rhs) == CALL_EXPR) { - case MODIFY_EXPR: - { - tree len, rhs; - - /* The RHS of the statement defining VAR must either have a - constant length or come from another SSA_NAME with a constant - length. */ - rhs = TREE_OPERAND (def_stmt, 1); - STRIP_NOPS (rhs); - if (TREE_CODE (rhs) == SSA_NAME) - return get_strlen (rhs, length, visited); + tree callee; - /* See if the RHS is a constant length. */ - len = c_strlen (rhs, 1); - if (len) + /* Check for builtins that CCP can handle using information not + available in the generic fold routines. */ + callee = get_callee_fndecl (rhs); + if (callee && DECL_BUILT_IN (callee)) + result = ccp_fold_builtin (stmt, rhs); + else + { + /* Check for resolvable OBJ_TYPE_REF. The only sorts we can resolve + here are when we've propagated the address of a decl into the + object slot. */ + /* ??? Should perhaps do this in fold proper. However, doing it + there requires that we create a new CALL_EXPR, and that requires + copying EH region info to the new node. Easier to just do it + here where we can just smash the call operand. */ + callee = TREE_OPERAND (rhs, 0); + if (TREE_CODE (callee) == OBJ_TYPE_REF + && lang_hooks.fold_obj_type_ref + && TREE_CODE (OBJ_TYPE_REF_OBJECT (callee)) == ADDR_EXPR + && DECL_P (TREE_OPERAND + (OBJ_TYPE_REF_OBJECT (callee), 0))) { - if (*length && simple_cst_equal (len, *length) != 1) - return false; + tree t; - *length = len; - return true; - } + /* ??? Caution: Broken ADDR_EXPR semantics means that + looking at the type of the operand of the addr_expr + can yield an array type. See silly exception in + check_pointer_types_r. */ - break; + t = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (callee))); + t = lang_hooks.fold_obj_type_ref (callee, t); + if (t) + { + TREE_OPERAND (rhs, 0) = t; + changed = true; + } + } } + } - case PHI_NODE: - { - /* All the arguments of the PHI node must have the same constant - length. */ - int i; + /* If we couldn't fold the RHS, hand over to the generic fold routines. */ + if (result == NULL_TREE) + result = fold (rhs); - for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++) - { - tree arg = PHI_ARG_DEF (def_stmt, i); + /* Strip away useless type conversions. Both the NON_LVALUE_EXPR that + may have been added by fold, and "useless" type conversions that might + now be apparent due to propagation. */ + STRIP_USELESS_TYPE_CONVERSION (result); - /* If this PHI has itself as an argument, we cannot - determine the string length of this argument. However, - if we can find a constant string length for the other - PHI args then we can still be sure that this is a - constant string length. So be optimistic and just - continue with the next argument. */ - if (arg == PHI_RESULT (def_stmt)) - continue; + if (result != rhs) + changed |= set_rhs (stmt_p, result); - if (!get_strlen (arg, length, visited)) - return false; - } + return changed; +} - return true; - } +/* Perform the minimal folding on statement STMT. Only operations like + *&x created by constant propagation are handled. The statement cannot + be replaced with a new one. */ - default: - break; - } +bool +fold_stmt_inplace (tree stmt) +{ + tree old_stmt = stmt, rhs, new_rhs; + bool changed = false; + walk_tree (&stmt, fold_stmt_r, &changed, NULL); + gcc_assert (stmt == old_stmt); - return false; -} + rhs = get_rhs (stmt); + if (!rhs || rhs == stmt) + return changed; + + new_rhs = fold (rhs); + if (new_rhs == rhs) + return changed; + + changed |= set_rhs (&stmt, new_rhs); + gcc_assert (stmt == old_stmt); + return changed; +} +/* Convert EXPR into a GIMPLE value suitable for substitution on the + RHS of an assignment. Insert the necessary statements before + iterator *SI_P. */ + +static tree +convert_to_gimple_builtin (block_stmt_iterator *si_p, tree expr) +{ + tree_stmt_iterator ti; + tree stmt = bsi_stmt (*si_p); + tree tmp, stmts = NULL; + + push_gimplify_context (); + tmp = get_initialized_tmp_var (expr, &stmts, NULL); + pop_gimplify_context (NULL); + + if (EXPR_HAS_LOCATION (stmt)) + annotate_all_with_locus (&stmts, EXPR_LOCATION (stmt)); + + /* The replacement can expose previously unreferenced variables. */ + for (ti = tsi_start (stmts); !tsi_end_p (ti); tsi_next (&ti)) + { + tree new_stmt = tsi_stmt (ti); + find_new_referenced_vars (tsi_stmt_ptr (ti)); + bsi_insert_before (si_p, new_stmt, BSI_NEW_STMT); + mark_new_vars_to_rename (bsi_stmt (*si_p)); + bsi_next (si_p); + } + + return tmp; +} + + /* A simple pass that attempts to fold all builtin functions. This pass is run after we've propagated as many constants as we can. */ static void execute_fold_all_builtins (void) { + bool cfg_changed = false; basic_block bb; FOR_EACH_BB (bb) { @@ -2493,6 +2341,7 @@ execute_fold_all_builtins (void) for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i)) { tree *stmtp = bsi_stmt_ptr (i); + tree old_stmt = *stmtp; tree call = get_rhs (*stmtp); tree callee, result; @@ -2523,8 +2372,20 @@ execute_fold_all_builtins (void) print_generic_stmt (dump_file, *stmtp, dump_flags); } - if (set_rhs (stmtp, result)) - modify_stmt (*stmtp); + if (!set_rhs (stmtp, result)) + { + result = convert_to_gimple_builtin (&i, result); + if (result) + { + bool ok = set_rhs (stmtp, result); + + gcc_assert (ok); + } + } + update_stmt (*stmtp); + if (maybe_clean_or_replace_eh_stmt (old_stmt, *stmtp) + && tree_purge_dead_eh_edges (bb)) + cfg_changed = true; if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -2534,8 +2395,13 @@ execute_fold_all_builtins (void) } } } + + /* Delete unreachable blocks. */ + if (cfg_changed) + cleanup_tree_cfg (); } + struct tree_opt_pass pass_fold_builtins = { "fab", /* name */ @@ -2545,12 +2411,12 @@ struct tree_opt_pass pass_fold_builtins = NULL, /* next */ 0, /* static_pass_number */ 0, /* tv_id */ - PROP_cfg | PROP_ssa, /* properties_required */ + PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ - TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */ + TODO_dump_func + | TODO_verify_ssa + | TODO_update_ssa, /* todo_flags_finish */ + 0 /* letter */ }; - - -#include "gt-tree-ssa-ccp.h"