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