1 /* Heuristics and transform for loop blocking and strip mining on
2 polyhedral representation.
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>.
8 This file is part of GCC.
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)
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.
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/>. */
27 /* Workaround for GMP 5.1.3 bug, see PR56019. */
32 #include <isl/union_map.h>
33 #include <isl/constraint.h>
37 #include "coretypes.h"
42 #include "hard-reg-set.h"
44 #include "fold-const.h"
45 #include "dominance.h"
46 #include "internal-fn.h"
47 #include "gimple-iterator.h"
48 #include "tree-ssa-loop.h"
51 #include "tree-chrec.h"
52 #include "tree-data-ref.h"
56 #include "graphite-poly.h"
59 /* Strip mines with a factor STRIDE the scattering (time) dimension
60 around PBB at depth TIME_DEPTH.
62 The following example comes from the wiki page:
63 http://gcc.gnu.org/wiki/Graphite/Strip_mine
65 The strip mine of a loop with a tile of 64 can be obtained with a
66 scattering function as follows:
68 $ cat ./albert_strip_mine.cloog
72 # parameter {n | n >= 0}
79 1 # Number of statements:
92 1 # Scattering functions
103 #the output of CLooG is like this:
104 #$ cloog ./albert_strip_mine.cloog
105 # for (NEW=0;NEW<=floord(n,64);NEW++) {
106 # for (OLD=max(64*NEW,0);OLD<=min(64*NEW+63,n);OLD++) {
113 pbb_strip_mine_time_depth (poly_bb_p pbb
, int time_depth
, int stride
)
118 /* STRIP is the dimension that iterates with stride STRIDE. */
119 /* ITER is the dimension that enumerates single iterations inside
120 one strip that has at most STRIDE iterations. */
124 pbb
->transformed
= isl_map_insert_dims (pbb
->transformed
, isl_dim_out
,
127 /* Lower bound of the striped loop. */
128 d
= isl_map_get_space (pbb
->transformed
);
129 c
= isl_inequality_alloc (isl_local_space_from_space (d
));
130 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, strip
, -stride
);
131 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, iter
, 1);
132 pbb
->transformed
= isl_map_add_constraint (pbb
->transformed
, c
);
134 /* Upper bound of the striped loop. */
135 d
= isl_map_get_space (pbb
->transformed
);
136 c
= isl_inequality_alloc (isl_local_space_from_space (d
));
137 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, strip
, stride
);
138 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, iter
, -1);
139 c
= isl_constraint_set_constant_si (c
, stride
- 1);
140 pbb
->transformed
= isl_map_add_constraint (pbb
->transformed
, c
);
142 /* Static scheduling for ITER level.
143 This is mandatory to keep the 2d + 1 canonical scheduling format. */
144 d
= isl_map_get_space (pbb
->transformed
);
145 c
= isl_equality_alloc (isl_local_space_from_space (d
));
146 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, strip
+ 1, 1);
147 pbb
->transformed
= isl_map_add_constraint (pbb
->transformed
, c
);
150 /* Returns true when strip mining with STRIDE of the loop LST is
154 lst_strip_mine_profitable_p (lst_p lst
, int stride
)
156 mpz_t niter
, strip_stride
;
159 gcc_assert (LST_LOOP_P (lst
));
160 mpz_init (strip_stride
);
163 mpz_set_si (strip_stride
, stride
);
164 lst_niter_for_loop (lst
, niter
);
165 res
= (mpz_cmp (niter
, strip_stride
) > 0);
167 mpz_clear (strip_stride
);
172 /* Strip-mines all the loops of LST with STRIDE. Return the number of
173 loops strip-mined. */
176 lst_do_strip_mine_loop (lst_p lst
, int depth
, int stride
)
185 if (LST_LOOP_P (lst
))
189 FOR_EACH_VEC_ELT (LST_SEQ (lst
), i
, l
)
190 res
+= lst_do_strip_mine_loop (l
, depth
, stride
);
196 pbb_strip_mine_time_depth (pbb
, psct_dynamic_dim (pbb
, depth
), stride
);
200 /* Strip-mines all the loops of LST with STRIDE. When STRIDE is zero,
201 read the stride from the PARAM_LOOP_BLOCK_TILE_SIZE. Return the
202 number of strip-mined loops.
204 Strip mining transforms a loop
206 | for (i = 0; i < N; i++)
209 into the following loop nest:
211 | for (k = 0; k < N; k += STRIDE)
212 | for (j = 0; j < STRIDE; j++)
217 lst_do_strip_mine (lst_p lst
, int stride
)
225 stride
= PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE
);
228 || !LST_LOOP_P (lst
))
231 FOR_EACH_VEC_ELT (LST_SEQ (lst
), i
, l
)
232 res
+= lst_do_strip_mine (l
, stride
);
234 depth
= lst_depth (lst
);
236 && lst_strip_mine_profitable_p (lst
, stride
))
238 res
+= lst_do_strip_mine_loop (lst
, lst_depth (lst
), stride
);
239 lst_add_loop_under_loop (lst
);
245 /* Strip mines all the loops in SCOP. Returns the number of
246 strip-mined loops. */
249 scop_do_strip_mine (scop_p scop
, int stride
)
251 return lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop
), stride
);
254 /* Loop blocks all the loops in SCOP. Returns true when we manage to
258 scop_do_block (scop_p scop
)
260 store_scattering (scop
);
262 /* If we don't strip mine at least two loops, or not interchange
263 loops, the strip mine alone will not be profitable, and the
264 transform is not a loop blocking: so revert the transform. */
265 if (lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop
), 0) < 2
266 || scop_do_interchange (scop
) == 0)
268 restore_scattering (scop
);
272 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
273 fprintf (dump_file
, "SCoP will be loop blocked.\n");