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"
51 #include "graphite-ppl.h"
53 #include "graphite-poly.h"
56 /* Strip mines with a factor STRIDE the scattering (time) dimension
57 around PBB at depth TIME_DEPTH.
59 The following example comes from the wiki page:
60 http://gcc.gnu.org/wiki/Graphite/Strip_mine
62 The strip mine of a loop with a tile of 64 can be obtained with a
63 scattering function as follows:
65 $ cat ./albert_strip_mine.cloog
69 # parameter {n | n >= 0}
76 1 # Number of statements:
89 1 # Scattering functions
100 #the output of CLooG is like this:
101 #$ cloog ./albert_strip_mine.cloog
102 # for (NEW=0;NEW<=floord(n,64);NEW++) {
103 # for (OLD=max(64*NEW,0);OLD<=min(64*NEW+63,n);OLD++) {
110 pbb_strip_mine_time_depth (poly_bb_p pbb
, int time_depth
, int stride
)
112 ppl_dimension_type iter
, dim
, strip
;
113 ppl_Polyhedron_t res
= PBB_TRANSFORMED_SCATTERING (pbb
);
114 /* STRIP is the dimension that iterates with stride STRIDE. */
115 /* ITER is the dimension that enumerates single iterations inside
116 one strip that has at most STRIDE iterations. */
120 psct_add_scattering_dimension (pbb
, strip
);
121 psct_add_scattering_dimension (pbb
, strip
+ 1);
123 ppl_Polyhedron_space_dimension (res
, &dim
);
125 /* Lower bound of the striped loop. */
127 ppl_Constraint_t new_cstr
;
128 ppl_Linear_Expression_t expr
;
130 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
131 ppl_set_coef (expr
, strip
, -1 * stride
);
132 ppl_set_coef (expr
, iter
, 1);
134 ppl_new_Constraint (&new_cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
135 ppl_delete_Linear_Expression (expr
);
136 ppl_Polyhedron_add_constraint (res
, new_cstr
);
137 ppl_delete_Constraint (new_cstr
);
140 /* Upper bound of the striped loop. */
142 ppl_Constraint_t new_cstr
;
143 ppl_Linear_Expression_t expr
;
145 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
146 ppl_set_coef (expr
, strip
, stride
);
147 ppl_set_coef (expr
, iter
, -1);
148 ppl_set_inhomogeneous (expr
, stride
- 1);
150 ppl_new_Constraint (&new_cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
151 ppl_delete_Linear_Expression (expr
);
152 ppl_Polyhedron_add_constraint (res
, new_cstr
);
153 ppl_delete_Constraint (new_cstr
);
156 /* Static scheduling for ITER level.
157 This is mandatory to keep the 2d + 1 canonical scheduling format. */
159 ppl_Constraint_t new_cstr
;
160 ppl_Linear_Expression_t expr
;
162 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
163 ppl_set_coef (expr
, strip
+ 1, 1);
164 ppl_set_inhomogeneous (expr
, 0);
166 ppl_new_Constraint (&new_cstr
, expr
, PPL_CONSTRAINT_TYPE_EQUAL
);
167 ppl_delete_Linear_Expression (expr
);
168 ppl_Polyhedron_add_constraint (res
, new_cstr
);
169 ppl_delete_Constraint (new_cstr
);
175 /* Returns true when strip mining with STRIDE of the loop around PBB
176 at DEPTH is profitable. */
179 pbb_strip_mine_profitable_p (poly_bb_p pbb
,
180 graphite_dim_t depth
,
183 mpz_t niter
, strip_stride
;
186 mpz_init (strip_stride
);
188 mpz_set_si (strip_stride
, stride
);
189 pbb_number_of_iterations_at_time (pbb
, psct_dynamic_dim (pbb
, depth
), niter
);
190 res
= (mpz_cmp (niter
, strip_stride
) > 0);
191 mpz_clear (strip_stride
);
197 /* Strip-mines all the loops of LST that are considered profitable to
198 strip-mine. Return true if it did strip-mined some loops. */
201 lst_do_strip_mine_loop (lst_p lst
, int depth
)
205 int stride
= PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE
);
211 if (LST_LOOP_P (lst
))
215 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (lst
), i
, l
); i
++)
216 res
|= lst_do_strip_mine_loop (l
, depth
);
222 return pbb_strip_mine_time_depth (pbb
, psct_dynamic_dim (pbb
, depth
),
226 /* Strip-mines all the loops of LST that are considered profitable to
227 strip-mine. Return true if it did strip-mined some loops. */
230 lst_do_strip_mine (lst_p lst
)
235 int stride
= PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE
);
239 || !LST_LOOP_P (lst
))
242 for (i
= 0; VEC_iterate (lst_p
, LST_SEQ (lst
), i
, l
); i
++)
243 res
|= lst_do_strip_mine (l
);
245 depth
= lst_depth (lst
);
247 && pbb_strip_mine_profitable_p (LST_PBB (lst_find_first_pbb (lst
)),
250 res
|= lst_do_strip_mine_loop (lst
, lst_depth (lst
));
251 lst_add_loop_under_loop (lst
);
257 /* Strip mines all the loops in SCOP. Nothing profitable in all this:
258 this is just a driver function. */
261 scop_do_strip_mine (scop_p scop
)
263 bool transform_done
= false;
265 store_scattering (scop
);
267 transform_done
= lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop
));
272 if (!graphite_legal_transform (scop
))
274 restore_scattering (scop
);
278 return transform_done
;
281 /* Loop blocks all the loops in SCOP. Returns true when we manage to
285 scop_do_block (scop_p scop
)
287 bool strip_mined
= false;
288 bool interchanged
= false;
290 store_scattering (scop
);
292 strip_mined
= lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop
));
293 interchanged
= scop_do_interchange (scop
);
295 /* If we don't interchange loops, then the strip mine is not
296 profitable, and the transform is not a loop blocking. */
298 || !graphite_legal_transform (scop
))
300 restore_scattering (scop
);
303 else if (strip_mined
&& interchanged
304 && dump_file
&& (dump_flags
& TDF_DETAILS
))
305 fprintf (dump_file
, "SCoP will be loop blocked.\n");
307 return strip_mined
|| interchanged
;