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