1 /* Interchange heuristics and transform for loop interchange on
2 polyhedral representation.
4 Copyright (C) 2009 Free Software Foundation, Inc.
5 Contributed by Sebastian Pop <sebastian.pop@amd.com> and
6 Harsha Jagasia <harsha.jagasia@amd.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/>. */
25 #include "coretypes.h"
31 #include "basic-block.h"
32 #include "diagnostic.h"
33 #include "tree-flow.h"
35 #include "tree-dump.h"
38 #include "tree-chrec.h"
39 #include "tree-data-ref.h"
40 #include "tree-scalar-evolution.h"
41 #include "tree-pass.h"
43 #include "value-prof.h"
44 #include "pointer-set.h"
49 #include "cloog/cloog.h"
52 #include "graphite-ppl.h"
54 #include "graphite-poly.h"
56 /* Returns the subscript dimension defined by CSTR in PDR. */
58 static ppl_dimension_type
59 compute_subscript (poly_dr_p pdr, ppl_const_Constraint_t cstr)
62 ppl_Linear_Expression_t expr;
63 ppl_Coefficient_t coef;
67 ppl_new_Coefficient (&coef);
69 for (i = 0; i < pdr_nb_subscripts (pdr); i++)
71 ppl_dimension_type sub_dim = pdr_subscript_dim (pdr, i);
73 ppl_new_Linear_Expression_from_Constraint (&expr, cstr);
74 ppl_Linear_Expression_coefficient (expr, sub_dim, coef);
75 ppl_delete_Linear_Expression (expr);
76 ppl_Coefficient_to_mpz_t (coef, val);
78 if (value_notzero_p (val))
80 gcc_assert (value_one_p (val)
81 || value_mone_p (val));
84 ppl_delete_Coefficient (coef);
94 compute_array_size_cstr (ppl_dimension_type sub_dim, Value res,
95 ppl_const_Constraint_t cstr)
97 ppl_Linear_Expression_t expr;
98 ppl_Coefficient_t coef;
102 ppl_new_Coefficient (&coef);
103 ppl_new_Linear_Expression_from_Constraint (&expr, cstr);
104 ppl_Linear_Expression_coefficient (expr, sub_dim, coef);
105 ppl_Coefficient_to_mpz_t (coef, val);
107 value_set_si (res, 0);
109 if (value_notzero_p (val))
111 gcc_assert (value_one_p (val) || value_mone_p (val));
112 ppl_Linear_Expression_inhomogeneous_term (expr, coef);
113 ppl_Coefficient_to_mpz_t (coef, res);
114 value_absolute (res, res);
118 ppl_delete_Coefficient (coef);
119 ppl_delete_Linear_Expression (expr);
122 /* Returns in ARRAY_SIZE the size in bytes of the array PDR for the
123 subscript at dimension SUB_DIM. */
126 compute_array_size_poly (poly_dr_p pdr, ppl_dimension_type sub_dim, Value array_size,
127 ppl_const_Polyhedron_t ph)
129 ppl_const_Constraint_System_t pcs;
130 ppl_Constraint_System_const_iterator_t cit, cend;
131 ppl_const_Constraint_t cstr;
135 if (sub_dim >= pdr_subscript_dim (pdr, pdr_nb_subscripts (pdr)))
137 value_set_si (array_size, 1);
144 value_set_si (res, 0);
146 ppl_Polyhedron_get_constraints (ph, &pcs);
147 ppl_new_Constraint_System_const_iterator (&cit);
148 ppl_new_Constraint_System_const_iterator (&cend);
150 for (ppl_Constraint_System_begin (pcs, cit),
151 ppl_Constraint_System_end (pcs, cend);
152 !ppl_Constraint_System_const_iterator_equal_test (cit, cend);
153 ppl_Constraint_System_const_iterator_increment (cit))
155 ppl_Constraint_System_const_iterator_dereference (cit, &cstr);
157 if (ppl_Constraint_type (cstr) == PPL_CONSTRAINT_TYPE_EQUAL)
160 compute_array_size_cstr (sub_dim, val, cstr);
161 value_max (res, res, val);
164 compute_array_size_poly (pdr, sub_dim + 1, val, ph);
165 value_multiply (array_size, res, val);
171 /* Initializes ARRAY_SIZE, the size in bytes of the array for the
172 subscript at dimension SUB_DIM in PDR. */
175 compute_array_size (poly_dr_p pdr, ppl_dimension_type sub_dim, Value array_size)
177 ppl_Pointset_Powerset_C_Polyhedron_t data_container = PDR_ACCESSES (pdr);
178 ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end;
181 value_set_si (array_size, 1);
182 if (sub_dim >= pdr_subscript_dim (pdr, pdr_nb_subscripts (pdr)))
186 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it);
187 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end);
189 for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (data_container, it),
190 ppl_Pointset_Powerset_C_Polyhedron_iterator_end (data_container, end);
191 !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end);
192 ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it))
194 ppl_const_Polyhedron_t ph;
196 ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph);
197 compute_array_size_poly (pdr, sub_dim, val, ph);
198 value_max (array_size, array_size, val);
202 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it);
203 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end);
206 /* Computes ACCESS_STRIDES, the sum of all the strides of PDR at
210 gather_access_strides_poly (poly_dr_p pdr, ppl_const_Polyhedron_t ph,
211 ppl_dimension_type loop_dim, Value res)
213 ppl_const_Constraint_System_t pcs;
214 ppl_Constraint_System_const_iterator_t cit, cend;
215 ppl_const_Constraint_t cstr;
216 ppl_Linear_Expression_t expr;
217 ppl_Coefficient_t coef;
221 value_init (array_size);
223 ppl_new_Coefficient (&coef);
224 value_set_si (res, 0);
226 ppl_Polyhedron_get_constraints (ph, &pcs);
227 ppl_new_Constraint_System_const_iterator (&cit);
228 ppl_new_Constraint_System_const_iterator (&cend);
230 for (ppl_Constraint_System_begin (pcs, cit),
231 ppl_Constraint_System_end (pcs, cend);
232 !ppl_Constraint_System_const_iterator_equal_test (cit, cend);
233 ppl_Constraint_System_const_iterator_increment (cit))
235 ppl_Constraint_System_const_iterator_dereference (cit, &cstr);
236 ppl_new_Linear_Expression_from_Constraint (&expr, cstr);
237 ppl_Linear_Expression_coefficient (expr, loop_dim, coef);
238 ppl_delete_Linear_Expression (expr);
239 ppl_Coefficient_to_mpz_t (coef, stride);
241 if (value_zero_p (stride))
244 value_absolute (stride, stride);
245 compute_array_size (pdr, compute_subscript (pdr, cstr), array_size);
246 value_multiply (stride, stride, array_size);
247 value_addto (res, res, stride);
250 value_clear (array_size);
251 value_clear (stride);
252 ppl_delete_Coefficient (coef);
253 ppl_delete_Constraint_System_const_iterator (cit);
254 ppl_delete_Constraint_System_const_iterator (cend);
257 /* Computes ACCESS_STRIDES, the sum of all the strides of PDR at
261 gather_access_strides (poly_dr_p pdr, graphite_dim_t loop_depth,
262 Value access_strides)
264 ppl_dimension_type loop_dim = pdr_iterator_dim (pdr, loop_depth);
266 ppl_Pointset_Powerset_C_Polyhedron_t accesses = PDR_ACCESSES (pdr);
267 ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end;
271 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it);
272 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end);
274 for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (accesses, it),
275 ppl_Pointset_Powerset_C_Polyhedron_iterator_end (accesses, end);
276 !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end);
277 ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it))
279 ppl_const_Polyhedron_t ph;
281 ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph);
282 gather_access_strides_poly (pdr, ph, loop_dim, res);
283 value_addto (access_strides, access_strides, res);
287 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it);
288 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end);
291 /* Returns true when it is profitable to interchange loop at depth1
292 and loop at depth2 with depth1 < depth2 for the polyhedral black
296 pbb_interchange_profitable_p (graphite_dim_t depth1, graphite_dim_t depth2, poly_bb_p pbb)
300 Value access_strides1, access_strides2;
303 gcc_assert (depth1 < depth2);
305 value_init (access_strides1);
306 value_init (access_strides2);
308 value_set_si (access_strides1, 0);
309 value_set_si (access_strides2, 0);
311 for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
313 gather_access_strides (pdr, depth1, access_strides1);
314 gather_access_strides (pdr, depth2, access_strides2);
317 res = value_lt (access_strides1, access_strides2);
319 value_clear (access_strides1);
320 value_clear (access_strides2);
325 /* Interchanges the loops at DEPTH1 and DEPTH2 of the original
326 scattering and assigns the resulting polyhedron to the transformed
330 pbb_interchange_loop_depths (graphite_dim_t depth1, graphite_dim_t depth2, poly_bb_p pbb)
332 ppl_dimension_type i, dim;
333 ppl_dimension_type *map;
334 ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
335 ppl_dimension_type dim1 = psct_iterator_dim (pbb, depth1);
336 ppl_dimension_type dim2 = psct_iterator_dim (pbb, depth2);
338 ppl_Polyhedron_space_dimension (poly, &dim);
339 map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
341 for (i = 0; i < dim; i++)
347 ppl_Polyhedron_map_space_dimensions (poly, map, dim);
351 /* Interchanges all the loop depths that are considered profitable for PBB. */
354 pbb_do_interchange (poly_bb_p pbb, scop_p scop)
357 bool transform_done = false;
359 for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
360 for (j = i + 1; j < pbb_dim_iter_domain (pbb); j++)
361 if (pbb_interchange_profitable_p (i, j, pbb))
363 pbb_interchange_loop_depths (i, j, pbb);
365 if (graphite_legal_transform (scop))
367 transform_done = true;
369 if (dump_file && (dump_flags & TDF_DETAILS))
371 "PBB %d: loops at depths %d and %d will be interchanged.\n",
372 GBB_BB (PBB_BLACK_BOX (pbb))->index, (int) i, (int) j);
375 /* Undo the transform. */
376 pbb_interchange_loop_depths (j, i, pbb);
379 return transform_done;
382 /* Interchanges all the loop depths that are considered profitable for SCOP. */
385 scop_do_interchange (scop_p scop)
389 bool transform_done = false;
391 store_scattering (scop);
393 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
394 transform_done |= pbb_do_interchange (pbb, scop);
399 if (!graphite_legal_transform (scop))
401 restore_scattering (scop);
405 return transform_done;