gcc/graphite-interchange.c

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