On Wed, Mar 16, 2011 at 7:49 AM, Ira Rosen <ira.ro...@linaro.org> wrote:
> Hi,
>
> This patch adds a support of conditional store sinking for cases with
> multiple data references in then and else basic blocks. The
> correctness of the transformation is checked by verifying that there
> are no read-after-write and write-after-write dependencies.
>
> Bootstrapped and tested on powerpc64-suse-linux.
> OK for trunk?
I will look at the patch later, but can you add a testcase that we don't sink
if (..)
{
*a = i;
*b = j;
}
else
{
*b = j;
*a = i;
}
if *a and *b may alias?
Thanks,
Richard.
> Thanks,
> Ira
>
> ChangeLog:
>
> * tree-data-ref.c (dr_equal_offsets_p1): Moved and renamed from
> tree-vect-data-refs.c vect_equal_offsets.
> (dr_equal_offsets_p): New function.
> * tree-data-ref.h (dr_equal_offsets_p): Declare.
> * tree-vect-data-refs.c (vect_equal_offsets): Move to tree-data-ref.c.
> (vect_drs_dependent_in_basic_block): Update calls to vect_equal_offsets.
> (vect_check_interleaving): Likewise.
> * tree-ssa-phiopt.c: Include cfgloop.h and tree-data-ref.h.
> (cond_if_else_store_replacement): Rename to...
> (cond_if_else_store_replacement_1): ... this. Change arguments and
> documentation.
> (cond_if_else_store_replacement): New function.
> * Makefile.in (tree-ssa-phiopt.o): Adjust dependencies.
>
> testsuite/ChangeLog:
>
> * gcc.dg/vect/vect-cselim-1.c: New test.
>
> Index: tree-data-ref.c
> ===================================================================
> --- tree-data-ref.c (revision 170712)
> +++ tree-data-ref.c (working copy)
> @@ -991,6 +991,48 @@ create_data_ref (loop_p nest, loop_p loop, tree me
> return dr;
> }
>
> +/* Check if OFFSET1 and OFFSET2 (DR_OFFSETs of some data-refs) are identical
> + expressions. */
> +static bool
> +dr_equal_offsets_p1 (tree offset1, tree offset2)
> +{
> + bool res;
> +
> + STRIP_NOPS (offset1);
> + STRIP_NOPS (offset2);
> +
> + if (offset1 == offset2)
> + return true;
> +
> + if (TREE_CODE (offset1) != TREE_CODE (offset2)
> + || (!BINARY_CLASS_P (offset1) && !UNARY_CLASS_P (offset1)))
> + return false;
> +
> + res = dr_equal_offsets_p1 (TREE_OPERAND (offset1, 0),
> + TREE_OPERAND (offset2, 0));
> +
> + if (!res || !BINARY_CLASS_P (offset1))
> + return res;
> +
> + res = dr_equal_offsets_p1 (TREE_OPERAND (offset1, 1),
> + TREE_OPERAND (offset2, 1));
> +
> + return res;
> +}
> +
> +/* Check if DRA and DRB have equal offsets. */
> +bool
> +dr_equal_offsets_p (struct data_reference *dra,
> + struct data_reference *drb)
> +{
> + tree offset1, offset2;
> +
> + offset1 = DR_OFFSET (dra);
> + offset2 = DR_OFFSET (drb);
> +
> + return dr_equal_offsets_p1 (offset1, offset2);
> +}
> +
> /* Returns true if FNA == FNB. */
>
> static bool
> Index: tree-data-ref.h
> ===================================================================
> --- tree-data-ref.h (revision 170712)
> +++ tree-data-ref.h (working copy)
> @@ -430,6 +430,8 @@ extern void compute_all_dependences (VEC (data_ref
> extern void create_rdg_vertices (struct graph *, VEC (gimple, heap) *);
> extern bool dr_may_alias_p (const struct data_reference *,
> const struct data_reference *);
> +extern bool dr_equal_offsets_p (struct data_reference *,
> + struct data_reference *);
>
>
> /* Return true when the base objects of data references A and B are
> @@ -755,5 +757,4 @@ lambda_matrix_new (int m, int n, struct obstack *l
>
> return mat;
> }
> -
> #endif /* GCC_TREE_DATA_REF_H */
> Index: tree-vect-data-refs.c
> ===================================================================
> --- tree-vect-data-refs.c (revision 170712)
> +++ tree-vect-data-refs.c (working copy)
> @@ -289,39 +289,6 @@ vect_update_interleaving_chain (struct data_refere
> }
> }
>
> -
> -/* Function vect_equal_offsets.
> -
> - Check if OFFSET1 and OFFSET2 are identical expressions. */
> -
> -static bool
> -vect_equal_offsets (tree offset1, tree offset2)
> -{
> - bool res;
> -
> - STRIP_NOPS (offset1);
> - STRIP_NOPS (offset2);
> -
> - if (offset1 == offset2)
> - return true;
> -
> - if (TREE_CODE (offset1) != TREE_CODE (offset2)
> - || (!BINARY_CLASS_P (offset1) && !UNARY_CLASS_P (offset1)))
> - return false;
> -
> - res = vect_equal_offsets (TREE_OPERAND (offset1, 0),
> - TREE_OPERAND (offset2, 0));
> -
> - if (!res || !BINARY_CLASS_P (offset1))
> - return res;
> -
> - res = vect_equal_offsets (TREE_OPERAND (offset1, 1),
> - TREE_OPERAND (offset2, 1));
> -
> - return res;
> -}
> -
> -
> /* Check dependence between DRA and DRB for basic block vectorization.
> If the accesses share same bases and offsets, we can compare their initial
> constant offsets to decide whether they differ or not. In case of a read-
> @@ -352,7 +319,7 @@ vect_drs_dependent_in_basic_block (struct data_ref
> || TREE_CODE (DR_BASE_ADDRESS (drb)) != ADDR_EXPR
> || TREE_OPERAND (DR_BASE_ADDRESS (dra), 0)
> != TREE_OPERAND (DR_BASE_ADDRESS (drb),0)))
> - || !vect_equal_offsets (DR_OFFSET (dra), DR_OFFSET (drb)))
> + || !dr_equal_offsets_p (dra, drb))
> return true;
>
> /* Check the types. */
> @@ -402,7 +369,7 @@ vect_check_interleaving (struct data_reference *dr
> || TREE_CODE (DR_BASE_ADDRESS (drb)) != ADDR_EXPR
> || TREE_OPERAND (DR_BASE_ADDRESS (dra), 0)
> != TREE_OPERAND (DR_BASE_ADDRESS (drb),0)))
> - || !vect_equal_offsets (DR_OFFSET (dra), DR_OFFSET (drb))
> + || !dr_equal_offsets_p (dra, drb)
> || !tree_int_cst_compare (DR_INIT (dra), DR_INIT (drb))
> || DR_IS_READ (dra) != DR_IS_READ (drb))
> return false;
> Index: tree-ssa-phiopt.c
> ===================================================================
> --- tree-ssa-phiopt.c (revision 170734)
> +++ tree-ssa-phiopt.c (working copy)
> @@ -34,6 +34,8 @@ along with GCC; see the file COPYING3. If not see
> #include "langhooks.h"
> #include "pointer-set.h"
> #include "domwalk.h"
> +#include "cfgloop.h"
> +#include "tree-data-ref.h"
>
> static unsigned int tree_ssa_phiopt (void);
> static unsigned int tree_ssa_phiopt_worker (bool);
> @@ -1292,35 +1294,18 @@ cond_store_replacement (basic_block middle_bb, bas
> return true;
> }
>
> -/* Do the main work of conditional store replacement. We already know
> - that the recognized pattern looks like so:
> +/* Do the main work of conditional store replacement. */
>
> - split:
> - if (cond) goto THEN_BB; else goto ELSE_BB (edge E1)
> - THEN_BB:
> - X = Y;
> - goto JOIN_BB;
> - ELSE_BB:
> - X = Z;
> - fallthrough (edge E0)
> - JOIN_BB:
> - some more
> -
> - We check that THEN_BB and ELSE_BB contain only one store
> - that the stores have a "simple" RHS. */
> -
> static bool
> -cond_if_else_store_replacement (basic_block then_bb, basic_block else_bb,
> - basic_block join_bb)
> +cond_if_else_store_replacement_1 (basic_block then_bb, basic_block else_bb,
> + basic_block join_bb, gimple then_assign,
> + gimple else_assign)
> {
> - gimple then_assign = last_and_only_stmt (then_bb);
> - gimple else_assign = last_and_only_stmt (else_bb);
> tree lhs_base, lhs, then_rhs, else_rhs;
> source_location then_locus, else_locus;
> gimple_stmt_iterator gsi;
> gimple newphi, new_stmt;
>
> - /* Check if then_bb and else_bb contain only one store each. */
> if (then_assign == NULL
> || !gimple_assign_single_p (then_assign)
> || else_assign == NULL
> @@ -1385,6 +1370,151 @@ static bool
> return true;
> }
>
> +/* Conditional store replacement. We already know
> + that the recognized pattern looks like so:
> +
> + split:
> + if (cond) goto THEN_BB; else goto ELSE_BB (edge E1)
> + THEN_BB:
> + ...
> + X = Y;
> + ...
> + goto JOIN_BB;
> + ELSE_BB:
> + ...
> + X = Z;
> + ...
> + fallthrough (edge E0)
> + JOIN_BB:
> + some more
> +
> + We check that it is safe to sink the store to JOIN_BB by verifying that
> + there are no read-after-write or write-after-write dependencies in
> + THEN_BB and ELSE_BB. */
> +
> +static bool
> +cond_if_else_store_replacement (basic_block then_bb, basic_block else_bb,
> + basic_block join_bb)
> +{
> + gimple then_assign = last_and_only_stmt (then_bb);
> + gimple else_assign = last_and_only_stmt (else_bb);
> + VEC (data_reference_p, heap) *then_datarefs, *else_datarefs;
> + VEC (ddr_p, heap) *then_ddrs, *else_ddrs;
> + gimple then_store, else_store;
> + bool found, ok = false, res;
> + struct data_dependence_relation *ddr;
> + data_reference_p then_dr, else_dr;
> + int i, j;
> + tree then_lhs, else_lhs;
> +
> + /* Handle the case with single statement in THEN_BB and ELSE_BB. */
> + if (then_assign && else_assign)
> + return cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
> + then_assign, else_assign);
> +
> + then_datarefs = VEC_alloc (data_reference_p, heap, 1);
> + else_datarefs = VEC_alloc (data_reference_p, heap, 1);
> + then_ddrs = VEC_alloc (ddr_p, heap, 1);
> + else_ddrs = VEC_alloc (ddr_p, heap, 1);
> + if (!compute_data_dependences_for_bb (then_bb, false, &then_datarefs,
> + &then_ddrs)
> + || !compute_data_dependences_for_bb (else_bb, false, &else_datarefs,
> + &else_ddrs)
> + || !VEC_length (data_reference_p, then_datarefs)
> + || !VEC_length (data_reference_p, else_datarefs))
> + {
> + free_data_refs (then_datarefs);
> + free_data_refs (else_datarefs);
> + free_dependence_relations (then_ddrs);
> + free_dependence_relations (else_ddrs);
> + return false;
> + }
> +
> + /* Check that there are no read-after-write or write-after-write
> dependencies
> + in THEN_BB. */
> + FOR_EACH_VEC_ELT (ddr_p, then_ddrs, i, ddr)
> + {
> + struct data_reference *dra = DDR_A (ddr);
> + struct data_reference *drb = DDR_B (ddr);
> +
> + if (DDR_ARE_DEPENDENT (ddr) != chrec_known
> + && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
> + && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
> + || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
> + && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
> + || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
> + {
> + free_data_refs (then_datarefs);
> + free_data_refs (else_datarefs);
> + free_dependence_relations (then_ddrs);
> + free_dependence_relations (else_ddrs);
> + return false;
> + }
> + }
> +
> + /* Check that there are no read-after-write or write-after-write
> dependencies
> + in ELSE_BB. */
> + FOR_EACH_VEC_ELT (ddr_p, else_ddrs, i, ddr)
> + {
> + struct data_reference *dra = DDR_A (ddr);
> + struct data_reference *drb = DDR_B (ddr);
> +
> + if (DDR_ARE_DEPENDENT (ddr) != chrec_known
> + && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
> + && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
> + || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
> + && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
> + || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
> + {
> + free_data_refs (then_datarefs);
> + free_data_refs (else_datarefs);
> + free_dependence_relations (then_ddrs);
> + free_dependence_relations (else_ddrs);
> + return false;
> + }
> + }
> +
> + /* Found pairs of stores with equal LHS. */
> + FOR_EACH_VEC_ELT (data_reference_p, then_datarefs, i, then_dr)
> + {
> + if (DR_IS_READ (then_dr))
> + continue;
> +
> + then_store = DR_STMT (then_dr);
> + then_lhs = gimple_assign_lhs (then_store);
> + found = false;
> +
> + FOR_EACH_VEC_ELT (data_reference_p, else_datarefs, j, else_dr)
> + {
> + if (DR_IS_READ (else_dr))
> + continue;
> +
> + else_store = DR_STMT (else_dr);
> + else_lhs = gimple_assign_lhs (else_store);
> +
> + if (operand_equal_p (then_lhs, else_lhs, 0))
> + {
> + found = true;
> + break;
> + }
> + }
> +
> + if (!found)
> + continue;
> +
> + res = cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
> + then_store, else_store);
> + ok = ok || res;
> + }
> +
> + free_data_refs (then_datarefs);
> + free_data_refs (else_datarefs);
> + free_dependence_relations (then_ddrs);
> + free_dependence_relations (else_ddrs);
> +
> + return ok;
> +}
> +
> /* Always do these optimizations if we have SSA
> trees to work on. */
> static bool
> Index: Makefile.in
> ===================================================================
> --- Makefile.in (revision 170712)
> +++ Makefile.in (working copy)
> @@ -2422,7 +2422,8 @@ tree-ssa-ifcombine.o : tree-ssa-ifcombine.c $(CONF
> tree-ssa-phiopt.o : tree-ssa-phiopt.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
> $(TM_H) $(GGC_H) $(TREE_H) $(TM_P_H) $(BASIC_BLOCK_H) \
> $(TREE_FLOW_H) $(TREE_PASS_H) $(TREE_DUMP_H) langhooks.h $(FLAGS_H) \
> - $(DIAGNOSTIC_H) $(TIMEVAR_H) pointer-set.h domwalk.h
> + $(DIAGNOSTIC_H) $(TIMEVAR_H) pointer-set.h domwalk.h $(CFGLOOP_H) \
> + $(TREE_DATA_REF_H)
> tree-nrv.o : tree-nrv.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
> $(TM_H) $(TREE_H) $(FUNCTION_H) $(BASIC_BLOCK_H) $(FLAGS_H) \
> $(DIAGNOSTIC_H) $(TREE_FLOW_H) $(TIMEVAR_H) $(TREE_DUMP_H) $(TREE_PASS_H)
> \
> Index: testsuite/gcc.dg/vect/vect-cselim-1.c
> ===================================================================
> --- testsuite/gcc.dg/vect/vect-cselim-1.c (revision 0)
> +++ testsuite/gcc.dg/vect/vect-cselim-1.c (revision 0)
> @@ -0,0 +1,86 @@
> +/* { dg-require-effective-target vect_int } */
> +
> +#include <stdarg.h>
> +#include "tree-vect.h"
> +
> +#define N 50
> +
> +typedef struct {
> + short a;
> + short b;
> +} data;
> +
> +data in1[N], in2[N], out[N];
> +short result[N*2] =
> {7,-7,9,-6,11,-5,13,-4,15,-3,17,-2,19,-1,21,0,23,1,25,2,27,3,29,4,31,5,33,6,35,7,37,8,39,9,41,10,43,11,45,12,47,13,49,14,51,15,53,16,55,17,57,18,59,19,61,20,63,21,65,22,67,23,69,24,71,25,73,26,75,27,77,28,79,29,81,30,83,31,85,32,87,33,89,34,91,35,93,36,95,37,97,38,99,39,101,40,103,41,105,42};
> +short out1[N], out2[N];
> +
> +__attribute__ ((noinline)) void
> +foo ()
> +{
> + int i;
> + short c, d;
> +
> + /* Vectorizable with conditional store sinking. */
> + for (i = 0; i < N; i++)
> + {
> + c = in1[i].b;
> + d = in2[i].b;
> +
> + if (c >= d)
> + {
> + out[i].b = c;
> + out[i].a = d + 5;
> + }
> + else
> + {
> + out[i].b = d - 12;
> + out[i].a = c + d;
> + }
> + }
> +
> + /* Not vectorizable. */
> + for (i = 0; i < N; i++)
> + {
> + c = in1[i].b;
> + d = in2[i].b;
> +
> + if (c >= d)
> + {
> + out1[i] = c;
> + }
> + else
> + {
> + out2[i] = c + d;
> + }
> + }
> +}
> +
> +int
> +main (void)
> +{
> + int i;
> +
> + check_vect ();
> +
> + for (i = 0; i < N; i++)
> + {
> + in1[i].a = i;
> + in1[i].b = i + 2;
> + in2[i].a = 5;
> + in2[i].b = i + 5;
> + __asm__ volatile ("");
> + }
> +
> + foo ();
> +
> + for (i = 0; i < N; i++)
> + {
> + if (out[i].a != result[2*i] || out[i].b != result[2*i+1])
> + abort ();
> + }
> +
> + return 0;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */
> +/* { dg-final { cleanup-tree-dump "vect" } } */
>
