Patchwork [07/10] Use PIP to determine the integer feasibility of a constraint system.

login
register
mail settings
Submitter Sebastian Pop
Date Jan. 15, 2011, 9:05 a.m.
Message ID <1295082315-32242-8-git-send-email-sebpop@gmail.com>
Download mbox | patch
Permalink /patch/79042/
State New
Headers show

Comments

Sebastian Pop - Jan. 15, 2011, 9:05 a.m.
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.
---
 gcc/ChangeLog.graphite                          |   24 ++++++++
 gcc/graphite-dependences.c                      |   23 ++++---
 gcc/graphite-ppl.c                              |   73 +++++++++++++++++++++++
 gcc/graphite-ppl.h                              |    2 +
 gcc/testsuite/gcc.dg/graphite/block-0.c         |    1 +
 gcc/testsuite/gcc.dg/graphite/block-4.c         |    2 +
 gcc/testsuite/gcc.dg/graphite/block-7.c         |    1 +
 gcc/testsuite/gcc.dg/graphite/block-8.c         |   58 ++++++++++++++++++
 gcc/testsuite/gcc.dg/graphite/interchange-1.c   |    4 +-
 gcc/testsuite/gcc.dg/graphite/interchange-11.c  |    3 +-
 gcc/testsuite/gcc.dg/graphite/interchange-12.c  |    4 +-
 gcc/testsuite/gcc.dg/graphite/interchange-13.c  |   54 +++++++++++++++++
 gcc/testsuite/gcc.dg/graphite/interchange-14.c  |   59 ++++++++++++++++++
 gcc/testsuite/gcc.dg/graphite/interchange-15.c  |   53 ++++++++++++++++
 gcc/testsuite/gcc.dg/graphite/interchange-8.c   |    2 +-
 gcc/testsuite/gcc.dg/graphite/interchange-mvt.c |    1 +
 gcc/tree-data-ref.c                             |    4 +-
 17 files changed, 353 insertions(+), 15 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/graphite/block-8.c
 create mode 100644 gcc/testsuite/gcc.dg/graphite/interchange-13.c
 create mode 100644 gcc/testsuite/gcc.dg/graphite/interchange-14.c
 create mode 100644 gcc/testsuite/gcc.dg/graphite/interchange-15.c
Sven Verdoolaege - Jan. 15, 2011, 5:10 p.m.
On Sat, Jan 15, 2011 at 03:05:12AM -0600, Sebastian Pop wrote:
> +bool
> +ppl_powerset_is_empty (ppl_Pointset_Powerset_C_Polyhedron_t ps,
> +		       int nb_params ATTRIBUTE_UNUSED)

Why would you have to know the number of parameters to check
whether a set is empty?  That makes no sense.

skimo
Sebastian Pop - Jan. 15, 2011, 6:53 p.m.
On Sat, Jan 15, 2011 at 11:10, Sven Verdoolaege <skimo@kotnet.org> wrote:
> On Sat, Jan 15, 2011 at 03:05:12AM -0600, Sebastian Pop wrote:
>> +bool
>> +ppl_powerset_is_empty (ppl_Pointset_Powerset_C_Polyhedron_t ps,
>> +                    int nb_params ATTRIBUTE_UNUSED)
>
> Why would you have to know the number of parameters to check
> whether a set is empty?  That makes no sense.

To create a PIP problem, PPL asks for the dimensions containing parameters.
http://www.cs.unipr.it/ppl/Documentation/user/ppl-user-c-interface-0.11-html/interfaceppl__PIP__Problem__tag.html#a51082042eaafc2db84f50f28d3d5b646
In all the constraint systems, the parameters are the last nb_params dimensions.

