OSDN Git Service

Add a stride parameter to scop_do_strip_mine.
[pf3gnuchains/gcc-fork.git] / gcc / graphite-blocking.c
1 /* Heuristics and transform for loop blocking and strip mining on
2    polyhedral representation.
3
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>.
7
8 This file is part of GCC.
9
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.
14
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.
19
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 "tm.h"
27 #include "ggc.h"
28 #include "tree.h"
29 #include "rtl.h"
30 #include "output.h"
31 #include "basic-block.h"
32 #include "diagnostic.h"
33 #include "tree-flow.h"
34 #include "tree-dump.h"
35 #include "timevar.h"
36 #include "cfgloop.h"
37 #include "tree-chrec.h"
38 #include "tree-data-ref.h"
39 #include "tree-scalar-evolution.h"
40 #include "tree-pass.h"
41 #include "domwalk.h"
42 #include "value-prof.h"
43 #include "pointer-set.h"
44 #include "gimple.h"
45 #include "params.h"
46
47 #ifdef HAVE_cloog
48 #include "ppl_c.h"
49 #include "sese.h"
50 #include "graphite-ppl.h"
51 #include "graphite.h"
52 #include "graphite-poly.h"
53
54
55 /* Strip mines with a factor STRIDE the scattering (time) dimension
56    around PBB at depth TIME_DEPTH.
57
58    The following example comes from the wiki page:
59    http://gcc.gnu.org/wiki/Graphite/Strip_mine
60
61    The strip mine of a loop with a tile of 64 can be obtained with a
62    scattering function as follows:
63
64    $ cat ./albert_strip_mine.cloog
65    # language: C
66    c
67
68    # parameter {n | n >= 0}
69    1 3
70    #  n  1
71    1  1  0
72    1
73    n
74
75    1 # Number of statements:
76
77    1
78    # {i | 0 <= i <= n}
79    2 4
80    #  i  n   1
81    1  1  0   0
82    1 -1  1   0
83
84    0  0  0
85    1
86    i
87
88    1 # Scattering functions
89
90    3 6
91    #  NEW  OLD    i    n    1
92    1  -64    0    1    0    0
93    1   64    0   -1    0   63
94    0    0    1   -1    0    0
95
96    1
97    NEW  OLD
98
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++) {
103    #     S1(i = OLD) ;
104    #   }
105    # }
106 */
107
108 static bool
109 pbb_strip_mine_time_depth (poly_bb_p pbb, int time_depth, int stride)
110 {
111   ppl_dimension_type iter, dim, strip;
112   ppl_Polyhedron_t res = PBB_TRANSFORMED_SCATTERING (pbb);
113   /* STRIP is the dimension that iterates with stride STRIDE.  */
114   /* ITER is the dimension that enumerates single iterations inside
115      one strip that has at most STRIDE iterations.  */
116   strip = time_depth;
117   iter = strip + 2;
118
119   psct_add_scattering_dimension (pbb, strip);
120   psct_add_scattering_dimension (pbb, strip + 1);
121
122   ppl_Polyhedron_space_dimension (res, &dim);
123
124   /* Lower bound of the striped loop.  */
125   {
126     ppl_Constraint_t new_cstr;
127     ppl_Linear_Expression_t expr;
128
129     ppl_new_Linear_Expression_with_dimension (&expr, dim);
130     ppl_set_coef (expr, strip, -1 * stride);
131     ppl_set_coef (expr, iter, 1);
132
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);
137   }
138
139   /* Upper bound of the striped loop.  */
140   {
141     ppl_Constraint_t new_cstr;
142     ppl_Linear_Expression_t expr;
143
144     ppl_new_Linear_Expression_with_dimension (&expr, dim);
145     ppl_set_coef (expr, strip, stride);
146     ppl_set_coef (expr, iter, -1);
147     ppl_set_inhomogeneous (expr, stride - 1);
148
149     ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
150     ppl_delete_Linear_Expression (expr);
151     ppl_Polyhedron_add_constraint (res, new_cstr);
152     ppl_delete_Constraint (new_cstr);
153   }
154
155   /* Static scheduling for ITER level.
156      This is mandatory to keep the 2d + 1 canonical scheduling format.  */
157   {
158     ppl_Constraint_t new_cstr;
159     ppl_Linear_Expression_t expr;
160
161     ppl_new_Linear_Expression_with_dimension (&expr, dim);
162     ppl_set_coef (expr, strip + 1, 1);
163     ppl_set_inhomogeneous (expr, 0);
164
165     ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
166     ppl_delete_Linear_Expression (expr);
167     ppl_Polyhedron_add_constraint (res, new_cstr);
168     ppl_delete_Constraint (new_cstr);
169   }
170
171   return true;
172 }
173
174 /* Returns true when strip mining with STRIDE of the loop LST is
175    profitable.  */
176
177 static bool
178 lst_strip_mine_profitable_p (lst_p lst, int stride)
179 {
180   mpz_t niter, strip_stride;
181   bool res;
182
183   gcc_assert (LST_LOOP_P (lst));
184   mpz_init (strip_stride);
185   mpz_init (niter);
186
187   mpz_set_si (strip_stride, stride);
188   lst_niter_for_loop (lst, niter);
189   res = (mpz_cmp (niter, strip_stride) > 0);
190
191   mpz_clear (strip_stride);
192   mpz_clear (niter);
193   return res;
194 }
195
196 /* Strip-mines all the loops of LST with STRIDE.  Return true if it
197    did strip-mined some loops.  */
198
199 static bool
200 lst_do_strip_mine_loop (lst_p lst, int depth, int stride)
201 {
202   int i;
203   lst_p l;
204   poly_bb_p pbb;
205
206   if (!lst)
207     return false;
208
209   if (LST_LOOP_P (lst))
210     {
211       bool res = false;
212
213       FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
214         res |= lst_do_strip_mine_loop (l, depth, stride);
215
216       return res;
217     }
218
219   pbb = LST_PBB (lst);
220   return pbb_strip_mine_time_depth (pbb, psct_dynamic_dim (pbb, depth),
221                                     stride);
222 }
223
224 /* Strip-mines all the loops of LST with STRIDE.  When STRIDE is zero,
225    read the stride from the PARAM_LOOP_BLOCK_TILE_SIZE.  Return true
226    if it did strip-mined some loops.
227
228    Strip mining transforms a loop
229
230    | for (i = 0; i < N; i++)
231    |   S (i);
232
233    into the following loop nest:
234
235    | for (k = 0; k < N; k += STRIDE)
236    |   for (j = 0; j < STRIDE; j++)
237    |     S (i = k + j);
238 */
239
240 static bool
241 lst_do_strip_mine (lst_p lst, int stride)
242 {
243   int i;
244   lst_p l;
245   bool res = false;
246   int depth;
247
248   if (!stride)
249     stride = PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE);
250
251   if (!lst
252       || !LST_LOOP_P (lst))
253     return false;
254
255   FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
256     res |= lst_do_strip_mine (l, stride);
257
258   depth = lst_depth (lst);
259   if (depth >= 0
260       && lst_strip_mine_profitable_p (lst, stride))
261     {
262       res |= lst_do_strip_mine_loop (lst, lst_depth (lst), stride);
263       lst_add_loop_under_loop (lst);
264     }
265
266   return res;
267 }
268
269 /* Strip mines all the loops in SCOP.  Returns true when some loops
270    have been strip-mined.  */
271
272 bool
273 scop_do_strip_mine (scop_p scop, int stride)
274 {
275   return lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop), stride);
276 }
277
278 /* Loop blocks all the loops in SCOP.  Returns true when we manage to
279    block some loops.  */
280
281 bool
282 scop_do_block (scop_p scop)
283 {
284   bool strip_mined = false;
285   bool interchanged = false;
286
287   store_scattering (scop);
288
289   strip_mined = lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop), 0);
290   interchanged = scop_do_interchange (scop);
291
292   /* If we don't interchange loops, the strip mine alone will not be
293      profitable, and the transform is not a loop blocking: so revert
294      the transform.  */
295   if (!interchanged)
296     {
297       restore_scattering (scop);
298       return false;
299     }
300   else if (strip_mined && interchanged
301            && dump_file && (dump_flags & TDF_DETAILS))
302     fprintf (dump_file, "SCoP will be loop blocked.\n");
303
304   return strip_mined || interchanged;
305 }
306
307 #endif