This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] Fix PR26135, store copyprop being not effective
- From: Richard Guenther <rguenther at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Date: Wed, 8 Feb 2006 14:16:44 +0100 (CET)
- Subject: Re: [PATCH] Fix PR26135, store copyprop being not effective
- References: <Pine.LNX.4.63.0602071642000.6210@t148.fhfr.qr>
On Tue, 7 Feb 2006, Richard Guenther wrote:
> This adds the missing parts to the copyprop implementation to do store
> copyprop.
>
> Bootstrapped and tested on x86_64-unknown-linux-gnu, plain and with
> -fno-tree-dominator-opts (as most store copyprop opportunities are
> already handled by DOM).
And here is an alternative patch, killing current store copyprop and
replacing it with a more powerful one walking virtual use-def chains
(but at the same time making the stores propagation barriers due to
limitation to single-outputs of the propagator).
As this is (with this patch) only done for store-copyprop and
store-copyprop runs very late (we could move it before PRE I suppose),
I'm currently re-doing SPEC testing.
Bootstrapped and tested on x86_64-unknown-linux-gnu.
I have a similar patch for tree-ssa-ccp.c, which would allow us to
kill mem_ref in prop_value_t. Also it looks like get_stmt_rhs_def_stmt
could be used by tree-ssa-pre.c:try_look_through_load or
get_stmt_rhs_def_stmt could be extended to allow multiple VUSEs.
Comments?
Thanks,
Richard.
2006-02-08 Richard Guenther <rguenther@suse.de>
* tree-flow.h (get_stmt_rhs_def_stmt): Declare.
(offset_overlaps_with_access): Likewise.
* tree-flow-inline.h (offset_overlaps_with_access): New
inline function definition.
* tree-ssa-structalias.c (offset_overlaps_with_access):
Remove.
* tree-dfa.c (get_ref_base_and_extent): Remove assertion.
Deal with structures ending in arrays and such unknown
extent.
(get_stmt_rhs_def_stmt): New helper walking virtual
use-def chains.
* tree-ssa-copy.c (stmt_may_generate_copy): Handle
memory load stmts.
(copy_prop_visit_stmt): Deal with memory load stmts, do not
simulate stores.
(copy_prop_visit_assignment): Remove store copyprop code.
(copy_prop_visit_phi_node): Remove store copyprop code.
Index: tree-flow-inline.h
===================================================================
*** tree-flow-inline.h (revision 110745)
--- tree-flow-inline.h (working copy)
*************** overlap_subvar (unsigned HOST_WIDE_INT o
*** 1525,1528 ****
--- 1525,1548 ----
}
+
+ /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
+ overlaps with a field at [FIELDPOS, FIELDSIZE] */
+
+ static inline bool
+ offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
+ const unsigned HOST_WIDE_INT fieldsize,
+ const unsigned HOST_WIDE_INT accesspos,
+ const unsigned HOST_WIDE_INT accesssize)
+ {
+ if (fieldpos == accesspos && fieldsize == accesssize)
+ return true;
+ if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize))
+ return true;
+ if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
+ return true;
+
+ return false;
+ }
+
#endif /* _TREE_FLOW_INLINE_H */
Index: tree-dfa.c
===================================================================
*** tree-dfa.c (revision 110745)
--- tree-dfa.c (working copy)
*************** get_ref_base_and_extent (tree exp, HOST_
*** 913,920 ****
HOST_WIDE_INT maxsize = -1;
tree size_tree = NULL_TREE;
tree bit_offset = bitsize_zero_node;
!
! gcc_assert (!SSA_VAR_P (exp));
/* First get the final access size from just the outermost expression. */
if (TREE_CODE (exp) == COMPONENT_REF)
--- 913,919 ----
HOST_WIDE_INT maxsize = -1;
tree size_tree = NULL_TREE;
tree bit_offset = bitsize_zero_node;
! bool seen_variable_array_ref = false;
/* First get the final access size from just the outermost expression. */
if (TREE_CODE (exp) == COMPONENT_REF)
*************** get_ref_base_and_extent (tree exp, HOST_
*** 1004,1009 ****
--- 1003,1011 ----
fold_convert (bitsizetype, index),
bitsize_unit_node);
bit_offset = size_binop (PLUS_EXPR, bit_offset, index);
+ /* A more outer constant index array ref subsumes any
+ variable array ref seen sofar. */
+ seen_variable_array_ref = false;
}
else
{
*************** get_ref_base_and_extent (tree exp, HOST_
*** 1019,1024 ****
--- 1021,1028 ----
}
else
maxsize = -1;
+ /* Remember we seen an array ref with a variable index. */
+ seen_variable_array_ref = true;
}
}
break;
*************** get_ref_base_and_extent (tree exp, HOST_
*** 1043,1048 ****
--- 1047,1067 ----
}
done:
+ /* We need to deal with variable arrays ending structures such as
+ struct { int length; int a[1]; } x; x.a[d]
+ struct { struct { int a; int b; } a[1]; } x; x.a[d].a
+ struct { struct { int a[1]; } a[1]; } x; x.a[0][d], x.a[d][0]
+ where we do not know maxsize for variable index accesses to
+ the array. The simplest way to conservatively deal with this
+ is to punt in the case that offset + maxsize reaches the
+ base type boundary. */
+ if (seen_variable_array_ref
+ && maxsize != -1
+ && host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)
+ && TREE_INT_CST_LOW (bit_offset) + maxsize
+ == TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))))
+ maxsize = -1;
+
/* ??? Due to negative offsets in ARRAY_REF we can end up with
negative bit_offset here. We might want to store a zero offset
in this case. */
*************** get_ref_base_and_extent (tree exp, HOST_
*** 1052,1054 ****
--- 1071,1140 ----
return exp;
}
+
+ /* Return the defining stmt for the rhs of STMT following the virtual
+ use-def chains. Returns the MODIFY_EXPR stmt which rhs is equal
+ to the lhs of STMT or NULL_TREE if no such stmt can be found. */
+
+ tree
+ get_stmt_rhs_def_stmt (tree stmt)
+ {
+ /* See if we know exactly where this comes from. */
+ tree def, rhs;
+ tree base;
+ HOST_WIDE_INT offset, size, maxsize;
+ tree base2;
+ HOST_WIDE_INT offset2, size2, maxsize2;
+ use_operand_p use;
+
+ gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR);
+
+ rhs = TREE_OPERAND (stmt, 1);
+
+ /* If we don't know where this comes from, bail out. */
+ base = get_ref_base_and_extent (rhs, &offset, &size, &maxsize);
+ if (size == -1 || size != maxsize)
+ return NULL_TREE;
+
+ /* The stmt must have a single VUSE. */
+ use = SINGLE_SSA_USE_OPERAND (stmt, SSA_OP_VUSE);
+ if (use == NULL_USE_OPERAND_P)
+ return NULL_TREE;
+
+ do
+ {
+ /* Look at the DEF for the VUSE and see if it matches this USE
+ and if it's RHS is an SSA_NAME. Don't try to deal with
+ PHI_NODEs. */
+ def = SSA_NAME_DEF_STMT (*use->use);
+ if (TREE_CODE (def) != MODIFY_EXPR)
+ return NULL_TREE;
+
+ base2 = get_ref_base_and_extent (TREE_OPERAND (def, 0), &offset2,
+ &size2, &maxsize2);
+ /* If the base of the DEF does not match that of the USE it may
+ be a clobber. Bail out in this case. */
+ if (!operand_equal_p (base, base2, 0))
+ return NULL_TREE;
+
+ /* If the access touches our read, this has to be the one we're
+ interested in. Bail out if it is not. */
+ if (offset_overlaps_with_access (offset, size, offset2, maxsize2))
+ {
+ /* If the DEF is not exact and matches, bail out. */
+ if (maxsize2 != size2
+ || size2 != size || offset2 != offset)
+ return NULL_TREE;
+
+ /* For now just handle a distance of one. If the RHS of the DEF
+ is another ref, we could recurse here.
+ ??? Recurse here? */
+ return def;
+ }
+
+ /* Else just skip it and search for the next one. */
+ use = SINGLE_SSA_USE_OPERAND (def, SSA_OP_VMAYUSE);
+ if (use == NULL_USE_OPERAND_P)
+ return NULL_TREE;
+ } while (1);
+ }
Index: tree-ssa-copy.c
===================================================================
*** tree-ssa-copy.c (revision 110745)
--- tree-ssa-copy.c (working copy)
*************** stmt_may_generate_copy (tree stmt)
*** 376,382 ****
/* 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 TREE_CODE (rhs) == SSA_NAME && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs);
}
--- 376,385 ----
/* 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 (do_store_copy_prop
! && TREE_CODE (lhs) == SSA_NAME)
! || (TREE_CODE (rhs) == SSA_NAME
! && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs));
}
*************** copy_prop_visit_assignment (tree stmt, t
*** 570,604 ****
else
return SSA_PROP_NOT_INTERESTING;
}
- else if (stmt_makes_single_store (stmt))
- {
- /* Otherwise, set the names in V_MAY_DEF/V_MUST_DEF operands
- to be a copy of RHS. */
- ssa_op_iter i;
- tree vdef;
- bool changed;
-
- /* This should only be executed when doing store copy-prop. */
- gcc_assert (do_store_copy_prop);
-
- /* Set the value of every VDEF to RHS_VAL. */
- changed = false;
- FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, i, SSA_OP_VIRTUAL_DEFS)
- changed |= set_copy_of_val (vdef, rhs_val->value, lhs);
-
- /* Note that for propagation purposes, we are only interested in
- visiting statements that load the exact same memory reference
- stored here. Those statements will have the exact same list
- of virtual uses, so it is enough to set the output of this
- statement to be its first virtual definition. */
- *result_p = first_vdef (stmt);
-
- if (changed)
- return SSA_PROP_INTERESTING;
- else
- return SSA_PROP_NOT_INTERESTING;
- }
-
return SSA_PROP_VARYING;
}
--- 573,578 ----
*************** copy_prop_visit_stmt (tree stmt, edge *t
*** 684,697 ****
ann = stmt_ann (stmt);
if (TREE_CODE (stmt) == MODIFY_EXPR
! && TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME
! && (do_store_copy_prop
! || TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME))
{
/* If the statement is a copy assignment, evaluate its RHS to
see if the lattice value of its output has changed. */
retval = copy_prop_visit_assignment (stmt, result_p);
}
else if (TREE_CODE (stmt) == COND_EXPR)
{
/* See if we can determine which edge goes out of a conditional
--- 658,699 ----
ann = stmt_ann (stmt);
if (TREE_CODE (stmt) == MODIFY_EXPR
! && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
! && TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME)
{
/* If the statement is a copy assignment, evaluate its RHS to
see if the lattice value of its output has changed. */
retval = copy_prop_visit_assignment (stmt, result_p);
}
+ else if (TREE_CODE (stmt) == MODIFY_EXPR
+ && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
+ && do_store_copy_prop
+ && stmt_makes_single_load (stmt))
+ {
+ /* If the statement is a copy assignment with a memory load
+ on the RHS, see if we know the value of this load and
+ update the lattice accordingly. Due to the inability of
+ the propagation engine to deal with multiple outputs use
+ the value from the RHS of the def stmt, not its lattice
+ value. This way a propagated store acts as a propagation
+ barrier. */
+ tree val = get_stmt_rhs_def_stmt (stmt);
+ if (val
+ && is_gimple_reg (TREE_OPERAND (val, 1)))
+ {
+ bool changed = set_copy_of_val (TREE_OPERAND (stmt, 0),
+ TREE_OPERAND (val, 1), NULL_TREE);
+ if (changed)
+ {
+ *result_p = TREE_OPERAND (stmt, 0);
+ retval = SSA_PROP_INTERESTING;
+ }
+ else
+ retval = SSA_PROP_NOT_INTERESTING;
+ }
+ else
+ retval = SSA_PROP_VARYING;
+ }
else if (TREE_CODE (stmt) == COND_EXPR)
{
/* See if we can determine which edge goes out of a conditional
*************** copy_prop_visit_phi_node (tree phi)
*** 804,814 ****
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)
! || (do_store_copy_prop
! && phi_val.mem_ref
! && arg_val->mem_ref
! && simple_cst_equal (phi_val.mem_ref, arg_val->mem_ref) != 1))
{
phi_val.value = lhs;
break;
--- 806,812 ----
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))
{
phi_val.value = lhs;
break;
Index: tree-flow.h
===================================================================
*** tree-flow.h (revision 110745)
--- tree-flow.h (working copy)
*************** static inline bool ref_contains_array_re
*** 607,616 ****
--- 607,622 ----
static inline bool array_ref_contains_indirect_ref (tree);
extern tree get_ref_base_and_extent (tree, HOST_WIDE_INT *,
HOST_WIDE_INT *, HOST_WIDE_INT *);
+ extern tree get_stmt_rhs_def_stmt (tree stmt);
static inline bool var_can_have_subvars (tree);
static inline bool overlap_subvar (unsigned HOST_WIDE_INT,
unsigned HOST_WIDE_INT,
subvar_t, bool *);
+ static inline bool
+ offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
+ const unsigned HOST_WIDE_INT fieldsize,
+ const unsigned HOST_WIDE_INT accesspos,
+ const unsigned HOST_WIDE_INT accesssize);
/* Call-back function for walk_use_def_chains(). At each reaching
definition, a function with this prototype is called. */
Index: tree-ssa-structalias.c
===================================================================
*** tree-ssa-structalias.c (revision 110745)
--- tree-ssa-structalias.c (working copy)
*************** bitpos_of_field (const tree fdecl)
*** 2317,2342 ****
+ tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
}
-
- /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
- overlaps with a field at [FIELDPOS, FIELDSIZE] */
-
- static bool
- offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
- const unsigned HOST_WIDE_INT fieldsize,
- const unsigned HOST_WIDE_INT accesspos,
- const unsigned HOST_WIDE_INT accesssize)
- {
- if (fieldpos == accesspos && fieldsize == accesssize)
- return true;
- if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize))
- return true;
- if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
- return true;
-
- return false;
- }
-
/* Given a COMPONENT_REF T, return the constraint_expr for it. */
static void
--- 2317,2322 ----