/* Generic SSA value propagation engine.
- Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
+ Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>
This file is part of GCC.
simulate_stmt (stmt);
}
- /* We can not predict when abnormal edges will be executed, so
+ /* We can not predict when abnormal and EH edges will be executed, so
once a block is considered executable, we consider any
outgoing abnormal edges as executable.
+ TODO: This is not exactly true. Simplifying statement might
+ prove it non-throwing and also computed goto can be handled
+ when destination is known.
+
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 = NULL;
FOR_EACH_EDGE (e, ei, block->succs)
{
- if (e->flags & EDGE_ABNORMAL)
+ if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
add_control_edge (e);
else
{
edge e;
edge_iterator ei;
basic_block bb;
- size_t i;
/* Worklists of SSA edges. */
interesting_ssa_edges = VEC_alloc (gimple, gc, 20);
cfg_blocks = VEC_alloc (basic_block, heap, 20);
VEC_safe_grow (basic_block, heap, cfg_blocks, 20);
- /* 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)
new_stmt = gimple_build_call_vec (fn, args);
gimple_call_set_lhs (new_stmt, lhs);
- copy_virtual_operands (new_stmt, stmt);
move_ssa_defining_stmt_for_defs (new_stmt, stmt);
+ gimple_set_vuse (new_stmt, gimple_vuse (stmt));
+ gimple_set_vdef (new_stmt, gimple_vdef (stmt));
gimple_set_location (new_stmt, gimple_location (stmt));
gsi_replace (si_p, new_stmt, false);
VEC_free (tree, heap, args);
Introduce a new GIMPLE_ASSIGN statement. */
STRIP_USELESS_TYPE_CONVERSION (expr);
new_stmt = gimple_build_assign (lhs, expr);
- copy_virtual_operands (new_stmt, stmt);
move_ssa_defining_stmt_for_defs (new_stmt, stmt);
+ gimple_set_vuse (new_stmt, gimple_vuse (stmt));
+ gimple_set_vdef (new_stmt, gimple_vdef (stmt));
}
else if (!TREE_SIDE_EFFECTS (expr))
{
/* No value is expected, and EXPR has no effect.
Replace it with an empty statement. */
new_stmt = gimple_build_nop ();
+ unlink_stmt_vdef (stmt);
+ release_defs (stmt);
}
else
{
add_referenced_var (lhs);
lhs = make_ssa_name (lhs, new_stmt);
gimple_assign_set_lhs (new_stmt, lhs);
- copy_virtual_operands (new_stmt, stmt);
+ gimple_set_vuse (new_stmt, gimple_vuse (stmt));
+ gimple_set_vdef (new_stmt, gimple_vdef (stmt));
move_ssa_defining_stmt_for_defs (new_stmt, stmt);
}
gimple_set_location (new_stmt, gimple_location (stmt));
}
-/* Return the first VDEF operand for STMT. */
-
-tree
-first_vdef (gimple 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 (gimple stmt)
-{
- tree rhs;
-
- if (gimple_code (stmt) != GIMPLE_ASSIGN)
- return false;
-
- /* Only a GIMPLE_SINGLE_RHS assignment may have a
- declaration or reference as its RHS. */
- if (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
- != GIMPLE_SINGLE_RHS)
- return false;
-
- if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF|SSA_OP_VUSE))
- return false;
-
- rhs = gimple_assign_rhs1 (stmt);
-
- 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
&& gimple_code (stmt) != GIMPLE_CALL)
return false;
- if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF))
+ if (!gimple_vdef (stmt))
return false;
lhs = gimple_get_lhs (stmt);
}
-/* 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 (gimple 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
{
}
-/* Replace the VUSE references in statement STMT with the values
- stored in PROP_VALUE. Return true if a reference 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 = VDEF <a_2>
- a.b = x_1;
- ...
- # VUSE <a_3>
- 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 = VDEF <a_2>
- # b_5 = VDEF <b_4>
- *p = 10;
- ...
- # VUSE <b_5>
- 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 = VDEF <a_2>
- a.b = 3;
- else
- # a_4 = VDEF <a_2>
- a.c = 3;
- # a_5 = PHI <a_3, a_4>
-
- 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 (gimple stmt, 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 = gimple_assign_rhs1 (stmt);
-
- if (val
- && val->value
- && (is_gimple_reg (val->value)
- || is_gimple_min_invariant (val->value))
- && simple_cst_equal (rhs, val->mem_ref) == 1)
- {
- /* 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. */
- gimple_assign_set_rhs1 (stmt, 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. */
{
bool did_replace;
gimple stmt = gsi_stmt (i);
+ gimple old_stmt;
enum gimple_code code = gimple_code (stmt);
/* Ignore ASSERT_EXPRs. They are used by VRP to generate
continue;
}
- /* Record the state of the statement before replacements. */
- push_stmt_changes (gsi_stmt_ptr (&i));
-
/* Replace the statement with its folded version and mark it
folded. */
did_replace = false;
gcc_assert (gsi_stmt (i) == 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, prop_value);
-
- did_replace |= replace_vuses_in (stmt, prop_value);
- }
+ /* Only replace real uses if we couldn't fold the
+ statement using value range information. */
+ if (prop_value
+ && !did_replace)
+ did_replace |= replace_uses_in (stmt, prop_value);
+
+ /* If we made a replacement, fold the statement. */
- /* If we made a replacement, fold and cleanup the statement. */
+ old_stmt = stmt;
if (did_replace)
- {
- gimple old_stmt = stmt;
+ fold_stmt (&i);
- fold_stmt (&i);
+ /* 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)
+ did_replace |= simplify_stmt_using_ranges (&i);
+
+ /* Now cleanup. */
+ if (did_replace)
+ {
stmt = gsi_stmt (i);
/* If we cleaned up EH information from the statement,
}
/* Determine what needs to be done to update the SSA form. */
- pop_stmt_changes (gsi_stmt_ptr (&i));
+ update_stmt (stmt);
something_changed = true;
}
- else
- {
- /* The statement was not modified, discard the change buffer. */
- discard_stmt_changes (gsi_stmt_ptr (&i));
- }
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Not folded\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);
-
gsi_prev (&i);
}
}