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 OFFSET is a number of dimensions to prepend before the
66 subscript dimensions: s_0, s_1, ..., s_n.
68 Thus, the final linear expression has the following format:
69 0 .. 0_{offset} | 0 .. 0_{nit} | 0 .. 0_{gd} | 0 | c_0 c_1 ... c_n
70 where the expression itself is:
71 c_0 * s_0 + c_1 * s_1 + ... c_n * s_n. */
73 static ppl_Linear_Expression_t
74 build_linearized_memory_access (ppl_dimension_type offset, poly_dr_p pdr)
76 ppl_Linear_Expression_t res;
77 ppl_Linear_Expression_t le;
79 ppl_dimension_type first = pdr_subscript_dim (pdr, 0);
80 ppl_dimension_type last = pdr_subscript_dim (pdr, PDR_NB_SUBSCRIPTS (pdr));
82 graphite_dim_t dim = offset + pdr_dim (pdr);
84 ppl_new_Linear_Expression_with_dimension (&res, dim);
87 value_set_si (size, 1);
88 value_init (sub_size);
89 value_set_si (sub_size, 1);
91 for (i = last - 1; i >= first; i--)
93 ppl_set_coef_gmp (res, i + offset, size);
95 ppl_new_Linear_Expression_with_dimension (&le, dim - offset);
96 ppl_set_coef (le, i, 1);
97 ppl_max_for_le_pointset (PDR_ACCESSES (pdr), le, sub_size);
98 value_multiply (size, size, sub_size);
99 ppl_delete_Linear_Expression (le);
102 value_clear (sub_size);
107 /* Set STRIDE to the stride of PDR in memory by advancing by one in
108 time dimension DEPTH. */
111 memory_stride_in_loop (Value stride, graphite_dim_t depth, poly_dr_p pdr)
113 ppl_dimension_type time_depth;
114 ppl_Linear_Expression_t le, lma;
115 ppl_Constraint_t new_cstr;
116 ppl_dimension_type i, *map;
117 ppl_Pointset_Powerset_C_Polyhedron_t p1, p2, sctr;
118 graphite_dim_t nb_subscripts = PDR_NB_SUBSCRIPTS (pdr) + 1;
119 poly_bb_p pbb = PDR_PBB (pdr);
120 ppl_dimension_type offset = pbb_nb_scattering_transform (pbb)
121 + pbb_nb_local_vars (pbb)
122 + pbb_dim_iter_domain (pbb);
123 ppl_dimension_type offsetg = offset + pbb_nb_params (pbb);
124 ppl_dimension_type dim_sctr = pbb_nb_scattering_transform (pbb)
125 + pbb_nb_local_vars (pbb);
126 ppl_dimension_type dim_L1 = offset + offsetg + 2 * nb_subscripts;
127 ppl_dimension_type dim_L2 = offset + offsetg + 2 * nb_subscripts + 1;
128 ppl_dimension_type new_dim = offset + offsetg + 2 * nb_subscripts + 2;
130 /* The resulting polyhedron should have the following format:
131 T|I|T'|I'|G|S|S'|l1|l2
133 | T = t_1..t_{dim_sctr}
134 | I = i_1..i_{dim_iter_domain}
135 | T'= t'_1..t'_{dim_sctr}
136 | I'= i'_1..i'_{dim_iter_domain}
137 | G = g_1..g_{nb_params}
138 | S = s_1..s_{nb_subscripts}
139 | S'= s'_1..s'_{nb_subscripts}
140 | l1 and l2 are scalars.
143 offset = dim_sctr + dim_iter_domain + nb_local_vars
144 offsetg = dim_sctr + dim_iter_domain + nb_local_vars + nb_params. */
146 /* Construct the T|I|0|0|G|0|0|0|0 part. */
148 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
149 (&sctr, PBB_TRANSFORMED_SCATTERING (pbb));
150 ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed
151 (sctr, 2 * nb_subscripts + 2);
152 ppl_insert_dimensions_pointset (sctr, offset, offset);
155 /* Construct the 0|I|0|0|G|S|0|0|0 part. */
157 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
158 (&p1, PDR_ACCESSES (pdr));
159 ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed
160 (p1, nb_subscripts + 2);
161 ppl_insert_dimensions_pointset (p1, 0, dim_sctr);
162 ppl_insert_dimensions_pointset (p1, offset, offset);
165 /* Construct the 0|0|0|0|0|S|0|l1|0 part. */
167 lma = build_linearized_memory_access (offset + dim_sctr, pdr);
168 ppl_set_coef (lma, dim_L1, -1);
169 ppl_new_Constraint (&new_cstr, lma, PPL_CONSTRAINT_TYPE_EQUAL);
170 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p1, new_cstr);
171 ppl_delete_Linear_Expression (lma);
172 ppl_delete_Constraint (new_cstr);
175 /* Now intersect all the parts to get the polyhedron P1:
180 T|I|0|0|G|S|0|l1|0. */
182 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (p1, sctr);
183 ppl_delete_Pointset_Powerset_C_Polyhedron (sctr);
185 /* Build P2, which would have the following form:
186 0|0|T'|I'|G|0|S'|0|l2
188 P2 is built, by remapping the P1 polyhedron:
191 using the following mapping:
197 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
200 map = ppl_new_id_map (new_dim);
203 for (i = 0; i < offset; i++)
204 ppl_interchange (map, i, i + offset);
207 ppl_interchange (map, dim_L1, dim_L2);
210 for (i = 0; i < nb_subscripts; i++)
211 ppl_interchange (map, offset + offsetg + i,
212 offset + offsetg + nb_subscripts + i);
214 ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (p2, map, new_dim);
221 | t_{depth-1} = t'_{depth-1}
222 | t_{depth+1} = t'_{depth+1}
224 | t_{dim_sctr} = t'_{dim_sctr}
226 This means that all the time dimensions are equal except for
227 depth, where we will add t_{depth} = t'_{depth} + 1 in the next
230 time_depth = psct_dynamic_dim (pbb, depth);
231 for (i = 0; i < dim_sctr; i++)
234 ppl_new_Linear_Expression_with_dimension (&le, new_dim);
235 ppl_set_coef (le, i, 1);
236 ppl_set_coef (le, i + offset, -1);
237 ppl_new_Constraint (&new_cstr, le, PPL_CONSTRAINT_TYPE_EQUAL);
238 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p2, new_cstr);
239 ppl_delete_Linear_Expression (le);
240 ppl_delete_Constraint (new_cstr);
243 /* Add equality : t_{depth} = t'_{depth} + 1.
244 This is the core part of this alogrithm, since this
245 constraint asks for the memory access stride (difference)
246 between two consecutive points in time dimensions. */
248 ppl_new_Linear_Expression_with_dimension (&le, new_dim);
249 ppl_set_coef (le, time_depth, 1);
250 ppl_set_coef (le, time_depth + offset, -1);
251 ppl_set_inhomogeneous (le, 1);
252 ppl_new_Constraint (&new_cstr, le, PPL_CONSTRAINT_TYPE_EQUAL);
253 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p2, new_cstr);
254 ppl_delete_Linear_Expression (le);
255 ppl_delete_Constraint (new_cstr);
258 /* P1 = P1 inter P2. */
259 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (p1, p2);
261 /* Maximise the expression L2 - L1. */
263 ppl_new_Linear_Expression_with_dimension (&le, new_dim);
264 ppl_set_coef (le, dim_L2, 1);
265 ppl_set_coef (le, dim_L1, -1);
266 ppl_max_for_le_pointset (p1, le, stride);
269 ppl_delete_Pointset_Powerset_C_Polyhedron (p1);
270 ppl_delete_Pointset_Powerset_C_Polyhedron (p2);
271 ppl_delete_Linear_Expression (le);
274 /* Returns true when it is profitable to interchange time dimensions DEPTH1
275 and DEPTH2 with DEPTH1 < DEPTH2 for PBB.
287 | for (i = 0; i < N; i++)
288 | for (j = 0; j < N; j++)
294 The data access A[j][i] is described like this:
302 | 0 0 0 0 -1 0 100 >= 0
303 | 0 0 0 0 0 -1 100 >= 0
305 The linearized memory access L to A[100][100] is:
310 TODO: the shown format is not valid as it does not show the fact
311 that the iteration domain "i j" is transformed using the scattering.
313 Next, to measure the impact of iterating once in loop "i", we build
314 a maximization problem: first, we add to DR accesses the dimensions
315 k, s2, s3, L1 = 100 * s0 + s1, L2, and D1: this is the polyhedron P1.
316 L1 and L2 are the linearized memory access functions.
318 | i j N a s0 s1 k s2 s3 L1 L2 D1 1
319 | 0 0 0 1 0 0 0 0 0 0 0 0 -5 = 0 alias = 5
320 | 0 -1 0 0 1 0 0 0 0 0 0 0 0 = 0 s0 = j
321 |-2 0 0 0 0 1 0 0 0 0 0 0 0 = 0 s1 = 2 * i
322 | 0 0 0 0 1 0 0 0 0 0 0 0 0 >= 0
323 | 0 0 0 0 0 1 0 0 0 0 0 0 0 >= 0
324 | 0 0 0 0 -1 0 0 0 0 0 0 0 100 >= 0
325 | 0 0 0 0 0 -1 0 0 0 0 0 0 100 >= 0
326 | 0 0 0 0 100 1 0 0 0 -1 0 0 0 = 0 L1 = 100 * s0 + s1
328 Then, we generate the polyhedron P2 by interchanging the dimensions
329 (s0, s2), (s1, s3), (L1, L2), (k, i)
331 | i j N a s0 s1 k s2 s3 L1 L2 D1 1
332 | 0 0 0 1 0 0 0 0 0 0 0 0 -5 = 0 alias = 5
333 | 0 -1 0 0 0 0 0 1 0 0 0 0 0 = 0 s2 = j
334 | 0 0 0 0 0 0 -2 0 1 0 0 0 0 = 0 s3 = 2 * k
335 | 0 0 0 0 0 0 0 1 0 0 0 0 0 >= 0
336 | 0 0 0 0 0 0 0 0 1 0 0 0 0 >= 0
337 | 0 0 0 0 0 0 0 -1 0 0 0 0 100 >= 0
338 | 0 0 0 0 0 0 0 0 -1 0 0 0 100 >= 0
339 | 0 0 0 0 0 0 0 100 1 0 -1 0 0 = 0 L2 = 100 * s2 + s3
341 then we add to P2 the equality k = i + 1:
343 |-1 0 0 0 0 0 1 0 0 0 0 0 -1 = 0 k = i + 1
345 and finally we maximize the expression "D1 = max (P1 inter P2, L2 - L1)".
347 Similarly, to determine the impact of one iteration on loop "j", we
348 interchange (k, j), we add "k = j + 1", and we compute D2 the
349 maximal value of the difference.
351 Finally, the profitability test is D1 < D2: if in the outer loop
352 the strides are smaller than in the inner loop, then it is
353 profitable to interchange the loops at DEPTH1 and DEPTH2. */
356 pbb_interchange_profitable_p (graphite_dim_t depth1, graphite_dim_t depth2,
364 gcc_assert (depth1 < depth2);
367 value_set_si (d1, 0);
369 value_set_si (d2, 0);
373 for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
375 value_set_si (n, PDR_NB_REFS (pdr));
377 memory_stride_in_loop (s, depth1, pdr);
378 value_multiply (s, s, n);
379 value_addto (d1, d1, s);
381 memory_stride_in_loop (s, depth2, pdr);
382 value_multiply (s, s, n);
383 value_addto (d2, d2, s);
386 res = value_lt (d1, d2);
396 /* Interchanges the loops at DEPTH1 and DEPTH2 of the original
397 scattering and assigns the resulting polyhedron to the transformed
401 pbb_interchange_loop_depths (graphite_dim_t depth1, graphite_dim_t depth2,
404 ppl_dimension_type i, dim;
405 ppl_dimension_type *map;
406 ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
407 ppl_dimension_type dim1 = psct_dynamic_dim (pbb, depth1);
408 ppl_dimension_type dim2 = psct_dynamic_dim (pbb, depth2);
410 ppl_Polyhedron_space_dimension (poly, &dim);
411 map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
413 for (i = 0; i < dim; i++)
419 ppl_Polyhedron_map_space_dimensions (poly, map, dim);
423 /* Apply the interchange of loops at depths DEPTH1 and DEPTH2 to all
424 the statements below LST. */
427 lst_apply_interchange (lst_p lst, int depth1, int depth2)
432 if (LST_LOOP_P (lst))
437 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
438 lst_apply_interchange (l, depth1, depth2);
441 pbb_interchange_loop_depths (depth1, depth2, LST_PBB (lst));
444 /* Return true when the interchange of loops at depths DEPTH1 and
445 DEPTH2 to all the statements below LST is profitable. */
448 lst_interchange_profitable_p (lst_p lst, int depth1, int depth2)
453 if (LST_LOOP_P (lst))
459 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
461 bool profitable = lst_interchange_profitable_p (l, depth1, depth2);
463 if (profitable && !LST_LOOP_P (lst)
464 && dump_file && (dump_flags & TDF_DETAILS))
466 "Interchanging loops at depths %d and %d is profitable for stmt_%d.\n",
467 depth1, depth2, pbb_index (LST_PBB (lst)));
475 return pbb_interchange_profitable_p (depth1, depth2, LST_PBB (lst));
478 /* Return true when the nest starting at LOOP1 and ending on LOOP2 is
479 perfect: i.e. there are no sequence of statements. */
482 lst_perfectly_nested_p (lst_p loop1, lst_p loop2)
487 if (!LST_LOOP_P (loop1))
490 return VEC_length (lst_p, LST_SEQ (loop1)) == 1
491 && lst_perfectly_nested_p (VEC_index (lst_p, LST_SEQ (loop1), 0), loop2);
494 /* Transform the loop nest between LOOP1 and LOOP2 into a perfect
495 nest. To continue the naming tradition, this function is called
496 after perfect_nestify. */
499 lst_perfect_nestify (lst_p loop1, lst_p loop2)
502 poly_bb_p first, last;
504 gcc_assert (loop1 && loop2
506 && LST_LOOP_P (loop1) && LST_LOOP_P (loop2));
508 first = LST_PBB (lst_find_first_pbb (loop2));
509 last = LST_PBB (lst_find_last_pbb (loop2));
511 before = copy_lst (loop1);
512 after = copy_lst (loop1);
514 lst_remove_all_before_including_pbb (before, first, false);
515 lst_remove_all_before_including_pbb (after, last, true);
517 lst_remove_all_before_excluding_pbb (loop1, first, true);
518 lst_remove_all_before_excluding_pbb (loop1, last, false);
520 lst_insert_in_sequence (before, loop1, true);
521 lst_insert_in_sequence (after, loop1, false);
524 /* Try to interchange LOOP1 with LOOP2 for all the statements of the
525 body of LOOP2. LOOP1 contains LOOP2. Return true if it did the
529 lst_try_interchange_loops (scop_p scop, lst_p loop1, lst_p loop2)
531 int depth1 = lst_depth (loop1);
532 int depth2 = lst_depth (loop2);
534 if (!lst_interchange_profitable_p (loop2, depth1, depth2))
537 store_lst_schedule (scop);
539 if (!lst_perfectly_nested_p (loop1, loop2))
540 lst_perfect_nestify (loop1, loop2);
542 gcc_assert (lst_perfectly_nested_p (loop1, loop2));
543 lst_apply_interchange (loop2, depth1, depth2);
545 if (graphite_legal_transform (scop))
547 if (dump_file && (dump_flags & TDF_DETAILS))
549 "Loops at depths %d and %d will be interchanged.\n",
555 /* Undo the transform. */
556 lst_apply_interchange (loop2, depth2, depth1);
557 restore_lst_schedule (scop);
561 /* Try to interchange LOOP with all the loops contained in the body of
562 LST. Return true if it did interchanged some loops. */
565 lst_try_interchange (scop_p scop, lst_p loop, lst_p lst)
570 if (LST_LOOP_P (lst))
574 bool res = lst_try_interchange_loops (scop, loop, lst);
576 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
577 res |= lst_try_interchange (scop, loop, l);
585 /* Interchanges all the loops of LST that are considered profitable to
586 interchange. Return true if it did interchanged some loops. */
589 lst_do_interchange (scop_p scop, lst_p lst)
594 if (LST_LOOP_P (lst))
600 if (lst_depth (lst) >= 0)
601 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
602 res |= lst_try_interchange (scop, lst, l);
604 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
605 res |= lst_do_interchange (scop, l);
613 /* Interchanges all the loop depths that are considered profitable for SCOP. */
616 scop_do_interchange (scop_p scop)
618 lst_p lst = copy_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
619 bool res = lst_do_interchange (scop, lst);