gcc/graphite-blocking.c

   1 /* Heuristics and transform for loop blocking and strip mining on
   2    polyhedral representation.
   3
   4    Copyright (C) 2009 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 "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 "ppl_c.h"
  50 #include "sese.h"
  51 #include "graphite-ppl.h"
  52 #include "graphite.h"
  53 #include "graphite-poly.h"
  54
  55
  56 /* Strip mines with a factor STRIDE the scattering (time) dimension
  57    around PBB at depth TIME_DEPTH.
  58
  59    The following example comes from the wiki page:
  60    http://gcc.gnu.org/wiki/Graphite/Strip_mine
  61
  62    The strip mine of a loop with a tile of 64 can be obtained with a
  63    scattering function as follows:
  64
  65    $ cat ./albert_strip_mine.cloog
  66    # language: C
  67    c
  68
  69    # parameter {n | n >= 0}
  70    1 3
  71    #  n  1
  72    1  1  0
  73    1
  74    n
  75
  76    1 # Number of statements:
  77
  78    1
  79    # {i | 0 <= i <= n}
  80    2 4
  81    #  i  n   1
  82    1  1  0   0
  83    1 -1  1   0
  84
  85    0  0  0
  86    1
  87    i
  88
  89    1 # Scattering functions
  90
  91    3 6
  92    #  NEW  OLD    i    n    1
  93    1  -64    0    1    0    0
  94    1   64    0   -1    0   63
  95    0    0    1   -1    0    0
  96
  97    1
  98    NEW  OLD
  99
 100    #the output of CLooG is like this:
 101    #$ cloog ./albert_strip_mine.cloog
 102    # for (NEW=0;NEW<=floord(n,64);NEW++) {
 103    #   for (OLD=max(64*NEW,0);OLD<=min(64*NEW+63,n);OLD++) {
 104    #     S1(i = OLD) ;
 105    #   }
 106    # }
 107 */
 108
 109 static bool
 110 pbb_strip_mine_time_depth (poly_bb_p pbb, int time_depth, int stride)
 111 {
 112   ppl_dimension_type iter, dim, strip;
 113   ppl_Polyhedron_t res = PBB_TRANSFORMED_SCATTERING (pbb);
 114   /* STRIP is the dimension that iterates with stride STRIDE.  */
 115   /* ITER is the dimension that enumerates single iterations inside
 116      one strip that has at most STRIDE iterations.  */
 117   strip = time_depth;
 118   iter = strip + 2;
 119
 120   psct_add_scattering_dimension (pbb, strip);
 121   psct_add_scattering_dimension (pbb, strip + 1);
 122
 123   ppl_Polyhedron_space_dimension (res, &dim);
 124
 125   /* Lower bound of the striped loop.  */
 126   {
 127     ppl_Constraint_t new_cstr;
 128     ppl_Linear_Expression_t expr;
 129
 130     ppl_new_Linear_Expression_with_dimension (&expr, dim);
 131     ppl_set_coef (expr, strip, -1 * stride);
 132     ppl_set_coef (expr, iter, 1);
 133
 134     ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
 135     ppl_delete_Linear_Expression (expr);
 136     ppl_Polyhedron_add_constraint (res, new_cstr);
 137     ppl_delete_Constraint (new_cstr);
 138   }
 139
 140   /* Upper bound of the striped loop.  */
 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, stride);
 147     ppl_set_coef (expr, iter, -1);
 148     ppl_set_inhomogeneous (expr, stride - 1);
 149
 150     ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
 151     ppl_delete_Linear_Expression (expr);
 152     ppl_Polyhedron_add_constraint (res, new_cstr);
 153     ppl_delete_Constraint (new_cstr);
 154   }
 155
 156   /* Static scheduling for ITER level.
 157      This is mandatory to keep the 2d + 1 canonical scheduling format.  */
 158   {
 159     ppl_Constraint_t new_cstr;
 160     ppl_Linear_Expression_t expr;
 161
 162     ppl_new_Linear_Expression_with_dimension (&expr, dim);
 163     ppl_set_coef (expr, strip + 1, 1);
 164     ppl_set_inhomogeneous (expr, 0);
 165
 166     ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
 167     ppl_delete_Linear_Expression (expr);
 168     ppl_Polyhedron_add_constraint (res, new_cstr);
 169     ppl_delete_Constraint (new_cstr);
 170   }
 171
 172   return true;
 173 }
 174
 175 /* Returns true when strip mining with STRIDE of the loop around PBB
 176    at DEPTH is profitable.  */
 177
 178 static bool
 179 pbb_strip_mine_profitable_p (poly_bb_p pbb,
 180                              graphite_dim_t depth,
 181                              int stride)
 182 {
 183   mpz_t niter, strip_stride;
 184   bool res;
 185
 186   mpz_init (strip_stride);
 187   mpz_init (niter);
 188   mpz_set_si (strip_stride, stride);
 189   pbb_number_of_iterations_at_time (pbb, psct_dynamic_dim (pbb, depth), niter);
 190   res = (mpz_cmp (niter, strip_stride) > 0);
 191   mpz_clear (strip_stride);
 192   mpz_clear (niter);
 193
 194   return res;
 195 }
 196
 197 /* Strip-mines all the loops of LST that are considered profitable to
 198    strip-mine.  Return true if it did strip-mined some loops.  */
 199
 200 static bool
 201 lst_do_strip_mine_loop (lst_p lst, int depth)
 202 {
 203   int i;
 204   lst_p l;
 205   int stride = PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE);
 206   poly_bb_p pbb;
 207
 208   if (!lst)
 209     return false;
 210
 211   if (LST_LOOP_P (lst))
 212     {
 213       bool res = false;
 214
 215       FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
 216         res |= lst_do_strip_mine_loop (l, depth);
 217
 218       return res;
 219     }
 220
 221   pbb = LST_PBB (lst);
 222   return pbb_strip_mine_time_depth (pbb, psct_dynamic_dim (pbb, depth),
 223                                     stride);
 224 }
 225
 226 /* Strip-mines all the loops of LST that are considered profitable to
 227    strip-mine.  Return true if it did strip-mined some loops.  */
 228
 229 static bool
 230 lst_do_strip_mine (lst_p lst)
 231 {
 232   int i;
 233   lst_p l;
 234   bool res = false;
 235   int stride = PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE);
 236   int depth;
 237
 238   if (!lst
 239       || !LST_LOOP_P (lst))
 240     return false;
 241
 242   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
 243     res |= lst_do_strip_mine (l);
 244
 245   depth = lst_depth (lst);
 246   if (depth >= 0
 247       && pbb_strip_mine_profitable_p (LST_PBB (lst_find_first_pbb (lst)),
 248                                       depth, stride))
 249     {
 250       res |= lst_do_strip_mine_loop (lst, lst_depth (lst));
 251       lst_add_loop_under_loop (lst);
 252     }
 253
 254   return res;
 255 }
 256
 257 /* Strip mines all the loops in SCOP.  Nothing profitable in all this:
 258    this is just a driver function.  */
 259
 260 bool
 261 scop_do_strip_mine (scop_p scop)
 262 {
 263   bool transform_done = false;
 264
 265   store_scattering (scop);
 266
 267   transform_done = lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop));
 268
 269   if (!transform_done)
 270     return false;
 271
 272   if (!graphite_legal_transform (scop))
 273     {
 274       restore_scattering (scop);
 275       return false;
 276     }
 277
 278   return transform_done;
 279 }
 280
 281 /* Loop blocks all the loops in SCOP.  Returns true when we manage to
 282    block some loops.  */
 283
 284 bool
 285 scop_do_block (scop_p scop)
 286 {
 287   bool strip_mined = false;
 288   bool interchanged = false;
 289
 290   store_scattering (scop);
 291
 292   strip_mined = lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop));
 293   interchanged = scop_do_interchange (scop);
 294
 295   /* If we don't interchange loops, then the strip mine is not
 296      profitable, and the transform is not a loop blocking.  */
 297   if (!interchanged
 298       || !graphite_legal_transform (scop))
 299     {
 300       restore_scattering (scop);
 301       return false;
 302     }
 303   else if (strip_mined && interchanged
 304            && dump_file && (dump_flags & TDF_DETAILS))
 305     fprintf (dump_file, "SCoP will be loop blocked.\n");
 306
 307   return strip_mined || interchanged;
 308 }
 309
 310 #endif