X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-ssa-propagate.c;h=00d5a9458896fa9780afedb86009cc6ab150e34d;hb=d5a2a489ecc9fa05b484cdb442bd98b8f7abf22b;hp=1577a9c0b5ab4a25215f048e52f7662d5f4a08bf;hpb=415115853a731f3e3b2a5fa4f722dbe0377992d4;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-ssa-propagate.c b/gcc/tree-ssa-propagate.c index 1577a9c0b5a..00d5a945889 100644 --- a/gcc/tree-ssa-propagate.c +++ b/gcc/tree-ssa-propagate.c @@ -1,5 +1,5 @@ /* Generic SSA value propagation engine. - Copyright (C) 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc. + Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc. Contributed by Diego Novillo This file is part of GCC. @@ -16,8 +16,8 @@ You should have received a copy of the GNU General Public License 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. */ + Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA + 02110-1301, USA. */ #include "config.h" #include "system.h" @@ -30,7 +30,6 @@ #include "ggc.h" #include "basic-block.h" #include "output.h" -#include "errors.h" #include "expr.h" #include "function.h" #include "diagnostic.h" @@ -40,7 +39,8 @@ #include "tree-pass.h" #include "tree-ssa-propagate.h" #include "langhooks.h" - +#include "varray.h" +#include "vec.h" /* This file implements a generic value propagation engine based on the same propagation used by the SSA-CCP algorithm [1]. @@ -50,7 +50,7 @@ proceeds as follows: 1- Initially, all edges of the CFG are marked not executable and - the CFG worklist seeded with all the statements in the entry + the CFG worklist is seeded with all the statements in the entry basic block (block 0). 2- Every statement S is simulated with a call to the call-back @@ -68,14 +68,14 @@ SSA_PROP_INTERESTING: S produces a value that can be computed at compile time. Its result can be propagated into the - statements that feed from S. Furhtermore, if S is a + statements that feed from S. Furthermore, if S is a conditional jump, only the edge known to be taken is added to the work list. Edges that are known not to execute are never simulated. 3- PHI nodes are simulated with a call to SSA_PROP_VISIT_PHI. The return value from SSA_PROP_VISIT_PHI has the same semantics as - described in #3. + described in #2. 4- Three work lists are kept. Statements are only added to these lists if they produce one of SSA_PROP_INTERESTING or @@ -130,7 +130,7 @@ static ssa_prop_visit_phi_fn ssa_prop_visit_phi; static sbitmap executable_blocks; /* Array of control flow edges on the worklist. */ -static GTY(()) varray_type cfg_blocks = NULL; +static VEC(basic_block,heap) *cfg_blocks; static unsigned int cfg_blocks_num = 0; static int cfg_blocks_tail; @@ -142,7 +142,7 @@ static sbitmap bb_in_list; definition has changed. SSA edges are def-use edges in the SSA web. For each D-U edge, we store the target statement or PHI node U. */ -static GTY(()) varray_type interesting_ssa_edges; +static GTY(()) VEC(tree,gc) *interesting_ssa_edges; /* Identical to INTERESTING_SSA_EDGES. For performance reasons, the list of SSA edges is split into two. One contains all SSA edges @@ -158,7 +158,7 @@ static GTY(()) varray_type interesting_ssa_edges; don't use a separate worklist for VARYING edges, we end up with situations where lattice values move from UNDEFINED->INTERESTING->VARYING instead of UNDEFINED->VARYING. */ -static GTY(()) varray_type varying_ssa_edges; +static GTY(()) VEC(tree,gc) *varying_ssa_edges; /* Return true if the block worklist empty. */ @@ -170,16 +170,14 @@ cfg_blocks_empty_p (void) } -/* Add a basic block to the worklist. */ +/* Add a basic block to the worklist. The block must not be already + in the worklist, and it must not be the ENTRY or EXIT block. */ static void cfg_blocks_add (basic_block bb) { - if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR) - return; - - if (TEST_BIT (bb_in_list, bb->index)) - return; + gcc_assert (bb != ENTRY_BLOCK_PTR && bb != EXIT_BLOCK_PTR); + gcc_assert (!TEST_BIT (bb_in_list, bb->index)); if (cfg_blocks_empty_p ()) { @@ -189,19 +187,23 @@ cfg_blocks_add (basic_block bb) else { cfg_blocks_num++; - if (cfg_blocks_num > VARRAY_SIZE (cfg_blocks)) + if (cfg_blocks_num > VEC_length (basic_block, 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); + /* We have to grow the array now. Adjust to queue to occupy + the full space of the original array. We do not need to + initialize the newly allocated portion of the array + because we keep track of CFG_BLOCKS_HEAD and + CFG_BLOCKS_HEAD. */ + cfg_blocks_tail = VEC_length (basic_block, cfg_blocks); cfg_blocks_head = 0; - VARRAY_GROW (cfg_blocks, 2 * VARRAY_SIZE (cfg_blocks)); + VEC_safe_grow (basic_block, heap, cfg_blocks, 2 * cfg_blocks_tail); } else - cfg_blocks_tail = (cfg_blocks_tail + 1) % VARRAY_SIZE (cfg_blocks); + cfg_blocks_tail = ((cfg_blocks_tail + 1) + % VEC_length (basic_block, cfg_blocks)); } - VARRAY_BB (cfg_blocks, cfg_blocks_tail) = bb; + VEC_replace (basic_block, cfg_blocks, cfg_blocks_tail, bb); SET_BIT (bb_in_list, bb->index); } @@ -213,14 +215,13 @@ cfg_blocks_get (void) { basic_block bb; - bb = VARRAY_BB (cfg_blocks, cfg_blocks_head); + bb = VEC_index (basic_block, cfg_blocks, cfg_blocks_head); -#ifdef ENABLE_CHECKING - if (cfg_blocks_empty_p () || !bb) - abort (); -#endif + gcc_assert (!cfg_blocks_empty_p ()); + gcc_assert (bb); - cfg_blocks_head = (cfg_blocks_head + 1) % VARRAY_SIZE (cfg_blocks); + cfg_blocks_head = ((cfg_blocks_head + 1) + % VEC_length (basic_block, cfg_blocks)); --cfg_blocks_num; RESET_BIT (bb_in_list, bb->index); @@ -235,23 +236,21 @@ cfg_blocks_get (void) static void add_ssa_edge (tree var, bool is_varying) { - tree stmt = SSA_NAME_DEF_STMT (var); - dataflow_t df = get_immediate_uses (stmt); - int num_uses = num_immediate_uses (df); - int i; + imm_use_iterator iter; + use_operand_p use_p; - for (i = 0; i < num_uses; i++) + FOR_EACH_IMM_USE_FAST (use_p, iter, var) { - tree use_stmt = immediate_use (df, i); + tree use_stmt = USE_STMT (use_p); if (!DONT_SIMULATE_AGAIN (use_stmt) && !STMT_IN_SSA_EDGE_WORKLIST (use_stmt)) { STMT_IN_SSA_EDGE_WORKLIST (use_stmt) = 1; if (is_varying) - VARRAY_PUSH_TREE (varying_ssa_edges, use_stmt); + VEC_safe_push (tree, gc, varying_ssa_edges, use_stmt); else - VARRAY_PUSH_TREE (interesting_ssa_edges, use_stmt); + VEC_safe_push (tree, gc, interesting_ssa_edges, use_stmt); } } } @@ -320,8 +319,9 @@ simulate_stmt (tree stmt) if (stmt_ends_bb_p (stmt)) { edge e; + edge_iterator ei; basic_block bb = bb_for_stmt (stmt); - for (e = bb->succ; e; e = e->succ_next) + FOR_EACH_EDGE (e, ei, bb->succs) add_control_edge (e); } } @@ -341,19 +341,20 @@ simulate_stmt (tree stmt) /* 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. */ + them until there are no more statements on WORKLIST. + We take a pointer to WORKLIST because it may be reallocated when an + SSA edge is added to it in simulate_stmt. */ static void -process_ssa_edge_worklist (varray_type *worklist) +process_ssa_edge_worklist (VEC(tree,gc) **worklist) { /* Drain the entire worklist. */ - while (VARRAY_ACTIVE_SIZE (*worklist) > 0) + while (VEC_length (tree, *worklist) > 0) { basic_block bb; /* Pull the statement to simulate off the worklist. */ - tree stmt = VARRAY_TOP_TREE (*worklist); - VARRAY_POP (*worklist); + tree stmt = VEC_pop (tree, *worklist); /* If this statement was already visited by simulate_block, then we don't need to visit it again here. */ @@ -408,6 +409,7 @@ simulate_block (basic_block block) block_stmt_iterator j; unsigned int normal_edge_count; edge e, normal_edge; + edge_iterator ei; /* Note that we have simulated this block. */ SET_BIT (executable_blocks, block->index); @@ -436,7 +438,7 @@ simulate_block (basic_block block) worklist. */ normal_edge_count = 0; normal_edge = NULL; - for (e = block->succ; e; e = e->succ_next) + FOR_EACH_EDGE (e, ei, block->succs) { if (e->flags & EDGE_ABNORMAL) add_control_edge (e); @@ -459,11 +461,13 @@ static void ssa_prop_init (void) { edge e; + edge_iterator ei; basic_block bb; + size_t i; /* Worklists of SSA edges. */ - VARRAY_TREE_INIT (interesting_ssa_edges, 20, "interesting_ssa_edges"); - VARRAY_TREE_INIT (varying_ssa_edges, 20, "varying_ssa_edges"); + interesting_ssa_edges = VEC_alloc (tree, gc, 20); + varying_ssa_edges = VEC_alloc (tree, gc, 20); executable_blocks = sbitmap_alloc (last_basic_block); sbitmap_zero (executable_blocks); @@ -474,30 +478,31 @@ ssa_prop_init (void) if (dump_file && (dump_flags & TDF_DETAILS)) dump_immediate_uses (dump_file); - VARRAY_BB_INIT (cfg_blocks, 20, "cfg_blocks"); + cfg_blocks = VEC_alloc (basic_block, heap, 20); + VEC_safe_grow (basic_block, heap, cfg_blocks, 20); - /* Initially assume that every edge in the CFG is not executable. */ - FOR_EACH_BB (bb) + /* Initialize the values for every SSA_NAME. */ + for (i = 1; i < num_ssa_names; i++) + if (ssa_name (i)) + SSA_NAME_VALUE (ssa_name (i)) = NULL_TREE; + + /* Initially assume that every edge in the CFG is not executable. + (including the edges coming out of ENTRY_BLOCK_PTR). */ + FOR_ALL_BB (bb) { block_stmt_iterator si; for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) STMT_IN_SSA_EDGE_WORKLIST (bsi_stmt (si)) = 0; - for (e = bb->succ; e; e = e->succ_next) + FOR_EACH_EDGE (e, ei, bb->succs) e->flags &= ~EDGE_EXECUTABLE; } /* 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); - } - } + FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) + add_control_edge (e); } @@ -506,12 +511,12 @@ ssa_prop_init (void) static void ssa_prop_fini (void) { - interesting_ssa_edges = NULL; - varying_ssa_edges = NULL; + VEC_free (tree, gc, interesting_ssa_edges); + VEC_free (tree, gc, varying_ssa_edges); + VEC_free (basic_block, heap, cfg_blocks); cfg_blocks = NULL; sbitmap_free (bb_in_list); sbitmap_free (executable_blocks); - free_df (); } @@ -566,17 +571,25 @@ set_rhs (tree *stmt_p, tree expr) ssa_op_iter iter; /* Verify the constant folded result is valid gimple. */ - if (TREE_CODE_CLASS (code) == '2') + if (TREE_CODE_CLASS (code) == tcc_binary) { if (!is_gimple_val (TREE_OPERAND (expr, 0)) || !is_gimple_val (TREE_OPERAND (expr, 1))) return false; } - else if (TREE_CODE_CLASS (code) == '1') + else if (TREE_CODE_CLASS (code) == tcc_unary) { if (!is_gimple_val (TREE_OPERAND (expr, 0))) return false; } + else if (code == ADDR_EXPR) + { + if (TREE_CODE (TREE_OPERAND (expr, 0)) == ARRAY_REF + && !is_gimple_val (TREE_OPERAND (TREE_OPERAND (expr, 0), 1))) + return false; + } + else if (code == COMPOUND_EXPR) + return false; switch (TREE_CODE (stmt)) { @@ -598,6 +611,8 @@ set_rhs (tree *stmt_p, tree expr) break; case COND_EXPR: + if (!is_gimple_condexpr (expr)) + return false; COND_EXPR_COND (stmt) = expr; break; case SWITCH_EXPR: @@ -617,7 +632,8 @@ set_rhs (tree *stmt_p, tree expr) *stmt_p = TREE_SIDE_EFFECTS (expr) ? expr : build_empty_stmt (); (*stmt_p)->common.ann = (tree_ann_t) ann; - if (TREE_SIDE_EFFECTS (expr)) + if (in_ssa_p + && TREE_SIDE_EFFECTS (expr)) { /* Fix all the SSA_NAMEs created by *STMT_P to point to its new replacement. */ @@ -650,8 +666,8 @@ ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt, /* Iterate until the worklists are empty. */ while (!cfg_blocks_empty_p () - || VARRAY_ACTIVE_SIZE (interesting_ssa_edges) > 0 - || VARRAY_ACTIVE_SIZE (varying_ssa_edges) > 0) + || VEC_length (tree, interesting_ssa_edges) > 0 + || VEC_length (tree, varying_ssa_edges) > 0) { if (!cfg_blocks_empty_p ()) { @@ -671,4 +687,513 @@ ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt, ssa_prop_fini (); } + +/* Return the first V_MAY_DEF or V_MUST_DEF operand for STMT. */ + +tree +first_vdef (tree stmt) +{ + ssa_op_iter iter; + tree op; + + /* Simply return the first operand we arrive at. */ + FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS) + return (op); + + gcc_unreachable (); +} + + +/* Return true if STMT is of the form 'LHS = mem_ref', where 'mem_ref' + is a non-volatile pointer dereference, a structure reference or a + reference to a single _DECL. Ignore volatile memory references + because they are not interesting for the optimizers. */ + +bool +stmt_makes_single_load (tree stmt) +{ + tree rhs; + + if (TREE_CODE (stmt) != MODIFY_EXPR) + return false; + + if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VUSE)) + return false; + + rhs = TREE_OPERAND (stmt, 1); + STRIP_NOPS (rhs); + + return (!TREE_THIS_VOLATILE (rhs) + && (DECL_P (rhs) + || REFERENCE_CLASS_P (rhs))); +} + + +/* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref' + is a non-volatile pointer dereference, a structure reference or a + reference to a single _DECL. Ignore volatile memory references + because they are not interesting for the optimizers. */ + +bool +stmt_makes_single_store (tree stmt) +{ + tree lhs; + + if (TREE_CODE (stmt) != MODIFY_EXPR) + return false; + + if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF)) + return false; + + lhs = TREE_OPERAND (stmt, 0); + STRIP_NOPS (lhs); + + return (!TREE_THIS_VOLATILE (lhs) + && (DECL_P (lhs) + || REFERENCE_CLASS_P (lhs))); +} + + +/* If STMT makes a single memory load and all the virtual use operands + have the same value in array VALUES, return it. Otherwise, return + NULL. */ + +prop_value_t * +get_value_loaded_by (tree stmt, prop_value_t *values) +{ + ssa_op_iter i; + tree vuse; + prop_value_t *prev_val = NULL; + prop_value_t *val = NULL; + + FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, i, SSA_OP_VIRTUAL_USES) + { + val = &values[SSA_NAME_VERSION (vuse)]; + if (prev_val && prev_val->value != val->value) + return NULL; + prev_val = val; + } + + return val; +} + + +/* Propagation statistics. */ +struct prop_stats_d +{ + long num_const_prop; + long num_copy_prop; + long num_pred_folded; +}; + +static struct prop_stats_d prop_stats; + +/* Replace USE references in statement STMT with the values stored in + PROP_VALUE. 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. */ + +bool +replace_uses_in (tree stmt, bool *replaced_addresses_p, + prop_value_t *prop_value) +{ + bool replaced = false; + use_operand_p use; + ssa_op_iter iter; + + FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE) + { + tree tuse = USE_FROM_PTR (use); + tree val = prop_value[SSA_NAME_VERSION (tuse)].value; + + if (val == tuse || val == NULL_TREE) + continue; + + if (TREE_CODE (stmt) == ASM_EXPR + && !may_propagate_copy_into_asm (tuse)) + continue; + + if (!may_propagate_copy (tuse, val)) + continue; + + if (TREE_CODE (val) != SSA_NAME) + prop_stats.num_const_prop++; + else + prop_stats.num_copy_prop++; + + propagate_value (use, val); + + replaced = true; + if (POINTER_TYPE_P (TREE_TYPE (tuse)) && replaced_addresses_p) + *replaced_addresses_p = true; + } + + return replaced; +} + + +/* Replace the VUSE references in statement STMT with the values + stored in PROP_VALUE. Return true if a reference was replaced. If + REPLACED_ADDRESSES_P is given, it will be set to true if an address + constant was replaced. + + Replacing VUSE operands is slightly more complex than replacing + regular USEs. We are only interested in two types of replacements + here: + + 1- If the value to be replaced is a constant or an SSA name for a + GIMPLE register, then we are making a copy/constant propagation + from a memory store. For instance, + + # a_3 = V_MAY_DEF + a.b = x_1; + ... + # VUSE + y_4 = a.b; + + This replacement is only possible iff STMT is an assignment + whose RHS is identical to the LHS of the statement that created + the VUSE(s) that we are replacing. Otherwise, we may do the + wrong replacement: + + # a_3 = V_MAY_DEF + # b_5 = V_MAY_DEF + *p = 10; + ... + # VUSE + x_8 = b; + + Even though 'b_5' acquires the value '10' during propagation, + there is no way for the propagator to tell whether the + replacement is correct in every reached use, because values are + computed at definition sites. Therefore, when doing final + substitution of propagated values, we have to check each use + site. Since the RHS of STMT ('b') is different from the LHS of + the originating statement ('*p'), we cannot replace 'b' with + '10'. + + Similarly, when merging values from PHI node arguments, + propagators need to take care not to merge the same values + stored in different locations: + + if (...) + # a_3 = V_MAY_DEF + a.b = 3; + else + # a_4 = V_MAY_DEF + a.c = 3; + # a_5 = PHI + + It would be wrong to propagate '3' into 'a_5' because that + operation merges two stores to different memory locations. + + + 2- If the value to be replaced is an SSA name for a virtual + register, then we simply replace each VUSE operand with its + value from PROP_VALUE. This is the same replacement done by + replace_uses_in. */ + +static bool +replace_vuses_in (tree stmt, bool *replaced_addresses_p, + prop_value_t *prop_value) +{ + bool replaced = false; + ssa_op_iter iter; + use_operand_p vuse; + + if (stmt_makes_single_load (stmt)) + { + /* If STMT is an assignment whose RHS is a single memory load, + see if we are trying to propagate a constant or a GIMPLE + register (case #1 above). */ + prop_value_t *val = get_value_loaded_by (stmt, prop_value); + tree rhs = TREE_OPERAND (stmt, 1); + + if (val + && val->value + && (is_gimple_reg (val->value) + || is_gimple_min_invariant (val->value)) + && simple_cst_equal (rhs, val->mem_ref) == 1) + + { + /* If we are replacing a constant address, inform our + caller. */ + if (TREE_CODE (val->value) != SSA_NAME + && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1))) + && replaced_addresses_p) + *replaced_addresses_p = true; + + /* We can only perform the substitution if the load is done + from the same memory location as the original store. + Since we already know that there are no intervening + stores between DEF_STMT and STMT, we only need to check + that the RHS of STMT is the same as the memory reference + propagated together with the value. */ + TREE_OPERAND (stmt, 1) = val->value; + + if (TREE_CODE (val->value) != SSA_NAME) + prop_stats.num_const_prop++; + else + prop_stats.num_copy_prop++; + + /* Since we have replaced the whole RHS of STMT, there + is no point in checking the other VUSEs, as they will + all have the same value. */ + return true; + } + } + + /* Otherwise, the values for every VUSE operand must be other + SSA_NAMEs that can be propagated into STMT. */ + FOR_EACH_SSA_USE_OPERAND (vuse, stmt, iter, SSA_OP_VIRTUAL_USES) + { + tree var = USE_FROM_PTR (vuse); + tree val = prop_value[SSA_NAME_VERSION (var)].value; + + if (val == NULL_TREE || var == val) + continue; + + /* Constants and copies propagated between real and virtual + operands are only possible in the cases handled above. They + should be ignored in any other context. */ + if (is_gimple_min_invariant (val) || is_gimple_reg (val)) + continue; + + propagate_value (vuse, val); + prop_stats.num_copy_prop++; + replaced = true; + } + + return replaced; +} + + +/* Replace propagated values into all the arguments for PHI using the + values from PROP_VALUE. */ + +static void +replace_phi_args_in (tree phi, prop_value_t *prop_value) +{ + int i; + bool replaced = false; + tree prev_phi = NULL; + + if (dump_file && (dump_flags & TDF_DETAILS)) + prev_phi = unshare_expr (phi); + + for (i = 0; i < PHI_NUM_ARGS (phi); i++) + { + tree arg = PHI_ARG_DEF (phi, i); + + if (TREE_CODE (arg) == SSA_NAME) + { + tree val = prop_value[SSA_NAME_VERSION (arg)].value; + + if (val && val != arg && may_propagate_copy (arg, val)) + { + if (TREE_CODE (val) != SSA_NAME) + prop_stats.num_const_prop++; + else + prop_stats.num_copy_prop++; + + propagate_value (PHI_ARG_DEF_PTR (phi, i), val); + replaced = true; + + /* If we propagated a copy and this argument flows + through an abnormal edge, update the replacement + accordingly. */ + if (TREE_CODE (val) == SSA_NAME + && PHI_ARG_EDGE (phi, i)->flags & EDGE_ABNORMAL) + SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1; + } + } + } + + if (replaced && dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Folded PHI node: "); + print_generic_stmt (dump_file, prev_phi, TDF_SLIM); + fprintf (dump_file, " into: "); + print_generic_stmt (dump_file, phi, TDF_SLIM); + fprintf (dump_file, "\n"); + } +} + + +/* If STMT has a predicate whose value can be computed using the value + range information computed by VRP, compute its value and return true. + Otherwise, return false. */ + +static bool +fold_predicate_in (tree stmt) +{ + tree *pred_p = NULL; + bool modify_expr_p = false; + tree val; + + if (TREE_CODE (stmt) == MODIFY_EXPR + && COMPARISON_CLASS_P (TREE_OPERAND (stmt, 1))) + { + modify_expr_p = true; + pred_p = &TREE_OPERAND (stmt, 1); + } + else if (TREE_CODE (stmt) == COND_EXPR) + pred_p = &COND_EXPR_COND (stmt); + else + return false; + + val = vrp_evaluate_conditional (*pred_p, true); + if (val) + { + if (modify_expr_p) + val = fold_convert (TREE_TYPE (*pred_p), val); + + if (dump_file) + { + fprintf (dump_file, "Folding predicate "); + print_generic_expr (dump_file, *pred_p, 0); + fprintf (dump_file, " to "); + print_generic_expr (dump_file, val, 0); + fprintf (dump_file, "\n"); + } + + prop_stats.num_pred_folded++; + *pred_p = val; + return true; + } + + return false; +} + + +/* Perform final substitution and folding of propagated values. + + PROP_VALUE[I] contains the single value that should be substituted + at every use of SSA name N_I. If PROP_VALUE is NULL, no values are + substituted. + + If USE_RANGES_P is true, statements that contain predicate + expressions are evaluated with a call to vrp_evaluate_conditional. + This will only give meaningful results when called from tree-vrp.c + (the information used by vrp_evaluate_conditional is built by the + VRP pass). */ + +void +substitute_and_fold (prop_value_t *prop_value, bool use_ranges_p) +{ + basic_block bb; + + if (prop_value == NULL && !use_ranges_p) + return; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "\nSubstituing values and folding statements\n\n"); + + memset (&prop_stats, 0, sizeof (prop_stats)); + + /* Substitute values in every statement of every basic block. */ + FOR_EACH_BB (bb) + { + block_stmt_iterator i; + tree phi; + + /* Propagate known values into PHI nodes. */ + if (prop_value) + for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) + replace_phi_args_in (phi, prop_value); + + for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i)) + { + bool replaced_address, did_replace; + tree prev_stmt = NULL; + tree stmt = bsi_stmt (i); + + /* Ignore ASSERT_EXPRs. They are used by VRP to generate + range information for names and they are discarded + afterwards. */ + if (TREE_CODE (stmt) == MODIFY_EXPR + && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR) + continue; + + /* Replace the statement with its folded version and mark it + folded. */ + did_replace = false; + replaced_address = false; + if (dump_file && (dump_flags & TDF_DETAILS)) + prev_stmt = unshare_expr (stmt); + + /* If we have range information, see if we can fold + predicate expressions. */ + if (use_ranges_p) + did_replace = fold_predicate_in (stmt); + + if (prop_value) + { + /* Only replace real uses if we couldn't fold the + statement using value range information (value range + information is not collected on virtuals, so we only + need to check this for real uses). */ + if (!did_replace) + did_replace |= replace_uses_in (stmt, &replaced_address, + prop_value); + + did_replace |= replace_vuses_in (stmt, &replaced_address, + prop_value); + } + + /* If we made a replacement, fold and cleanup the statement. */ + if (did_replace) + { + tree old_stmt = stmt; + tree rhs; + + fold_stmt (bsi_stmt_ptr (i)); + stmt = bsi_stmt (i); + + /* If we folded a builtin function, we'll likely + need to rename VDEFs. */ + mark_new_vars_to_rename (stmt); + + /* If we cleaned up EH information from the statement, + remove EH edges. */ + if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)) + tree_purge_dead_eh_edges (bb); + + rhs = get_rhs (stmt); + if (TREE_CODE (rhs) == ADDR_EXPR) + recompute_tree_invariant_for_addr_expr (rhs); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Folded statement: "); + print_generic_stmt (dump_file, prev_stmt, TDF_SLIM); + fprintf (dump_file, " into: "); + print_generic_stmt (dump_file, stmt, TDF_SLIM); + fprintf (dump_file, "\n"); + } + } + + /* Some statements may be simplified using ranges. For + example, division may be replaced by shifts, modulo + replaced with bitwise and, etc. Do this after + substituting constants, folding, etc so that we're + presented with a fully propagated, canonicalized + statement. */ + if (use_ranges_p) + simplify_stmt_using_ranges (stmt); + + } + } + + if (dump_file && (dump_flags & TDF_STATS)) + { + fprintf (dump_file, "Constants propagated: %6ld\n", + prop_stats.num_const_prop); + fprintf (dump_file, "Copies propagated: %6ld\n", + prop_stats.num_copy_prop); + fprintf (dump_file, "Predicates folded: %6ld\n", + prop_stats.num_pred_folded); + } +} + #include "gt-tree-ssa-propagate.h"