gcc/graphite-interchange.c

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