gcc/graphite-blocking.c

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