2011-10-08 Paul Thomas <pault@gcc.gnu.org>
[official-gcc.git] / gcc / graphite-flattening.c
blobccd0f5f0c6ff5f60a833241f303066d12ecc79de
1 /* Loop flattening for Graphite.
2 Copyright (C) 2010 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tree-flow.h"
25 #include "tree-dump.h"
26 #include "cfgloop.h"
27 #include "tree-chrec.h"
28 #include "tree-data-ref.h"
29 #include "tree-scalar-evolution.h"
30 #include "sese.h"
32 #ifdef HAVE_cloog
33 #include "ppl_c.h"
34 #include "graphite-ppl.h"
35 #include "graphite-poly.h"
37 /* The loop flattening pass transforms loop nests into a single loop,
38 removing the loop nesting structure. The auto-vectorization can
39 then apply on the full loop body, without needing the outer-loop
40 vectorization.
42 The loop flattening pass that has been described in a very Fortran
43 specific way in the 1992 paper by Reinhard von Hanxleden and Ken
44 Kennedy: "Relaxing SIMD Control Flow Constraints using Loop
45 Transformations" available from
46 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.5033
48 The canonical example is as follows: suppose that we have a loop
49 nest with known iteration counts
51 | for (i = 1; i <= 6; i++)
52 | for (j = 1; j <= 6; j++)
53 | S1(i,j);
55 The loop flattening is performed by linearizing the iteration space
56 using the function "f (x) = 6 * i + j". In this case, CLooG would
57 produce this code:
59 | for (c1=7;c1<=42;c1++) {
60 | i = floord(c1-1,6);
61 | S1(i,c1-6*i);
62 | }
64 There are several limitations for loop flattening that are linked
65 to the expressivity of the polyhedral model. One has to take an
66 upper bound approximation to deal with the parametric case of loop
67 flattening. For example, in the loop nest:
69 | for (i = 1; i <= N; i++)
70 | for (j = 1; j <= M; j++)
71 | S1(i,j);
73 One would like to flatten this loop using a linearization function
74 like this "f (x) = M * i + j". However CLooG's schedules are not
75 expressive enough to deal with this case, and so the parameter M
76 has to be replaced by an integer upper bound approximation. If we
77 further know in the context of the scop that "M <= 6", then it is
78 possible to linearize the loop with "f (x) = 6 * i + j". In this
79 case, CLooG would produce this code:
81 | for (c1=7;c1<=6*M+N;c1++) {
82 | i = ceild(c1-N,6);
83 | if (i <= floord(c1-1,6)) {
84 | S1(i,c1-6*i);
85 | }
86 | }
88 For an arbitrarily complex loop nest the algorithm proceeds in two
89 steps. First, the LST is flattened by removing the loops structure
90 and by inserting the statements in the order they appear in
91 depth-first order. Then, the scattering of each statement is
92 transformed accordingly.
94 Supposing that the original program is represented by the following
95 LST:
97 | (loop_1
98 | stmt_1
99 | (loop_2 stmt_3
100 | (loop_3 stmt_4)
101 | (loop_4 stmt_5 stmt_6)
102 | stmt_7
104 | stmt_2
107 Loop flattening traverses the LST in depth-first order, and
108 flattens pairs of loops successively by projecting the inner loops
109 in the iteration domain of the outer loops:
111 lst_project_loop (loop_2, loop_3, stride)
113 | (loop_1
114 | stmt_1
115 | (loop_2 stmt_3 stmt_4
116 | (loop_4 stmt_5 stmt_6)
117 | stmt_7
119 | stmt_2
122 lst_project_loop (loop_2, loop_4, stride)
124 | (loop_1
125 | stmt_1
126 | (loop_2 stmt_3 stmt_4 stmt_5 stmt_6 stmt_7)
127 | stmt_2
130 lst_project_loop (loop_1, loop_2, stride)
132 | (loop_1
133 | stmt_1 stmt_3 stmt_4 stmt_5 stmt_6 stmt_7 stmt_2
136 At each step, the iteration domain of the outer loop is enlarged to
137 contain enough points to iterate over the inner loop domain. */
139 /* Initializes RES to the number of iterations of the linearized loop
140 LST. RES is the cardinal of the iteration domain of LST. */
142 static void
143 lst_linearized_niter (lst_p lst, mpz_t res)
145 int i;
146 lst_p l;
147 mpz_t n;
149 mpz_init (n);
150 mpz_set_si (res, 0);
152 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
153 if (LST_LOOP_P (l))
155 lst_linearized_niter (l, n);
156 mpz_add (res, res, n);
159 if (LST_LOOP_P (lst))
161 lst_niter_for_loop (lst, n);
163 if (mpz_cmp_si (res, 0) != 0)
164 mpz_mul (res, res, n);
165 else
166 mpz_set (res, n);
169 mpz_clear (n);
172 /* Applies the translation "f (x) = x + OFFSET" to the loop containing
173 STMT. */
175 static void
176 lst_offset (lst_p stmt, mpz_t offset)
178 lst_p inner = LST_LOOP_FATHER (stmt);
179 poly_bb_p pbb = LST_PBB (stmt);
180 ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
181 int inner_depth = lst_depth (inner);
182 ppl_dimension_type inner_dim = psct_dynamic_dim (pbb, inner_depth);
183 ppl_Linear_Expression_t expr;
184 ppl_dimension_type dim;
185 ppl_Coefficient_t one;
186 mpz_t x;
188 mpz_init (x);
189 mpz_set_si (x, 1);
190 ppl_new_Coefficient (&one);
191 ppl_assign_Coefficient_from_mpz_t (one, x);
193 ppl_Polyhedron_space_dimension (poly, &dim);
194 ppl_new_Linear_Expression_with_dimension (&expr, dim);
196 ppl_set_coef (expr, inner_dim, 1);
197 ppl_set_inhomogeneous_gmp (expr, offset);
198 ppl_Polyhedron_affine_image (poly, inner_dim, expr, one);
199 ppl_delete_Linear_Expression (expr);
200 ppl_delete_Coefficient (one);
203 /* Scale by FACTOR the loop LST containing STMT. */
205 static void
206 lst_scale (lst_p lst, lst_p stmt, mpz_t factor)
208 mpz_t x;
209 ppl_Coefficient_t one;
210 int outer_depth = lst_depth (lst);
211 poly_bb_p pbb = LST_PBB (stmt);
212 ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
213 ppl_dimension_type outer_dim = psct_dynamic_dim (pbb, outer_depth);
214 ppl_Linear_Expression_t expr;
215 ppl_dimension_type dim;
217 mpz_init (x);
218 mpz_set_si (x, 1);
219 ppl_new_Coefficient (&one);
220 ppl_assign_Coefficient_from_mpz_t (one, x);
222 ppl_Polyhedron_space_dimension (poly, &dim);
223 ppl_new_Linear_Expression_with_dimension (&expr, dim);
225 /* outer_dim = factor * outer_dim. */
226 ppl_set_coef_gmp (expr, outer_dim, factor);
227 ppl_Polyhedron_affine_image (poly, outer_dim, expr, one);
228 ppl_delete_Linear_Expression (expr);
230 mpz_clear (x);
231 ppl_delete_Coefficient (one);
234 /* Project the INNER loop into the iteration domain of the OUTER loop.
235 STRIDE is the number of iterations between two iterations of the
236 outer loop. */
238 static void
239 lst_project_loop (lst_p outer, lst_p inner, mpz_t stride)
241 int i;
242 lst_p stmt;
243 mpz_t x;
244 ppl_Coefficient_t one;
245 int outer_depth = lst_depth (outer);
246 int inner_depth = lst_depth (inner);
248 mpz_init (x);
249 mpz_set_si (x, 1);
250 ppl_new_Coefficient (&one);
251 ppl_assign_Coefficient_from_mpz_t (one, x);
253 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (inner), i, stmt)
255 poly_bb_p pbb = LST_PBB (stmt);
256 ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
257 ppl_dimension_type outer_dim = psct_dynamic_dim (pbb, outer_depth);
258 ppl_dimension_type inner_dim = psct_dynamic_dim (pbb, inner_depth);
259 ppl_Linear_Expression_t expr;
260 ppl_dimension_type dim;
261 ppl_dimension_type *ds;
263 /* There should be no loops under INNER. */
264 gcc_assert (!LST_LOOP_P (stmt));
265 ppl_Polyhedron_space_dimension (poly, &dim);
266 ppl_new_Linear_Expression_with_dimension (&expr, dim);
268 /* outer_dim = outer_dim * stride + inner_dim. */
269 ppl_set_coef (expr, inner_dim, 1);
270 ppl_set_coef_gmp (expr, outer_dim, stride);
271 ppl_Polyhedron_affine_image (poly, outer_dim, expr, one);
272 ppl_delete_Linear_Expression (expr);
274 /* Project on inner_dim. */
275 ppl_new_Linear_Expression_with_dimension (&expr, dim - 1);
276 ppl_Polyhedron_affine_image (poly, inner_dim, expr, one);
277 ppl_delete_Linear_Expression (expr);
279 /* Remove inner loop and the static schedule of its body. */
280 ds = XNEWVEC (ppl_dimension_type, 2);
281 ds[0] = inner_dim;
282 ds[1] = inner_dim + 1;
283 ppl_Polyhedron_remove_space_dimensions (poly, ds, 2);
284 PBB_NB_SCATTERING_TRANSFORM (pbb) -= 2;
285 free (ds);
288 mpz_clear (x);
289 ppl_delete_Coefficient (one);
292 /* Flattens the loop nest LST. Return true when something changed.
293 OFFSET is used to compute the number of iterations of the outermost
294 loop before the current LST is executed. */
296 static bool
297 lst_flatten_loop (lst_p lst, mpz_t init_offset)
299 int i;
300 lst_p l;
301 bool res = false;
302 mpz_t n, one, offset, stride;
304 mpz_init (n);
305 mpz_init (one);
306 mpz_init (offset);
307 mpz_init (stride);
308 mpz_set (offset, init_offset);
309 mpz_set_si (one, 1);
311 lst_linearized_niter (lst, stride);
312 lst_niter_for_loop (lst, n);
313 mpz_tdiv_q (stride, stride, n);
315 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
316 if (LST_LOOP_P (l))
318 res = true;
320 lst_flatten_loop (l, offset);
321 lst_niter_for_loop (l, n);
323 lst_project_loop (lst, l, stride);
325 /* The offset is the number of iterations minus 1, as we want
326 to execute the next statements at the same iteration as the
327 last iteration of the loop. */
328 mpz_sub (n, n, one);
329 mpz_add (offset, offset, n);
331 else
333 lst_scale (lst, l, stride);
334 if (mpz_cmp_si (offset, 0) != 0)
335 lst_offset (l, offset);
338 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
339 if (LST_LOOP_P (l))
340 lst_remove_loop_and_inline_stmts_in_loop_father (l);
342 mpz_clear (n);
343 mpz_clear (one);
344 mpz_clear (offset);
345 mpz_clear (stride);
346 return res;
349 /* Remove all but the first 3 dimensions of the scattering:
350 - dim0: the static schedule for the loop
351 - dim1: the dynamic schedule of the loop
352 - dim2: the static schedule for the loop body. */
354 static void
355 remove_unused_scattering_dimensions (lst_p lst)
357 int i;
358 lst_p stmt;
359 mpz_t x;
360 ppl_Coefficient_t one;
362 mpz_init (x);
363 mpz_set_si (x, 1);
364 ppl_new_Coefficient (&one);
365 ppl_assign_Coefficient_from_mpz_t (one, x);
367 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, stmt)
369 poly_bb_p pbb = LST_PBB (stmt);
370 ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
371 int j, nb_dims_to_remove = PBB_NB_SCATTERING_TRANSFORM (pbb) - 3;
372 ppl_dimension_type *ds;
374 /* There should be no loops inside LST after flattening. */
375 gcc_assert (!LST_LOOP_P (stmt));
377 if (!nb_dims_to_remove)
378 continue;
380 ds = XNEWVEC (ppl_dimension_type, nb_dims_to_remove);
381 for (j = 0; j < nb_dims_to_remove; j++)
382 ds[j] = j + 3;
384 ppl_Polyhedron_remove_space_dimensions (poly, ds, nb_dims_to_remove);
385 PBB_NB_SCATTERING_TRANSFORM (pbb) -= nb_dims_to_remove;
386 free (ds);
389 mpz_clear (x);
390 ppl_delete_Coefficient (one);
393 /* Flattens all the loop nests of LST. Return true when something
394 changed. */
396 static bool
397 lst_do_flatten (lst_p lst)
399 int i;
400 lst_p l;
401 bool res = false;
402 mpz_t zero;
404 if (!lst
405 || !LST_LOOP_P (lst))
406 return false;
408 mpz_init (zero);
409 mpz_set_si (zero, 0);
411 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
412 if (LST_LOOP_P (l))
414 res |= lst_flatten_loop (l, zero);
415 remove_unused_scattering_dimensions (l);
418 lst_update_scattering (lst);
419 mpz_clear (zero);
420 return res;
423 /* Flatten all the loop nests in SCOP. Returns true when something
424 changed. */
426 bool
427 flatten_all_loops (scop_p scop)
429 return lst_do_flatten (SCOP_TRANSFORMED_SCHEDULE (scop));
432 #endif