OSDN Git Service

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