gcc/graphite-interchange.c

   1 /* Interchange heuristics and transform for loop interchange on
   2    polyhedral representation.
   3
   4    Copyright (C) 2009-2013 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
  24 #include "config.h"
  25
  26 #ifdef HAVE_cloog
  27 #include <isl/aff.h>
  28 #include <isl/set.h>
  29 #include <isl/map.h>
  30 #include <isl/union_map.h>
  31 #include <isl/ilp.h>
  32 #include <cloog/cloog.h>
  33 #include <cloog/isl/domain.h>
  34 #endif
  35
  36 #include "system.h"
  37 #include "coretypes.h"
  38 #include "tree.h"
  39 #include "gimple.h"
  40 #include "gimple-iterator.h"
  41 #include "tree-ssa-loop.h"
  42 #include "dumpfile.h"
  43 #include "cfgloop.h"
  44 #include "tree-chrec.h"
  45 #include "tree-data-ref.h"
  46 #include "tree-scalar-evolution.h"
  47 #include "sese.h"
  48
  49 #ifdef HAVE_cloog
  50 #include "graphite-poly.h"
  51
  52 /* XXX isl rewrite following comment */
  53 /* Builds a linear expression, of dimension DIM, representing PDR's
  54    memory access:
  55
  56    L = r_{n}*r_{n-1}*...*r_{1}*s_{0} + ... + r_{n}*s_{n-1} + s_{n}.
  57
  58    For an array A[10][20] with two subscript locations s0 and s1, the
  59    linear memory access is 20 * s0 + s1: a stride of 1 in subscript s0
  60    corresponds to a memory stride of 20.
  61
  62    OFFSET is a number of dimensions to prepend before the
  63    subscript dimensions: s_0, s_1, ..., s_n.
  64
  65    Thus, the final linear expression has the following format:
  66    0 .. 0_{offset} | 0 .. 0_{nit} | 0 .. 0_{gd} | 0 | c_0 c_1 ... c_n
  67    where the expression itself is:
  68    c_0 * s_0 + c_1 * s_1 + ... c_n * s_n.  */
  69
  70 static isl_constraint *
  71 build_linearized_memory_access (isl_map *map, poly_dr_p pdr)
  72 {
  73   isl_constraint *res;
  74   isl_local_space *ls = isl_local_space_from_space (isl_map_get_space (map));
  75   unsigned offset, nsubs;
  76   int i;
  77   isl_int size, subsize;
  78
  79   res = isl_equality_alloc (ls);
  80   isl_int_init (size);
  81   isl_int_set_ui (size, 1);
  82   isl_int_init (subsize);
  83   isl_int_set_ui (subsize, 1);
  84
  85   nsubs = isl_set_dim (pdr->extent, isl_dim_set);
  86   /* -1 for the already included L dimension.  */
  87   offset = isl_map_dim (map, isl_dim_out) - 1 - nsubs;
  88   res = isl_constraint_set_coefficient_si (res, isl_dim_out, offset + nsubs, -1);
  89   /* Go through all subscripts from last to first.  First dimension
  90      is the alias set, ignore it.  */
  91   for (i = nsubs - 1; i >= 1; i--)
  92     {
  93       isl_space *dc;
  94       isl_aff *aff;
  95
  96       res = isl_constraint_set_coefficient (res, isl_dim_out, offset + i, size);
  97
  98       dc = isl_set_get_space (pdr->extent);
  99       aff = isl_aff_zero_on_domain (isl_local_space_from_space (dc));
 100       aff = isl_aff_set_coefficient_si (aff, isl_dim_in, i, 1);
 101       isl_set_max (pdr->extent, aff, &subsize);
 102       isl_aff_free (aff);
 103       isl_int_mul (size, size, subsize);
 104     }
 105
 106   isl_int_clear (subsize);
 107   isl_int_clear (size);
 108
 109   return res;
 110 }
 111
 112 /* Set STRIDE to the stride of PDR in memory by advancing by one in
 113    the loop at DEPTH.  */
 114
 115 static void
 116 pdr_stride_in_loop (mpz_t stride, graphite_dim_t depth, poly_dr_p pdr)
 117 {
 118   poly_bb_p pbb = PDR_PBB (pdr);
 119   isl_map *map;
 120   isl_set *set;
 121   isl_aff *aff;
 122   isl_space *dc;
 123   isl_constraint *lma, *c;
 124   isl_int islstride;
 125   graphite_dim_t time_depth;
 126   unsigned offset, nt;
 127   unsigned i;
 128   /* XXX isl rewrite following comments.  */
 129   /* Builds a partial difference equations and inserts them
 130      into pointset powerset polyhedron P.  Polyhedron is assumed
 131      to have the format: T|I|T'|I'|G|S|S'|l1|l2.
 132
 133      TIME_DEPTH is the time dimension w.r.t. which we are
 134      differentiating.
 135      OFFSET represents the number of dimensions between
 136      columns t_{time_depth} and t'_{time_depth}.
 137      DIM_SCTR is the number of scattering dimensions.  It is
 138      essentially the dimensionality of the T vector.
 139
 140      The following equations are inserted into the polyhedron P:
 141      | t_1 = t_1'
 142      | ...
 143      | t_{time_depth-1} = t'_{time_depth-1}
 144      | t_{time_depth} = t'_{time_depth} + 1
 145      | t_{time_depth+1} = t'_{time_depth + 1}
 146      | ...
 147      | t_{dim_sctr} = t'_{dim_sctr}.  */
 148
 149   /* Add the equality: t_{time_depth} = t'_{time_depth} + 1.
 150      This is the core part of this alogrithm, since this
 151      constraint asks for the memory access stride (difference)
 152      between two consecutive points in time dimensions.  */
 153
 154   /* Add equalities:
 155      | t1 = t1'
 156      | ...
 157      | t_{time_depth-1} = t'_{time_depth-1}
 158      | t_{time_depth+1} = t'_{time_depth+1}
 159      | ...
 160      | t_{dim_sctr} = t'_{dim_sctr}
 161
 162      This means that all the time dimensions are equal except for
 163      time_depth, where the constraint is t_{depth} = t'_{depth} + 1
 164      step.  More to this: we should be careful not to add equalities
 165      to the 'coupled' dimensions, which happens when the one dimension
 166      is stripmined dimension, and the other dimension corresponds
 167      to the point loop inside stripmined dimension.  */
 168
 169   /* pdr->accesses:    [P1..nb_param,I1..nb_domain]->[a,S1..nb_subscript]
 170           ??? [P] not used for PDRs?
 171      pdr->extent:      [a,S1..nb_subscript]
 172      pbb->domain:      [P1..nb_param,I1..nb_domain]
 173      pbb->transformed: [P1..nb_param,I1..nb_domain]->[T1..Tnb_sctr]
 174           [T] includes local vars (currently unused)
 175
 176      First we create [P,I] -> [T,a,S].  */
 177
 178   map = isl_map_flat_range_product (isl_map_copy (pbb->transformed),
 179                                     isl_map_copy (pdr->accesses));
 180   /* Add a dimension for L: [P,I] -> [T,a,S,L].*/
 181   map = isl_map_add_dims (map, isl_dim_out, 1);
 182   /* Build a constraint for "lma[S] - L == 0", effectively calculating
 183      L in terms of subscripts.  */
 184   lma = build_linearized_memory_access (map, pdr);
 185   /* And add it to the map, so we now have:
 186      [P,I] -> [T,a,S,L] : lma([S]) == L.  */
 187   map = isl_map_add_constraint (map, lma);
 188
 189   /* Then we create  [P,I,P',I'] -> [T,a,S,L,T',a',S',L'].  */
 190   map = isl_map_flat_product (map, isl_map_copy (map));
 191
 192   /* Now add the equality T[time_depth] == T'[time_depth]+1.  This will
 193      force L' to be the linear address at T[time_depth] + 1. */
 194   time_depth = psct_dynamic_dim (pbb, depth);
 195   /* Length of [a,S] plus [L] ...  */
 196   offset = 1 + isl_map_dim (pdr->accesses, isl_dim_out);
 197   /* ... plus [T].  */
 198   offset += isl_map_dim (pbb->transformed, isl_dim_out);
 199
 200   c = isl_equality_alloc (isl_local_space_from_space (isl_map_get_space (map)));
 201   c = isl_constraint_set_coefficient_si (c, isl_dim_out, time_depth, 1);
 202   c = isl_constraint_set_coefficient_si (c, isl_dim_out,
 203                                          offset + time_depth, -1);
 204   c = isl_constraint_set_constant_si (c, 1);
 205   map = isl_map_add_constraint (map, c);
 206
 207   /* Now we equate most of the T/T' elements (making PITaSL nearly
 208      the same is (PITaSL)', except for one dimension, namely for 'depth'
 209      (an index into [I]), after translating to index into [T].  Take care
 210      to not produce an empty map, which indicates we wanted to equate
 211      two dimensions that are already coupled via the above time_depth
 212      dimension.  Happens with strip mining where several scatter dimension
 213      are interdependend.  */
 214   /* Length of [T].  */
 215   nt = pbb_nb_scattering_transform (pbb) + pbb_nb_local_vars (pbb);
 216   for (i = 0; i < nt; i++)
 217     if (i != time_depth)
 218       {
 219         isl_map *temp = isl_map_equate (isl_map_copy (map),
 220                                         isl_dim_out, i,
 221                                         isl_dim_out, offset + i);
 222         if (isl_map_is_empty (temp))
 223           isl_map_free (temp);
 224         else
 225           {
 226             isl_map_free (map);
 227             map = temp;
 228           }
 229       }
 230
 231   /* Now maximize the expression L' - L.  */
 232   set = isl_map_range (map);
 233   dc = isl_set_get_space (set);
 234   aff = isl_aff_zero_on_domain (isl_local_space_from_space (dc));
 235   aff = isl_aff_set_coefficient_si (aff, isl_dim_in, offset - 1, -1);
 236   aff = isl_aff_set_coefficient_si (aff, isl_dim_in, offset + offset - 1, 1);
 237   isl_int_init (islstride);
 238   isl_set_max (set, aff, &islstride);
 239   isl_int_get_gmp (islstride, stride);
 240   isl_int_clear (islstride);
 241   isl_aff_free (aff);
 242   isl_set_free (set);
 243
 244   if (dump_file && (dump_flags & TDF_DETAILS))
 245     {
 246       gmp_fprintf (dump_file, "\nStride in BB_%d, DR_%d, depth %d:  %Zd ",
 247                    pbb_index (pbb), PDR_ID (pdr), (int) depth, stride);
 248     }
 249 }
 250
 251 /* Sets STRIDES to the sum of all the strides of the data references
 252    accessed in LOOP at DEPTH.  */
 253
 254 static void
 255 memory_strides_in_loop_1 (lst_p loop, graphite_dim_t depth, mpz_t strides)
 256 {
 257   int i, j;
 258   lst_p l;
 259   poly_dr_p pdr;
 260   mpz_t s, n;
 261
 262   mpz_init (s);
 263   mpz_init (n);
 264
 265   FOR_EACH_VEC_ELT (LST_SEQ (loop), j, l)
 266     if (LST_LOOP_P (l))
 267       memory_strides_in_loop_1 (l, depth, strides);
 268     else
 269       FOR_EACH_VEC_ELT (PBB_DRS (LST_PBB (l)), i, pdr)
 270         {
 271           pdr_stride_in_loop (s, depth, pdr);
 272           mpz_set_si (n, PDR_NB_REFS (pdr));
 273           mpz_mul (s, s, n);
 274           mpz_add (strides, strides, s);
 275         }
 276
 277   mpz_clear (s);
 278   mpz_clear (n);
 279 }
 280
 281 /* Sets STRIDES to the sum of all the strides of the data references
 282    accessed in LOOP at DEPTH.  */
 283
 284 static void
 285 memory_strides_in_loop (lst_p loop, graphite_dim_t depth, mpz_t strides)
 286 {
 287   if (mpz_cmp_si (loop->memory_strides, -1) == 0)
 288     {
 289       mpz_set_si (strides, 0);
 290       memory_strides_in_loop_1 (loop, depth, strides);
 291     }
 292   else
 293     mpz_set (strides, loop->memory_strides);
 294 }
 295
 296 /* Return true when the interchange of loops LOOP1 and LOOP2 is
 297    profitable.
 298
 299    Example:
 300
 301    | int a[100][100];
 302    |
 303    | int
 304    | foo (int N)
 305    | {
 306    |   int j;
 307    |   int i;
 308    |
 309    |   for (i = 0; i < N; i++)
 310    |     for (j = 0; j < N; j++)
 311    |       a[j][2 * i] += 1;
 312    |
 313    |   return a[N][12];
 314    | }
 315
 316    The data access A[j][i] is described like this:
 317
 318    | i   j   N   a  s0  s1   1
 319    | 0   0   0   1   0   0  -5    = 0
 320    | 0  -1   0   0   1   0   0    = 0
 321    |-2   0   0   0   0   1   0    = 0
 322    | 0   0   0   0   1   0   0   >= 0
 323    | 0   0   0   0   0   1   0   >= 0
 324    | 0   0   0   0  -1   0 100   >= 0
 325    | 0   0   0   0   0  -1 100   >= 0
 326
 327    The linearized memory access L to A[100][100] is:
 328
 329    | i   j   N   a  s0  s1   1
 330    | 0   0   0   0 100   1   0
 331
 332    TODO: the shown format is not valid as it does not show the fact
 333    that the iteration domain "i j" is transformed using the scattering.
 334
 335    Next, to measure the impact of iterating once in loop "i", we build
 336    a maximization problem: first, we add to DR accesses the dimensions
 337    k, s2, s3, L1 = 100 * s0 + s1, L2, and D1: this is the polyhedron P1.
 338    L1 and L2 are the linearized memory access functions.
 339
 340    | i   j   N   a  s0  s1   k  s2  s3  L1  L2  D1   1
 341    | 0   0   0   1   0   0   0   0   0   0   0   0  -5    = 0  alias = 5
 342    | 0  -1   0   0   1   0   0   0   0   0   0   0   0    = 0  s0 = j
 343    |-2   0   0   0   0   1   0   0   0   0   0   0   0    = 0  s1 = 2 * i
 344    | 0   0   0   0   1   0   0   0   0   0   0   0   0   >= 0
 345    | 0   0   0   0   0   1   0   0   0   0   0   0   0   >= 0
 346    | 0   0   0   0  -1   0   0   0   0   0   0   0 100   >= 0
 347    | 0   0   0   0   0  -1   0   0   0   0   0   0 100   >= 0
 348    | 0   0   0   0 100   1   0   0   0  -1   0   0   0    = 0  L1 = 100 * s0 + s1
 349
 350    Then, we generate the polyhedron P2 by interchanging the dimensions
 351    (s0, s2), (s1, s3), (L1, L2), (k, i)
 352
 353    | i   j   N   a  s0  s1   k  s2  s3  L1  L2  D1   1
 354    | 0   0   0   1   0   0   0   0   0   0   0   0  -5    = 0  alias = 5
 355    | 0  -1   0   0   0   0   0   1   0   0   0   0   0    = 0  s2 = j
 356    | 0   0   0   0   0   0  -2   0   1   0   0   0   0    = 0  s3 = 2 * k
 357    | 0   0   0   0   0   0   0   1   0   0   0   0   0   >= 0
 358    | 0   0   0   0   0   0   0   0   1   0   0   0   0   >= 0
 359    | 0   0   0   0   0   0   0  -1   0   0   0   0 100   >= 0
 360    | 0   0   0   0   0   0   0   0  -1   0   0   0 100   >= 0
 361    | 0   0   0   0   0   0   0 100   1   0  -1   0   0    = 0  L2 = 100 * s2 + s3
 362
 363    then we add to P2 the equality k = i + 1:
 364
 365    |-1   0   0   0   0   0   1   0   0   0   0   0  -1    = 0  k = i + 1
 366
 367    and finally we maximize the expression "D1 = max (P1 inter P2, L2 - L1)".
 368
 369    Similarly, to determine the impact of one iteration on loop "j", we
 370    interchange (k, j), we add "k = j + 1", and we compute D2 the
 371    maximal value of the difference.
 372
 373    Finally, the profitability test is D1 < D2: if in the outer loop
 374    the strides are smaller than in the inner loop, then it is
 375    profitable to interchange the loops at DEPTH1 and DEPTH2.  */
 376
 377 static bool
 378 lst_interchange_profitable_p (lst_p nest, int depth1, int depth2)
 379 {
 380   mpz_t d1, d2;
 381   bool res;
 382
 383   gcc_assert (depth1 < depth2);
 384
 385   mpz_init (d1);
 386   mpz_init (d2);
 387
 388   memory_strides_in_loop (nest, depth1, d1);
 389   memory_strides_in_loop (nest, depth2, d2);
 390
 391   res = mpz_cmp (d1, d2) < 0;
 392
 393   mpz_clear (d1);
 394   mpz_clear (d2);
 395
 396   return res;
 397 }
 398
 399 /* Interchanges the loops at DEPTH1 and DEPTH2 of the original
 400    scattering and assigns the resulting polyhedron to the transformed
 401    scattering.  */
 402
 403 static void
 404 pbb_interchange_loop_depths (graphite_dim_t depth1, graphite_dim_t depth2,
 405                              poly_bb_p pbb)
 406 {
 407   unsigned i;
 408   unsigned dim1 = psct_dynamic_dim (pbb, depth1);
 409   unsigned dim2 = psct_dynamic_dim (pbb, depth2);
 410   isl_space *d = isl_map_get_space (pbb->transformed);
 411   isl_space *d1 = isl_space_range (d);
 412   unsigned n = isl_space_dim (d1, isl_dim_out);
 413   isl_space *d2 = isl_space_add_dims (d1, isl_dim_in, n);
 414   isl_map *x = isl_map_universe (d2);
 415
 416   x = isl_map_equate (x, isl_dim_in, dim1, isl_dim_out, dim2);
 417   x = isl_map_equate (x, isl_dim_in, dim2, isl_dim_out, dim1);
 418
 419   for (i = 0; i < n; i++)
 420     if (i != dim1 && i != dim2)
 421       x = isl_map_equate (x, isl_dim_in, i, isl_dim_out, i);
 422
 423   pbb->transformed = isl_map_apply_range (pbb->transformed, x);
 424 }
 425
 426 /* Apply the interchange of loops at depths DEPTH1 and DEPTH2 to all
 427    the statements below LST.  */
 428
 429 static void
 430 lst_apply_interchange (lst_p lst, int depth1, int depth2)
 431 {
 432   if (!lst)
 433     return;
 434
 435   if (LST_LOOP_P (lst))
 436     {
 437       int i;
 438       lst_p l;
 439
 440       FOR_EACH_VEC_ELT (LST_SEQ (lst), i, l)
 441         lst_apply_interchange (l, depth1, depth2);
 442     }
 443   else
 444     pbb_interchange_loop_depths (depth1, depth2, LST_PBB (lst));
 445 }
 446
 447 /* Return true when the nest starting at LOOP1 and ending on LOOP2 is
 448    perfect: i.e. there are no sequence of statements.  */
 449
 450 static bool
 451 lst_perfectly_nested_p (lst_p loop1, lst_p loop2)
 452 {
 453   if (loop1 == loop2)
 454     return true;
 455
 456   if (!LST_LOOP_P (loop1))
 457     return false;
 458
 459   return LST_SEQ (loop1).length () == 1
 460          && lst_perfectly_nested_p (LST_SEQ (loop1)[0], loop2);
 461 }
 462
 463 /* Transform the loop nest between LOOP1 and LOOP2 into a perfect
 464    nest.  To continue the naming tradition, this function is called
 465    after perfect_nestify.  NEST is set to the perfectly nested loop
 466    that is created.  BEFORE/AFTER are set to the loops distributed
 467    before/after the loop NEST.  */
 468
 469 static void
 470 lst_perfect_nestify (lst_p loop1, lst_p loop2, lst_p *before,
 471                      lst_p *nest, lst_p *after)
 472 {
 473   poly_bb_p first, last;
 474
 475   gcc_assert (loop1 && loop2
 476               && loop1 != loop2
 477               && LST_LOOP_P (loop1) && LST_LOOP_P (loop2));
 478
 479   first = LST_PBB (lst_find_first_pbb (loop2));
 480   last = LST_PBB (lst_find_last_pbb (loop2));
 481
 482   *before = copy_lst (loop1);
 483   *nest = copy_lst (loop1);
 484   *after = copy_lst (loop1);
 485
 486   lst_remove_all_before_including_pbb (*before, first, false);
 487   lst_remove_all_before_including_pbb (*after, last, true);
 488
 489   lst_remove_all_before_excluding_pbb (*nest, first, true);
 490   lst_remove_all_before_excluding_pbb (*nest, last, false);
 491
 492   if (lst_empty_p (*before))
 493     {
 494       free_lst (*before);
 495       *before = NULL;
 496     }
 497   if (lst_empty_p (*after))
 498     {
 499       free_lst (*after);
 500       *after = NULL;
 501     }
 502   if (lst_empty_p (*nest))
 503     {
 504       free_lst (*nest);
 505       *nest = NULL;
 506     }
 507 }
 508
 509 /* Try to interchange LOOP1 with LOOP2 for all the statements of the
 510    body of LOOP2.  LOOP1 contains LOOP2.  Return true if it did the
 511    interchange.  */
 512
 513 static bool
 514 lst_try_interchange_loops (scop_p scop, lst_p loop1, lst_p loop2)
 515 {
 516   int depth1 = lst_depth (loop1);
 517   int depth2 = lst_depth (loop2);
 518   lst_p transformed;
 519
 520   lst_p before = NULL, nest = NULL, after = NULL;
 521
 522   if (!lst_perfectly_nested_p (loop1, loop2))
 523     lst_perfect_nestify (loop1, loop2, &before, &nest, &after);
 524
 525   if (!lst_interchange_profitable_p (loop2, depth1, depth2))
 526     return false;
 527
 528   lst_apply_interchange (loop2, depth1, depth2);
 529
 530   /* Sync the transformed LST information and the PBB scatterings
 531      before using the scatterings in the data dependence analysis.  */
 532   if (before || nest || after)
 533     {
 534       transformed = lst_substitute_3 (SCOP_TRANSFORMED_SCHEDULE (scop), loop1,
 535                                       before, nest, after);
 536       lst_update_scattering (transformed);
 537       free_lst (transformed);
 538     }
 539
 540   if (graphite_legal_transform (scop))
 541     {
 542       if (dump_file && (dump_flags & TDF_DETAILS))
 543         fprintf (dump_file,
 544                  "Loops at depths %d and %d will be interchanged.\n",
 545                  depth1, depth2);
 546
 547       /* Transform the SCOP_TRANSFORMED_SCHEDULE of the SCOP.  */
 548       lst_insert_in_sequence (before, loop1, true);
 549       lst_insert_in_sequence (after, loop1, false);
 550
 551       if (nest)
 552         {
 553           lst_replace (loop1, nest);
 554           free_lst (loop1);
 555         }
 556
 557       return true;
 558     }
 559
 560   /* Undo the transform.  */
 561   free_lst (before);
 562   free_lst (nest);
 563   free_lst (after);
 564   lst_apply_interchange (loop2, depth2, depth1);
 565   return false;
 566 }
 567
 568 /* Selects the inner loop in LST_SEQ (INNER_FATHER) to be interchanged
 569    with the loop OUTER in LST_SEQ (OUTER_FATHER).  */
 570
 571 static bool
 572 lst_interchange_select_inner (scop_p scop, lst_p outer_father, int outer,
 573                               lst_p inner_father)
 574 {
 575   int inner;
 576   lst_p loop1, loop2;
 577
 578   gcc_assert (outer_father
 579               && LST_LOOP_P (outer_father)
 580               && LST_LOOP_P (LST_SEQ (outer_father)[outer])
 581               && inner_father
 582               && LST_LOOP_P (inner_father));
 583
 584   loop1 = LST_SEQ (outer_father)[outer];
 585
 586   FOR_EACH_VEC_ELT (LST_SEQ (inner_father), inner, loop2)
 587     if (LST_LOOP_P (loop2)
 588         && (lst_try_interchange_loops (scop, loop1, loop2)
 589             || lst_interchange_select_inner (scop, outer_father, outer, loop2)))
 590       return true;
 591
 592   return false;
 593 }
 594
 595 /* Interchanges all the loops of LOOP and the loops of its body that
 596    are considered profitable to interchange.  Return the number of
 597    interchanged loops.  OUTER is the index in LST_SEQ (LOOP) that
 598    points to the next outer loop to be considered for interchange.  */
 599
 600 static int
 601 lst_interchange_select_outer (scop_p scop, lst_p loop, int outer)
 602 {
 603   lst_p l;
 604   int res = 0;
 605   int i = 0;
 606   lst_p father;
 607
 608   if (!loop || !LST_LOOP_P (loop))
 609     return 0;
 610
 611   father = LST_LOOP_FATHER (loop);
 612   if (father)
 613     {
 614       while (lst_interchange_select_inner (scop, father, outer, loop))
 615         {
 616           res++;
 617           loop = LST_SEQ (father)[outer];
 618         }
 619     }
 620
 621   if (LST_LOOP_P (loop))
 622     FOR_EACH_VEC_ELT (LST_SEQ (loop), i, l)
 623       if (LST_LOOP_P (l))
 624         res += lst_interchange_select_outer (scop, l, i);
 625
 626   return res;
 627 }
 628
 629 /* Interchanges all the loop depths that are considered profitable for
 630    SCOP.  Return the number of interchanged loops.  */
 631
 632 int
 633 scop_do_interchange (scop_p scop)
 634 {
 635   int res = lst_interchange_select_outer
 636     (scop, SCOP_TRANSFORMED_SCHEDULE (scop), 0);
 637
 638   lst_update_scattering (SCOP_TRANSFORMED_SCHEDULE (scop));
 639
 640   return res;
 641 }
 642
 643
 644 #endif
 645