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