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 /* Return in RES the maximum of the linear expression LE on polyhedron PS.  */
  57
  58 static void
  59 ppl_max_for_le (ppl_Pointset_Powerset_C_Polyhedron_t ps,
  60                 ppl_Linear_Expression_t le, Value res)
  61 {
  62   ppl_Coefficient_t num, denom;
  63   Value dv, nv;
  64   int maximum;
  65
  66   value_init (nv);
  67   value_init (dv);
  68   ppl_new_Coefficient (&num);
  69   ppl_new_Coefficient (&denom);
  70   ppl_Pointset_Powerset_C_Polyhedron_maximize (ps, le, num, denom, &maximum);
  71
  72   if (maximum)
  73     {
  74       ppl_Coefficient_to_mpz_t (num, nv);
  75       ppl_Coefficient_to_mpz_t (denom, dv);
  76       value_division (res, nv, dv);
  77     }
  78
  79   value_clear (nv);
  80   value_clear (dv);
  81   ppl_delete_Coefficient (num);
  82   ppl_delete_Coefficient (denom);
  83 }
  84
  85 /* Builds a linear expression, of dimension DIM, representing PDR's
  86    memory access:
  87
  88    L = r_{n}*r_{n-1}*...*r_{1}*s_{0} + ... + r_{n}*s_{n-1} + s_{n}.
  89
  90    For an array A[10][20] with two subscript locations s0 and s1, the
  91    linear memory access is 20 * s0 + s1: a stride of 1 in subscript s0
  92    corresponds to a memory stride of 20.  */
  93
  94 static ppl_Linear_Expression_t
  95 build_linearized_memory_access (poly_dr_p pdr)
  96 {
  97   ppl_Linear_Expression_t res;
  98   ppl_Linear_Expression_t le;
  99   ppl_dimension_type i;
 100   ppl_dimension_type first = pdr_subscript_dim (pdr, 0);
 101   ppl_dimension_type last = pdr_subscript_dim (pdr, PDR_NB_SUBSCRIPTS (pdr));
 102   Value size, sub_size;
 103   graphite_dim_t dim = pdr_dim (pdr);
 104
 105   ppl_new_Linear_Expression_with_dimension (&res, dim);
 106
 107   value_init (size);
 108   value_set_si (size, 1);
 109   value_init (sub_size);
 110   value_set_si (sub_size, 1);
 111
 112   for (i = last - 1; i >= first; i--)
 113     {
 114       ppl_set_coef_gmp (res, i, size);
 115
 116       ppl_new_Linear_Expression_with_dimension (&le, dim);
 117       ppl_set_coef (le, i, 1);
 118       ppl_max_for_le (PDR_ACCESSES (pdr), le, sub_size);
 119       value_multiply (size, size, sub_size);
 120       ppl_delete_Linear_Expression (le);
 121     }
 122
 123   value_clear (sub_size);
 124   value_clear (size);
 125   return res;
 126 }
 127
 128 /* Set STRIDE to the stride of PDR in memory by advancing by one in
 129    loop DEPTH.  */
 130
 131 static void
 132 memory_stride_in_loop (Value stride, graphite_dim_t depth, poly_dr_p pdr)
 133 {
 134   ppl_Linear_Expression_t le, lma;
 135   ppl_Constraint_t new_cstr;
 136   ppl_Pointset_Powerset_C_Polyhedron_t p1, p2;
 137   graphite_dim_t nb_subscripts = PDR_NB_SUBSCRIPTS (pdr);
 138   ppl_dimension_type i, *map;
 139   ppl_dimension_type dim = pdr_dim (pdr);
 140   ppl_dimension_type dim_i = pdr_iterator_dim (pdr, depth);
 141   ppl_dimension_type dim_k = dim;
 142   ppl_dimension_type dim_L1 = dim + nb_subscripts + 1;
 143   ppl_dimension_type dim_L2 = dim + nb_subscripts + 2;
 144   ppl_dimension_type new_dim = dim + nb_subscripts + 3;
 145
 146   /* Add new dimensions to the polyhedron corresponding to
 147      k, s0', s1',..., L1, and L2.  These new variables are at
 148      dimensions dim, dim + 1,... of the polyhedron P1 respectively.  */
 149   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 150     (&p1, PDR_ACCESSES (pdr));
 151   ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed
 152     (p1, nb_subscripts + 3);
 153
 154   lma = build_linearized_memory_access (pdr);
 155   ppl_set_coef (lma, dim_L1, -1);
 156   ppl_new_Constraint (&new_cstr, lma, PPL_CONSTRAINT_TYPE_EQUAL);
 157   ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p1, new_cstr);
 158
 159   /* Build P2.  */
 160   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 161     (&p2, p1);
 162   map = ppl_new_id_map (new_dim);
 163   ppl_interchange (map, dim_L1, dim_L2);
 164   ppl_interchange (map, dim_i, dim_k);
 165   for (i = 0; i < PDR_NB_SUBSCRIPTS (pdr); i++)
 166     ppl_interchange (map, pdr_subscript_dim (pdr, i), dim + i + 1);
 167   ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (p2, map, new_dim);
 168   free (map);
 169
 170   /* Add constraint k = i + 1.  */
 171   ppl_new_Linear_Expression_with_dimension (&le, new_dim);
 172   ppl_set_coef (le, dim_i, 1);
 173   ppl_set_coef (le, dim_k, -1);
 174   ppl_set_inhomogeneous (le, 1);
 175   ppl_new_Constraint (&new_cstr, le, PPL_CONSTRAINT_TYPE_EQUAL);
 176   ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p2, new_cstr);
 177   ppl_delete_Linear_Expression (le);
 178   ppl_delete_Constraint (new_cstr);
 179
 180   /* P1 = P1 inter P2.  */
 181   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (p1, p2);
 182   ppl_delete_Pointset_Powerset_C_Polyhedron (p2);
 183
 184   /* Maximise the expression L2 - L1.  */
 185   ppl_new_Linear_Expression_with_dimension (&le, new_dim);
 186   ppl_set_coef (le, dim_L2, 1);
 187   ppl_set_coef (le, dim_L1, -1);
 188   ppl_max_for_le (p1, le, stride);
 189   ppl_delete_Linear_Expression (le);
 190 }
 191
 192
 193 /* Returns true when it is profitable to interchange loop at DEPTH1
 194    and loop at DEPTH2 with DEPTH1 < DEPTH2 for PBB.
 195
 196    Example:
 197
 198    | int a[100][100];
 199    |
 200    | int
 201    | foo (int N)
 202    | {
 203    |   int j;
 204    |   int i;
 205    |
 206    |   for (i = 0; i < N; i++)
 207    |     for (j = 0; j < N; j++)
 208    |       a[j][2 * i] += 1;
 209    |
 210    |   return a[N][12];
 211    | }
 212
 213    The data access A[j][i] is described like this:
 214
 215    | i   j   N   a  s0  s1   1
 216    | 0   0   0   1   0   0  -5    = 0
 217    | 0  -1   0   0   1   0   0    = 0
 218    |-2   0   0   0   0   1   0    = 0
 219    | 0   0   0   0   1   0   0   >= 0
 220    | 0   0   0   0   0   1   0   >= 0
 221    | 0   0   0   0  -1   0 100   >= 0
 222    | 0   0   0   0   0  -1 100   >= 0
 223
 224    The linearized memory access L to A[100][100] is:
 225
 226    | i   j   N   a  s0  s1   1
 227    | 0   0   0   0 100   1   0
 228
 229    Next, to measure the impact of iterating once in loop "i", we build
 230    a maximization problem: first, we add to DR accesses the dimensions
 231    k, s2, s3, L1 = 100 * s0 + s1, L2, and D1: polyhedron P1.
 232
 233    | i   j   N   a  s0  s1   k  s2  s3  L1  L2  D1   1
 234    | 0   0   0   1   0   0   0   0   0   0   0   0  -5    = 0  alias = 5
 235    | 0  -1   0   0   1   0   0   0   0   0   0   0   0    = 0  s0 = j
 236    |-2   0   0   0   0   1   0   0   0   0   0   0   0    = 0  s1 = 2 * i
 237    | 0   0   0   0   1   0   0   0   0   0   0   0   0   >= 0
 238    | 0   0   0   0   0   1   0   0   0   0   0   0   0   >= 0
 239    | 0   0   0   0  -1   0   0   0   0   0   0   0 100   >= 0
 240    | 0   0   0   0   0  -1   0   0   0   0   0   0 100   >= 0
 241    | 0   0   0   0 100   1   0   0   0  -1   0   0   0    = 0  L1 = 100 * s0 + s1
 242
 243    Then, we generate the polyhedron P2 by interchanging the dimensions
 244    (s0, s2), (s1, s3), (L1, L2), (i0, i)
 245
 246    | i   j   N   a  s0  s1   k  s2  s3  L1  L2  D1   1
 247    | 0   0   0   1   0   0   0   0   0   0   0   0  -5    = 0  alias = 5
 248    | 0  -1   0   0   0   0   0   1   0   0   0   0   0    = 0  s2 = j
 249    | 0   0   0   0   0   0  -2   0   1   0   0   0   0    = 0  s3 = 2 * k
 250    | 0   0   0   0   0   0   0   1   0   0   0   0   0   >= 0
 251    | 0   0   0   0   0   0   0   0   1   0   0   0   0   >= 0
 252    | 0   0   0   0   0   0   0  -1   0   0   0   0 100   >= 0
 253    | 0   0   0   0   0   0   0   0  -1   0   0   0 100   >= 0
 254    | 0   0   0   0   0   0   0 100   1   0  -1   0   0    = 0  L2 = 100 * s2 + s3
 255
 256    then we add to P2 the equality k = i + 1:
 257
 258    |-1   0   0   0   0   0   1   0   0   0   0   0  -1    = 0  k = i + 1
 259
 260    and finally we maximize the expression "D1 = max (P1 inter P2, L2 - L1)".
 261
 262    For determining the impact of one iteration on loop "j", we
 263    interchange (k, j), we add "k = j + 1", and we compute D2 the
 264    maximal value of the difference.
 265
 266    Finally, the profitability test is D1 < D2: if in the outer loop
 267    the strides are smaller than in the inner loop, then it is
 268    profitable to interchange the loops at DEPTH1 and DEPTH2.  */
 269
 270 static bool
 271 pbb_interchange_profitable_p (graphite_dim_t depth1, graphite_dim_t depth2,
 272                               poly_bb_p pbb)
 273 {
 274   int i;
 275   poly_dr_p pdr;
 276   Value d1, d2, s;
 277   bool res;
 278
 279   gcc_assert (depth1 < depth2);
 280
 281   value_init (d1);
 282   value_set_si (d1, 0);
 283   value_init (d2);
 284   value_set_si (d2, 0);
 285   value_init (s);
 286
 287   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
 288     {
 289       memory_stride_in_loop (s, depth1, pdr);
 290       value_addto (d1, d1, s);
 291
 292       memory_stride_in_loop (s, depth2, pdr);
 293       value_addto (d2, d2, s);
 294     }
 295
 296   res = value_lt (d1, d2);
 297
 298   value_clear (d1);
 299   value_clear (d2);
 300   value_clear (s);
 301
 302   return res;
 303 }
 304
 305 /* Interchanges the loops at DEPTH1 and DEPTH2 of the original
 306    scattering and assigns the resulting polyhedron to the transformed
 307    scattering.  */
 308
 309 static void
 310 pbb_interchange_loop_depths (graphite_dim_t depth1, graphite_dim_t depth2, poly_bb_p pbb)
 311 {
 312   ppl_dimension_type i, dim;
 313   ppl_dimension_type *map;
 314   ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
 315   ppl_dimension_type dim1 = psct_iterator_dim (pbb, depth1);
 316   ppl_dimension_type dim2 = psct_iterator_dim (pbb, depth2);
 317
 318   ppl_Polyhedron_space_dimension (poly, &dim);
 319   map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
 320
 321   for (i = 0; i < dim; i++)
 322     map[i] = i;
 323
 324   map[dim1] = dim2;
 325   map[dim2] = dim1;
 326
 327   ppl_Polyhedron_map_space_dimensions (poly, map, dim);
 328   free (map);
 329 }
 330
 331 /* Interchanges all the loop depths that are considered profitable for PBB.  */
 332
 333 static bool
 334 pbb_do_interchange (poly_bb_p pbb, scop_p scop)
 335 {
 336   graphite_dim_t i, j;
 337   bool transform_done = false;
 338
 339   for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
 340     for (j = i + 1; j < pbb_dim_iter_domain (pbb); j++)
 341       if (pbb_interchange_profitable_p (i, j, pbb))
 342         {
 343           pbb_interchange_loop_depths (i, j, pbb);
 344
 345           if (graphite_legal_transform (scop))
 346             {
 347               transform_done = true;
 348
 349               if (dump_file && (dump_flags & TDF_DETAILS))
 350                 fprintf (dump_file,
 351                          "PBB %d: loops at depths %d and %d will be interchanged.\n",
 352                          GBB_BB (PBB_BLACK_BOX (pbb))->index, (int) i, (int) j);
 353             }
 354           else
 355             /* Undo the transform.  */
 356             pbb_interchange_loop_depths (j, i, pbb);
 357         }
 358
 359   return transform_done;
 360 }
 361
 362 /* Interchanges all the loop depths that are considered profitable for SCOP.  */
 363
 364 bool
 365 scop_do_interchange (scop_p scop)
 366 {
 367   int i;
 368   poly_bb_p pbb;
 369   bool transform_done = false;
 370
 371   store_scattering (scop);
 372
 373   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
 374     transform_done |= pbb_do_interchange (pbb, scop);
 375
 376   if (!transform_done)
 377     return false;
 378
 379   if (!graphite_legal_transform (scop))
 380     {
 381       restore_scattering (scop);
 382       return false;
 383     }
 384
 385   return transform_done;
 386 }
 387
 388 #endif
 389