gcc/graphite-interchange.c

   1 /* Interchange heuristics and transform for loop interchange on
   2    polyhedral representation.
   3
   4    Copyright (C) 2009, 2010 Free Software Foundation, Inc.
   5    Contributed by Sebastian Pop <sebastian.pop@amd.com> and
   6    Harsha Jagasia <harsha.jagasia@amd.com>.
   7
   8 This file is part of GCC.
   9
  10 GCC is free software; you can redistribute it and/or modify
  11 it under the terms of the GNU General Public License as published by
  12 the Free Software Foundation; either version 3, or (at your option)
  13 any later version.
  14
  15 GCC is distributed in the hope that it will be useful,
  16 but WITHOUT ANY WARRANTY; without even the implied warranty of
  17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18 GNU General Public License for more details.
  19
  20 You should have received a copy of the GNU General Public License
  21 along with GCC; see the file COPYING3.  If not see
  22 <http://www.gnu.org/licenses/>.  */
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "tree-flow.h"
  27 #include "tree-dump.h"
  28 #include "cfgloop.h"
  29 #include "tree-chrec.h"
  30 #include "tree-data-ref.h"
  31 #include "tree-scalar-evolution.h"
  32 #include "sese.h"
  33
  34 #ifdef HAVE_cloog
  35 #include "ppl_c.h"
  36 #include "graphite-ppl.h"
  37 #include "graphite-poly.h"
  38
  39 /* Builds a linear expression, of dimension DIM, representing PDR's
  40    memory access:
  41
  42    L = r_{n}*r_{n-1}*...*r_{1}*s_{0} + ... + r_{n}*s_{n-1} + s_{n}.
  43
  44    For an array A[10][20] with two subscript locations s0 and s1, the
  45    linear memory access is 20 * s0 + s1: a stride of 1 in subscript s0
  46    corresponds to a memory stride of 20.
  47
  48    OFFSET is a number of dimensions to prepend before the
  49    subscript dimensions: s_0, s_1, ..., s_n.
  50
  51    Thus, the final linear expression has the following format:
  52    0 .. 0_{offset} | 0 .. 0_{nit} | 0 .. 0_{gd} | 0 | c_0 c_1 ... c_n
  53    where the expression itself is:
  54    c_0 * s_0 + c_1 * s_1 + ... c_n * s_n.  */
  55
  56 static ppl_Linear_Expression_t
  57 build_linearized_memory_access (ppl_dimension_type offset, poly_dr_p pdr)
  58 {
  59   ppl_Linear_Expression_t res;
  60   ppl_Linear_Expression_t le;
  61   ppl_dimension_type i;
  62   ppl_dimension_type first = pdr_subscript_dim (pdr, 0);
  63   ppl_dimension_type last = pdr_subscript_dim (pdr, PDR_NB_SUBSCRIPTS (pdr));
  64   mpz_t size, sub_size;
  65   graphite_dim_t dim = offset + pdr_dim (pdr);
  66
  67   ppl_new_Linear_Expression_with_dimension (&res, dim);
  68
  69   mpz_init (size);
  70   mpz_set_si (size, 1);
  71   mpz_init (sub_size);
  72   mpz_set_si (sub_size, 1);
  73
  74   for (i = last - 1; i >= first; i--)
  75     {
  76       ppl_set_coef_gmp (res, i + offset, size);
  77
  78       ppl_new_Linear_Expression_with_dimension (&le, dim - offset);
  79       ppl_set_coef (le, i, 1);
  80       ppl_max_for_le_pointset (PDR_ACCESSES (pdr), le, sub_size);
  81       mpz_mul (size, size, sub_size);
  82       ppl_delete_Linear_Expression (le);
  83     }
  84
  85   mpz_clear (sub_size);
  86   mpz_clear (size);
  87   return res;
  88 }
  89
  90 /* Builds a partial difference equations and inserts them
  91    into pointset powerset polyhedron P.  Polyhedron is assumed
  92    to have the format: T|I|T'|I'|G|S|S'|l1|l2.
  93
  94    TIME_DEPTH is the time dimension w.r.t. which we are
  95    differentiating.
  96    OFFSET represents the number of dimensions between
  97    columns t_{time_depth} and t'_{time_depth}.
  98    DIM_SCTR is the number of scattering dimensions.  It is
  99    essentially the dimensionality of the T vector.
 100
 101    The following equations are inserted into the polyhedron P:
 102     | t_1 = t_1'
 103     | ...
 104     | t_{time_depth-1} = t'_{time_depth-1}
 105     | t_{time_depth} = t'_{time_depth} + 1
 106     | t_{time_depth+1} = t'_{time_depth + 1}
 107     | ...
 108     | t_{dim_sctr} = t'_{dim_sctr}.  */
 109
 110 static void
 111 build_partial_difference (ppl_Pointset_Powerset_C_Polyhedron_t *p,
 112                           ppl_dimension_type time_depth,
 113                           ppl_dimension_type offset,
 114                           ppl_dimension_type dim_sctr)
 115 {
 116   ppl_Constraint_t new_cstr;
 117   ppl_Linear_Expression_t le;
 118   ppl_dimension_type i;
 119   ppl_dimension_type dim;
 120   ppl_Pointset_Powerset_C_Polyhedron_t temp;
 121
 122   /* Add the equality: t_{time_depth} = t'_{time_depth} + 1.
 123      This is the core part of this alogrithm, since this
 124      constraint asks for the memory access stride (difference)
 125      between two consecutive points in time dimensions.  */
 126
 127   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (*p, &dim);
 128   ppl_new_Linear_Expression_with_dimension (&le, dim);
 129   ppl_set_coef (le, time_depth, 1);
 130   ppl_set_coef (le, time_depth + offset, -1);
 131   ppl_set_inhomogeneous (le, 1);
 132   ppl_new_Constraint (&new_cstr, le, PPL_CONSTRAINT_TYPE_EQUAL);
 133   ppl_Pointset_Powerset_C_Polyhedron_add_constraint (*p, new_cstr);
 134   ppl_delete_Linear_Expression (le);
 135   ppl_delete_Constraint (new_cstr);
 136
 137   /* Add equalities:
 138      | t1 = t1'
 139      | ...
 140      | t_{time_depth-1} = t'_{time_depth-1}
 141      | t_{time_depth+1} = t'_{time_depth+1}
 142      | ...
 143      | t_{dim_sctr} = t'_{dim_sctr}
 144
 145      This means that all the time dimensions are equal except for
 146      time_depth, where the constraint is t_{depth} = t'_{depth} + 1
 147      step.  More to this: we should be carefull not to add equalities
 148      to the 'coupled' dimensions, which happens when the one dimension
 149      is stripmined dimension, and the other dimension corresponds
 150      to the point loop inside stripmined dimension.  */
 151
 152   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron (&temp, *p);
 153
 154   for (i = 0; i < dim_sctr; i++)
 155     if (i != time_depth)
 156       {
 157         ppl_new_Linear_Expression_with_dimension (&le, dim);
 158         ppl_set_coef (le, i, 1);
 159         ppl_set_coef (le, i + offset, -1);
 160         ppl_new_Constraint (&new_cstr, le, PPL_CONSTRAINT_TYPE_EQUAL);
 161         ppl_Pointset_Powerset_C_Polyhedron_add_constraint (temp, new_cstr);
 162
 163         if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (temp))
 164           {
 165             ppl_delete_Pointset_Powerset_C_Polyhedron (temp);
 166             ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron (&temp, *p);
 167           }
 168         else
 169           ppl_Pointset_Powerset_C_Polyhedron_add_constraint (*p, new_cstr);
 170         ppl_delete_Linear_Expression (le);
 171         ppl_delete_Constraint (new_cstr);
 172       }
 173
 174   ppl_delete_Pointset_Powerset_C_Polyhedron (temp);
 175 }
 176
 177
 178 /* Set STRIDE to the stride of PDR in memory by advancing by one in
 179    the loop at DEPTH.  */
 180
 181 static void
 182 pdr_stride_in_loop (mpz_t stride, graphite_dim_t depth, poly_dr_p pdr)
 183 {
 184   ppl_dimension_type time_depth;
 185   ppl_Linear_Expression_t le, lma;
 186   ppl_Constraint_t new_cstr;
 187   ppl_dimension_type i, *map;
 188   ppl_Pointset_Powerset_C_Polyhedron_t p1, p2, sctr;
 189   graphite_dim_t nb_subscripts = PDR_NB_SUBSCRIPTS (pdr) + 1;
 190   poly_bb_p pbb = PDR_PBB (pdr);
 191   ppl_dimension_type offset = pbb_nb_scattering_transform (pbb)
 192                               + pbb_nb_local_vars (pbb)
 193                               + pbb_dim_iter_domain (pbb);
 194   ppl_dimension_type offsetg = offset + pbb_nb_params (pbb);
 195   ppl_dimension_type dim_sctr = pbb_nb_scattering_transform (pbb)
 196                                 + pbb_nb_local_vars (pbb);
 197   ppl_dimension_type dim_L1 = offset + offsetg + 2 * nb_subscripts;
 198   ppl_dimension_type dim_L2 = offset + offsetg + 2 * nb_subscripts + 1;
 199   ppl_dimension_type new_dim = offset + offsetg + 2 * nb_subscripts + 2;
 200
 201   /* The resulting polyhedron should have the following format:
 202      T|I|T'|I'|G|S|S'|l1|l2
 203      where:
 204      | T = t_1..t_{dim_sctr}
 205      | I = i_1..i_{dim_iter_domain}
 206      | T'= t'_1..t'_{dim_sctr}
 207      | I'= i'_1..i'_{dim_iter_domain}
 208      | G = g_1..g_{nb_params}
 209      | S = s_1..s_{nb_subscripts}
 210      | S'= s'_1..s'_{nb_subscripts}
 211      | l1 and l2 are scalars.
 212
 213      Some invariants:
 214      offset = dim_sctr + dim_iter_domain + nb_local_vars
 215      offsetg = dim_sctr + dim_iter_domain + nb_local_vars + nb_params.  */
 216
 217   /* Construct the T|I|0|0|G|0|0|0|0 part.  */
 218   {
 219     ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
 220       (&sctr, PBB_TRANSFORMED_SCATTERING (pbb));
 221     ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed
 222       (sctr, 2 * nb_subscripts + 2);
 223     ppl_insert_dimensions_pointset (sctr, offset, offset);
 224   }
 225
 226   /* Construct the 0|I|0|0|G|S|0|0|0 part.  */
 227   {
 228     ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 229       (&p1, PDR_ACCESSES (pdr));
 230     ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed
 231       (p1, nb_subscripts + 2);
 232     ppl_insert_dimensions_pointset (p1, 0, dim_sctr);
 233     ppl_insert_dimensions_pointset (p1, offset, offset);
 234   }
 235
 236   /* Construct the 0|0|0|0|0|S|0|l1|0 part.  */
 237   {
 238     lma = build_linearized_memory_access (offset + dim_sctr, pdr);
 239     ppl_set_coef (lma, dim_L1, -1);
 240     ppl_new_Constraint (&new_cstr, lma, PPL_CONSTRAINT_TYPE_EQUAL);
 241     ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p1, new_cstr);
 242     ppl_delete_Linear_Expression (lma);
 243     ppl_delete_Constraint (new_cstr);
 244   }
 245
 246   /* Now intersect all the parts to get the polyhedron P1:
 247      T|I|0|0|G|0|0|0 |0
 248      0|I|0|0|G|S|0|0 |0
 249      0|0|0|0|0|S|0|l1|0
 250      ------------------
 251      T|I|0|0|G|S|0|l1|0.  */
 252
 253   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (p1, sctr);
 254   ppl_delete_Pointset_Powerset_C_Polyhedron (sctr);
 255
 256   /* Build P2, which would have the following form:
 257      0|0|T'|I'|G|0|S'|0|l2
 258
 259      P2 is built, by remapping the P1 polyhedron:
 260      T|I|0|0|G|S|0|l1|0
 261
 262      using the following mapping:
 263      T->T'
 264      I->I'
 265      S->S'
 266      l1->l2.  */
 267   {
 268     ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 269       (&p2, p1);
 270
 271     map = ppl_new_id_map (new_dim);
 272
 273     /* TI -> T'I'.  */
 274     for (i = 0; i < offset; i++)
 275       ppl_interchange (map, i, i + offset);
 276
 277     /* l1 -> l2.  */
 278     ppl_interchange (map, dim_L1, dim_L2);
 279
 280     /* S -> S'.  */
 281     for (i = 0; i < nb_subscripts; i++)
 282       ppl_interchange (map, offset + offsetg + i,
 283                        offset + offsetg + nb_subscripts + i);
 284
 285     ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (p2, map, new_dim);
 286     free (map);
 287   }
 288
 289   time_depth = psct_dynamic_dim (pbb, depth);
 290
 291   /* P1 = P1 inter P2.  */
 292   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (p1, p2);
 293   build_partial_difference (&p1, time_depth, offset, dim_sctr);
 294
 295   /* Maximise the expression L2 - L1.  */
 296   {
 297     ppl_new_Linear_Expression_with_dimension (&le, new_dim);
 298     ppl_set_coef (le, dim_L2, 1);
 299     ppl_set_coef (le, dim_L1, -1);
 300     ppl_max_for_le_pointset (p1, le, stride);
 301   }
 302
 303   if (dump_file && (dump_flags & TDF_DETAILS))
 304     {
 305       char *str;
 306       void (*gmp_free) (void *, size_t);
 307
 308       fprintf (dump_file, "\nStride in BB_%d, DR_%d, depth %d:",
 309                pbb_index (pbb), PDR_ID (pdr), (int) depth);
 310       str = mpz_get_str (0, 10, stride);
 311       fprintf (dump_file, "  %s ", str);
 312       mp_get_memory_functions (NULL, NULL, &gmp_free);
 313       (*gmp_free) (str, strlen (str) + 1);
 314     }
 315
 316   ppl_delete_Pointset_Powerset_C_Polyhedron (p1);
 317   ppl_delete_Pointset_Powerset_C_Polyhedron (p2);
 318   ppl_delete_Linear_Expression (le);
 319 }
 320
 321
 322 /* Sets STRIDES to the sum of all the strides of the data references
 323    accessed in LOOP at DEPTH.  */
 324
 325 static void
 326 memory_strides_in_loop_1 (lst_p loop, graphite_dim_t depth, mpz_t strides)
 327 {
 328   int i, j;
 329   lst_p l;
 330   poly_dr_p pdr;
 331   mpz_t s, n;
 332
 333   mpz_init (s);
 334   mpz_init (n);
 335
 336   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (loop), j, l)
 337     if (LST_LOOP_P (l))
 338       memory_strides_in_loop_1 (l, depth, strides);
 339     else
 340       FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (LST_PBB (l)), i, pdr)
 341         {
 342           pdr_stride_in_loop (s, depth, pdr);
 343           mpz_set_si (n, PDR_NB_REFS (pdr));
 344           mpz_mul (s, s, n);
 345           mpz_add (strides, strides, s);
 346         }
 347
 348   mpz_clear (s);
 349   mpz_clear (n);
 350 }
 351
 352 /* Sets STRIDES to the sum of all the strides of the data references
 353    accessed in LOOP at DEPTH.  */
 354
 355 static void
 356 memory_strides_in_loop (lst_p loop, graphite_dim_t depth, mpz_t strides)
 357 {
 358   if (mpz_cmp_si (loop->memory_strides, -1) == 0)
 359     {
 360       mpz_set_si (strides, 0);
 361       memory_strides_in_loop_1 (loop, depth, strides);
 362     }
 363   else
 364     mpz_set (strides, loop->memory_strides);
 365 }
 366
 367 /* Return true when the interchange of loops LOOP1 and LOOP2 is
 368    profitable.
 369
 370    Example:
 371
 372    | int a[100][100];
 373    |
 374    | int
 375    | foo (int N)
 376    | {
 377    |   int j;
 378    |   int i;
 379    |
 380    |   for (i = 0; i < N; i++)
 381    |     for (j = 0; j < N; j++)
 382    |       a[j][2 * i] += 1;
 383    |
 384    |   return a[N][12];
 385    | }
 386
 387    The data access A[j][i] is described like this:
 388
 389    | i   j   N   a  s0  s1   1
 390    | 0   0   0   1   0   0  -5    = 0
 391    | 0  -1   0   0   1   0   0    = 0
 392    |-2   0   0   0   0   1   0    = 0
 393    | 0   0   0   0   1   0   0   >= 0
 394    | 0   0   0   0   0   1   0   >= 0
 395    | 0   0   0   0  -1   0 100   >= 0
 396    | 0   0   0   0   0  -1 100   >= 0
 397
 398    The linearized memory access L to A[100][100] is:
 399
 400    | i   j   N   a  s0  s1   1
 401    | 0   0   0   0 100   1   0
 402
 403    TODO: the shown format is not valid as it does not show the fact
 404    that the iteration domain "i j" is transformed using the scattering.
 405
 406    Next, to measure the impact of iterating once in loop "i", we build
 407    a maximization problem: first, we add to DR accesses the dimensions
 408    k, s2, s3, L1 = 100 * s0 + s1, L2, and D1: this is the polyhedron P1.
 409    L1 and L2 are the linearized memory access functions.
 410
 411    | i   j   N   a  s0  s1   k  s2  s3  L1  L2  D1   1
 412    | 0   0   0   1   0   0   0   0   0   0   0   0  -5    = 0  alias = 5
 413    | 0  -1   0   0   1   0   0   0   0   0   0   0   0    = 0  s0 = j
 414    |-2   0   0   0   0   1   0   0   0   0   0   0   0    = 0  s1 = 2 * i
 415    | 0   0   0   0   1   0   0   0   0   0   0   0   0   >= 0
 416    | 0   0   0   0   0   1   0   0   0   0   0   0   0   >= 0
 417    | 0   0   0   0  -1   0   0   0   0   0   0   0 100   >= 0
 418    | 0   0   0   0   0  -1   0   0   0   0   0   0 100   >= 0
 419    | 0   0   0   0 100   1   0   0   0  -1   0   0   0    = 0  L1 = 100 * s0 + s1
 420
 421    Then, we generate the polyhedron P2 by interchanging the dimensions
 422    (s0, s2), (s1, s3), (L1, L2), (k, i)
 423
 424    | i   j   N   a  s0  s1   k  s2  s3  L1  L2  D1   1
 425    | 0   0   0   1   0   0   0   0   0   0   0   0  -5    = 0  alias = 5
 426    | 0  -1   0   0   0   0   0   1   0   0   0   0   0    = 0  s2 = j
 427    | 0   0   0   0   0   0  -2   0   1   0   0   0   0    = 0  s3 = 2 * k
 428    | 0   0   0   0   0   0   0   1   0   0   0   0   0   >= 0
 429    | 0   0   0   0   0   0   0   0   1   0   0   0   0   >= 0
 430    | 0   0   0   0   0   0   0  -1   0   0   0   0 100   >= 0
 431    | 0   0   0   0   0   0   0   0  -1   0   0   0 100   >= 0
 432    | 0   0   0   0   0   0   0 100   1   0  -1   0   0    = 0  L2 = 100 * s2 + s3
 433
 434    then we add to P2 the equality k = i + 1:
 435
 436    |-1   0   0   0   0   0   1   0   0   0   0   0  -1    = 0  k = i + 1
 437
 438    and finally we maximize the expression "D1 = max (P1 inter P2, L2 - L1)".
 439
 440    Similarly, to determine the impact of one iteration on loop "j", we
 441    interchange (k, j), we add "k = j + 1", and we compute D2 the
 442    maximal value of the difference.
 443
 444    Finally, the profitability test is D1 < D2: if in the outer loop
 445    the strides are smaller than in the inner loop, then it is
 446    profitable to interchange the loops at DEPTH1 and DEPTH2.  */
 447
 448 static bool
 449 lst_interchange_profitable_p (lst_p loop1, lst_p loop2)
 450 {
 451   mpz_t d1, d2;
 452   bool res;
 453
 454   gcc_assert (loop1 && loop2
 455               && LST_LOOP_P (loop1) && LST_LOOP_P (loop2)
 456               && lst_depth (loop1) < lst_depth (loop2));
 457
 458   mpz_init (d1);
 459   mpz_init (d2);
 460
 461   memory_strides_in_loop (loop1, lst_depth (loop1), d1);
 462   memory_strides_in_loop (loop2, lst_depth (loop2), d2);
 463
 464   res = mpz_cmp (d1, d2) < 0;
 465
 466   mpz_clear (d1);
 467   mpz_clear (d2);
 468
 469   return res;
 470 }
 471
 472 /* Interchanges the loops at DEPTH1 and DEPTH2 of the original
 473    scattering and assigns the resulting polyhedron to the transformed
 474    scattering.  */
 475
 476 static void
 477 pbb_interchange_loop_depths (graphite_dim_t depth1, graphite_dim_t depth2,
 478                              poly_bb_p pbb)
 479 {
 480   ppl_dimension_type i, dim;
 481   ppl_dimension_type *map;
 482   ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
 483   ppl_dimension_type dim1 = psct_dynamic_dim (pbb, depth1);
 484   ppl_dimension_type dim2 = psct_dynamic_dim (pbb, depth2);
 485
 486   ppl_Polyhedron_space_dimension (poly, &dim);
 487   map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
 488
 489   for (i = 0; i < dim; i++)
 490     map[i] = i;
 491
 492   map[dim1] = dim2;
 493   map[dim2] = dim1;
 494
 495   ppl_Polyhedron_map_space_dimensions (poly, map, dim);
 496   free (map);
 497 }
 498
 499 /* Apply the interchange of loops at depths DEPTH1 and DEPTH2 to all
 500    the statements below LST.  */
 501
 502 static void
 503 lst_apply_interchange (lst_p lst, int depth1, int depth2)
 504 {
 505   if (!lst)
 506     return;
 507
 508   if (LST_LOOP_P (lst))
 509     {
 510       int i;
 511       lst_p l;
 512
 513       FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
 514         lst_apply_interchange (l, depth1, depth2);
 515     }
 516   else
 517     pbb_interchange_loop_depths (depth1, depth2, LST_PBB (lst));
 518 }
 519
 520 /* Return true when the nest starting at LOOP1 and ending on LOOP2 is
 521    perfect: i.e. there are no sequence of statements.  */
 522
 523 static bool
 524 lst_perfectly_nested_p (lst_p loop1, lst_p loop2)
 525 {
 526   if (loop1 == loop2)
 527     return true;
 528
 529   if (!LST_LOOP_P (loop1))
 530     return false;
 531
 532   return VEC_length (lst_p, LST_SEQ (loop1)) == 1
 533     && lst_perfectly_nested_p (VEC_index (lst_p, LST_SEQ (loop1), 0), loop2);
 534 }
 535
 536 /* Transform the loop nest between LOOP1 and LOOP2 into a perfect
 537    nest.  To continue the naming tradition, this function is called
 538    after perfect_nestify.  NEST is set to the perfectly nested loop
 539    that is created.  BEFORE/AFTER are set to the loops distributed
 540    before/after the loop NEST.  */
 541
 542 static void
 543 lst_perfect_nestify (lst_p loop1, lst_p loop2, lst_p *before,
 544                      lst_p *nest, lst_p *after)
 545 {
 546   poly_bb_p first, last;
 547
 548   gcc_assert (loop1 && loop2
 549               && loop1 != loop2
 550               && LST_LOOP_P (loop1) && LST_LOOP_P (loop2));
 551
 552   first = LST_PBB (lst_find_first_pbb (loop2));
 553   last = LST_PBB (lst_find_last_pbb (loop2));
 554
 555   *before = copy_lst (loop1);
 556   *nest = copy_lst (loop1);
 557   *after = copy_lst (loop1);
 558
 559   lst_remove_all_before_including_pbb (*before, first, false);
 560   lst_remove_all_before_including_pbb (*after, last, true);
 561
 562   lst_remove_all_before_excluding_pbb (*nest, first, true);
 563   lst_remove_all_before_excluding_pbb (*nest, last, false);
 564
 565   if (lst_empty_p (*before))
 566     {
 567       free_lst (*before);
 568       *before = NULL;
 569     }
 570   if (lst_empty_p (*after))
 571     {
 572       free_lst (*after);
 573       *after = NULL;
 574     }
 575   if (lst_empty_p (*nest))
 576     {
 577       free_lst (*nest);
 578       *nest = NULL;
 579     }
 580 }
 581
 582 /* Try to interchange LOOP1 with LOOP2 for all the statements of the
 583    body of LOOP2.  LOOP1 contains LOOP2.  Return true if it did the
 584    interchange.  */
 585
 586 static bool
 587 lst_try_interchange_loops (scop_p scop, lst_p loop1, lst_p loop2)
 588 {
 589   int depth1 = lst_depth (loop1);
 590   int depth2 = lst_depth (loop2);
 591   lst_p transformed;
 592
 593   lst_p before = NULL, nest = NULL, after = NULL;
 594
 595   if (!lst_interchange_profitable_p (loop1, loop2))
 596     return false;
 597
 598   if (!lst_perfectly_nested_p (loop1, loop2))
 599     lst_perfect_nestify (loop1, loop2, &before, &nest, &after);
 600
 601   lst_apply_interchange (loop2, depth1, depth2);
 602
 603   /* Sync the transformed LST information and the PBB scatterings
 604      before using the scatterings in the data dependence analysis.  */
 605   if (before || nest || after)
 606     {
 607       transformed = lst_substitute_3 (SCOP_TRANSFORMED_SCHEDULE (scop), loop1,
 608                                       before, nest, after);
 609       lst_update_scattering (transformed);
 610       free_lst (transformed);
 611     }
 612
 613   if (graphite_legal_transform (scop))
 614     {
 615       if (dump_file && (dump_flags & TDF_DETAILS))
 616         fprintf (dump_file,
 617                  "Loops at depths %d and %d will be interchanged.\n",
 618                  depth1, depth2);
 619
 620       /* Transform the SCOP_TRANSFORMED_SCHEDULE of the SCOP.  */
 621       lst_insert_in_sequence (before, loop1, true);
 622       lst_insert_in_sequence (after, loop1, false);
 623
 624       if (nest)
 625         {
 626           lst_replace (loop1, nest);
 627           free_lst (loop1);
 628         }
 629
 630       return true;
 631     }
 632
 633   /* Undo the transform.  */
 634   free_lst (before);
 635   free_lst (nest);
 636   free_lst (after);
 637   lst_apply_interchange (loop2, depth2, depth1);
 638   return false;
 639 }
 640
 641 /* Selects the inner loop in LST_SEQ (INNER_FATHER) to be interchanged
 642    with the loop OUTER in LST_SEQ (OUTER_FATHER).  */
 643
 644 static bool
 645 lst_interchange_select_inner (scop_p scop, lst_p outer_father, int outer,
 646                               lst_p inner_father)
 647 {
 648   int inner;
 649   lst_p loop1, loop2;
 650
 651   gcc_assert (outer_father
 652               && LST_LOOP_P (outer_father)
 653               && LST_LOOP_P (VEC_index (lst_p, LST_SEQ (outer_father), outer))
 654               && inner_father
 655               && LST_LOOP_P (inner_father));
 656
 657   loop1 = VEC_index (lst_p, LST_SEQ (outer_father), outer);
 658
 659   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (inner_father), inner, loop2)
 660     if (LST_LOOP_P (loop2)
 661         && (lst_try_interchange_loops (scop, loop1, loop2)
 662             || lst_interchange_select_inner (scop, outer_father, outer, loop2)))
 663       return true;
 664
 665   return false;
 666 }
 667
 668 /* Interchanges all the loops of LOOP and the loops of its body that
 669    are considered profitable to interchange.  Return true if it did
 670    interchanged some loops.  OUTER is the index in LST_SEQ (LOOP) that
 671    points to the next outer loop to be considered for interchange.  */
 672
 673 static bool
 674 lst_interchange_select_outer (scop_p scop, lst_p loop, int outer)
 675 {
 676   lst_p l;
 677   bool res = false;
 678   int i = 0;
 679   lst_p father;
 680
 681   if (!loop || !LST_LOOP_P (loop))
 682     return false;
 683
 684   father = LST_LOOP_FATHER (loop);
 685   if (father)
 686     {
 687       while (lst_interchange_select_inner (scop, father, outer, loop))
 688         {
 689           res = true;
 690           loop = VEC_index (lst_p, LST_SEQ (father), outer);
 691         }
 692     }
 693
 694   if (LST_LOOP_P (loop))
 695     FOR_EACH_VEC_ELT (lst_p, LST_SEQ (loop), i, l)
 696       if (LST_LOOP_P (l))
 697         res |= lst_interchange_select_outer (scop, l, i);
 698
 699   return res;
 700 }
 701
 702 /* Interchanges all the loop depths that are considered profitable for SCOP.  */
 703
 704 bool
 705 scop_do_interchange (scop_p scop)
 706 {
 707   bool res = lst_interchange_select_outer
 708     (scop, SCOP_TRANSFORMED_SCHEDULE (scop), 0);
 709
 710   lst_update_scattering (SCOP_TRANSFORMED_SCHEDULE (scop));
 711
 712   return res;
 713 }
 714
 715
 716 #endif
 717