Daily bump.
[official-gcc.git] / gcc / graphite-blocking.c
blobbcd077a8310876da1c70d3f73143da72ec9be3ee
1 /* Heuristics and transform for loop blocking and strip mining on
2 polyhedral representation.
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>.
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)
13 any later version.
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/>. */
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"
33 #ifdef HAVE_cloog
34 #include "ppl_c.h"
35 #include "graphite-ppl.h"
36 #include "graphite-poly.h"
39 /* Strip mines with a factor STRIDE the scattering (time) dimension
40 around PBB at depth TIME_DEPTH.
42 The following example comes from the wiki page:
43 http://gcc.gnu.org/wiki/Graphite/Strip_mine
45 The strip mine of a loop with a tile of 64 can be obtained with a
46 scattering function as follows:
48 $ cat ./albert_strip_mine.cloog
49 # language: C
52 # parameter {n | n >= 0}
53 1 3
54 # n 1
55 1 1 0
59 1 # Number of statements:
62 # {i | 0 <= i <= n}
63 2 4
64 # i n 1
65 1 1 0 0
66 1 -1 1 0
68 0 0 0
72 1 # Scattering functions
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
81 NEW OLD
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 # }
92 static bool
93 pbb_strip_mine_time_depth (poly_bb_p pbb, int time_depth, int stride)
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;
103 psct_add_scattering_dimension (pbb, strip);
104 psct_add_scattering_dimension (pbb, strip + 1);
106 ppl_Polyhedron_space_dimension (res, &dim);
108 /* Lower bound of the striped loop. */
110 ppl_Constraint_t new_cstr;
111 ppl_Linear_Expression_t expr;
113 ppl_new_Linear_Expression_with_dimension (&expr, dim);
114 ppl_set_coef (expr, strip, -1 * stride);
115 ppl_set_coef (expr, iter, 1);
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);
123 /* Upper bound of the striped loop. */
125 ppl_Constraint_t new_cstr;
126 ppl_Linear_Expression_t expr;
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);
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);
139 /* Static scheduling for ITER level.
140 This is mandatory to keep the 2d + 1 canonical scheduling format. */
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 + 1, 1);
147 ppl_set_inhomogeneous (expr, 0);
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);
155 return true;
158 /* Returns true when strip mining with STRIDE of the loop LST is
159 profitable. */
161 static bool
162 lst_strip_mine_profitable_p (lst_p lst, int stride)
164 mpz_t niter, strip_stride;
165 bool res;
167 gcc_assert (LST_LOOP_P (lst));
168 mpz_init (strip_stride);
169 mpz_init (niter);
171 mpz_set_si (strip_stride, stride);
172 lst_niter_for_loop (lst, niter);
173 res = (mpz_cmp (niter, strip_stride) > 0);
175 mpz_clear (strip_stride);
176 mpz_clear (niter);
177 return res;
180 /* Strip-mines all the loops of LST with STRIDE. Return true if it
181 did strip-mined some loops. */
183 static bool
184 lst_do_strip_mine_loop (lst_p lst, int depth, int stride)
186 int i;
187 lst_p l;
188 poly_bb_p pbb;
190 if (!lst)
191 return false;
193 if (LST_LOOP_P (lst))
195 bool res = false;
197 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
198 res |= lst_do_strip_mine_loop (l, depth, stride);
200 return res;
203 pbb = LST_PBB (lst);
204 return pbb_strip_mine_time_depth (pbb, psct_dynamic_dim (pbb, depth),
205 stride);
208 /* Strip-mines all the loops of LST with STRIDE. When STRIDE is zero,
209 read the stride from the PARAM_LOOP_BLOCK_TILE_SIZE. Return true
210 if it did strip-mined some loops.
212 Strip mining transforms a loop
214 | for (i = 0; i < N; i++)
215 | S (i);
217 into the following loop nest:
219 | for (k = 0; k < N; k += STRIDE)
220 | for (j = 0; j < STRIDE; j++)
221 | S (i = k + j);
224 static bool
225 lst_do_strip_mine (lst_p lst, int stride)
227 int i;
228 lst_p l;
229 bool res = false;
230 int depth;
232 if (!stride)
233 stride = PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE);
235 if (!lst
236 || !LST_LOOP_P (lst))
237 return false;
239 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
240 res |= lst_do_strip_mine (l, stride);
242 depth = lst_depth (lst);
243 if (depth >= 0
244 && lst_strip_mine_profitable_p (lst, stride))
246 res |= lst_do_strip_mine_loop (lst, lst_depth (lst), stride);
247 lst_add_loop_under_loop (lst);
250 return res;
253 /* Strip mines all the loops in SCOP. Returns true when some loops
254 have been strip-mined. */
256 bool
257 scop_do_strip_mine (scop_p scop, int stride)
259 return lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop), stride);
262 /* Loop blocks all the loops in SCOP. Returns true when we manage to
263 block some loops. */
265 bool
266 scop_do_block (scop_p scop)
268 bool strip_mined = false;
269 bool interchanged = false;
271 store_scattering (scop);
273 strip_mined = lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop), 0);
274 interchanged = scop_do_interchange (scop);
276 /* If we don't interchange loops, the strip mine alone will not be
277 profitable, and the transform is not a loop blocking: so revert
278 the transform. */
279 if (!interchanged)
281 restore_scattering (scop);
282 return false;
284 else if (strip_mined && interchanged
285 && dump_file && (dump_flags & TDF_DETAILS))
286 fprintf (dump_file, "SCoP will be loop blocked.\n");
288 return strip_mined || interchanged;
291 #endif