Merge branch 'vendor/GCC50' - gcc 5.0 snapshot 1 FEB 2015
[dragonfly.git] / contrib / gcc-5.0 / gcc / graphite-blocking.c
1 /* Heuristics and transform for loop blocking and strip mining on
2    polyhedral representation.
3
4    Copyright (C) 2009-2015 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
24 #include "config.h"
25
26 #ifdef HAVE_isl
27 #include <isl/set.h>
28 #include <isl/map.h>
29 #include <isl/union_map.h>
30 #include <isl/constraint.h>
31 #endif
32
33 #include "system.h"
34 #include "coretypes.h"
35 #include "hash-set.h"
36 #include "machmode.h"
37 #include "vec.h"
38 #include "double-int.h"
39 #include "input.h"
40 #include "alias.h"
41 #include "symtab.h"
42 #include "options.h"
43 #include "wide-int.h"
44 #include "inchash.h"
45 #include "tree.h"
46 #include "fold-const.h"
47 #include "predict.h"
48 #include "tm.h"
49 #include "hard-reg-set.h"
50 #include "input.h"
51 #include "function.h"
52 #include "dominance.h"
53 #include "basic-block.h"
54 #include "tree-ssa-alias.h"
55 #include "internal-fn.h"
56 #include "gimple-expr.h"
57 #include "is-a.h"
58 #include "gimple.h"
59 #include "gimple-iterator.h"
60 #include "tree-ssa-loop.h"
61 #include "dumpfile.h"
62 #include "cfgloop.h"
63 #include "tree-chrec.h"
64 #include "tree-data-ref.h"
65 #include "sese.h"
66
67 #ifdef HAVE_isl
68 #include "graphite-poly.h"
69
70
71 /* Strip mines with a factor STRIDE the scattering (time) dimension
72    around PBB at depth TIME_DEPTH.
73
74    The following example comes from the wiki page:
75    http://gcc.gnu.org/wiki/Graphite/Strip_mine
76
77    The strip mine of a loop with a tile of 64 can be obtained with a
78    scattering function as follows:
79
80    $ cat ./albert_strip_mine.cloog
81    # language: C
82    c
83
84    # parameter {n | n >= 0}
85    1 3
86    #  n  1
87    1  1  0
88    1
89    n
90
91    1 # Number of statements:
92
93    1
94    # {i | 0 <= i <= n}
95    2 4
96    #  i  n   1
97    1  1  0   0
98    1 -1  1   0
99
100    0  0  0
101    1
102    i
103
104    1 # Scattering functions
105
106    3 6
107    #  NEW  OLD    i    n    1
108    1  -64    0    1    0    0
109    1   64    0   -1    0   63
110    0    0    1   -1    0    0
111
112    1
113    NEW  OLD
114
115    #the output of CLooG is like this:
116    #$ cloog ./albert_strip_mine.cloog
117    # for (NEW=0;NEW<=floord(n,64);NEW++) {
118    #   for (OLD=max(64*NEW,0);OLD<=min(64*NEW+63,n);OLD++) {
119    #     S1(i = OLD) ;
120    #   }
121    # }
122 */
123
124 static void
125 pbb_strip_mine_time_depth (poly_bb_p pbb, int time_depth, int stride)
126 {
127   isl_space *d;
128   isl_constraint *c;
129   int iter, strip;
130   /* STRIP is the dimension that iterates with stride STRIDE.  */
131   /* ITER is the dimension that enumerates single iterations inside
132      one strip that has at most STRIDE iterations.  */
133   strip = time_depth;
134   iter = strip + 2;
135
136   pbb->transformed = isl_map_insert_dims (pbb->transformed, isl_dim_out,
137                                           strip, 2);
138
139   /* Lower bound of the striped loop.  */
140   d = isl_map_get_space (pbb->transformed);
141   c = isl_inequality_alloc (isl_local_space_from_space (d));
142   c = isl_constraint_set_coefficient_si (c, isl_dim_out, strip, -stride);
143   c = isl_constraint_set_coefficient_si (c, isl_dim_out, iter, 1);
144   pbb->transformed = isl_map_add_constraint (pbb->transformed, c);
145
146   /* Upper bound of the striped loop.  */
147   d = isl_map_get_space (pbb->transformed);
148   c = isl_inequality_alloc (isl_local_space_from_space (d));
149   c = isl_constraint_set_coefficient_si (c, isl_dim_out, strip, stride);
150   c = isl_constraint_set_coefficient_si (c, isl_dim_out, iter, -1);
151   c = isl_constraint_set_constant_si (c, stride - 1);
152   pbb->transformed = isl_map_add_constraint (pbb->transformed, c);
153
154   /* Static scheduling for ITER level.
155      This is mandatory to keep the 2d + 1 canonical scheduling format.  */
156   d = isl_map_get_space (pbb->transformed);
157   c = isl_equality_alloc (isl_local_space_from_space (d));
158   c = isl_constraint_set_coefficient_si (c, isl_dim_out, strip + 1, 1);
159   pbb->transformed = isl_map_add_constraint (pbb->transformed, c);
160 }
161
162 /* Returns true when strip mining with STRIDE of the loop LST is
163    profitable.  */
164
165 static bool
166 lst_strip_mine_profitable_p (lst_p lst, int stride)
167 {
168   mpz_t niter, strip_stride;
169   bool res;
170
171   gcc_assert (LST_LOOP_P (lst));
172   mpz_init (strip_stride);
173   mpz_init (niter);
174
175   mpz_set_si (strip_stride, stride);
176   lst_niter_for_loop (lst, niter);
177   res = (mpz_cmp (niter, strip_stride) > 0);
178
179   mpz_clear (strip_stride);
180   mpz_clear (niter);
181   return res;
182 }
183
184 /* Strip-mines all the loops of LST with STRIDE.  Return the number of
185    loops strip-mined.  */
186
187 static int
188 lst_do_strip_mine_loop (lst_p lst, int depth, int stride)
189 {
190   int i;
191   lst_p l;
192   poly_bb_p pbb;
193
194   if (!lst)
195     return 0;
196
197   if (LST_LOOP_P (lst))
198     {
199       int res = 0;
200
201       FOR_EACH_VEC_ELT (LST_SEQ (lst), i, l)
202         res += lst_do_strip_mine_loop (l, depth, stride);
203
204       return res;
205     }
206
207   pbb = LST_PBB (lst);
208   pbb_strip_mine_time_depth (pbb, psct_dynamic_dim (pbb, depth), stride);
209   return 1;
210 }
211
212 /* Strip-mines all the loops of LST with STRIDE.  When STRIDE is zero,
213    read the stride from the PARAM_LOOP_BLOCK_TILE_SIZE.  Return the
214    number of strip-mined loops.
215
216    Strip mining transforms a loop
217
218    | for (i = 0; i < N; i++)
219    |   S (i);
220
221    into the following loop nest:
222
223    | for (k = 0; k < N; k += STRIDE)
224    |   for (j = 0; j < STRIDE; j++)
225    |     S (i = k + j);
226 */
227
228 static int
229 lst_do_strip_mine (lst_p lst, int stride)
230 {
231   int i;
232   lst_p l;
233   int res = 0;
234   int depth;
235
236   if (!stride)
237     stride = PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE);
238
239   if (!lst
240       || !LST_LOOP_P (lst))
241     return false;
242
243   FOR_EACH_VEC_ELT (LST_SEQ (lst), i, l)
244     res += lst_do_strip_mine (l, stride);
245
246   depth = lst_depth (lst);
247   if (depth >= 0
248       && lst_strip_mine_profitable_p (lst, stride))
249     {
250       res += lst_do_strip_mine_loop (lst, lst_depth (lst), stride);
251       lst_add_loop_under_loop (lst);
252     }
253
254   return res;
255 }
256
257 /* Strip mines all the loops in SCOP.  Returns the number of
258    strip-mined loops.  */
259
260 int
261 scop_do_strip_mine (scop_p scop, int stride)
262 {
263   return lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop), stride);
264 }
265
266 /* Loop blocks all the loops in SCOP.  Returns true when we manage to
267    block some loops.  */
268
269 bool
270 scop_do_block (scop_p scop)
271 {
272   store_scattering (scop);
273
274   /* If we don't strip mine at least two loops, or not interchange
275      loops, the strip mine alone will not be profitable, and the
276      transform is not a loop blocking: so revert the transform.  */
277   if (lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop), 0) < 2
278       || scop_do_interchange (scop) == 0)
279     {
280       restore_scattering (scop);
281       return false;
282     }
283
284   if (dump_file && (dump_flags & TDF_DETAILS))
285     fprintf (dump_file, "SCoP will be loop blocked.\n");
286
287   return true;
288 }
289
290 #endif