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 "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 "tree-dump.h"
  35 #include "timevar.h"
  36 #include "cfgloop.h"
  37 #include "tree-chrec.h"
  38 #include "tree-data-ref.h"
  39 #include "tree-scalar-evolution.h"
  40 #include "tree-pass.h"
  41 #include "domwalk.h"
  42 #include "value-prof.h"
  43 #include "pointer-set.h"
  44 #include "gimple.h"
  45 #include "params.h"
  46
  47 #ifdef HAVE_cloog
  48 #include "ppl_c.h"
  49 #include "sese.h"
  50 #include "graphite-ppl.h"
  51 #include "graphite.h"
  52 #include "graphite-poly.h"
  53
  54
  55 /* Strip mines with a factor STRIDE the scattering (time) dimension
  56    around PBB at depth TIME_DEPTH.
  57
  58    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_time_depth (poly_bb_p pbb, int time_depth, int stride)
 110 {
 111   ppl_dimension_type iter, dim, strip;
 112   ppl_Polyhedron_t res = PBB_TRANSFORMED_SCATTERING (pbb);
 113   /* STRIP is the dimension that iterates with stride STRIDE.  */
 114   /* ITER is the dimension that enumerates single iterations inside
 115      one strip that has at most STRIDE iterations.  */
 116   strip = time_depth;
 117   iter = strip + 2;
 118
 119   psct_add_scattering_dimension (pbb, strip);
 120   psct_add_scattering_dimension (pbb, strip + 1);
 121
 122   ppl_Polyhedron_space_dimension (res, &dim);
 123
 124   /* Lower bound of the striped loop.  */
 125   {
 126     ppl_Constraint_t new_cstr;
 127     ppl_Linear_Expression_t expr;
 128
 129     ppl_new_Linear_Expression_with_dimension (&expr, dim);
 130     ppl_set_coef (expr, strip, -1 * stride);
 131     ppl_set_coef (expr, iter, 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   /* Upper bound of the striped loop.  */
 140   {
 141     ppl_Constraint_t new_cstr;
 142     ppl_Linear_Expression_t expr;
 143
 144     ppl_new_Linear_Expression_with_dimension (&expr, dim);
 145     ppl_set_coef (expr, strip, stride);
 146     ppl_set_coef (expr, iter, -1);
 147     ppl_set_inhomogeneous (expr, stride - 1);
 148
 149     ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
 150     ppl_delete_Linear_Expression (expr);
 151     ppl_Polyhedron_add_constraint (res, new_cstr);
 152     ppl_delete_Constraint (new_cstr);
 153   }
 154
 155   /* Static scheduling for ITER level.
 156      This is mandatory to keep the 2d + 1 canonical scheduling format.  */
 157   {
 158     ppl_Constraint_t new_cstr;
 159     ppl_Linear_Expression_t expr;
 160
 161     ppl_new_Linear_Expression_with_dimension (&expr, dim);
 162     ppl_set_coef (expr, strip + 1, 1);
 163     ppl_set_inhomogeneous (expr, 0);
 164
 165     ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
 166     ppl_delete_Linear_Expression (expr);
 167     ppl_Polyhedron_add_constraint (res, new_cstr);
 168     ppl_delete_Constraint (new_cstr);
 169   }
 170
 171   return true;
 172 }
 173
 174 /* Returns true when strip mining with STRIDE of the loop LST is
 175    profitable.  */
 176
 177 static bool
 178 lst_strip_mine_profitable_p (lst_p lst, int stride)
 179 {
 180   mpz_t niter, strip_stride;
 181   bool res;
 182
 183   gcc_assert (LST_LOOP_P (lst));
 184   mpz_init (strip_stride);
 185   mpz_init (niter);
 186
 187   mpz_set_si (strip_stride, stride);
 188   lst_niter_for_loop (lst, niter);
 189   res = (mpz_cmp (niter, strip_stride) > 0);
 190
 191   mpz_clear (strip_stride);
 192   mpz_clear (niter);
 193   return res;
 194 }
 195
 196 /* Strip-mines all the loops of LST with STRIDE.  Return true if it
 197    did strip-mined some loops.  */
 198
 199 static bool
 200 lst_do_strip_mine_loop (lst_p lst, int depth, int stride)
 201 {
 202   int i;
 203   lst_p l;
 204   poly_bb_p pbb;
 205
 206   if (!lst)
 207     return false;
 208
 209   if (LST_LOOP_P (lst))
 210     {
 211       bool res = false;
 212
 213       FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
 214         res |= lst_do_strip_mine_loop (l, depth, stride);
 215
 216       return res;
 217     }
 218
 219   pbb = LST_PBB (lst);
 220   return pbb_strip_mine_time_depth (pbb, psct_dynamic_dim (pbb, depth),
 221                                     stride);
 222 }
 223
 224 /* Strip-mines all the loops of LST with STRIDE.  When STRIDE is zero,
 225    read the stride from the PARAM_LOOP_BLOCK_TILE_SIZE.  Return true
 226    if it did strip-mined some loops.
 227
 228    Strip mining transforms a loop
 229
 230    | for (i = 0; i < N; i++)
 231    |   S (i);
 232
 233    into the following loop nest:
 234
 235    | for (k = 0; k < N; k += STRIDE)
 236    |   for (j = 0; j < STRIDE; j++)
 237    |     S (i = k + j);
 238 */
 239
 240 static bool
 241 lst_do_strip_mine (lst_p lst, int stride)
 242 {
 243   int i;
 244   lst_p l;
 245   bool res = false;
 246   int depth;
 247
 248   if (!stride)
 249     stride = PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE);
 250
 251   if (!lst
 252       || !LST_LOOP_P (lst))
 253     return false;
 254
 255   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
 256     res |= lst_do_strip_mine (l, stride);
 257
 258   depth = lst_depth (lst);
 259   if (depth >= 0
 260       && lst_strip_mine_profitable_p (lst, stride))
 261     {
 262       res |= lst_do_strip_mine_loop (lst, lst_depth (lst), stride);
 263       lst_add_loop_under_loop (lst);
 264     }
 265
 266   return res;
 267 }
 268
 269 /* Strip mines all the loops in SCOP.  Returns true when some loops
 270    have been strip-mined.  */
 271
 272 bool
 273 scop_do_strip_mine (scop_p scop, int stride)
 274 {
 275   return lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop), stride);
 276 }
 277
 278 /* Loop blocks all the loops in SCOP.  Returns true when we manage to
 279    block some loops.  */
 280
 281 bool
 282 scop_do_block (scop_p scop)
 283 {
 284   bool strip_mined = false;
 285   bool interchanged = false;
 286
 287   store_scattering (scop);
 288
 289   strip_mined = lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop), 0);
 290   interchanged = scop_do_interchange (scop);
 291
 292   /* If we don't interchange loops, the strip mine alone will not be
 293      profitable, and the transform is not a loop blocking: so revert
 294      the transform.  */
 295   if (!interchanged)
 296     {
 297       restore_scattering (scop);
 298       return false;
 299     }
 300   else if (strip_mined && interchanged
 301            && dump_file && (dump_flags & TDF_DETAILS))
 302     fprintf (dump_file, "SCoP will be loop blocked.\n");
 303
 304   return strip_mined || interchanged;
 305 }
 306
 307 #endif