Sebastian
Sven Verdoolaege - Jan. 15, 2011, 7:24 p.m.
On Sat, Jan 15, 2011 at 12:53:23PM -0600, Sebastian Pop wrote:
> On Sat, Jan 15, 2011 at 11:10, Sven Verdoolaege <skimo@kotnet.org> wrote:
> > On Sat, Jan 15, 2011 at 03:05:12AM -0600, Sebastian Pop wrote:
> >> +bool
> >> +ppl_powerset_is_empty (ppl_Pointset_Powerset_C_Polyhedron_t ps,
> >> +                    int nb_params ATTRIBUTE_UNUSED)
> >
> > Why would you have to know the number of parameters to check
> > whether a set is empty?  That makes no sense.
> 
> To create a PIP problem, PPL asks for the dimensions containing parameters.

So? Just tell it that there are no parameters (or that all dimensions
are parameters).  For checking whether a set is empty, it does not matter
whether a dimension represents a parameter or not.

skimo

Patch

diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index 86ba9c9..b844d04 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -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.
 
diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c
index 5e4e087..b7f9442 100644
--- a/gcc/graphite-dependences.c
+++ b/gcc/graphite-dependences.c
@@ -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);
diff --git a/gcc/graphite-ppl.c b/gcc/graphite-ppl.c
index 3013b33..d879d78 100644
--- a/gcc/graphite-ppl.c
+++ b/gcc/graphite-ppl.c
@@ -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
diff --git a/gcc/graphite-ppl.h b/gcc/graphite-ppl.h
index f6c279b..f6c3ad3 100644
--- a/gcc/graphite-ppl.h
+++ b/gcc/graphite-ppl.h
@@ -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.  */
 
diff --git a/gcc/testsuite/gcc.dg/graphite/block-0.c b/gcc/testsuite/gcc.dg/graphite/block-0.c
index af02363..d772743 100644
--- a/gcc/testsuite/gcc.dg/graphite/block-0.c
+++ b/gcc/testsuite/gcc.dg/graphite/block-0.c
@@ -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;
diff --git a/gcc/testsuite/gcc.dg/graphite/block-4.c b/gcc/testsuite/gcc.dg/graphite/block-4.c
index ac22ec3..eb98f04 100644
--- a/gcc/testsuite/gcc.dg/graphite/block-4.c
+++ b/gcc/testsuite/gcc.dg/graphite/block-4.c
@@ -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++)
diff --git a/gcc/testsuite/gcc.dg/graphite/block-7.c b/gcc/testsuite/gcc.dg/graphite/block-7.c
index 07c626c..6f33651 100644
--- a/gcc/testsuite/gcc.dg/graphite/block-7.c
+++ b/gcc/testsuite/gcc.dg/graphite/block-7.c
@@ -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++)
       {
diff --git a/gcc/testsuite/gcc.dg/graphite/block-8.c b/gcc/testsuite/gcc.dg/graphite/block-8.c
new file mode 100644
index 0000000..4e7e5b5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/graphite/block-8.c
@@ -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" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-1.c b/gcc/testsuite/gcc.dg/graphite/interchange-1.c
index 787124f..b4559d1 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-1.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-1.c
@@ -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" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-11.c b/gcc/testsuite/gcc.dg/graphite/interchange-11.c
index 95b60b8..491fda1 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-11.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-11.c
@@ -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" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-12.c b/gcc/testsuite/gcc.dg/graphite/interchange-12.c
index 16c0ddb..f569b78 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-12.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-12.c
@@ -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" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-13.c b/gcc/testsuite/gcc.dg/graphite/interchange-13.c
new file mode 100644
index 0000000..a8bf23b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-13.c
@@ -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" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-14.c b/gcc/testsuite/gcc.dg/graphite/interchange-14.c
new file mode 100644
index 0000000..00b7f82
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-14.c
@@ -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" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-15.c b/gcc/testsuite/gcc.dg/graphite/interchange-15.c
new file mode 100644
index 0000000..bfb8a73
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-15.c
@@ -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" } } */
+
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-8.c b/gcc/testsuite/gcc.dg/graphite/interchange-8.c
index 8c07b6f..e084bd8 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-8.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-8.c
@@ -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" } } */
diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c b/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c
index 62a9c46..61e73c1 100644
--- a/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c
+++ b/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c
@@ -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];
diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index 3de3234..ccc0091 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -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);