[PATCH] Remove copy propagation restrictions on loops
Richard Biener
rguenther@suse.de
Tue Jul 8 09:18:00 GMT 2014
As promised and analyzed in the DOM thread the following patch
removes restriction on copy propagating through PHIs on loop
exits (when we don't have to preserve loop-closed SSA form).
Fallout in out-of-SSA coalescing has been dealt with there.
Bootstrapped and tested on x86_64-unknown-linux-gnu, applied.
Richard.
2014-07-08 Richard Biener <rguenther@suse.de>
* tree-ssa-dom.h (loop_depth_of_name): Remove.
* tree-ssa-dom.c (record_equivalences_from_phis): Remove
restriction on loop depth difference.
(record_equality): Likewise.
(propagate_rhs_into_lhs): Likewise. Simplify condition.
(loop_depth_of_name): Remove.
* tree-ssa-copy.c (copy_prop_visit_phi_node): Remove
restriction on loop depth difference.
(init_copy_prop): Likewise.
* gcc.dg/tree-ssa/ssa-pre-16.c: Adjust expected eliminations.
Index: gcc/tree-ssa-dom.c
===================================================================
--- gcc/tree-ssa-dom.c (revision 212065)
+++ gcc/tree-ssa-dom.c (working copy)
@@ -1235,12 +1235,7 @@ record_equivalences_from_phis (basic_blo
inferred from a comparison. All uses of this ssa name are dominated
by this assignment, so unwinding just costs time and space. */
if (i == gimple_phi_num_args (phi)
- && may_propagate_copy (lhs, rhs)
- /* Do not propagate copies if the propagated value is at a deeper loop
- depth than the propagatee. Otherwise, this may introduce uses
- of loop variant variables outside of their loops and prevent
- coalescing opportunities. */
- && !(loop_depth_of_name (rhs) > loop_depth_of_name (lhs)))
+ && may_propagate_copy (lhs, rhs))
set_ssa_name_value (lhs, rhs);
}
}
@@ -1575,33 +1570,6 @@ record_const_or_copy_1 (tree x, tree y,
const_and_copies_stack.quick_push (x);
}
-/* Return the loop depth of the basic block of the defining statement of X.
- This number should not be treated as absolutely correct because the loop
- information may not be completely up-to-date when dom runs. However, it
- will be relatively correct, and as more passes are taught to keep loop info
- up to date, the result will become more and more accurate. */
-
-int
-loop_depth_of_name (tree x)
-{
- gimple defstmt;
- basic_block defbb;
-
- /* If it's not an SSA_NAME, we have no clue where the definition is. */
- if (TREE_CODE (x) != SSA_NAME)
- return 0;
-
- /* Otherwise return the loop depth of the defining statement's bb.
- Note that there may not actually be a bb for this statement, if the
- ssa_name is live on entry. */
- defstmt = SSA_NAME_DEF_STMT (x);
- defbb = gimple_bb (defstmt);
- if (!defbb)
- return 0;
-
- return bb_loop_depth (defbb);
-}
-
/* Record that X is equal to Y in const_and_copies. Record undo
information in the block-local vector. */
@@ -1641,8 +1609,7 @@ record_equality (tree x, tree y)
long as we canonicalize on one value. */
if (is_gimple_min_invariant (y))
;
- else if (is_gimple_min_invariant (x)
- || (loop_depth_of_name (x) <= loop_depth_of_name (y)))
+ else if (is_gimple_min_invariant (x))
prev_x = x, x = y, y = prev_x, prev_x = prev_y;
else if (prev_x && is_gimple_min_invariant (prev_x))
x = y, y = prev_x, prev_x = prev_y;
@@ -2686,13 +2653,8 @@ get_lhs_or_phi_result (gimple stmt)
static void
propagate_rhs_into_lhs (gimple stmt, tree lhs, tree rhs, bitmap interesting_names)
{
- /* First verify that propagation is valid and isn't going to move a
- loop variant variable outside its loop. */
- if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)
- && (TREE_CODE (rhs) != SSA_NAME
- || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
- && may_propagate_copy (lhs, rhs)
- && loop_depth_of_name (lhs) >= loop_depth_of_name (rhs))
+ /* First verify that propagation is valid. */
+ if (may_propagate_copy (lhs, rhs))
{
use_operand_p use_p;
imm_use_iterator iter;
Index: gcc/tree-ssa-copy.c
===================================================================
--- gcc/tree-ssa-copy.c (revision 212065)
+++ gcc/tree-ssa-copy.c (working copy)
@@ -400,15 +400,11 @@ copy_prop_visit_phi_node (gimple phi)
else
arg_value = valueize_val (arg);
- /* Avoid copy propagation from an inner into an outer loop.
- Otherwise, this may introduce uses of loop variant variables
- outside of their loops and prevent coalescing opportunities.
- In loop-closed SSA form do not copy-propagate through
- PHI nodes in blocks with a loop exit edge predecessor. */
- if (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))))
+ /* In loop-closed SSA form do not copy-propagate SSA-names across
+ loop exit edges. */
+ if (loops_state_satisfies_p (LOOP_CLOSED_SSA)
+ && TREE_CODE (arg_value) == SSA_NAME
+ && loop_exit_edge_p (e->src->loop_father, e))
{
phi_val.value = lhs;
break;
@@ -470,7 +466,6 @@ init_copy_prop (void)
FOR_EACH_BB_FN (bb, cfun)
{
gimple_stmt_iterator si;
- int depth = bb_loop_depth (bb);
for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
{
@@ -481,21 +476,10 @@ init_copy_prop (void)
/* The only statements that we care about are those that may
generate useful copies. We also need to mark conditional
jumps so that their outgoing edges are added to the work
- lists of the propagator.
-
- 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.
- ??? This doesn't make sense. */
+ lists of the propagator. */
if (stmt_ends_bb_p (stmt))
prop_set_simulate_again (stmt, true);
- else if (stmt_may_generate_copy (stmt)
- /* Since we are iterating over the statements in
- BB, not the phi nodes, STMT will always be an
- assignment. */
- && loop_depth_of_name (gimple_assign_rhs1 (stmt)) <= depth)
+ else if (stmt_may_generate_copy (stmt))
prop_set_simulate_again (stmt, true);
else
prop_set_simulate_again (stmt, false);
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-16.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-16.c (revision 212065)
+++ gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-16.c (working copy)
@@ -11,5 +11,5 @@ int foo(int k, int *x)
} while (++j<k);
return res;
}
-/* { dg-final { scan-tree-dump-times "Eliminated: 2" 1 "pre"} } */
+/* { dg-final { scan-tree-dump-times "Eliminated: 1" 1 "pre"} } */
/* { dg-final { cleanup-tree-dump "pre" } } */
More information about the Gcc-patches
mailing list