[PATCH] Make sure copy-prop runs before forwprop, do not propagate ADDR_EXPRs to simple copy statements
Richard Guenther
rguenther@suse.de
Thu Mar 15 13:18:00 GMT 2007
This patch rewrites the code from forwprop that would
propagate ADDR_EXPRs to simple copies (to work around the not fully
copypropped IL) even if they have multiple uses. Like
int *pi = &Foo.i[i];
int *q1 = pi;
int *q2 = pi;
int *q3 = pi;
int *q4 = pi;
foobar(q1,q2,q3,q4);
where it would propagate &Foo.i[i] into all rhs. This is bad as it
causes interesting optimization oscillations between this and the
previous form.
Instead of doing so, we now recurse to look for propagation opportunities
on the uses of the simple copies. This is still necessary and profitable
as even if we were fully copyproped by copyprop we miss copyprop
opportunities due to different type variants.
While re-structuring the code I updated the patch for PR31146 which made
us propagate to conversion expressions to this same scheme.
The interesting non-renaming parts of the patch are after
- /* Trivial case.
and
+ /* Remove intermediate now unused copy and conversion chains. */
Bootstrapped and tested on x86_64-unknown-linux-gnu. I'll apply this
to mainline after giving people some time to comment.
Thanks,
Richard.
2007-03-12 Richard Guenther <rguenther@suse.de>
PR tree-optimization/31146
* tree-ssa-forwprop.c (forward_propagate_addr_expr_1): Restructure
to allow recursion of forward_propagate_addr_expr.
(forward_propagate_addr_into_variable_array_index): Likewise.
(forward_propagate_addr_expr): Likewise.
(tree_ssa_forward_propagate_single_use_vars): Likewise.
(forward_propagate_addr_expr_1): Recurse on simple copies
instead of propagating into them. Do so for useless conversions
as well.
(forward_propagate_addr_expr): Clean up unused statements after
recursion.
* g++.dg/tree-ssa/pr31146.C: New testcase.
Index: gcc/tree-ssa-forwprop.c
===================================================================
--- gcc.orig/tree-ssa-forwprop.c 2007-03-14 16:33:41.000000000 +0100
+++ gcc/tree-ssa-forwprop.c 2007-03-15 11:32:52.000000000 +0100
@@ -149,6 +149,7 @@ Boston, MA 02110-1301, USA. */
This will (of course) be extended as other needs arise. */
+static bool forward_propagate_addr_expr (tree name, tree rhs);
/* Set to true if we delete EH edges during the optimization. */
static bool cfg_changed;
@@ -591,7 +592,7 @@ tidy_after_forward_propagate_addr (tree
mark_symbols_for_renaming (stmt);
}
-/* STMT defines LHS which is contains the address of the 0th element
+/* DEF_RHS defines LHS which is contains the address of the 0th element
in an array. USE_STMT uses LHS to compute the address of an
arbitrary element within the array. The (variable) byte offset
of the element is contained in OFFSET.
@@ -608,7 +609,7 @@ tidy_after_forward_propagate_addr (tree
static bool
forward_propagate_addr_into_variable_array_index (tree offset, tree lhs,
- tree stmt, tree use_stmt)
+ tree def_rhs, tree use_stmt)
{
tree index;
@@ -650,8 +651,7 @@ forward_propagate_addr_into_variable_arr
index = TREE_OPERAND (offset, 0);
/* Replace the pointer addition with array indexing. */
- GIMPLE_STMT_OPERAND (use_stmt, 1)
- = unshare_expr (GIMPLE_STMT_OPERAND (stmt, 1));
+ GIMPLE_STMT_OPERAND (use_stmt, 1) = unshare_expr (def_rhs);
TREE_OPERAND (TREE_OPERAND (GIMPLE_STMT_OPERAND (use_stmt, 1), 0), 1)
= index;
@@ -662,7 +662,8 @@ forward_propagate_addr_into_variable_arr
return true;
}
-/* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
+/* NAME is a SSA_NAME representing DEF_RHS which is of the form
+ ADDR_EXPR <whatever>.
Try to forward propagate the ADDR_EXPR into the use USE_STMT.
Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
@@ -672,9 +673,8 @@ forward_propagate_addr_into_variable_arr
be not totally successful, yet things may have been changed). */
static bool
-forward_propagate_addr_expr_1 (tree stmt, tree use_stmt)
+forward_propagate_addr_expr_1 (tree name, tree def_rhs, tree use_stmt)
{
- tree name = GIMPLE_STMT_OPERAND (stmt, 0);
tree lhs, rhs, array_ref;
/* Strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
@@ -683,36 +683,37 @@ forward_propagate_addr_expr_1 (tree stmt
while (TREE_CODE (lhs) == COMPONENT_REF || TREE_CODE (lhs) == ARRAY_REF)
lhs = TREE_OPERAND (lhs, 0);
+ rhs = GIMPLE_STMT_OPERAND (use_stmt, 1);
+
/* Now see if the LHS node is an INDIRECT_REF using NAME. If so,
propagate the ADDR_EXPR into the use of NAME and fold the result. */
if (TREE_CODE (lhs) == INDIRECT_REF && TREE_OPERAND (lhs, 0) == name)
{
/* This should always succeed in creating gimple, so there is
no need to save enough state to undo this propagation. */
- TREE_OPERAND (lhs, 0) = unshare_expr (GIMPLE_STMT_OPERAND (stmt, 1));
+ TREE_OPERAND (lhs, 0) = unshare_expr (def_rhs);
fold_stmt_inplace (use_stmt);
tidy_after_forward_propagate_addr (use_stmt);
- }
- /* Trivial case. The use statement could be a trivial copy. We
- go ahead and handle that case here since it's trivial and
- removes the need to run copy-prop before this pass to get
- the best results. Also note that by handling this case here
- we can catch some cascading effects, ie the single use is
- in a copy, and the copy is used later by a single INDIRECT_REF
- for example. */
- else if (TREE_CODE (lhs) == SSA_NAME
- && GIMPLE_STMT_OPERAND (use_stmt, 1) == name)
- {
- GIMPLE_STMT_OPERAND (use_stmt, 1)
- = unshare_expr (GIMPLE_STMT_OPERAND (stmt, 1));
- tidy_after_forward_propagate_addr (use_stmt);
- return true;
- }
+ /* The only case we did not replace all uses this way is if the
+ use statement is of the form *name = name. */
+ return rhs != name;
+ }
+
+ /* Trivial case. The use statement could be a trivial copy or a
+ useless conversion. Recurse to the uses of the lhs as copyprop does
+ not copy through differen variant pointers and FRE does not catch
+ all useless conversions. */
+ else if ((TREE_CODE (lhs) == SSA_NAME
+ && rhs == name)
+ || ((TREE_CODE (rhs) == NOP_EXPR
+ || TREE_CODE (rhs) == CONVERT_EXPR)
+ && tree_ssa_useless_type_conversion_1 (TREE_TYPE (rhs),
+ TREE_TYPE (def_rhs))))
+ return forward_propagate_addr_expr (lhs, def_rhs);
/* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
nodes from the RHS. */
- rhs = GIMPLE_STMT_OPERAND (use_stmt, 1);
while (TREE_CODE (rhs) == COMPONENT_REF
|| TREE_CODE (rhs) == ARRAY_REF
|| TREE_CODE (rhs) == ADDR_EXPR)
@@ -724,7 +725,7 @@ forward_propagate_addr_expr_1 (tree stmt
{
/* This should always succeed in creating gimple, so there is
no need to save enough state to undo this propagation. */
- TREE_OPERAND (rhs, 0) = unshare_expr (GIMPLE_STMT_OPERAND (stmt, 1));
+ TREE_OPERAND (rhs, 0) = unshare_expr (def_rhs);
fold_stmt_inplace (use_stmt);
tidy_after_forward_propagate_addr (use_stmt);
return true;
@@ -734,7 +735,7 @@ forward_propagate_addr_expr_1 (tree stmt
array indexing. They only apply when we have the address of
element zero in an array. If that is not the case then there
is nothing to do. */
- array_ref = TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt, 1), 0);
+ array_ref = TREE_OPERAND (def_rhs, 0);
if (TREE_CODE (array_ref) != ARRAY_REF
|| TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE
|| !integer_zerop (TREE_OPERAND (array_ref, 1)))
@@ -751,7 +752,7 @@ forward_propagate_addr_expr_1 (tree stmt
&& TREE_CODE (TREE_OPERAND (rhs, 1)) == INTEGER_CST)
{
tree orig = unshare_expr (rhs);
- TREE_OPERAND (rhs, 0) = unshare_expr (GIMPLE_STMT_OPERAND (stmt, 1));
+ TREE_OPERAND (rhs, 0) = unshare_expr (def_rhs);
/* If folding succeeds, then we have just exposed new variables
in USE_STMT which will need to be renamed. If folding fails,
@@ -783,7 +784,7 @@ forward_propagate_addr_expr_1 (tree stmt
tree offset_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 1));
res = forward_propagate_addr_into_variable_array_index (offset_stmt, lhs,
- stmt, use_stmt);
+ def_rhs, use_stmt);
return res;
}
@@ -798,7 +799,7 @@ forward_propagate_addr_expr_1 (tree stmt
bool res;
tree offset_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
res = forward_propagate_addr_into_variable_array_index (offset_stmt, lhs,
- stmt, use_stmt);
+ def_rhs, use_stmt);
return res;
}
return false;
@@ -812,10 +813,9 @@ forward_propagate_addr_expr_1 (tree stmt
Returns true, if all uses have been propagated into. */
static bool
-forward_propagate_addr_expr (tree stmt)
+forward_propagate_addr_expr (tree name, tree rhs)
{
- int stmt_loop_depth = bb_for_stmt (stmt)->loop_depth;
- tree name = GIMPLE_STMT_OPERAND (stmt, 0);
+ int stmt_loop_depth = bb_for_stmt (SSA_NAME_DEF_STMT (name))->loop_depth;
imm_use_iterator iter;
tree use_stmt;
bool all = true;
@@ -843,10 +843,22 @@ forward_propagate_addr_expr (tree stmt)
push_stmt_changes (&use_stmt);
- result = forward_propagate_addr_expr_1 (stmt, use_stmt);
+ result = forward_propagate_addr_expr_1 (name, rhs, use_stmt);
all &= result;
pop_stmt_changes (&use_stmt);
+
+ /* Remove intermediate now unused copy and conversion chains. */
+ if (result
+ && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 0)) == SSA_NAME
+ && (TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == SSA_NAME
+ || TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == NOP_EXPR
+ || TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == CONVERT_EXPR))
+ {
+ block_stmt_iterator bsi = bsi_for_stmt (use_stmt);
+ release_defs (use_stmt);
+ bsi_remove (&bsi, true);
+ }
}
return all;
@@ -981,7 +993,7 @@ tree_ssa_forward_propagate_single_use_va
if (TREE_CODE (rhs) == ADDR_EXPR)
{
- if (forward_propagate_addr_expr (stmt))
+ if (forward_propagate_addr_expr (lhs, rhs))
{
release_defs (stmt);
todoflags |= TODO_remove_unused_locals;
Index: gcc/testsuite/g++.dg/tree-ssa/pr31146.C
===================================================================
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ gcc/testsuite/g++.dg/tree-ssa/pr31146.C 2007-03-15 11:38:31.000000000 +0100
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-forwprop1" } */
+
+/* We should be able to optimize this to i[j] = 1 during
+ early optimizations. */
+
+int i[5];
+void foo (int j)
+{
+ void *p = &i[j];
+ int *q = (int *)p;
+ *q = 1;
+}
+
+/* { dg-final { scan-tree-dump "i\\\[j.*\\\] = 1;" "forwprop1" } } */
+/* { dg-final { cleanup-tree-dump "forwprop1" } } */
More information about the Gcc-patches
mailing list