1 /* Interchange heuristics and transform for loop interchange on
2 polyhedral representation.
4 Copyright (C) 2009-2014 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/>. */
30 #include <isl/union_map.h>
33 #if defined(__cplusplus)
36 #include <isl/val_gmp.h>
37 #if defined(__cplusplus)
41 #include <cloog/cloog.h>
42 #include <cloog/isl/domain.h>
47 #include "coretypes.h"
55 #include "hard-reg-set.h"
58 #include "dominance.h"
60 #include "basic-block.h"
61 #include "tree-ssa-alias.h"
62 #include "internal-fn.h"
63 #include "gimple-expr.h"
66 #include "gimple-iterator.h"
67 #include "tree-ssa-loop.h"
70 #include "tree-chrec.h"
71 #include "tree-data-ref.h"
72 #include "tree-scalar-evolution.h"
76 #include "graphite-poly.h"
78 /* XXX isl rewrite following comment */
79 /* Builds a linear expression, of dimension DIM, representing PDR's
82 L = r_{n}*r_{n-1}*...*r_{1}*s_{0} + ... + r_{n}*s_{n-1} + s_{n}.
84 For an array A[10][20] with two subscript locations s0 and s1, the
85 linear memory access is 20 * s0 + s1: a stride of 1 in subscript s0
86 corresponds to a memory stride of 20.
88 OFFSET is a number of dimensions to prepend before the
89 subscript dimensions: s_0, s_1, ..., s_n.
91 Thus, the final linear expression has the following format:
92 0 .. 0_{offset} | 0 .. 0_{nit} | 0 .. 0_{gd} | 0 | c_0 c_1 ... c_n
93 where the expression itself is:
94 c_0 * s_0 + c_1 * s_1 + ... c_n * s_n. */
96 static isl_constraint
*
97 build_linearized_memory_access (isl_map
*map
, poly_dr_p pdr
)
100 isl_local_space
*ls
= isl_local_space_from_space (isl_map_get_space (map
));
101 unsigned offset
, nsubs
;
105 isl_val
*size
, *subsize
, *size1
;
107 res
= isl_equality_alloc (ls
);
108 ctx
= isl_local_space_get_ctx (ls
);
109 size
= isl_val_int_from_ui (ctx
, 1);
111 nsubs
= isl_set_dim (pdr
->extent
, isl_dim_set
);
112 /* -1 for the already included L dimension. */
113 offset
= isl_map_dim (map
, isl_dim_out
) - 1 - nsubs
;
114 res
= isl_constraint_set_coefficient_si (res
, isl_dim_out
, offset
+ nsubs
, -1);
115 /* Go through all subscripts from last to first. First dimension
116 is the alias set, ignore it. */
117 for (i
= nsubs
- 1; i
>= 1; i
--)
122 size1
= isl_val_copy (size
);
123 res
= isl_constraint_set_coefficient_val (res
, isl_dim_out
, offset
+ i
, size
);
124 dc
= isl_set_get_space (pdr
->extent
);
125 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
126 aff
= isl_aff_set_coefficient_si (aff
, isl_dim_in
, i
, 1);
127 subsize
= isl_set_max_val (pdr
->extent
, aff
);
129 size
= isl_val_mul (size1
, subsize
);
137 /* Set STRIDE to the stride of PDR in memory by advancing by one in
138 the loop at DEPTH. */
141 pdr_stride_in_loop (mpz_t stride
, graphite_dim_t depth
, poly_dr_p pdr
)
143 poly_bb_p pbb
= PDR_PBB (pdr
);
148 isl_constraint
*lma
, *c
;
150 graphite_dim_t time_depth
;
153 /* XXX isl rewrite following comments. */
154 /* Builds a partial difference equations and inserts them
155 into pointset powerset polyhedron P. Polyhedron is assumed
156 to have the format: T|I|T'|I'|G|S|S'|l1|l2.
158 TIME_DEPTH is the time dimension w.r.t. which we are
160 OFFSET represents the number of dimensions between
161 columns t_{time_depth} and t'_{time_depth}.
162 DIM_SCTR is the number of scattering dimensions. It is
163 essentially the dimensionality of the T vector.
165 The following equations are inserted into the polyhedron P:
168 | t_{time_depth-1} = t'_{time_depth-1}
169 | t_{time_depth} = t'_{time_depth} + 1
170 | t_{time_depth+1} = t'_{time_depth + 1}
172 | t_{dim_sctr} = t'_{dim_sctr}. */
174 /* Add the equality: t_{time_depth} = t'_{time_depth} + 1.
175 This is the core part of this alogrithm, since this
176 constraint asks for the memory access stride (difference)
177 between two consecutive points in time dimensions. */
182 | t_{time_depth-1} = t'_{time_depth-1}
183 | t_{time_depth+1} = t'_{time_depth+1}
185 | t_{dim_sctr} = t'_{dim_sctr}
187 This means that all the time dimensions are equal except for
188 time_depth, where the constraint is t_{depth} = t'_{depth} + 1
189 step. More to this: we should be careful not to add equalities
190 to the 'coupled' dimensions, which happens when the one dimension
191 is stripmined dimension, and the other dimension corresponds
192 to the point loop inside stripmined dimension. */
194 /* pdr->accesses: [P1..nb_param,I1..nb_domain]->[a,S1..nb_subscript]
195 ??? [P] not used for PDRs?
196 pdr->extent: [a,S1..nb_subscript]
197 pbb->domain: [P1..nb_param,I1..nb_domain]
198 pbb->transformed: [P1..nb_param,I1..nb_domain]->[T1..Tnb_sctr]
199 [T] includes local vars (currently unused)
201 First we create [P,I] -> [T,a,S]. */
203 map
= isl_map_flat_range_product (isl_map_copy (pbb
->transformed
),
204 isl_map_copy (pdr
->accesses
));
205 /* Add a dimension for L: [P,I] -> [T,a,S,L].*/
206 map
= isl_map_add_dims (map
, isl_dim_out
, 1);
207 /* Build a constraint for "lma[S] - L == 0", effectively calculating
208 L in terms of subscripts. */
209 lma
= build_linearized_memory_access (map
, pdr
);
210 /* And add it to the map, so we now have:
211 [P,I] -> [T,a,S,L] : lma([S]) == L. */
212 map
= isl_map_add_constraint (map
, lma
);
214 /* Then we create [P,I,P',I'] -> [T,a,S,L,T',a',S',L']. */
215 map
= isl_map_flat_product (map
, isl_map_copy (map
));
217 /* Now add the equality T[time_depth] == T'[time_depth]+1. This will
218 force L' to be the linear address at T[time_depth] + 1. */
219 time_depth
= psct_dynamic_dim (pbb
, depth
);
220 /* Length of [a,S] plus [L] ... */
221 offset
= 1 + isl_map_dim (pdr
->accesses
, isl_dim_out
);
223 offset
+= isl_map_dim (pbb
->transformed
, isl_dim_out
);
225 c
= isl_equality_alloc (isl_local_space_from_space (isl_map_get_space (map
)));
226 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, time_depth
, 1);
227 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
,
228 offset
+ time_depth
, -1);
229 c
= isl_constraint_set_constant_si (c
, 1);
230 map
= isl_map_add_constraint (map
, c
);
232 /* Now we equate most of the T/T' elements (making PITaSL nearly
233 the same is (PITaSL)', except for one dimension, namely for 'depth'
234 (an index into [I]), after translating to index into [T]. Take care
235 to not produce an empty map, which indicates we wanted to equate
236 two dimensions that are already coupled via the above time_depth
237 dimension. Happens with strip mining where several scatter dimension
238 are interdependend. */
240 nt
= pbb_nb_scattering_transform (pbb
) + pbb_nb_local_vars (pbb
);
241 for (i
= 0; i
< nt
; i
++)
244 isl_map
*temp
= isl_map_equate (isl_map_copy (map
),
246 isl_dim_out
, offset
+ i
);
247 if (isl_map_is_empty (temp
))
256 /* Now maximize the expression L' - L. */
257 set
= isl_map_range (map
);
258 dc
= isl_set_get_space (set
);
259 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
260 aff
= isl_aff_set_coefficient_si (aff
, isl_dim_in
, offset
- 1, -1);
261 aff
= isl_aff_set_coefficient_si (aff
, isl_dim_in
, offset
+ offset
- 1, 1);
262 islstride
= isl_set_max_val (set
, aff
);
263 isl_val_get_num_gmp (islstride
, stride
);
264 isl_val_free (islstride
);
268 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
270 gmp_fprintf (dump_file
, "\nStride in BB_%d, DR_%d, depth %d: %Zd ",
271 pbb_index (pbb
), PDR_ID (pdr
), (int) depth
, stride
);
275 /* Sets STRIDES to the sum of all the strides of the data references
276 accessed in LOOP at DEPTH. */
279 memory_strides_in_loop_1 (lst_p loop
, graphite_dim_t depth
, mpz_t strides
)
289 FOR_EACH_VEC_ELT (LST_SEQ (loop
), j
, l
)
291 memory_strides_in_loop_1 (l
, depth
, strides
);
293 FOR_EACH_VEC_ELT (PBB_DRS (LST_PBB (l
)), i
, pdr
)
295 pdr_stride_in_loop (s
, depth
, pdr
);
296 mpz_set_si (n
, PDR_NB_REFS (pdr
));
298 mpz_add (strides
, strides
, s
);
305 /* Sets STRIDES to the sum of all the strides of the data references
306 accessed in LOOP at DEPTH. */
309 memory_strides_in_loop (lst_p loop
, graphite_dim_t depth
, mpz_t strides
)
311 if (mpz_cmp_si (loop
->memory_strides
, -1) == 0)
313 mpz_set_si (strides
, 0);
314 memory_strides_in_loop_1 (loop
, depth
, strides
);
317 mpz_set (strides
, loop
->memory_strides
);
320 /* Return true when the interchange of loops LOOP1 and LOOP2 is
333 | for (i = 0; i < N; i++)
334 | for (j = 0; j < N; j++)
340 The data access A[j][i] is described like this:
348 | 0 0 0 0 -1 0 100 >= 0
349 | 0 0 0 0 0 -1 100 >= 0
351 The linearized memory access L to A[100][100] is:
356 TODO: the shown format is not valid as it does not show the fact
357 that the iteration domain "i j" is transformed using the scattering.
359 Next, to measure the impact of iterating once in loop "i", we build
360 a maximization problem: first, we add to DR accesses the dimensions
361 k, s2, s3, L1 = 100 * s0 + s1, L2, and D1: this is the polyhedron P1.
362 L1 and L2 are the linearized memory access functions.
364 | i j N a s0 s1 k s2 s3 L1 L2 D1 1
365 | 0 0 0 1 0 0 0 0 0 0 0 0 -5 = 0 alias = 5
366 | 0 -1 0 0 1 0 0 0 0 0 0 0 0 = 0 s0 = j
367 |-2 0 0 0 0 1 0 0 0 0 0 0 0 = 0 s1 = 2 * i
368 | 0 0 0 0 1 0 0 0 0 0 0 0 0 >= 0
369 | 0 0 0 0 0 1 0 0 0 0 0 0 0 >= 0
370 | 0 0 0 0 -1 0 0 0 0 0 0 0 100 >= 0
371 | 0 0 0 0 0 -1 0 0 0 0 0 0 100 >= 0
372 | 0 0 0 0 100 1 0 0 0 -1 0 0 0 = 0 L1 = 100 * s0 + s1
374 Then, we generate the polyhedron P2 by interchanging the dimensions
375 (s0, s2), (s1, s3), (L1, L2), (k, i)
377 | i j N a s0 s1 k s2 s3 L1 L2 D1 1
378 | 0 0 0 1 0 0 0 0 0 0 0 0 -5 = 0 alias = 5
379 | 0 -1 0 0 0 0 0 1 0 0 0 0 0 = 0 s2 = j
380 | 0 0 0 0 0 0 -2 0 1 0 0 0 0 = 0 s3 = 2 * k
381 | 0 0 0 0 0 0 0 1 0 0 0 0 0 >= 0
382 | 0 0 0 0 0 0 0 0 1 0 0 0 0 >= 0
383 | 0 0 0 0 0 0 0 -1 0 0 0 0 100 >= 0
384 | 0 0 0 0 0 0 0 0 -1 0 0 0 100 >= 0
385 | 0 0 0 0 0 0 0 100 1 0 -1 0 0 = 0 L2 = 100 * s2 + s3
387 then we add to P2 the equality k = i + 1:
389 |-1 0 0 0 0 0 1 0 0 0 0 0 -1 = 0 k = i + 1
391 and finally we maximize the expression "D1 = max (P1 inter P2, L2 - L1)".
393 Similarly, to determine the impact of one iteration on loop "j", we
394 interchange (k, j), we add "k = j + 1", and we compute D2 the
395 maximal value of the difference.
397 Finally, the profitability test is D1 < D2: if in the outer loop
398 the strides are smaller than in the inner loop, then it is
399 profitable to interchange the loops at DEPTH1 and DEPTH2. */
402 lst_interchange_profitable_p (lst_p nest
, int depth1
, int depth2
)
407 gcc_assert (depth1
< depth2
);
412 memory_strides_in_loop (nest
, depth1
, d1
);
413 memory_strides_in_loop (nest
, depth2
, d2
);
415 res
= mpz_cmp (d1
, d2
) < 0;
423 /* Interchanges the loops at DEPTH1 and DEPTH2 of the original
424 scattering and assigns the resulting polyhedron to the transformed
428 pbb_interchange_loop_depths (graphite_dim_t depth1
, graphite_dim_t depth2
,
432 unsigned dim1
= psct_dynamic_dim (pbb
, depth1
);
433 unsigned dim2
= psct_dynamic_dim (pbb
, depth2
);
434 isl_space
*d
= isl_map_get_space (pbb
->transformed
);
435 isl_space
*d1
= isl_space_range (d
);
436 unsigned n
= isl_space_dim (d1
, isl_dim_out
);
437 isl_space
*d2
= isl_space_add_dims (d1
, isl_dim_in
, n
);
438 isl_map
*x
= isl_map_universe (d2
);
440 x
= isl_map_equate (x
, isl_dim_in
, dim1
, isl_dim_out
, dim2
);
441 x
= isl_map_equate (x
, isl_dim_in
, dim2
, isl_dim_out
, dim1
);
443 for (i
= 0; i
< n
; i
++)
444 if (i
!= dim1
&& i
!= dim2
)
445 x
= isl_map_equate (x
, isl_dim_in
, i
, isl_dim_out
, i
);
447 pbb
->transformed
= isl_map_apply_range (pbb
->transformed
, x
);
450 /* Apply the interchange of loops at depths DEPTH1 and DEPTH2 to all
451 the statements below LST. */
454 lst_apply_interchange (lst_p lst
, int depth1
, int depth2
)
459 if (LST_LOOP_P (lst
))
464 FOR_EACH_VEC_ELT (LST_SEQ (lst
), i
, l
)
465 lst_apply_interchange (l
, depth1
, depth2
);
468 pbb_interchange_loop_depths (depth1
, depth2
, LST_PBB (lst
));
471 /* Return true when the nest starting at LOOP1 and ending on LOOP2 is
472 perfect: i.e. there are no sequence of statements. */
475 lst_perfectly_nested_p (lst_p loop1
, lst_p loop2
)
480 if (!LST_LOOP_P (loop1
))
483 return LST_SEQ (loop1
).length () == 1
484 && lst_perfectly_nested_p (LST_SEQ (loop1
)[0], loop2
);
487 /* Transform the loop nest between LOOP1 and LOOP2 into a perfect
488 nest. To continue the naming tradition, this function is called
489 after perfect_nestify. NEST is set to the perfectly nested loop
490 that is created. BEFORE/AFTER are set to the loops distributed
491 before/after the loop NEST. */
494 lst_perfect_nestify (lst_p loop1
, lst_p loop2
, lst_p
*before
,
495 lst_p
*nest
, lst_p
*after
)
497 poly_bb_p first
, last
;
499 gcc_assert (loop1
&& loop2
501 && LST_LOOP_P (loop1
) && LST_LOOP_P (loop2
));
503 first
= LST_PBB (lst_find_first_pbb (loop2
));
504 last
= LST_PBB (lst_find_last_pbb (loop2
));
506 *before
= copy_lst (loop1
);
507 *nest
= copy_lst (loop1
);
508 *after
= copy_lst (loop1
);
510 lst_remove_all_before_including_pbb (*before
, first
, false);
511 lst_remove_all_before_including_pbb (*after
, last
, true);
513 lst_remove_all_before_excluding_pbb (*nest
, first
, true);
514 lst_remove_all_before_excluding_pbb (*nest
, last
, false);
516 if (lst_empty_p (*before
))
521 if (lst_empty_p (*after
))
526 if (lst_empty_p (*nest
))
533 /* Try to interchange LOOP1 with LOOP2 for all the statements of the
534 body of LOOP2. LOOP1 contains LOOP2. Return true if it did the
538 lst_try_interchange_loops (scop_p scop
, lst_p loop1
, lst_p loop2
)
540 int depth1
= lst_depth (loop1
);
541 int depth2
= lst_depth (loop2
);
544 lst_p before
= NULL
, nest
= NULL
, after
= NULL
;
546 if (!lst_perfectly_nested_p (loop1
, loop2
))
547 lst_perfect_nestify (loop1
, loop2
, &before
, &nest
, &after
);
549 if (!lst_interchange_profitable_p (loop2
, depth1
, depth2
))
552 lst_apply_interchange (loop2
, depth1
, depth2
);
554 /* Sync the transformed LST information and the PBB scatterings
555 before using the scatterings in the data dependence analysis. */
556 if (before
|| nest
|| after
)
558 transformed
= lst_substitute_3 (SCOP_TRANSFORMED_SCHEDULE (scop
), loop1
,
559 before
, nest
, after
);
560 lst_update_scattering (transformed
);
561 free_lst (transformed
);
564 if (graphite_legal_transform (scop
))
566 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
568 "Loops at depths %d and %d will be interchanged.\n",
571 /* Transform the SCOP_TRANSFORMED_SCHEDULE of the SCOP. */
572 lst_insert_in_sequence (before
, loop1
, true);
573 lst_insert_in_sequence (after
, loop1
, false);
577 lst_replace (loop1
, nest
);
584 /* Undo the transform. */
588 lst_apply_interchange (loop2
, depth2
, depth1
);
592 /* Selects the inner loop in LST_SEQ (INNER_FATHER) to be interchanged
593 with the loop OUTER in LST_SEQ (OUTER_FATHER). */
596 lst_interchange_select_inner (scop_p scop
, lst_p outer_father
, int outer
,
602 gcc_assert (outer_father
603 && LST_LOOP_P (outer_father
)
604 && LST_LOOP_P (LST_SEQ (outer_father
)[outer
])
606 && LST_LOOP_P (inner_father
));
608 loop1
= LST_SEQ (outer_father
)[outer
];
610 FOR_EACH_VEC_ELT (LST_SEQ (inner_father
), inner
, loop2
)
611 if (LST_LOOP_P (loop2
)
612 && (lst_try_interchange_loops (scop
, loop1
, loop2
)
613 || lst_interchange_select_inner (scop
, outer_father
, outer
, loop2
)))
619 /* Interchanges all the loops of LOOP and the loops of its body that
620 are considered profitable to interchange. Return the number of
621 interchanged loops. OUTER is the index in LST_SEQ (LOOP) that
622 points to the next outer loop to be considered for interchange. */
625 lst_interchange_select_outer (scop_p scop
, lst_p loop
, int outer
)
632 if (!loop
|| !LST_LOOP_P (loop
))
635 father
= LST_LOOP_FATHER (loop
);
638 while (lst_interchange_select_inner (scop
, father
, outer
, loop
))
641 loop
= LST_SEQ (father
)[outer
];
645 if (LST_LOOP_P (loop
))
646 FOR_EACH_VEC_ELT (LST_SEQ (loop
), i
, l
)
648 res
+= lst_interchange_select_outer (scop
, l
, i
);
653 /* Interchanges all the loop depths that are considered profitable for
654 SCOP. Return the number of interchanged loops. */
657 scop_do_interchange (scop_p scop
)
659 int res
= lst_interchange_select_outer
660 (scop
, SCOP_TRANSFORMED_SCHEDULE (scop
), 0);
662 lst_update_scattering (SCOP_TRANSFORMED_SCHEDULE (scop
));