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