obtained gcc-4.6.4.tar.bz2 from upstream website;upstream

verified gcc-4.6.4.tar.bz2.sig;
imported gcc-4.6.4 source tree from verified upstream tarball.

downloading a git-generated archive based on the 'upstream' tag
should provide you with a source tree that is binary identical
to the one extracted from the above tarball.

if you have obtained the source via the command 'git clone',
however, do note that line-endings of files in your working
directory might differ from line-endings of the respective
files in the upstream repository.

1 files changed, 715 insertions, 0 deletions

diff --git a/gcc/graphite-interchange.c b/gcc/graphite-interchange.c
new file mode 100644
index 000000000..934839aac
--- /dev/null
+++ b/gcc/graphite-interchange.c
@@ -0,0 +1,715 @@
+/* Interchange heuristics and transform for loop interchange on
+   polyhedral representation.
+
+   Copyright (C) 2009, 2010 Free Software Foundation, Inc.
+   Contributed by Sebastian Pop <sebastian.pop@amd.com> and
+   Harsha Jagasia <harsha.jagasia@amd.com>.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tree-flow.h"
+#include "tree-dump.h"
+#include "cfgloop.h"
+#include "tree-chrec.h"
+#include "tree-data-ref.h"
+#include "tree-scalar-evolution.h"
+#include "sese.h"
+
+#ifdef HAVE_cloog
+#include "ppl_c.h"
+#include "graphite-ppl.h"
+#include "graphite-poly.h"
+
+/* Builds a linear expression, of dimension DIM, representing PDR's
+   memory access:
+
+   L = r_{n}*r_{n-1}*...*r_{1}*s_{0} + ... + r_{n}*s_{n-1} + s_{n}.
+
+   For an array A[10][20] with two subscript locations s0 and s1, the
+   linear memory access is 20 * s0 + s1: a stride of 1 in subscript s0
+   corresponds to a memory stride of 20.
+
+   OFFSET is a number of dimensions to prepend before the
+   subscript dimensions: s_0, s_1, ..., s_n.
+
+   Thus, the final linear expression has the following format:
+   0 .. 0_{offset} | 0 .. 0_{nit} | 0 .. 0_{gd} | 0 | c_0 c_1 ... c_n
+   where the expression itself is:
+   c_0 * s_0 + c_1 * s_1 + ... c_n * s_n.  */
+
+static ppl_Linear_Expression_t
+build_linearized_memory_access (ppl_dimension_type offset, poly_dr_p pdr)
+{
+  ppl_Linear_Expression_t res;
+  ppl_Linear_Expression_t le;
+  ppl_dimension_type i;
+  ppl_dimension_type first = pdr_subscript_dim (pdr, 0);
+  ppl_dimension_type last = pdr_subscript_dim (pdr, PDR_NB_SUBSCRIPTS (pdr));
+  mpz_t size, sub_size;
+  graphite_dim_t dim = offset + pdr_dim (pdr);
+
+  ppl_new_Linear_Expression_with_dimension (&res, dim);
+
+  mpz_init (size);
+  mpz_set_si (size, 1);
+  mpz_init (sub_size);
+  mpz_set_si (sub_size, 1);
+
+  for (i = last - 1; i >= first; i--)
+    {
+      ppl_set_coef_gmp (res, i + offset, size);
+
+      ppl_new_Linear_Expression_with_dimension (&le, dim - offset);
+      ppl_set_coef (le, i, 1);
+      ppl_max_for_le_pointset (PDR_ACCESSES (pdr), le, sub_size);
+      mpz_mul (size, size, sub_size);
+      ppl_delete_Linear_Expression (le);
+    }
+
+  mpz_clear (sub_size);
+  mpz_clear (size);
+  return res;
+}
+
+/* Builds a partial difference equations and inserts them
+   into pointset powerset polyhedron P.  Polyhedron is assumed
+   to have the format: T|I|T'|I'|G|S|S'|l1|l2.
+
+   TIME_DEPTH is the time dimension w.r.t. which we are
+   differentiating.
+   OFFSET represents the number of dimensions between
+   columns t_{time_depth} and t'_{time_depth}.
+   DIM_SCTR is the number of scattering dimensions.  It is
+   essentially the dimensionality of the T vector.
+
+   The following equations are inserted into the polyhedron P:
+    | t_1 = t_1'
+    | ...
+    | t_{time_depth-1} = t'_{time_depth-1}
+    | t_{time_depth} = t'_{time_depth} + 1
+    | t_{time_depth+1} = t'_{time_depth + 1}
+    | ...
+    | t_{dim_sctr} = t'_{dim_sctr}.  */
+
+static void
+build_partial_difference (ppl_Pointset_Powerset_C_Polyhedron_t *p,
+                          ppl_dimension_type time_depth,
+                          ppl_dimension_type offset,
+                          ppl_dimension_type dim_sctr)
+{
+  ppl_Constraint_t new_cstr;
+  ppl_Linear_Expression_t le;
+  ppl_dimension_type i;
+  ppl_dimension_type dim;
+  ppl_Pointset_Powerset_C_Polyhedron_t temp;
+
+  /* Add the equality: t_{time_depth} = t'_{time_depth} + 1.
+     This is the core part of this alogrithm, since this
+     constraint asks for the memory access stride (difference)
+     between two consecutive points in time dimensions.  */
+
+  ppl_Pointset_Powerset_C_Polyhedron_space_dimension (*p, &dim);
+  ppl_new_Linear_Expression_with_dimension (&le, dim);
+  ppl_set_coef (le, time_depth, 1);
+  ppl_set_coef (le, time_depth + offset, -1);
+  ppl_set_inhomogeneous (le, 1);
+  ppl_new_Constraint (&new_cstr, le, PPL_CONSTRAINT_TYPE_EQUAL);
+  ppl_Pointset_Powerset_C_Polyhedron_add_constraint (*p, new_cstr);
+  ppl_delete_Linear_Expression (le);
+  ppl_delete_Constraint (new_cstr);
+
+  /* Add equalities:
+     | t1 = t1'
+     | ...
+     | t_{time_depth-1} = t'_{time_depth-1}
+     | t_{time_depth+1} = t'_{time_depth+1}
+     | ...
+     | t_{dim_sctr} = t'_{dim_sctr}
+
+     This means that all the time dimensions are equal except for
+     time_depth, where the constraint is t_{depth} = t'_{depth} + 1
+     step.  More to this: we should be carefull not to add equalities
+     to the 'coupled' dimensions, which happens when the one dimension
+     is stripmined dimension, and the other dimension corresponds
+     to the point loop inside stripmined dimension.  */
+
+  ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron (&temp, *p);
+
+  for (i = 0; i < dim_sctr; i++)
+    if (i != time_depth)
+      {
+        ppl_new_Linear_Expression_with_dimension (&le, dim);
+        ppl_set_coef (le, i, 1);
+        ppl_set_coef (le, i + offset, -1);
+        ppl_new_Constraint (&new_cstr, le, PPL_CONSTRAINT_TYPE_EQUAL);
+        ppl_Pointset_Powerset_C_Polyhedron_add_constraint (temp, new_cstr);
+
+        if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (temp))
+          {
+            ppl_delete_Pointset_Powerset_C_Polyhedron (temp);
+            ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron (&temp, *p);
+          }
+        else
+          ppl_Pointset_Powerset_C_Polyhedron_add_constraint (*p, new_cstr);
+        ppl_delete_Linear_Expression (le);
+        ppl_delete_Constraint (new_cstr);
+      }
+
+  ppl_delete_Pointset_Powerset_C_Polyhedron (temp);
+}
+
+
+/* Set STRIDE to the stride of PDR in memory by advancing by one in
+   the loop at DEPTH.  */
+
+static void
+pdr_stride_in_loop (mpz_t stride, graphite_dim_t depth, poly_dr_p pdr)
+{
+  ppl_dimension_type time_depth;
+  ppl_Linear_Expression_t le, lma;
+  ppl_Constraint_t new_cstr;
+  ppl_dimension_type i, *map;
+  ppl_Pointset_Powerset_C_Polyhedron_t p1, p2, sctr;
+  graphite_dim_t nb_subscripts = PDR_NB_SUBSCRIPTS (pdr) + 1;
+  poly_bb_p pbb = PDR_PBB (pdr);
+  ppl_dimension_type offset = pbb_nb_scattering_transform (pbb)
+                              + pbb_nb_local_vars (pbb)
+                              + pbb_dim_iter_domain (pbb);
+  ppl_dimension_type offsetg = offset + pbb_nb_params (pbb);
+  ppl_dimension_type dim_sctr = pbb_nb_scattering_transform (pbb)
+                                + pbb_nb_local_vars (pbb);
+  ppl_dimension_type dim_L1 = offset + offsetg + 2 * nb_subscripts;
+  ppl_dimension_type dim_L2 = offset + offsetg + 2 * nb_subscripts + 1;
+  ppl_dimension_type new_dim = offset + offsetg + 2 * nb_subscripts + 2;
+
+  /* The resulting polyhedron should have the following format:
+     T|I|T'|I'|G|S|S'|l1|l2
+     where:
+     | T = t_1..t_{dim_sctr}
+     | I = i_1..i_{dim_iter_domain}
+     | T'= t'_1..t'_{dim_sctr}
+     | I'= i'_1..i'_{dim_iter_domain}
+     | G = g_1..g_{nb_params}
+     | S = s_1..s_{nb_subscripts}
+     | S'= s'_1..s'_{nb_subscripts}
+     | l1 and l2 are scalars.
+
+     Some invariants:
+     offset = dim_sctr + dim_iter_domain + nb_local_vars
+     offsetg = dim_sctr + dim_iter_domain + nb_local_vars + nb_params.  */
+
+  /* Construct the T|I|0|0|G|0|0|0|0 part.  */
+  {
+    ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
+      (&sctr, PBB_TRANSFORMED_SCATTERING (pbb));
+    ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed
+      (sctr, 2 * nb_subscripts + 2);
+    ppl_insert_dimensions_pointset (sctr, offset, offset);
+  }
+
+  /* Construct the 0|I|0|0|G|S|0|0|0 part.  */
+  {
+    ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
+      (&p1, PDR_ACCESSES (pdr));
+    ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed
+      (p1, nb_subscripts + 2);
+    ppl_insert_dimensions_pointset (p1, 0, dim_sctr);
+    ppl_insert_dimensions_pointset (p1, offset, offset);
+  }
+
+  /* Construct the 0|0|0|0|0|S|0|l1|0 part.  */
+  {
+    lma = build_linearized_memory_access (offset + dim_sctr, pdr);
+    ppl_set_coef (lma, dim_L1, -1);
+    ppl_new_Constraint (&new_cstr, lma, PPL_CONSTRAINT_TYPE_EQUAL);
+    ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p1, new_cstr);
+    ppl_delete_Linear_Expression (lma);
+    ppl_delete_Constraint (new_cstr);
+  }
+
+  /* Now intersect all the parts to get the polyhedron P1:
+     T|I|0|0|G|0|0|0 |0
+     0|I|0|0|G|S|0|0 |0
+     0|0|0|0|0|S|0|l1|0
+     ------------------
+     T|I|0|0|G|S|0|l1|0.  */
+
+  ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (p1, sctr);
+  ppl_delete_Pointset_Powerset_C_Polyhedron (sctr);
+
+  /* Build P2, which would have the following form:
+     0|0|T'|I'|G|0|S'|0|l2
+
+     P2 is built, by remapping the P1 polyhedron:
+     T|I|0|0|G|S|0|l1|0
+
+     using the following mapping:
+     T->T'
+     I->I'
+     S->S'
+     l1->l2.  */
+  {
+    ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
+      (&p2, p1);
+
+    map = ppl_new_id_map (new_dim);
+
+    /* TI -> T'I'.  */
+    for (i = 0; i < offset; i++)
+      ppl_interchange (map, i, i + offset);
+
+    /* l1 -> l2.  */
+    ppl_interchange (map, dim_L1, dim_L2);
+
+    /* S -> S'.  */
+    for (i = 0; i < nb_subscripts; i++)
+      ppl_interchange (map, offset + offsetg + i,
+		       offset + offsetg + nb_subscripts + i);
+
+    ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (p2, map, new_dim);
+    free (map);
+  }
+
+  time_depth = psct_dynamic_dim (pbb, depth);
+
+  /* P1 = P1 inter P2.  */
+  ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (p1, p2);
+  build_partial_difference (&p1, time_depth, offset, dim_sctr);
+
+  /* Maximise the expression L2 - L1.  */
+  {
+    ppl_new_Linear_Expression_with_dimension (&le, new_dim);
+    ppl_set_coef (le, dim_L2, 1);
+    ppl_set_coef (le, dim_L1, -1);
+    ppl_max_for_le_pointset (p1, le, stride);
+  }
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      char *str;
+      void (*gmp_free) (void *, size_t);
+
+      fprintf (dump_file, "\nStride in BB_%d, DR_%d, depth %d:",
+	       pbb_index (pbb), PDR_ID (pdr), (int) depth);
+      str = mpz_get_str (0, 10, stride);
+      fprintf (dump_file, "  %s ", str);
+      mp_get_memory_functions (NULL, NULL, &gmp_free);
+      (*gmp_free) (str, strlen (str) + 1);
+    }
+
+  ppl_delete_Pointset_Powerset_C_Polyhedron (p1);
+  ppl_delete_Pointset_Powerset_C_Polyhedron (p2);
+  ppl_delete_Linear_Expression (le);
+}
+
+
+/* Sets STRIDES to the sum of all the strides of the data references
+   accessed in LOOP at DEPTH.  */
+
+static void
+memory_strides_in_loop_1 (lst_p loop, graphite_dim_t depth, mpz_t strides)
+{
+  int i, j;
+  lst_p l;
+  poly_dr_p pdr;
+  mpz_t s, n;
+
+  mpz_init (s);
+  mpz_init (n);
+
+  FOR_EACH_VEC_ELT (lst_p, LST_SEQ (loop), j, l)
+    if (LST_LOOP_P (l))
+      memory_strides_in_loop_1 (l, depth, strides);
+    else
+      FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (LST_PBB (l)), i, pdr)
+	{
+	  pdr_stride_in_loop (s, depth, pdr);
+	  mpz_set_si (n, PDR_NB_REFS (pdr));
+	  mpz_mul (s, s, n);
+	  mpz_add (strides, strides, s);
+	}
+
+  mpz_clear (s);
+  mpz_clear (n);
+}
+
+/* Sets STRIDES to the sum of all the strides of the data references
+   accessed in LOOP at DEPTH.  */
+
+static void
+memory_strides_in_loop (lst_p loop, graphite_dim_t depth, mpz_t strides)
+{
+  if (mpz_cmp_si (loop->memory_strides, -1) == 0)
+    {
+      mpz_set_si (strides, 0);
+      memory_strides_in_loop_1 (loop, depth, strides);
+    }
+  else
+    mpz_set (strides, loop->memory_strides);
+}
+
+/* Return true when the interchange of loops LOOP1 and LOOP2 is
+   profitable.
+
+   Example:
+
+   | int a[100][100];
+   |
+   | int
+   | foo (int N)
+   | {
+   |   int j;
+   |   int i;
+   |
+   |   for (i = 0; i < N; i++)
+   |     for (j = 0; j < N; j++)
+   |       a[j][2 * i] += 1;
+   |
+   |   return a[N][12];
+   | }
+
+   The data access A[j][i] is described like this:
+
+   | i   j   N   a  s0  s1   1
+   | 0   0   0   1   0   0  -5    = 0
+   | 0  -1   0   0   1   0   0    = 0
+   |-2   0   0   0   0   1   0    = 0
+   | 0   0   0   0   1   0   0   >= 0
+   | 0   0   0   0   0   1   0   >= 0
+   | 0   0   0   0  -1   0 100   >= 0
+   | 0   0   0   0   0  -1 100   >= 0
+
+   The linearized memory access L to A[100][100] is:
+
+   | i   j   N   a  s0  s1   1
+   | 0   0   0   0 100   1   0
+
+   TODO: the shown format is not valid as it does not show the fact
+   that the iteration domain "i j" is transformed using the scattering.
+
+   Next, to measure the impact of iterating once in loop "i", we build
+   a maximization problem: first, we add to DR accesses the dimensions
+   k, s2, s3, L1 = 100 * s0 + s1, L2, and D1: this is the polyhedron P1.
+   L1 and L2 are the linearized memory access functions.
+
+   | i   j   N   a  s0  s1   k  s2  s3  L1  L2  D1   1
+   | 0   0   0   1   0   0   0   0   0   0   0   0  -5    = 0  alias = 5
+   | 0  -1   0   0   1   0   0   0   0   0   0   0   0    = 0  s0 = j
+   |-2   0   0   0   0   1   0   0   0   0   0   0   0    = 0  s1 = 2 * i
+   | 0   0   0   0   1   0   0   0   0   0   0   0   0   >= 0
+   | 0   0   0   0   0   1   0   0   0   0   0   0   0   >= 0
+   | 0   0   0   0  -1   0   0   0   0   0   0   0 100   >= 0
+   | 0   0   0   0   0  -1   0   0   0   0   0   0 100   >= 0
+   | 0   0   0   0 100   1   0   0   0  -1   0   0   0    = 0  L1 = 100 * s0 + s1
+
+   Then, we generate the polyhedron P2 by interchanging the dimensions
+   (s0, s2), (s1, s3), (L1, L2), (k, i)
+
+   | i   j   N   a  s0  s1   k  s2  s3  L1  L2  D1   1
+   | 0   0   0   1   0   0   0   0   0   0   0   0  -5    = 0  alias = 5
+   | 0  -1   0   0   0   0   0   1   0   0   0   0   0    = 0  s2 = j
+   | 0   0   0   0   0   0  -2   0   1   0   0   0   0    = 0  s3 = 2 * k
+   | 0   0   0   0   0   0   0   1   0   0   0   0   0   >= 0
+   | 0   0   0   0   0   0   0   0   1   0   0   0   0   >= 0
+   | 0   0   0   0   0   0   0  -1   0   0   0   0 100   >= 0
+   | 0   0   0   0   0   0   0   0  -1   0   0   0 100   >= 0
+   | 0   0   0   0   0   0   0 100   1   0  -1   0   0    = 0  L2 = 100 * s2 + s3
+
+   then we add to P2 the equality k = i + 1:
+
+   |-1   0   0   0   0   0   1   0   0   0   0   0  -1    = 0  k = i + 1
+
+   and finally we maximize the expression "D1 = max (P1 inter P2, L2 - L1)".
+
+   Similarly, to determine the impact of one iteration on loop "j", we
+   interchange (k, j), we add "k = j + 1", and we compute D2 the
+   maximal value of the difference.
+
+   Finally, the profitability test is D1 < D2: if in the outer loop
+   the strides are smaller than in the inner loop, then it is
+   profitable to interchange the loops at DEPTH1 and DEPTH2.  */
+
+static bool
+lst_interchange_profitable_p (lst_p nest, int depth1, int depth2)
+{
+  mpz_t d1, d2;
+  bool res;
+
+  gcc_assert (depth1 < depth2);
+
+  mpz_init (d1);
+  mpz_init (d2);
+
+  memory_strides_in_loop (nest, depth1, d1);
+  memory_strides_in_loop (nest, depth2, d2);
+
+  res = mpz_cmp (d1, d2) < 0;
+
+  mpz_clear (d1);
+  mpz_clear (d2);
+
+  return res;
+}
+
+/* Interchanges the loops at DEPTH1 and DEPTH2 of the original
+   scattering and assigns the resulting polyhedron to the transformed
+   scattering.  */
+
+static void
+pbb_interchange_loop_depths (graphite_dim_t depth1, graphite_dim_t depth2,
+			     poly_bb_p pbb)
+{
+  ppl_dimension_type i, dim;
+  ppl_dimension_type *map;
+  ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
+  ppl_dimension_type dim1 = psct_dynamic_dim (pbb, depth1);
+  ppl_dimension_type dim2 = psct_dynamic_dim (pbb, depth2);
+
+  ppl_Polyhedron_space_dimension (poly, &dim);
+  map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
+
+  for (i = 0; i < dim; i++)
+    map[i] = i;
+
+  map[dim1] = dim2;
+  map[dim2] = dim1;
+
+  ppl_Polyhedron_map_space_dimensions (poly, map, dim);
+  free (map);
+}
+
+/* Apply the interchange of loops at depths DEPTH1 and DEPTH2 to all
+   the statements below LST.  */
+
+static void
+lst_apply_interchange (lst_p lst, int depth1, int depth2)
+{
+  if (!lst)
+    return;
+
+  if (LST_LOOP_P (lst))
+    {
+      int i;
+      lst_p l;
+
+      FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
+	lst_apply_interchange (l, depth1, depth2);
+    }
+  else
+    pbb_interchange_loop_depths (depth1, depth2, LST_PBB (lst));
+}
+
+/* Return true when the nest starting at LOOP1 and ending on LOOP2 is
+   perfect: i.e. there are no sequence of statements.  */
+
+static bool
+lst_perfectly_nested_p (lst_p loop1, lst_p loop2)
+{
+  if (loop1 == loop2)
+    return true;
+
+  if (!LST_LOOP_P (loop1))
+    return false;
+
+  return VEC_length (lst_p, LST_SEQ (loop1)) == 1
+    && lst_perfectly_nested_p (VEC_index (lst_p, LST_SEQ (loop1), 0), loop2);
+}
+
+/* Transform the loop nest between LOOP1 and LOOP2 into a perfect
+   nest.  To continue the naming tradition, this function is called
+   after perfect_nestify.  NEST is set to the perfectly nested loop
+   that is created.  BEFORE/AFTER are set to the loops distributed
+   before/after the loop NEST.  */
+
+static void
+lst_perfect_nestify (lst_p loop1, lst_p loop2, lst_p *before,
+		     lst_p *nest, lst_p *after)
+{
+  poly_bb_p first, last;
+
+  gcc_assert (loop1 && loop2
+	      && loop1 != loop2
+	      && LST_LOOP_P (loop1) && LST_LOOP_P (loop2));
+
+  first = LST_PBB (lst_find_first_pbb (loop2));
+  last = LST_PBB (lst_find_last_pbb (loop2));
+
+  *before = copy_lst (loop1);
+  *nest = copy_lst (loop1);
+  *after = copy_lst (loop1);
+
+  lst_remove_all_before_including_pbb (*before, first, false);
+  lst_remove_all_before_including_pbb (*after, last, true);
+
+  lst_remove_all_before_excluding_pbb (*nest, first, true);
+  lst_remove_all_before_excluding_pbb (*nest, last, false);
+
+  if (lst_empty_p (*before))
+    {
+      free_lst (*before);
+      *before = NULL;
+    }
+  if (lst_empty_p (*after))
+    {
+      free_lst (*after);
+      *after = NULL;
+    }
+  if (lst_empty_p (*nest))
+    {
+      free_lst (*nest);
+      *nest = NULL;
+    }
+}
+
+/* Try to interchange LOOP1 with LOOP2 for all the statements of the
+   body of LOOP2.  LOOP1 contains LOOP2.  Return true if it did the
+   interchange.  */
+
+static bool
+lst_try_interchange_loops (scop_p scop, lst_p loop1, lst_p loop2)
+{
+  int depth1 = lst_depth (loop1);
+  int depth2 = lst_depth (loop2);
+  lst_p transformed;
+
+  lst_p before = NULL, nest = NULL, after = NULL;
+
+  if (!lst_perfectly_nested_p (loop1, loop2))
+    lst_perfect_nestify (loop1, loop2, &before, &nest, &after);
+
+  if (!lst_interchange_profitable_p (loop2, depth1, depth2))
+    return false;
+
+  lst_apply_interchange (loop2, depth1, depth2);
+
+  /* Sync the transformed LST information and the PBB scatterings
+     before using the scatterings in the data dependence analysis.  */
+  if (before || nest || after)
+    {
+      transformed = lst_substitute_3 (SCOP_TRANSFORMED_SCHEDULE (scop), loop1,
+				      before, nest, after);
+      lst_update_scattering (transformed);
+      free_lst (transformed);
+    }
+
+  if (graphite_legal_transform (scop))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file,
+		 "Loops at depths %d and %d will be interchanged.\n",
+		 depth1, depth2);
+
+      /* Transform the SCOP_TRANSFORMED_SCHEDULE of the SCOP.  */
+      lst_insert_in_sequence (before, loop1, true);
+      lst_insert_in_sequence (after, loop1, false);
+
+      if (nest)
+	{
+	  lst_replace (loop1, nest);
+	  free_lst (loop1);
+	}
+
+      return true;
+    }
+
+  /* Undo the transform.  */
+  free_lst (before);
+  free_lst (nest);
+  free_lst (after);
+  lst_apply_interchange (loop2, depth2, depth1);
+  return false;
+}
+
+/* Selects the inner loop in LST_SEQ (INNER_FATHER) to be interchanged
+   with the loop OUTER in LST_SEQ (OUTER_FATHER).  */
+
+static bool
+lst_interchange_select_inner (scop_p scop, lst_p outer_father, int outer,
+			      lst_p inner_father)
+{
+  int inner;
+  lst_p loop1, loop2;
+
+  gcc_assert (outer_father
+	      && LST_LOOP_P (outer_father)
+	      && LST_LOOP_P (VEC_index (lst_p, LST_SEQ (outer_father), outer))
+	      && inner_father
+	      && LST_LOOP_P (inner_father));
+
+  loop1 = VEC_index (lst_p, LST_SEQ (outer_father), outer);
+
+  FOR_EACH_VEC_ELT (lst_p, LST_SEQ (inner_father), inner, loop2)
+    if (LST_LOOP_P (loop2)
+	&& (lst_try_interchange_loops (scop, loop1, loop2)
+	    || lst_interchange_select_inner (scop, outer_father, outer, loop2)))
+      return true;
+
+  return false;
+}
+
+/* Interchanges all the loops of LOOP and the loops of its body that
+   are considered profitable to interchange.  Return true if it did
+   interchanged some loops.  OUTER is the index in LST_SEQ (LOOP) that
+   points to the next outer loop to be considered for interchange.  */
+
+static bool
+lst_interchange_select_outer (scop_p scop, lst_p loop, int outer)
+{
+  lst_p l;
+  bool res = false;
+  int i = 0;
+  lst_p father;
+
+  if (!loop || !LST_LOOP_P (loop))
+    return false;
+
+  father = LST_LOOP_FATHER (loop);
+  if (father)
+    {
+      while (lst_interchange_select_inner (scop, father, outer, loop))
+	{
+	  res = true;
+	  loop = VEC_index (lst_p, LST_SEQ (father), outer);
+	}
+    }
+
+  if (LST_LOOP_P (loop))
+    FOR_EACH_VEC_ELT (lst_p, LST_SEQ (loop), i, l)
+      if (LST_LOOP_P (l))
+	res |= lst_interchange_select_outer (scop, l, i);
+
+  return res;
+}
+
+/* Interchanges all the loop depths that are considered profitable for SCOP.  */
+
+bool
+scop_do_interchange (scop_p scop)
+{
+  bool res = lst_interchange_select_outer
+    (scop, SCOP_TRANSFORMED_SCHEDULE (scop), 0);
+
+  lst_update_scattering (SCOP_TRANSFORMED_SCHEDULE (scop));
+
+  return res;
+}
+
+
+#endif
+