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