Daily bump.
[official-gcc.git] / gcc / graphite-interchange.c
blob9f30d2420c3e0ee878cbbb9b77b48da2fe0f62e1
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)
13 any later version.
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/>. */
24 #include "config.h"
26 #ifdef HAVE_isl
27 #include <isl/aff.h>
28 #include <isl/set.h>
29 #include <isl/map.h>
30 #include <isl/union_map.h>
31 #include <isl/ilp.h>
32 #include <isl/val.h>
34 /* Since ISL-0.13, the extern is in val_gmp.h. */
35 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
36 extern "C" {
37 #endif
38 #include <isl/val_gmp.h>
39 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
41 #endif
42 #endif
44 #include "system.h"
45 #include "coretypes.h"
46 #include "tree.h"
47 #include "predict.h"
48 #include "vec.h"
49 #include "hashtab.h"
50 #include "hash-set.h"
51 #include "machmode.h"
52 #include "tm.h"
53 #include "hard-reg-set.h"
54 #include "input.h"
55 #include "function.h"
56 #include "dominance.h"
57 #include "cfg.h"
58 #include "basic-block.h"
59 #include "tree-ssa-alias.h"
60 #include "internal-fn.h"
61 #include "gimple-expr.h"
62 #include "is-a.h"
63 #include "gimple.h"
64 #include "gimple-iterator.h"
65 #include "tree-ssa-loop.h"
66 #include "dumpfile.h"
67 #include "cfgloop.h"
68 #include "tree-chrec.h"
69 #include "tree-data-ref.h"
70 #include "tree-scalar-evolution.h"
71 #include "sese.h"
73 #ifdef HAVE_isl
74 #include "graphite-poly.h"
76 /* XXX isl rewrite following comment */
77 /* Builds a linear expression, of dimension DIM, representing PDR's
78 memory access:
80 L = r_{n}*r_{n-1}*...*r_{1}*s_{0} + ... + r_{n}*s_{n-1} + s_{n}.
82 For an array A[10][20] with two subscript locations s0 and s1, the
83 linear memory access is 20 * s0 + s1: a stride of 1 in subscript s0
84 corresponds to a memory stride of 20.
86 OFFSET is a number of dimensions to prepend before the
87 subscript dimensions: s_0, s_1, ..., s_n.
89 Thus, the final linear expression has the following format:
90 0 .. 0_{offset} | 0 .. 0_{nit} | 0 .. 0_{gd} | 0 | c_0 c_1 ... c_n
91 where the expression itself is:
92 c_0 * s_0 + c_1 * s_1 + ... c_n * s_n. */
94 static isl_constraint *
95 build_linearized_memory_access (isl_map *map, poly_dr_p pdr)
97 isl_constraint *res;
98 isl_local_space *ls = isl_local_space_from_space (isl_map_get_space (map));
99 unsigned offset, nsubs;
100 int i;
101 isl_ctx *ctx;
103 isl_val *size, *subsize, *size1;
105 res = isl_equality_alloc (ls);
106 ctx = isl_local_space_get_ctx (ls);
107 size = isl_val_int_from_ui (ctx, 1);
109 nsubs = isl_set_dim (pdr->extent, isl_dim_set);
110 /* -1 for the already included L dimension. */
111 offset = isl_map_dim (map, isl_dim_out) - 1 - nsubs;
112 res = isl_constraint_set_coefficient_si (res, isl_dim_out, offset + nsubs, -1);
113 /* Go through all subscripts from last to first. First dimension
114 is the alias set, ignore it. */
115 for (i = nsubs - 1; i >= 1; i--)
117 isl_space *dc;
118 isl_aff *aff;
120 size1 = isl_val_copy (size);
121 res = isl_constraint_set_coefficient_val (res, isl_dim_out, offset + i, size);
122 dc = isl_set_get_space (pdr->extent);
123 aff = isl_aff_zero_on_domain (isl_local_space_from_space (dc));
124 aff = isl_aff_set_coefficient_si (aff, isl_dim_in, i, 1);
125 subsize = isl_set_max_val (pdr->extent, aff);
126 isl_aff_free (aff);
127 size = isl_val_mul (size1, subsize);
130 isl_val_free (size);
132 return res;
135 /* Set STRIDE to the stride of PDR in memory by advancing by one in
136 the loop at DEPTH. */
138 static void
139 pdr_stride_in_loop (mpz_t stride, graphite_dim_t depth, poly_dr_p pdr)
141 poly_bb_p pbb = PDR_PBB (pdr);
142 isl_map *map;
143 isl_set *set;
144 isl_aff *aff;
145 isl_space *dc;
146 isl_constraint *lma, *c;
147 isl_val *islstride;
148 graphite_dim_t time_depth;
149 unsigned offset, nt;
150 unsigned i;
151 /* XXX isl rewrite following comments. */
152 /* Builds a partial difference equations and inserts them
153 into pointset powerset polyhedron P. Polyhedron is assumed
154 to have the format: T|I|T'|I'|G|S|S'|l1|l2.
156 TIME_DEPTH is the time dimension w.r.t. which we are
157 differentiating.
158 OFFSET represents the number of dimensions between
159 columns t_{time_depth} and t'_{time_depth}.
160 DIM_SCTR is the number of scattering dimensions. It is
161 essentially the dimensionality of the T vector.
163 The following equations are inserted into the polyhedron P:
164 | t_1 = t_1'
165 | ...
166 | t_{time_depth-1} = t'_{time_depth-1}
167 | t_{time_depth} = t'_{time_depth} + 1
168 | t_{time_depth+1} = t'_{time_depth + 1}
169 | ...
170 | t_{dim_sctr} = t'_{dim_sctr}. */
172 /* Add the equality: t_{time_depth} = t'_{time_depth} + 1.
173 This is the core part of this alogrithm, since this
174 constraint asks for the memory access stride (difference)
175 between two consecutive points in time dimensions. */
177 /* Add equalities:
178 | t1 = t1'
179 | ...
180 | t_{time_depth-1} = t'_{time_depth-1}
181 | t_{time_depth+1} = t'_{time_depth+1}
182 | ...
183 | t_{dim_sctr} = t'_{dim_sctr}
185 This means that all the time dimensions are equal except for
186 time_depth, where the constraint is t_{depth} = t'_{depth} + 1
187 step. More to this: we should be careful not to add equalities
188 to the 'coupled' dimensions, which happens when the one dimension
189 is stripmined dimension, and the other dimension corresponds
190 to the point loop inside stripmined dimension. */
192 /* pdr->accesses: [P1..nb_param,I1..nb_domain]->[a,S1..nb_subscript]
193 ??? [P] not used for PDRs?
194 pdr->extent: [a,S1..nb_subscript]
195 pbb->domain: [P1..nb_param,I1..nb_domain]
196 pbb->transformed: [P1..nb_param,I1..nb_domain]->[T1..Tnb_sctr]
197 [T] includes local vars (currently unused)
199 First we create [P,I] -> [T,a,S]. */
201 map = isl_map_flat_range_product (isl_map_copy (pbb->transformed),
202 isl_map_copy (pdr->accesses));
203 /* Add a dimension for L: [P,I] -> [T,a,S,L].*/
204 map = isl_map_add_dims (map, isl_dim_out, 1);
205 /* Build a constraint for "lma[S] - L == 0", effectively calculating
206 L in terms of subscripts. */
207 lma = build_linearized_memory_access (map, pdr);
208 /* And add it to the map, so we now have:
209 [P,I] -> [T,a,S,L] : lma([S]) == L. */
210 map = isl_map_add_constraint (map, lma);
212 /* Then we create [P,I,P',I'] -> [T,a,S,L,T',a',S',L']. */
213 map = isl_map_flat_product (map, isl_map_copy (map));
215 /* Now add the equality T[time_depth] == T'[time_depth]+1. This will
216 force L' to be the linear address at T[time_depth] + 1. */
217 time_depth = psct_dynamic_dim (pbb, depth);
218 /* Length of [a,S] plus [L] ... */
219 offset = 1 + isl_map_dim (pdr->accesses, isl_dim_out);
220 /* ... plus [T]. */
221 offset += isl_map_dim (pbb->transformed, isl_dim_out);
223 c = isl_equality_alloc (isl_local_space_from_space (isl_map_get_space (map)));
224 c = isl_constraint_set_coefficient_si (c, isl_dim_out, time_depth, 1);
225 c = isl_constraint_set_coefficient_si (c, isl_dim_out,
226 offset + time_depth, -1);
227 c = isl_constraint_set_constant_si (c, 1);
228 map = isl_map_add_constraint (map, c);
230 /* Now we equate most of the T/T' elements (making PITaSL nearly
231 the same is (PITaSL)', except for one dimension, namely for 'depth'
232 (an index into [I]), after translating to index into [T]. Take care
233 to not produce an empty map, which indicates we wanted to equate
234 two dimensions that are already coupled via the above time_depth
235 dimension. Happens with strip mining where several scatter dimension
236 are interdependend. */
237 /* Length of [T]. */
238 nt = pbb_nb_scattering_transform (pbb) + pbb_nb_local_vars (pbb);
239 for (i = 0; i < nt; i++)
240 if (i != time_depth)
242 isl_map *temp = isl_map_equate (isl_map_copy (map),
243 isl_dim_out, i,
244 isl_dim_out, offset + i);
245 if (isl_map_is_empty (temp))
246 isl_map_free (temp);
247 else
249 isl_map_free (map);
250 map = temp;
254 /* Now maximize the expression L' - L. */
255 set = isl_map_range (map);
256 dc = isl_set_get_space (set);
257 aff = isl_aff_zero_on_domain (isl_local_space_from_space (dc));
258 aff = isl_aff_set_coefficient_si (aff, isl_dim_in, offset - 1, -1);
259 aff = isl_aff_set_coefficient_si (aff, isl_dim_in, offset + offset - 1, 1);
260 islstride = isl_set_max_val (set, aff);
261 isl_val_get_num_gmp (islstride, stride);
262 isl_val_free (islstride);
263 isl_aff_free (aff);
264 isl_set_free (set);
266 if (dump_file && (dump_flags & TDF_DETAILS))
268 gmp_fprintf (dump_file, "\nStride in BB_%d, DR_%d, depth %d: %Zd ",
269 pbb_index (pbb), PDR_ID (pdr), (int) depth, stride);
273 /* Sets STRIDES to the sum of all the strides of the data references
274 accessed in LOOP at DEPTH. */
276 static void
277 memory_strides_in_loop_1 (lst_p loop, graphite_dim_t depth, mpz_t strides)
279 int i, j;
280 lst_p l;
281 poly_dr_p pdr;
282 mpz_t s, n;
284 mpz_init (s);
285 mpz_init (n);
287 FOR_EACH_VEC_ELT (LST_SEQ (loop), j, l)
288 if (LST_LOOP_P (l))
289 memory_strides_in_loop_1 (l, depth, strides);
290 else
291 FOR_EACH_VEC_ELT (PBB_DRS (LST_PBB (l)), i, pdr)
293 pdr_stride_in_loop (s, depth, pdr);
294 mpz_set_si (n, PDR_NB_REFS (pdr));
295 mpz_mul (s, s, n);
296 mpz_add (strides, strides, s);
299 mpz_clear (s);
300 mpz_clear (n);
303 /* Sets STRIDES to the sum of all the strides of the data references
304 accessed in LOOP at DEPTH. */
306 static void
307 memory_strides_in_loop (lst_p loop, graphite_dim_t depth, mpz_t strides)
309 if (mpz_cmp_si (loop->memory_strides, -1) == 0)
311 mpz_set_si (strides, 0);
312 memory_strides_in_loop_1 (loop, depth, strides);
314 else
315 mpz_set (strides, loop->memory_strides);
318 /* Return true when the interchange of loops LOOP1 and LOOP2 is
319 profitable.
321 Example:
323 | int a[100][100];
325 | int
326 | foo (int N)
328 | int j;
329 | int i;
331 | for (i = 0; i < N; i++)
332 | for (j = 0; j < N; j++)
333 | a[j][2 * i] += 1;
335 | return a[N][12];
338 The data access A[j][i] is described like this:
340 | i j N a s0 s1 1
341 | 0 0 0 1 0 0 -5 = 0
342 | 0 -1 0 0 1 0 0 = 0
343 |-2 0 0 0 0 1 0 = 0
344 | 0 0 0 0 1 0 0 >= 0
345 | 0 0 0 0 0 1 0 >= 0
346 | 0 0 0 0 -1 0 100 >= 0
347 | 0 0 0 0 0 -1 100 >= 0
349 The linearized memory access L to A[100][100] is:
351 | i j N a s0 s1 1
352 | 0 0 0 0 100 1 0
354 TODO: the shown format is not valid as it does not show the fact
355 that the iteration domain "i j" is transformed using the scattering.
357 Next, to measure the impact of iterating once in loop "i", we build
358 a maximization problem: first, we add to DR accesses the dimensions
359 k, s2, s3, L1 = 100 * s0 + s1, L2, and D1: this is the polyhedron P1.
360 L1 and L2 are the linearized memory access functions.
362 | i j N a s0 s1 k s2 s3 L1 L2 D1 1
363 | 0 0 0 1 0 0 0 0 0 0 0 0 -5 = 0 alias = 5
364 | 0 -1 0 0 1 0 0 0 0 0 0 0 0 = 0 s0 = j
365 |-2 0 0 0 0 1 0 0 0 0 0 0 0 = 0 s1 = 2 * i
366 | 0 0 0 0 1 0 0 0 0 0 0 0 0 >= 0
367 | 0 0 0 0 0 1 0 0 0 0 0 0 0 >= 0
368 | 0 0 0 0 -1 0 0 0 0 0 0 0 100 >= 0
369 | 0 0 0 0 0 -1 0 0 0 0 0 0 100 >= 0
370 | 0 0 0 0 100 1 0 0 0 -1 0 0 0 = 0 L1 = 100 * s0 + s1
372 Then, we generate the polyhedron P2 by interchanging the dimensions
373 (s0, s2), (s1, s3), (L1, L2), (k, i)
375 | i j N a s0 s1 k s2 s3 L1 L2 D1 1
376 | 0 0 0 1 0 0 0 0 0 0 0 0 -5 = 0 alias = 5
377 | 0 -1 0 0 0 0 0 1 0 0 0 0 0 = 0 s2 = j
378 | 0 0 0 0 0 0 -2 0 1 0 0 0 0 = 0 s3 = 2 * k
379 | 0 0 0 0 0 0 0 1 0 0 0 0 0 >= 0
380 | 0 0 0 0 0 0 0 0 1 0 0 0 0 >= 0
381 | 0 0 0 0 0 0 0 -1 0 0 0 0 100 >= 0
382 | 0 0 0 0 0 0 0 0 -1 0 0 0 100 >= 0
383 | 0 0 0 0 0 0 0 100 1 0 -1 0 0 = 0 L2 = 100 * s2 + s3
385 then we add to P2 the equality k = i + 1:
387 |-1 0 0 0 0 0 1 0 0 0 0 0 -1 = 0 k = i + 1
389 and finally we maximize the expression "D1 = max (P1 inter P2, L2 - L1)".
391 Similarly, to determine the impact of one iteration on loop "j", we
392 interchange (k, j), we add "k = j + 1", and we compute D2 the
393 maximal value of the difference.
395 Finally, the profitability test is D1 < D2: if in the outer loop
396 the strides are smaller than in the inner loop, then it is
397 profitable to interchange the loops at DEPTH1 and DEPTH2. */
399 static bool
400 lst_interchange_profitable_p (lst_p nest, int depth1, int depth2)
402 mpz_t d1, d2;
403 bool res;
405 gcc_assert (depth1 < depth2);
407 mpz_init (d1);
408 mpz_init (d2);
410 memory_strides_in_loop (nest, depth1, d1);
411 memory_strides_in_loop (nest, depth2, d2);
413 res = mpz_cmp (d1, d2) < 0;
415 mpz_clear (d1);
416 mpz_clear (d2);
418 return res;
421 /* Interchanges the loops at DEPTH1 and DEPTH2 of the original
422 scattering and assigns the resulting polyhedron to the transformed
423 scattering. */
425 static void
426 pbb_interchange_loop_depths (graphite_dim_t depth1, graphite_dim_t depth2,
427 poly_bb_p pbb)
429 unsigned i;
430 unsigned dim1 = psct_dynamic_dim (pbb, depth1);
431 unsigned dim2 = psct_dynamic_dim (pbb, depth2);
432 isl_space *d = isl_map_get_space (pbb->transformed);
433 isl_space *d1 = isl_space_range (d);
434 unsigned n = isl_space_dim (d1, isl_dim_out);
435 isl_space *d2 = isl_space_add_dims (d1, isl_dim_in, n);
436 isl_map *x = isl_map_universe (d2);
438 x = isl_map_equate (x, isl_dim_in, dim1, isl_dim_out, dim2);
439 x = isl_map_equate (x, isl_dim_in, dim2, isl_dim_out, dim1);
441 for (i = 0; i < n; i++)
442 if (i != dim1 && i != dim2)
443 x = isl_map_equate (x, isl_dim_in, i, isl_dim_out, i);
445 pbb->transformed = isl_map_apply_range (pbb->transformed, x);
448 /* Apply the interchange of loops at depths DEPTH1 and DEPTH2 to all
449 the statements below LST. */
451 static void
452 lst_apply_interchange (lst_p lst, int depth1, int depth2)
454 if (!lst)
455 return;
457 if (LST_LOOP_P (lst))
459 int i;
460 lst_p l;
462 FOR_EACH_VEC_ELT (LST_SEQ (lst), i, l)
463 lst_apply_interchange (l, depth1, depth2);
465 else
466 pbb_interchange_loop_depths (depth1, depth2, LST_PBB (lst));
469 /* Return true when the nest starting at LOOP1 and ending on LOOP2 is
470 perfect: i.e. there are no sequence of statements. */
472 static bool
473 lst_perfectly_nested_p (lst_p loop1, lst_p loop2)
475 if (loop1 == loop2)
476 return true;
478 if (!LST_LOOP_P (loop1))
479 return false;
481 return LST_SEQ (loop1).length () == 1
482 && lst_perfectly_nested_p (LST_SEQ (loop1)[0], loop2);
485 /* Transform the loop nest between LOOP1 and LOOP2 into a perfect
486 nest. To continue the naming tradition, this function is called
487 after perfect_nestify. NEST is set to the perfectly nested loop
488 that is created. BEFORE/AFTER are set to the loops distributed
489 before/after the loop NEST. */
491 static void
492 lst_perfect_nestify (lst_p loop1, lst_p loop2, lst_p *before,
493 lst_p *nest, lst_p *after)
495 poly_bb_p first, last;
497 gcc_assert (loop1 && loop2
498 && loop1 != loop2
499 && LST_LOOP_P (loop1) && LST_LOOP_P (loop2));
501 first = LST_PBB (lst_find_first_pbb (loop2));
502 last = LST_PBB (lst_find_last_pbb (loop2));
504 *before = copy_lst (loop1);
505 *nest = copy_lst (loop1);
506 *after = copy_lst (loop1);
508 lst_remove_all_before_including_pbb (*before, first, false);
509 lst_remove_all_before_including_pbb (*after, last, true);
511 lst_remove_all_before_excluding_pbb (*nest, first, true);
512 lst_remove_all_before_excluding_pbb (*nest, last, false);
514 if (lst_empty_p (*before))
516 free_lst (*before);
517 *before = NULL;
519 if (lst_empty_p (*after))
521 free_lst (*after);
522 *after = NULL;
524 if (lst_empty_p (*nest))
526 free_lst (*nest);
527 *nest = NULL;
531 /* Try to interchange LOOP1 with LOOP2 for all the statements of the
532 body of LOOP2. LOOP1 contains LOOP2. Return true if it did the
533 interchange. */
535 static bool
536 lst_try_interchange_loops (scop_p scop, lst_p loop1, lst_p loop2)
538 int depth1 = lst_depth (loop1);
539 int depth2 = lst_depth (loop2);
540 lst_p transformed;
542 lst_p before = NULL, nest = NULL, after = NULL;
544 if (!lst_perfectly_nested_p (loop1, loop2))
545 lst_perfect_nestify (loop1, loop2, &before, &nest, &after);
547 if (!lst_interchange_profitable_p (loop2, depth1, depth2))
548 return false;
550 lst_apply_interchange (loop2, depth1, depth2);
552 /* Sync the transformed LST information and the PBB scatterings
553 before using the scatterings in the data dependence analysis. */
554 if (before || nest || after)
556 transformed = lst_substitute_3 (SCOP_TRANSFORMED_SCHEDULE (scop), loop1,
557 before, nest, after);
558 lst_update_scattering (transformed);
559 free_lst (transformed);
562 if (graphite_legal_transform (scop))
564 if (dump_file && (dump_flags & TDF_DETAILS))
565 fprintf (dump_file,
566 "Loops at depths %d and %d will be interchanged.\n",
567 depth1, depth2);
569 /* Transform the SCOP_TRANSFORMED_SCHEDULE of the SCOP. */
570 lst_insert_in_sequence (before, loop1, true);
571 lst_insert_in_sequence (after, loop1, false);
573 if (nest)
575 lst_replace (loop1, nest);
576 free_lst (loop1);
579 return true;
582 /* Undo the transform. */
583 free_lst (before);
584 free_lst (nest);
585 free_lst (after);
586 lst_apply_interchange (loop2, depth2, depth1);
587 return false;
590 /* Selects the inner loop in LST_SEQ (INNER_FATHER) to be interchanged
591 with the loop OUTER in LST_SEQ (OUTER_FATHER). */
593 static bool
594 lst_interchange_select_inner (scop_p scop, lst_p outer_father, int outer,
595 lst_p inner_father)
597 int inner;
598 lst_p loop1, loop2;
600 gcc_assert (outer_father
601 && LST_LOOP_P (outer_father)
602 && LST_LOOP_P (LST_SEQ (outer_father)[outer])
603 && inner_father
604 && LST_LOOP_P (inner_father));
606 loop1 = LST_SEQ (outer_father)[outer];
608 FOR_EACH_VEC_ELT (LST_SEQ (inner_father), inner, loop2)
609 if (LST_LOOP_P (loop2)
610 && (lst_try_interchange_loops (scop, loop1, loop2)
611 || lst_interchange_select_inner (scop, outer_father, outer, loop2)))
612 return true;
614 return false;
617 /* Interchanges all the loops of LOOP and the loops of its body that
618 are considered profitable to interchange. Return the number of
619 interchanged loops. OUTER is the index in LST_SEQ (LOOP) that
620 points to the next outer loop to be considered for interchange. */
622 static int
623 lst_interchange_select_outer (scop_p scop, lst_p loop, int outer)
625 lst_p l;
626 int res = 0;
627 int i = 0;
628 lst_p father;
630 if (!loop || !LST_LOOP_P (loop))
631 return 0;
633 father = LST_LOOP_FATHER (loop);
634 if (father)
636 while (lst_interchange_select_inner (scop, father, outer, loop))
638 res++;
639 loop = LST_SEQ (father)[outer];
643 if (LST_LOOP_P (loop))
644 FOR_EACH_VEC_ELT (LST_SEQ (loop), i, l)
645 if (LST_LOOP_P (l))
646 res += lst_interchange_select_outer (scop, l, i);
648 return res;
651 /* Interchanges all the loop depths that are considered profitable for
652 SCOP. Return the number of interchanged loops. */
655 scop_do_interchange (scop_p scop)
657 int res = lst_interchange_select_outer
658 (scop, SCOP_TRANSFORMED_SCHEDULE (scop), 0);
660 lst_update_scattering (SCOP_TRANSFORMED_SCHEDULE (scop));
662 return res;
666 #endif