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 /* Builds a linear expression, of dimension DIM, representing PDR's
59 L = r_{n}*r_{n-1}*...*r_{1}*s_{0} + ... + r_{n}*s_{n-1} + s_{n}.
61 For an array A[10][20] with two subscript locations s0 and s1, the
62 linear memory access is 20 * s0 + s1: a stride of 1 in subscript s0
63 corresponds to a memory stride of 20. */
65 static ppl_Linear_Expression_t
66 build_linearized_memory_access (poly_dr_p pdr)
68 ppl_Linear_Expression_t res;
69 ppl_Linear_Expression_t le;
71 ppl_dimension_type first = pdr_subscript_dim (pdr, 0);
72 ppl_dimension_type last = pdr_subscript_dim (pdr, PDR_NB_SUBSCRIPTS (pdr));
74 graphite_dim_t dim = pdr_dim (pdr);
76 ppl_new_Linear_Expression_with_dimension (&res, dim);
79 value_set_si (size, 1);
80 value_init (sub_size);
81 value_set_si (sub_size, 1);
83 for (i = last - 1; i >= first; i--)
85 ppl_set_coef_gmp (res, i, size);
87 ppl_new_Linear_Expression_with_dimension (&le, dim);
88 ppl_set_coef (le, i, 1);
89 ppl_max_for_le (PDR_ACCESSES (pdr), le, sub_size);
90 value_multiply (size, size, sub_size);
91 ppl_delete_Linear_Expression (le);
94 value_clear (sub_size);
99 /* Set STRIDE to the stride of PDR in memory by advancing by one in
103 memory_stride_in_loop (Value stride, graphite_dim_t depth, poly_dr_p pdr)
105 ppl_Linear_Expression_t le, lma;
106 ppl_Constraint_t new_cstr;
107 ppl_Pointset_Powerset_C_Polyhedron_t p1, p2;
108 graphite_dim_t nb_subscripts = PDR_NB_SUBSCRIPTS (pdr);
109 ppl_dimension_type i, *map;
110 ppl_dimension_type dim = pdr_dim (pdr);
111 ppl_dimension_type dim_i = pdr_iterator_dim (pdr, depth);
112 ppl_dimension_type dim_k = dim;
113 ppl_dimension_type dim_L1 = dim + nb_subscripts + 1;
114 ppl_dimension_type dim_L2 = dim + nb_subscripts + 2;
115 ppl_dimension_type new_dim = dim + nb_subscripts + 3;
117 /* Add new dimensions to the polyhedron corresponding to
118 k, s0', s1',..., L1, and L2. These new variables are at
119 dimensions dim, dim + 1,... of the polyhedron P1 respectively. */
120 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
121 (&p1, PDR_ACCESSES (pdr));
122 ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed
123 (p1, nb_subscripts + 3);
125 lma = build_linearized_memory_access (pdr);
126 ppl_set_coef (lma, dim_L1, -1);
127 ppl_new_Constraint (&new_cstr, lma, PPL_CONSTRAINT_TYPE_EQUAL);
128 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p1, new_cstr);
131 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
133 map = ppl_new_id_map (new_dim);
134 ppl_interchange (map, dim_L1, dim_L2);
135 ppl_interchange (map, dim_i, dim_k);
136 for (i = 0; i < PDR_NB_SUBSCRIPTS (pdr); i++)
137 ppl_interchange (map, pdr_subscript_dim (pdr, i), dim + i + 1);
138 ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (p2, map, new_dim);
141 /* Add constraint k = i + 1. */
142 ppl_new_Linear_Expression_with_dimension (&le, new_dim);
143 ppl_set_coef (le, dim_i, 1);
144 ppl_set_coef (le, dim_k, -1);
145 ppl_set_inhomogeneous (le, 1);
146 ppl_new_Constraint (&new_cstr, le, PPL_CONSTRAINT_TYPE_EQUAL);
147 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p2, new_cstr);
148 ppl_delete_Linear_Expression (le);
149 ppl_delete_Constraint (new_cstr);
151 /* P1 = P1 inter P2. */
152 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (p1, p2);
153 ppl_delete_Pointset_Powerset_C_Polyhedron (p2);
155 /* Maximise the expression L2 - L1. */
156 ppl_new_Linear_Expression_with_dimension (&le, new_dim);
157 ppl_set_coef (le, dim_L2, 1);
158 ppl_set_coef (le, dim_L1, -1);
159 ppl_max_for_le (p1, le, stride);
160 ppl_delete_Linear_Expression (le);
164 /* Returns true when it is profitable to interchange loop at DEPTH1
165 and loop at DEPTH2 with DEPTH1 < DEPTH2 for PBB.
177 | for (i = 0; i < N; i++)
178 | for (j = 0; j < N; j++)
184 The data access A[j][i] is described like this:
192 | 0 0 0 0 -1 0 100 >= 0
193 | 0 0 0 0 0 -1 100 >= 0
195 The linearized memory access L to A[100][100] is:
200 Next, to measure the impact of iterating once in loop "i", we build
201 a maximization problem: first, we add to DR accesses the dimensions
202 k, s2, s3, L1 = 100 * s0 + s1, L2, and D1: polyhedron P1.
204 | i j N a s0 s1 k s2 s3 L1 L2 D1 1
205 | 0 0 0 1 0 0 0 0 0 0 0 0 -5 = 0 alias = 5
206 | 0 -1 0 0 1 0 0 0 0 0 0 0 0 = 0 s0 = j
207 |-2 0 0 0 0 1 0 0 0 0 0 0 0 = 0 s1 = 2 * i
208 | 0 0 0 0 1 0 0 0 0 0 0 0 0 >= 0
209 | 0 0 0 0 0 1 0 0 0 0 0 0 0 >= 0
210 | 0 0 0 0 -1 0 0 0 0 0 0 0 100 >= 0
211 | 0 0 0 0 0 -1 0 0 0 0 0 0 100 >= 0
212 | 0 0 0 0 100 1 0 0 0 -1 0 0 0 = 0 L1 = 100 * s0 + s1
214 Then, we generate the polyhedron P2 by interchanging the dimensions
215 (s0, s2), (s1, s3), (L1, L2), (i0, i)
217 | i j N a s0 s1 k s2 s3 L1 L2 D1 1
218 | 0 0 0 1 0 0 0 0 0 0 0 0 -5 = 0 alias = 5
219 | 0 -1 0 0 0 0 0 1 0 0 0 0 0 = 0 s2 = j
220 | 0 0 0 0 0 0 -2 0 1 0 0 0 0 = 0 s3 = 2 * k
221 | 0 0 0 0 0 0 0 1 0 0 0 0 0 >= 0
222 | 0 0 0 0 0 0 0 0 1 0 0 0 0 >= 0
223 | 0 0 0 0 0 0 0 -1 0 0 0 0 100 >= 0
224 | 0 0 0 0 0 0 0 0 -1 0 0 0 100 >= 0
225 | 0 0 0 0 0 0 0 100 1 0 -1 0 0 = 0 L2 = 100 * s2 + s3
227 then we add to P2 the equality k = i + 1:
229 |-1 0 0 0 0 0 1 0 0 0 0 0 -1 = 0 k = i + 1
231 and finally we maximize the expression "D1 = max (P1 inter P2, L2 - L1)".
233 For determining the impact of one iteration on loop "j", we
234 interchange (k, j), we add "k = j + 1", and we compute D2 the
235 maximal value of the difference.
237 Finally, the profitability test is D1 < D2: if in the outer loop
238 the strides are smaller than in the inner loop, then it is
239 profitable to interchange the loops at DEPTH1 and DEPTH2. */
242 pbb_interchange_profitable_p (graphite_dim_t depth1, graphite_dim_t depth2,
250 gcc_assert (depth1 < depth2);
253 value_set_si (d1, 0);
255 value_set_si (d2, 0);
258 for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
260 memory_stride_in_loop (s, depth1, pdr);
261 value_addto (d1, d1, s);
263 memory_stride_in_loop (s, depth2, pdr);
264 value_addto (d2, d2, s);
267 res = value_lt (d1, d2);
276 /* Interchanges the loops at DEPTH1 and DEPTH2 of the original
277 scattering and assigns the resulting polyhedron to the transformed
281 pbb_interchange_loop_depths (graphite_dim_t depth1, graphite_dim_t depth2, poly_bb_p pbb)
283 ppl_dimension_type i, dim;
284 ppl_dimension_type *map;
285 ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
286 ppl_dimension_type dim1 = psct_iterator_dim (pbb, depth1);
287 ppl_dimension_type dim2 = psct_iterator_dim (pbb, depth2);
289 ppl_Polyhedron_space_dimension (poly, &dim);
290 map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
292 for (i = 0; i < dim; i++)
298 ppl_Polyhedron_map_space_dimensions (poly, map, dim);
302 /* Interchanges all the loop depths that are considered profitable for PBB. */
305 pbb_do_interchange (poly_bb_p pbb, scop_p scop)
308 bool transform_done = false;
310 for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
311 for (j = i + 1; j < pbb_dim_iter_domain (pbb); j++)
312 if (pbb_interchange_profitable_p (i, j, pbb))
314 pbb_interchange_loop_depths (i, j, pbb);
316 if (graphite_legal_transform (scop))
318 transform_done = true;
320 if (dump_file && (dump_flags & TDF_DETAILS))
322 "PBB %d: loops at depths %d and %d will be interchanged.\n",
323 GBB_BB (PBB_BLACK_BOX (pbb))->index, (int) i, (int) j);
326 /* Undo the transform. */
327 pbb_interchange_loop_depths (j, i, pbb);
330 return transform_done;
333 /* Interchanges all the loop depths that are considered profitable for SCOP. */
336 scop_do_interchange (scop_p scop)
340 bool transform_done = false;
342 store_scattering (scop);
344 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
345 transform_done |= pbb_do_interchange (pbb, scop);
350 if (!graphite_legal_transform (scop))
352 restore_scattering (scop);
356 return transform_done;