gcc/graphite-interchange.c

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