OSDN Git Service

Resolve CLooG's value_* macros to their respective mpz_* counterparts.
[pf3gnuchains/gcc-fork.git] / gcc / graphite-interchange.c
1 /* Interchange heuristics and transform for loop interchange on
2    polyhedral representation.
3
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>.
7
8 This file is part of GCC.
9
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.
14
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.
19
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/>.  */
23 #include "config.h"
24 #include "system.h"
25 #include "coretypes.h"
26 #include "tm.h"
27 #include "ggc.h"
28 #include "tree.h"
29 #include "rtl.h"
30 #include "output.h"
31 #include "basic-block.h"
32 #include "diagnostic.h"
33 #include "tree-flow.h"
34 #include "toplev.h"
35 #include "tree-dump.h"
36 #include "timevar.h"
37 #include "cfgloop.h"
38 #include "tree-chrec.h"
39 #include "tree-data-ref.h"
40 #include "tree-scalar-evolution.h"
41 #include "tree-pass.h"
42 #include "domwalk.h"
43 #include "value-prof.h"
44 #include "pointer-set.h"
45 #include "gimple.h"
46 #include "params.h"
47
48 #ifdef HAVE_cloog
49 #include "cloog/cloog.h"
50 #include "ppl_c.h"
51 #include "sese.h"
52 #include "graphite-ppl.h"
53 #include "graphite.h"
54 #include "graphite-poly.h"
55
56 /* Builds a linear expression, of dimension DIM, representing PDR's
57    memory access:
58
59    L = r_{n}*r_{n-1}*...*r_{1}*s_{0} + ... + r_{n}*s_{n-1} + s_{n}.
60
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.
64
65    OFFSET is a number of dimensions to prepend before the
66    subscript dimensions: s_0, s_1, ..., s_n.
67
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.  */
72
73 static ppl_Linear_Expression_t
74 build_linearized_memory_access (ppl_dimension_type offset, poly_dr_p pdr)
75 {
76   ppl_Linear_Expression_t res;
77   ppl_Linear_Expression_t le;
78   ppl_dimension_type i;
79   ppl_dimension_type first = pdr_subscript_dim (pdr, 0);
80   ppl_dimension_type last = pdr_subscript_dim (pdr, PDR_NB_SUBSCRIPTS (pdr));
81   Value size, sub_size;
82   graphite_dim_t dim = offset + pdr_dim (pdr);
83
84   ppl_new_Linear_Expression_with_dimension (&res, dim);
85
86   mpz_init (size);
87   mpz_set_si (size, 1);
88   mpz_init (sub_size);
89   mpz_set_si (sub_size, 1);
90
91   for (i = last - 1; i >= first; i--)
92     {
93       ppl_set_coef_gmp (res, i + offset, size);
94
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       mpz_mul (size, size, sub_size);
99       ppl_delete_Linear_Expression (le);
100     }
101
102   mpz_clear (sub_size);
103   mpz_clear (size);
104   return res;
105 }
106
107 /* Builds a partial difference equations and inserts them
108    into pointset powerset polyhedron P.  Polyhedron is assumed
109    to have the format: T|I|T'|I'|G|S|S'|l1|l2.
110
111    TIME_DEPTH is the time dimension w.r.t. which we are
112    differentiating.
113    OFFSET represents the number of dimensions between
114    columns t_{time_depth} and t'_{time_depth}.
115    DIM_SCTR is the number of scattering dimensions.  It is
116    essentially the dimensionality of the T vector.
117
118    The following equations are inserted into the polyhedron P:
119     | t_1 = t_1'
120     | ...
121     | t_{time_depth-1} = t'_{time_depth-1}
122     | t_{time_depth} = t'_{time_depth} + 1
123     | t_{time_depth+1} = t'_{time_depth + 1}
124     | ...
125     | t_{dim_sctr} = t'_{dim_sctr}.  */
126
127 static void
128 build_partial_difference (ppl_Pointset_Powerset_C_Polyhedron_t *p,
129                           ppl_dimension_type time_depth,
130                           ppl_dimension_type offset,
131                           ppl_dimension_type dim_sctr)
132 {
133   ppl_Constraint_t new_cstr;
134   ppl_Linear_Expression_t le;
135   ppl_dimension_type i;
136   ppl_dimension_type dim;
137   ppl_Pointset_Powerset_C_Polyhedron_t temp;
138
139   /* Add the equality: t_{time_depth} = t'_{time_depth} + 1.
140      This is the core part of this alogrithm, since this
141      constraint asks for the memory access stride (difference)
142      between two consecutive points in time dimensions.  */
143
144   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (*p, &dim);
145   ppl_new_Linear_Expression_with_dimension (&le, dim);
146   ppl_set_coef (le, time_depth, 1);
147   ppl_set_coef (le, time_depth + offset, -1);
148   ppl_set_inhomogeneous (le, 1);
149   ppl_new_Constraint (&new_cstr, le, PPL_CONSTRAINT_TYPE_EQUAL);
150   ppl_Pointset_Powerset_C_Polyhedron_add_constraint (*p, new_cstr);
151   ppl_delete_Linear_Expression (le);
152   ppl_delete_Constraint (new_cstr);
153
154   /* Add equalities:
155      | t1 = t1'
156      | ...
157      | t_{time_depth-1} = t'_{time_depth-1}
158      | t_{time_depth+1} = t'_{time_depth+1}
159      | ...
160      | t_{dim_sctr} = t'_{dim_sctr}
161
162      This means that all the time dimensions are equal except for
163      time_depth, where the constraint is t_{depth} = t'_{depth} + 1
164      step.  More to this: we should be carefull not to add equalities
165      to the 'coupled' dimensions, which happens when the one dimension
166      is stripmined dimension, and the other dimension corresponds
167      to the point loop inside stripmined dimension.  */
168
169   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron (&temp, *p);
170
171   for (i = 0; i < dim_sctr; i++)
172     if (i != time_depth)
173       {
174         ppl_new_Linear_Expression_with_dimension (&le, dim);
175         ppl_set_coef (le, i, 1);
176         ppl_set_coef (le, i + offset, -1);
177         ppl_new_Constraint (&new_cstr, le, PPL_CONSTRAINT_TYPE_EQUAL);
178         ppl_Pointset_Powerset_C_Polyhedron_add_constraint (temp, new_cstr);
179
180         if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (temp))
181           {
182             ppl_delete_Pointset_Powerset_C_Polyhedron (temp);
183             ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron (&temp, *p);
184           }
185         else
186           ppl_Pointset_Powerset_C_Polyhedron_add_constraint (*p, new_cstr);
187         ppl_delete_Linear_Expression (le);
188         ppl_delete_Constraint (new_cstr);
189       }
190
191   ppl_delete_Pointset_Powerset_C_Polyhedron (temp);
192 }
193
194
195 /* Set STRIDE to the stride of PDR in memory by advancing by one in
196    the loop at DEPTH.  */
197
198 static void
199 pdr_stride_in_loop (Value stride, graphite_dim_t depth, poly_dr_p pdr)
200 {
201   ppl_dimension_type time_depth;
202   ppl_Linear_Expression_t le, lma;
203   ppl_Constraint_t new_cstr;
204   ppl_dimension_type i, *map;
205   ppl_Pointset_Powerset_C_Polyhedron_t p1, p2, sctr;
206   graphite_dim_t nb_subscripts = PDR_NB_SUBSCRIPTS (pdr) + 1;
207   poly_bb_p pbb = PDR_PBB (pdr);
208   ppl_dimension_type offset = pbb_nb_scattering_transform (pbb)
209                               + pbb_nb_local_vars (pbb)
210                               + pbb_dim_iter_domain (pbb);
211   ppl_dimension_type offsetg = offset + pbb_nb_params (pbb);
212   ppl_dimension_type dim_sctr = pbb_nb_scattering_transform (pbb)
213                                 + pbb_nb_local_vars (pbb);
214   ppl_dimension_type dim_L1 = offset + offsetg + 2 * nb_subscripts;
215   ppl_dimension_type dim_L2 = offset + offsetg + 2 * nb_subscripts + 1;
216   ppl_dimension_type new_dim = offset + offsetg + 2 * nb_subscripts + 2;
217
218   /* The resulting polyhedron should have the following format:
219      T|I|T'|I'|G|S|S'|l1|l2
220      where:
221      | T = t_1..t_{dim_sctr}
222      | I = i_1..i_{dim_iter_domain}
223      | T'= t'_1..t'_{dim_sctr}
224      | I'= i'_1..i'_{dim_iter_domain}
225      | G = g_1..g_{nb_params}
226      | S = s_1..s_{nb_subscripts}
227      | S'= s'_1..s'_{nb_subscripts}
228      | l1 and l2 are scalars.
229
230      Some invariants:
231      offset = dim_sctr + dim_iter_domain + nb_local_vars
232      offsetg = dim_sctr + dim_iter_domain + nb_local_vars + nb_params.  */
233
234   /* Construct the T|I|0|0|G|0|0|0|0 part.  */
235   {
236     ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
237       (&sctr, PBB_TRANSFORMED_SCATTERING (pbb));
238     ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed
239       (sctr, 2 * nb_subscripts + 2);
240     ppl_insert_dimensions_pointset (sctr, offset, offset);
241   }
242
243   /* Construct the 0|I|0|0|G|S|0|0|0 part.  */
244   {
245     ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
246       (&p1, PDR_ACCESSES (pdr));
247     ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed
248       (p1, nb_subscripts + 2);
249     ppl_insert_dimensions_pointset (p1, 0, dim_sctr);
250     ppl_insert_dimensions_pointset (p1, offset, offset);
251   }
252
253   /* Construct the 0|0|0|0|0|S|0|l1|0 part.  */
254   {
255     lma = build_linearized_memory_access (offset + dim_sctr, pdr);
256     ppl_set_coef (lma, dim_L1, -1);
257     ppl_new_Constraint (&new_cstr, lma, PPL_CONSTRAINT_TYPE_EQUAL);
258     ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p1, new_cstr);
259     ppl_delete_Linear_Expression (lma);
260     ppl_delete_Constraint (new_cstr);
261   }
262
263   /* Now intersect all the parts to get the polyhedron P1:
264      T|I|0|0|G|0|0|0 |0
265      0|I|0|0|G|S|0|0 |0
266      0|0|0|0|0|S|0|l1|0
267      ------------------
268      T|I|0|0|G|S|0|l1|0.  */
269
270   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (p1, sctr);
271   ppl_delete_Pointset_Powerset_C_Polyhedron (sctr);
272
273   /* Build P2, which would have the following form:
274      0|0|T'|I'|G|0|S'|0|l2
275
276      P2 is built, by remapping the P1 polyhedron:
277      T|I|0|0|G|S|0|l1|0
278
279      using the following mapping:
280      T->T'
281      I->I'
282      S->S'
283      l1->l2.  */
284   {
285     ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
286       (&p2, p1);
287
288     map = ppl_new_id_map (new_dim);
289
290     /* TI -> T'I'.  */
291     for (i = 0; i < offset; i++)
292       ppl_interchange (map, i, i + offset);
293
294     /* l1 -> l2.  */
295     ppl_interchange (map, dim_L1, dim_L2);
296
297     /* S -> S'.  */
298     for (i = 0; i < nb_subscripts; i++)
299       ppl_interchange (map, offset + offsetg + i,
300                        offset + offsetg + nb_subscripts + i);
301
302     ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (p2, map, new_dim);
303     free (map);
304   }
305
306   time_depth = psct_dynamic_dim (pbb, depth);
307
308   /* P1 = P1 inter P2.  */
309   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (p1, p2);
310   build_partial_difference (&p1, time_depth, offset, dim_sctr);
311
312   /* Maximise the expression L2 - L1.  */
313   {
314     ppl_new_Linear_Expression_with_dimension (&le, new_dim);
315     ppl_set_coef (le, dim_L2, 1);
316     ppl_set_coef (le, dim_L1, -1);
317     ppl_max_for_le_pointset (p1, le, stride);
318   }
319
320   if (dump_file && (dump_flags & TDF_DETAILS))
321     {
322       char *str;
323       void (*gmp_free) (void *, size_t);
324       
325       fprintf (dump_file, "\nStride in BB_%d, DR_%d, depth %d:",
326                pbb_index (pbb), PDR_ID (pdr), (int) depth);
327       str = mpz_get_str (0, 10, stride);
328       fprintf (dump_file, "  %s ", str);
329       mp_get_memory_functions (NULL, NULL, &gmp_free);
330       (*gmp_free) (str, strlen (str) + 1);
331     }
332
333   ppl_delete_Pointset_Powerset_C_Polyhedron (p1);
334   ppl_delete_Pointset_Powerset_C_Polyhedron (p2);
335   ppl_delete_Linear_Expression (le);
336 }
337
338
339 /* Sets STRIDES to the sum of all the strides of the data references
340    accessed in LOOP at DEPTH.  */
341
342 static void
343 memory_strides_in_loop_1 (lst_p loop, graphite_dim_t depth, Value strides)
344 {
345   int i, j;
346   lst_p l;
347   poly_dr_p pdr;
348   Value s, n;
349
350   mpz_init (s);
351   mpz_init (n);
352
353   for (j = 0; VEC_iterate (lst_p, LST_SEQ (loop), j, l); j++)
354     if (LST_LOOP_P (l))
355       memory_strides_in_loop_1 (l, depth, strides);
356     else
357       for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (LST_PBB (l)), i, pdr); i++)
358         {
359           pdr_stride_in_loop (s, depth, pdr);
360           mpz_set_si (n, PDR_NB_REFS (pdr));
361           mpz_mul (s, s, n);
362           mpz_add (strides, strides, s);
363         }
364
365   mpz_clear (s);
366   mpz_clear (n);
367 }
368
369 /* Sets STRIDES to the sum of all the strides of the data references
370    accessed in LOOP at DEPTH.  */
371
372 static void
373 memory_strides_in_loop (lst_p loop, graphite_dim_t depth, Value strides)
374 {
375   if (mpz_cmp_si (loop->memory_strides, -1) == 0)
376     {
377       mpz_set_si (strides, 0);
378       memory_strides_in_loop_1 (loop, depth, strides);
379     }
380   else
381     mpz_set (strides, loop->memory_strides);
382 }
383
384 /* Return true when the interchange of loops LOOP1 and LOOP2 is
385    profitable.
386
387    Example:
388
389    | int a[100][100];
390    |
391    | int
392    | foo (int N)
393    | {
394    |   int j;
395    |   int i;
396    |
397    |   for (i = 0; i < N; i++)
398    |     for (j = 0; j < N; j++)
399    |       a[j][2 * i] += 1;
400    |
401    |   return a[N][12];
402    | }
403
404    The data access A[j][i] is described like this:
405
406    | i   j   N   a  s0  s1   1
407    | 0   0   0   1   0   0  -5    = 0
408    | 0  -1   0   0   1   0   0    = 0
409    |-2   0   0   0   0   1   0    = 0
410    | 0   0   0   0   1   0   0   >= 0
411    | 0   0   0   0   0   1   0   >= 0
412    | 0   0   0   0  -1   0 100   >= 0
413    | 0   0   0   0   0  -1 100   >= 0
414
415    The linearized memory access L to A[100][100] is:
416
417    | i   j   N   a  s0  s1   1
418    | 0   0   0   0 100   1   0
419
420    TODO: the shown format is not valid as it does not show the fact
421    that the iteration domain "i j" is transformed using the scattering.
422
423    Next, to measure the impact of iterating once in loop "i", we build
424    a maximization problem: first, we add to DR accesses the dimensions
425    k, s2, s3, L1 = 100 * s0 + s1, L2, and D1: this is the polyhedron P1.
426    L1 and L2 are the linearized memory access functions.
427
428    | i   j   N   a  s0  s1   k  s2  s3  L1  L2  D1   1
429    | 0   0   0   1   0   0   0   0   0   0   0   0  -5    = 0  alias = 5
430    | 0  -1   0   0   1   0   0   0   0   0   0   0   0    = 0  s0 = j
431    |-2   0   0   0   0   1   0   0   0   0   0   0   0    = 0  s1 = 2 * i
432    | 0   0   0   0   1   0   0   0   0   0   0   0   0   >= 0
433    | 0   0   0   0   0   1   0   0   0   0   0   0   0   >= 0
434    | 0   0   0   0  -1   0   0   0   0   0   0   0 100   >= 0
435    | 0   0   0   0   0  -1   0   0   0   0   0   0 100   >= 0
436    | 0   0   0   0 100   1   0   0   0  -1   0   0   0    = 0  L1 = 100 * s0 + s1
437
438    Then, we generate the polyhedron P2 by interchanging the dimensions
439    (s0, s2), (s1, s3), (L1, L2), (k, i)
440
441    | i   j   N   a  s0  s1   k  s2  s3  L1  L2  D1   1
442    | 0   0   0   1   0   0   0   0   0   0   0   0  -5    = 0  alias = 5
443    | 0  -1   0   0   0   0   0   1   0   0   0   0   0    = 0  s2 = j
444    | 0   0   0   0   0   0  -2   0   1   0   0   0   0    = 0  s3 = 2 * k
445    | 0   0   0   0   0   0   0   1   0   0   0   0   0   >= 0
446    | 0   0   0   0   0   0   0   0   1   0   0   0   0   >= 0
447    | 0   0   0   0   0   0   0  -1   0   0   0   0 100   >= 0
448    | 0   0   0   0   0   0   0   0  -1   0   0   0 100   >= 0
449    | 0   0   0   0   0   0   0 100   1   0  -1   0   0    = 0  L2 = 100 * s2 + s3
450
451    then we add to P2 the equality k = i + 1:
452
453    |-1   0   0   0   0   0   1   0   0   0   0   0  -1    = 0  k = i + 1
454
455    and finally we maximize the expression "D1 = max (P1 inter P2, L2 - L1)".
456
457    Similarly, to determine the impact of one iteration on loop "j", we
458    interchange (k, j), we add "k = j + 1", and we compute D2 the
459    maximal value of the difference.
460
461    Finally, the profitability test is D1 < D2: if in the outer loop
462    the strides are smaller than in the inner loop, then it is
463    profitable to interchange the loops at DEPTH1 and DEPTH2.  */
464
465 static bool
466 lst_interchange_profitable_p (lst_p loop1, lst_p loop2)
467 {
468   Value d1, d2;
469   bool res;
470
471   gcc_assert (loop1 && loop2
472               && LST_LOOP_P (loop1) && LST_LOOP_P (loop2)
473               && lst_depth (loop1) < lst_depth (loop2));
474
475   mpz_init (d1);
476   mpz_init (d2);
477
478   memory_strides_in_loop (loop1, lst_depth (loop1), d1);
479   memory_strides_in_loop (loop2, lst_depth (loop2), d2);
480
481   res = value_lt (d1, d2);
482
483   mpz_clear (d1);
484   mpz_clear (d2);
485
486   return res;
487 }
488
489 /* Interchanges the loops at DEPTH1 and DEPTH2 of the original
490    scattering and assigns the resulting polyhedron to the transformed
491    scattering.  */
492
493 static void
494 pbb_interchange_loop_depths (graphite_dim_t depth1, graphite_dim_t depth2,
495                              poly_bb_p pbb)
496 {
497   ppl_dimension_type i, dim;
498   ppl_dimension_type *map;
499   ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
500   ppl_dimension_type dim1 = psct_dynamic_dim (pbb, depth1);
501   ppl_dimension_type dim2 = psct_dynamic_dim (pbb, depth2);
502
503   ppl_Polyhedron_space_dimension (poly, &dim);
504   map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
505
506   for (i = 0; i < dim; i++)
507     map[i] = i;
508
509   map[dim1] = dim2;
510   map[dim2] = dim1;
511
512   ppl_Polyhedron_map_space_dimensions (poly, map, dim);
513   free (map);
514 }
515
516 /* Apply the interchange of loops at depths DEPTH1 and DEPTH2 to all
517    the statements below LST.  */
518
519 static void
520 lst_apply_interchange (lst_p lst, int depth1, int depth2)
521 {
522   if (!lst)
523     return;
524
525   if (LST_LOOP_P (lst))
526     {
527       int i;
528       lst_p l;
529
530       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
531         lst_apply_interchange (l, depth1, depth2);
532     }
533   else
534     pbb_interchange_loop_depths (depth1, depth2, LST_PBB (lst));
535 }
536
537 /* Return true when the nest starting at LOOP1 and ending on LOOP2 is
538    perfect: i.e. there are no sequence of statements.  */
539
540 static bool
541 lst_perfectly_nested_p (lst_p loop1, lst_p loop2)
542 {
543   if (loop1 == loop2)
544     return true;
545
546   if (!LST_LOOP_P (loop1))
547     return false;
548
549   return VEC_length (lst_p, LST_SEQ (loop1)) == 1
550     && lst_perfectly_nested_p (VEC_index (lst_p, LST_SEQ (loop1), 0), loop2);
551 }
552
553 /* Transform the loop nest between LOOP1 and LOOP2 into a perfect
554    nest.  To continue the naming tradition, this function is called
555    after perfect_nestify.  NEST is set to the perfectly nested loop
556    that is created.  BEFORE/AFTER are set to the loops distributed
557    before/after the loop NEST.  */
558
559 static void
560 lst_perfect_nestify (lst_p loop1, lst_p loop2, lst_p *before,
561                      lst_p *nest, lst_p *after)
562 {
563   poly_bb_p first, last;
564
565   gcc_assert (loop1 && loop2
566               && loop1 != loop2
567               && LST_LOOP_P (loop1) && LST_LOOP_P (loop2));
568
569   first = LST_PBB (lst_find_first_pbb (loop2));
570   last = LST_PBB (lst_find_last_pbb (loop2));
571
572   *before = copy_lst (loop1);
573   *nest = copy_lst (loop1);
574   *after = copy_lst (loop1);
575
576   lst_remove_all_before_including_pbb (*before, first, false);
577   lst_remove_all_before_including_pbb (*after, last, true);
578
579   lst_remove_all_before_excluding_pbb (*nest, first, true);
580   lst_remove_all_before_excluding_pbb (*nest, last, false);
581
582   if (lst_empty_p (*before))
583     {
584       free_lst (*before);
585       *before = NULL;
586     }
587   if (lst_empty_p (*after))
588     {
589       free_lst (*after);
590       *after = NULL;
591     }
592   if (lst_empty_p (*nest))
593     {
594       free_lst (*nest);
595       *nest = NULL;
596     }
597 }
598
599 /* Try to interchange LOOP1 with LOOP2 for all the statements of the
600    body of LOOP2.  LOOP1 contains LOOP2.  Return true if it did the
601    interchange.  */
602
603 static bool
604 lst_try_interchange_loops (scop_p scop, lst_p loop1, lst_p loop2)
605 {
606   int depth1 = lst_depth (loop1);
607   int depth2 = lst_depth (loop2);
608   lst_p transformed;
609
610   lst_p before = NULL, nest = NULL, after = NULL;
611
612   if (!lst_interchange_profitable_p (loop1, loop2))
613     return false;
614
615   if (!lst_perfectly_nested_p (loop1, loop2))
616     lst_perfect_nestify (loop1, loop2, &before, &nest, &after);
617
618   lst_apply_interchange (loop2, depth1, depth2);
619
620   /* Sync the transformed LST information and the PBB scatterings
621      before using the scatterings in the data dependence analysis.  */
622   if (before || nest || after)
623     {
624       transformed = lst_substitute_3 (SCOP_TRANSFORMED_SCHEDULE (scop), loop1,
625                                       before, nest, after);
626       lst_update_scattering (transformed);
627       free_lst (transformed);
628     }
629
630   if (graphite_legal_transform (scop))
631     {
632       if (dump_file && (dump_flags & TDF_DETAILS))
633         fprintf (dump_file,
634                  "Loops at depths %d and %d will be interchanged.\n",
635                  depth1, depth2);
636
637       /* Transform the SCOP_TRANSFORMED_SCHEDULE of the SCOP.  */
638       lst_insert_in_sequence (before, loop1, true);
639       lst_insert_in_sequence (after, loop1, false);
640
641       if (nest)
642         {
643           lst_replace (loop1, nest);
644           free_lst (loop1);
645         }
646
647       return true;
648     }
649
650   /* Undo the transform.  */
651   free_lst (before);
652   free_lst (nest);
653   free_lst (after);
654   lst_apply_interchange (loop2, depth2, depth1);
655   return false;
656 }
657
658 /* Selects the inner loop in LST_SEQ (INNER_FATHER) to be interchanged
659    with the loop OUTER in LST_SEQ (OUTER_FATHER).  */
660
661 static bool
662 lst_interchange_select_inner (scop_p scop, lst_p outer_father, int outer,
663                               lst_p inner_father)
664 {
665   int inner;
666   lst_p loop1, loop2;
667
668   gcc_assert (outer_father
669               && LST_LOOP_P (outer_father)
670               && LST_LOOP_P (VEC_index (lst_p, LST_SEQ (outer_father), outer))
671               && inner_father
672               && LST_LOOP_P (inner_father));
673
674   loop1 = VEC_index (lst_p, LST_SEQ (outer_father), outer);
675
676   for (inner = 0; VEC_iterate (lst_p, LST_SEQ (inner_father), inner, loop2); inner++)
677     if (LST_LOOP_P (loop2)
678         && (lst_try_interchange_loops (scop, loop1, loop2)
679             || lst_interchange_select_inner (scop, outer_father, outer, loop2)))
680       return true;
681
682   return false;
683 }
684
685 /* Interchanges all the loops of LOOP and the loops of its body that
686    are considered profitable to interchange.  Return true if it did
687    interchanged some loops.  OUTER is the index in LST_SEQ (LOOP) that
688    points to the next outer loop to be considered for interchange.  */
689
690 static bool
691 lst_interchange_select_outer (scop_p scop, lst_p loop, int outer)
692 {
693   lst_p l;
694   bool res = false;
695   int i = 0;
696   lst_p father;
697
698   if (!loop || !LST_LOOP_P (loop))
699     return false;
700
701   father = LST_LOOP_FATHER (loop);
702   if (father)
703     {
704       while (lst_interchange_select_inner (scop, father, outer, loop))
705         {
706           res = true;
707           loop = VEC_index (lst_p, LST_SEQ (father), outer);
708         }
709     }
710
711   if (LST_LOOP_P (loop))
712     for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l); i++)
713       if (LST_LOOP_P (l))
714         res |= lst_interchange_select_outer (scop, l, i);
715
716   return res;
717 }
718
719 /* Interchanges all the loop depths that are considered profitable for SCOP.  */
720
721 bool
722 scop_do_interchange (scop_p scop)
723 {
724   bool res = lst_interchange_select_outer
725     (scop, SCOP_TRANSFORMED_SCHEDULE (scop), 0);
726
727   lst_update_scattering (SCOP_TRANSFORMED_SCHEDULE (scop));
728
729   return res;
730 }
731
732
733 #endif
734