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