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