1 /* Heuristics and transform for loop blocking and strip mining on
2 polyhedral representation.
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>.
8 This file is part of GCC.
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)
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.
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/>. */
25 #include "coretypes.h"
31 #include "basic-block.h"
32 #include "diagnostic.h"
33 #include "tree-flow.h"
35 #include "tree-dump.h"
38 #include "tree-chrec.h"
39 #include "tree-data-ref.h"
40 #include "tree-scalar-evolution.h"
41 #include "tree-pass.h"
43 #include "value-prof.h"
44 #include "pointer-set.h"
49 #include "cloog/cloog.h"
52 #include "graphite-ppl.h"
54 #include "graphite-poly.h"
57 /* Strip mines with a factor STRIDE the scattering (time) dimension
58 around PBB at depth TIME_DEPTH.
60 The following example comes from the wiki page:
61 http://gcc.gnu.org/wiki/Graphite/Strip_mine
63 The strip mine of a loop with a tile of 64 can be obtained with a
64 scattering function as follows:
66 $ cat ./albert_strip_mine.cloog
70 # parameter {n | n >= 0}
77 1 # Number of statements:
90 1 # Scattering functions
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++) {
111 pbb_strip_mine_time_depth (poly_bb_p pbb, int time_depth, int stride)
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. */
121 psct_add_scattering_dimension (pbb, strip);
122 psct_add_scattering_dimension (pbb, strip + 1);
124 ppl_Polyhedron_space_dimension (res, &dim);
126 /* Lower bound of the striped loop. */
128 ppl_Constraint_t new_cstr;
129 ppl_Linear_Expression_t expr;
131 ppl_new_Linear_Expression_with_dimension (&expr, dim);
132 ppl_set_coef (expr, strip, -1 * stride);
133 ppl_set_coef (expr, iter, 1);
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);
141 /* Upper bound of the striped loop. */
143 ppl_Constraint_t new_cstr;
144 ppl_Linear_Expression_t expr;
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);
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);
157 /* Static scheduling for ITER level.
158 This is mandatory to keep the 2d + 1 canonical scheduling format. */
160 ppl_Constraint_t new_cstr;
161 ppl_Linear_Expression_t expr;
163 ppl_new_Linear_Expression_with_dimension (&expr, dim);
164 ppl_set_coef (expr, strip + 1, 1);
165 ppl_set_inhomogeneous (expr, 0);
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);
176 /* Returns true when strip mining with STRIDE of the loop around PBB
177 at DEPTH is profitable. */
180 pbb_strip_mine_profitable_p (poly_bb_p pbb,
181 graphite_dim_t depth,
184 Value niter, strip_stride;
187 value_init (strip_stride);
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);
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. */
202 lst_do_strip_mine_loop (lst_p lst, int depth)
206 int stride = PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE);
212 if (LST_LOOP_P (lst))
216 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
217 res |= lst_do_strip_mine_loop (l, depth);
223 return pbb_strip_mine_time_depth (pbb, psct_dynamic_dim (pbb, depth),
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. */
231 lst_do_strip_mine (lst_p lst)
236 int stride = PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE);
240 || !LST_LOOP_P (lst))
243 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
244 res |= lst_do_strip_mine (l);
246 depth = lst_depth (lst);
248 && pbb_strip_mine_profitable_p (LST_PBB (lst_find_first_pbb (lst)),
251 res |= lst_do_strip_mine_loop (lst, lst_depth (lst));
252 lst_add_loop_under_loop (lst);
258 /* Strip mines all the loops in SCOP. Nothing profitable in all this:
259 this is just a driver function. */
262 scop_do_strip_mine (scop_p scop)
264 bool transform_done = false;
266 store_scattering (scop);
268 transform_done = lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop));
273 if (!graphite_legal_transform (scop))
275 restore_scattering (scop);
279 return transform_done;
282 /* Loop blocks all the loops in SCOP. Returns true when we manage to
286 scop_do_block (scop_p scop)
288 bool strip_mined = false;
289 bool interchanged = false;
291 store_scattering (scop);
293 strip_mined = lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop));
294 interchanged = scop_do_interchange (scop);
296 /* If we don't interchange loops, then the strip mine is not
297 profitable, and the transform is not a loop blocking. */
299 || !graphite_legal_transform (scop))
301 restore_scattering (scop);
304 else if (strip_mined && interchanged
305 && dump_file && (dump_flags & TDF_DETAILS))
306 fprintf (dump_file, "SCoP will be loop blocked.\n");
308 return strip_mined || interchanged;