OSDN Git Service

291d1d91e5b135d6d78267fba5a4b5c3daef8473
[pf3gnuchains/gcc-fork.git] / gcc / lambda-code.c
1 /*  Loop transformation code generation
2     Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3     Contributed by Daniel Berlin <dberlin@dberlin.org>
4
5     This file is part of GCC.
6     
7     GCC is free software; you can redistribute it and/or modify it under
8     the terms of the GNU General Public License as published by the Free
9     Software Foundation; either version 2, or (at your option) any later
10     version.
11     
12     GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13     WARRANTY; without even the implied warranty of MERCHANTABILITY or
14     FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15     for more details.
16     
17     You should have received a copy of the GNU General Public License
18     along with GCC; see the file COPYING.  If not, write to the Free
19     Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20     02110-1301, USA.  */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "ggc.h"
27 #include "tree.h"
28 #include "target.h"
29 #include "rtl.h"
30 #include "basic-block.h"
31 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
34 #include "timevar.h"
35 #include "cfgloop.h"
36 #include "expr.h"
37 #include "optabs.h"
38 #include "tree-chrec.h"
39 #include "tree-data-ref.h"
40 #include "tree-pass.h"
41 #include "tree-scalar-evolution.h"
42 #include "vec.h"
43 #include "lambda.h"
44 #include "vecprim.h"
45
46 /* This loop nest code generation is based on non-singular matrix
47    math.
48  
49  A little terminology and a general sketch of the algorithm.  See "A singular
50  loop transformation framework based on non-singular matrices" by Wei Li and
51  Keshav Pingali for formal proofs that the various statements below are
52  correct. 
53
54  A loop iteration space represents the points traversed by the loop.  A point in the
55  iteration space can be represented by a vector of size <loop depth>.  You can
56  therefore represent the iteration space as an integral combinations of a set
57  of basis vectors. 
58
59  A loop iteration space is dense if every integer point between the loop
60  bounds is a point in the iteration space.  Every loop with a step of 1
61  therefore has a dense iteration space.
62
63  for i = 1 to 3, step 1 is a dense iteration space.
64    
65  A loop iteration space is sparse if it is not dense.  That is, the iteration
66  space skips integer points that are within the loop bounds.  
67
68  for i = 1 to 3, step 2 is a sparse iteration space, because the integer point
69  2 is skipped.
70
71  Dense source spaces are easy to transform, because they don't skip any
72  points to begin with.  Thus we can compute the exact bounds of the target
73  space using min/max and floor/ceil.
74
75  For a dense source space, we take the transformation matrix, decompose it
76  into a lower triangular part (H) and a unimodular part (U). 
77  We then compute the auxiliary space from the unimodular part (source loop
78  nest . U = auxiliary space) , which has two important properties:
79   1. It traverses the iterations in the same lexicographic order as the source
80   space.
81   2. It is a dense space when the source is a dense space (even if the target
82   space is going to be sparse).
83  
84  Given the auxiliary space, we use the lower triangular part to compute the
85  bounds in the target space by simple matrix multiplication.
86  The gaps in the target space (IE the new loop step sizes) will be the
87  diagonals of the H matrix.
88
89  Sparse source spaces require another step, because you can't directly compute
90  the exact bounds of the auxiliary and target space from the sparse space.
91  Rather than try to come up with a separate algorithm to handle sparse source
92  spaces directly, we just find a legal transformation matrix that gives you
93  the sparse source space, from a dense space, and then transform the dense
94  space.
95
96  For a regular sparse space, you can represent the source space as an integer
97  lattice, and the base space of that lattice will always be dense.  Thus, we
98  effectively use the lattice to figure out the transformation from the lattice
99  base space, to the sparse iteration space (IE what transform was applied to
100  the dense space to make it sparse).  We then compose this transform with the
101  transformation matrix specified by the user (since our matrix transformations
102  are closed under composition, this is okay).  We can then use the base space
103  (which is dense) plus the composed transformation matrix, to compute the rest
104  of the transform using the dense space algorithm above.
105  
106  In other words, our sparse source space (B) is decomposed into a dense base
107  space (A), and a matrix (L) that transforms A into B, such that A.L = B.
108  We then compute the composition of L and the user transformation matrix (T),
109  so that T is now a transform from A to the result, instead of from B to the
110  result. 
111  IE A.(LT) = result instead of B.T = result
112  Since A is now a dense source space, we can use the dense source space
113  algorithm above to compute the result of applying transform (LT) to A.
114
115  Fourier-Motzkin elimination is used to compute the bounds of the base space
116  of the lattice.  */
117
118 static bool perfect_nestify (struct loop *, VEC(tree,heap) *, 
119                              VEC(tree,heap) *, VEC(int,heap) *,
120                              VEC(tree,heap) *);
121 /* Lattice stuff that is internal to the code generation algorithm.  */
122
123 typedef struct
124 {
125   /* Lattice base matrix.  */
126   lambda_matrix base;
127   /* Lattice dimension.  */
128   int dimension;
129   /* Origin vector for the coefficients.  */
130   lambda_vector origin;
131   /* Origin matrix for the invariants.  */
132   lambda_matrix origin_invariants;
133   /* Number of invariants.  */
134   int invariants;
135 } *lambda_lattice;
136
137 #define LATTICE_BASE(T) ((T)->base)
138 #define LATTICE_DIMENSION(T) ((T)->dimension)
139 #define LATTICE_ORIGIN(T) ((T)->origin)
140 #define LATTICE_ORIGIN_INVARIANTS(T) ((T)->origin_invariants)
141 #define LATTICE_INVARIANTS(T) ((T)->invariants)
142
143 static bool lle_equal (lambda_linear_expression, lambda_linear_expression,
144                        int, int);
145 static lambda_lattice lambda_lattice_new (int, int);
146 static lambda_lattice lambda_lattice_compute_base (lambda_loopnest);
147
148 static tree find_induction_var_from_exit_cond (struct loop *);
149 static bool can_convert_to_perfect_nest (struct loop *);
150
151 /* Create a new lambda body vector.  */
152
153 lambda_body_vector
154 lambda_body_vector_new (int size)
155 {
156   lambda_body_vector ret;
157
158   ret = ggc_alloc (sizeof (*ret));
159   LBV_COEFFICIENTS (ret) = lambda_vector_new (size);
160   LBV_SIZE (ret) = size;
161   LBV_DENOMINATOR (ret) = 1;
162   return ret;
163 }
164
165 /* Compute the new coefficients for the vector based on the
166   *inverse* of the transformation matrix.  */
167
168 lambda_body_vector
169 lambda_body_vector_compute_new (lambda_trans_matrix transform,
170                                 lambda_body_vector vect)
171 {
172   lambda_body_vector temp;
173   int depth;
174
175   /* Make sure the matrix is square.  */
176   gcc_assert (LTM_ROWSIZE (transform) == LTM_COLSIZE (transform));
177
178   depth = LTM_ROWSIZE (transform);
179
180   temp = lambda_body_vector_new (depth);
181   LBV_DENOMINATOR (temp) =
182     LBV_DENOMINATOR (vect) * LTM_DENOMINATOR (transform);
183   lambda_vector_matrix_mult (LBV_COEFFICIENTS (vect), depth,
184                              LTM_MATRIX (transform), depth,
185                              LBV_COEFFICIENTS (temp));
186   LBV_SIZE (temp) = LBV_SIZE (vect);
187   return temp;
188 }
189
190 /* Print out a lambda body vector.  */
191
192 void
193 print_lambda_body_vector (FILE * outfile, lambda_body_vector body)
194 {
195   print_lambda_vector (outfile, LBV_COEFFICIENTS (body), LBV_SIZE (body));
196 }
197
198 /* Return TRUE if two linear expressions are equal.  */
199
200 static bool
201 lle_equal (lambda_linear_expression lle1, lambda_linear_expression lle2,
202            int depth, int invariants)
203 {
204   int i;
205
206   if (lle1 == NULL || lle2 == NULL)
207     return false;
208   if (LLE_CONSTANT (lle1) != LLE_CONSTANT (lle2))
209     return false;
210   if (LLE_DENOMINATOR (lle1) != LLE_DENOMINATOR (lle2))
211     return false;
212   for (i = 0; i < depth; i++)
213     if (LLE_COEFFICIENTS (lle1)[i] != LLE_COEFFICIENTS (lle2)[i])
214       return false;
215   for (i = 0; i < invariants; i++)
216     if (LLE_INVARIANT_COEFFICIENTS (lle1)[i] !=
217         LLE_INVARIANT_COEFFICIENTS (lle2)[i])
218       return false;
219   return true;
220 }
221
222 /* Create a new linear expression with dimension DIM, and total number
223    of invariants INVARIANTS.  */
224
225 lambda_linear_expression
226 lambda_linear_expression_new (int dim, int invariants)
227 {
228   lambda_linear_expression ret;
229
230   ret = ggc_alloc_cleared (sizeof (*ret));
231
232   LLE_COEFFICIENTS (ret) = lambda_vector_new (dim);
233   LLE_CONSTANT (ret) = 0;
234   LLE_INVARIANT_COEFFICIENTS (ret) = lambda_vector_new (invariants);
235   LLE_DENOMINATOR (ret) = 1;
236   LLE_NEXT (ret) = NULL;
237
238   return ret;
239 }
240
241 /* Print out a linear expression EXPR, with SIZE coefficients, to OUTFILE.
242    The starting letter used for variable names is START.  */
243
244 static void
245 print_linear_expression (FILE * outfile, lambda_vector expr, int size,
246                          char start)
247 {
248   int i;
249   bool first = true;
250   for (i = 0; i < size; i++)
251     {
252       if (expr[i] != 0)
253         {
254           if (first)
255             {
256               if (expr[i] < 0)
257                 fprintf (outfile, "-");
258               first = false;
259             }
260           else if (expr[i] > 0)
261             fprintf (outfile, " + ");
262           else
263             fprintf (outfile, " - ");
264           if (abs (expr[i]) == 1)
265             fprintf (outfile, "%c", start + i);
266           else
267             fprintf (outfile, "%d%c", abs (expr[i]), start + i);
268         }
269     }
270 }
271
272 /* Print out a lambda linear expression structure, EXPR, to OUTFILE. The
273    depth/number of coefficients is given by DEPTH, the number of invariants is
274    given by INVARIANTS, and the character to start variable names with is given
275    by START.  */
276
277 void
278 print_lambda_linear_expression (FILE * outfile,
279                                 lambda_linear_expression expr,
280                                 int depth, int invariants, char start)
281 {
282   fprintf (outfile, "\tLinear expression: ");
283   print_linear_expression (outfile, LLE_COEFFICIENTS (expr), depth, start);
284   fprintf (outfile, " constant: %d ", LLE_CONSTANT (expr));
285   fprintf (outfile, "  invariants: ");
286   print_linear_expression (outfile, LLE_INVARIANT_COEFFICIENTS (expr),
287                            invariants, 'A');
288   fprintf (outfile, "  denominator: %d\n", LLE_DENOMINATOR (expr));
289 }
290
291 /* Print a lambda loop structure LOOP to OUTFILE.  The depth/number of
292    coefficients is given by DEPTH, the number of invariants is 
293    given by INVARIANTS, and the character to start variable names with is given
294    by START.  */
295
296 void
297 print_lambda_loop (FILE * outfile, lambda_loop loop, int depth,
298                    int invariants, char start)
299 {
300   int step;
301   lambda_linear_expression expr;
302
303   gcc_assert (loop);
304
305   expr = LL_LINEAR_OFFSET (loop);
306   step = LL_STEP (loop);
307   fprintf (outfile, "  step size = %d \n", step);
308
309   if (expr)
310     {
311       fprintf (outfile, "  linear offset: \n");
312       print_lambda_linear_expression (outfile, expr, depth, invariants,
313                                       start);
314     }
315
316   fprintf (outfile, "  lower bound: \n");
317   for (expr = LL_LOWER_BOUND (loop); expr != NULL; expr = LLE_NEXT (expr))
318     print_lambda_linear_expression (outfile, expr, depth, invariants, start);
319   fprintf (outfile, "  upper bound: \n");
320   for (expr = LL_UPPER_BOUND (loop); expr != NULL; expr = LLE_NEXT (expr))
321     print_lambda_linear_expression (outfile, expr, depth, invariants, start);
322 }
323
324 /* Create a new loop nest structure with DEPTH loops, and INVARIANTS as the
325    number of invariants.  */
326
327 lambda_loopnest
328 lambda_loopnest_new (int depth, int invariants)
329 {
330   lambda_loopnest ret;
331   ret = ggc_alloc (sizeof (*ret));
332
333   LN_LOOPS (ret) = ggc_alloc_cleared (depth * sizeof (lambda_loop));
334   LN_DEPTH (ret) = depth;
335   LN_INVARIANTS (ret) = invariants;
336
337   return ret;
338 }
339
340 /* Print a lambda loopnest structure, NEST, to OUTFILE.  The starting
341    character to use for loop names is given by START.  */
342
343 void
344 print_lambda_loopnest (FILE * outfile, lambda_loopnest nest, char start)
345 {
346   int i;
347   for (i = 0; i < LN_DEPTH (nest); i++)
348     {
349       fprintf (outfile, "Loop %c\n", start + i);
350       print_lambda_loop (outfile, LN_LOOPS (nest)[i], LN_DEPTH (nest),
351                          LN_INVARIANTS (nest), 'i');
352       fprintf (outfile, "\n");
353     }
354 }
355
356 /* Allocate a new lattice structure of DEPTH x DEPTH, with INVARIANTS number
357    of invariants.  */
358
359 static lambda_lattice
360 lambda_lattice_new (int depth, int invariants)
361 {
362   lambda_lattice ret;
363   ret = ggc_alloc (sizeof (*ret));
364   LATTICE_BASE (ret) = lambda_matrix_new (depth, depth);
365   LATTICE_ORIGIN (ret) = lambda_vector_new (depth);
366   LATTICE_ORIGIN_INVARIANTS (ret) = lambda_matrix_new (depth, invariants);
367   LATTICE_DIMENSION (ret) = depth;
368   LATTICE_INVARIANTS (ret) = invariants;
369   return ret;
370 }
371
372 /* Compute the lattice base for NEST.  The lattice base is essentially a
373    non-singular transform from a dense base space to a sparse iteration space.
374    We use it so that we don't have to specially handle the case of a sparse
375    iteration space in other parts of the algorithm.  As a result, this routine
376    only does something interesting (IE produce a matrix that isn't the
377    identity matrix) if NEST is a sparse space.  */
378
379 static lambda_lattice
380 lambda_lattice_compute_base (lambda_loopnest nest)
381 {
382   lambda_lattice ret;
383   int depth, invariants;
384   lambda_matrix base;
385
386   int i, j, step;
387   lambda_loop loop;
388   lambda_linear_expression expression;
389
390   depth = LN_DEPTH (nest);
391   invariants = LN_INVARIANTS (nest);
392
393   ret = lambda_lattice_new (depth, invariants);
394   base = LATTICE_BASE (ret);
395   for (i = 0; i < depth; i++)
396     {
397       loop = LN_LOOPS (nest)[i];
398       gcc_assert (loop);
399       step = LL_STEP (loop);
400       /* If we have a step of 1, then the base is one, and the
401          origin and invariant coefficients are 0.  */
402       if (step == 1)
403         {
404           for (j = 0; j < depth; j++)
405             base[i][j] = 0;
406           base[i][i] = 1;
407           LATTICE_ORIGIN (ret)[i] = 0;
408           for (j = 0; j < invariants; j++)
409             LATTICE_ORIGIN_INVARIANTS (ret)[i][j] = 0;
410         }
411       else
412         {
413           /* Otherwise, we need the lower bound expression (which must
414              be an affine function)  to determine the base.  */
415           expression = LL_LOWER_BOUND (loop);
416           gcc_assert (expression && !LLE_NEXT (expression) 
417                       && LLE_DENOMINATOR (expression) == 1);
418
419           /* The lower triangular portion of the base is going to be the
420              coefficient times the step */
421           for (j = 0; j < i; j++)
422             base[i][j] = LLE_COEFFICIENTS (expression)[j]
423               * LL_STEP (LN_LOOPS (nest)[j]);
424           base[i][i] = step;
425           for (j = i + 1; j < depth; j++)
426             base[i][j] = 0;
427
428           /* Origin for this loop is the constant of the lower bound
429              expression.  */
430           LATTICE_ORIGIN (ret)[i] = LLE_CONSTANT (expression);
431
432           /* Coefficient for the invariants are equal to the invariant
433              coefficients in the expression.  */
434           for (j = 0; j < invariants; j++)
435             LATTICE_ORIGIN_INVARIANTS (ret)[i][j] =
436               LLE_INVARIANT_COEFFICIENTS (expression)[j];
437         }
438     }
439   return ret;
440 }
441
442 /* Compute the least common multiple of two numbers A and B .  */
443
444 int
445 least_common_multiple (int a, int b)
446 {
447   return (abs (a) * abs (b) / gcd (a, b));
448 }
449
450 /* Perform Fourier-Motzkin elimination to calculate the bounds of the
451    auxiliary nest.
452    Fourier-Motzkin is a way of reducing systems of linear inequalities so that
453    it is easy to calculate the answer and bounds.
454    A sketch of how it works:
455    Given a system of linear inequalities, ai * xj >= bk, you can always
456    rewrite the constraints so they are all of the form
457    a <= x, or x <= b, or x >= constant for some x in x1 ... xj (and some b
458    in b1 ... bk, and some a in a1...ai)
459    You can then eliminate this x from the non-constant inequalities by
460    rewriting these as a <= b, x >= constant, and delete the x variable.
461    You can then repeat this for any remaining x variables, and then we have
462    an easy to use variable <= constant (or no variables at all) form that we
463    can construct our bounds from. 
464    
465    In our case, each time we eliminate, we construct part of the bound from
466    the ith variable, then delete the ith variable. 
467    
468    Remember the constant are in our vector a, our coefficient matrix is A,
469    and our invariant coefficient matrix is B.
470    
471    SIZE is the size of the matrices being passed.
472    DEPTH is the loop nest depth.
473    INVARIANTS is the number of loop invariants.
474    A, B, and a are the coefficient matrix, invariant coefficient, and a
475    vector of constants, respectively.  */
476
477 static lambda_loopnest 
478 compute_nest_using_fourier_motzkin (int size,
479                                     int depth, 
480                                     int invariants,
481                                     lambda_matrix A,
482                                     lambda_matrix B,
483                                     lambda_vector a)
484 {
485
486   int multiple, f1, f2;
487   int i, j, k;
488   lambda_linear_expression expression;
489   lambda_loop loop;
490   lambda_loopnest auxillary_nest;
491   lambda_matrix swapmatrix, A1, B1;
492   lambda_vector swapvector, a1;
493   int newsize;
494
495   A1 = lambda_matrix_new (128, depth);
496   B1 = lambda_matrix_new (128, invariants);
497   a1 = lambda_vector_new (128);
498
499   auxillary_nest = lambda_loopnest_new (depth, invariants);
500
501   for (i = depth - 1; i >= 0; i--)
502     {
503       loop = lambda_loop_new ();
504       LN_LOOPS (auxillary_nest)[i] = loop;
505       LL_STEP (loop) = 1;
506
507       for (j = 0; j < size; j++)
508         {
509           if (A[j][i] < 0)
510             {
511               /* Any linear expression in the matrix with a coefficient less
512                  than 0 becomes part of the new lower bound.  */ 
513               expression = lambda_linear_expression_new (depth, invariants);
514
515               for (k = 0; k < i; k++)
516                 LLE_COEFFICIENTS (expression)[k] = A[j][k];
517
518               for (k = 0; k < invariants; k++)
519                 LLE_INVARIANT_COEFFICIENTS (expression)[k] = -1 * B[j][k];
520
521               LLE_DENOMINATOR (expression) = -1 * A[j][i];
522               LLE_CONSTANT (expression) = -1 * a[j];
523
524               /* Ignore if identical to the existing lower bound.  */
525               if (!lle_equal (LL_LOWER_BOUND (loop),
526                               expression, depth, invariants))
527                 {
528                   LLE_NEXT (expression) = LL_LOWER_BOUND (loop);
529                   LL_LOWER_BOUND (loop) = expression;
530                 }
531
532             }
533           else if (A[j][i] > 0)
534             {
535               /* Any linear expression with a coefficient greater than 0
536                  becomes part of the new upper bound.  */ 
537               expression = lambda_linear_expression_new (depth, invariants);
538               for (k = 0; k < i; k++)
539                 LLE_COEFFICIENTS (expression)[k] = -1 * A[j][k];
540
541               for (k = 0; k < invariants; k++)
542                 LLE_INVARIANT_COEFFICIENTS (expression)[k] = B[j][k];
543
544               LLE_DENOMINATOR (expression) = A[j][i];
545               LLE_CONSTANT (expression) = a[j];
546
547               /* Ignore if identical to the existing upper bound.  */
548               if (!lle_equal (LL_UPPER_BOUND (loop),
549                               expression, depth, invariants))
550                 {
551                   LLE_NEXT (expression) = LL_UPPER_BOUND (loop);
552                   LL_UPPER_BOUND (loop) = expression;
553                 }
554
555             }
556         }
557
558       /* This portion creates a new system of linear inequalities by deleting
559          the i'th variable, reducing the system by one variable.  */
560       newsize = 0;
561       for (j = 0; j < size; j++)
562         {
563           /* If the coefficient for the i'th variable is 0, then we can just
564              eliminate the variable straightaway.  Otherwise, we have to
565              multiply through by the coefficients we are eliminating.  */
566           if (A[j][i] == 0)
567             {
568               lambda_vector_copy (A[j], A1[newsize], depth);
569               lambda_vector_copy (B[j], B1[newsize], invariants);
570               a1[newsize] = a[j];
571               newsize++;
572             }
573           else if (A[j][i] > 0)
574             {
575               for (k = 0; k < size; k++)
576                 {
577                   if (A[k][i] < 0)
578                     {
579                       multiple = least_common_multiple (A[j][i], A[k][i]);
580                       f1 = multiple / A[j][i];
581                       f2 = -1 * multiple / A[k][i];
582
583                       lambda_vector_add_mc (A[j], f1, A[k], f2,
584                                             A1[newsize], depth);
585                       lambda_vector_add_mc (B[j], f1, B[k], f2,
586                                             B1[newsize], invariants);
587                       a1[newsize] = f1 * a[j] + f2 * a[k];
588                       newsize++;
589                     }
590                 }
591             }
592         }
593
594       swapmatrix = A;
595       A = A1;
596       A1 = swapmatrix;
597
598       swapmatrix = B;
599       B = B1;
600       B1 = swapmatrix;
601
602       swapvector = a;
603       a = a1;
604       a1 = swapvector;
605
606       size = newsize;
607     }
608
609   return auxillary_nest;
610 }
611
612 /* Compute the loop bounds for the auxiliary space NEST.
613    Input system used is Ax <= b.  TRANS is the unimodular transformation.  
614    Given the original nest, this function will 
615    1. Convert the nest into matrix form, which consists of a matrix for the
616    coefficients, a matrix for the 
617    invariant coefficients, and a vector for the constants.  
618    2. Use the matrix form to calculate the lattice base for the nest (which is
619    a dense space) 
620    3. Compose the dense space transform with the user specified transform, to 
621    get a transform we can easily calculate transformed bounds for.
622    4. Multiply the composed transformation matrix times the matrix form of the
623    loop.
624    5. Transform the newly created matrix (from step 4) back into a loop nest
625    using Fourier-Motzkin elimination to figure out the bounds.  */
626
627 static lambda_loopnest
628 lambda_compute_auxillary_space (lambda_loopnest nest,
629                                 lambda_trans_matrix trans)
630 {
631   lambda_matrix A, B, A1, B1;
632   lambda_vector a, a1;
633   lambda_matrix invertedtrans;
634   int depth, invariants, size;
635   int i, j;
636   lambda_loop loop;
637   lambda_linear_expression expression;
638   lambda_lattice lattice;
639
640   depth = LN_DEPTH (nest);
641   invariants = LN_INVARIANTS (nest);
642
643   /* Unfortunately, we can't know the number of constraints we'll have
644      ahead of time, but this should be enough even in ridiculous loop nest
645      cases. We must not go over this limit.  */
646   A = lambda_matrix_new (128, depth);
647   B = lambda_matrix_new (128, invariants);
648   a = lambda_vector_new (128);
649
650   A1 = lambda_matrix_new (128, depth);
651   B1 = lambda_matrix_new (128, invariants);
652   a1 = lambda_vector_new (128);
653
654   /* Store the bounds in the equation matrix A, constant vector a, and
655      invariant matrix B, so that we have Ax <= a + B.
656      This requires a little equation rearranging so that everything is on the
657      correct side of the inequality.  */
658   size = 0;
659   for (i = 0; i < depth; i++)
660     {
661       loop = LN_LOOPS (nest)[i];
662
663       /* First we do the lower bound.  */
664       if (LL_STEP (loop) > 0)
665         expression = LL_LOWER_BOUND (loop);
666       else
667         expression = LL_UPPER_BOUND (loop);
668
669       for (; expression != NULL; expression = LLE_NEXT (expression))
670         {
671           /* Fill in the coefficient.  */
672           for (j = 0; j < i; j++)
673             A[size][j] = LLE_COEFFICIENTS (expression)[j];
674
675           /* And the invariant coefficient.  */
676           for (j = 0; j < invariants; j++)
677             B[size][j] = LLE_INVARIANT_COEFFICIENTS (expression)[j];
678
679           /* And the constant.  */
680           a[size] = LLE_CONSTANT (expression);
681
682           /* Convert (2x+3y+2+b)/4 <= z to 2x+3y-4z <= -2-b.  IE put all
683              constants and single variables on   */
684           A[size][i] = -1 * LLE_DENOMINATOR (expression);
685           a[size] *= -1;
686           for (j = 0; j < invariants; j++)
687             B[size][j] *= -1;
688
689           size++;
690           /* Need to increase matrix sizes above.  */
691           gcc_assert (size <= 127);
692           
693         }
694
695       /* Then do the exact same thing for the upper bounds.  */
696       if (LL_STEP (loop) > 0)
697         expression = LL_UPPER_BOUND (loop);
698       else
699         expression = LL_LOWER_BOUND (loop);
700
701       for (; expression != NULL; expression = LLE_NEXT (expression))
702         {
703           /* Fill in the coefficient.  */
704           for (j = 0; j < i; j++)
705             A[size][j] = LLE_COEFFICIENTS (expression)[j];
706
707           /* And the invariant coefficient.  */
708           for (j = 0; j < invariants; j++)
709             B[size][j] = LLE_INVARIANT_COEFFICIENTS (expression)[j];
710
711           /* And the constant.  */
712           a[size] = LLE_CONSTANT (expression);
713
714           /* Convert z <= (2x+3y+2+b)/4 to -2x-3y+4z <= 2+b.  */
715           for (j = 0; j < i; j++)
716             A[size][j] *= -1;
717           A[size][i] = LLE_DENOMINATOR (expression);
718           size++;
719           /* Need to increase matrix sizes above.  */
720           gcc_assert (size <= 127);
721
722         }
723     }
724
725   /* Compute the lattice base x = base * y + origin, where y is the
726      base space.  */
727   lattice = lambda_lattice_compute_base (nest);
728
729   /* Ax <= a + B then becomes ALy <= a+B - A*origin.  L is the lattice base  */
730
731   /* A1 = A * L */
732   lambda_matrix_mult (A, LATTICE_BASE (lattice), A1, size, depth, depth);
733
734   /* a1 = a - A * origin constant.  */
735   lambda_matrix_vector_mult (A, size, depth, LATTICE_ORIGIN (lattice), a1);
736   lambda_vector_add_mc (a, 1, a1, -1, a1, size);
737
738   /* B1 = B - A * origin invariant.  */
739   lambda_matrix_mult (A, LATTICE_ORIGIN_INVARIANTS (lattice), B1, size, depth,
740                       invariants);
741   lambda_matrix_add_mc (B, 1, B1, -1, B1, size, invariants);
742
743   /* Now compute the auxiliary space bounds by first inverting U, multiplying
744      it by A1, then performing Fourier-Motzkin.  */
745
746   invertedtrans = lambda_matrix_new (depth, depth);
747
748   /* Compute the inverse of U.  */
749   lambda_matrix_inverse (LTM_MATRIX (trans),
750                          invertedtrans, depth);
751
752   /* A = A1 inv(U).  */
753   lambda_matrix_mult (A1, invertedtrans, A, size, depth, depth);
754
755   return compute_nest_using_fourier_motzkin (size, depth, invariants,
756                                              A, B1, a1);
757 }
758
759 /* Compute the loop bounds for the target space, using the bounds of
760    the auxiliary nest AUXILLARY_NEST, and the triangular matrix H.  
761    The target space loop bounds are computed by multiplying the triangular
762    matrix H by the auxiliary nest, to get the new loop bounds.  The sign of
763    the loop steps (positive or negative) is then used to swap the bounds if
764    the loop counts downwards.
765    Return the target loopnest.  */
766
767 static lambda_loopnest
768 lambda_compute_target_space (lambda_loopnest auxillary_nest,
769                              lambda_trans_matrix H, lambda_vector stepsigns)
770 {
771   lambda_matrix inverse, H1;
772   int determinant, i, j;
773   int gcd1, gcd2;
774   int factor;
775
776   lambda_loopnest target_nest;
777   int depth, invariants;
778   lambda_matrix target;
779
780   lambda_loop auxillary_loop, target_loop;
781   lambda_linear_expression expression, auxillary_expr, target_expr, tmp_expr;
782
783   depth = LN_DEPTH (auxillary_nest);
784   invariants = LN_INVARIANTS (auxillary_nest);
785
786   inverse = lambda_matrix_new (depth, depth);
787   determinant = lambda_matrix_inverse (LTM_MATRIX (H), inverse, depth);
788
789   /* H1 is H excluding its diagonal.  */
790   H1 = lambda_matrix_new (depth, depth);
791   lambda_matrix_copy (LTM_MATRIX (H), H1, depth, depth);
792
793   for (i = 0; i < depth; i++)
794     H1[i][i] = 0;
795
796   /* Computes the linear offsets of the loop bounds.  */
797   target = lambda_matrix_new (depth, depth);
798   lambda_matrix_mult (H1, inverse, target, depth, depth, depth);
799
800   target_nest = lambda_loopnest_new (depth, invariants);
801
802   for (i = 0; i < depth; i++)
803     {
804
805       /* Get a new loop structure.  */
806       target_loop = lambda_loop_new ();
807       LN_LOOPS (target_nest)[i] = target_loop;
808
809       /* Computes the gcd of the coefficients of the linear part.  */
810       gcd1 = lambda_vector_gcd (target[i], i);
811
812       /* Include the denominator in the GCD.  */
813       gcd1 = gcd (gcd1, determinant);
814
815       /* Now divide through by the gcd.  */
816       for (j = 0; j < i; j++)
817         target[i][j] = target[i][j] / gcd1;
818
819       expression = lambda_linear_expression_new (depth, invariants);
820       lambda_vector_copy (target[i], LLE_COEFFICIENTS (expression), depth);
821       LLE_DENOMINATOR (expression) = determinant / gcd1;
822       LLE_CONSTANT (expression) = 0;
823       lambda_vector_clear (LLE_INVARIANT_COEFFICIENTS (expression),
824                            invariants);
825       LL_LINEAR_OFFSET (target_loop) = expression;
826     }
827
828   /* For each loop, compute the new bounds from H.  */
829   for (i = 0; i < depth; i++)
830     {
831       auxillary_loop = LN_LOOPS (auxillary_nest)[i];
832       target_loop = LN_LOOPS (target_nest)[i];
833       LL_STEP (target_loop) = LTM_MATRIX (H)[i][i];
834       factor = LTM_MATRIX (H)[i][i];
835
836       /* First we do the lower bound.  */
837       auxillary_expr = LL_LOWER_BOUND (auxillary_loop);
838
839       for (; auxillary_expr != NULL;
840            auxillary_expr = LLE_NEXT (auxillary_expr))
841         {
842           target_expr = lambda_linear_expression_new (depth, invariants);
843           lambda_vector_matrix_mult (LLE_COEFFICIENTS (auxillary_expr),
844                                      depth, inverse, depth,
845                                      LLE_COEFFICIENTS (target_expr));
846           lambda_vector_mult_const (LLE_COEFFICIENTS (target_expr),
847                                     LLE_COEFFICIENTS (target_expr), depth,
848                                     factor);
849
850           LLE_CONSTANT (target_expr) = LLE_CONSTANT (auxillary_expr) * factor;
851           lambda_vector_copy (LLE_INVARIANT_COEFFICIENTS (auxillary_expr),
852                               LLE_INVARIANT_COEFFICIENTS (target_expr),
853                               invariants);
854           lambda_vector_mult_const (LLE_INVARIANT_COEFFICIENTS (target_expr),
855                                     LLE_INVARIANT_COEFFICIENTS (target_expr),
856                                     invariants, factor);
857           LLE_DENOMINATOR (target_expr) = LLE_DENOMINATOR (auxillary_expr);
858
859           if (!lambda_vector_zerop (LLE_COEFFICIENTS (target_expr), depth))
860             {
861               LLE_CONSTANT (target_expr) = LLE_CONSTANT (target_expr)
862                 * determinant;
863               lambda_vector_mult_const (LLE_INVARIANT_COEFFICIENTS
864                                         (target_expr),
865                                         LLE_INVARIANT_COEFFICIENTS
866                                         (target_expr), invariants,
867                                         determinant);
868               LLE_DENOMINATOR (target_expr) =
869                 LLE_DENOMINATOR (target_expr) * determinant;
870             }
871           /* Find the gcd and divide by it here, rather than doing it
872              at the tree level.  */
873           gcd1 = lambda_vector_gcd (LLE_COEFFICIENTS (target_expr), depth);
874           gcd2 = lambda_vector_gcd (LLE_INVARIANT_COEFFICIENTS (target_expr),
875                                     invariants);
876           gcd1 = gcd (gcd1, gcd2);
877           gcd1 = gcd (gcd1, LLE_CONSTANT (target_expr));
878           gcd1 = gcd (gcd1, LLE_DENOMINATOR (target_expr));
879           for (j = 0; j < depth; j++)
880             LLE_COEFFICIENTS (target_expr)[j] /= gcd1;
881           for (j = 0; j < invariants; j++)
882             LLE_INVARIANT_COEFFICIENTS (target_expr)[j] /= gcd1;
883           LLE_CONSTANT (target_expr) /= gcd1;
884           LLE_DENOMINATOR (target_expr) /= gcd1;
885           /* Ignore if identical to existing bound.  */
886           if (!lle_equal (LL_LOWER_BOUND (target_loop), target_expr, depth,
887                           invariants))
888             {
889               LLE_NEXT (target_expr) = LL_LOWER_BOUND (target_loop);
890               LL_LOWER_BOUND (target_loop) = target_expr;
891             }
892         }
893       /* Now do the upper bound.  */
894       auxillary_expr = LL_UPPER_BOUND (auxillary_loop);
895
896       for (; auxillary_expr != NULL;
897            auxillary_expr = LLE_NEXT (auxillary_expr))
898         {
899           target_expr = lambda_linear_expression_new (depth, invariants);
900           lambda_vector_matrix_mult (LLE_COEFFICIENTS (auxillary_expr),
901                                      depth, inverse, depth,
902                                      LLE_COEFFICIENTS (target_expr));
903           lambda_vector_mult_const (LLE_COEFFICIENTS (target_expr),
904                                     LLE_COEFFICIENTS (target_expr), depth,
905                                     factor);
906           LLE_CONSTANT (target_expr) = LLE_CONSTANT (auxillary_expr) * factor;
907           lambda_vector_copy (LLE_INVARIANT_COEFFICIENTS (auxillary_expr),
908                               LLE_INVARIANT_COEFFICIENTS (target_expr),
909                               invariants);
910           lambda_vector_mult_const (LLE_INVARIANT_COEFFICIENTS (target_expr),
911                                     LLE_INVARIANT_COEFFICIENTS (target_expr),
912                                     invariants, factor);
913           LLE_DENOMINATOR (target_expr) = LLE_DENOMINATOR (auxillary_expr);
914
915           if (!lambda_vector_zerop (LLE_COEFFICIENTS (target_expr), depth))
916             {
917               LLE_CONSTANT (target_expr) = LLE_CONSTANT (target_expr)
918                 * determinant;
919               lambda_vector_mult_const (LLE_INVARIANT_COEFFICIENTS
920                                         (target_expr),
921                                         LLE_INVARIANT_COEFFICIENTS
922                                         (target_expr), invariants,
923                                         determinant);
924               LLE_DENOMINATOR (target_expr) =
925                 LLE_DENOMINATOR (target_expr) * determinant;
926             }
927           /* Find the gcd and divide by it here, instead of at the
928              tree level.  */
929           gcd1 = lambda_vector_gcd (LLE_COEFFICIENTS (target_expr), depth);
930           gcd2 = lambda_vector_gcd (LLE_INVARIANT_COEFFICIENTS (target_expr),
931                                     invariants);
932           gcd1 = gcd (gcd1, gcd2);
933           gcd1 = gcd (gcd1, LLE_CONSTANT (target_expr));
934           gcd1 = gcd (gcd1, LLE_DENOMINATOR (target_expr));
935           for (j = 0; j < depth; j++)
936             LLE_COEFFICIENTS (target_expr)[j] /= gcd1;
937           for (j = 0; j < invariants; j++)
938             LLE_INVARIANT_COEFFICIENTS (target_expr)[j] /= gcd1;
939           LLE_CONSTANT (target_expr) /= gcd1;
940           LLE_DENOMINATOR (target_expr) /= gcd1;
941           /* Ignore if equal to existing bound.  */
942           if (!lle_equal (LL_UPPER_BOUND (target_loop), target_expr, depth,
943                           invariants))
944             {
945               LLE_NEXT (target_expr) = LL_UPPER_BOUND (target_loop);
946               LL_UPPER_BOUND (target_loop) = target_expr;
947             }
948         }
949     }
950   for (i = 0; i < depth; i++)
951     {
952       target_loop = LN_LOOPS (target_nest)[i];
953       /* If necessary, exchange the upper and lower bounds and negate
954          the step size.  */
955       if (stepsigns[i] < 0)
956         {
957           LL_STEP (target_loop) *= -1;
958           tmp_expr = LL_LOWER_BOUND (target_loop);
959           LL_LOWER_BOUND (target_loop) = LL_UPPER_BOUND (target_loop);
960           LL_UPPER_BOUND (target_loop) = tmp_expr;
961         }
962     }
963   return target_nest;
964 }
965
966 /* Compute the step signs of TRANS, using TRANS and stepsigns.  Return the new
967    result.  */
968
969 static lambda_vector
970 lambda_compute_step_signs (lambda_trans_matrix trans, lambda_vector stepsigns)
971 {
972   lambda_matrix matrix, H;
973   int size;
974   lambda_vector newsteps;
975   int i, j, factor, minimum_column;
976   int temp;
977
978   matrix = LTM_MATRIX (trans);
979   size = LTM_ROWSIZE (trans);
980   H = lambda_matrix_new (size, size);
981
982   newsteps = lambda_vector_new (size);
983   lambda_vector_copy (stepsigns, newsteps, size);
984
985   lambda_matrix_copy (matrix, H, size, size);
986
987   for (j = 0; j < size; j++)
988     {
989       lambda_vector row;
990       row = H[j];
991       for (i = j; i < size; i++)
992         if (row[i] < 0)
993           lambda_matrix_col_negate (H, size, i);
994       while (lambda_vector_first_nz (row, size, j + 1) < size)
995         {
996           minimum_column = lambda_vector_min_nz (row, size, j);
997           lambda_matrix_col_exchange (H, size, j, minimum_column);
998
999           temp = newsteps[j];
1000           newsteps[j] = newsteps[minimum_column];
1001           newsteps[minimum_column] = temp;
1002
1003           for (i = j + 1; i < size; i++)
1004             {
1005               factor = row[i] / row[j];
1006               lambda_matrix_col_add (H, size, j, i, -1 * factor);
1007             }
1008         }
1009     }
1010   return newsteps;
1011 }
1012
1013 /* Transform NEST according to TRANS, and return the new loopnest.
1014    This involves
1015    1. Computing a lattice base for the transformation
1016    2. Composing the dense base with the specified transformation (TRANS)
1017    3. Decomposing the combined transformation into a lower triangular portion,
1018    and a unimodular portion. 
1019    4. Computing the auxiliary nest using the unimodular portion.
1020    5. Computing the target nest using the auxiliary nest and the lower
1021    triangular portion.  */ 
1022
1023 lambda_loopnest
1024 lambda_loopnest_transform (lambda_loopnest nest, lambda_trans_matrix trans)
1025 {
1026   lambda_loopnest auxillary_nest, target_nest;
1027
1028   int depth, invariants;
1029   int i, j;
1030   lambda_lattice lattice;
1031   lambda_trans_matrix trans1, H, U;
1032   lambda_loop loop;
1033   lambda_linear_expression expression;
1034   lambda_vector origin;
1035   lambda_matrix origin_invariants;
1036   lambda_vector stepsigns;
1037   int f;
1038
1039   depth = LN_DEPTH (nest);
1040   invariants = LN_INVARIANTS (nest);
1041
1042   /* Keep track of the signs of the loop steps.  */
1043   stepsigns = lambda_vector_new (depth);
1044   for (i = 0; i < depth; i++)
1045     {
1046       if (LL_STEP (LN_LOOPS (nest)[i]) > 0)
1047         stepsigns[i] = 1;
1048       else
1049         stepsigns[i] = -1;
1050     }
1051
1052   /* Compute the lattice base.  */
1053   lattice = lambda_lattice_compute_base (nest);
1054   trans1 = lambda_trans_matrix_new (depth, depth);
1055
1056   /* Multiply the transformation matrix by the lattice base.  */
1057
1058   lambda_matrix_mult (LTM_MATRIX (trans), LATTICE_BASE (lattice),
1059                       LTM_MATRIX (trans1), depth, depth, depth);
1060
1061   /* Compute the Hermite normal form for the new transformation matrix.  */
1062   H = lambda_trans_matrix_new (depth, depth);
1063   U = lambda_trans_matrix_new (depth, depth);
1064   lambda_matrix_hermite (LTM_MATRIX (trans1), depth, LTM_MATRIX (H),
1065                          LTM_MATRIX (U));
1066
1067   /* Compute the auxiliary loop nest's space from the unimodular
1068      portion.  */
1069   auxillary_nest = lambda_compute_auxillary_space (nest, U);
1070
1071   /* Compute the loop step signs from the old step signs and the
1072      transformation matrix.  */
1073   stepsigns = lambda_compute_step_signs (trans1, stepsigns);
1074
1075   /* Compute the target loop nest space from the auxiliary nest and
1076      the lower triangular matrix H.  */
1077   target_nest = lambda_compute_target_space (auxillary_nest, H, stepsigns);
1078   origin = lambda_vector_new (depth);
1079   origin_invariants = lambda_matrix_new (depth, invariants);
1080   lambda_matrix_vector_mult (LTM_MATRIX (trans), depth, depth,
1081                              LATTICE_ORIGIN (lattice), origin);
1082   lambda_matrix_mult (LTM_MATRIX (trans), LATTICE_ORIGIN_INVARIANTS (lattice),
1083                       origin_invariants, depth, depth, invariants);
1084
1085   for (i = 0; i < depth; i++)
1086     {
1087       loop = LN_LOOPS (target_nest)[i];
1088       expression = LL_LINEAR_OFFSET (loop);
1089       if (lambda_vector_zerop (LLE_COEFFICIENTS (expression), depth))
1090         f = 1;
1091       else
1092         f = LLE_DENOMINATOR (expression);
1093
1094       LLE_CONSTANT (expression) += f * origin[i];
1095
1096       for (j = 0; j < invariants; j++)
1097         LLE_INVARIANT_COEFFICIENTS (expression)[j] +=
1098           f * origin_invariants[i][j];
1099     }
1100
1101   return target_nest;
1102
1103 }
1104
1105 /* Convert a gcc tree expression EXPR to a lambda linear expression, and
1106    return the new expression.  DEPTH is the depth of the loopnest.
1107    OUTERINDUCTIONVARS is an array of the induction variables for outer loops
1108    in this nest.  INVARIANTS is the array of invariants for the loop.  EXTRA
1109    is the amount we have to add/subtract from the expression because of the
1110    type of comparison it is used in.  */
1111
1112 static lambda_linear_expression
1113 gcc_tree_to_linear_expression (int depth, tree expr,
1114                                VEC(tree,heap) *outerinductionvars,
1115                                VEC(tree,heap) *invariants, int extra)
1116 {
1117   lambda_linear_expression lle = NULL;
1118   switch (TREE_CODE (expr))
1119     {
1120     case INTEGER_CST:
1121       {
1122         lle = lambda_linear_expression_new (depth, 2 * depth);
1123         LLE_CONSTANT (lle) = TREE_INT_CST_LOW (expr);
1124         if (extra != 0)
1125           LLE_CONSTANT (lle) += extra;
1126
1127         LLE_DENOMINATOR (lle) = 1;
1128       }
1129       break;
1130     case SSA_NAME:
1131       {
1132         tree iv, invar;
1133         size_t i;
1134         for (i = 0; VEC_iterate (tree, outerinductionvars, i, iv); i++)
1135           if (iv != NULL)
1136             {
1137               if (SSA_NAME_VAR (iv) == SSA_NAME_VAR (expr))
1138                 {
1139                   lle = lambda_linear_expression_new (depth, 2 * depth);
1140                   LLE_COEFFICIENTS (lle)[i] = 1;
1141                   if (extra != 0)
1142                     LLE_CONSTANT (lle) = extra;
1143
1144                   LLE_DENOMINATOR (lle) = 1;
1145                 }
1146             }
1147         for (i = 0; VEC_iterate (tree, invariants, i, invar); i++)
1148           if (invar != NULL)
1149             {
1150               if (SSA_NAME_VAR (invar) == SSA_NAME_VAR (expr))
1151                 {
1152                   lle = lambda_linear_expression_new (depth, 2 * depth);
1153                   LLE_INVARIANT_COEFFICIENTS (lle)[i] = 1;
1154                   if (extra != 0)
1155                     LLE_CONSTANT (lle) = extra;
1156                   LLE_DENOMINATOR (lle) = 1;
1157                 }
1158             }
1159       }
1160       break;
1161     default:
1162       return NULL;
1163     }
1164
1165   return lle;
1166 }
1167
1168 /* Return the depth of the loopnest NEST */
1169
1170 static int 
1171 depth_of_nest (struct loop *nest)
1172 {
1173   size_t depth = 0;
1174   while (nest)
1175     {
1176       depth++;
1177       nest = nest->inner;
1178     }
1179   return depth;
1180 }
1181
1182
1183 /* Return true if OP is invariant in LOOP and all outer loops.  */
1184
1185 static bool
1186 invariant_in_loop_and_outer_loops (struct loop *loop, tree op)
1187 {
1188   if (is_gimple_min_invariant (op))
1189     return true;
1190   if (loop_depth (loop) == 0)
1191     return true;
1192   if (!expr_invariant_in_loop_p (loop, op))
1193     return false;
1194   if (!invariant_in_loop_and_outer_loops (loop_outer (loop), op))
1195     return false;
1196   return true;
1197 }
1198
1199 /* Generate a lambda loop from a gcc loop LOOP.  Return the new lambda loop,
1200    or NULL if it could not be converted.
1201    DEPTH is the depth of the loop.
1202    INVARIANTS is a pointer to the array of loop invariants.
1203    The induction variable for this loop should be stored in the parameter
1204    OURINDUCTIONVAR.
1205    OUTERINDUCTIONVARS is an array of induction variables for outer loops.  */
1206
1207 static lambda_loop
1208 gcc_loop_to_lambda_loop (struct loop *loop, int depth,
1209                          VEC(tree,heap) ** invariants,
1210                          tree * ourinductionvar,
1211                          VEC(tree,heap) * outerinductionvars,
1212                          VEC(tree,heap) ** lboundvars,
1213                          VEC(tree,heap) ** uboundvars,
1214                          VEC(int,heap) ** steps)
1215 {
1216   tree phi;
1217   tree exit_cond;
1218   tree access_fn, inductionvar;
1219   tree step;
1220   lambda_loop lloop = NULL;
1221   lambda_linear_expression lbound, ubound;
1222   tree test;
1223   int stepint;
1224   int extra = 0;
1225   tree lboundvar, uboundvar, uboundresult;
1226
1227   /* Find out induction var and exit condition.  */
1228   inductionvar = find_induction_var_from_exit_cond (loop);
1229   exit_cond = get_loop_exit_condition (loop);
1230
1231   if (inductionvar == NULL || exit_cond == NULL)
1232     {
1233       if (dump_file && (dump_flags & TDF_DETAILS))
1234         fprintf (dump_file,
1235                  "Unable to convert loop: Cannot determine exit condition or induction variable for loop.\n");
1236       return NULL;
1237     }
1238
1239   test = TREE_OPERAND (exit_cond, 0);
1240
1241   if (SSA_NAME_DEF_STMT (inductionvar) == NULL_TREE)
1242     {
1243
1244       if (dump_file && (dump_flags & TDF_DETAILS))
1245         fprintf (dump_file,
1246                  "Unable to convert loop: Cannot find PHI node for induction variable\n");
1247
1248       return NULL;
1249     }
1250
1251   phi = SSA_NAME_DEF_STMT (inductionvar);
1252   if (TREE_CODE (phi) != PHI_NODE)
1253     {
1254       phi = SINGLE_SSA_TREE_OPERAND (phi, SSA_OP_USE);
1255       if (!phi)
1256         {
1257
1258           if (dump_file && (dump_flags & TDF_DETAILS))
1259             fprintf (dump_file,
1260                      "Unable to convert loop: Cannot find PHI node for induction variable\n");
1261
1262           return NULL;
1263         }
1264
1265       phi = SSA_NAME_DEF_STMT (phi);
1266       if (TREE_CODE (phi) != PHI_NODE)
1267         {
1268
1269           if (dump_file && (dump_flags & TDF_DETAILS))
1270             fprintf (dump_file,
1271                      "Unable to convert loop: Cannot find PHI node for induction variable\n");
1272           return NULL;
1273         }
1274
1275     }
1276
1277   /* The induction variable name/version we want to put in the array is the
1278      result of the induction variable phi node.  */
1279   *ourinductionvar = PHI_RESULT (phi);
1280   access_fn = instantiate_parameters
1281     (loop, analyze_scalar_evolution (loop, PHI_RESULT (phi)));
1282   if (access_fn == chrec_dont_know)
1283     {
1284       if (dump_file && (dump_flags & TDF_DETAILS))
1285         fprintf (dump_file,
1286                  "Unable to convert loop: Access function for induction variable phi is unknown\n");
1287
1288       return NULL;
1289     }
1290
1291   step = evolution_part_in_loop_num (access_fn, loop->num);
1292   if (!step || step == chrec_dont_know)
1293     {
1294       if (dump_file && (dump_flags & TDF_DETAILS))
1295         fprintf (dump_file,
1296                  "Unable to convert loop: Cannot determine step of loop.\n");
1297
1298       return NULL;
1299     }
1300   if (TREE_CODE (step) != INTEGER_CST)
1301     {
1302
1303       if (dump_file && (dump_flags & TDF_DETAILS))
1304         fprintf (dump_file,
1305                  "Unable to convert loop: Step of loop is not integer.\n");
1306       return NULL;
1307     }
1308
1309   stepint = TREE_INT_CST_LOW (step);
1310
1311   /* Only want phis for induction vars, which will have two
1312      arguments.  */
1313   if (PHI_NUM_ARGS (phi) != 2)
1314     {
1315       if (dump_file && (dump_flags & TDF_DETAILS))
1316         fprintf (dump_file,
1317                  "Unable to convert loop: PHI node for induction variable has >2 arguments\n");
1318       return NULL;
1319     }
1320
1321   /* Another induction variable check. One argument's source should be
1322      in the loop, one outside the loop.  */
1323   if (flow_bb_inside_loop_p (loop, PHI_ARG_EDGE (phi, 0)->src)
1324       && flow_bb_inside_loop_p (loop, PHI_ARG_EDGE (phi, 1)->src))
1325     {
1326
1327       if (dump_file && (dump_flags & TDF_DETAILS))
1328         fprintf (dump_file,
1329                  "Unable to convert loop: PHI edges both inside loop, or both outside loop.\n");
1330
1331       return NULL;
1332     }
1333
1334   if (flow_bb_inside_loop_p (loop, PHI_ARG_EDGE (phi, 0)->src))
1335     {
1336       lboundvar = PHI_ARG_DEF (phi, 1);
1337       lbound = gcc_tree_to_linear_expression (depth, lboundvar,
1338                                               outerinductionvars, *invariants,
1339                                               0);
1340     }
1341   else
1342     {
1343       lboundvar = PHI_ARG_DEF (phi, 0);
1344       lbound = gcc_tree_to_linear_expression (depth, lboundvar,
1345                                               outerinductionvars, *invariants,
1346                                               0);
1347     }
1348   
1349   if (!lbound)
1350     {
1351
1352       if (dump_file && (dump_flags & TDF_DETAILS))
1353         fprintf (dump_file,
1354                  "Unable to convert loop: Cannot convert lower bound to linear expression\n");
1355
1356       return NULL;
1357     }
1358   /* One part of the test may be a loop invariant tree.  */
1359   VEC_reserve (tree, heap, *invariants, 1);
1360   if (TREE_CODE (TREE_OPERAND (test, 1)) == SSA_NAME
1361       && invariant_in_loop_and_outer_loops (loop, TREE_OPERAND (test, 1)))
1362     VEC_quick_push (tree, *invariants, TREE_OPERAND (test, 1));
1363   else if (TREE_CODE (TREE_OPERAND (test, 0)) == SSA_NAME
1364            && invariant_in_loop_and_outer_loops (loop, TREE_OPERAND (test, 0)))
1365     VEC_quick_push (tree, *invariants, TREE_OPERAND (test, 0));
1366   
1367   /* The non-induction variable part of the test is the upper bound variable.
1368    */
1369   if (TREE_OPERAND (test, 0) == inductionvar)
1370     uboundvar = TREE_OPERAND (test, 1);
1371   else
1372     uboundvar = TREE_OPERAND (test, 0);
1373     
1374
1375   /* We only size the vectors assuming we have, at max, 2 times as many
1376      invariants as we do loops (one for each bound).
1377      This is just an arbitrary number, but it has to be matched against the
1378      code below.  */
1379   gcc_assert (VEC_length (tree, *invariants) <= (unsigned int) (2 * depth));
1380   
1381
1382   /* We might have some leftover.  */
1383   if (TREE_CODE (test) == LT_EXPR)
1384     extra = -1 * stepint;
1385   else if (TREE_CODE (test) == NE_EXPR)
1386     extra = -1 * stepint;
1387   else if (TREE_CODE (test) == GT_EXPR)
1388     extra = -1 * stepint;
1389   else if (TREE_CODE (test) == EQ_EXPR)
1390     extra = 1 * stepint;
1391   
1392   ubound = gcc_tree_to_linear_expression (depth, uboundvar,
1393                                           outerinductionvars,
1394                                           *invariants, extra);
1395   uboundresult = build2 (PLUS_EXPR, TREE_TYPE (uboundvar), uboundvar,
1396                          build_int_cst (TREE_TYPE (uboundvar), extra));
1397   VEC_safe_push (tree, heap, *uboundvars, uboundresult);
1398   VEC_safe_push (tree, heap, *lboundvars, lboundvar);
1399   VEC_safe_push (int, heap, *steps, stepint);
1400   if (!ubound)
1401     {
1402       if (dump_file && (dump_flags & TDF_DETAILS))
1403         fprintf (dump_file,
1404                  "Unable to convert loop: Cannot convert upper bound to linear expression\n");
1405       return NULL;
1406     }
1407
1408   lloop = lambda_loop_new ();
1409   LL_STEP (lloop) = stepint;
1410   LL_LOWER_BOUND (lloop) = lbound;
1411   LL_UPPER_BOUND (lloop) = ubound;
1412   return lloop;
1413 }
1414
1415 /* Given a LOOP, find the induction variable it is testing against in the exit
1416    condition.  Return the induction variable if found, NULL otherwise.  */
1417
1418 static tree
1419 find_induction_var_from_exit_cond (struct loop *loop)
1420 {
1421   tree expr = get_loop_exit_condition (loop);
1422   tree ivarop;
1423   tree test;
1424   if (expr == NULL_TREE)
1425     return NULL_TREE;
1426   if (TREE_CODE (expr) != COND_EXPR)
1427     return NULL_TREE;
1428   test = TREE_OPERAND (expr, 0);
1429   if (!COMPARISON_CLASS_P (test))
1430     return NULL_TREE;
1431
1432   /* Find the side that is invariant in this loop. The ivar must be the other
1433      side.  */
1434   
1435   if (expr_invariant_in_loop_p (loop, TREE_OPERAND (test, 0)))
1436       ivarop = TREE_OPERAND (test, 1);
1437   else if (expr_invariant_in_loop_p (loop, TREE_OPERAND (test, 1)))
1438       ivarop = TREE_OPERAND (test, 0);
1439   else
1440     return NULL_TREE;
1441
1442   if (TREE_CODE (ivarop) != SSA_NAME)
1443     return NULL_TREE;
1444   return ivarop;
1445 }
1446
1447 DEF_VEC_P(lambda_loop);
1448 DEF_VEC_ALLOC_P(lambda_loop,heap);
1449
1450 /* Generate a lambda loopnest from a gcc loopnest LOOP_NEST.
1451    Return the new loop nest.  
1452    INDUCTIONVARS is a pointer to an array of induction variables for the
1453    loopnest that will be filled in during this process.
1454    INVARIANTS is a pointer to an array of invariants that will be filled in
1455    during this process.  */
1456
1457 lambda_loopnest
1458 gcc_loopnest_to_lambda_loopnest (struct loop *loop_nest,
1459                                  VEC(tree,heap) **inductionvars,
1460                                  VEC(tree,heap) **invariants)
1461 {
1462   lambda_loopnest ret = NULL;
1463   struct loop *temp = loop_nest;
1464   int depth = depth_of_nest (loop_nest);
1465   size_t i;
1466   VEC(lambda_loop,heap) *loops = NULL;
1467   VEC(tree,heap) *uboundvars = NULL;
1468   VEC(tree,heap) *lboundvars  = NULL;
1469   VEC(int,heap) *steps = NULL;
1470   lambda_loop newloop;
1471   tree inductionvar = NULL;
1472   bool perfect_nest = perfect_nest_p (loop_nest);
1473
1474   if (!perfect_nest && !can_convert_to_perfect_nest (loop_nest))
1475     goto fail;
1476
1477   while (temp)
1478     {
1479       newloop = gcc_loop_to_lambda_loop (temp, depth, invariants,
1480                                          &inductionvar, *inductionvars,
1481                                          &lboundvars, &uboundvars,
1482                                          &steps);
1483       if (!newloop)
1484         goto fail;
1485
1486       VEC_safe_push (tree, heap, *inductionvars, inductionvar);
1487       VEC_safe_push (lambda_loop, heap, loops, newloop);
1488       temp = temp->inner;
1489     }
1490
1491   if (!perfect_nest)
1492     {
1493       if (!perfect_nestify (loop_nest, lboundvars, uboundvars, steps,
1494                             *inductionvars))
1495         {
1496           if (dump_file)
1497             fprintf (dump_file,
1498                      "Not a perfect loop nest and couldn't convert to one.\n");    
1499           goto fail;
1500         }
1501       else if (dump_file)
1502         fprintf (dump_file,
1503                  "Successfully converted loop nest to perfect loop nest.\n");
1504     }
1505
1506   ret = lambda_loopnest_new (depth, 2 * depth);
1507
1508   for (i = 0; VEC_iterate (lambda_loop, loops, i, newloop); i++)
1509     LN_LOOPS (ret)[i] = newloop;
1510
1511  fail:
1512   VEC_free (lambda_loop, heap, loops);
1513   VEC_free (tree, heap, uboundvars);
1514   VEC_free (tree, heap, lboundvars);
1515   VEC_free (int, heap, steps);
1516   
1517   return ret;
1518 }
1519
1520 /* Convert a lambda body vector LBV to a gcc tree, and return the new tree. 
1521    STMTS_TO_INSERT is a pointer to a tree where the statements we need to be
1522    inserted for us are stored.  INDUCTION_VARS is the array of induction
1523    variables for the loop this LBV is from.  TYPE is the tree type to use for
1524    the variables and trees involved.  */
1525
1526 static tree
1527 lbv_to_gcc_expression (lambda_body_vector lbv, 
1528                        tree type, VEC(tree,heap) *induction_vars, 
1529                        tree *stmts_to_insert)
1530 {
1531   tree stmts, stmt, resvar, name;
1532   tree iv;
1533   size_t i;
1534   tree_stmt_iterator tsi;
1535
1536   /* Create a statement list and a linear expression temporary.  */
1537   stmts = alloc_stmt_list ();
1538   resvar = create_tmp_var (type, "lbvtmp");
1539   add_referenced_var (resvar);
1540
1541   /* Start at 0.  */
1542   stmt = build_gimple_modify_stmt (resvar,
1543                                    fold_convert (type, integer_zero_node));
1544   name = make_ssa_name (resvar, stmt);
1545   GIMPLE_STMT_OPERAND (stmt, 0) = name;
1546   tsi = tsi_last (stmts);
1547   tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1548
1549   for (i = 0; VEC_iterate (tree, induction_vars, i, iv); i++)
1550     {
1551       if (LBV_COEFFICIENTS (lbv)[i] != 0)
1552         {
1553           tree newname;
1554           tree coeffmult;
1555           
1556           /* newname = coefficient * induction_variable */
1557           coeffmult = build_int_cst (type, LBV_COEFFICIENTS (lbv)[i]);
1558           stmt = build_gimple_modify_stmt (resvar,
1559                                            fold_build2 (MULT_EXPR, type,
1560                                                         iv, coeffmult));
1561
1562           newname = make_ssa_name (resvar, stmt);
1563           GIMPLE_STMT_OPERAND (stmt, 0) = newname;
1564           fold_stmt (&stmt);
1565           tsi = tsi_last (stmts);
1566           tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1567
1568           /* name = name + newname */
1569           stmt = build_gimple_modify_stmt (resvar,
1570                                            build2 (PLUS_EXPR, type,
1571                                                    name, newname));
1572           name = make_ssa_name (resvar, stmt);
1573           GIMPLE_STMT_OPERAND (stmt, 0) = name;
1574           fold_stmt (&stmt);
1575           tsi = tsi_last (stmts);
1576           tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1577
1578         }
1579     }
1580
1581   /* Handle any denominator that occurs.  */
1582   if (LBV_DENOMINATOR (lbv) != 1)
1583     {
1584       tree denominator = build_int_cst (type, LBV_DENOMINATOR (lbv));
1585       stmt = build_gimple_modify_stmt (resvar,
1586                                        build2 (CEIL_DIV_EXPR, type,
1587                                                name, denominator));
1588       name = make_ssa_name (resvar, stmt);
1589       GIMPLE_STMT_OPERAND (stmt, 0) = name;
1590       fold_stmt (&stmt);
1591       tsi = tsi_last (stmts);
1592       tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1593     }
1594   *stmts_to_insert = stmts;
1595   return name;
1596 }
1597
1598 /* Convert a linear expression from coefficient and constant form to a
1599    gcc tree.
1600    Return the tree that represents the final value of the expression.
1601    LLE is the linear expression to convert.
1602    OFFSET is the linear offset to apply to the expression.
1603    TYPE is the tree type to use for the variables and math. 
1604    INDUCTION_VARS is a vector of induction variables for the loops.
1605    INVARIANTS is a vector of the loop nest invariants.
1606    WRAP specifies what tree code to wrap the results in, if there is more than
1607    one (it is either MAX_EXPR, or MIN_EXPR).
1608    STMTS_TO_INSERT Is a pointer to the statement list we fill in with
1609    statements that need to be inserted for the linear expression.  */
1610
1611 static tree
1612 lle_to_gcc_expression (lambda_linear_expression lle,
1613                        lambda_linear_expression offset,
1614                        tree type,
1615                        VEC(tree,heap) *induction_vars,
1616                        VEC(tree,heap) *invariants,
1617                        enum tree_code wrap, tree *stmts_to_insert)
1618 {
1619   tree stmts, stmt, resvar, name;
1620   size_t i;
1621   tree_stmt_iterator tsi;
1622   tree iv, invar;
1623   VEC(tree,heap) *results = NULL;
1624
1625   gcc_assert (wrap == MAX_EXPR || wrap == MIN_EXPR);
1626   name = NULL_TREE;
1627   /* Create a statement list and a linear expression temporary.  */
1628   stmts = alloc_stmt_list ();
1629   resvar = create_tmp_var (type, "lletmp");
1630   add_referenced_var (resvar);
1631
1632   /* Build up the linear expressions, and put the variable representing the
1633      result in the results array.  */
1634   for (; lle != NULL; lle = LLE_NEXT (lle))
1635     {
1636       /* Start at name = 0.  */
1637       stmt = build_gimple_modify_stmt (resvar,
1638                                        fold_convert (type, integer_zero_node));
1639       name = make_ssa_name (resvar, stmt);
1640       GIMPLE_STMT_OPERAND (stmt, 0) = name;
1641       fold_stmt (&stmt);
1642       tsi = tsi_last (stmts);
1643       tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1644
1645       /* First do the induction variables.  
1646          at the end, name = name + all the induction variables added
1647          together.  */
1648       for (i = 0; VEC_iterate (tree, induction_vars, i, iv); i++)
1649         {
1650           if (LLE_COEFFICIENTS (lle)[i] != 0)
1651             {
1652               tree newname;
1653               tree mult;
1654               tree coeff;
1655
1656               /* mult = induction variable * coefficient.  */
1657               if (LLE_COEFFICIENTS (lle)[i] == 1)
1658                 {
1659                   mult = VEC_index (tree, induction_vars, i);
1660                 }
1661               else
1662                 {
1663                   coeff = build_int_cst (type,
1664                                          LLE_COEFFICIENTS (lle)[i]);
1665                   mult = fold_build2 (MULT_EXPR, type, iv, coeff);
1666                 }
1667
1668               /* newname = mult */
1669               stmt = build_gimple_modify_stmt (resvar, mult);
1670               newname = make_ssa_name (resvar, stmt);
1671               GIMPLE_STMT_OPERAND (stmt, 0) = newname;
1672               fold_stmt (&stmt);
1673               tsi = tsi_last (stmts);
1674               tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1675
1676               /* name = name + newname */
1677               stmt = build_gimple_modify_stmt (resvar,
1678                                                build2 (PLUS_EXPR, type,
1679                                                        name, newname));
1680               name = make_ssa_name (resvar, stmt);
1681               GIMPLE_STMT_OPERAND (stmt, 0) = name;
1682               fold_stmt (&stmt);
1683               tsi = tsi_last (stmts);
1684               tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1685             }
1686         }
1687
1688       /* Handle our invariants.
1689          At the end, we have name = name + result of adding all multiplied
1690          invariants.  */
1691       for (i = 0; VEC_iterate (tree, invariants, i, invar); i++)
1692         {
1693           if (LLE_INVARIANT_COEFFICIENTS (lle)[i] != 0)
1694             {
1695               tree newname;
1696               tree mult;
1697               tree coeff;
1698               int invcoeff = LLE_INVARIANT_COEFFICIENTS (lle)[i];
1699               /* mult = invariant * coefficient  */
1700               if (invcoeff == 1)
1701                 {
1702                   mult = invar;
1703                 }
1704               else
1705                 {
1706                   coeff = build_int_cst (type, invcoeff);
1707                   mult = fold_build2 (MULT_EXPR, type, invar, coeff);
1708                 }
1709
1710               /* newname = mult */
1711               stmt = build_gimple_modify_stmt (resvar, mult);
1712               newname = make_ssa_name (resvar, stmt);
1713               GIMPLE_STMT_OPERAND (stmt, 0) = newname;
1714               fold_stmt (&stmt);
1715               tsi = tsi_last (stmts);
1716               tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1717
1718               /* name = name + newname */
1719               stmt = build_gimple_modify_stmt (resvar,
1720                                                build2 (PLUS_EXPR, type,
1721                                                        name, newname));
1722               name = make_ssa_name (resvar, stmt);
1723               GIMPLE_STMT_OPERAND (stmt, 0) = name;
1724               fold_stmt (&stmt);
1725               tsi = tsi_last (stmts);
1726               tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1727             }
1728         }
1729
1730       /* Now handle the constant.
1731          name = name + constant.  */
1732       if (LLE_CONSTANT (lle) != 0)
1733         {
1734           tree incr = build_int_cst (type, LLE_CONSTANT (lle));
1735           stmt = build_gimple_modify_stmt (resvar, build2 (PLUS_EXPR, type,
1736                                                            name, incr));
1737           name = make_ssa_name (resvar, stmt);
1738           GIMPLE_STMT_OPERAND (stmt, 0) = name;
1739           fold_stmt (&stmt);
1740           tsi = tsi_last (stmts);
1741           tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1742         }
1743
1744       /* Now handle the offset.
1745          name = name + linear offset.  */
1746       if (LLE_CONSTANT (offset) != 0)
1747         {
1748           tree incr = build_int_cst (type, LLE_CONSTANT (offset));
1749           stmt = build_gimple_modify_stmt (resvar, build2 (PLUS_EXPR, type,
1750                                                            name, incr));
1751           name = make_ssa_name (resvar, stmt);
1752           GIMPLE_STMT_OPERAND (stmt, 0) = name;
1753           fold_stmt (&stmt);
1754           tsi = tsi_last (stmts);
1755           tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1756         }
1757
1758       /* Handle any denominator that occurs.  */
1759       if (LLE_DENOMINATOR (lle) != 1)
1760         {
1761           stmt = build_int_cst (type, LLE_DENOMINATOR (lle));
1762           stmt = build2 (wrap == MAX_EXPR ? CEIL_DIV_EXPR : FLOOR_DIV_EXPR,
1763                          type, name, stmt);
1764           stmt = build_gimple_modify_stmt (resvar, stmt);
1765
1766           /* name = {ceil, floor}(name/denominator) */
1767           name = make_ssa_name (resvar, stmt);
1768           GIMPLE_STMT_OPERAND (stmt, 0) = name;
1769           tsi = tsi_last (stmts);
1770           tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1771         }
1772       VEC_safe_push (tree, heap, results, name);
1773     }
1774
1775   /* Again, out of laziness, we don't handle this case yet.  It's not
1776      hard, it just hasn't occurred.  */
1777   gcc_assert (VEC_length (tree, results) <= 2);
1778   
1779   /* We may need to wrap the results in a MAX_EXPR or MIN_EXPR.  */
1780   if (VEC_length (tree, results) > 1)
1781     {
1782       tree op1 = VEC_index (tree, results, 0);
1783       tree op2 = VEC_index (tree, results, 1);
1784       stmt = build_gimple_modify_stmt (resvar, build2 (wrap, type, op1, op2));
1785       name = make_ssa_name (resvar, stmt);
1786       GIMPLE_STMT_OPERAND (stmt, 0) = name;
1787       tsi = tsi_last (stmts);
1788       tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1789     }
1790
1791   VEC_free (tree, heap, results);
1792   
1793   *stmts_to_insert = stmts;
1794   return name;
1795 }
1796
1797 /* Transform a lambda loopnest NEW_LOOPNEST, which had TRANSFORM applied to
1798    it, back into gcc code.  This changes the
1799    loops, their induction variables, and their bodies, so that they
1800    match the transformed loopnest.  
1801    OLD_LOOPNEST is the loopnest before we've replaced it with the new
1802    loopnest.
1803    OLD_IVS is a vector of induction variables from the old loopnest.
1804    INVARIANTS is a vector of loop invariants from the old loopnest.
1805    NEW_LOOPNEST is the new lambda loopnest to replace OLD_LOOPNEST with.
1806    TRANSFORM is the matrix transform that was applied to OLD_LOOPNEST to get 
1807    NEW_LOOPNEST.  */
1808
1809 void
1810 lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest,
1811                                  VEC(tree,heap) *old_ivs,
1812                                  VEC(tree,heap) *invariants,
1813                                  lambda_loopnest new_loopnest,
1814                                  lambda_trans_matrix transform)
1815 {
1816   struct loop *temp;
1817   size_t i = 0;
1818   size_t depth = 0;
1819   VEC(tree,heap) *new_ivs = NULL;
1820   tree oldiv;
1821   
1822   block_stmt_iterator bsi;
1823
1824   if (dump_file)
1825     {
1826       transform = lambda_trans_matrix_inverse (transform);
1827       fprintf (dump_file, "Inverse of transformation matrix:\n");
1828       print_lambda_trans_matrix (dump_file, transform);
1829     }
1830   depth = depth_of_nest (old_loopnest);
1831   temp = old_loopnest;
1832
1833   while (temp)
1834     {
1835       lambda_loop newloop;
1836       basic_block bb;
1837       edge exit;
1838       tree ivvar, ivvarinced, exitcond, stmts;
1839       enum tree_code testtype;
1840       tree newupperbound, newlowerbound;
1841       lambda_linear_expression offset;
1842       tree type;
1843       bool insert_after;
1844       tree inc_stmt;
1845
1846       oldiv = VEC_index (tree, old_ivs, i);
1847       type = TREE_TYPE (oldiv);
1848
1849       /* First, build the new induction variable temporary  */
1850
1851       ivvar = create_tmp_var (type, "lnivtmp");
1852       add_referenced_var (ivvar);
1853
1854       VEC_safe_push (tree, heap, new_ivs, ivvar);
1855
1856       newloop = LN_LOOPS (new_loopnest)[i];
1857
1858       /* Linear offset is a bit tricky to handle.  Punt on the unhandled
1859          cases for now.  */
1860       offset = LL_LINEAR_OFFSET (newloop);
1861       
1862       gcc_assert (LLE_DENOMINATOR (offset) == 1 &&
1863                   lambda_vector_zerop (LLE_COEFFICIENTS (offset), depth));
1864             
1865       /* Now build the  new lower bounds, and insert the statements
1866          necessary to generate it on the loop preheader.  */
1867       newlowerbound = lle_to_gcc_expression (LL_LOWER_BOUND (newloop),
1868                                              LL_LINEAR_OFFSET (newloop),
1869                                              type,
1870                                              new_ivs,
1871                                              invariants, MAX_EXPR, &stmts);
1872       bsi_insert_on_edge (loop_preheader_edge (temp), stmts);
1873       bsi_commit_edge_inserts ();
1874       /* Build the new upper bound and insert its statements in the
1875          basic block of the exit condition */
1876       newupperbound = lle_to_gcc_expression (LL_UPPER_BOUND (newloop),
1877                                              LL_LINEAR_OFFSET (newloop),
1878                                              type,
1879                                              new_ivs,
1880                                              invariants, MIN_EXPR, &stmts);
1881       exit = single_exit (temp);
1882       exitcond = get_loop_exit_condition (temp);
1883       bb = bb_for_stmt (exitcond);
1884       bsi = bsi_after_labels (bb);
1885       bsi_insert_before (&bsi, stmts, BSI_NEW_STMT);
1886
1887       /* Create the new iv.  */
1888
1889       standard_iv_increment_position (temp, &bsi, &insert_after);
1890       create_iv (newlowerbound,
1891                  build_int_cst (type, LL_STEP (newloop)),
1892                  ivvar, temp, &bsi, insert_after, &ivvar,
1893                  NULL);
1894
1895       /* Unfortunately, the incremented ivvar that create_iv inserted may not
1896          dominate the block containing the exit condition.
1897          So we simply create our own incremented iv to use in the new exit
1898          test,  and let redundancy elimination sort it out.  */
1899       inc_stmt = build2 (PLUS_EXPR, type, 
1900                          ivvar, build_int_cst (type, LL_STEP (newloop)));
1901       inc_stmt = build_gimple_modify_stmt (SSA_NAME_VAR (ivvar), inc_stmt);
1902       ivvarinced = make_ssa_name (SSA_NAME_VAR (ivvar), inc_stmt);
1903       GIMPLE_STMT_OPERAND (inc_stmt, 0) = ivvarinced;
1904       bsi = bsi_for_stmt (exitcond);
1905       bsi_insert_before (&bsi, inc_stmt, BSI_SAME_STMT);
1906
1907       /* Replace the exit condition with the new upper bound
1908          comparison.  */
1909       
1910       testtype = LL_STEP (newloop) >= 0 ? LE_EXPR : GE_EXPR;
1911       
1912       /* We want to build a conditional where true means exit the loop, and
1913          false means continue the loop.
1914          So swap the testtype if this isn't the way things are.*/
1915
1916       if (exit->flags & EDGE_FALSE_VALUE)
1917         testtype = swap_tree_comparison (testtype);
1918
1919       COND_EXPR_COND (exitcond) = build2 (testtype,
1920                                           boolean_type_node,
1921                                           newupperbound, ivvarinced);
1922       update_stmt (exitcond);
1923       VEC_replace (tree, new_ivs, i, ivvar);
1924
1925       i++;
1926       temp = temp->inner;
1927     }
1928
1929   /* Rewrite uses of the old ivs so that they are now specified in terms of
1930      the new ivs.  */
1931
1932   for (i = 0; VEC_iterate (tree, old_ivs, i, oldiv); i++)
1933     {
1934       imm_use_iterator imm_iter;
1935       use_operand_p use_p;
1936       tree oldiv_def;
1937       tree oldiv_stmt = SSA_NAME_DEF_STMT (oldiv);
1938       tree stmt;
1939
1940       if (TREE_CODE (oldiv_stmt) == PHI_NODE)
1941         oldiv_def = PHI_RESULT (oldiv_stmt);
1942       else
1943         oldiv_def = SINGLE_SSA_TREE_OPERAND (oldiv_stmt, SSA_OP_DEF);
1944       gcc_assert (oldiv_def != NULL_TREE);
1945
1946       FOR_EACH_IMM_USE_STMT (stmt, imm_iter, oldiv_def)
1947         {
1948           tree newiv, stmts;
1949           lambda_body_vector lbv, newlbv;
1950
1951           gcc_assert (TREE_CODE (stmt) != PHI_NODE);
1952
1953           /* Compute the new expression for the induction
1954              variable.  */
1955           depth = VEC_length (tree, new_ivs);
1956           lbv = lambda_body_vector_new (depth);
1957           LBV_COEFFICIENTS (lbv)[i] = 1;
1958           
1959           newlbv = lambda_body_vector_compute_new (transform, lbv);
1960
1961           newiv = lbv_to_gcc_expression (newlbv, TREE_TYPE (oldiv),
1962                                          new_ivs, &stmts);
1963           bsi = bsi_for_stmt (stmt);
1964           /* Insert the statements to build that
1965              expression.  */
1966           bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
1967
1968           FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
1969             propagate_value (use_p, newiv);
1970           update_stmt (stmt);
1971         }
1972     }
1973   VEC_free (tree, heap, new_ivs);
1974 }
1975
1976 /* Return TRUE if this is not interesting statement from the perspective of
1977    determining if we have a perfect loop nest.  */
1978
1979 static bool
1980 not_interesting_stmt (tree stmt)
1981 {
1982   /* Note that COND_EXPR's aren't interesting because if they were exiting the
1983      loop, we would have already failed the number of exits tests.  */
1984   if (TREE_CODE (stmt) == LABEL_EXPR
1985       || TREE_CODE (stmt) == GOTO_EXPR
1986       || TREE_CODE (stmt) == COND_EXPR)
1987     return true;
1988   return false;
1989 }
1990
1991 /* Return TRUE if PHI uses DEF for it's in-the-loop edge for LOOP.  */
1992
1993 static bool
1994 phi_loop_edge_uses_def (struct loop *loop, tree phi, tree def)
1995 {
1996   int i;
1997   for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1998     if (flow_bb_inside_loop_p (loop, PHI_ARG_EDGE (phi, i)->src))
1999       if (PHI_ARG_DEF (phi, i) == def)
2000         return true;
2001   return false;
2002 }
2003
2004 /* Return TRUE if STMT is a use of PHI_RESULT.  */
2005
2006 static bool
2007 stmt_uses_phi_result (tree stmt, tree phi_result)
2008 {
2009   tree use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
2010   
2011   /* This is conservatively true, because we only want SIMPLE bumpers
2012      of the form x +- constant for our pass.  */
2013   return (use == phi_result);
2014 }
2015
2016 /* STMT is a bumper stmt for LOOP if the version it defines is used in the
2017    in-loop-edge in a phi node, and the operand it uses is the result of that
2018    phi node. 
2019    I.E. i_29 = i_3 + 1
2020         i_3 = PHI (0, i_29);  */
2021
2022 static bool
2023 stmt_is_bumper_for_loop (struct loop *loop, tree stmt)
2024 {
2025   tree use;
2026   tree def;
2027   imm_use_iterator iter;
2028   use_operand_p use_p;
2029   
2030   def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
2031   if (!def)
2032     return false;
2033
2034   FOR_EACH_IMM_USE_FAST (use_p, iter, def)
2035     {
2036       use = USE_STMT (use_p);
2037       if (TREE_CODE (use) == PHI_NODE)
2038         {
2039           if (phi_loop_edge_uses_def (loop, use, def))
2040             if (stmt_uses_phi_result (stmt, PHI_RESULT (use)))
2041               return true;
2042         } 
2043     }
2044   return false;
2045 }
2046
2047
2048 /* Return true if LOOP is a perfect loop nest.
2049    Perfect loop nests are those loop nests where all code occurs in the
2050    innermost loop body.
2051    If S is a program statement, then
2052
2053    i.e. 
2054    DO I = 1, 20
2055        S1
2056        DO J = 1, 20
2057        ...
2058        END DO
2059    END DO
2060    is not a perfect loop nest because of S1.
2061    
2062    DO I = 1, 20
2063       DO J = 1, 20
2064         S1
2065         ...
2066       END DO
2067    END DO 
2068    is a perfect loop nest.  
2069
2070    Since we don't have high level loops anymore, we basically have to walk our
2071    statements and ignore those that are there because the loop needs them (IE
2072    the induction variable increment, and jump back to the top of the loop).  */
2073
2074 bool
2075 perfect_nest_p (struct loop *loop)
2076 {
2077   basic_block *bbs;
2078   size_t i;
2079   tree exit_cond;
2080
2081   if (!loop->inner)
2082     return true;
2083   bbs = get_loop_body (loop);
2084   exit_cond = get_loop_exit_condition (loop);
2085   for (i = 0; i < loop->num_nodes; i++)
2086     {
2087       if (bbs[i]->loop_father == loop)
2088         {
2089           block_stmt_iterator bsi;
2090           for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi))
2091             {
2092               tree stmt = bsi_stmt (bsi);
2093               if (stmt == exit_cond
2094                   || not_interesting_stmt (stmt)
2095                   || stmt_is_bumper_for_loop (loop, stmt))
2096                 continue;
2097               free (bbs);
2098               return false;
2099             }
2100         }
2101     }
2102   free (bbs);
2103   /* See if the inner loops are perfectly nested as well.  */
2104   if (loop->inner)    
2105     return perfect_nest_p (loop->inner);
2106   return true;
2107 }
2108
2109 /* Replace the USES of X in STMT, or uses with the same step as X with Y.
2110    YINIT is the initial value of Y, REPLACEMENTS is a hash table to
2111    avoid creating duplicate temporaries and FIRSTBSI is statement
2112    iterator where new temporaries should be inserted at the beginning
2113    of body basic block.  */
2114
2115 static void
2116 replace_uses_equiv_to_x_with_y (struct loop *loop, tree stmt, tree x, 
2117                                 int xstep, tree y, tree yinit,
2118                                 htab_t replacements,
2119                                 block_stmt_iterator *firstbsi)
2120 {
2121   ssa_op_iter iter;
2122   use_operand_p use_p;
2123
2124   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
2125     {
2126       tree use = USE_FROM_PTR (use_p);
2127       tree step = NULL_TREE;
2128       tree scev, init, val, var, setstmt;
2129       struct tree_map *h, in;
2130       void **loc;
2131
2132       /* Replace uses of X with Y right away.  */
2133       if (use == x)
2134         {
2135           SET_USE (use_p, y);
2136           continue;
2137         }
2138
2139       scev = instantiate_parameters (loop,
2140                                      analyze_scalar_evolution (loop, use));
2141
2142       if (scev == NULL || scev == chrec_dont_know)
2143         continue;
2144
2145       step = evolution_part_in_loop_num (scev, loop->num);
2146       if (step == NULL
2147           || step == chrec_dont_know
2148           || TREE_CODE (step) != INTEGER_CST
2149           || int_cst_value (step) != xstep)
2150         continue;
2151
2152       /* Use REPLACEMENTS hash table to cache already created
2153          temporaries.  */
2154       in.hash = htab_hash_pointer (use);
2155       in.base.from = use;
2156       h = htab_find_with_hash (replacements, &in, in.hash);
2157       if (h != NULL)
2158         {
2159           SET_USE (use_p, h->to);
2160           continue;
2161         }
2162
2163       /* USE which has the same step as X should be replaced
2164          with a temporary set to Y + YINIT - INIT.  */
2165       init = initial_condition_in_loop_num (scev, loop->num);
2166       gcc_assert (init != NULL && init != chrec_dont_know);
2167       if (TREE_TYPE (use) == TREE_TYPE (y))
2168         {
2169           val = fold_build2 (MINUS_EXPR, TREE_TYPE (y), init, yinit);
2170           val = fold_build2 (PLUS_EXPR, TREE_TYPE (y), y, val);
2171           if (val == y)
2172             {
2173               /* If X has the same type as USE, the same step
2174                  and same initial value, it can be replaced by Y.  */
2175               SET_USE (use_p, y);
2176               continue;
2177             }
2178         }
2179       else
2180         {
2181           val = fold_build2 (MINUS_EXPR, TREE_TYPE (y), y, yinit);
2182           val = fold_convert (TREE_TYPE (use), val);
2183           val = fold_build2 (PLUS_EXPR, TREE_TYPE (use), val, init);
2184         }
2185
2186       /* Create a temporary variable and insert it at the beginning
2187          of the loop body basic block, right after the PHI node
2188          which sets Y.  */
2189       var = create_tmp_var (TREE_TYPE (use), "perfecttmp");
2190       add_referenced_var (var);
2191       val = force_gimple_operand_bsi (firstbsi, val, false, NULL);
2192       setstmt = build_gimple_modify_stmt (var, val);
2193       var = make_ssa_name (var, setstmt);
2194       GIMPLE_STMT_OPERAND (setstmt, 0) = var;
2195       bsi_insert_before (firstbsi, setstmt, BSI_SAME_STMT);
2196       update_stmt (setstmt);
2197       SET_USE (use_p, var);
2198       h = ggc_alloc (sizeof (struct tree_map));
2199       h->hash = in.hash;
2200       h->base.from = use;
2201       h->to = var;
2202       loc = htab_find_slot_with_hash (replacements, h, in.hash, INSERT);
2203       gcc_assert ((*(struct tree_map **)loc) == NULL);
2204       *(struct tree_map **) loc = h;
2205     }
2206 }
2207
2208 /* Return true if STMT is an exit PHI for LOOP */
2209
2210 static bool
2211 exit_phi_for_loop_p (struct loop *loop, tree stmt)
2212 {
2213   
2214   if (TREE_CODE (stmt) != PHI_NODE
2215       || PHI_NUM_ARGS (stmt) != 1
2216       || bb_for_stmt (stmt) != single_exit (loop)->dest)
2217     return false;
2218   
2219   return true;
2220 }
2221
2222 /* Return true if STMT can be put back into the loop INNER, by
2223    copying it to the beginning of that loop and changing the uses.  */
2224
2225 static bool
2226 can_put_in_inner_loop (struct loop *inner, tree stmt)
2227 {
2228   imm_use_iterator imm_iter;
2229   use_operand_p use_p;
2230   
2231   gcc_assert (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
2232   if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)
2233       || !expr_invariant_in_loop_p (inner, GIMPLE_STMT_OPERAND (stmt, 1)))
2234     return false;
2235   
2236   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, GIMPLE_STMT_OPERAND (stmt, 0))
2237     {
2238       if (!exit_phi_for_loop_p (inner, USE_STMT (use_p)))
2239         {
2240           basic_block immbb = bb_for_stmt (USE_STMT (use_p));
2241
2242           if (!flow_bb_inside_loop_p (inner, immbb))
2243             return false;
2244         }
2245     }
2246   return true;  
2247 }
2248
2249 /* Return true if STMT can be put *after* the inner loop of LOOP.  */
2250 static bool
2251 can_put_after_inner_loop (struct loop *loop, tree stmt)
2252 {
2253   imm_use_iterator imm_iter;
2254   use_operand_p use_p;
2255
2256   if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
2257     return false;
2258   
2259   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, GIMPLE_STMT_OPERAND (stmt, 0))
2260     {
2261       if (!exit_phi_for_loop_p (loop, USE_STMT (use_p)))
2262         {
2263           basic_block immbb = bb_for_stmt (USE_STMT (use_p));
2264           
2265           if (!dominated_by_p (CDI_DOMINATORS,
2266                                immbb,
2267                                loop->inner->header)
2268               && !can_put_in_inner_loop (loop->inner, stmt))
2269             return false;
2270         }
2271     }
2272   return true;
2273 }
2274
2275
2276
2277 /* Return TRUE if LOOP is an imperfect nest that we can convert to a
2278    perfect one.  At the moment, we only handle imperfect nests of
2279    depth 2, where all of the statements occur after the inner loop.  */
2280
2281 static bool
2282 can_convert_to_perfect_nest (struct loop *loop)
2283 {
2284   basic_block *bbs;
2285   tree exit_condition, phi;
2286   size_t i;
2287   block_stmt_iterator bsi;
2288   basic_block exitdest;
2289
2290   /* Can't handle triply nested+ loops yet.  */
2291   if (!loop->inner || loop->inner->inner)
2292     return false;
2293   
2294   bbs = get_loop_body (loop);
2295   exit_condition = get_loop_exit_condition (loop);
2296   for (i = 0; i < loop->num_nodes; i++)
2297     {
2298       if (bbs[i]->loop_father == loop)
2299         {
2300           for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi))
2301             { 
2302               tree stmt = bsi_stmt (bsi);
2303
2304               if (stmt == exit_condition
2305                   || not_interesting_stmt (stmt)
2306                   || stmt_is_bumper_for_loop (loop, stmt))
2307                 continue;
2308
2309               /* If this is a scalar operation that can be put back
2310                  into the inner loop, or after the inner loop, through
2311                  copying, then do so. This works on the theory that
2312                  any amount of scalar code we have to reduplicate
2313                  into or after the loops is less expensive that the
2314                  win we get from rearranging the memory walk
2315                  the loop is doing so that it has better
2316                  cache behavior.  */
2317               if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
2318                 {
2319                   use_operand_p use_a, use_b;
2320                   imm_use_iterator imm_iter;
2321                   ssa_op_iter op_iter, op_iter1;
2322                   tree op0 = GIMPLE_STMT_OPERAND (stmt, 0);
2323                   tree scev = instantiate_parameters
2324                     (loop, analyze_scalar_evolution (loop, op0));
2325
2326                   /* If the IV is simple, it can be duplicated.  */
2327                   if (!automatically_generated_chrec_p (scev))
2328                     {
2329                       tree step = evolution_part_in_loop_num (scev, loop->num);
2330                       if (step && step != chrec_dont_know 
2331                           && TREE_CODE (step) == INTEGER_CST)
2332                         continue;
2333                     }
2334
2335                   /* The statement should not define a variable used
2336                      in the inner loop.  */
2337                   if (TREE_CODE (op0) == SSA_NAME)
2338                     FOR_EACH_IMM_USE_FAST (use_a, imm_iter, op0)
2339                       if (bb_for_stmt (USE_STMT (use_a))->loop_father
2340                           == loop->inner)
2341                         goto fail;
2342
2343                   FOR_EACH_SSA_USE_OPERAND (use_a, stmt, op_iter, SSA_OP_USE)
2344                     {
2345                       tree node, op = USE_FROM_PTR (use_a);
2346
2347                       /* The variables should not be used in both loops.  */
2348                       FOR_EACH_IMM_USE_FAST (use_b, imm_iter, op)
2349                       if (bb_for_stmt (USE_STMT (use_b))->loop_father
2350                           == loop->inner)
2351                         goto fail;
2352
2353                       /* The statement should not use the value of a
2354                          scalar that was modified in the loop.  */
2355                       node = SSA_NAME_DEF_STMT (op);
2356                       if (TREE_CODE (node) == PHI_NODE)
2357                         FOR_EACH_PHI_ARG (use_b, node, op_iter1, SSA_OP_USE)
2358                           {
2359                             tree arg = USE_FROM_PTR (use_b);
2360
2361                             if (TREE_CODE (arg) == SSA_NAME)
2362                               {
2363                                 tree arg_stmt = SSA_NAME_DEF_STMT (arg);
2364
2365                                 if (bb_for_stmt (arg_stmt)
2366                                     && (bb_for_stmt (arg_stmt)->loop_father
2367                                         == loop->inner))
2368                                   goto fail;
2369                               }
2370                           }
2371                     }
2372
2373                   if (can_put_in_inner_loop (loop->inner, stmt)
2374                       || can_put_after_inner_loop (loop, stmt))
2375                     continue;
2376                 }
2377
2378               /* Otherwise, if the bb of a statement we care about isn't
2379                  dominated by the header of the inner loop, then we can't
2380                  handle this case right now.  This test ensures that the
2381                  statement comes completely *after* the inner loop.  */
2382               if (!dominated_by_p (CDI_DOMINATORS,
2383                                    bb_for_stmt (stmt), 
2384                                    loop->inner->header))
2385                 goto fail;
2386             }
2387         }
2388     }
2389
2390   /* We also need to make sure the loop exit only has simple copy phis in it,
2391      otherwise we don't know how to transform it into a perfect nest right
2392      now.  */
2393   exitdest = single_exit (loop)->dest;
2394   
2395   for (phi = phi_nodes (exitdest); phi; phi = PHI_CHAIN (phi))
2396     if (PHI_NUM_ARGS (phi) != 1)
2397       goto fail;
2398   
2399   free (bbs);
2400   return true;
2401   
2402  fail:
2403   free (bbs);
2404   return false;
2405 }
2406
2407 /* Transform the loop nest into a perfect nest, if possible.
2408    LOOP is the loop nest to transform into a perfect nest
2409    LBOUNDS are the lower bounds for the loops to transform
2410    UBOUNDS are the upper bounds for the loops to transform
2411    STEPS is the STEPS for the loops to transform.
2412    LOOPIVS is the induction variables for the loops to transform.
2413    
2414    Basically, for the case of
2415
2416    FOR (i = 0; i < 50; i++)
2417     {
2418      FOR (j =0; j < 50; j++)
2419      {
2420         <whatever>
2421      }
2422      <some code>
2423     }
2424
2425    This function will transform it into a perfect loop nest by splitting the
2426    outer loop into two loops, like so:
2427
2428    FOR (i = 0; i < 50; i++)
2429    {
2430      FOR (j = 0; j < 50; j++)
2431      {
2432          <whatever>
2433      }
2434    }
2435    
2436    FOR (i = 0; i < 50; i ++)
2437    {
2438     <some code>
2439    }
2440
2441    Return FALSE if we can't make this loop into a perfect nest.  */
2442
2443 static bool
2444 perfect_nestify (struct loop *loop,
2445                  VEC(tree,heap) *lbounds,
2446                  VEC(tree,heap) *ubounds,
2447                  VEC(int,heap) *steps,
2448                  VEC(tree,heap) *loopivs)
2449 {
2450   basic_block *bbs;
2451   tree exit_condition;
2452   tree cond_stmt;
2453   basic_block preheaderbb, headerbb, bodybb, latchbb, olddest;
2454   int i;
2455   block_stmt_iterator bsi, firstbsi;
2456   bool insert_after;
2457   edge e;
2458   struct loop *newloop;
2459   tree phi;
2460   tree uboundvar;
2461   tree stmt;
2462   tree oldivvar, ivvar, ivvarinced;
2463   VEC(tree,heap) *phis = NULL;
2464   htab_t replacements = NULL;
2465
2466   /* Create the new loop.  */
2467   olddest = single_exit (loop)->dest;
2468   preheaderbb = split_edge (single_exit (loop));
2469   headerbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
2470   
2471   /* Push the exit phi nodes that we are moving.  */
2472   for (phi = phi_nodes (olddest); phi; phi = PHI_CHAIN (phi))
2473     {
2474       VEC_reserve (tree, heap, phis, 2);
2475       VEC_quick_push (tree, phis, PHI_RESULT (phi));
2476       VEC_quick_push (tree, phis, PHI_ARG_DEF (phi, 0));
2477     }
2478   e = redirect_edge_and_branch (single_succ_edge (preheaderbb), headerbb);
2479
2480   /* Remove the exit phis from the old basic block.  */
2481   while (phi_nodes (olddest) != NULL)
2482     remove_phi_node (phi_nodes (olddest), NULL, false);
2483
2484   /* and add them back to the new basic block.  */
2485   while (VEC_length (tree, phis) != 0)
2486     {
2487       tree def;
2488       tree phiname;
2489       def = VEC_pop (tree, phis);
2490       phiname = VEC_pop (tree, phis);      
2491       phi = create_phi_node (phiname, preheaderbb);
2492       add_phi_arg (phi, def, single_pred_edge (preheaderbb));
2493     }
2494   flush_pending_stmts (e);
2495   VEC_free (tree, heap, phis);
2496
2497   bodybb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
2498   latchbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
2499   make_edge (headerbb, bodybb, EDGE_FALLTHRU); 
2500   cond_stmt = build3 (COND_EXPR, void_type_node,
2501                       build2 (NE_EXPR, boolean_type_node, 
2502                               integer_one_node, 
2503                               integer_zero_node), 
2504                       NULL_TREE, NULL_TREE);
2505   bsi = bsi_start (bodybb);
2506   bsi_insert_after (&bsi, cond_stmt, BSI_NEW_STMT);
2507   e = make_edge (bodybb, olddest, EDGE_FALSE_VALUE);
2508   make_edge (bodybb, latchbb, EDGE_TRUE_VALUE);
2509   make_edge (latchbb, headerbb, EDGE_FALLTHRU);
2510
2511   /* Update the loop structures.  */
2512   newloop = duplicate_loop (loop, olddest->loop_father);  
2513   newloop->header = headerbb;
2514   newloop->latch = latchbb;
2515   add_bb_to_loop (latchbb, newloop);
2516   add_bb_to_loop (bodybb, newloop);
2517   add_bb_to_loop (headerbb, newloop);
2518   set_immediate_dominator (CDI_DOMINATORS, bodybb, headerbb);
2519   set_immediate_dominator (CDI_DOMINATORS, headerbb, preheaderbb);
2520   set_immediate_dominator (CDI_DOMINATORS, preheaderbb, 
2521                            single_exit (loop)->src);
2522   set_immediate_dominator (CDI_DOMINATORS, latchbb, bodybb);
2523   set_immediate_dominator (CDI_DOMINATORS, olddest,
2524                            recompute_dominator (CDI_DOMINATORS, olddest));
2525   /* Create the new iv.  */
2526   oldivvar = VEC_index (tree, loopivs, 0);
2527   ivvar = create_tmp_var (TREE_TYPE (oldivvar), "perfectiv");
2528   add_referenced_var (ivvar);
2529   standard_iv_increment_position (newloop, &bsi, &insert_after);
2530   create_iv (VEC_index (tree, lbounds, 0),
2531              build_int_cst (TREE_TYPE (oldivvar), VEC_index (int, steps, 0)),
2532              ivvar, newloop, &bsi, insert_after, &ivvar, &ivvarinced);       
2533
2534   /* Create the new upper bound.  This may be not just a variable, so we copy
2535      it to one just in case.  */
2536
2537   exit_condition = get_loop_exit_condition (newloop);
2538   uboundvar = create_tmp_var (integer_type_node, "uboundvar");
2539   add_referenced_var (uboundvar);
2540   stmt = build_gimple_modify_stmt (uboundvar, VEC_index (tree, ubounds, 0));
2541   uboundvar = make_ssa_name (uboundvar, stmt);
2542   GIMPLE_STMT_OPERAND (stmt, 0) = uboundvar;
2543
2544   if (insert_after)
2545     bsi_insert_after (&bsi, stmt, BSI_SAME_STMT);
2546   else
2547     bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
2548   update_stmt (stmt);
2549   COND_EXPR_COND (exit_condition) = build2 (GE_EXPR, 
2550                                             boolean_type_node,
2551                                             uboundvar,
2552                                             ivvarinced);
2553   update_stmt (exit_condition);
2554   replacements = htab_create_ggc (20, tree_map_hash,
2555                                   tree_map_eq, NULL);
2556   bbs = get_loop_body_in_dom_order (loop); 
2557   /* Now move the statements, and replace the induction variable in the moved
2558      statements with the correct loop induction variable.  */
2559   oldivvar = VEC_index (tree, loopivs, 0);
2560   firstbsi = bsi_start (bodybb);
2561   for (i = loop->num_nodes - 1; i >= 0 ; i--)
2562     {
2563       block_stmt_iterator tobsi = bsi_last (bodybb);
2564       if (bbs[i]->loop_father == loop)
2565         {
2566           /* If this is true, we are *before* the inner loop.
2567              If this isn't true, we are *after* it.
2568
2569              The only time can_convert_to_perfect_nest returns true when we
2570              have statements before the inner loop is if they can be moved
2571              into the inner loop. 
2572
2573              The only time can_convert_to_perfect_nest returns true when we
2574              have statements after the inner loop is if they can be moved into
2575              the new split loop.  */
2576
2577           if (dominated_by_p (CDI_DOMINATORS, loop->inner->header, bbs[i]))
2578             {
2579               block_stmt_iterator header_bsi 
2580                 = bsi_after_labels (loop->inner->header);
2581
2582               for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi);)
2583                 { 
2584                   tree stmt = bsi_stmt (bsi);
2585
2586                   if (stmt == exit_condition
2587                       || not_interesting_stmt (stmt)
2588                       || stmt_is_bumper_for_loop (loop, stmt))
2589                     {
2590                       bsi_next (&bsi);
2591                       continue;
2592                     }
2593
2594                   bsi_move_before (&bsi, &header_bsi);
2595                 }
2596             }
2597           else
2598             { 
2599               /* Note that the bsi only needs to be explicitly incremented
2600                  when we don't move something, since it is automatically
2601                  incremented when we do.  */
2602               for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi);)
2603                 { 
2604                   ssa_op_iter i;
2605                   tree n, stmt = bsi_stmt (bsi);
2606                   
2607                   if (stmt == exit_condition
2608                       || not_interesting_stmt (stmt)
2609                       || stmt_is_bumper_for_loop (loop, stmt))
2610                     {
2611                       bsi_next (&bsi);
2612                       continue;
2613                     }
2614                   
2615                   replace_uses_equiv_to_x_with_y 
2616                     (loop, stmt, oldivvar, VEC_index (int, steps, 0), ivvar,
2617                      VEC_index (tree, lbounds, 0), replacements, &firstbsi);
2618
2619                   bsi_move_before (&bsi, &tobsi);
2620                   
2621                   /* If the statement has any virtual operands, they may
2622                      need to be rewired because the original loop may
2623                      still reference them.  */
2624                   FOR_EACH_SSA_TREE_OPERAND (n, stmt, i, SSA_OP_ALL_VIRTUALS)
2625                     mark_sym_for_renaming (SSA_NAME_VAR (n));
2626                 }
2627             }
2628           
2629         }
2630     }
2631
2632   free (bbs);
2633   htab_delete (replacements);
2634   return perfect_nest_p (loop);
2635 }
2636
2637 /* Return true if TRANS is a legal transformation matrix that respects
2638    the dependence vectors in DISTS and DIRS.  The conservative answer
2639    is false.
2640
2641    "Wolfe proves that a unimodular transformation represented by the
2642    matrix T is legal when applied to a loop nest with a set of
2643    lexicographically non-negative distance vectors RDG if and only if
2644    for each vector d in RDG, (T.d >= 0) is lexicographically positive.
2645    i.e.: if and only if it transforms the lexicographically positive
2646    distance vectors to lexicographically positive vectors.  Note that
2647    a unimodular matrix must transform the zero vector (and only it) to
2648    the zero vector." S.Muchnick.  */
2649
2650 bool
2651 lambda_transform_legal_p (lambda_trans_matrix trans, 
2652                           int nb_loops,
2653                           VEC (ddr_p, heap) *dependence_relations)
2654 {
2655   unsigned int i, j;
2656   lambda_vector distres;
2657   struct data_dependence_relation *ddr;
2658
2659   gcc_assert (LTM_COLSIZE (trans) == nb_loops
2660               && LTM_ROWSIZE (trans) == nb_loops);
2661
2662   /* When there is an unknown relation in the dependence_relations, we
2663      know that it is no worth looking at this loop nest: give up.  */
2664   ddr = VEC_index (ddr_p, dependence_relations, 0);
2665   if (ddr == NULL)
2666     return true;
2667   if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
2668     return false;
2669
2670   distres = lambda_vector_new (nb_loops);
2671
2672   /* For each distance vector in the dependence graph.  */
2673   for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
2674     {
2675       /* Don't care about relations for which we know that there is no
2676          dependence, nor about read-read (aka. output-dependences):
2677          these data accesses can happen in any order.  */
2678       if (DDR_ARE_DEPENDENT (ddr) == chrec_known
2679           || (DR_IS_READ (DDR_A (ddr)) && DR_IS_READ (DDR_B (ddr))))
2680         continue;
2681
2682       /* Conservatively answer: "this transformation is not valid".  */
2683       if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
2684         return false;
2685           
2686       /* If the dependence could not be captured by a distance vector,
2687          conservatively answer that the transform is not valid.  */
2688       if (DDR_NUM_DIST_VECTS (ddr) == 0)
2689         return false;
2690
2691       /* Compute trans.dist_vect */
2692       for (j = 0; j < DDR_NUM_DIST_VECTS (ddr); j++)
2693         {
2694           lambda_matrix_vector_mult (LTM_MATRIX (trans), nb_loops, nb_loops, 
2695                                      DDR_DIST_VECT (ddr, j), distres);
2696
2697           if (!lambda_vector_lexico_pos (distres, nb_loops))
2698             return false;
2699         }
2700     }
2701   return true;
2702 }