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