#include "tm.h"
#include "tree.h"
#include "flags.h"
-#include "rtl.h"
#include "tm_p.h"
-#include "ggc.h"
#include "basic-block.h"
#include "output.h"
-#include "expr.h"
#include "function.h"
-#include "diagnostic.h"
+#include "tree-pretty-print.h"
+#include "gimple-pretty-print.h"
#include "timevar.h"
#include "tree-dump.h"
#include "tree-flow.h"
Use this version when not const/copy propagating values. For example,
PRE uses this version when building expressions as they would appear
- in specific blocks taking into account actions of PHI nodes. */
+ in specific blocks taking into account actions of PHI nodes.
+
+ The statement in which an expression has been replaced should be
+ folded using fold_stmt_inplace. */
void
replace_exp (use_operand_p op_p, tree val)
void
propagate_tree_value (tree *op_p, tree val)
{
-#if defined ENABLE_CHECKING
- gcc_assert (!(TREE_CODE (val) == SSA_NAME
- && *op_p
- && TREE_CODE (*op_p) == SSA_NAME
- && !may_propagate_copy (*op_p, val)));
-#endif
+ gcc_checking_assert (!(TREE_CODE (val) == SSA_NAME
+ && *op_p
+ && TREE_CODE (*op_p) == SSA_NAME
+ && !may_propagate_copy (*op_p, val)));
if (TREE_CODE (val) == SSA_NAME)
*op_p = val;
expr = gimple_assign_rhs1 (stmt);
propagate_tree_value (&expr, val);
gimple_assign_set_rhs_from_tree (gsi, expr);
- stmt = gsi_stmt (*gsi);
}
else if (gimple_code (stmt) == GIMPLE_COND)
{
tree lhs = NULL_TREE;
- tree rhs = fold_convert (TREE_TYPE (val), integer_zero_node);
+ tree rhs = build_zero_cst (TREE_TYPE (val));
propagate_tree_value (&lhs, val);
gimple_cond_set_code (stmt, NE_EXPR);
gimple_cond_set_lhs (stmt, lhs);
/*---------------------------------------------------------------------------
Copy propagation
---------------------------------------------------------------------------*/
-/* During propagation, we keep chains of variables that are copies of
- one another. If variable X_i is a copy of X_j and X_j is a copy of
- X_k, COPY_OF will contain:
-
- COPY_OF[i].VALUE = X_j
- COPY_OF[j].VALUE = X_k
- COPY_OF[k].VALUE = X_k
+/* Lattice for copy-propagation. The lattice is initialized to
+ UNDEFINED (value == NULL) for SSA names that can become a copy
+ of something or VARYING (value == self) if not (see get_copy_of_val
+ and stmt_may_generate_copy). Other values make the name a COPY
+ of that value.
+
+ When visiting a statement or PHI node the lattice value for an
+ SSA name can transition from UNDEFINED to COPY to VARYING. */
+
+struct prop_value_d {
+ /* Copy-of value. */
+ tree value;
+};
+typedef struct prop_value_d prop_value_t;
- After propagation, the copy-of value for each variable X_i is
- converted into the final value by walking the copy-of chains and
- updating COPY_OF[i].VALUE to be the last element of the chain. */
static prop_value_t *copy_of;
-/* Used in set_copy_of_val to determine if the last link of a copy-of
- chain has changed. */
-static tree *cached_last_copy_of;
-
/* Return true if this statement may generate a useful copy. */
/* Otherwise, the only statements that generate useful copies are
assignments whose RHS is just an SSA name that doesn't flow
through abnormal edges. */
- return (gimple_assign_rhs_code (stmt) == SSA_NAME
- && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)));
+ return ((gimple_assign_rhs_code (stmt) == SSA_NAME
+ && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)))
+ || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)));
}
return val;
}
+/* Return the variable VAR is a copy of or VAR if VAR isn't the result
+ of a copy. */
-/* Return last link in the copy-of chain for VAR. */
-
-static tree
-get_last_copy_of (tree var)
+static inline tree
+valueize_val (tree var)
{
- tree last;
- int i;
-
- /* Traverse COPY_OF starting at VAR until we get to the last
- link in the chain. Since it is possible to have cycles in PHI
- nodes, the copy-of chain may also contain cycles.
-
- To avoid infinite loops and to avoid traversing lengthy copy-of
- chains, we artificially limit the maximum number of chains we are
- willing to traverse.
-
- The value 5 was taken from a compiler and runtime library
- bootstrap and a mixture of C and C++ code from various sources.
- More than 82% of all copy-of chains were shorter than 5 links. */
-#define LIMIT 5
-
- last = var;
- for (i = 0; i < LIMIT; i++)
+ if (TREE_CODE (var) == SSA_NAME)
{
- tree copy = copy_of[SSA_NAME_VERSION (last)].value;
- if (copy == NULL_TREE || copy == last)
- break;
- last = copy;
+ tree val = get_copy_of_val (var)->value;
+ if (val)
+ return val;
}
-
- /* If we have reached the limit, then we are either in a copy-of
- cycle or the copy-of chain is too long. In this case, just
- return VAR so that it is not considered a copy of anything. */
- return (i < LIMIT ? last : var);
+ return var;
}
-
-/* Set FIRST to be the first variable in the copy-of chain for DEST.
- If DEST's copy-of value or its copy-of chain has changed, return
- true.
-
- MEM_REF is the memory reference where FIRST is stored. This is
- used when DEST is a non-register and we are copy propagating loads
- and stores. */
+/* Set VAL to be the copy of VAR. If that changed return true. */
static inline bool
-set_copy_of_val (tree dest, tree first)
+set_copy_of_val (tree var, tree val)
{
- unsigned int dest_ver = SSA_NAME_VERSION (dest);
- tree old_first, old_last, new_last;
+ unsigned int ver = SSA_NAME_VERSION (var);
+ tree old;
/* Set FIRST to be the first link in COPY_OF[DEST]. If that
changed, return true. */
- old_first = copy_of[dest_ver].value;
- copy_of[dest_ver].value = first;
+ old = copy_of[ver].value;
+ copy_of[ver].value = val;
- if (old_first != first)
+ if (old != val
+ || (val && !operand_equal_p (old, val, 0)))
return true;
- /* If FIRST and OLD_FIRST are the same, we need to check whether the
- copy-of chain starting at FIRST ends in a different variable. If
- the copy-of chain starting at FIRST ends up in a different
- variable than the last cached value we had for DEST, then return
- true because DEST is now a copy of a different variable.
-
- This test is necessary because even though the first link in the
- copy-of chain may not have changed, if any of the variables in
- the copy-of chain changed its final value, DEST will now be the
- copy of a different variable, so we have to do another round of
- propagation for everything that depends on DEST. */
- old_last = cached_last_copy_of[dest_ver];
- new_last = get_last_copy_of (dest);
- cached_last_copy_of[dest_ver] = new_last;
-
- return (old_last != new_last);
+ return false;
}
dump_copy_of (FILE *file, tree var)
{
tree val;
- sbitmap visited;
print_generic_expr (file, var, dump_flags);
-
if (TREE_CODE (var) != SSA_NAME)
return;
- visited = sbitmap_alloc (num_ssa_names);
- sbitmap_zero (visited);
- SET_BIT (visited, SSA_NAME_VERSION (var));
-
+ val = copy_of[SSA_NAME_VERSION (var)].value;
fprintf (file, " copy-of chain: ");
-
- val = var;
- print_generic_expr (file, val, 0);
+ print_generic_expr (file, var, 0);
fprintf (file, " ");
- while (copy_of[SSA_NAME_VERSION (val)].value)
+ if (!val)
+ fprintf (file, "[UNDEFINED]");
+ else if (val == var)
+ fprintf (file, "[NOT A COPY]");
+ else
{
fprintf (file, "-> ");
- val = copy_of[SSA_NAME_VERSION (val)].value;
print_generic_expr (file, val, 0);
fprintf (file, " ");
- if (TEST_BIT (visited, SSA_NAME_VERSION (val)))
- break;
- SET_BIT (visited, SSA_NAME_VERSION (val));
+ fprintf (file, "[COPY]");
}
-
- val = get_copy_of_val (var)->value;
- if (val == NULL_TREE)
- fprintf (file, "[UNDEFINED]");
- else if (val != var)
- fprintf (file, "[COPY]");
- else
- fprintf (file, "[NOT A COPY]");
-
- sbitmap_free (visited);
}
/* Evaluate the RHS of STMT. If it produces a valid copy, set the LHS
- value and store the LHS into *RESULT_P. If STMT generates more
- than one name (i.e., STMT is an aliased store), it is enough to
- store the first name in the VDEF list into *RESULT_P. After
- all, the names generated will be VUSEd in the same statements. */
+ value and store the LHS into *RESULT_P. */
static enum ssa_prop_result
copy_prop_visit_assignment (gimple stmt, tree *result_p)
{
tree lhs, rhs;
- prop_value_t *rhs_val;
lhs = gimple_assign_lhs (stmt);
- rhs = gimple_assign_rhs1 (stmt);
-
-
- gcc_assert (gimple_assign_rhs_code (stmt) == SSA_NAME);
-
- rhs_val = get_copy_of_val (rhs);
+ rhs = valueize_val (gimple_assign_rhs1 (stmt));
if (TREE_CODE (lhs) == SSA_NAME)
{
if (!may_propagate_copy (lhs, rhs))
return SSA_PROP_VARYING;
- /* Notice that in the case of assignments, we make the LHS be a
- copy of RHS's value, not of RHS itself. This avoids keeping
- unnecessary copy-of chains (assignments cannot be in a cycle
- like PHI nodes), speeding up the propagation process.
- This is different from what we do in copy_prop_visit_phi_node.
- In those cases, we are interested in the copy-of chains. */
*result_p = lhs;
- if (set_copy_of_val (*result_p, rhs_val->value))
+ if (set_copy_of_val (*result_p, rhs))
return SSA_PROP_INTERESTING;
else
return SSA_PROP_NOT_INTERESTING;
are predicates involving two SSA_NAMEs. */
if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME)
{
- op0 = get_last_copy_of (op0);
- op1 = get_last_copy_of (op1);
+ op0 = valueize_val (op0);
+ op1 = valueize_val (op1);
/* See if we can determine the predicate's value. */
if (dump_file && (dump_flags & TDF_DETAILS))
if (gimple_assign_single_p (stmt)
&& TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
- && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
+ && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
+ || is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
{
/* If the statement is a copy assignment, evaluate its RHS to
see if the lattice value of its output has changed. */
{
enum ssa_prop_result retval;
unsigned i;
- prop_value_t phi_val = { 0, NULL_TREE };
+ prop_value_t phi_val = { NULL_TREE };
tree lhs = gimple_phi_result (phi);
{
fprintf (dump_file, "\nVisiting PHI node: ");
print_gimple_stmt (dump_file, phi, 0, dump_flags);
- fprintf (dump_file, "\n\n");
}
for (i = 0; i < gimple_phi_num_args (phi); i++)
{
prop_value_t *arg_val;
+ tree arg_value;
tree arg = gimple_phi_arg_def (phi, i);
edge e = gimple_phi_arg_edge (phi, i);
if (!(e->flags & EDGE_EXECUTABLE))
continue;
- /* Constants in the argument list never generate a useful copy.
- Similarly, names that flow through abnormal edges cannot be
- used to derive copies. */
- if (TREE_CODE (arg) != SSA_NAME || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg))
+ /* Names that flow through abnormal edges cannot be used to
+ derive copies. */
+ if (TREE_CODE (arg) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg))
{
phi_val.value = lhs;
break;
}
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "\tArgument #%d: ", i);
+ dump_copy_of (dump_file, arg);
+ fprintf (dump_file, "\n");
+ }
+
+ if (TREE_CODE (arg) == SSA_NAME)
+ {
+ arg_val = get_copy_of_val (arg);
+
+ /* If we didn't visit the definition of arg yet treat it as
+ UNDEFINED. This also handles PHI arguments that are the
+ same as lhs. We'll come here again. */
+ if (!arg_val->value)
+ continue;
+
+ arg_value = arg_val->value;
+ }
+ else
+ arg_value = valueize_val (arg);
+
/* Avoid copy propagation from an inner into an outer loop.
Otherwise, this may move loop variant variables outside of
their loops and prevent coalescing opportunities. If the
value was loop invariant, it will be hoisted by LICM and
- exposed for copy propagation. Not a problem for virtual
- operands though. */
- if (is_gimple_reg (lhs)
- && loop_depth_of_name (arg) > loop_depth_of_name (lhs))
+ exposed for copy propagation.
+ ??? The value will be always loop invariant.
+ In loop-closed SSA form do not copy-propagate through
+ PHI nodes in blocks with a loop exit edge predecessor. */
+ if (current_loops
+ && TREE_CODE (arg_value) == SSA_NAME
+ && (loop_depth_of_name (arg_value) > loop_depth_of_name (lhs)
+ || (loops_state_satisfies_p (LOOP_CLOSED_SSA)
+ && loop_exit_edge_p (e->src->loop_father, e))))
{
phi_val.value = lhs;
break;
}
- /* If the LHS appears in the argument list, ignore it. It is
- irrelevant as a copy. */
- if (arg == lhs || get_last_copy_of (arg) == lhs)
- continue;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\tArgument #%d: ", i);
- dump_copy_of (dump_file, arg);
- fprintf (dump_file, "\n");
- }
-
- arg_val = get_copy_of_val (arg);
-
/* If the LHS didn't have a value yet, make it a copy of the
- first argument we find. Notice that while we make the LHS be
- a copy of the argument itself, we take the memory reference
- from the argument's value so that we can compare it to the
- memory reference of all the other arguments. */
+ first argument we find. */
if (phi_val.value == NULL_TREE)
{
- phi_val.value = arg_val->value ? arg_val->value : arg;
+ phi_val.value = arg_value;
continue;
}
/* If PHI_VAL and ARG don't have a common copy-of chain, then
- this PHI node cannot be a copy operation. Also, if we are
- copy propagating stores and these two arguments came from
- different memory references, they cannot be considered
- copies. */
- if (get_last_copy_of (phi_val.value) != get_last_copy_of (arg))
+ this PHI node cannot be a copy operation. */
+ if (phi_val.value != arg_value
+ && !operand_equal_p (phi_val.value, arg_value, 0))
{
phi_val.value = lhs;
break;
}
}
- if (phi_val.value && may_propagate_copy (lhs, phi_val.value)
+ if (phi_val.value
+ && may_propagate_copy (lhs, phi_val.value)
&& set_copy_of_val (lhs, phi_val.value))
retval = (phi_val.value != lhs) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
else
if (dump_file && (dump_flags & TDF_DETAILS))
{
- fprintf (dump_file, "\nPHI node ");
+ fprintf (dump_file, "PHI node ");
dump_copy_of (dump_file, lhs);
fprintf (dump_file, "\nTelling the propagator to ");
if (retval == SSA_PROP_INTERESTING)
}
-/* Initialize structures used for copy propagation. PHIS_ONLY is true
- if we should only consider PHI nodes as generating copy propagation
- opportunities. */
+/* Initialize structures used for copy propagation. */
static void
init_copy_prop (void)
copy_of = XCNEWVEC (prop_value_t, num_ssa_names);
- cached_last_copy_of = XCNEWVEC (tree, num_ssa_names);
-
FOR_EACH_BB (bb)
{
gimple_stmt_iterator si;
int depth = bb->loop_depth;
- bool loop_exit_p = false;
for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
{
Otherwise, this may move loop variant variables outside of
their loops and prevent coalescing opportunities. If the
value was loop invariant, it will be hoisted by LICM and
- exposed for copy propagation. */
+ exposed for copy propagation.
+ ??? This doesn't make sense. */
if (stmt_ends_bb_p (stmt))
prop_set_simulate_again (stmt, true);
else if (stmt_may_generate_copy (stmt)
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
if (!prop_simulate_again_p (stmt))
set_copy_of_val (def, def);
- else
- cached_last_copy_of[SSA_NAME_VERSION (def)] = def;
- }
-
- /* In loop-closed SSA form do not copy-propagate through
- PHI nodes in blocks with a loop exit edge predecessor. */
- if (current_loops
- && loops_state_satisfies_p (LOOP_CLOSED_SSA))
- {
- edge_iterator ei;
- edge e;
- FOR_EACH_EDGE (e, ei, bb->preds)
- if (loop_exit_edge_p (e->src->loop_father, e))
- loop_exit_p = true;
}
for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
tree def;
def = gimple_phi_result (phi);
- if (!is_gimple_reg (def)
- || loop_exit_p)
+ if (!is_gimple_reg (def))
prop_set_simulate_again (phi, false);
else
prop_set_simulate_again (phi, true);
if (!prop_simulate_again_p (phi))
set_copy_of_val (def, def);
- else
- cached_last_copy_of[SSA_NAME_VERSION (def)] = def;
}
}
}
+/* Callback for substitute_and_fold to get at the final copy-of values. */
+
+static tree
+get_value (tree name)
+{
+ tree val = copy_of[SSA_NAME_VERSION (name)].value;
+ if (val && val != name)
+ return val;
+ return NULL_TREE;
+}
/* Deallocate memory used in copy propagation and do final
substitution. */
static void
fini_copy_prop (void)
{
- size_t i;
- prop_value_t *tmp;
+ unsigned i;
/* Set the final copy-of value for each variable by traversing the
copy-of chains. */
- tmp = XCNEWVEC (prop_value_t, num_ssa_names);
for (i = 1; i < num_ssa_names; i++)
{
tree var = ssa_name (i);
|| copy_of[i].value == var)
continue;
- tmp[i].value = get_last_copy_of (var);
-
/* In theory the points-to solution of all members of the
copy chain is their intersection. For now we do not bother
to compute this but only make sure we do not lose points-to
information completely by setting the points-to solution
of the representative to the first solution we find if
it doesn't have one already. */
- if (tmp[i].value != var
+ if (copy_of[i].value != var
+ && TREE_CODE (copy_of[i].value) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (var))
&& SSA_NAME_PTR_INFO (var)
- && !SSA_NAME_PTR_INFO (tmp[i].value))
- duplicate_ssa_name_ptr_info (tmp[i].value, SSA_NAME_PTR_INFO (var));
+ && !SSA_NAME_PTR_INFO (copy_of[i].value))
+ duplicate_ssa_name_ptr_info (copy_of[i].value, SSA_NAME_PTR_INFO (var));
}
- substitute_and_fold (tmp, NULL);
+ /* Don't do DCE if we have loops. That's the simplest way to not
+ destroy the scev cache. */
+ substitute_and_fold (get_value, NULL, !current_loops);
- free (cached_last_copy_of);
free (copy_of);
- free (tmp);
}
through edges marked executable by the propagation engine. So,
when visiting statement #2 for the first time, we will only look at
the first argument (a_24) and optimistically assume that its value
- is the copy of a_24 (x_1).
-
- The problem with this approach is that it may fail to discover copy
- relations in PHI cycles. Instead of propagating copy-of
- values, we actually propagate copy-of chains. For instance:
-
- A_3 = B_1;
- C_9 = A_3;
- D_4 = C_9;
- X_i = D_4;
-
- In this code fragment, COPY-OF (X_i) = { D_4, C_9, A_3, B_1 }.
- Obviously, we are only really interested in the last value of the
- chain, however the propagator needs to access the copy-of chain
- when visiting PHI nodes.
-
- To represent the copy-of chain, we use the array COPY_CHAINS, which
- holds the first link in the copy-of chain for every variable.
- If variable X_i is a copy of X_j, which in turn is a copy of X_k,
- the array will contain:
-
- COPY_CHAINS[i] = X_j
- COPY_CHAINS[j] = X_k
- COPY_CHAINS[k] = X_k
-
- Keeping copy-of chains instead of copy-of values directly becomes
- important when visiting PHI nodes. Suppose that we had the
- following PHI cycle, such that x_52 is already considered a copy of
- x_53:
-
- 1 x_54 = PHI <x_53, x_52>
- 2 x_53 = PHI <x_898, x_54>
-
- Visit #1: x_54 is copy-of x_53 (because x_52 is copy-of x_53)
- Visit #2: x_53 is copy-of x_898 (because x_54 is a copy of x_53,
- so it is considered irrelevant
- as a copy).
- Visit #1: x_54 is copy-of nothing (x_53 is a copy-of x_898 and
- x_52 is a copy of x_53, so
- they don't match)
- Visit #2: x_53 is copy-of nothing
-
- This problem is avoided by keeping a chain of copies, instead of
- the final copy-of value. Propagation will now only keep the first
- element of a variable's copy-of chain. When visiting PHI nodes,
- arguments are considered equal if their copy-of chains end in the
- same variable. So, as long as their copy-of chains overlap, we
- know that they will be a copy of the same variable, regardless of
- which variable that may be).
-
- Propagation would then proceed as follows (the notation a -> b
- means that a is a copy-of b):
-
- Visit #1: x_54 = PHI <x_53, x_52>
- x_53 -> x_53
- x_52 -> x_53
- Result: x_54 -> x_53. Value changed. Add SSA edges.
-
- Visit #1: x_53 = PHI <x_898, x_54>
- x_898 -> x_898
- x_54 -> x_53
- Result: x_53 -> x_898. Value changed. Add SSA edges.
-
- Visit #2: x_54 = PHI <x_53, x_52>
- x_53 -> x_898
- x_52 -> x_53 -> x_898
- Result: x_54 -> x_898. Value changed. Add SSA edges.
-
- Visit #2: x_53 = PHI <x_898, x_54>
- x_898 -> x_898
- x_54 -> x_898
- Result: x_53 -> x_898. Value didn't change. Stable state
-
- Once the propagator stabilizes, we end up with the desired result
- x_53 and x_54 are both copies of x_898. */
+ is the copy of a_24 (x_1). */
static unsigned int
execute_copy_prop (void)
OSDN Git Service
