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 "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
  57 /* Strip mines with a factor STRIDE the loop around PBB at depth
  58    LOOP_DEPTH.  The following example comes from the wiki page:
  59    http://gcc.gnu.org/wiki/Graphite/Strip_mine
  60
  61    The strip mine of a loop with a tile of 64 can be obtained with a
  62    scattering function as follows:
  63
  64    $ cat ./albert_strip_mine.cloog
  65    # language: C
  66    c
  67
  68    # parameter {n | n >= 0}
  69    1 3
  70    #  n  1
  71    1  1  0
  72    1
  73    n
  74
  75    1 # Number of statements:
  76
  77    1
  78    # {i | 0 <= i <= n}
  79    2 4
  80    #  i  n   1
  81    1  1  0   0
  82    1 -1  1   0
  83
  84    0  0  0
  85    1
  86    i
  87
  88    1 # Scattering functions
  89
  90    3 6
  91    #  NEW  OLD    i    n    1
  92    1  -64    0    1    0    0
  93    1   64    0   -1    0   63
  94    0    0    1   -1    0    0
  95
  96    1
  97    NEW  OLD
  98
  99    #the output of CLooG is like this:
 100    #$ cloog ./albert_strip_mine.cloog
 101    # for (NEW=0;NEW<=floord(n,64);NEW++) {
 102    #   for (OLD=max(64*NEW,0);OLD<=min(64*NEW+63,n);OLD++) {
 103    #     S1(i = OLD) ;
 104    #   }
 105    # }
 106 */
 107
 108 static bool
 109 pbb_strip_mine_loop_depth (poly_bb_p pbb, int loop_depth, int stride)
 110 {
 111   ppl_dimension_type iter, dim;
 112   ppl_Polyhedron_t res = PBB_TRANSFORMED_SCATTERING (pbb);
 113   ppl_dimension_type strip = psct_scattering_dim_for_loop_depth (pbb,
 114                                                                  loop_depth);
 115
 116   psct_add_scattering_dimension (pbb, strip);
 117
 118   iter = psct_iterator_dim (pbb, loop_depth);
 119   ppl_Polyhedron_space_dimension (res, &dim);
 120
 121   /* Lower bound of the striped loop.  */
 122   {
 123     ppl_Constraint_t new_cstr;
 124     ppl_Linear_Expression_t expr;
 125
 126     ppl_new_Linear_Expression_with_dimension (&expr, dim);
 127     ppl_set_coef (expr, strip, -1 * stride);
 128     ppl_set_coef (expr, iter, 1);
 129
 130     ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
 131     ppl_delete_Linear_Expression (expr);
 132     ppl_Polyhedron_add_constraint (res, new_cstr);
 133     ppl_delete_Constraint (new_cstr);
 134   }
 135
 136   /* Upper bound of the striped loop.  */
 137   {
 138     ppl_Constraint_t new_cstr;
 139     ppl_Linear_Expression_t expr;
 140
 141     ppl_new_Linear_Expression_with_dimension (&expr, dim);
 142     ppl_set_coef (expr, strip, stride);
 143     ppl_set_coef (expr, iter, -1);
 144     ppl_set_inhomogeneous (expr, stride - 1);
 145
 146     ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
 147     ppl_delete_Linear_Expression (expr);
 148     ppl_Polyhedron_add_constraint (res, new_cstr);
 149     ppl_delete_Constraint (new_cstr);
 150   }
 151
 152   return true;
 153 }
 154
 155 /* Returns true when strip mining with STRIDE of the loop around PBB
 156    at depth LOOP_DEPTH is profitable.  */
 157
 158 static bool
 159 pbb_strip_mine_profitable_p (poly_bb_p pbb,
 160                              graphite_dim_t loop_depth,
 161                              int stride)
 162 {
 163   Value niter, strip_stride;
 164   bool res;
 165
 166   value_init (strip_stride);
 167   value_init (niter);
 168   value_set_si (strip_stride, stride);
 169   pbb_number_of_iterations (pbb, loop_depth, niter);
 170   res = value_gt (niter, strip_stride);
 171   value_clear (strip_stride);
 172   value_clear (niter);
 173
 174   return res;
 175 }
 176
 177 /* Strip mines all the loops around PBB.  Nothing profitable in all this:
 178    this is just a driver function.  */
 179
 180 static bool
 181 pbb_do_strip_mine (poly_bb_p pbb)
 182 {
 183   graphite_dim_t loop_depth;
 184   int stride = 64;
 185   bool transform_done = false;
 186
 187   for (loop_depth = 0; loop_depth < pbb_dim_iter_domain (pbb); loop_depth++)
 188     if (pbb_strip_mine_profitable_p (pbb, loop_depth, stride))
 189       transform_done |= pbb_strip_mine_loop_depth (pbb, loop_depth, stride);
 190
 191   return transform_done;
 192 }
 193
 194 /* Strip mines all the loops in SCOP.  Nothing profitable in all this:
 195    this is just a driver function.  */
 196
 197 bool
 198 scop_do_strip_mine (scop_p scop)
 199 {
 200   poly_bb_p pbb;
 201   int i;
 202   bool transform_done = false;
 203
 204   store_scattering (scop);
 205
 206   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
 207     transform_done |= pbb_do_strip_mine (pbb);
 208
 209   if (!transform_done)
 210     return false;
 211
 212   if (!graphite_legal_transform (scop))
 213     {
 214       restore_scattering (scop);
 215       return false;
 216     }
 217
 218   return true;
 219 }
 220
 221 #endif