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