gcc/graphite-blocking.c

   1 /* Heuristics and transform for loop blocking and strip mining 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    Pranav Garg  <pranav.garg2107@gmail.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 "tree-flow.h"
  27 #include "tree-dump.h"
  28 #include "cfgloop.h"
  29 #include "tree-chrec.h"
  30 #include "tree-data-ref.h"
  31 #include "sese.h"
  32
  33 #ifdef HAVE_cloog
  34 #include "ppl_c.h"
  35 #include "graphite-ppl.h"
  36 #include "graphite-poly.h"
  37
  38
  39 /* Strip mines with a factor STRIDE the scattering (time) dimension
  40    around PBB at depth TIME_DEPTH.
  41
  42    The following example comes from the wiki page:
  43    http://gcc.gnu.org/wiki/Graphite/Strip_mine
  44
  45    The strip mine of a loop with a tile of 64 can be obtained with a
  46    scattering function as follows:
  47
  48    $ cat ./albert_strip_mine.cloog
  49    # language: C
  50    c
  51
  52    # parameter {n | n >= 0}
  53    1 3
  54    #  n  1
  55    1  1  0
  56    1
  57    n
  58
  59    1 # Number of statements:
  60
  61    1
  62    # {i | 0 <= i <= n}
  63    2 4
  64    #  i  n   1
  65    1  1  0   0
  66    1 -1  1   0
  67
  68    0  0  0
  69    1
  70    i
  71
  72    1 # Scattering functions
  73
  74    3 6
  75    #  NEW  OLD    i    n    1
  76    1  -64    0    1    0    0
  77    1   64    0   -1    0   63
  78    0    0    1   -1    0    0
  79
  80    1
  81    NEW  OLD
  82
  83    #the output of CLooG is like this:
  84    #$ cloog ./albert_strip_mine.cloog
  85    # for (NEW=0;NEW<=floord(n,64);NEW++) {
  86    #   for (OLD=max(64*NEW,0);OLD<=min(64*NEW+63,n);OLD++) {
  87    #     S1(i = OLD) ;
  88    #   }
  89    # }
  90 */
  91
  92 static void
  93 pbb_strip_mine_time_depth (poly_bb_p pbb, int time_depth, int stride)
  94 {
  95   ppl_dimension_type iter, dim, strip;
  96   ppl_Polyhedron_t res = PBB_TRANSFORMED_SCATTERING (pbb);
  97   /* STRIP is the dimension that iterates with stride STRIDE.  */
  98   /* ITER is the dimension that enumerates single iterations inside
  99      one strip that has at most STRIDE iterations.  */
 100   strip = time_depth;
 101   iter = strip + 2;
 102
 103   psct_add_scattering_dimension (pbb, strip);
 104   psct_add_scattering_dimension (pbb, strip + 1);
 105
 106   ppl_Polyhedron_space_dimension (res, &dim);
 107
 108   /* Lower bound of the striped loop.  */
 109   {
 110     ppl_Constraint_t new_cstr;
 111     ppl_Linear_Expression_t expr;
 112
 113     ppl_new_Linear_Expression_with_dimension (&expr, dim);
 114     ppl_set_coef (expr, strip, -1 * stride);
 115     ppl_set_coef (expr, iter, 1);
 116
 117     ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
 118     ppl_delete_Linear_Expression (expr);
 119     ppl_Polyhedron_add_constraint (res, new_cstr);
 120     ppl_delete_Constraint (new_cstr);
 121   }
 122
 123   /* Upper bound of the striped loop.  */
 124   {
 125     ppl_Constraint_t new_cstr;
 126     ppl_Linear_Expression_t expr;
 127
 128     ppl_new_Linear_Expression_with_dimension (&expr, dim);
 129     ppl_set_coef (expr, strip, stride);
 130     ppl_set_coef (expr, iter, -1);
 131     ppl_set_inhomogeneous (expr, stride - 1);
 132
 133     ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
 134     ppl_delete_Linear_Expression (expr);
 135     ppl_Polyhedron_add_constraint (res, new_cstr);
 136     ppl_delete_Constraint (new_cstr);
 137   }
 138
 139   /* Static scheduling for ITER level.
 140      This is mandatory to keep the 2d + 1 canonical scheduling format.  */
 141   {
 142     ppl_Constraint_t new_cstr;
 143     ppl_Linear_Expression_t expr;
 144
 145     ppl_new_Linear_Expression_with_dimension (&expr, dim);
 146     ppl_set_coef (expr, strip + 1, 1);
 147     ppl_set_inhomogeneous (expr, 0);
 148
 149     ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
 150     ppl_delete_Linear_Expression (expr);
 151     ppl_Polyhedron_add_constraint (res, new_cstr);
 152     ppl_delete_Constraint (new_cstr);
 153   }
 154 }
 155
 156 /* Returns true when strip mining with STRIDE of the loop LST is
 157    profitable.  */
 158
 159 static bool
 160 lst_strip_mine_profitable_p (lst_p lst, int stride)
 161 {
 162   mpz_t niter, strip_stride;
 163   bool res;
 164
 165   gcc_assert (LST_LOOP_P (lst));
 166   mpz_init (strip_stride);
 167   mpz_init (niter);
 168
 169   mpz_set_si (strip_stride, stride);
 170   lst_niter_for_loop (lst, niter);
 171   res = (mpz_cmp (niter, strip_stride) > 0);
 172
 173   mpz_clear (strip_stride);
 174   mpz_clear (niter);
 175   return res;
 176 }
 177
 178 /* Strip-mines all the loops of LST with STRIDE.  Return the number of
 179    loops strip-mined.  */
 180
 181 static int
 182 lst_do_strip_mine_loop (lst_p lst, int depth, int stride)
 183 {
 184   int i;
 185   lst_p l;
 186   poly_bb_p pbb;
 187
 188   if (!lst)
 189     return 0;
 190
 191   if (LST_LOOP_P (lst))
 192     {
 193       int res = 0;
 194
 195       FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
 196         res += lst_do_strip_mine_loop (l, depth, stride);
 197
 198       return res;
 199     }
 200
 201   pbb = LST_PBB (lst);
 202   pbb_strip_mine_time_depth (pbb, psct_dynamic_dim (pbb, depth), stride);
 203   return 1;
 204 }
 205
 206 /* Strip-mines all the loops of LST with STRIDE.  When STRIDE is zero,
 207    read the stride from the PARAM_LOOP_BLOCK_TILE_SIZE.  Return the
 208    number of strip-mined loops.
 209
 210    Strip mining transforms a loop
 211
 212    | for (i = 0; i < N; i++)
 213    |   S (i);
 214
 215    into the following loop nest:
 216
 217    | for (k = 0; k < N; k += STRIDE)
 218    |   for (j = 0; j < STRIDE; j++)
 219    |     S (i = k + j);
 220 */
 221
 222 static int
 223 lst_do_strip_mine (lst_p lst, int stride)
 224 {
 225   int i;
 226   lst_p l;
 227   int res = 0;
 228   int depth;
 229
 230   if (!stride)
 231     stride = PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE);
 232
 233   if (!lst
 234       || !LST_LOOP_P (lst))
 235     return false;
 236
 237   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
 238     res += lst_do_strip_mine (l, stride);
 239
 240   depth = lst_depth (lst);
 241   if (depth >= 0
 242       && lst_strip_mine_profitable_p (lst, stride))
 243     {
 244       res += lst_do_strip_mine_loop (lst, lst_depth (lst), stride);
 245       lst_add_loop_under_loop (lst);
 246     }
 247
 248   return res;
 249 }
 250
 251 /* Strip mines all the loops in SCOP.  Returns the number of
 252    strip-mined loops.  */
 253
 254 int
 255 scop_do_strip_mine (scop_p scop, int stride)
 256 {
 257   return lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop), stride);
 258 }
 259
 260 /* Loop blocks all the loops in SCOP.  Returns true when we manage to
 261    block some loops.  */
 262
 263 bool
 264 scop_do_block (scop_p scop)
 265 {
 266   store_scattering (scop);
 267
 268   /* If we don't strip mine at least two loops, or not interchange
 269      loops, the strip mine alone will not be profitable, and the
 270      transform is not a loop blocking: so revert the transform.  */
 271   if (lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop), 0) < 2
 272       || scop_do_interchange (scop) == 0)
 273     {
 274       restore_scattering (scop);
 275       return false;
 276     }
 277
 278   if (dump_file && (dump_flags & TDF_DETAILS))
 279     fprintf (dump_file, "SCoP will be loop blocked.\n");
 280
 281   return true;
 282 }
 283
 284 #endif