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