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 loop around PBB at depth
58 LOOP_DEPTH. The following example comes from the wiki page:
59 http://gcc.gnu.org/wiki/Graphite/Strip_mine
61 The strip mine of a loop with a tile of 64 can be obtained with a
62 scattering function as follows:
64 $ cat ./albert_strip_mine.cloog
68 # parameter {n | n >= 0}
75 1 # Number of statements:
88 1 # Scattering functions
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++) {
109 pbb_strip_mine_loop_depth (poly_bb_p pbb, int loop_depth, int stride)
111 ppl_dimension_type iter, dim;
112 ppl_Polyhedron_t res = PBB_TRANSFORMED_SCATTERING (pbb);
113 ppl_dimension_type strip = psct_scattering_dim_for_loop_depth (pbb,
116 psct_add_scattering_dimension (pbb, strip);
118 iter = psct_iterator_dim (pbb, loop_depth);
119 ppl_Polyhedron_space_dimension (res, &dim);
121 /* Lower bound of the striped loop. */
123 ppl_Constraint_t new_cstr;
124 ppl_Linear_Expression_t expr;
126 ppl_new_Linear_Expression_with_dimension (&expr, dim);
127 ppl_set_coef (expr, strip, -1 * stride);
128 ppl_set_coef (expr, iter, 1);
130 ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
131 ppl_delete_Linear_Expression (expr);
132 ppl_Polyhedron_add_constraint (res, new_cstr);
133 ppl_delete_Constraint (new_cstr);
136 /* Upper bound of the striped loop. */
138 ppl_Constraint_t new_cstr;
139 ppl_Linear_Expression_t expr;
141 ppl_new_Linear_Expression_with_dimension (&expr, dim);
142 ppl_set_coef (expr, strip, stride);
143 ppl_set_coef (expr, iter, -1);
144 ppl_set_inhomogeneous (expr, stride - 1);
146 ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
147 ppl_delete_Linear_Expression (expr);
148 ppl_Polyhedron_add_constraint (res, new_cstr);
149 ppl_delete_Constraint (new_cstr);
155 /* Returns true when strip mining with STRIDE of the loop around PBB
156 at depth LOOP_DEPTH is profitable. */
159 pbb_strip_mine_profitable_p (poly_bb_p pbb,
160 graphite_dim_t loop_depth,
163 Value niter, strip_stride;
166 value_init (strip_stride);
168 value_set_si (strip_stride, stride);
169 pbb_number_of_iterations (pbb, loop_depth, niter);
170 res = value_gt (niter, strip_stride);
171 value_clear (strip_stride);
177 /* Strip mines all the loops around PBB. Nothing profitable in all this:
178 this is just a driver function. */
181 pbb_do_strip_mine (poly_bb_p pbb)
183 graphite_dim_t loop_depth;
185 bool transform_done = false;
187 for (loop_depth = 0; loop_depth < pbb_dim_iter_domain (pbb); loop_depth++)
188 if (pbb_strip_mine_profitable_p (pbb, loop_depth, stride))
189 transform_done |= pbb_strip_mine_loop_depth (pbb, loop_depth, stride);
191 return transform_done;
194 /* Strip mines all the loops in SCOP. Nothing profitable in all this:
195 this is just a driver function. */
198 scop_do_strip_mine (scop_p scop)
202 bool transform_done = false;
204 store_scattering (scop);
206 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
207 transform_done |= pbb_do_strip_mine (pbb);
212 if (!graphite_legal_transform (scop))
214 restore_scattering (scop);