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