gcc/graphite-interchange.c

   1 /* Interchange heuristics and transform for loop interchange on
   2    polyhedral representation.
   3
   4    Copyright (C) 2009, 2010 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 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "tm.h"
  27 #include "ggc.h"
  28 #include "tree.h"
  29 #include "rtl.h"
  30 #include "output.h"
  31 #include "basic-block.h"
  32 #include "diagnostic.h"
  33 #include "tree-flow.h"
  34 #include "tree-dump.h"
  35 #include "timevar.h"
  36 #include "cfgloop.h"
  37 #include "tree-chrec.h"
  38 #include "tree-data-ref.h"
  39 #include "tree-scalar-evolution.h"
  40 #include "tree-pass.h"
  41 #include "domwalk.h"
  42 #include "value-prof.h"
  43 #include "pointer-set.h"
  44 #include "gimple.h"
  45 #include "params.h"
  46
  47 #ifdef HAVE_cloog
  48 #include "ppl_c.h"
  49 #include "sese.h"
  50 #include "graphite-ppl.h"
  51 #include "graphite.h"
  52 #include "graphite-poly.h"
  53
  54 /* Builds a linear expression, of dimension DIM, representing PDR's
  55    memory access:
  56
  57    L = r_{n}*r_{n-1}*...*r_{1}*s_{0} + ... + r_{n}*s_{n-1} + s_{n}.
  58
  59    For an array A[10][20] with two subscript locations s0 and s1, the
  60    linear memory access is 20 * s0 + s1: a stride of 1 in subscript s0
  61    corresponds to a memory stride of 20.
  62
  63    OFFSET is a number of dimensions to prepend before the
  64    subscript dimensions: s_0, s_1, ..., s_n.
  65
  66    Thus, the final linear expression has the following format:
  67    0 .. 0_{offset} | 0 .. 0_{nit} | 0 .. 0_{gd} | 0 | c_0 c_1 ... c_n
  68    where the expression itself is:
  69    c_0 * s_0 + c_1 * s_1 + ... c_n * s_n.  */
  70
  71 static ppl_Linear_Expression_t
  72 build_linearized_memory_access (ppl_dimension_type offset, poly_dr_p pdr)
  73 {
  74   ppl_Linear_Expression_t res;
  75   ppl_Linear_Expression_t le;
  76   ppl_dimension_type i;
  77   ppl_dimension_type first = pdr_subscript_dim (pdr, 0);
  78   ppl_dimension_type last = pdr_subscript_dim (pdr, PDR_NB_SUBSCRIPTS (pdr));
  79   mpz_t size, sub_size;
  80   graphite_dim_t dim = offset + pdr_dim (pdr);
  81
  82   ppl_new_Linear_Expression_with_dimension (&res, dim);
  83
  84   mpz_init (size);
  85   mpz_set_si (size, 1);
  86   mpz_init (sub_size);
  87   mpz_set_si (sub_size, 1);
  88
  89   for (i = last - 1; i >= first; i--)
  90     {
  91       ppl_set_coef_gmp (res, i + offset, size);
  92
  93       ppl_new_Linear_Expression_with_dimension (&le, dim - offset);
  94       ppl_set_coef (le, i, 1);
  95       ppl_max_for_le_pointset (PDR_ACCESSES (pdr), le, sub_size);
  96       mpz_mul (size, size, sub_size);
  97       ppl_delete_Linear_Expression (le);
  98     }
  99
 100   mpz_clear (sub_size);
 101   mpz_clear (size);
 102   return res;
 103 }
 104
 105 /* Builds a partial difference equations and inserts them
 106    into pointset powerset polyhedron P.  Polyhedron is assumed
 107    to have the format: T|I|T'|I'|G|S|S'|l1|l2.
 108
 109    TIME_DEPTH is the time dimension w.r.t. which we are
 110    differentiating.
 111    OFFSET represents the number of dimensions between
 112    columns t_{time_depth} and t'_{time_depth}.
 113    DIM_SCTR is the number of scattering dimensions.  It is
 114    essentially the dimensionality of the T vector.
 115
 116    The following equations are inserted into the polyhedron P:
 117     | t_1 = t_1'
 118     | ...
 119     | t_{time_depth-1} = t'_{time_depth-1}
 120     | t_{time_depth} = t'_{time_depth} + 1
 121     | t_{time_depth+1} = t'_{time_depth + 1}
 122     | ...
 123     | t_{dim_sctr} = t'_{dim_sctr}.  */
 124
 125 static void
 126 build_partial_difference (ppl_Pointset_Powerset_C_Polyhedron_t *p,
 127                           ppl_dimension_type time_depth,
 128                           ppl_dimension_type offset,
 129                           ppl_dimension_type dim_sctr)
 130 {
 131   ppl_Constraint_t new_cstr;
 132   ppl_Linear_Expression_t le;
 133   ppl_dimension_type i;
 134   ppl_dimension_type dim;
 135   ppl_Pointset_Powerset_C_Polyhedron_t temp;
 136
 137   /* Add the equality: t_{time_depth} = t'_{time_depth} + 1.
 138      This is the core part of this alogrithm, since this
 139      constraint asks for the memory access stride (difference)
 140      between two consecutive points in time dimensions.  */
 141
 142   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (*p, &dim);
 143   ppl_new_Linear_Expression_with_dimension (&le, dim);
 144   ppl_set_coef (le, time_depth, 1);
 145   ppl_set_coef (le, time_depth + offset, -1);
 146   ppl_set_inhomogeneous (le, 1);
 147   ppl_new_Constraint (&new_cstr, le, PPL_CONSTRAINT_TYPE_EQUAL);
 148   ppl_Pointset_Powerset_C_Polyhedron_add_constraint (*p, new_cstr);
 149   ppl_delete_Linear_Expression (le);
 150   ppl_delete_Constraint (new_cstr);
 151
 152   /* Add equalities:
 153      | t1 = t1'
 154      | ...
 155      | t_{time_depth-1} = t'_{time_depth-1}
 156      | t_{time_depth+1} = t'_{time_depth+1}
 157      | ...
 158      | t_{dim_sctr} = t'_{dim_sctr}
 159
 160      This means that all the time dimensions are equal except for
 161      time_depth, where the constraint is t_{depth} = t'_{depth} + 1
 162      step.  More to this: we should be carefull not to add equalities
 163      to the 'coupled' dimensions, which happens when the one dimension
 164      is stripmined dimension, and the other dimension corresponds
 165      to the point loop inside stripmined dimension.  */
 166
 167   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron (&temp, *p);
 168
 169   for (i = 0; i < dim_sctr; i++)
 170     if (i != time_depth)
 171       {
 172         ppl_new_Linear_Expression_with_dimension (&le, dim);
 173         ppl_set_coef (le, i, 1);
 174         ppl_set_coef (le, i + offset, -1);
 175         ppl_new_Constraint (&new_cstr, le, PPL_CONSTRAINT_TYPE_EQUAL);
 176         ppl_Pointset_Powerset_C_Polyhedron_add_constraint (temp, new_cstr);
 177
 178         if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (temp))
 179           {
 180             ppl_delete_Pointset_Powerset_C_Polyhedron (temp);
 181             ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron (&temp, *p);
 182           }
 183         else
 184           ppl_Pointset_Powerset_C_Polyhedron_add_constraint (*p, new_cstr);
 185         ppl_delete_Linear_Expression (le);
 186         ppl_delete_Constraint (new_cstr);
 187       }
 188
 189   ppl_delete_Pointset_Powerset_C_Polyhedron (temp);
 190 }
 191
 192
 193 /* Set STRIDE to the stride of PDR in memory by advancing by one in
 194    the loop at DEPTH.  */
 195
 196 static void
 197 pdr_stride_in_loop (mpz_t stride, graphite_dim_t depth, poly_dr_p pdr)
 198 {
 199   ppl_dimension_type time_depth;
 200   ppl_Linear_Expression_t le, lma;
 201   ppl_Constraint_t new_cstr;
 202   ppl_dimension_type i, *map;
 203   ppl_Pointset_Powerset_C_Polyhedron_t p1, p2, sctr;
 204   graphite_dim_t nb_subscripts = PDR_NB_SUBSCRIPTS (pdr) + 1;
 205   poly_bb_p pbb = PDR_PBB (pdr);
 206   ppl_dimension_type offset = pbb_nb_scattering_transform (pbb)
 207                               + pbb_nb_local_vars (pbb)
 208                               + pbb_dim_iter_domain (pbb);
 209   ppl_dimension_type offsetg = offset + pbb_nb_params (pbb);
 210   ppl_dimension_type dim_sctr = pbb_nb_scattering_transform (pbb)
 211                                 + pbb_nb_local_vars (pbb);
 212   ppl_dimension_type dim_L1 = offset + offsetg + 2 * nb_subscripts;
 213   ppl_dimension_type dim_L2 = offset + offsetg + 2 * nb_subscripts + 1;
 214   ppl_dimension_type new_dim = offset + offsetg + 2 * nb_subscripts + 2;
 215
 216   /* The resulting polyhedron should have the following format:
 217      T|I|T'|I'|G|S|S'|l1|l2
 218      where:
 219      | T = t_1..t_{dim_sctr}
 220      | I = i_1..i_{dim_iter_domain}
 221      | T'= t'_1..t'_{dim_sctr}
 222      | I'= i'_1..i'_{dim_iter_domain}
 223      | G = g_1..g_{nb_params}
 224      | S = s_1..s_{nb_subscripts}
 225      | S'= s'_1..s'_{nb_subscripts}
 226      | l1 and l2 are scalars.
 227
 228      Some invariants:
 229      offset = dim_sctr + dim_iter_domain + nb_local_vars
 230      offsetg = dim_sctr + dim_iter_domain + nb_local_vars + nb_params.  */
 231
 232   /* Construct the T|I|0|0|G|0|0|0|0 part.  */
 233   {
 234     ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
 235       (&sctr, PBB_TRANSFORMED_SCATTERING (pbb));
 236     ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed
 237       (sctr, 2 * nb_subscripts + 2);
 238     ppl_insert_dimensions_pointset (sctr, offset, offset);
 239   }
 240
 241   /* Construct the 0|I|0|0|G|S|0|0|0 part.  */
 242   {
 243     ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 244       (&p1, PDR_ACCESSES (pdr));
 245     ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed
 246       (p1, nb_subscripts + 2);
 247     ppl_insert_dimensions_pointset (p1, 0, dim_sctr);
 248     ppl_insert_dimensions_pointset (p1, offset, offset);
 249   }
 250
 251   /* Construct the 0|0|0|0|0|S|0|l1|0 part.  */
 252   {
 253     lma = build_linearized_memory_access (offset + dim_sctr, pdr);
 254     ppl_set_coef (lma, dim_L1, -1);
 255     ppl_new_Constraint (&new_cstr, lma, PPL_CONSTRAINT_TYPE_EQUAL);
 256     ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p1, new_cstr);
 257     ppl_delete_Linear_Expression (lma);
 258     ppl_delete_Constraint (new_cstr);
 259   }
 260
 261   /* Now intersect all the parts to get the polyhedron P1:
 262      T|I|0|0|G|0|0|0 |0
 263      0|I|0|0|G|S|0|0 |0
 264      0|0|0|0|0|S|0|l1|0
 265      ------------------
 266      T|I|0|0|G|S|0|l1|0.  */
 267
 268   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (p1, sctr);
 269   ppl_delete_Pointset_Powerset_C_Polyhedron (sctr);
 270
 271   /* Build P2, which would have the following form:
 272      0|0|T'|I'|G|0|S'|0|l2
 273
 274      P2 is built, by remapping the P1 polyhedron:
 275      T|I|0|0|G|S|0|l1|0
 276
 277      using the following mapping:
 278      T->T'
 279      I->I'
 280      S->S'
 281      l1->l2.  */
 282   {
 283     ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 284       (&p2, p1);
 285
 286     map = ppl_new_id_map (new_dim);
 287
 288     /* TI -> T'I'.  */
 289     for (i = 0; i < offset; i++)
 290       ppl_interchange (map, i, i + offset);
 291
 292     /* l1 -> l2.  */
 293     ppl_interchange (map, dim_L1, dim_L2);
 294
 295     /* S -> S'.  */
 296     for (i = 0; i < nb_subscripts; i++)
 297       ppl_interchange (map, offset + offsetg + i,
 298                        offset + offsetg + nb_subscripts + i);
 299
 300     ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (p2, map, new_dim);
 301     free (map);
 302   }
 303
 304   time_depth = psct_dynamic_dim (pbb, depth);
 305
 306   /* P1 = P1 inter P2.  */
 307   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (p1, p2);
 308   build_partial_difference (&p1, time_depth, offset, dim_sctr);
 309
 310   /* Maximise the expression L2 - L1.  */
 311   {
 312     ppl_new_Linear_Expression_with_dimension (&le, new_dim);
 313     ppl_set_coef (le, dim_L2, 1);
 314     ppl_set_coef (le, dim_L1, -1);
 315     ppl_max_for_le_pointset (p1, le, stride);
 316   }
 317
 318   if (dump_file && (dump_flags & TDF_DETAILS))
 319     {
 320       char *str;
 321       void (*gmp_free) (void *, size_t);
 322
 323       fprintf (dump_file, "\nStride in BB_%d, DR_%d, depth %d:",
 324                pbb_index (pbb), PDR_ID (pdr), (int) depth);
 325       str = mpz_get_str (0, 10, stride);
 326       fprintf (dump_file, "  %s ", str);
 327       mp_get_memory_functions (NULL, NULL, &gmp_free);
 328       (*gmp_free) (str, strlen (str) + 1);
 329     }
 330
 331   ppl_delete_Pointset_Powerset_C_Polyhedron (p1);
 332   ppl_delete_Pointset_Powerset_C_Polyhedron (p2);
 333   ppl_delete_Linear_Expression (le);
 334 }
 335
 336
 337 /* Sets STRIDES to the sum of all the strides of the data references
 338    accessed in LOOP at DEPTH.  */
 339
 340 static void
 341 memory_strides_in_loop_1 (lst_p loop, graphite_dim_t depth, mpz_t strides)
 342 {
 343   int i, j;
 344   lst_p l;
 345   poly_dr_p pdr;
 346   mpz_t s, n;
 347
 348   mpz_init (s);
 349   mpz_init (n);
 350
 351   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (loop), j, l)
 352     if (LST_LOOP_P (l))
 353       memory_strides_in_loop_1 (l, depth, strides);
 354     else
 355       FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (LST_PBB (l)), i, pdr)
 356         {
 357           pdr_stride_in_loop (s, depth, pdr);
 358           mpz_set_si (n, PDR_NB_REFS (pdr));
 359           mpz_mul (s, s, n);
 360           mpz_add (strides, strides, s);
 361         }
 362
 363   mpz_clear (s);
 364   mpz_clear (n);
 365 }
 366
 367 /* Sets STRIDES to the sum of all the strides of the data references
 368    accessed in LOOP at DEPTH.  */
 369
 370 static void
 371 memory_strides_in_loop (lst_p loop, graphite_dim_t depth, mpz_t strides)
 372 {
 373   if (mpz_cmp_si (loop->memory_strides, -1) == 0)
 374     {
 375       mpz_set_si (strides, 0);
 376       memory_strides_in_loop_1 (loop, depth, strides);
 377     }
 378   else
 379     mpz_set (strides, loop->memory_strides);
 380 }
 381
 382 /* Return true when the interchange of loops LOOP1 and LOOP2 is
 383    profitable.
 384
 385    Example:
 386
 387    | int a[100][100];
 388    |
 389    | int
 390    | foo (int N)
 391    | {
 392    |   int j;
 393    |   int i;
 394    |
 395    |   for (i = 0; i < N; i++)
 396    |     for (j = 0; j < N; j++)
 397    |       a[j][2 * i] += 1;
 398    |
 399    |   return a[N][12];
 400    | }
 401
 402    The data access A[j][i] is described like this:
 403
 404    | i   j   N   a  s0  s1   1
 405    | 0   0   0   1   0   0  -5    = 0
 406    | 0  -1   0   0   1   0   0    = 0
 407    |-2   0   0   0   0   1   0    = 0
 408    | 0   0   0   0   1   0   0   >= 0
 409    | 0   0   0   0   0   1   0   >= 0
 410    | 0   0   0   0  -1   0 100   >= 0
 411    | 0   0   0   0   0  -1 100   >= 0
 412
 413    The linearized memory access L to A[100][100] is:
 414
 415    | i   j   N   a  s0  s1   1
 416    | 0   0   0   0 100   1   0
 417
 418    TODO: the shown format is not valid as it does not show the fact
 419    that the iteration domain "i j" is transformed using the scattering.
 420
 421    Next, to measure the impact of iterating once in loop "i", we build
 422    a maximization problem: first, we add to DR accesses the dimensions
 423    k, s2, s3, L1 = 100 * s0 + s1, L2, and D1: this is the polyhedron P1.
 424    L1 and L2 are the linearized memory access functions.
 425
 426    | i   j   N   a  s0  s1   k  s2  s3  L1  L2  D1   1
 427    | 0   0   0   1   0   0   0   0   0   0   0   0  -5    = 0  alias = 5
 428    | 0  -1   0   0   1   0   0   0   0   0   0   0   0    = 0  s0 = j
 429    |-2   0   0   0   0   1   0   0   0   0   0   0   0    = 0  s1 = 2 * i
 430    | 0   0   0   0   1   0   0   0   0   0   0   0   0   >= 0
 431    | 0   0   0   0   0   1   0   0   0   0   0   0   0   >= 0
 432    | 0   0   0   0  -1   0   0   0   0   0   0   0 100   >= 0
 433    | 0   0   0   0   0  -1   0   0   0   0   0   0 100   >= 0
 434    | 0   0   0   0 100   1   0   0   0  -1   0   0   0    = 0  L1 = 100 * s0 + s1
 435
 436    Then, we generate the polyhedron P2 by interchanging the dimensions
 437    (s0, s2), (s1, s3), (L1, L2), (k, i)
 438
 439    | i   j   N   a  s0  s1   k  s2  s3  L1  L2  D1   1
 440    | 0   0   0   1   0   0   0   0   0   0   0   0  -5    = 0  alias = 5
 441    | 0  -1   0   0   0   0   0   1   0   0   0   0   0    = 0  s2 = j
 442    | 0   0   0   0   0   0  -2   0   1   0   0   0   0    = 0  s3 = 2 * k
 443    | 0   0   0   0   0   0   0   1   0   0   0   0   0   >= 0
 444    | 0   0   0   0   0   0   0   0   1   0   0   0   0   >= 0
 445    | 0   0   0   0   0   0   0  -1   0   0   0   0 100   >= 0
 446    | 0   0   0   0   0   0   0   0  -1   0   0   0 100   >= 0
 447    | 0   0   0   0   0   0   0 100   1   0  -1   0   0    = 0  L2 = 100 * s2 + s3
 448
 449    then we add to P2 the equality k = i + 1:
 450
 451    |-1   0   0   0   0   0   1   0   0   0   0   0  -1    = 0  k = i + 1
 452
 453    and finally we maximize the expression "D1 = max (P1 inter P2, L2 - L1)".
 454
 455    Similarly, to determine the impact of one iteration on loop "j", we
 456    interchange (k, j), we add "k = j + 1", and we compute D2 the
 457    maximal value of the difference.
 458
 459    Finally, the profitability test is D1 < D2: if in the outer loop
 460    the strides are smaller than in the inner loop, then it is
 461    profitable to interchange the loops at DEPTH1 and DEPTH2.  */
 462
 463 static bool
 464 lst_interchange_profitable_p (lst_p loop1, lst_p loop2)
 465 {
 466   mpz_t d1, d2;
 467   bool res;
 468
 469   gcc_assert (loop1 && loop2
 470               && LST_LOOP_P (loop1) && LST_LOOP_P (loop2)
 471               && lst_depth (loop1) < lst_depth (loop2));
 472
 473   mpz_init (d1);
 474   mpz_init (d2);
 475
 476   memory_strides_in_loop (loop1, lst_depth (loop1), d1);
 477   memory_strides_in_loop (loop2, lst_depth (loop2), d2);
 478
 479   res = mpz_cmp (d1, d2) < 0;
 480
 481   mpz_clear (d1);
 482   mpz_clear (d2);
 483
 484   return res;
 485 }
 486
 487 /* Interchanges the loops at DEPTH1 and DEPTH2 of the original
 488    scattering and assigns the resulting polyhedron to the transformed
 489    scattering.  */
 490
 491 static void
 492 pbb_interchange_loop_depths (graphite_dim_t depth1, graphite_dim_t depth2,
 493                              poly_bb_p pbb)
 494 {
 495   ppl_dimension_type i, dim;
 496   ppl_dimension_type *map;
 497   ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
 498   ppl_dimension_type dim1 = psct_dynamic_dim (pbb, depth1);
 499   ppl_dimension_type dim2 = psct_dynamic_dim (pbb, depth2);
 500
 501   ppl_Polyhedron_space_dimension (poly, &dim);
 502   map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
 503
 504   for (i = 0; i < dim; i++)
 505     map[i] = i;
 506
 507   map[dim1] = dim2;
 508   map[dim2] = dim1;
 509
 510   ppl_Polyhedron_map_space_dimensions (poly, map, dim);
 511   free (map);
 512 }
 513
 514 /* Apply the interchange of loops at depths DEPTH1 and DEPTH2 to all
 515    the statements below LST.  */
 516
 517 static void
 518 lst_apply_interchange (lst_p lst, int depth1, int depth2)
 519 {
 520   if (!lst)
 521     return;
 522
 523   if (LST_LOOP_P (lst))
 524     {
 525       int i;
 526       lst_p l;
 527
 528       FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
 529         lst_apply_interchange (l, depth1, depth2);
 530     }
 531   else
 532     pbb_interchange_loop_depths (depth1, depth2, LST_PBB (lst));
 533 }
 534
 535 /* Return true when the nest starting at LOOP1 and ending on LOOP2 is
 536    perfect: i.e. there are no sequence of statements.  */
 537
 538 static bool
 539 lst_perfectly_nested_p (lst_p loop1, lst_p loop2)
 540 {
 541   if (loop1 == loop2)
 542     return true;
 543
 544   if (!LST_LOOP_P (loop1))
 545     return false;
 546
 547   return VEC_length (lst_p, LST_SEQ (loop1)) == 1
 548     && lst_perfectly_nested_p (VEC_index (lst_p, LST_SEQ (loop1), 0), loop2);
 549 }
 550
 551 /* Transform the loop nest between LOOP1 and LOOP2 into a perfect
 552    nest.  To continue the naming tradition, this function is called
 553    after perfect_nestify.  NEST is set to the perfectly nested loop
 554    that is created.  BEFORE/AFTER are set to the loops distributed
 555    before/after the loop NEST.  */
 556
 557 static void
 558 lst_perfect_nestify (lst_p loop1, lst_p loop2, lst_p *before,
 559                      lst_p *nest, lst_p *after)
 560 {
 561   poly_bb_p first, last;
 562
 563   gcc_assert (loop1 && loop2
 564               && loop1 != loop2
 565               && LST_LOOP_P (loop1) && LST_LOOP_P (loop2));
 566
 567   first = LST_PBB (lst_find_first_pbb (loop2));
 568   last = LST_PBB (lst_find_last_pbb (loop2));
 569
 570   *before = copy_lst (loop1);
 571   *nest = copy_lst (loop1);
 572   *after = copy_lst (loop1);
 573
 574   lst_remove_all_before_including_pbb (*before, first, false);
 575   lst_remove_all_before_including_pbb (*after, last, true);
 576
 577   lst_remove_all_before_excluding_pbb (*nest, first, true);
 578   lst_remove_all_before_excluding_pbb (*nest, last, false);
 579
 580   if (lst_empty_p (*before))
 581     {
 582       free_lst (*before);
 583       *before = NULL;
 584     }
 585   if (lst_empty_p (*after))
 586     {
 587       free_lst (*after);
 588       *after = NULL;
 589     }
 590   if (lst_empty_p (*nest))
 591     {
 592       free_lst (*nest);
 593       *nest = NULL;
 594     }
 595 }
 596
 597 /* Try to interchange LOOP1 with LOOP2 for all the statements of the
 598    body of LOOP2.  LOOP1 contains LOOP2.  Return true if it did the
 599    interchange.  */
 600
 601 static bool
 602 lst_try_interchange_loops (scop_p scop, lst_p loop1, lst_p loop2)
 603 {
 604   int depth1 = lst_depth (loop1);
 605   int depth2 = lst_depth (loop2);
 606   lst_p transformed;
 607
 608   lst_p before = NULL, nest = NULL, after = NULL;
 609
 610   if (!lst_interchange_profitable_p (loop1, loop2))
 611     return false;
 612
 613   if (!lst_perfectly_nested_p (loop1, loop2))
 614     lst_perfect_nestify (loop1, loop2, &before, &nest, &after);
 615
 616   lst_apply_interchange (loop2, depth1, depth2);
 617
 618   /* Sync the transformed LST information and the PBB scatterings
 619      before using the scatterings in the data dependence analysis.  */
 620   if (before || nest || after)
 621     {
 622       transformed = lst_substitute_3 (SCOP_TRANSFORMED_SCHEDULE (scop), loop1,
 623                                       before, nest, after);
 624       lst_update_scattering (transformed);
 625       free_lst (transformed);
 626     }
 627
 628   if (graphite_legal_transform (scop))
 629     {
 630       if (dump_file && (dump_flags & TDF_DETAILS))
 631         fprintf (dump_file,
 632                  "Loops at depths %d and %d will be interchanged.\n",
 633                  depth1, depth2);
 634
 635       /* Transform the SCOP_TRANSFORMED_SCHEDULE of the SCOP.  */
 636       lst_insert_in_sequence (before, loop1, true);
 637       lst_insert_in_sequence (after, loop1, false);
 638
 639       if (nest)
 640         {
 641           lst_replace (loop1, nest);
 642           free_lst (loop1);
 643         }
 644
 645       return true;
 646     }
 647
 648   /* Undo the transform.  */
 649   free_lst (before);
 650   free_lst (nest);
 651   free_lst (after);
 652   lst_apply_interchange (loop2, depth2, depth1);
 653   return false;
 654 }
 655
 656 /* Selects the inner loop in LST_SEQ (INNER_FATHER) to be interchanged
 657    with the loop OUTER in LST_SEQ (OUTER_FATHER).  */
 658
 659 static bool
 660 lst_interchange_select_inner (scop_p scop, lst_p outer_father, int outer,
 661                               lst_p inner_father)
 662 {
 663   int inner;
 664   lst_p loop1, loop2;
 665
 666   gcc_assert (outer_father
 667               && LST_LOOP_P (outer_father)
 668               && LST_LOOP_P (VEC_index (lst_p, LST_SEQ (outer_father), outer))
 669               && inner_father
 670               && LST_LOOP_P (inner_father));
 671
 672   loop1 = VEC_index (lst_p, LST_SEQ (outer_father), outer);
 673
 674   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (inner_father), inner, loop2)
 675     if (LST_LOOP_P (loop2)
 676         && (lst_try_interchange_loops (scop, loop1, loop2)
 677             || lst_interchange_select_inner (scop, outer_father, outer, loop2)))
 678       return true;
 679
 680   return false;
 681 }
 682
 683 /* Interchanges all the loops of LOOP and the loops of its body that
 684    are considered profitable to interchange.  Return true if it did
 685    interchanged some loops.  OUTER is the index in LST_SEQ (LOOP) that
 686    points to the next outer loop to be considered for interchange.  */
 687
 688 static bool
 689 lst_interchange_select_outer (scop_p scop, lst_p loop, int outer)
 690 {
 691   lst_p l;
 692   bool res = false;
 693   int i = 0;
 694   lst_p father;
 695
 696   if (!loop || !LST_LOOP_P (loop))
 697     return false;
 698
 699   father = LST_LOOP_FATHER (loop);
 700   if (father)
 701     {
 702       while (lst_interchange_select_inner (scop, father, outer, loop))
 703         {
 704           res = true;
 705           loop = VEC_index (lst_p, LST_SEQ (father), outer);
 706         }
 707     }
 708
 709   if (LST_LOOP_P (loop))
 710     FOR_EACH_VEC_ELT (lst_p, LST_SEQ (loop), i, l)
 711       if (LST_LOOP_P (l))
 712         res |= lst_interchange_select_outer (scop, l, i);
 713
 714   return res;
 715 }
 716
 717 /* Interchanges all the loop depths that are considered profitable for SCOP.  */
 718
 719 bool
 720 scop_do_interchange (scop_p scop)
 721 {
 722   bool res = lst_interchange_select_outer
 723     (scop, SCOP_TRANSFORMED_SCHEDULE (scop), 0);
 724
 725   lst_update_scattering (SCOP_TRANSFORMED_SCHEDULE (scop));
 726
 727   return res;
 728 }
 729
 730
 731 #endif
 732