1 /* Heuristics and transform for loop blocking and strip mining on
2 polyhedral representation.
4 Copyright (C) 2009-2013 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/>. */
29 #include <isl/union_map.h>
30 #include <isl/constraint.h>
31 #include <cloog/cloog.h>
32 #include <cloog/isl/domain.h>
36 #include "coretypes.h"
37 #include "tree-flow.h"
40 #include "tree-chrec.h"
41 #include "tree-data-ref.h"
45 #include "graphite-poly.h"
48 /* Strip mines with a factor STRIDE the scattering (time) dimension
49 around PBB at depth TIME_DEPTH.
51 The following example comes from the wiki page:
52 http://gcc.gnu.org/wiki/Graphite/Strip_mine
54 The strip mine of a loop with a tile of 64 can be obtained with a
55 scattering function as follows:
57 $ cat ./albert_strip_mine.cloog
61 # parameter {n | n >= 0}
68 1 # Number of statements:
81 1 # Scattering functions
92 #the output of CLooG is like this:
93 #$ cloog ./albert_strip_mine.cloog
94 # for (NEW=0;NEW<=floord(n,64);NEW++) {
95 # for (OLD=max(64*NEW,0);OLD<=min(64*NEW+63,n);OLD++) {
102 pbb_strip_mine_time_depth (poly_bb_p pbb, int time_depth, int stride)
107 /* STRIP is the dimension that iterates with stride STRIDE. */
108 /* ITER is the dimension that enumerates single iterations inside
109 one strip that has at most STRIDE iterations. */
113 pbb->transformed = isl_map_insert_dims (pbb->transformed, isl_dim_out,
116 /* Lower bound of the striped loop. */
117 d = isl_map_get_space (pbb->transformed);
118 c = isl_inequality_alloc (isl_local_space_from_space (d));
119 c = isl_constraint_set_coefficient_si (c, isl_dim_out, strip, -stride);
120 c = isl_constraint_set_coefficient_si (c, isl_dim_out, iter, 1);
121 pbb->transformed = isl_map_add_constraint (pbb->transformed, c);
123 /* Upper bound of the striped loop. */
124 d = isl_map_get_space (pbb->transformed);
125 c = isl_inequality_alloc (isl_local_space_from_space (d));
126 c = isl_constraint_set_coefficient_si (c, isl_dim_out, strip, stride);
127 c = isl_constraint_set_coefficient_si (c, isl_dim_out, iter, -1);
128 c = isl_constraint_set_constant_si (c, stride - 1);
129 pbb->transformed = isl_map_add_constraint (pbb->transformed, c);
131 /* Static scheduling for ITER level.
132 This is mandatory to keep the 2d + 1 canonical scheduling format. */
133 d = isl_map_get_space (pbb->transformed);
134 c = isl_equality_alloc (isl_local_space_from_space (d));
135 c = isl_constraint_set_coefficient_si (c, isl_dim_out, strip + 1, 1);
136 pbb->transformed = isl_map_add_constraint (pbb->transformed, c);
139 /* Returns true when strip mining with STRIDE of the loop LST is
143 lst_strip_mine_profitable_p (lst_p lst, int stride)
145 mpz_t niter, strip_stride;
148 gcc_assert (LST_LOOP_P (lst));
149 mpz_init (strip_stride);
152 mpz_set_si (strip_stride, stride);
153 lst_niter_for_loop (lst, niter);
154 res = (mpz_cmp (niter, strip_stride) > 0);
156 mpz_clear (strip_stride);
161 /* Strip-mines all the loops of LST with STRIDE. Return the number of
162 loops strip-mined. */
165 lst_do_strip_mine_loop (lst_p lst, int depth, int stride)
174 if (LST_LOOP_P (lst))
178 FOR_EACH_VEC_ELT (LST_SEQ (lst), i, l)
179 res += lst_do_strip_mine_loop (l, depth, stride);
185 pbb_strip_mine_time_depth (pbb, psct_dynamic_dim (pbb, depth), stride);
189 /* Strip-mines all the loops of LST with STRIDE. When STRIDE is zero,
190 read the stride from the PARAM_LOOP_BLOCK_TILE_SIZE. Return the
191 number of strip-mined loops.
193 Strip mining transforms a loop
195 | for (i = 0; i < N; i++)
198 into the following loop nest:
200 | for (k = 0; k < N; k += STRIDE)
201 | for (j = 0; j < STRIDE; j++)
206 lst_do_strip_mine (lst_p lst, int stride)
214 stride = PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE);
217 || !LST_LOOP_P (lst))
220 FOR_EACH_VEC_ELT (LST_SEQ (lst), i, l)
221 res += lst_do_strip_mine (l, stride);
223 depth = lst_depth (lst);
225 && lst_strip_mine_profitable_p (lst, stride))
227 res += lst_do_strip_mine_loop (lst, lst_depth (lst), stride);
228 lst_add_loop_under_loop (lst);
234 /* Strip mines all the loops in SCOP. Returns the number of
235 strip-mined loops. */
238 scop_do_strip_mine (scop_p scop, int stride)
240 return lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop), stride);
243 /* Loop blocks all the loops in SCOP. Returns true when we manage to
247 scop_do_block (scop_p scop)
249 store_scattering (scop);
251 /* If we don't strip mine at least two loops, or not interchange
252 loops, the strip mine alone will not be profitable, and the
253 transform is not a loop blocking: so revert the transform. */
254 if (lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop), 0) < 2
255 || scop_do_interchange (scop) == 0)
257 restore_scattering (scop);
261 if (dump_file && (dump_flags & TDF_DETAILS))
262 fprintf (dump_file, "SCoP will be loop blocked.\n");