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_DATA_CONTAINER (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 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
392 transform_done
|= pbb_do_interchange (pbb
, scop
);
394 return transform_done
;