* graphite-dependences.c (reduction_dr_1): New.
(reduction_dr_p): New.
(graphite_legal_transform_dr): Call reduction_dr_p.
(reduction_ddr): Renamed reduction_ddr_p.
* graphite-poly.h (same_pdr_p): New.
(number_of_write_pdrs): New.
* graphite-sese-to-poly.c (nb_data_writes_in_bb): New.
(split_reduction_stmt): Do not split reduction statements
when there are no writes to memory.
(translate_scalar_reduction_to_array_for_stmt): Insert the
memory reduction statement just after the scalar reduction statement.
* gcc.dg/graphite/interchange-10.c: Updated to differ from interchange-4.c.
Un-XFAIL-ed.
* gcc.dg/graphite/interchange-3.c: Un-XFAIL-ed.
* gcc.dg/graphite/interchange-4.c: Un-XFAIL-ed.
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@154564
138bc75d-0d04-0410-961f-
82ee72b054a4
2009-10-06 Sebastian Pop <sebastian.pop@amd.com>
+ * graphite-dependences.c (reduction_dr_1): New.
+ (reduction_dr_p): New.
+ (graphite_legal_transform_dr): Call reduction_dr_p.
+ (reduction_ddr): Renamed reduction_ddr_p.
+ * graphite-poly.h (same_pdr_p): New.
+ (number_of_write_pdrs): New.
+ * graphite-sese-to-poly.c (nb_data_writes_in_bb): New.
+ (split_reduction_stmt): Do not split reduction statements
+ when there are no writes to memory.
+ (translate_scalar_reduction_to_array_for_stmt): Insert the
+ memory reduction statement just after the scalar reduction statement.
+
+ * gcc.dg/graphite/interchange-10.c: Updated to differ from interchange-4.c.
+ Un-XFAIL-ed.
+ * gcc.dg/graphite/interchange-3.c: Un-XFAIL-ed.
+ * gcc.dg/graphite/interchange-4.c: Un-XFAIL-ed.
+
+2009-10-06 Sebastian Pop <sebastian.pop@amd.com>
+
* graphite-interchange.c (lst_apply_interchange): New.
(lst_interchange_profitable_p): New.
(lst_try_interchange_loops): New.
return pddr;
}
+/* Return true when the data dependence relation between the data
+ references PDR1 belonging to PBB1 and PDR2 is part of a
+ reduction. */
+
+static inline bool
+reduction_dr_1 (poly_bb_p pbb1, poly_dr_p pdr1, poly_dr_p pdr2)
+{
+ int i;
+ poly_dr_p pdr;
+
+ /* PBB1 should be a reduction PBB. Reduction PBBs should have only
+ one write. */
+ gcc_assert (PBB_IS_REDUCTION (pbb1)
+ && number_of_write_pdrs (pbb1) == 1);
+
+ for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr); i++)
+ if (PDR_TYPE (pdr) == PDR_WRITE)
+ break;
+
+ return same_pdr_p (pdr, pdr1) && same_pdr_p (pdr, pdr2);
+}
+
+/* Return true when the data dependence relation between the data
+ references PDR1 belonging to PBB1 and PDR2 belonging to PBB2 is
+ part of a reduction. */
+
+static inline bool
+reduction_dr_p (poly_bb_p pbb1, poly_bb_p pbb2,
+ poly_dr_p pdr1, poly_dr_p pdr2)
+{
+ if (PBB_IS_REDUCTION (pbb1))
+ return reduction_dr_1 (pbb1, pdr1, pdr2);
+
+ if (PBB_IS_REDUCTION (pbb2))
+ return reduction_dr_1 (pbb2, pdr2, pdr1);
+
+ return false;
+}
+
/* Returns true when the PBB_TRANSFORMED_SCATTERING functions of PBB1
and PBB2 respect the data dependences of PBB_ORIGINAL_SCATTERING
functions. */
ppl_Pointset_Powerset_C_Polyhedron_t d1 = PBB_DOMAIN (pbb1);
ppl_Pointset_Powerset_C_Polyhedron_t d2 = PBB_DOMAIN (pbb2);
+ if (reduction_dr_p (pbb1, pbb2, pdr1, pdr2))
+ return true;
+
pddr = pddr_original_scattering (pbb1, pbb2, pdr1, pdr2);
if (!pddr)
return true;
part of a reduction. */
static inline bool
-reduction_ddr (poly_bb_p pbb1, poly_bb_p pbb2)
+reduction_ddr_p (poly_bb_p pbb1, poly_bb_p pbb2)
{
return pbb1 == pbb2 && PBB_IS_REDUCTION (pbb1);
}
if (!PBB_PDR_DUPLICATES_REMOVED (pbb2))
pbb_remove_duplicate_pdrs (pbb2);
- if (reduction_ddr (pbb1, pbb2))
+ if (reduction_ddr_p (pbb1, pbb2))
return true;
for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++)
return PDR_TYPE (pdr) == PDR_MAY_WRITE;
}
+/* Return true when PDR1 and PDR2 are similar data accesses: they have
+ the same base array, and the same access functions. */
+
+static inline bool
+same_pdr_p (poly_dr_p pdr1, poly_dr_p pdr2)
+{
+ return PDR_TYPE (pdr1) == PDR_TYPE (pdr2)
+ && PDR_NB_SUBSCRIPTS (pdr1) == PDR_NB_SUBSCRIPTS (pdr2)
+ && PDR_BASE_OBJECT_SET (pdr1) == PDR_BASE_OBJECT_SET (pdr2);
+}
+
typedef struct poly_scattering *poly_scattering_p;
struct poly_scattering
extern void pbb_number_of_iterations_at_time (poly_bb_p, graphite_dim_t, Value);
extern void pbb_remove_duplicate_pdrs (poly_bb_p);
+/* Return the number of write data references in PBB. */
+
+static inline int
+number_of_write_pdrs (poly_bb_p pbb)
+{
+ int res = 0;
+ int i;
+ poly_dr_p pdr;
+
+ for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
+ if (PDR_TYPE (pdr) == PDR_WRITE)
+ res++;
+
+ return res;
+}
+
/* The index of the PBB. */
static inline int
return res;
}
+/* Return the number of data references in BB that write in
+ memory. */
+
+static int
+nb_data_writes_in_bb (basic_block bb)
+{
+ int res = 0;
+ gimple_stmt_iterator gsi;
+
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ if (gimple_vdef (gsi_stmt (gsi)))
+ res++;
+
+ return res;
+}
+
/* Splits STMT out of its current BB. */
static basic_block
basic_block bb = gimple_bb (stmt);
edge e;
+ /* Do not split basic blocks with no writes to memory: the reduction
+ will be the only write to memory. */
+ if (nb_data_writes_in_bb (bb) == 0)
+ return bb;
+
split_block (bb, stmt);
gsi = gsi_last_bb (bb);
gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT);
assign = gimple_build_assign (red, gimple_assign_lhs (stmt));
- insert_gsi = gsi_last_bb (bb);
+ insert_gsi = gsi_for_stmt (stmt);
gsi_insert_after (&insert_gsi, assign, GSI_SAME_STMT);
}
*res = sum + N;
}
-/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" } } */
/* { dg-final { cleanup-tree-dump "graphite" } } */
{
int i, j;
double sum = 0;
- for (i = 0; i < N; i++)
+ for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
sum = sum + u[i + 1335 * j];
-
+
for (i = 0; i < N; i++)
u[1336 * i] *= 2;
*res = sum + N;
}
-/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" } } */
/* { dg-final { cleanup-tree-dump "graphite" } } */