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 nest, int depth1, int depth2)
 450 {
 451   mpz_t d1, d2;
 452   bool res;
 453
 454   gcc_assert (depth1 < depth2);
 455
 456   mpz_init (d1);
 457   mpz_init (d2);
 458
 459   memory_strides_in_loop (nest, depth1, d1);
 460   memory_strides_in_loop (nest, depth2, d2);
 461
 462   res = mpz_cmp (d1, d2) < 0;
 463
 464   mpz_clear (d1);
 465   mpz_clear (d2);
 466
 467   return res;
 468 }
 469
 470 /* Interchanges the loops at DEPTH1 and DEPTH2 of the original
 471    scattering and assigns the resulting polyhedron to the transformed
 472    scattering.  */
 473
 474 static void
 475 pbb_interchange_loop_depths (graphite_dim_t depth1, graphite_dim_t depth2,
 476                              poly_bb_p pbb)
 477 {
 478   ppl_dimension_type i, dim;
 479   ppl_dimension_type *map;
 480   ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
 481   ppl_dimension_type dim1 = psct_dynamic_dim (pbb, depth1);
 482   ppl_dimension_type dim2 = psct_dynamic_dim (pbb, depth2);
 483
 484   ppl_Polyhedron_space_dimension (poly, &dim);
 485   map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
 486
 487   for (i = 0; i < dim; i++)
 488     map[i] = i;
 489
 490   map[dim1] = dim2;
 491   map[dim2] = dim1;
 492
 493   ppl_Polyhedron_map_space_dimensions (poly, map, dim);
 494   free (map);
 495 }
 496
 497 /* Apply the interchange of loops at depths DEPTH1 and DEPTH2 to all
 498    the statements below LST.  */
 499
 500 static void
 501 lst_apply_interchange (lst_p lst, int depth1, int depth2)
 502 {
 503   if (!lst)
 504     return;
 505
 506   if (LST_LOOP_P (lst))
 507     {
 508       int i;
 509       lst_p l;
 510
 511       FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
 512         lst_apply_interchange (l, depth1, depth2);
 513     }
 514   else
 515     pbb_interchange_loop_depths (depth1, depth2, LST_PBB (lst));
 516 }
 517
 518 /* Return true when the nest starting at LOOP1 and ending on LOOP2 is
 519    perfect: i.e. there are no sequence of statements.  */
 520
 521 static bool
 522 lst_perfectly_nested_p (lst_p loop1, lst_p loop2)
 523 {
 524   if (loop1 == loop2)
 525     return true;
 526
 527   if (!LST_LOOP_P (loop1))
 528     return false;
 529
 530   return VEC_length (lst_p, LST_SEQ (loop1)) == 1
 531     && lst_perfectly_nested_p (VEC_index (lst_p, LST_SEQ (loop1), 0), loop2);
 532 }
 533
 534 /* Transform the loop nest between LOOP1 and LOOP2 into a perfect
 535    nest.  To continue the naming tradition, this function is called
 536    after perfect_nestify.  NEST is set to the perfectly nested loop
 537    that is created.  BEFORE/AFTER are set to the loops distributed
 538    before/after the loop NEST.  */
 539
 540 static void
 541 lst_perfect_nestify (lst_p loop1, lst_p loop2, lst_p *before,
 542                      lst_p *nest, lst_p *after)
 543 {
 544   poly_bb_p first, last;
 545
 546   gcc_assert (loop1 && loop2
 547               && loop1 != loop2
 548               && LST_LOOP_P (loop1) && LST_LOOP_P (loop2));
 549
 550   first = LST_PBB (lst_find_first_pbb (loop2));
 551   last = LST_PBB (lst_find_last_pbb (loop2));
 552
 553   *before = copy_lst (loop1);
 554   *nest = copy_lst (loop1);
 555   *after = copy_lst (loop1);
 556
 557   lst_remove_all_before_including_pbb (*before, first, false);
 558   lst_remove_all_before_including_pbb (*after, last, true);
 559
 560   lst_remove_all_before_excluding_pbb (*nest, first, true);
 561   lst_remove_all_before_excluding_pbb (*nest, last, false);
 562
 563   if (lst_empty_p (*before))
 564     {
 565       free_lst (*before);
 566       *before = NULL;
 567     }
 568   if (lst_empty_p (*after))
 569     {
 570       free_lst (*after);
 571       *after = NULL;
 572     }
 573   if (lst_empty_p (*nest))
 574     {
 575       free_lst (*nest);
 576       *nest = NULL;
 577     }
 578 }
 579
 580 /* Try to interchange LOOP1 with LOOP2 for all the statements of the
 581    body of LOOP2.  LOOP1 contains LOOP2.  Return true if it did the
 582    interchange.  */
 583
 584 static bool
 585 lst_try_interchange_loops (scop_p scop, lst_p loop1, lst_p loop2)
 586 {
 587   int depth1 = lst_depth (loop1);
 588   int depth2 = lst_depth (loop2);
 589   lst_p transformed;
 590
 591   lst_p before = NULL, nest = NULL, after = NULL;
 592
 593   if (!lst_perfectly_nested_p (loop1, loop2))
 594     lst_perfect_nestify (loop1, loop2, &before, &nest, &after);
 595
 596   if (!lst_interchange_profitable_p (loop2, depth1, depth2))
 597     return false;
 598
 599   lst_apply_interchange (loop2, depth1, depth2);
 600
 601   /* Sync the transformed LST information and the PBB scatterings
 602      before using the scatterings in the data dependence analysis.  */
 603   if (before || nest || after)
 604     {
 605       transformed = lst_substitute_3 (SCOP_TRANSFORMED_SCHEDULE (scop), loop1,
 606                                       before, nest, after);
 607       lst_update_scattering (transformed);
 608       free_lst (transformed);
 609     }
 610
 611   if (graphite_legal_transform (scop))
 612     {
 613       if (dump_file && (dump_flags & TDF_DETAILS))
 614         fprintf (dump_file,
 615                  "Loops at depths %d and %d will be interchanged.\n",
 616                  depth1, depth2);
 617
 618       /* Transform the SCOP_TRANSFORMED_SCHEDULE of the SCOP.  */
 619       lst_insert_in_sequence (before, loop1, true);
 620       lst_insert_in_sequence (after, loop1, false);
 621
 622       if (nest)
 623         {
 624           lst_replace (loop1, nest);
 625           free_lst (loop1);
 626         }
 627
 628       return true;
 629     }
 630
 631   /* Undo the transform.  */
 632   free_lst (before);
 633   free_lst (nest);
 634   free_lst (after);
 635   lst_apply_interchange (loop2, depth2, depth1);
 636   return false;
 637 }
 638
 639 /* Selects the inner loop in LST_SEQ (INNER_FATHER) to be interchanged
 640    with the loop OUTER in LST_SEQ (OUTER_FATHER).  */
 641
 642 static bool
 643 lst_interchange_select_inner (scop_p scop, lst_p outer_father, int outer,
 644                               lst_p inner_father)
 645 {
 646   int inner;
 647   lst_p loop1, loop2;
 648
 649   gcc_assert (outer_father
 650               && LST_LOOP_P (outer_father)
 651               && LST_LOOP_P (VEC_index (lst_p, LST_SEQ (outer_father), outer))
 652               && inner_father
 653               && LST_LOOP_P (inner_father));
 654
 655   loop1 = VEC_index (lst_p, LST_SEQ (outer_father), outer);
 656
 657   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (inner_father), inner, loop2)
 658     if (LST_LOOP_P (loop2)
 659         && (lst_try_interchange_loops (scop, loop1, loop2)
 660             || lst_interchange_select_inner (scop, outer_father, outer, loop2)))
 661       return true;
 662
 663   return false;
 664 }
 665
 666 /* Interchanges all the loops of LOOP and the loops of its body that
 667    are considered profitable to interchange.  Return the number of
 668    interchanged loops.  OUTER is the index in LST_SEQ (LOOP) that
 669    points to the next outer loop to be considered for interchange.  */
 670
 671 static int
 672 lst_interchange_select_outer (scop_p scop, lst_p loop, int outer)
 673 {
 674   lst_p l;
 675   int res = 0;
 676   int i = 0;
 677   lst_p father;
 678
 679   if (!loop || !LST_LOOP_P (loop))
 680     return 0;
 681
 682   father = LST_LOOP_FATHER (loop);
 683   if (father)
 684     {
 685       while (lst_interchange_select_inner (scop, father, outer, loop))
 686         {
 687           res++;
 688           loop = VEC_index (lst_p, LST_SEQ (father), outer);
 689         }
 690     }
 691
 692   if (LST_LOOP_P (loop))
 693     FOR_EACH_VEC_ELT (lst_p, LST_SEQ (loop), i, l)
 694       if (LST_LOOP_P (l))
 695         res += lst_interchange_select_outer (scop, l, i);
 696
 697   return res;
 698 }
 699
 700 /* Interchanges all the loop depths that are considered profitable for
 701    SCOP.  Return the number of interchanged loops.  */
 702
 703 int
 704 scop_do_interchange (scop_p scop)
 705 {
 706   int res = lst_interchange_select_outer
 707     (scop, SCOP_TRANSFORMED_SCHEDULE (scop), 0);
 708
 709   lst_update_scattering (SCOP_TRANSFORMED_SCHEDULE (scop));
 710
 711   return res;
 712 }
 713
 714
 715 #endif
 716