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 /* Return in RES the maximum of the linear expression LE on polyhedron PS. */
59 ppl_max_for_le (ppl_Pointset_Powerset_C_Polyhedron_t ps
,
60 ppl_Linear_Expression_t le
, Value res
)
62 ppl_Coefficient_t num
, denom
;
68 ppl_new_Coefficient (&num
);
69 ppl_new_Coefficient (&denom
);
70 ppl_Pointset_Powerset_C_Polyhedron_maximize (ps
, le
, num
, denom
, &maximum
);
74 ppl_Coefficient_to_mpz_t (num
, nv
);
75 ppl_Coefficient_to_mpz_t (denom
, dv
);
76 value_division (res
, nv
, dv
);
81 ppl_delete_Coefficient (num
);
82 ppl_delete_Coefficient (denom
);
85 /* Builds a linear expression, of dimension DIM, representing PDR's
88 L = r_{n}*r_{n-1}*...*r_{1}*s_{0} + ... + r_{n}*s_{n-1} + s_{n}.
90 For an array A[10][20] with two subscript locations s0 and s1, the
91 linear memory access is 20 * s0 + s1: a stride of 1 in subscript s0
92 corresponds to a memory stride of 20. */
94 static ppl_Linear_Expression_t
95 build_linearized_memory_access (poly_dr_p pdr
)
97 ppl_Linear_Expression_t res
;
98 ppl_Linear_Expression_t le
;
100 ppl_dimension_type first
= pdr_subscript_dim (pdr
, 0);
101 ppl_dimension_type last
= pdr_subscript_dim (pdr
, PDR_NB_SUBSCRIPTS (pdr
));
102 Value size
, sub_size
;
103 graphite_dim_t dim
= pdr_dim (pdr
);
105 ppl_new_Linear_Expression_with_dimension (&res
, dim
);
108 value_set_si (size
, 1);
109 value_init (sub_size
);
110 value_set_si (sub_size
, 1);
112 for (i
= last
- 1; i
>= first
; i
--)
114 ppl_set_coef_gmp (res
, i
, size
);
116 ppl_new_Linear_Expression_with_dimension (&le
, dim
);
117 ppl_set_coef (le
, i
, 1);
118 ppl_max_for_le (PDR_ACCESSES (pdr
), le
, sub_size
);
119 value_multiply (size
, size
, sub_size
);
120 ppl_delete_Linear_Expression (le
);
123 value_clear (sub_size
);
128 /* Set STRIDE to the stride of PDR in memory by advancing by one in
132 memory_stride_in_loop (Value stride
, graphite_dim_t depth
, poly_dr_p pdr
)
134 ppl_Linear_Expression_t le
, lma
;
135 ppl_Constraint_t new_cstr
;
136 ppl_Pointset_Powerset_C_Polyhedron_t p1
, p2
;
137 graphite_dim_t nb_subscripts
= PDR_NB_SUBSCRIPTS (pdr
);
138 ppl_dimension_type i
, *map
;
139 ppl_dimension_type dim
= pdr_dim (pdr
);
140 ppl_dimension_type dim_i
= pdr_iterator_dim (pdr
, depth
);
141 ppl_dimension_type dim_k
= dim
;
142 ppl_dimension_type dim_L1
= dim
+ nb_subscripts
+ 1;
143 ppl_dimension_type dim_L2
= dim
+ nb_subscripts
+ 2;
144 ppl_dimension_type new_dim
= dim
+ nb_subscripts
+ 3;
146 /* Add new dimensions to the polyhedron corresponding to
147 k, s0', s1',..., L1, and L2. These new variables are at
148 dimensions dim, dim + 1,... of the polyhedron P1 respectively. */
149 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
150 (&p1
, PDR_ACCESSES (pdr
));
151 ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed
152 (p1
, nb_subscripts
+ 3);
154 lma
= build_linearized_memory_access (pdr
);
155 ppl_set_coef (lma
, dim_L1
, -1);
156 ppl_new_Constraint (&new_cstr
, lma
, PPL_CONSTRAINT_TYPE_EQUAL
);
157 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p1
, new_cstr
);
160 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
162 map
= ppl_new_id_map (new_dim
);
163 ppl_interchange (map
, dim_L1
, dim_L2
);
164 ppl_interchange (map
, dim_i
, dim_k
);
165 for (i
= 0; i
< PDR_NB_SUBSCRIPTS (pdr
); i
++)
166 ppl_interchange (map
, pdr_subscript_dim (pdr
, i
), dim
+ i
+ 1);
167 ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (p2
, map
, new_dim
);
170 /* Add constraint k = i + 1. */
171 ppl_new_Linear_Expression_with_dimension (&le
, new_dim
);
172 ppl_set_coef (le
, dim_i
, 1);
173 ppl_set_coef (le
, dim_k
, -1);
174 ppl_set_inhomogeneous (le
, 1);
175 ppl_new_Constraint (&new_cstr
, le
, PPL_CONSTRAINT_TYPE_EQUAL
);
176 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p2
, new_cstr
);
177 ppl_delete_Linear_Expression (le
);
178 ppl_delete_Constraint (new_cstr
);
180 /* P1 = P1 inter P2. */
181 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (p1
, p2
);
182 ppl_delete_Pointset_Powerset_C_Polyhedron (p2
);
184 /* Maximise the expression L2 - L1. */
185 ppl_new_Linear_Expression_with_dimension (&le
, new_dim
);
186 ppl_set_coef (le
, dim_L2
, 1);
187 ppl_set_coef (le
, dim_L1
, -1);
188 ppl_max_for_le (p1
, le
, stride
);
189 ppl_delete_Linear_Expression (le
);
193 /* Returns true when it is profitable to interchange loop at DEPTH1
194 and loop at DEPTH2 with DEPTH1 < DEPTH2 for PBB.
206 | for (i = 0; i < N; i++)
207 | for (j = 0; j < N; j++)
213 The data access A[j][i] is described like this:
221 | 0 0 0 0 -1 0 100 >= 0
222 | 0 0 0 0 0 -1 100 >= 0
224 The linearized memory access L to A[100][100] is:
229 Next, to measure the impact of iterating once in loop "i", we build
230 a maximization problem: first, we add to DR accesses the dimensions
231 k, s2, s3, L1 = 100 * s0 + s1, L2, and D1: polyhedron P1.
233 | i j N a s0 s1 k s2 s3 L1 L2 D1 1
234 | 0 0 0 1 0 0 0 0 0 0 0 0 -5 = 0 alias = 5
235 | 0 -1 0 0 1 0 0 0 0 0 0 0 0 = 0 s0 = j
236 |-2 0 0 0 0 1 0 0 0 0 0 0 0 = 0 s1 = 2 * i
237 | 0 0 0 0 1 0 0 0 0 0 0 0 0 >= 0
238 | 0 0 0 0 0 1 0 0 0 0 0 0 0 >= 0
239 | 0 0 0 0 -1 0 0 0 0 0 0 0 100 >= 0
240 | 0 0 0 0 0 -1 0 0 0 0 0 0 100 >= 0
241 | 0 0 0 0 100 1 0 0 0 -1 0 0 0 = 0 L1 = 100 * s0 + s1
243 Then, we generate the polyhedron P2 by interchanging the dimensions
244 (s0, s2), (s1, s3), (L1, L2), (i0, i)
246 | i j N a s0 s1 k s2 s3 L1 L2 D1 1
247 | 0 0 0 1 0 0 0 0 0 0 0 0 -5 = 0 alias = 5
248 | 0 -1 0 0 0 0 0 1 0 0 0 0 0 = 0 s2 = j
249 | 0 0 0 0 0 0 -2 0 1 0 0 0 0 = 0 s3 = 2 * k
250 | 0 0 0 0 0 0 0 1 0 0 0 0 0 >= 0
251 | 0 0 0 0 0 0 0 0 1 0 0 0 0 >= 0
252 | 0 0 0 0 0 0 0 -1 0 0 0 0 100 >= 0
253 | 0 0 0 0 0 0 0 0 -1 0 0 0 100 >= 0
254 | 0 0 0 0 0 0 0 100 1 0 -1 0 0 = 0 L2 = 100 * s2 + s3
256 then we add to P2 the equality k = i + 1:
258 |-1 0 0 0 0 0 1 0 0 0 0 0 -1 = 0 k = i + 1
260 and finally we maximize the expression "D1 = max (P1 inter P2, L2 - L1)".
262 For determining the impact of one iteration on loop "j", we
263 interchange (k, j), we add "k = j + 1", and we compute D2 the
264 maximal value of the difference.
266 Finally, the profitability test is D1 < D2: if in the outer loop
267 the strides are smaller than in the inner loop, then it is
268 profitable to interchange the loops at DEPTH1 and DEPTH2. */
271 pbb_interchange_profitable_p (graphite_dim_t depth1
, graphite_dim_t depth2
,
279 gcc_assert (depth1
< depth2
);
282 value_set_si (d1
, 0);
284 value_set_si (d2
, 0);
287 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb
), i
, pdr
); i
++)
289 memory_stride_in_loop (s
, depth1
, pdr
);
290 value_addto (d1
, d1
, s
);
292 memory_stride_in_loop (s
, depth2
, pdr
);
293 value_addto (d2
, d2
, s
);
296 res
= value_lt (d1
, d2
);
305 /* Interchanges the loops at DEPTH1 and DEPTH2 of the original
306 scattering and assigns the resulting polyhedron to the transformed
310 pbb_interchange_loop_depths (graphite_dim_t depth1
, graphite_dim_t depth2
, poly_bb_p pbb
)
312 ppl_dimension_type i
, dim
;
313 ppl_dimension_type
*map
;
314 ppl_Polyhedron_t poly
= PBB_TRANSFORMED_SCATTERING (pbb
);
315 ppl_dimension_type dim1
= psct_iterator_dim (pbb
, depth1
);
316 ppl_dimension_type dim2
= psct_iterator_dim (pbb
, depth2
);
318 ppl_Polyhedron_space_dimension (poly
, &dim
);
319 map
= (ppl_dimension_type
*) XNEWVEC (ppl_dimension_type
, dim
);
321 for (i
= 0; i
< dim
; i
++)
327 ppl_Polyhedron_map_space_dimensions (poly
, map
, dim
);
331 /* Interchanges all the loop depths that are considered profitable for PBB. */
334 pbb_do_interchange (poly_bb_p pbb
, scop_p scop
)
337 bool transform_done
= false;
339 for (i
= 0; i
< pbb_dim_iter_domain (pbb
); i
++)
340 for (j
= i
+ 1; j
< pbb_dim_iter_domain (pbb
); j
++)
341 if (pbb_interchange_profitable_p (i
, j
, pbb
))
343 pbb_interchange_loop_depths (i
, j
, pbb
);
345 if (graphite_legal_transform (scop
))
347 transform_done
= true;
349 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
351 "PBB %d: loops at depths %d and %d will be interchanged.\n",
352 GBB_BB (PBB_BLACK_BOX (pbb
))->index
, (int) i
, (int) j
);
355 /* Undo the transform. */
356 pbb_interchange_loop_depths (j
, i
, pbb
);
359 return transform_done
;
362 /* Interchanges all the loop depths that are considered profitable for SCOP. */
365 scop_do_interchange (scop_p scop
)
369 bool transform_done
= false;
371 store_scattering (scop
);
373 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
374 transform_done
|= pbb_do_interchange (pbb
, scop
);
379 if (!graphite_legal_transform (scop
))
381 restore_scattering (scop
);
385 return transform_done
;