OSDN Git Service

Fix comments.
[pf3gnuchains/gcc-fork.git] / gcc / graphite-flattening.c
1 /* Loop flattening for Graphite.
2    Copyright (C) 2010 Free Software Foundation, Inc.
3    Contributed by Sebastian Pop <sebastian.pop@amd.com>.
4
5 This file is part of GCC.
6
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.
11
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.
16
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/>.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "ggc.h"
26 #include "tree.h"
27 #include "rtl.h"
28 #include "output.h"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
32 #include "toplev.h"
33 #include "tree-dump.h"
34 #include "timevar.h"
35 #include "cfgloop.h"
36 #include "tree-chrec.h"
37 #include "tree-data-ref.h"
38 #include "tree-scalar-evolution.h"
39 #include "tree-pass.h"
40 #include "domwalk.h"
41 #include "value-prof.h"
42 #include "pointer-set.h"
43 #include "gimple.h"
44 #include "params.h"
45
46 #ifdef HAVE_cloog
47 #include "ppl_c.h"
48 #include "sese.h"
49 #include "graphite-ppl.h"
50 #include "graphite.h"
51 #include "graphite-poly.h"
52
53 /* The loop flattening pass transforms loop nests into a single loop,
54    removing the loop nesting structure.  The auto-vectorization can
55    then apply on the full loop body, without needing the outer-loop
56    vectorization.
57
58    The loop flattening pass that has been described in a very Fortran
59    specific way in the 1992 paper by Reinhard von Hanxleden and Ken
60    Kennedy: "Relaxing SIMD Control Flow Constraints using Loop
61    Transformations" available from
62    http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.5033
63
64    The canonical example is as follows: suppose that we have a loop
65    nest with known iteration counts
66
67    | for (i = 1; i <= 6; i++)
68    |   for (j = 1; j <= 6; j++)
69    |     S1(i,j);
70
71    The loop flattening is performed by linearizing the iteration space
72    using the function "f (x) = 6 * i + j".  In this case, CLooG would
73    produce this code:
74
75    | for (c1=7;c1<=42;c1++) {
76    |   i = floord(c1-1,6);
77    |   S1(i,c1-6*i);
78    | }
79
80    There are several limitations for loop flattening that are linked
81    to the expressivity of the polyhedral model.  One has to take an
82    upper bound approximation to deal with the parametric case of loop
83    flattening.  For example, in the loop nest:
84
85    | for (i = 1; i <= N; i++)
86    |   for (j = 1; j <= M; j++)
87    |     S1(i,j);
88
89    One would like to flatten this loop using a linearization function
90    like this "f (x) = M * i + j".  However CLooG's schedules are not
91    expressive enough to deal with this case, and so the parameter M
92    has to be replaced by an integer upper bound approximation.  If we
93    further know in the context of the scop that "M <= 6", then it is
94    possible to linearize the loop with "f (x) = 6 * i + j".  In this
95    case, CLooG would produce this code:
96
97    | for (c1=7;c1<=6*M+N;c1++) {
98    |   i = ceild(c1-N,6);
99    |   if (i <= floord(c1-1,6)) {
100    |     S1(i,c1-6*i);
101    |   }
102    | }
103
104    For an arbitrarily complex loop nest the algorithm proceeds in two
105    steps.  First, the LST is flattened by removing the loops structure
106    and by inserting the statements in the order they appear in
107    depth-first order.  Then, the scattering of each statement is
108    transformed accordingly.
109
110    Supposing that the original program is represented by the following
111    LST:
112
113    | (loop_1
114    |  stmt_1
115    |  (loop_2 stmt_3
116    |   (loop_3 stmt_4)
117    |   (loop_4 stmt_5 stmt_6)
118    |   stmt_7
119    |  )
120    |  stmt_2
121    | )
122
123    Loop flattening traverses the LST in depth-first order, and
124    flattens pairs of loops successively by projecting the inner loops
125    in the iteration domain of the outer loops:
126
127    lst_project_loop (loop_2, loop_3, stride)
128
129    | (loop_1
130    |  stmt_1
131    |  (loop_2 stmt_3 stmt_4
132    |   (loop_4 stmt_5 stmt_6)
133    |   stmt_7
134    |  )
135    |  stmt_2
136    | )
137
138    lst_project_loop (loop_2, loop_4, stride)
139
140    | (loop_1
141    |  stmt_1
142    |  (loop_2 stmt_3 stmt_4 stmt_5 stmt_6 stmt_7)
143    |  stmt_2
144    | )
145
146    lst_project_loop (loop_1, loop_2, stride)
147
148    | (loop_1
149    |  stmt_1 stmt_3 stmt_4 stmt_5 stmt_6 stmt_7 stmt_2
150    | )
151
152    At each step, the iteration domain of the outer loop is enlarged to
153    contain enough points to iterate over the inner loop domain.  */
154
155 /* Initializes RES to the number of iterations of the linearized loop
156    LST.  RES is the cardinal of the iteration domain of LST.  */
157
158 static void
159 lst_linearized_niter (lst_p lst, mpz_t res)
160 {
161   int i;
162   lst_p l;
163   mpz_t n;
164
165   mpz_init (n);
166   mpz_set_si (res, 0);
167
168   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
169     if (LST_LOOP_P (l))
170       {
171         lst_linearized_niter (l, n);
172         mpz_add (res, res, n);
173       }
174
175   if (LST_LOOP_P (lst))
176     {
177       lst_niter_for_loop (lst, n);
178
179       if (mpz_cmp_si (res, 0) != 0)
180         mpz_mul (res, res, n);
181       else
182         mpz_set (res, n);
183     }
184
185   mpz_clear (n);
186 }
187
188 /* Applies the translation "f (x) = x + OFFSET" to the loop containing
189    STMT.  */
190
191 static void
192 lst_offset (lst_p stmt, mpz_t offset)
193 {
194   lst_p inner = LST_LOOP_FATHER (stmt);
195   poly_bb_p pbb = LST_PBB (stmt);
196   ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
197   int inner_depth = lst_depth (inner);
198   ppl_dimension_type inner_dim = psct_dynamic_dim (pbb, inner_depth);
199   ppl_Linear_Expression_t expr;
200   ppl_dimension_type dim;
201   ppl_Coefficient_t one;
202   mpz_t x;
203
204   mpz_init (x);
205   mpz_set_si (x, 1);
206   ppl_new_Coefficient (&one);
207   ppl_assign_Coefficient_from_mpz_t (one, x);
208
209   ppl_Polyhedron_space_dimension (poly, &dim);
210   ppl_new_Linear_Expression_with_dimension (&expr, dim);
211
212   ppl_set_coef (expr, inner_dim, 1);
213   ppl_set_inhomogeneous_gmp (expr, offset);
214   ppl_Polyhedron_affine_image (poly, inner_dim, expr, one);
215   ppl_delete_Linear_Expression (expr);
216   ppl_delete_Coefficient (one);
217 }
218
219 /* Scale by FACTOR the loop LST containing STMT.  */
220
221 static void
222 lst_scale (lst_p lst, lst_p stmt, mpz_t factor)
223 {
224   mpz_t x;
225   ppl_Coefficient_t one;
226   int outer_depth = lst_depth (lst);
227   poly_bb_p pbb = LST_PBB (stmt);
228   ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
229   ppl_dimension_type outer_dim = psct_dynamic_dim (pbb, outer_depth);
230   ppl_Linear_Expression_t expr;
231   ppl_dimension_type dim;
232
233   mpz_init (x);
234   mpz_set_si (x, 1);
235   ppl_new_Coefficient (&one);
236   ppl_assign_Coefficient_from_mpz_t (one, x);
237
238   ppl_Polyhedron_space_dimension (poly, &dim);
239   ppl_new_Linear_Expression_with_dimension (&expr, dim);
240
241   /* outer_dim = factor * outer_dim.  */
242   ppl_set_coef_gmp (expr, outer_dim, factor);
243   ppl_Polyhedron_affine_image (poly, outer_dim, expr, one);
244   ppl_delete_Linear_Expression (expr);
245
246   mpz_clear (x);
247   ppl_delete_Coefficient (one);
248 }
249
250 /* Project the INNER loop into the iteration domain of the OUTER loop.
251    STRIDE is the number of iterations between two iterations of the
252    outer loop.  */
253
254 static void
255 lst_project_loop (lst_p outer, lst_p inner, mpz_t stride)
256 {
257   int i;
258   lst_p stmt;
259   mpz_t x;
260   ppl_Coefficient_t one;
261   int outer_depth = lst_depth (outer);
262   int inner_depth = lst_depth (inner);
263
264   mpz_init (x);
265   mpz_set_si (x, 1);
266   ppl_new_Coefficient (&one);
267   ppl_assign_Coefficient_from_mpz_t (one, x);
268
269   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (inner), i, stmt)
270     {
271       poly_bb_p pbb = LST_PBB (stmt);
272       ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
273       ppl_dimension_type outer_dim = psct_dynamic_dim (pbb, outer_depth);
274       ppl_dimension_type inner_dim = psct_dynamic_dim (pbb, inner_depth);
275       ppl_Linear_Expression_t expr;
276       ppl_dimension_type dim;
277       ppl_dimension_type *ds;
278
279       /* There should be no loops under INNER.  */
280       gcc_assert (!LST_LOOP_P (stmt));
281       ppl_Polyhedron_space_dimension (poly, &dim);
282       ppl_new_Linear_Expression_with_dimension (&expr, dim);
283
284       /* outer_dim = outer_dim * stride + inner_dim.  */
285       ppl_set_coef (expr, inner_dim, 1);
286       ppl_set_coef_gmp (expr, outer_dim, stride);
287       ppl_Polyhedron_affine_image (poly, outer_dim, expr, one);
288       ppl_delete_Linear_Expression (expr);
289
290       /* Project on inner_dim.  */
291       ppl_new_Linear_Expression_with_dimension (&expr, dim - 1);
292       ppl_Polyhedron_affine_image (poly, inner_dim, expr, one);
293       ppl_delete_Linear_Expression (expr);
294
295       /* Remove inner loop and the static schedule of its body.  */
296       ds = XNEWVEC (ppl_dimension_type, 2);
297       ds[0] = inner_dim;
298       ds[1] = inner_dim + 1;
299       ppl_Polyhedron_remove_space_dimensions (poly, ds, 2);
300       PBB_NB_SCATTERING_TRANSFORM (pbb) -= 2;
301       free (ds);
302     }
303
304   mpz_clear (x);
305   ppl_delete_Coefficient (one);
306 }
307
308 /* Flattens the loop nest LST.  Return true when something changed.
309    OFFSET is used to compute the number of iterations of the outermost
310    loop before the current LST is executed.  */
311
312 static bool
313 lst_flatten_loop (lst_p lst, mpz_t init_offset)
314 {
315   int i;
316   lst_p l;
317   bool res = false;
318   mpz_t n, one, offset, stride;
319
320   mpz_init (n);
321   mpz_init (one);
322   mpz_init (offset);
323   mpz_init (stride);
324   mpz_set (offset, init_offset);
325   mpz_set_si (one, 1);
326
327   lst_linearized_niter (lst, stride);
328   lst_niter_for_loop (lst, n);
329   mpz_tdiv_q (stride, stride, n);
330
331   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
332     if (LST_LOOP_P (l))
333       {
334         res = true;
335
336         lst_flatten_loop (l, offset);
337         lst_niter_for_loop (l, n);
338
339         lst_project_loop (lst, l, stride);
340
341         /* The offset is the number of iterations minus 1, as we want
342            to execute the next statements at the same iteration as the
343            last iteration of the loop.  */
344         mpz_sub (n, n, one);
345         mpz_add (offset, offset, n);
346       }
347     else
348       {
349         lst_scale (lst, l, stride);
350         if (mpz_cmp_si (offset, 0) != 0)
351           lst_offset (l, offset);
352       }
353
354   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
355     if (LST_LOOP_P (l))
356       lst_remove_loop_and_inline_stmts_in_loop_father (l);
357
358   mpz_clear (n);
359   mpz_clear (one);
360   mpz_clear (offset);
361   mpz_clear (stride);
362   return res;
363 }
364
365 /* Remove all but the first 3 dimensions of the scattering:
366    - dim0: the static schedule for the loop
367    - dim1: the dynamic schedule of the loop
368    - dim2: the static schedule for the loop body.  */
369
370 static void
371 remove_unused_scattering_dimensions (lst_p lst)
372 {
373   int i;
374   lst_p stmt;
375   mpz_t x;
376   ppl_Coefficient_t one;
377
378   mpz_init (x);
379   mpz_set_si (x, 1);
380   ppl_new_Coefficient (&one);
381   ppl_assign_Coefficient_from_mpz_t (one, x);
382
383   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, stmt)
384     {
385       poly_bb_p pbb = LST_PBB (stmt);
386       ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
387       int j, nb_dims_to_remove = PBB_NB_SCATTERING_TRANSFORM (pbb) - 3;
388       ppl_dimension_type *ds;
389
390       /* There should be no loops inside LST after flattening.  */
391       gcc_assert (!LST_LOOP_P (stmt));
392
393       if (!nb_dims_to_remove)
394         continue;
395
396       ds = XNEWVEC (ppl_dimension_type, nb_dims_to_remove);
397       for (j = 0; j < nb_dims_to_remove; j++)
398         ds[j] = j + 3;
399
400       ppl_Polyhedron_remove_space_dimensions (poly, ds, nb_dims_to_remove);
401       PBB_NB_SCATTERING_TRANSFORM (pbb) -= nb_dims_to_remove;
402       free (ds);
403     }
404
405   mpz_clear (x);
406   ppl_delete_Coefficient (one);
407 }
408
409 /* Flattens all the loop nests of LST.  Return true when something
410    changed.  */
411
412 static bool
413 lst_do_flatten (lst_p lst)
414 {
415   int i;
416   lst_p l;
417   bool res = false;
418   mpz_t zero;
419
420   if (!lst
421       || !LST_LOOP_P (lst))
422     return false;
423
424   mpz_init (zero);
425   mpz_set_si (zero, 0);
426
427   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
428     if (LST_LOOP_P (l))
429       {
430         res |= lst_flatten_loop (l, zero);
431         remove_unused_scattering_dimensions (l);
432       }
433
434   lst_update_scattering (lst);
435   mpz_clear (zero);
436   return res;
437 }
438
439 /* Flatten all the loop nests in SCOP.  Returns true when something
440    changed.  */
441
442 bool
443 flatten_all_loops (scop_p scop)
444 {
445   return lst_do_flatten (SCOP_TRANSFORMED_SCHEDULE (scop));
446 }
447
448 #endif