@@ -1,5 +1,29 @@
2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
+ * graphite-dependences.c (new_poly_dr): Call ppl_powerset_is_empty.
+ (build_lexicographical_constraint): Same.
+ (dependence_polyhedron_1): Same.
+ (graphite_legal_transform_dr): Same.
+ (graphite_carried_dependence_level_k): Same.
+ * graphite-ppl.c (ppl_powerset_is_empty): New.
+ * graphite-ppl.h (ppl_powerset_is_empty): Declared.
+ * tree-data-ref.c (dump_data_reference): Print the basic block index.
+
+ * gcc.dg/graphite/block-0.c: Add documentation.
+ * gcc.dg/graphite/block-4.c: Same.
+ * gcc.dg/graphite/block-7.c: Same.
+ * gcc.dg/graphite/block-8.c: New.
+ * gcc.dg/graphite/interchange-1.c: Un-XFAILed.
+ * gcc.dg/graphite/interchange-11.c: Un-XFAILed.
+ * gcc.dg/graphite/interchange-12.c: Add documentation.
+ * gcc.dg/graphite/interchange-13.c: New.
+ * gcc.dg/graphite/interchange-14.c: New.
+ * gcc.dg/graphite/interchange-15.c: New.
+ * gcc.dg/graphite/interchange-8.c: Add documentation.
+ * gcc.dg/graphite/interchange-mvt.c: Same.
+
+2011-01-15 Sebastian Pop <sebastian.pop@amd.com>
+
* graphite-dependences.c (build_pairwise_scheduling): Correctly compute
the "a followed by b" relation and document it.
@@ -54,7 +54,9 @@ new_poly_ddr (poly_dr_p source, poly_dr_p sink,
PDDR_DDP (pddr) = ddp;
PDDR_ORIGINAL_SCATTERING_P (pddr) = original_scattering_p;
- if (!ddp || ppl_Pointset_Powerset_C_Polyhedron_is_empty (ddp))
+ if (!ddp
+ || ppl_powerset_is_empty (ddp,
+ scop_nb_params (PBB_SCOP (PDR_PBB (source)))))
PDDR_KIND (pddr) = no_dependence;
else
PDDR_KIND (pddr) = has_dependence;
@@ -395,13 +397,14 @@ build_pairwise_scheduling (graphite_dim_t dim,
the BAG polyhedron: T1|I1|T2|I2|S1|S2|G. When DIRECTION is set to
1, compute the direct dependence from PDR1 to PDR2, and when
DIRECTION is -1, compute the reversed dependence relation, from
- PDR2 to PDR1. */
+ PDR2 to PDR1. GDIM is the number of parameters in the scop. */
static ppl_Pointset_Powerset_C_Polyhedron_t
build_lexicographical_constraint (ppl_Pointset_Powerset_C_Polyhedron_t bag,
graphite_dim_t dim,
graphite_dim_t tdim,
graphite_dim_t offset,
+ graphite_dim_t gdim,
int direction)
{
graphite_dim_t i;
@@ -412,7 +415,7 @@ build_lexicographical_constraint (ppl_Pointset_Powerset_C_Polyhedron_t bag,
lex = build_pairwise_scheduling (dim, 0, offset, direction);
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag);
- if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (lex))
+ if (!ppl_powerset_is_empty (lex, gdim))
ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex);
ppl_delete_Pointset_Powerset_C_Polyhedron (lex);
@@ -425,13 +428,13 @@ build_lexicographical_constraint (ppl_Pointset_Powerset_C_Polyhedron_t bag,
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (bag, sceq);
ppl_delete_Pointset_Powerset_C_Polyhedron (sceq);
- if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (bag))
+ if (ppl_powerset_is_empty (bag, gdim))
break;
lex = build_pairwise_scheduling (dim, i + 1, offset, direction);
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag);
- if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (lex))
+ if (!ppl_powerset_is_empty (lex, gdim))
ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex);
ppl_delete_Pointset_Powerset_C_Polyhedron (lex);
@@ -510,11 +513,11 @@ dependence_polyhedron_1 (poly_dr_p pdr1, poly_dr_p pdr2,
ppl_delete_Pointset_Powerset_C_Polyhedron (idr2);
ppl_delete_Pointset_Powerset_C_Polyhedron (dreq);
- if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (res))
+ if (!ppl_powerset_is_empty (res, gdim))
{
ppl_Pointset_Powerset_C_Polyhedron_t lex =
build_lexicographical_constraint (res, dim, MIN (tdim1, tdim2),
- tdim1 + ddim1, direction);
+ tdim1 + ddim1, gdim, direction);
ppl_delete_Pointset_Powerset_C_Polyhedron (res);
res = lex;
}
@@ -683,7 +686,8 @@ graphite_legal_transform_dr (poly_dr_p pdr1, poly_dr_p pdr2)
ppl_insert_dimensions_pointset (pt, otdim1 + ttdim1 + ddim1, otdim2);
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po_temp, pt);
- is_empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (po_temp);
+ is_empty_p = ppl_powerset_is_empty (po_temp,
+ scop_nb_params (PBB_SCOP (pbb1)));
ppl_delete_Pointset_Powerset_C_Polyhedron (po_temp);
free_poly_ddr (tpddr);
@@ -911,7 +915,8 @@ graphite_carried_dependence_level_k (poly_dr_p pdr1, poly_dr_p pdr2,
eqpp = build_pairwise_scheduling (dim, level, tdim1 + ddim1, 1);
ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp, po);
- empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (eqpp);
+ empty_p = ppl_powerset_is_empty
+ (eqpp, scop_nb_params (PBB_SCOP (PDR_PBB (pdr1))));
ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp);
free_poly_ddr (pddr);
@@ -515,4 +515,77 @@ debug_gmp_value (mpz_t val)
(*gmp_free) (str, strlen (str) + 1);
}
+/* Checks for integer feasibility: returns true when the powerset
+ polyhedron PS has no integer solutions. NB_PARAMS is the number of
+ dimensions used as parameters in PS. If DIM is the dimension of
+ PS, the parameter dimensions are in between DIM - NB_PARAMS and
+ DIM. */
+
+bool
+ppl_powerset_is_empty (ppl_Pointset_Powerset_C_Polyhedron_t ps,
+ int nb_params ATTRIBUTE_UNUSED)
+{
+#if PPL_VERSION_MAJOR == 0 && PPL_VERSION_MINOR < 11
+ /* On PPL 0.10,
+ ppl_Pointset_Powerset_C_Polyhedron_contains_integer_point (ps)
+ takes too long on some cases and so we call _is_empty instead. */
+ return ppl_Pointset_Powerset_C_Polyhedron_is_empty (ps);
+
+#else
+ /* On PPL 0.11 or later, we can check for integer feasibility using
+ the PIP solver. */
+ ppl_PIP_Problem_t pip;
+ ppl_dimension_type d;
+ ppl_const_Constraint_System_t pcs;
+ ppl_Constraint_System_const_iterator_t first, last;
+ ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end;
+ int i;
+ bool has_integer_solutions = false;
+ ppl_dimension_type *ds;
+ int dim_first_parameter;
+
+ if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (ps))
+ return true;
+
+ ppl_Pointset_Powerset_C_Polyhedron_space_dimension (ps, &d);
+ dim_first_parameter = d - nb_params;
+ ds = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, nb_params);
+
+ for (i = 0; i < nb_params; i++)
+ ds[i] = dim_first_parameter + i;
+
+ ppl_new_Constraint_System_const_iterator (&first);
+ ppl_new_Constraint_System_const_iterator (&last);
+ ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it);
+ ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end);
+
+ for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it),
+ ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end);
+ !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end);
+ ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it))
+ {
+ ppl_const_Polyhedron_t ph;
+ ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph);
+
+ ppl_Polyhedron_get_constraints (ph, &pcs);
+ ppl_Constraint_System_begin (pcs, first);
+ ppl_Constraint_System_end (pcs, last);
+
+ ppl_new_PIP_Problem_from_constraints (&pip, d, first, last, nb_params, ds);
+ has_integer_solutions |= ppl_PIP_Problem_is_satisfiable (pip);
+
+ ppl_delete_PIP_Problem (pip);
+ }
+
+ ppl_delete_Constraint_System_const_iterator (first);
+ ppl_delete_Constraint_System_const_iterator (last);
+ ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it);
+ ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end);
+ if (ds)
+ free (ds);
+
+ return !has_integer_solutions;
+#endif
+}
+
#endif
@@ -47,6 +47,8 @@ void ppl_min_for_le_pointset (ppl_Pointset_Powerset_C_Polyhedron_t,
ppl_Constraint_t ppl_build_relation (int, int, int, int,
enum ppl_enum_Constraint_Type);
void debug_gmp_value (mpz_t);
+bool ppl_powerset_is_empty (ppl_Pointset_Powerset_C_Polyhedron_t, int);
+
/* Assigns to RES the value of the INTEGER_CST T. */
@@ -12,6 +12,7 @@ foo (void)
int j;
int i;
+ /* This should be blocked. */
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
a[j] = a[i] + 1;
@@ -15,11 +15,13 @@ foo (void)
{
int i, j, k;
+ /* This should NOT be blocked: each loop iterates only 24 times. */
for (i = 0; i < 24; i++)
for (j = 0; j < 24; j++)
for (k = 0; k < 24; k++)
A[i][j] = B[i][k] * C[k][j];
+ /* This should be blocked. */
for (i = 0; i < M; i++)
for (j = 0; j < M; j++)
for (k = 0; k < M; k++)
@@ -14,6 +14,7 @@ matmult (void)
{
int i, j, k;
+ /* This should be blocked. */
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
{
new file mode 100644
@@ -0,0 +1,58 @@
+/* { dg-require-effective-target size32plus } */
+
+#define DEBUG 0
+#if DEBUG
+#include <stdio.h>
+#endif
+
+#define N 200
+
+int A[N][N], B[N][N], C[N][N];
+
+static void __attribute__((noinline))
+matmult (void)
+{
+ int i, j, k;
+
+ for (i = 0; i < N; i++)
+ for (j = 0; j < N; j++)
+ A[i][j] = 0;
+
+ /* This should be blocked. */
+ for (i = 0; i < N; i++)
+ for (j = 0; j < N; j++)
+ for (k = 0; k < N; k++)
+ A[i][j] += B[i][k] * C[k][j];
+}
+
+extern void abort ();
+
+int
+main (void)
+{
+ int i, j, res = 0;
+
+ for (i = 0; i < N; i++)
+ for (j = 0; j < N; j++)
+ {
+ B[i][j] = j;
+ C[i][j] = i;
+ }
+
+ matmult ();
+
+ for (i = 0; i < N; i++)
+ res += A[i][i];
+
+#if DEBUG
+ fprintf (stderr, "res = %d \n", res);
+#endif
+
+ if (res != 529340000)
+ abort ();
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "will be loop blocked" 1 "graphite" { xfail *-*-* } } } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
@@ -15,6 +15,7 @@ foo (int N)
int i, j;
double sum = 0.0;
+ /* These two loops should be interchanged. */
for (i = 0; i < N; i++)
{
for (j = 0; j < N; j++)
@@ -48,6 +49,5 @@ main (void)
return 0;
}
-
-/* { 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" } } */
@@ -13,6 +13,7 @@ foo (int N, int *res)
int i, j;
double sum = 0.0;
+ /* These two loops should be interchanged. */
for (i = 0; i < 1335; i++)
{
for (j = 0; j < 1335; j++)
@@ -45,5 +46,5 @@ main (void)
return 0;
}
-/* { 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" } } */
@@ -14,6 +14,8 @@ matmult (void)
{
int i, j, k;
+ /* This should be interchanged twice: (i, k) and (j, i). The
+ resulting nest should look like this (k, i, j). */
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
{
@@ -52,5 +54,5 @@ main (void)
return 0;
}
-/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump-times "will be interchanged" 2 "graphite" { xfail *-*-* } } } */
/* { dg-final { cleanup-tree-dump "graphite" } } */
new file mode 100644
@@ -0,0 +1,54 @@
+/* { dg-require-effective-target size32plus } */
+
+/* Formerly known as ltrans-1.c */
+
+#define DEBUG 0
+#if DEBUG
+#include <stdio.h>
+#endif
+
+double u[25];
+
+static int __attribute__((noinline))
+foo (int N)
+{
+ int i, j;
+ double sum = 0.0;
+
+ /* These two loops should be interchanged. */
+ for (i = 0; i < N; i++)
+ {
+ for (j = 0; j < N; j++)
+ sum = sum + u[i + 5 * j];
+
+ u[6 * i] *= 2;
+ }
+
+ return sum + N + u[6];
+}
+
+extern void abort ();
+
+int
+main (void)
+{
+ int i, j, res;
+
+ for (i = 0; i < 25; i++)
+ u[i] = 2;
+
+ res = foo (5);
+
+#if DEBUG
+ fprintf (stderr, "res = %d \n", res);
+#endif
+
+ if (res != 59)
+ abort ();
+
+ return 0;
+}
+
+
+/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" } } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
new file mode 100644
@@ -0,0 +1,59 @@
+/* { dg-require-effective-target size32plus } */
+
+#define DEBUG 0
+#if DEBUG
+#include <stdio.h>
+#endif
+
+#define N 200
+
+int A[N][N], B[N][N], C[N][N];
+
+static void __attribute__((noinline))
+matmult (void)
+{
+ int i, j, k;
+
+ for (i = 0; i < N; i++)
+ for (j = 0; j < N; j++)
+ A[i][j] = 0;
+
+ /* This should be interchanged twice: (i, k) and (j, i). The
+ resulting nest should look like this (k, i, j). */
+ for (i = 0; i < N; i++)
+ for (j = 0; j < N; j++)
+ for (k = 0; k < N; k++)
+ A[i][j] += B[i][k] * C[k][j];
+}
+
+extern void abort ();
+
+int
+main (void)
+{
+ int i, j, res = 0;
+
+ for (i = 0; i < N; i++)
+ for (j = 0; j < N; j++)
+ {
+ B[i][j] = j;
+ C[i][j] = i;
+ }
+
+ matmult ();
+
+ for (i = 0; i < N; i++)
+ res += A[i][i];
+
+#if DEBUG
+ fprintf (stderr, "res = %d \n", res);
+#endif
+
+ if (res != 529340000)
+ abort ();
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "will be interchanged" 2 "graphite" { xfail *-*-* } } } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
new file mode 100644
@@ -0,0 +1,53 @@
+/* { dg-require-effective-target size32plus } */
+
+#define DEBUG 0
+#if DEBUG
+#include <stdio.h>
+#endif
+
+#define NMAX 2000
+
+static int x[NMAX], a[NMAX][NMAX];
+
+static int __attribute__((noinline))
+mvt (long N)
+{
+ int i,j;
+
+ /* These two loops should be interchanged. */
+ for (i = 0; i < N; i++)
+ for (j = 0; j < N; j++)
+ x[i] += a[j][i];
+
+ return x[1];
+}
+
+extern void abort ();
+
+int
+main (void)
+{
+ int i, j, res;
+
+ for (i = 0; i < NMAX; i++)
+ for (j = 0; j < NMAX; j++)
+ a[i][j] = j;
+
+ for (i = 0; i < NMAX; i++)
+ x[i] = i;
+
+ res = mvt (NMAX);
+
+#if DEBUG
+ fprintf (stderr, "res = %d \n", res);
+#endif
+
+ if (res != 2001)
+ abort ();
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" { xfail *-*-* } } } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
+
@@ -11,6 +11,7 @@ foo (void)
{
int i, j, k, l;
+ /* Loops K and L should be interchanged. */
for (l = 0; l < 4; l++)
{
for (k = 0; k < 4; k++)
@@ -80,6 +81,5 @@ main (void)
return 0;
}
-/* Loops K and L should be interchanged. */
/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" { xfail *-*-* } } } */
/* { dg-final { cleanup-tree-dump "graphite" } } */
@@ -19,6 +19,7 @@ mvt (long N)
for (j = 0; j < N; j++)
x1[i] = x1[i] + a[i][j] * y1[j];
+ /* These two loops should be interchanged. */
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
x2[i] = x2[i] + a[j][i] * y2[j];
@@ -193,7 +193,9 @@ dump_data_reference (FILE *outf,
{
unsigned int i;
- fprintf (outf, "#(Data Ref: \n# stmt: ");
+ fprintf (outf, "#(Data Ref: \n");
+ fprintf (outf, "# bb: %d \n", gimple_bb (DR_STMT (dr))->index);
+ fprintf (outf, "# stmt: ");
print_gimple_stmt (outf, DR_STMT (dr), 0, 0);
fprintf (outf, "# ref: ");
print_generic_stmt (outf, DR_REF (dr), 0);