OSDN Git Service

2009-11-18 Sebastian Pop <sebastian.pop@amd.com>
[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 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 "toplev.h"
35 #include "tree-dump.h"
36 #include "timevar.h"
37 #include "cfgloop.h"
38 #include "tree-chrec.h"
39 #include "tree-data-ref.h"
40 #include "tree-scalar-evolution.h"
41 #include "tree-pass.h"
42 #include "domwalk.h"
43 #include "value-prof.h"
44 #include "pointer-set.h"
45 #include "gimple.h"
46 #include "params.h"
47
48 #ifdef HAVE_cloog
49 #include "cloog/cloog.h"
50 #include "ppl_c.h"
51 #include "sese.h"
52 #include "graphite-ppl.h"
53 #include "graphite.h"
54 #include "graphite-poly.h"
55
56
57 /* Strip mines with a factor STRIDE the scattering (time) dimension
58    around PBB at depth TIME_DEPTH.
59
60    The following example comes from the wiki page:
61    http://gcc.gnu.org/wiki/Graphite/Strip_mine
62
63    The strip mine of a loop with a tile of 64 can be obtained with a
64    scattering function as follows:
65
66    $ cat ./albert_strip_mine.cloog
67    # language: C
68    c
69
70    # parameter {n | n >= 0}
71    1 3
72    #  n  1
73    1  1  0
74    1
75    n
76
77    1 # Number of statements:
78
79    1
80    # {i | 0 <= i <= n}
81    2 4
82    #  i  n   1
83    1  1  0   0
84    1 -1  1   0
85
86    0  0  0
87    1
88    i
89
90    1 # Scattering functions
91
92    3 6
93    #  NEW  OLD    i    n    1
94    1  -64    0    1    0    0
95    1   64    0   -1    0   63
96    0    0    1   -1    0    0
97
98    1
99    NEW  OLD
100
101    #the output of CLooG is like this:
102    #$ cloog ./albert_strip_mine.cloog
103    # for (NEW=0;NEW<=floord(n,64);NEW++) {
104    #   for (OLD=max(64*NEW,0);OLD<=min(64*NEW+63,n);OLD++) {
105    #     S1(i = OLD) ;
106    #   }
107    # }
108 */
109
110 static bool
111 pbb_strip_mine_time_depth (poly_bb_p pbb, int time_depth, int stride)
112 {
113   ppl_dimension_type iter, dim, strip;
114   ppl_Polyhedron_t res = PBB_TRANSFORMED_SCATTERING (pbb);
115   /* STRIP is the dimension that iterates with stride STRIDE.  */
116   /* ITER is the dimension that enumerates single iterations inside
117      one strip that has at most STRIDE iterations.  */
118   strip = time_depth;
119   iter = strip + 2;
120
121   psct_add_scattering_dimension (pbb, strip);
122   psct_add_scattering_dimension (pbb, strip + 1);
123
124   ppl_Polyhedron_space_dimension (res, &dim);
125
126   /* Lower bound of the striped loop.  */
127   {
128     ppl_Constraint_t new_cstr;
129     ppl_Linear_Expression_t expr;
130
131     ppl_new_Linear_Expression_with_dimension (&expr, dim);
132     ppl_set_coef (expr, strip, -1 * stride);
133     ppl_set_coef (expr, iter, 1);
134
135     ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
136     ppl_delete_Linear_Expression (expr);
137     ppl_Polyhedron_add_constraint (res, new_cstr);
138     ppl_delete_Constraint (new_cstr);
139   }
140
141   /* Upper bound of the striped loop.  */
142   {
143     ppl_Constraint_t new_cstr;
144     ppl_Linear_Expression_t expr;
145
146     ppl_new_Linear_Expression_with_dimension (&expr, dim);
147     ppl_set_coef (expr, strip, stride);
148     ppl_set_coef (expr, iter, -1);
149     ppl_set_inhomogeneous (expr, stride - 1);
150
151     ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
152     ppl_delete_Linear_Expression (expr);
153     ppl_Polyhedron_add_constraint (res, new_cstr);
154     ppl_delete_Constraint (new_cstr);
155   }
156
157   /* Static scheduling for ITER level.
158      This is mandatory to keep the 2d + 1 canonical scheduling format.  */
159   {
160     ppl_Constraint_t new_cstr;
161     ppl_Linear_Expression_t expr;
162
163     ppl_new_Linear_Expression_with_dimension (&expr, dim);
164     ppl_set_coef (expr, strip + 1, 1);
165     ppl_set_inhomogeneous (expr, 0);
166
167     ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
168     ppl_delete_Linear_Expression (expr);
169     ppl_Polyhedron_add_constraint (res, new_cstr);
170     ppl_delete_Constraint (new_cstr);
171   }
172
173   return true;
174 }
175
176 /* Returns true when strip mining with STRIDE of the loop around PBB
177    at DEPTH is profitable.  */
178
179 static bool
180 pbb_strip_mine_profitable_p (poly_bb_p pbb,
181                              graphite_dim_t depth,
182                              int stride)
183 {
184   Value niter, strip_stride;
185   bool res;
186
187   value_init (strip_stride);
188   value_init (niter);
189   value_set_si (strip_stride, stride);
190   pbb_number_of_iterations_at_time (pbb, psct_dynamic_dim (pbb, depth), niter);
191   res = value_gt (niter, strip_stride);
192   value_clear (strip_stride);
193   value_clear (niter);
194
195   return res;
196 }
197
198 /* Strip-mines all the loops of LST that are considered profitable to
199    strip-mine.  Return true if it did strip-mined some loops.  */
200
201 static bool
202 lst_do_strip_mine_loop (lst_p lst, int depth)
203 {
204   int i;
205   lst_p l;
206   int stride = PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE);
207   poly_bb_p pbb;
208
209   if (!lst)
210     return false;
211
212   if (LST_LOOP_P (lst))
213     {
214       bool res = false;
215
216       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
217         res |= lst_do_strip_mine_loop (l, depth);
218
219       return res;
220     }
221
222   pbb = LST_PBB (lst);
223   return pbb_strip_mine_time_depth (pbb, psct_dynamic_dim (pbb, depth),
224                                     stride);
225 }
226
227 /* Strip-mines all the loops of LST that are considered profitable to
228    strip-mine.  Return true if it did strip-mined some loops.  */
229
230 static bool
231 lst_do_strip_mine (lst_p lst)
232 {
233   int i;
234   lst_p l;
235   bool res = false;
236   int stride = PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE);
237   int depth;
238
239   if (!lst
240       || !LST_LOOP_P (lst))
241     return false;
242
243   for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
244     res |= lst_do_strip_mine (l);
245
246   depth = lst_depth (lst);
247   if (depth >= 0
248       && pbb_strip_mine_profitable_p (LST_PBB (lst_find_first_pbb (lst)),
249                                       depth, stride))
250     {
251       res |= lst_do_strip_mine_loop (lst, lst_depth (lst));
252       lst_add_loop_under_loop (lst);
253     }
254
255   return res;
256 }
257
258
259 /* Strip mines all the loops in SCOP.  Nothing profitable in all this:
260    this is just a driver function.  */
261
262 bool
263 scop_do_strip_mine (scop_p scop)
264 {
265   bool transform_done = false;
266
267   store_scattering (scop);
268
269   transform_done = lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop));
270
271   if (!transform_done)
272     return false;
273
274   if (!graphite_legal_transform (scop))
275     {
276       restore_scattering (scop);
277       return false;
278     }
279
280   return transform_done;
281 }
282
283 #endif