gcc/graphite-interchange.c

   1 /* Interchange heuristics and transform for loop interchange on
   2    polyhedral representation.
   3
   4    Copyright (C) 2009 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 "toplev.h"
  35 #include "tree-dump.h"
  36 #include "timevar.h"
  37 #include "cfgloop.h"
  38 #include "tree-chrec.h"
  39 #include "tree-data-ref.h"
  40 #include "tree-scalar-evolution.h"
  41 #include "tree-pass.h"
  42 #include "domwalk.h"
  43 #include "value-prof.h"
  44 #include "pointer-set.h"
  45 #include "gimple.h"
  46 #include "params.h"
  47
  48 #ifdef HAVE_cloog
  49 #include "cloog/cloog.h"
  50 #include "ppl_c.h"
  51 #include "sese.h"
  52 #include "graphite-ppl.h"
  53 #include "graphite.h"
  54 #include "graphite-poly.h"
  55
  56 /* Builds a linear expression, of dimension DIM, representing PDR's
  57    memory access:
  58
  59    L = r_{n}*r_{n-1}*...*r_{1}*s_{0} + ... + r_{n}*s_{n-1} + s_{n}.
  60
  61    For an array A[10][20] with two subscript locations s0 and s1, the
  62    linear memory access is 20 * s0 + s1: a stride of 1 in subscript s0
  63    corresponds to a memory stride of 20.  */
  64
  65 static ppl_Linear_Expression_t
  66 build_linearized_memory_access (poly_dr_p pdr)
  67 {
  68   ppl_Linear_Expression_t res;
  69   ppl_Linear_Expression_t le;
  70   ppl_dimension_type i;
  71   ppl_dimension_type first = pdr_subscript_dim (pdr, 0);
  72   ppl_dimension_type last = pdr_subscript_dim (pdr, PDR_NB_SUBSCRIPTS (pdr));
  73   Value size, sub_size;
  74   graphite_dim_t dim = pdr_dim (pdr);
  75
  76   ppl_new_Linear_Expression_with_dimension (&res, dim);
  77
  78   value_init (size);
  79   value_set_si (size, 1);
  80   value_init (sub_size);
  81   value_set_si (sub_size, 1);
  82
  83   for (i = last - 1; i >= first; i--)
  84     {
  85       ppl_set_coef_gmp (res, i, size);
  86
  87       ppl_new_Linear_Expression_with_dimension (&le, dim);
  88       ppl_set_coef (le, i, 1);
  89       ppl_max_for_le_pointset (PDR_ACCESSES (pdr), le, sub_size);
  90       value_multiply (size, size, sub_size);
  91       ppl_delete_Linear_Expression (le);
  92     }
  93
  94   value_clear (sub_size);
  95   value_clear (size);
  96   return res;
  97 }
  98
  99 /* Set STRIDE to the stride of PDR in memory by advancing by one in
 100    loop DEPTH.  */
 101
 102 static void
 103 memory_stride_in_loop (Value stride, graphite_dim_t depth, poly_dr_p pdr)
 104 {
 105   ppl_Linear_Expression_t le, lma;
 106   ppl_Constraint_t new_cstr;
 107   ppl_Pointset_Powerset_C_Polyhedron_t p1, p2;
 108   graphite_dim_t nb_subscripts = PDR_NB_SUBSCRIPTS (pdr);
 109   ppl_dimension_type i, *map;
 110   ppl_dimension_type dim = pdr_dim (pdr);
 111   ppl_dimension_type dim_i = pdr_iterator_dim (pdr, depth);
 112   ppl_dimension_type dim_k = dim;
 113   ppl_dimension_type dim_L1 = dim + nb_subscripts + 1;
 114   ppl_dimension_type dim_L2 = dim + nb_subscripts + 2;
 115   ppl_dimension_type new_dim = dim + nb_subscripts + 3;
 116
 117   /* Add new dimensions to the polyhedron corresponding to
 118      k, s0', s1',..., L1, and L2.  These new variables are at
 119      dimensions dim, dim + 1,... of the polyhedron P1 respectively.  */
 120   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 121     (&p1, PDR_ACCESSES (pdr));
 122   ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed
 123     (p1, nb_subscripts + 3);
 124
 125   lma = build_linearized_memory_access (pdr);
 126   ppl_set_coef (lma, dim_L1, -1);
 127   ppl_new_Constraint (&new_cstr, lma, PPL_CONSTRAINT_TYPE_EQUAL);
 128   ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p1, new_cstr);
 129
 130   /* Build P2.  */
 131   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 132     (&p2, p1);
 133   map = ppl_new_id_map (new_dim);
 134   ppl_interchange (map, dim_L1, dim_L2);
 135   ppl_interchange (map, dim_i, dim_k);
 136   for (i = 0; i < PDR_NB_SUBSCRIPTS (pdr); i++)
 137     ppl_interchange (map, pdr_subscript_dim (pdr, i), dim + i + 1);
 138   ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (p2, map, new_dim);
 139   free (map);
 140
 141   /* Add constraint k = i + 1.  */
 142   ppl_new_Linear_Expression_with_dimension (&le, new_dim);
 143   ppl_set_coef (le, dim_i, 1);
 144   ppl_set_coef (le, dim_k, -1);
 145   ppl_set_inhomogeneous (le, 1);
 146   ppl_new_Constraint (&new_cstr, le, PPL_CONSTRAINT_TYPE_EQUAL);
 147   ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p2, new_cstr);
 148   ppl_delete_Linear_Expression (le);
 149   ppl_delete_Constraint (new_cstr);
 150
 151   /* P1 = P1 inter P2.  */
 152   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (p1, p2);
 153   ppl_delete_Pointset_Powerset_C_Polyhedron (p2);
 154
 155   /* Maximise the expression L2 - L1.  */
 156   ppl_new_Linear_Expression_with_dimension (&le, new_dim);
 157   ppl_set_coef (le, dim_L2, 1);
 158   ppl_set_coef (le, dim_L1, -1);
 159   ppl_max_for_le_pointset (p1, le, stride);
 160   ppl_delete_Linear_Expression (le);
 161 }
 162
 163
 164 /* Returns true when it is profitable to interchange loop at DEPTH1
 165    and loop at DEPTH2 with DEPTH1 < DEPTH2 for PBB.
 166
 167    Example:
 168
 169    | int a[100][100];
 170    |
 171    | int
 172    | foo (int N)
 173    | {
 174    |   int j;
 175    |   int i;
 176    |
 177    |   for (i = 0; i < N; i++)
 178    |     for (j = 0; j < N; j++)
 179    |       a[j][2 * i] += 1;
 180    |
 181    |   return a[N][12];
 182    | }
 183
 184    The data access A[j][i] is described like this:
 185
 186    | i   j   N   a  s0  s1   1
 187    | 0   0   0   1   0   0  -5    = 0
 188    | 0  -1   0   0   1   0   0    = 0
 189    |-2   0   0   0   0   1   0    = 0
 190    | 0   0   0   0   1   0   0   >= 0
 191    | 0   0   0   0   0   1   0   >= 0
 192    | 0   0   0   0  -1   0 100   >= 0
 193    | 0   0   0   0   0  -1 100   >= 0
 194
 195    The linearized memory access L to A[100][100] is:
 196
 197    | i   j   N   a  s0  s1   1
 198    | 0   0   0   0 100   1   0
 199
 200    Next, to measure the impact of iterating once in loop "i", we build
 201    a maximization problem: first, we add to DR accesses the dimensions
 202    k, s2, s3, L1 = 100 * s0 + s1, L2, and D1: polyhedron P1.
 203
 204    | i   j   N   a  s0  s1   k  s2  s3  L1  L2  D1   1
 205    | 0   0   0   1   0   0   0   0   0   0   0   0  -5    = 0  alias = 5
 206    | 0  -1   0   0   1   0   0   0   0   0   0   0   0    = 0  s0 = j
 207    |-2   0   0   0   0   1   0   0   0   0   0   0   0    = 0  s1 = 2 * i
 208    | 0   0   0   0   1   0   0   0   0   0   0   0   0   >= 0
 209    | 0   0   0   0   0   1   0   0   0   0   0   0   0   >= 0
 210    | 0   0   0   0  -1   0   0   0   0   0   0   0 100   >= 0
 211    | 0   0   0   0   0  -1   0   0   0   0   0   0 100   >= 0
 212    | 0   0   0   0 100   1   0   0   0  -1   0   0   0    = 0  L1 = 100 * s0 + s1
 213
 214    Then, we generate the polyhedron P2 by interchanging the dimensions
 215    (s0, s2), (s1, s3), (L1, L2), (i0, i)
 216
 217    | i   j   N   a  s0  s1   k  s2  s3  L1  L2  D1   1
 218    | 0   0   0   1   0   0   0   0   0   0   0   0  -5    = 0  alias = 5
 219    | 0  -1   0   0   0   0   0   1   0   0   0   0   0    = 0  s2 = j
 220    | 0   0   0   0   0   0  -2   0   1   0   0   0   0    = 0  s3 = 2 * k
 221    | 0   0   0   0   0   0   0   1   0   0   0   0   0   >= 0
 222    | 0   0   0   0   0   0   0   0   1   0   0   0   0   >= 0
 223    | 0   0   0   0   0   0   0  -1   0   0   0   0 100   >= 0
 224    | 0   0   0   0   0   0   0   0  -1   0   0   0 100   >= 0
 225    | 0   0   0   0   0   0   0 100   1   0  -1   0   0    = 0  L2 = 100 * s2 + s3
 226
 227    then we add to P2 the equality k = i + 1:
 228
 229    |-1   0   0   0   0   0   1   0   0   0   0   0  -1    = 0  k = i + 1
 230
 231    and finally we maximize the expression "D1 = max (P1 inter P2, L2 - L1)".
 232
 233    For determining the impact of one iteration on loop "j", we
 234    interchange (k, j), we add "k = j + 1", and we compute D2 the
 235    maximal value of the difference.
 236
 237    Finally, the profitability test is D1 < D2: if in the outer loop
 238    the strides are smaller than in the inner loop, then it is
 239    profitable to interchange the loops at DEPTH1 and DEPTH2.  */
 240
 241 static bool
 242 pbb_interchange_profitable_p (graphite_dim_t depth1, graphite_dim_t depth2,
 243                               poly_bb_p pbb)
 244 {
 245   int i;
 246   poly_dr_p pdr;
 247   Value d1, d2, s, n;
 248   bool res;
 249
 250   gcc_assert (depth1 < depth2);
 251
 252   value_init (d1);
 253   value_set_si (d1, 0);
 254   value_init (d2);
 255   value_set_si (d2, 0);
 256   value_init (s);
 257   value_init (n);
 258
 259   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
 260     {
 261       value_set_si (n, PDR_NB_REFS (pdr));
 262
 263       memory_stride_in_loop (s, depth1, pdr);
 264       value_multiply (s, s, n);
 265       value_addto (d1, d1, s);
 266
 267       memory_stride_in_loop (s, depth2, pdr);
 268       value_multiply (s, s, n);
 269       value_addto (d2, d2, s);
 270     }
 271
 272   res = value_lt (d1, d2);
 273
 274   value_clear (d1);
 275   value_clear (d2);
 276   value_clear (s);
 277   value_clear (n);
 278
 279   return res;
 280 }
 281
 282 /* Interchanges the loops at DEPTH1 and DEPTH2 of the original
 283    scattering and assigns the resulting polyhedron to the transformed
 284    scattering.  */
 285
 286 static void
 287 pbb_interchange_loop_depths (graphite_dim_t depth1, graphite_dim_t depth2, poly_bb_p pbb)
 288 {
 289   ppl_dimension_type i, dim;
 290   ppl_dimension_type *map;
 291   ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
 292   ppl_dimension_type dim1 = psct_iterator_dim (pbb, depth1);
 293   ppl_dimension_type dim2 = psct_iterator_dim (pbb, depth2);
 294
 295   ppl_Polyhedron_space_dimension (poly, &dim);
 296   map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
 297
 298   for (i = 0; i < dim; i++)
 299     map[i] = i;
 300
 301   map[dim1] = dim2;
 302   map[dim2] = dim1;
 303
 304   ppl_Polyhedron_map_space_dimensions (poly, map, dim);
 305   free (map);
 306 }
 307
 308 /* Apply the interchange of loops at depths DEPTH1 and DEPTH2 to all
 309    the statements below LST.  */
 310
 311 static void
 312 lst_apply_interchange (lst_p lst, int depth1, int depth2)
 313 {
 314   if (!lst)
 315     return;
 316
 317   if (LST_LOOP_P (lst))
 318     {
 319       int i;
 320       lst_p l;
 321
 322       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 323         lst_apply_interchange (l, depth1, depth2);
 324     }
 325   else
 326     pbb_interchange_loop_depths (depth1, depth2, LST_PBB (lst));
 327 }
 328
 329 /* Return true when the interchange of loops at depths DEPTH1 and
 330    DEPTH2 to all the statements below LST is profitable.  */
 331
 332 static bool
 333 lst_interchange_profitable_p (lst_p lst, int depth1, int depth2)
 334 {
 335   if (!lst)
 336     return false;
 337
 338   if (LST_LOOP_P (lst))
 339     {
 340       int i;
 341       lst_p l;
 342       bool res = false;
 343
 344       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 345         {
 346           bool profitable = lst_interchange_profitable_p (l, depth1, depth2);
 347
 348           if (profitable && !LST_LOOP_P (lst)
 349               && dump_file && (dump_flags & TDF_DETAILS))
 350             fprintf (dump_file,
 351                      "Interchanging loops at depths %d and %d is profitable for stmt_%d.\n",
 352                      depth1, depth2, pbb_index (LST_PBB (lst)));
 353
 354           res |= profitable;
 355         }
 356
 357       return res;
 358     }
 359   else
 360     return pbb_interchange_profitable_p (depth1, depth2, LST_PBB (lst));
 361 }
 362
 363
 364 /* Try to interchange LOOP1 with LOOP2 for all the statements of the
 365    body of LOOP2.  LOOP1 contains LOOP2.  Return true if it did the
 366    interchange.  */
 367
 368 static bool
 369 lst_try_interchange_loops (scop_p scop, lst_p loop1, lst_p loop2)
 370 {
 371   int depth1 = lst_depth (loop1);
 372   int depth2 = lst_depth (loop2);
 373
 374   if (!lst_interchange_profitable_p (loop2, depth1, depth2))
 375     return false;
 376
 377   lst_apply_interchange (loop2, depth1, depth2);
 378
 379   if (graphite_legal_transform (scop))
 380     {
 381       if (dump_file && (dump_flags & TDF_DETAILS))
 382         fprintf (dump_file,
 383                  "Loops at depths %d and %d will be interchanged.\n",
 384                  depth1, depth2);
 385
 386       return true;
 387     }
 388
 389   /* Undo the transform.  */
 390   lst_apply_interchange (loop2, depth2, depth1);
 391   return false;
 392 }
 393
 394 /* Try to interchange LOOP with all the loops contained in the body of
 395    LST.  Return true if it did interchanged some loops.  */
 396
 397 static bool
 398 lst_try_interchange (scop_p scop, lst_p loop, lst_p lst)
 399 {
 400   if (!lst)
 401     return false;
 402
 403   if (LST_LOOP_P (lst))
 404     {
 405       int i;
 406       lst_p l;
 407       bool res = lst_try_interchange_loops (scop, loop, lst);
 408
 409       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 410         res |= lst_try_interchange (scop, loop, l);
 411
 412       return res;
 413     }
 414
 415   return false;
 416 }
 417
 418 /* Interchanges all the loops of LST that are considered profitable to
 419    interchange.  Return true if it did interchanged some loops.  */
 420
 421 static bool
 422 lst_do_interchange (scop_p scop, lst_p lst)
 423 {
 424   if (!lst)
 425     return false;
 426
 427   if (LST_LOOP_P (lst))
 428     {
 429       int i;
 430       lst_p l;
 431       bool res = false;
 432
 433       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 434         res |= lst_try_interchange (scop, lst, l);
 435
 436       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
 437         res |= lst_do_interchange (scop, l);
 438
 439       return res;
 440     }
 441
 442   return false;
 443 }
 444
 445 /* Interchanges all the loop depths that are considered profitable for SCOP.  */
 446
 447 bool
 448 scop_do_interchange (scop_p scop)
 449 {
 450   bool transform_done = false;
 451
 452   store_scattering (scop);
 453
 454   transform_done = lst_do_interchange (scop, SCOP_TRANSFORMED_SCHEDULE (scop));
 455
 456   if (!transform_done)
 457     return false;
 458
 459   if (!graphite_legal_transform (scop))
 460     {
 461       restore_scattering (scop);
 462       return false;
 463     }
 464
 465   return transform_done;
 466 }
 467
 468
 469 #endif
 470