1 /* Loop transformation code generation
2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dberlin@dberlin.org>
5 This file is part of GCC.
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
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
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, 59 Temple Place - Suite 330, Boston, MA
24 #include "coretypes.h"
31 #include "basic-block.h"
32 #include "diagnostic.h"
33 #include "tree-flow.h"
34 #include "tree-dump.h"
39 #include "tree-chrec.h"
40 #include "tree-data-ref.h"
41 #include "tree-pass.h"
42 #include "tree-scalar-evolution.h"
46 /* This loop nest code generation is based on non-singular matrix
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
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
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.
63 for i = 1 to 3, step 1 is a dense iteration space.
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.
68 for i = 1 to 3, step 2 is a sparse iteration space, because the integer point
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.
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
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).
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.
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
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.
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
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.
115 Fourier-Motzkin elimination is used to compute the bounds of the base space
121 static bool perfect_nestify (struct loops *,
122 struct loop *, VEC (tree) *,
123 VEC (tree) *, VEC (int) *, VEC (tree) *);
124 /* Lattice stuff that is internal to the code generation algorithm. */
128 /* Lattice base matrix. */
130 /* Lattice dimension. */
132 /* Origin vector for the coefficients. */
133 lambda_vector origin;
134 /* Origin matrix for the invariants. */
135 lambda_matrix origin_invariants;
136 /* Number of invariants. */
140 #define LATTICE_BASE(T) ((T)->base)
141 #define LATTICE_DIMENSION(T) ((T)->dimension)
142 #define LATTICE_ORIGIN(T) ((T)->origin)
143 #define LATTICE_ORIGIN_INVARIANTS(T) ((T)->origin_invariants)
144 #define LATTICE_INVARIANTS(T) ((T)->invariants)
146 static bool lle_equal (lambda_linear_expression, lambda_linear_expression,
148 static lambda_lattice lambda_lattice_new (int, int);
149 static lambda_lattice lambda_lattice_compute_base (lambda_loopnest);
151 static tree find_induction_var_from_exit_cond (struct loop *);
153 /* Create a new lambda body vector. */
156 lambda_body_vector_new (int size)
158 lambda_body_vector ret;
160 ret = ggc_alloc (sizeof (*ret));
161 LBV_COEFFICIENTS (ret) = lambda_vector_new (size);
162 LBV_SIZE (ret) = size;
163 LBV_DENOMINATOR (ret) = 1;
167 /* Compute the new coefficients for the vector based on the
168 *inverse* of the transformation matrix. */
171 lambda_body_vector_compute_new (lambda_trans_matrix transform,
172 lambda_body_vector vect)
174 lambda_body_vector temp;
177 /* Make sure the matrix is square. */
178 gcc_assert (LTM_ROWSIZE (transform) == LTM_COLSIZE (transform));
180 depth = LTM_ROWSIZE (transform);
182 temp = lambda_body_vector_new (depth);
183 LBV_DENOMINATOR (temp) =
184 LBV_DENOMINATOR (vect) * LTM_DENOMINATOR (transform);
185 lambda_vector_matrix_mult (LBV_COEFFICIENTS (vect), depth,
186 LTM_MATRIX (transform), depth,
187 LBV_COEFFICIENTS (temp));
188 LBV_SIZE (temp) = LBV_SIZE (vect);
192 /* Print out a lambda body vector. */
195 print_lambda_body_vector (FILE * outfile, lambda_body_vector body)
197 print_lambda_vector (outfile, LBV_COEFFICIENTS (body), LBV_SIZE (body));
200 /* Return TRUE if two linear expressions are equal. */
203 lle_equal (lambda_linear_expression lle1, lambda_linear_expression lle2,
204 int depth, int invariants)
208 if (lle1 == NULL || lle2 == NULL)
210 if (LLE_CONSTANT (lle1) != LLE_CONSTANT (lle2))
212 if (LLE_DENOMINATOR (lle1) != LLE_DENOMINATOR (lle2))
214 for (i = 0; i < depth; i++)
215 if (LLE_COEFFICIENTS (lle1)[i] != LLE_COEFFICIENTS (lle2)[i])
217 for (i = 0; i < invariants; i++)
218 if (LLE_INVARIANT_COEFFICIENTS (lle1)[i] !=
219 LLE_INVARIANT_COEFFICIENTS (lle2)[i])
224 /* Create a new linear expression with dimension DIM, and total number
225 of invariants INVARIANTS. */
227 lambda_linear_expression
228 lambda_linear_expression_new (int dim, int invariants)
230 lambda_linear_expression ret;
232 ret = ggc_alloc_cleared (sizeof (*ret));
234 LLE_COEFFICIENTS (ret) = lambda_vector_new (dim);
235 LLE_CONSTANT (ret) = 0;
236 LLE_INVARIANT_COEFFICIENTS (ret) = lambda_vector_new (invariants);
237 LLE_DENOMINATOR (ret) = 1;
238 LLE_NEXT (ret) = NULL;
243 /* Print out a linear expression EXPR, with SIZE coefficients, to OUTFILE.
244 The starting letter used for variable names is START. */
247 print_linear_expression (FILE * outfile, lambda_vector expr, int size,
252 for (i = 0; i < size; i++)
259 fprintf (outfile, "-");
262 else if (expr[i] > 0)
263 fprintf (outfile, " + ");
265 fprintf (outfile, " - ");
266 if (abs (expr[i]) == 1)
267 fprintf (outfile, "%c", start + i);
269 fprintf (outfile, "%d%c", abs (expr[i]), start + i);
274 /* Print out a lambda linear expression structure, EXPR, to OUTFILE. The
275 depth/number of coefficients is given by DEPTH, the number of invariants is
276 given by INVARIANTS, and the character to start variable names with is given
280 print_lambda_linear_expression (FILE * outfile,
281 lambda_linear_expression expr,
282 int depth, int invariants, char start)
284 fprintf (outfile, "\tLinear expression: ");
285 print_linear_expression (outfile, LLE_COEFFICIENTS (expr), depth, start);
286 fprintf (outfile, " constant: %d ", LLE_CONSTANT (expr));
287 fprintf (outfile, " invariants: ");
288 print_linear_expression (outfile, LLE_INVARIANT_COEFFICIENTS (expr),
290 fprintf (outfile, " denominator: %d\n", LLE_DENOMINATOR (expr));
293 /* Print a lambda loop structure LOOP to OUTFILE. The depth/number of
294 coefficients is given by DEPTH, the number of invariants is
295 given by INVARIANTS, and the character to start variable names with is given
299 print_lambda_loop (FILE * outfile, lambda_loop loop, int depth,
300 int invariants, char start)
303 lambda_linear_expression expr;
307 expr = LL_LINEAR_OFFSET (loop);
308 step = LL_STEP (loop);
309 fprintf (outfile, " step size = %d \n", step);
313 fprintf (outfile, " linear offset: \n");
314 print_lambda_linear_expression (outfile, expr, depth, invariants,
318 fprintf (outfile, " lower bound: \n");
319 for (expr = LL_LOWER_BOUND (loop); expr != NULL; expr = LLE_NEXT (expr))
320 print_lambda_linear_expression (outfile, expr, depth, invariants, start);
321 fprintf (outfile, " upper bound: \n");
322 for (expr = LL_UPPER_BOUND (loop); expr != NULL; expr = LLE_NEXT (expr))
323 print_lambda_linear_expression (outfile, expr, depth, invariants, start);
326 /* Create a new loop nest structure with DEPTH loops, and INVARIANTS as the
327 number of invariants. */
330 lambda_loopnest_new (int depth, int invariants)
333 ret = ggc_alloc (sizeof (*ret));
335 LN_LOOPS (ret) = ggc_alloc_cleared (depth * sizeof (lambda_loop));
336 LN_DEPTH (ret) = depth;
337 LN_INVARIANTS (ret) = invariants;
342 /* Print a lambda loopnest structure, NEST, to OUTFILE. The starting
343 character to use for loop names is given by START. */
346 print_lambda_loopnest (FILE * outfile, lambda_loopnest nest, char start)
349 for (i = 0; i < LN_DEPTH (nest); i++)
351 fprintf (outfile, "Loop %c\n", start + i);
352 print_lambda_loop (outfile, LN_LOOPS (nest)[i], LN_DEPTH (nest),
353 LN_INVARIANTS (nest), 'i');
354 fprintf (outfile, "\n");
358 /* Allocate a new lattice structure of DEPTH x DEPTH, with INVARIANTS number
361 static lambda_lattice
362 lambda_lattice_new (int depth, int invariants)
365 ret = ggc_alloc (sizeof (*ret));
366 LATTICE_BASE (ret) = lambda_matrix_new (depth, depth);
367 LATTICE_ORIGIN (ret) = lambda_vector_new (depth);
368 LATTICE_ORIGIN_INVARIANTS (ret) = lambda_matrix_new (depth, invariants);
369 LATTICE_DIMENSION (ret) = depth;
370 LATTICE_INVARIANTS (ret) = invariants;
374 /* Compute the lattice base for NEST. The lattice base is essentially a
375 non-singular transform from a dense base space to a sparse iteration space.
376 We use it so that we don't have to specially handle the case of a sparse
377 iteration space in other parts of the algorithm. As a result, this routine
378 only does something interesting (IE produce a matrix that isn't the
379 identity matrix) if NEST is a sparse space. */
381 static lambda_lattice
382 lambda_lattice_compute_base (lambda_loopnest nest)
385 int depth, invariants;
390 lambda_linear_expression expression;
392 depth = LN_DEPTH (nest);
393 invariants = LN_INVARIANTS (nest);
395 ret = lambda_lattice_new (depth, invariants);
396 base = LATTICE_BASE (ret);
397 for (i = 0; i < depth; i++)
399 loop = LN_LOOPS (nest)[i];
401 step = LL_STEP (loop);
402 /* If we have a step of 1, then the base is one, and the
403 origin and invariant coefficients are 0. */
406 for (j = 0; j < depth; j++)
409 LATTICE_ORIGIN (ret)[i] = 0;
410 for (j = 0; j < invariants; j++)
411 LATTICE_ORIGIN_INVARIANTS (ret)[i][j] = 0;
415 /* Otherwise, we need the lower bound expression (which must
416 be an affine function) to determine the base. */
417 expression = LL_LOWER_BOUND (loop);
418 gcc_assert (expression && !LLE_NEXT (expression)
419 && LLE_DENOMINATOR (expression) == 1);
421 /* The lower triangular portion of the base is going to be the
422 coefficient times the step */
423 for (j = 0; j < i; j++)
424 base[i][j] = LLE_COEFFICIENTS (expression)[j]
425 * LL_STEP (LN_LOOPS (nest)[j]);
427 for (j = i + 1; j < depth; j++)
430 /* Origin for this loop is the constant of the lower bound
432 LATTICE_ORIGIN (ret)[i] = LLE_CONSTANT (expression);
434 /* Coefficient for the invariants are equal to the invariant
435 coefficients in the expression. */
436 for (j = 0; j < invariants; j++)
437 LATTICE_ORIGIN_INVARIANTS (ret)[i][j] =
438 LLE_INVARIANT_COEFFICIENTS (expression)[j];
444 /* Compute the greatest common denominator of two numbers (A and B) using
445 Euclid's algorithm. */
466 /* Compute the greatest common denominator of a VECTOR of SIZE numbers. */
469 gcd_vector (lambda_vector vector, int size)
477 for (i = 1; i < size; i++)
478 gcd1 = gcd (gcd1, vector[i]);
483 /* Compute the least common multiple of two numbers A and B . */
488 return (abs (a) * abs (b) / gcd (a, b));
491 /* Perform Fourier-Motzkin elimination to calculate the bounds of the
493 Fourier-Motzkin is a way of reducing systems of linear inequalities so that
494 it is easy to calculate the answer and bounds.
495 A sketch of how it works:
496 Given a system of linear inequalities, ai * xj >= bk, you can always
497 rewrite the constraints so they are all of the form
498 a <= x, or x <= b, or x >= constant for some x in x1 ... xj (and some b
499 in b1 ... bk, and some a in a1...ai)
500 You can then eliminate this x from the non-constant inequalities by
501 rewriting these as a <= b, x >= constant, and delete the x variable.
502 You can then repeat this for any remaining x variables, and then we have
503 an easy to use variable <= constant (or no variables at all) form that we
504 can construct our bounds from.
506 In our case, each time we eliminate, we construct part of the bound from
507 the ith variable, then delete the ith variable.
509 Remember the constant are in our vector a, our coefficient matrix is A,
510 and our invariant coefficient matrix is B.
512 SIZE is the size of the matrices being passed.
513 DEPTH is the loop nest depth.
514 INVARIANTS is the number of loop invariants.
515 A, B, and a are the coefficient matrix, invariant coefficient, and a
516 vector of constants, respectively. */
518 static lambda_loopnest
519 compute_nest_using_fourier_motzkin (int size,
527 int multiple, f1, f2;
529 lambda_linear_expression expression;
531 lambda_loopnest auxillary_nest;
532 lambda_matrix swapmatrix, A1, B1;
533 lambda_vector swapvector, a1;
536 A1 = lambda_matrix_new (128, depth);
537 B1 = lambda_matrix_new (128, invariants);
538 a1 = lambda_vector_new (128);
540 auxillary_nest = lambda_loopnest_new (depth, invariants);
542 for (i = depth - 1; i >= 0; i--)
544 loop = lambda_loop_new ();
545 LN_LOOPS (auxillary_nest)[i] = loop;
548 for (j = 0; j < size; j++)
552 /* Any linear expression in the matrix with a coefficient less
553 than 0 becomes part of the new lower bound. */
554 expression = lambda_linear_expression_new (depth, invariants);
556 for (k = 0; k < i; k++)
557 LLE_COEFFICIENTS (expression)[k] = A[j][k];
559 for (k = 0; k < invariants; k++)
560 LLE_INVARIANT_COEFFICIENTS (expression)[k] = -1 * B[j][k];
562 LLE_DENOMINATOR (expression) = -1 * A[j][i];
563 LLE_CONSTANT (expression) = -1 * a[j];
565 /* Ignore if identical to the existing lower bound. */
566 if (!lle_equal (LL_LOWER_BOUND (loop),
567 expression, depth, invariants))
569 LLE_NEXT (expression) = LL_LOWER_BOUND (loop);
570 LL_LOWER_BOUND (loop) = expression;
574 else if (A[j][i] > 0)
576 /* Any linear expression with a coefficient greater than 0
577 becomes part of the new upper bound. */
578 expression = lambda_linear_expression_new (depth, invariants);
579 for (k = 0; k < i; k++)
580 LLE_COEFFICIENTS (expression)[k] = -1 * A[j][k];
582 for (k = 0; k < invariants; k++)
583 LLE_INVARIANT_COEFFICIENTS (expression)[k] = B[j][k];
585 LLE_DENOMINATOR (expression) = A[j][i];
586 LLE_CONSTANT (expression) = a[j];
588 /* Ignore if identical to the existing upper bound. */
589 if (!lle_equal (LL_UPPER_BOUND (loop),
590 expression, depth, invariants))
592 LLE_NEXT (expression) = LL_UPPER_BOUND (loop);
593 LL_UPPER_BOUND (loop) = expression;
599 /* This portion creates a new system of linear inequalities by deleting
600 the i'th variable, reducing the system by one variable. */
602 for (j = 0; j < size; j++)
604 /* If the coefficient for the i'th variable is 0, then we can just
605 eliminate the variable straightaway. Otherwise, we have to
606 multiply through by the coefficients we are eliminating. */
609 lambda_vector_copy (A[j], A1[newsize], depth);
610 lambda_vector_copy (B[j], B1[newsize], invariants);
614 else if (A[j][i] > 0)
616 for (k = 0; k < size; k++)
620 multiple = lcm (A[j][i], A[k][i]);
621 f1 = multiple / A[j][i];
622 f2 = -1 * multiple / A[k][i];
624 lambda_vector_add_mc (A[j], f1, A[k], f2,
626 lambda_vector_add_mc (B[j], f1, B[k], f2,
627 B1[newsize], invariants);
628 a1[newsize] = f1 * a[j] + f2 * a[k];
650 return auxillary_nest;
653 /* Compute the loop bounds for the auxiliary space NEST.
654 Input system used is Ax <= b. TRANS is the unimodular transformation.
655 Given the original nest, this function will
656 1. Convert the nest into matrix form, which consists of a matrix for the
657 coefficients, a matrix for the
658 invariant coefficients, and a vector for the constants.
659 2. Use the matrix form to calculate the lattice base for the nest (which is
661 3. Compose the dense space transform with the user specified transform, to
662 get a transform we can easily calculate transformed bounds for.
663 4. Multiply the composed transformation matrix times the matrix form of the
665 5. Transform the newly created matrix (from step 4) back into a loop nest
666 using fourier motzkin elimination to figure out the bounds. */
668 static lambda_loopnest
669 lambda_compute_auxillary_space (lambda_loopnest nest,
670 lambda_trans_matrix trans)
672 lambda_matrix A, B, A1, B1;
674 lambda_matrix invertedtrans;
675 int depth, invariants, size;
678 lambda_linear_expression expression;
679 lambda_lattice lattice;
681 depth = LN_DEPTH (nest);
682 invariants = LN_INVARIANTS (nest);
684 /* Unfortunately, we can't know the number of constraints we'll have
685 ahead of time, but this should be enough even in ridiculous loop nest
686 cases. We abort if we go over this limit. */
687 A = lambda_matrix_new (128, depth);
688 B = lambda_matrix_new (128, invariants);
689 a = lambda_vector_new (128);
691 A1 = lambda_matrix_new (128, depth);
692 B1 = lambda_matrix_new (128, invariants);
693 a1 = lambda_vector_new (128);
695 /* Store the bounds in the equation matrix A, constant vector a, and
696 invariant matrix B, so that we have Ax <= a + B.
697 This requires a little equation rearranging so that everything is on the
698 correct side of the inequality. */
700 for (i = 0; i < depth; i++)
702 loop = LN_LOOPS (nest)[i];
704 /* First we do the lower bound. */
705 if (LL_STEP (loop) > 0)
706 expression = LL_LOWER_BOUND (loop);
708 expression = LL_UPPER_BOUND (loop);
710 for (; expression != NULL; expression = LLE_NEXT (expression))
712 /* Fill in the coefficient. */
713 for (j = 0; j < i; j++)
714 A[size][j] = LLE_COEFFICIENTS (expression)[j];
716 /* And the invariant coefficient. */
717 for (j = 0; j < invariants; j++)
718 B[size][j] = LLE_INVARIANT_COEFFICIENTS (expression)[j];
720 /* And the constant. */
721 a[size] = LLE_CONSTANT (expression);
723 /* Convert (2x+3y+2+b)/4 <= z to 2x+3y-4z <= -2-b. IE put all
724 constants and single variables on */
725 A[size][i] = -1 * LLE_DENOMINATOR (expression);
727 for (j = 0; j < invariants; j++)
731 /* Need to increase matrix sizes above. */
732 gcc_assert (size <= 127);
736 /* Then do the exact same thing for the upper bounds. */
737 if (LL_STEP (loop) > 0)
738 expression = LL_UPPER_BOUND (loop);
740 expression = LL_LOWER_BOUND (loop);
742 for (; expression != NULL; expression = LLE_NEXT (expression))
744 /* Fill in the coefficient. */
745 for (j = 0; j < i; j++)
746 A[size][j] = LLE_COEFFICIENTS (expression)[j];
748 /* And the invariant coefficient. */
749 for (j = 0; j < invariants; j++)
750 B[size][j] = LLE_INVARIANT_COEFFICIENTS (expression)[j];
752 /* And the constant. */
753 a[size] = LLE_CONSTANT (expression);
755 /* Convert z <= (2x+3y+2+b)/4 to -2x-3y+4z <= 2+b. */
756 for (j = 0; j < i; j++)
758 A[size][i] = LLE_DENOMINATOR (expression);
760 /* Need to increase matrix sizes above. */
761 gcc_assert (size <= 127);
766 /* Compute the lattice base x = base * y + origin, where y is the
768 lattice = lambda_lattice_compute_base (nest);
770 /* Ax <= a + B then becomes ALy <= a+B - A*origin. L is the lattice base */
773 lambda_matrix_mult (A, LATTICE_BASE (lattice), A1, size, depth, depth);
775 /* a1 = a - A * origin constant. */
776 lambda_matrix_vector_mult (A, size, depth, LATTICE_ORIGIN (lattice), a1);
777 lambda_vector_add_mc (a, 1, a1, -1, a1, size);
779 /* B1 = B - A * origin invariant. */
780 lambda_matrix_mult (A, LATTICE_ORIGIN_INVARIANTS (lattice), B1, size, depth,
782 lambda_matrix_add_mc (B, 1, B1, -1, B1, size, invariants);
784 /* Now compute the auxiliary space bounds by first inverting U, multiplying
785 it by A1, then performing fourier motzkin. */
787 invertedtrans = lambda_matrix_new (depth, depth);
789 /* Compute the inverse of U. */
790 lambda_matrix_inverse (LTM_MATRIX (trans),
791 invertedtrans, depth);
794 lambda_matrix_mult (A1, invertedtrans, A, size, depth, depth);
796 return compute_nest_using_fourier_motzkin (size, depth, invariants,
800 /* Compute the loop bounds for the target space, using the bounds of
801 the auxiliary nest AUXILLARY_NEST, and the triangular matrix H.
802 The target space loop bounds are computed by multiplying the triangular
803 matrix H by the auxiliary nest, to get the new loop bounds. The sign of
804 the loop steps (positive or negative) is then used to swap the bounds if
805 the loop counts downwards.
806 Return the target loopnest. */
808 static lambda_loopnest
809 lambda_compute_target_space (lambda_loopnest auxillary_nest,
810 lambda_trans_matrix H, lambda_vector stepsigns)
812 lambda_matrix inverse, H1;
813 int determinant, i, j;
817 lambda_loopnest target_nest;
818 int depth, invariants;
819 lambda_matrix target;
821 lambda_loop auxillary_loop, target_loop;
822 lambda_linear_expression expression, auxillary_expr, target_expr, tmp_expr;
824 depth = LN_DEPTH (auxillary_nest);
825 invariants = LN_INVARIANTS (auxillary_nest);
827 inverse = lambda_matrix_new (depth, depth);
828 determinant = lambda_matrix_inverse (LTM_MATRIX (H), inverse, depth);
830 /* H1 is H excluding its diagonal. */
831 H1 = lambda_matrix_new (depth, depth);
832 lambda_matrix_copy (LTM_MATRIX (H), H1, depth, depth);
834 for (i = 0; i < depth; i++)
837 /* Computes the linear offsets of the loop bounds. */
838 target = lambda_matrix_new (depth, depth);
839 lambda_matrix_mult (H1, inverse, target, depth, depth, depth);
841 target_nest = lambda_loopnest_new (depth, invariants);
843 for (i = 0; i < depth; i++)
846 /* Get a new loop structure. */
847 target_loop = lambda_loop_new ();
848 LN_LOOPS (target_nest)[i] = target_loop;
850 /* Computes the gcd of the coefficients of the linear part. */
851 gcd1 = gcd_vector (target[i], i);
853 /* Include the denominator in the GCD. */
854 gcd1 = gcd (gcd1, determinant);
856 /* Now divide through by the gcd. */
857 for (j = 0; j < i; j++)
858 target[i][j] = target[i][j] / gcd1;
860 expression = lambda_linear_expression_new (depth, invariants);
861 lambda_vector_copy (target[i], LLE_COEFFICIENTS (expression), depth);
862 LLE_DENOMINATOR (expression) = determinant / gcd1;
863 LLE_CONSTANT (expression) = 0;
864 lambda_vector_clear (LLE_INVARIANT_COEFFICIENTS (expression),
866 LL_LINEAR_OFFSET (target_loop) = expression;
869 /* For each loop, compute the new bounds from H. */
870 for (i = 0; i < depth; i++)
872 auxillary_loop = LN_LOOPS (auxillary_nest)[i];
873 target_loop = LN_LOOPS (target_nest)[i];
874 LL_STEP (target_loop) = LTM_MATRIX (H)[i][i];
875 factor = LTM_MATRIX (H)[i][i];
877 /* First we do the lower bound. */
878 auxillary_expr = LL_LOWER_BOUND (auxillary_loop);
880 for (; auxillary_expr != NULL;
881 auxillary_expr = LLE_NEXT (auxillary_expr))
883 target_expr = lambda_linear_expression_new (depth, invariants);
884 lambda_vector_matrix_mult (LLE_COEFFICIENTS (auxillary_expr),
885 depth, inverse, depth,
886 LLE_COEFFICIENTS (target_expr));
887 lambda_vector_mult_const (LLE_COEFFICIENTS (target_expr),
888 LLE_COEFFICIENTS (target_expr), depth,
891 LLE_CONSTANT (target_expr) = LLE_CONSTANT (auxillary_expr) * factor;
892 lambda_vector_copy (LLE_INVARIANT_COEFFICIENTS (auxillary_expr),
893 LLE_INVARIANT_COEFFICIENTS (target_expr),
895 lambda_vector_mult_const (LLE_INVARIANT_COEFFICIENTS (target_expr),
896 LLE_INVARIANT_COEFFICIENTS (target_expr),
898 LLE_DENOMINATOR (target_expr) = LLE_DENOMINATOR (auxillary_expr);
900 if (!lambda_vector_zerop (LLE_COEFFICIENTS (target_expr), depth))
902 LLE_CONSTANT (target_expr) = LLE_CONSTANT (target_expr)
904 lambda_vector_mult_const (LLE_INVARIANT_COEFFICIENTS
906 LLE_INVARIANT_COEFFICIENTS
907 (target_expr), invariants,
909 LLE_DENOMINATOR (target_expr) =
910 LLE_DENOMINATOR (target_expr) * determinant;
912 /* Find the gcd and divide by it here, rather than doing it
913 at the tree level. */
914 gcd1 = gcd_vector (LLE_COEFFICIENTS (target_expr), depth);
915 gcd2 = gcd_vector (LLE_INVARIANT_COEFFICIENTS (target_expr),
917 gcd1 = gcd (gcd1, gcd2);
918 gcd1 = gcd (gcd1, LLE_CONSTANT (target_expr));
919 gcd1 = gcd (gcd1, LLE_DENOMINATOR (target_expr));
920 for (j = 0; j < depth; j++)
921 LLE_COEFFICIENTS (target_expr)[j] /= gcd1;
922 for (j = 0; j < invariants; j++)
923 LLE_INVARIANT_COEFFICIENTS (target_expr)[j] /= gcd1;
924 LLE_CONSTANT (target_expr) /= gcd1;
925 LLE_DENOMINATOR (target_expr) /= gcd1;
926 /* Ignore if identical to existing bound. */
927 if (!lle_equal (LL_LOWER_BOUND (target_loop), target_expr, depth,
930 LLE_NEXT (target_expr) = LL_LOWER_BOUND (target_loop);
931 LL_LOWER_BOUND (target_loop) = target_expr;
934 /* Now do the upper bound. */
935 auxillary_expr = LL_UPPER_BOUND (auxillary_loop);
937 for (; auxillary_expr != NULL;
938 auxillary_expr = LLE_NEXT (auxillary_expr))
940 target_expr = lambda_linear_expression_new (depth, invariants);
941 lambda_vector_matrix_mult (LLE_COEFFICIENTS (auxillary_expr),
942 depth, inverse, depth,
943 LLE_COEFFICIENTS (target_expr));
944 lambda_vector_mult_const (LLE_COEFFICIENTS (target_expr),
945 LLE_COEFFICIENTS (target_expr), depth,
947 LLE_CONSTANT (target_expr) = LLE_CONSTANT (auxillary_expr) * factor;
948 lambda_vector_copy (LLE_INVARIANT_COEFFICIENTS (auxillary_expr),
949 LLE_INVARIANT_COEFFICIENTS (target_expr),
951 lambda_vector_mult_const (LLE_INVARIANT_COEFFICIENTS (target_expr),
952 LLE_INVARIANT_COEFFICIENTS (target_expr),
954 LLE_DENOMINATOR (target_expr) = LLE_DENOMINATOR (auxillary_expr);
956 if (!lambda_vector_zerop (LLE_COEFFICIENTS (target_expr), depth))
958 LLE_CONSTANT (target_expr) = LLE_CONSTANT (target_expr)
960 lambda_vector_mult_const (LLE_INVARIANT_COEFFICIENTS
962 LLE_INVARIANT_COEFFICIENTS
963 (target_expr), invariants,
965 LLE_DENOMINATOR (target_expr) =
966 LLE_DENOMINATOR (target_expr) * determinant;
968 /* Find the gcd and divide by it here, instead of at the
970 gcd1 = gcd_vector (LLE_COEFFICIENTS (target_expr), depth);
971 gcd2 = gcd_vector (LLE_INVARIANT_COEFFICIENTS (target_expr),
973 gcd1 = gcd (gcd1, gcd2);
974 gcd1 = gcd (gcd1, LLE_CONSTANT (target_expr));
975 gcd1 = gcd (gcd1, LLE_DENOMINATOR (target_expr));
976 for (j = 0; j < depth; j++)
977 LLE_COEFFICIENTS (target_expr)[j] /= gcd1;
978 for (j = 0; j < invariants; j++)
979 LLE_INVARIANT_COEFFICIENTS (target_expr)[j] /= gcd1;
980 LLE_CONSTANT (target_expr) /= gcd1;
981 LLE_DENOMINATOR (target_expr) /= gcd1;
982 /* Ignore if equal to existing bound. */
983 if (!lle_equal (LL_UPPER_BOUND (target_loop), target_expr, depth,
986 LLE_NEXT (target_expr) = LL_UPPER_BOUND (target_loop);
987 LL_UPPER_BOUND (target_loop) = target_expr;
991 for (i = 0; i < depth; i++)
993 target_loop = LN_LOOPS (target_nest)[i];
994 /* If necessary, exchange the upper and lower bounds and negate
996 if (stepsigns[i] < 0)
998 LL_STEP (target_loop) *= -1;
999 tmp_expr = LL_LOWER_BOUND (target_loop);
1000 LL_LOWER_BOUND (target_loop) = LL_UPPER_BOUND (target_loop);
1001 LL_UPPER_BOUND (target_loop) = tmp_expr;
1007 /* Compute the step signs of TRANS, using TRANS and stepsigns. Return the new
1010 static lambda_vector
1011 lambda_compute_step_signs (lambda_trans_matrix trans, lambda_vector stepsigns)
1013 lambda_matrix matrix, H;
1015 lambda_vector newsteps;
1016 int i, j, factor, minimum_column;
1019 matrix = LTM_MATRIX (trans);
1020 size = LTM_ROWSIZE (trans);
1021 H = lambda_matrix_new (size, size);
1023 newsteps = lambda_vector_new (size);
1024 lambda_vector_copy (stepsigns, newsteps, size);
1026 lambda_matrix_copy (matrix, H, size, size);
1028 for (j = 0; j < size; j++)
1032 for (i = j; i < size; i++)
1034 lambda_matrix_col_negate (H, size, i);
1035 while (lambda_vector_first_nz (row, size, j + 1) < size)
1037 minimum_column = lambda_vector_min_nz (row, size, j);
1038 lambda_matrix_col_exchange (H, size, j, minimum_column);
1041 newsteps[j] = newsteps[minimum_column];
1042 newsteps[minimum_column] = temp;
1044 for (i = j + 1; i < size; i++)
1046 factor = row[i] / row[j];
1047 lambda_matrix_col_add (H, size, j, i, -1 * factor);
1054 /* Transform NEST according to TRANS, and return the new loopnest.
1056 1. Computing a lattice base for the transformation
1057 2. Composing the dense base with the specified transformation (TRANS)
1058 3. Decomposing the combined transformation into a lower triangular portion,
1059 and a unimodular portion.
1060 4. Computing the auxiliary nest using the unimodular portion.
1061 5. Computing the target nest using the auxiliary nest and the lower
1062 triangular portion. */
1065 lambda_loopnest_transform (lambda_loopnest nest, lambda_trans_matrix trans)
1067 lambda_loopnest auxillary_nest, target_nest;
1069 int depth, invariants;
1071 lambda_lattice lattice;
1072 lambda_trans_matrix trans1, H, U;
1074 lambda_linear_expression expression;
1075 lambda_vector origin;
1076 lambda_matrix origin_invariants;
1077 lambda_vector stepsigns;
1080 depth = LN_DEPTH (nest);
1081 invariants = LN_INVARIANTS (nest);
1083 /* Keep track of the signs of the loop steps. */
1084 stepsigns = lambda_vector_new (depth);
1085 for (i = 0; i < depth; i++)
1087 if (LL_STEP (LN_LOOPS (nest)[i]) > 0)
1093 /* Compute the lattice base. */
1094 lattice = lambda_lattice_compute_base (nest);
1095 trans1 = lambda_trans_matrix_new (depth, depth);
1097 /* Multiply the transformation matrix by the lattice base. */
1099 lambda_matrix_mult (LTM_MATRIX (trans), LATTICE_BASE (lattice),
1100 LTM_MATRIX (trans1), depth, depth, depth);
1102 /* Compute the Hermite normal form for the new transformation matrix. */
1103 H = lambda_trans_matrix_new (depth, depth);
1104 U = lambda_trans_matrix_new (depth, depth);
1105 lambda_matrix_hermite (LTM_MATRIX (trans1), depth, LTM_MATRIX (H),
1108 /* Compute the auxiliary loop nest's space from the unimodular
1110 auxillary_nest = lambda_compute_auxillary_space (nest, U);
1112 /* Compute the loop step signs from the old step signs and the
1113 transformation matrix. */
1114 stepsigns = lambda_compute_step_signs (trans1, stepsigns);
1116 /* Compute the target loop nest space from the auxiliary nest and
1117 the lower triangular matrix H. */
1118 target_nest = lambda_compute_target_space (auxillary_nest, H, stepsigns);
1119 origin = lambda_vector_new (depth);
1120 origin_invariants = lambda_matrix_new (depth, invariants);
1121 lambda_matrix_vector_mult (LTM_MATRIX (trans), depth, depth,
1122 LATTICE_ORIGIN (lattice), origin);
1123 lambda_matrix_mult (LTM_MATRIX (trans), LATTICE_ORIGIN_INVARIANTS (lattice),
1124 origin_invariants, depth, depth, invariants);
1126 for (i = 0; i < depth; i++)
1128 loop = LN_LOOPS (target_nest)[i];
1129 expression = LL_LINEAR_OFFSET (loop);
1130 if (lambda_vector_zerop (LLE_COEFFICIENTS (expression), depth))
1133 f = LLE_DENOMINATOR (expression);
1135 LLE_CONSTANT (expression) += f * origin[i];
1137 for (j = 0; j < invariants; j++)
1138 LLE_INVARIANT_COEFFICIENTS (expression)[j] +=
1139 f * origin_invariants[i][j];
1146 /* Convert a gcc tree expression EXPR to a lambda linear expression, and
1147 return the new expression. DEPTH is the depth of the loopnest.
1148 OUTERINDUCTIONVARS is an array of the induction variables for outer loops
1149 in this nest. INVARIANTS is the array of invariants for the loop. EXTRA
1150 is the amount we have to add/subtract from the expression because of the
1151 type of comparison it is used in. */
1153 static lambda_linear_expression
1154 gcc_tree_to_linear_expression (int depth, tree expr,
1155 VEC(tree) *outerinductionvars,
1156 VEC(tree) *invariants, int extra)
1158 lambda_linear_expression lle = NULL;
1159 switch (TREE_CODE (expr))
1163 lle = lambda_linear_expression_new (depth, 2 * depth);
1164 LLE_CONSTANT (lle) = TREE_INT_CST_LOW (expr);
1166 LLE_CONSTANT (lle) += extra;
1168 LLE_DENOMINATOR (lle) = 1;
1175 for (i = 0; VEC_iterate (tree, outerinductionvars, i, iv); i++)
1178 if (SSA_NAME_VAR (iv) == SSA_NAME_VAR (expr))
1180 lle = lambda_linear_expression_new (depth, 2 * depth);
1181 LLE_COEFFICIENTS (lle)[i] = 1;
1183 LLE_CONSTANT (lle) = extra;
1185 LLE_DENOMINATOR (lle) = 1;
1188 for (i = 0; VEC_iterate (tree, invariants, i, invar); i++)
1191 if (SSA_NAME_VAR (invar) == SSA_NAME_VAR (expr))
1193 lle = lambda_linear_expression_new (depth, 2 * depth);
1194 LLE_INVARIANT_COEFFICIENTS (lle)[i] = 1;
1196 LLE_CONSTANT (lle) = extra;
1197 LLE_DENOMINATOR (lle) = 1;
1209 /* Return the depth of the loopnest NEST */
1212 depth_of_nest (struct loop *nest)
1224 /* Return true if OP is invariant in LOOP and all outer loops. */
1227 invariant_in_loop_and_outer_loops (struct loop *loop, tree op)
1229 if (is_gimple_min_invariant (op))
1231 if (loop->depth == 0)
1233 if (!expr_invariant_in_loop_p (loop, op))
1236 && !invariant_in_loop_and_outer_loops (loop->outer, op))
1241 /* Generate a lambda loop from a gcc loop LOOP. Return the new lambda loop,
1242 or NULL if it could not be converted.
1243 DEPTH is the depth of the loop.
1244 INVARIANTS is a pointer to the array of loop invariants.
1245 The induction variable for this loop should be stored in the parameter
1247 OUTERINDUCTIONVARS is an array of induction variables for outer loops. */
1250 gcc_loop_to_lambda_loop (struct loop *loop, int depth,
1251 VEC (tree) ** invariants,
1252 tree * ourinductionvar,
1253 VEC (tree) * outerinductionvars,
1254 VEC (tree) ** lboundvars,
1255 VEC (tree) ** uboundvars,
1260 tree access_fn, inductionvar;
1262 lambda_loop lloop = NULL;
1263 lambda_linear_expression lbound, ubound;
1267 tree lboundvar, uboundvar, uboundresult;
1270 /* Find out induction var and exit condition. */
1271 inductionvar = find_induction_var_from_exit_cond (loop);
1272 exit_cond = get_loop_exit_condition (loop);
1274 if (inductionvar == NULL || exit_cond == NULL)
1276 if (dump_file && (dump_flags & TDF_DETAILS))
1278 "Unable to convert loop: Cannot determine exit condition or induction variable for loop.\n");
1282 test = TREE_OPERAND (exit_cond, 0);
1284 if (SSA_NAME_DEF_STMT (inductionvar) == NULL_TREE)
1287 if (dump_file && (dump_flags & TDF_DETAILS))
1289 "Unable to convert loop: Cannot find PHI node for induction variable\n");
1294 phi = SSA_NAME_DEF_STMT (inductionvar);
1295 if (TREE_CODE (phi) != PHI_NODE)
1297 uses = STMT_USE_OPS (phi);
1302 if (dump_file && (dump_flags & TDF_DETAILS))
1304 "Unable to convert loop: Cannot find PHI node for induction variable\n");
1309 phi = USE_OP (uses, 0);
1310 phi = SSA_NAME_DEF_STMT (phi);
1311 if (TREE_CODE (phi) != PHI_NODE)
1314 if (dump_file && (dump_flags & TDF_DETAILS))
1316 "Unable to convert loop: Cannot find PHI node for induction variable\n");
1322 /* The induction variable name/version we want to put in the array is the
1323 result of the induction variable phi node. */
1324 *ourinductionvar = PHI_RESULT (phi);
1325 access_fn = instantiate_parameters
1326 (loop, analyze_scalar_evolution (loop, PHI_RESULT (phi)));
1327 if (access_fn == chrec_dont_know)
1329 if (dump_file && (dump_flags & TDF_DETAILS))
1331 "Unable to convert loop: Access function for induction variable phi is unknown\n");
1336 step = evolution_part_in_loop_num (access_fn, loop->num);
1337 if (!step || step == chrec_dont_know)
1339 if (dump_file && (dump_flags & TDF_DETAILS))
1341 "Unable to convert loop: Cannot determine step of loop.\n");
1345 if (TREE_CODE (step) != INTEGER_CST)
1348 if (dump_file && (dump_flags & TDF_DETAILS))
1350 "Unable to convert loop: Step of loop is not integer.\n");
1354 stepint = TREE_INT_CST_LOW (step);
1356 /* Only want phis for induction vars, which will have two
1358 if (PHI_NUM_ARGS (phi) != 2)
1360 if (dump_file && (dump_flags & TDF_DETAILS))
1362 "Unable to convert loop: PHI node for induction variable has >2 arguments\n");
1366 /* Another induction variable check. One argument's source should be
1367 in the loop, one outside the loop. */
1368 if (flow_bb_inside_loop_p (loop, PHI_ARG_EDGE (phi, 0)->src)
1369 && flow_bb_inside_loop_p (loop, PHI_ARG_EDGE (phi, 1)->src))
1372 if (dump_file && (dump_flags & TDF_DETAILS))
1374 "Unable to convert loop: PHI edges both inside loop, or both outside loop.\n");
1379 if (flow_bb_inside_loop_p (loop, PHI_ARG_EDGE (phi, 0)->src))
1381 lboundvar = PHI_ARG_DEF (phi, 1);
1382 lbound = gcc_tree_to_linear_expression (depth, lboundvar,
1383 outerinductionvars, *invariants,
1388 lboundvar = PHI_ARG_DEF (phi, 0);
1389 lbound = gcc_tree_to_linear_expression (depth, lboundvar,
1390 outerinductionvars, *invariants,
1397 if (dump_file && (dump_flags & TDF_DETAILS))
1399 "Unable to convert loop: Cannot convert lower bound to linear expression\n");
1403 /* One part of the test may be a loop invariant tree. */
1404 if (TREE_CODE (TREE_OPERAND (test, 1)) == SSA_NAME
1405 && invariant_in_loop_and_outer_loops (loop, TREE_OPERAND (test, 1)))
1406 VEC_safe_push (tree, *invariants, TREE_OPERAND (test, 1));
1407 else if (TREE_CODE (TREE_OPERAND (test, 0)) == SSA_NAME
1408 && invariant_in_loop_and_outer_loops (loop, TREE_OPERAND (test, 0)))
1409 VEC_safe_push (tree, *invariants, TREE_OPERAND (test, 0));
1411 /* The non-induction variable part of the test is the upper bound variable.
1413 if (TREE_OPERAND (test, 0) == inductionvar)
1414 uboundvar = TREE_OPERAND (test, 1);
1416 uboundvar = TREE_OPERAND (test, 0);
1419 /* We only size the vectors assuming we have, at max, 2 times as many
1420 invariants as we do loops (one for each bound).
1421 This is just an arbitrary number, but it has to be matched against the
1423 gcc_assert (VEC_length (tree, *invariants) <= (unsigned int) (2 * depth));
1426 /* We might have some leftover. */
1427 if (TREE_CODE (test) == LT_EXPR)
1428 extra = -1 * stepint;
1429 else if (TREE_CODE (test) == NE_EXPR)
1430 extra = -1 * stepint;
1431 else if (TREE_CODE (test) == GT_EXPR)
1432 extra = -1 * stepint;
1433 else if (TREE_CODE (test) == EQ_EXPR)
1434 extra = 1 * stepint;
1436 ubound = gcc_tree_to_linear_expression (depth, uboundvar,
1438 *invariants, extra);
1439 uboundresult = build (PLUS_EXPR, TREE_TYPE (uboundvar), uboundvar,
1440 build_int_cst (TREE_TYPE (uboundvar), extra));
1441 VEC_safe_push (tree, *uboundvars, uboundresult);
1442 VEC_safe_push (tree, *lboundvars, lboundvar);
1443 VEC_safe_push (int, *steps, stepint);
1446 if (dump_file && (dump_flags & TDF_DETAILS))
1448 "Unable to convert loop: Cannot convert upper bound to linear expression\n");
1452 lloop = lambda_loop_new ();
1453 LL_STEP (lloop) = stepint;
1454 LL_LOWER_BOUND (lloop) = lbound;
1455 LL_UPPER_BOUND (lloop) = ubound;
1459 /* Given a LOOP, find the induction variable it is testing against in the exit
1460 condition. Return the induction variable if found, NULL otherwise. */
1463 find_induction_var_from_exit_cond (struct loop *loop)
1465 tree expr = get_loop_exit_condition (loop);
1468 if (expr == NULL_TREE)
1470 if (TREE_CODE (expr) != COND_EXPR)
1472 test = TREE_OPERAND (expr, 0);
1473 if (!COMPARISON_CLASS_P (test))
1476 /* Find the side that is invariant in this loop. The ivar must be the other
1479 if (expr_invariant_in_loop_p (loop, TREE_OPERAND (test, 0)))
1480 ivarop = TREE_OPERAND (test, 1);
1481 else if (expr_invariant_in_loop_p (loop, TREE_OPERAND (test, 1)))
1482 ivarop = TREE_OPERAND (test, 0);
1486 if (TREE_CODE (ivarop) != SSA_NAME)
1491 DEF_VEC_GC_P(lambda_loop);
1492 /* Generate a lambda loopnest from a gcc loopnest LOOP_NEST.
1493 Return the new loop nest.
1494 INDUCTIONVARS is a pointer to an array of induction variables for the
1495 loopnest that will be filled in during this process.
1496 INVARIANTS is a pointer to an array of invariants that will be filled in
1497 during this process. */
1500 gcc_loopnest_to_lambda_loopnest (struct loops *currloops,
1501 struct loop * loop_nest,
1502 VEC (tree) **inductionvars,
1503 VEC (tree) **invariants,
1504 bool need_perfect_nest)
1506 lambda_loopnest ret;
1510 VEC (lambda_loop) *loops = NULL;
1511 VEC (tree) *uboundvars = NULL;
1512 VEC (tree) *lboundvars = NULL;
1513 VEC (int) *steps = NULL;
1514 lambda_loop newloop;
1515 tree inductionvar = NULL;
1517 depth = depth_of_nest (loop_nest);
1521 newloop = gcc_loop_to_lambda_loop (temp, depth, invariants,
1522 &inductionvar, *inductionvars,
1523 &lboundvars, &uboundvars,
1527 VEC_safe_push (tree, *inductionvars, inductionvar);
1528 VEC_safe_push (lambda_loop, loops, newloop);
1531 if (need_perfect_nest)
1533 if (!perfect_nestify (currloops, loop_nest,
1534 lboundvars, uboundvars, steps, *inductionvars))
1537 fprintf (dump_file, "Not a perfect loop nest and couldn't convert to one.\n");
1541 fprintf (dump_file, "Successfully converted loop nest to perfect loop nest.\n");
1545 ret = lambda_loopnest_new (depth, 2 * depth);
1546 for (i = 0; VEC_iterate (lambda_loop, loops, i, newloop); i++)
1547 LN_LOOPS (ret)[i] = newloop;
1554 /* Convert a lambda body vector LBV to a gcc tree, and return the new tree.
1555 STMTS_TO_INSERT is a pointer to a tree where the statements we need to be
1556 inserted for us are stored. INDUCTION_VARS is the array of induction
1557 variables for the loop this LBV is from. TYPE is the tree type to use for
1558 the variables and trees involved. */
1561 lbv_to_gcc_expression (lambda_body_vector lbv,
1562 tree type, VEC (tree) *induction_vars,
1563 tree * stmts_to_insert)
1565 tree stmts, stmt, resvar, name;
1568 tree_stmt_iterator tsi;
1570 /* Create a statement list and a linear expression temporary. */
1571 stmts = alloc_stmt_list ();
1572 resvar = create_tmp_var (type, "lbvtmp");
1573 add_referenced_tmp_var (resvar);
1576 stmt = build (MODIFY_EXPR, void_type_node, resvar, integer_zero_node);
1577 name = make_ssa_name (resvar, stmt);
1578 TREE_OPERAND (stmt, 0) = name;
1579 tsi = tsi_last (stmts);
1580 tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1582 for (i = 0; VEC_iterate (tree, induction_vars, i, iv); i++)
1584 if (LBV_COEFFICIENTS (lbv)[i] != 0)
1589 /* newname = coefficient * induction_variable */
1590 coeffmult = build_int_cst (type, LBV_COEFFICIENTS (lbv)[i]);
1591 stmt = build (MODIFY_EXPR, void_type_node, resvar,
1592 fold (build (MULT_EXPR, type, iv, coeffmult)));
1594 newname = make_ssa_name (resvar, stmt);
1595 TREE_OPERAND (stmt, 0) = newname;
1597 tsi = tsi_last (stmts);
1598 tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1600 /* name = name + newname */
1601 stmt = build (MODIFY_EXPR, void_type_node, resvar,
1602 build (PLUS_EXPR, type, name, newname));
1603 name = make_ssa_name (resvar, stmt);
1604 TREE_OPERAND (stmt, 0) = name;
1606 tsi = tsi_last (stmts);
1607 tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1612 /* Handle any denominator that occurs. */
1613 if (LBV_DENOMINATOR (lbv) != 1)
1615 tree denominator = build_int_cst (type, LBV_DENOMINATOR (lbv));
1616 stmt = build (MODIFY_EXPR, void_type_node, resvar,
1617 build (CEIL_DIV_EXPR, type, name, denominator));
1618 name = make_ssa_name (resvar, stmt);
1619 TREE_OPERAND (stmt, 0) = name;
1621 tsi = tsi_last (stmts);
1622 tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1624 *stmts_to_insert = stmts;
1628 /* Convert a linear expression from coefficient and constant form to a
1630 Return the tree that represents the final value of the expression.
1631 LLE is the linear expression to convert.
1632 OFFSET is the linear offset to apply to the expression.
1633 TYPE is the tree type to use for the variables and math.
1634 INDUCTION_VARS is a vector of induction variables for the loops.
1635 INVARIANTS is a vector of the loop nest invariants.
1636 WRAP specifies what tree code to wrap the results in, if there is more than
1637 one (it is either MAX_EXPR, or MIN_EXPR).
1638 STMTS_TO_INSERT Is a pointer to the statement list we fill in with
1639 statements that need to be inserted for the linear expression. */
1642 lle_to_gcc_expression (lambda_linear_expression lle,
1643 lambda_linear_expression offset,
1645 VEC(tree) *induction_vars,
1646 VEC(tree) *invariants,
1647 enum tree_code wrap, tree * stmts_to_insert)
1649 tree stmts, stmt, resvar, name;
1651 tree_stmt_iterator tsi;
1653 VEC(tree) *results = NULL;
1656 /* Create a statement list and a linear expression temporary. */
1657 stmts = alloc_stmt_list ();
1658 resvar = create_tmp_var (type, "lletmp");
1659 add_referenced_tmp_var (resvar);
1661 /* Build up the linear expressions, and put the variable representing the
1662 result in the results array. */
1663 for (; lle != NULL; lle = LLE_NEXT (lle))
1665 /* Start at name = 0. */
1666 stmt = build (MODIFY_EXPR, void_type_node, resvar, integer_zero_node);
1667 name = make_ssa_name (resvar, stmt);
1668 TREE_OPERAND (stmt, 0) = name;
1670 tsi = tsi_last (stmts);
1671 tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1673 /* First do the induction variables.
1674 at the end, name = name + all the induction variables added
1676 for (i = 0; VEC_iterate (tree, induction_vars, i, iv); i++)
1678 if (LLE_COEFFICIENTS (lle)[i] != 0)
1684 /* mult = induction variable * coefficient. */
1685 if (LLE_COEFFICIENTS (lle)[i] == 1)
1687 mult = VEC_index (tree, induction_vars, i);
1691 coeff = build_int_cst (type,
1692 LLE_COEFFICIENTS (lle)[i]);
1693 mult = fold (build (MULT_EXPR, type, iv, coeff));
1696 /* newname = mult */
1697 stmt = build (MODIFY_EXPR, void_type_node, resvar, mult);
1698 newname = make_ssa_name (resvar, stmt);
1699 TREE_OPERAND (stmt, 0) = newname;
1701 tsi = tsi_last (stmts);
1702 tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1704 /* name = name + newname */
1705 stmt = build (MODIFY_EXPR, void_type_node, resvar,
1706 build (PLUS_EXPR, type, name, newname));
1707 name = make_ssa_name (resvar, stmt);
1708 TREE_OPERAND (stmt, 0) = name;
1710 tsi = tsi_last (stmts);
1711 tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1715 /* Handle our invariants.
1716 At the end, we have name = name + result of adding all multiplied
1718 for (i = 0; VEC_iterate (tree, invariants, i, invar); i++)
1720 if (LLE_INVARIANT_COEFFICIENTS (lle)[i] != 0)
1725 int invcoeff = LLE_INVARIANT_COEFFICIENTS (lle)[i];
1726 /* mult = invariant * coefficient */
1733 coeff = build_int_cst (type, invcoeff);
1734 mult = fold (build (MULT_EXPR, type, invar, coeff));
1737 /* newname = mult */
1738 stmt = build (MODIFY_EXPR, void_type_node, resvar, mult);
1739 newname = make_ssa_name (resvar, stmt);
1740 TREE_OPERAND (stmt, 0) = newname;
1742 tsi = tsi_last (stmts);
1743 tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1745 /* name = name + newname */
1746 stmt = build (MODIFY_EXPR, void_type_node, resvar,
1747 build (PLUS_EXPR, type, name, newname));
1748 name = make_ssa_name (resvar, stmt);
1749 TREE_OPERAND (stmt, 0) = name;
1751 tsi = tsi_last (stmts);
1752 tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1756 /* Now handle the constant.
1757 name = name + constant. */
1758 if (LLE_CONSTANT (lle) != 0)
1760 stmt = build (MODIFY_EXPR, void_type_node, resvar,
1761 build (PLUS_EXPR, type, name,
1762 build_int_cst (type, LLE_CONSTANT (lle))));
1763 name = make_ssa_name (resvar, stmt);
1764 TREE_OPERAND (stmt, 0) = name;
1766 tsi = tsi_last (stmts);
1767 tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1770 /* Now handle the offset.
1771 name = name + linear offset. */
1772 if (LLE_CONSTANT (offset) != 0)
1774 stmt = build (MODIFY_EXPR, void_type_node, resvar,
1775 build (PLUS_EXPR, type, name,
1776 build_int_cst (type, LLE_CONSTANT (offset))));
1777 name = make_ssa_name (resvar, stmt);
1778 TREE_OPERAND (stmt, 0) = name;
1780 tsi = tsi_last (stmts);
1781 tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1784 /* Handle any denominator that occurs. */
1785 if (LLE_DENOMINATOR (lle) != 1)
1787 if (wrap == MAX_EXPR)
1788 stmt = build (MODIFY_EXPR, void_type_node, resvar,
1789 build (CEIL_DIV_EXPR, type, name,
1790 build_int_cst (type, LLE_DENOMINATOR (lle))));
1791 else if (wrap == MIN_EXPR)
1792 stmt = build (MODIFY_EXPR, void_type_node, resvar,
1793 build (FLOOR_DIV_EXPR, type, name,
1794 build_int_cst (type, LLE_DENOMINATOR (lle))));
1798 /* name = {ceil, floor}(name/denominator) */
1799 name = make_ssa_name (resvar, stmt);
1800 TREE_OPERAND (stmt, 0) = name;
1801 tsi = tsi_last (stmts);
1802 tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1804 VEC_safe_push (tree, results, name);
1807 /* Again, out of laziness, we don't handle this case yet. It's not
1808 hard, it just hasn't occurred. */
1809 gcc_assert (VEC_length (tree, results) <= 2);
1811 /* We may need to wrap the results in a MAX_EXPR or MIN_EXPR. */
1812 if (VEC_length (tree, results) > 1)
1814 tree op1 = VEC_index (tree, results, 0);
1815 tree op2 = VEC_index (tree, results, 1);
1816 stmt = build (MODIFY_EXPR, void_type_node, resvar,
1817 build (wrap, type, op1, op2));
1818 name = make_ssa_name (resvar, stmt);
1819 TREE_OPERAND (stmt, 0) = name;
1820 tsi = tsi_last (stmts);
1821 tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
1824 *stmts_to_insert = stmts;
1828 /* Transform a lambda loopnest NEW_LOOPNEST, which had TRANSFORM applied to
1829 it, back into gcc code. This changes the
1830 loops, their induction variables, and their bodies, so that they
1831 match the transformed loopnest.
1832 OLD_LOOPNEST is the loopnest before we've replaced it with the new
1834 OLD_IVS is a vector of induction variables from the old loopnest.
1835 INVARIANTS is a vector of loop invariants from the old loopnest.
1836 NEW_LOOPNEST is the new lambda loopnest to replace OLD_LOOPNEST with.
1837 TRANSFORM is the matrix transform that was applied to OLD_LOOPNEST to get
1841 lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest,
1843 VEC(tree) *invariants,
1844 lambda_loopnest new_loopnest,
1845 lambda_trans_matrix transform)
1851 VEC(tree) *new_ivs = NULL;
1854 block_stmt_iterator bsi;
1858 transform = lambda_trans_matrix_inverse (transform);
1859 fprintf (dump_file, "Inverse of transformation matrix:\n");
1860 print_lambda_trans_matrix (dump_file, transform);
1862 depth = depth_of_nest (old_loopnest);
1863 temp = old_loopnest;
1867 lambda_loop newloop;
1870 tree ivvar, ivvarinced, exitcond, stmts;
1871 enum tree_code testtype;
1872 tree newupperbound, newlowerbound;
1873 lambda_linear_expression offset;
1878 oldiv = VEC_index (tree, old_ivs, i);
1879 type = TREE_TYPE (oldiv);
1881 /* First, build the new induction variable temporary */
1883 ivvar = create_tmp_var (type, "lnivtmp");
1884 add_referenced_tmp_var (ivvar);
1886 VEC_safe_push (tree, new_ivs, ivvar);
1888 newloop = LN_LOOPS (new_loopnest)[i];
1890 /* Linear offset is a bit tricky to handle. Punt on the unhandled
1892 offset = LL_LINEAR_OFFSET (newloop);
1894 gcc_assert (LLE_DENOMINATOR (offset) == 1 &&
1895 lambda_vector_zerop (LLE_COEFFICIENTS (offset), depth));
1897 /* Now build the new lower bounds, and insert the statements
1898 necessary to generate it on the loop preheader. */
1899 newlowerbound = lle_to_gcc_expression (LL_LOWER_BOUND (newloop),
1900 LL_LINEAR_OFFSET (newloop),
1903 invariants, MAX_EXPR, &stmts);
1904 bsi_insert_on_edge (loop_preheader_edge (temp), stmts);
1905 bsi_commit_edge_inserts ();
1906 /* Build the new upper bound and insert its statements in the
1907 basic block of the exit condition */
1908 newupperbound = lle_to_gcc_expression (LL_UPPER_BOUND (newloop),
1909 LL_LINEAR_OFFSET (newloop),
1912 invariants, MIN_EXPR, &stmts);
1913 exit = temp->single_exit;
1914 exitcond = get_loop_exit_condition (temp);
1915 bb = bb_for_stmt (exitcond);
1916 bsi = bsi_start (bb);
1917 bsi_insert_after (&bsi, stmts, BSI_NEW_STMT);
1919 /* Create the new iv. */
1921 standard_iv_increment_position (temp, &bsi, &insert_after);
1922 create_iv (newlowerbound,
1923 build_int_cst (type, LL_STEP (newloop)),
1924 ivvar, temp, &bsi, insert_after, &ivvar,
1927 /* Unfortunately, the incremented ivvar that create_iv inserted may not
1928 dominate the block containing the exit condition.
1929 So we simply create our own incremented iv to use in the new exit
1930 test, and let redundancy elimination sort it out. */
1931 inc_stmt = build (PLUS_EXPR, type,
1932 ivvar, build_int_cst (type, LL_STEP (newloop)));
1933 inc_stmt = build (MODIFY_EXPR, void_type_node, SSA_NAME_VAR (ivvar),
1935 ivvarinced = make_ssa_name (SSA_NAME_VAR (ivvar), inc_stmt);
1936 TREE_OPERAND (inc_stmt, 0) = ivvarinced;
1937 bsi = bsi_for_stmt (exitcond);
1938 bsi_insert_before (&bsi, inc_stmt, BSI_SAME_STMT);
1940 /* Replace the exit condition with the new upper bound
1943 testtype = LL_STEP (newloop) >= 0 ? LE_EXPR : GE_EXPR;
1945 /* We want to build a conditional where true means exit the loop, and
1946 false means continue the loop.
1947 So swap the testtype if this isn't the way things are.*/
1949 if (exit->flags & EDGE_FALSE_VALUE)
1950 testtype = swap_tree_comparison (testtype);
1952 COND_EXPR_COND (exitcond) = build (testtype,
1954 newupperbound, ivvarinced);
1955 update_stmt (exitcond);
1956 VEC_replace (tree, new_ivs, i, ivvar);
1962 /* Rewrite uses of the old ivs so that they are now specified in terms of
1965 for (i = 0; VEC_iterate (tree, old_ivs, i, oldiv); i++)
1967 imm_use_iterator imm_iter;
1968 use_operand_p imm_use;
1970 tree oldiv_stmt = SSA_NAME_DEF_STMT (oldiv);
1972 gcc_assert (TREE_CODE (oldiv_stmt) == PHI_NODE
1973 || NUM_DEFS (STMT_DEF_OPS (oldiv_stmt)) == 1);
1974 if (TREE_CODE (oldiv_stmt) == PHI_NODE)
1975 oldiv_def = PHI_RESULT (oldiv_stmt);
1977 oldiv_def = DEF_OP (STMT_DEF_OPS (oldiv_stmt), 0);
1979 FOR_EACH_IMM_USE_SAFE (imm_use, imm_iter, oldiv_def)
1981 tree stmt = USE_STMT (imm_use);
1982 use_operand_p use_p;
1984 gcc_assert (TREE_CODE (stmt) != PHI_NODE);
1985 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1987 if (USE_FROM_PTR (use_p) == oldiv)
1990 lambda_body_vector lbv, newlbv;
1991 /* Compute the new expression for the induction
1993 depth = VEC_length (tree, new_ivs);
1994 lbv = lambda_body_vector_new (depth);
1995 LBV_COEFFICIENTS (lbv)[i] = 1;
1997 newlbv = lambda_body_vector_compute_new (transform, lbv);
1999 newiv = lbv_to_gcc_expression (newlbv, TREE_TYPE (oldiv),
2001 bsi = bsi_for_stmt (stmt);
2002 /* Insert the statements to build that
2004 bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
2005 propagate_value (use_p, newiv);
2015 /* Returns true when the vector V is lexicographically positive, in
2016 other words, when the first nonzero element is positive. */
2019 lambda_vector_lexico_pos (lambda_vector v,
2023 for (i = 0; i < n; i++)
2036 /* Return TRUE if this is not interesting statement from the perspective of
2037 determining if we have a perfect loop nest. */
2040 not_interesting_stmt (tree stmt)
2042 /* Note that COND_EXPR's aren't interesting because if they were exiting the
2043 loop, we would have already failed the number of exits tests. */
2044 if (TREE_CODE (stmt) == LABEL_EXPR
2045 || TREE_CODE (stmt) == GOTO_EXPR
2046 || TREE_CODE (stmt) == COND_EXPR)
2051 /* Return TRUE if PHI uses DEF for it's in-the-loop edge for LOOP. */
2054 phi_loop_edge_uses_def (struct loop *loop, tree phi, tree def)
2057 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
2058 if (flow_bb_inside_loop_p (loop, PHI_ARG_EDGE (phi, i)->src))
2059 if (PHI_ARG_DEF (phi, i) == def)
2064 /* Return TRUE if STMT is a use of PHI_RESULT. */
2067 stmt_uses_phi_result (tree stmt, tree phi_result)
2069 use_optype uses = STMT_USE_OPS (stmt);
2071 /* This is conservatively true, because we only want SIMPLE bumpers
2072 of the form x +- constant for our pass. */
2073 if (NUM_USES (uses) != 1)
2075 if (USE_OP (uses, 0) == phi_result)
2081 /* STMT is a bumper stmt for LOOP if the version it defines is used in the
2082 in-loop-edge in a phi node, and the operand it uses is the result of that
2085 i_3 = PHI (0, i_29); */
2088 stmt_is_bumper_for_loop (struct loop *loop, tree stmt)
2092 def_optype defs = STMT_DEF_OPS (stmt);
2093 imm_use_iterator iter;
2094 use_operand_p use_p;
2096 if (NUM_DEFS (defs) != 1)
2098 def = DEF_OP (defs, 0);
2099 FOR_EACH_IMM_USE_FAST (use_p, iter, def)
2101 use = USE_STMT (use_p);
2102 if (TREE_CODE (use) == PHI_NODE)
2104 if (phi_loop_edge_uses_def (loop, use, def))
2105 if (stmt_uses_phi_result (stmt, PHI_RESULT (use)))
2113 /* Return true if LOOP is a perfect loop nest.
2114 Perfect loop nests are those loop nests where all code occurs in the
2115 innermost loop body.
2116 If S is a program statement, then
2125 is not a perfect loop nest because of S1.
2133 is a perfect loop nest.
2135 Since we don't have high level loops anymore, we basically have to walk our
2136 statements and ignore those that are there because the loop needs them (IE
2137 the induction variable increment, and jump back to the top of the loop). */
2140 perfect_nest_p (struct loop *loop)
2148 bbs = get_loop_body (loop);
2149 exit_cond = get_loop_exit_condition (loop);
2150 for (i = 0; i < loop->num_nodes; i++)
2152 if (bbs[i]->loop_father == loop)
2154 block_stmt_iterator bsi;
2155 for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi))
2157 tree stmt = bsi_stmt (bsi);
2158 if (stmt == exit_cond
2159 || not_interesting_stmt (stmt)
2160 || stmt_is_bumper_for_loop (loop, stmt))
2168 /* See if the inner loops are perfectly nested as well. */
2170 return perfect_nest_p (loop->inner);
2174 /* Replace the USES of tree X in STMT with tree Y */
2177 replace_uses_of_x_with_y (tree stmt, tree x, tree y)
2179 use_optype uses = STMT_USE_OPS (stmt);
2181 for (i = 0; i < NUM_USES (uses); i++)
2183 if (USE_OP (uses, i) == x)
2184 SET_USE_OP (uses, i, y);
2188 /* Return TRUE if STMT uses tree OP in it's uses. */
2191 stmt_uses_op (tree stmt, tree op)
2193 use_optype uses = STMT_USE_OPS (stmt);
2195 for (i = 0; i < NUM_USES (uses); i++)
2197 if (USE_OP (uses, i) == op)
2203 /* Return TRUE if LOOP is an imperfect nest that we can convert to a perfect
2204 one. LOOPIVS is a vector of induction variables, one per loop.
2205 ATM, we only handle imperfect nests of depth 2, where all of the statements
2206 occur after the inner loop. */
2209 can_convert_to_perfect_nest (struct loop *loop,
2210 VEC (tree) *loopivs)
2213 tree exit_condition, phi;
2215 block_stmt_iterator bsi;
2216 basic_block exitdest;
2218 /* Can't handle triply nested+ loops yet. */
2219 if (!loop->inner || loop->inner->inner)
2222 /* We only handle moving the after-inner-body statements right now, so make
2223 sure all the statements we need to move are located in that position. */
2224 bbs = get_loop_body (loop);
2225 exit_condition = get_loop_exit_condition (loop);
2226 for (i = 0; i < loop->num_nodes; i++)
2228 if (bbs[i]->loop_father == loop)
2230 for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi))
2233 tree stmt = bsi_stmt (bsi);
2234 if (stmt == exit_condition
2235 || not_interesting_stmt (stmt)
2236 || stmt_is_bumper_for_loop (loop, stmt))
2238 /* If the statement uses inner loop ivs, we == screwed. */
2239 for (j = 1; j < VEC_length (tree, loopivs); j++)
2240 if (stmt_uses_op (stmt, VEC_index (tree, loopivs, j)))
2246 /* If the bb of a statement we care about isn't dominated by
2247 the header of the inner loop, then we are also screwed. */
2248 if (!dominated_by_p (CDI_DOMINATORS,
2250 loop->inner->header))
2259 /* We also need to make sure the loop exit only has simple copy phis in it,
2260 otherwise we don't know how to transform it into a perfect nest right
2262 exitdest = loop->single_exit->dest;
2264 for (phi = phi_nodes (exitdest); phi; phi = PHI_CHAIN (phi))
2265 if (PHI_NUM_ARGS (phi) != 1)
2271 /* Transform the loop nest into a perfect nest, if possible.
2272 LOOPS is the current struct loops *
2273 LOOP is the loop nest to transform into a perfect nest
2274 LBOUNDS are the lower bounds for the loops to transform
2275 UBOUNDS are the upper bounds for the loops to transform
2276 STEPS is the STEPS for the loops to transform.
2277 LOOPIVS is the induction variables for the loops to transform.
2279 Basically, for the case of
2281 FOR (i = 0; i < 50; i++)
2283 FOR (j =0; j < 50; j++)
2290 This function will transform it into a perfect loop nest by splitting the
2291 outer loop into two loops, like so:
2293 FOR (i = 0; i < 50; i++)
2295 FOR (j = 0; j < 50; j++)
2301 FOR (i = 0; i < 50; i ++)
2306 Return FALSE if we can't make this loop into a perfect nest. */
2308 perfect_nestify (struct loops *loops,
2310 VEC (tree) *lbounds,
2311 VEC (tree) *ubounds,
2313 VEC (tree) *loopivs)
2316 tree exit_condition;
2317 tree then_label, else_label, cond_stmt;
2318 basic_block preheaderbb, headerbb, bodybb, latchbb, olddest;
2320 block_stmt_iterator bsi;
2323 struct loop *newloop;
2327 tree oldivvar, ivvar, ivvarinced;
2328 VEC (tree) *phis = NULL;
2330 if (!can_convert_to_perfect_nest (loop, loopivs))
2333 /* Create the new loop */
2335 olddest = loop->single_exit->dest;
2336 preheaderbb = loop_split_edge_with (loop->single_exit, NULL);
2337 headerbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
2339 /* Push the exit phi nodes that we are moving. */
2340 for (phi = phi_nodes (olddest); phi; phi = PHI_CHAIN (phi))
2342 VEC_safe_push (tree, phis, PHI_RESULT (phi));
2343 VEC_safe_push (tree, phis, PHI_ARG_DEF (phi, 0));
2345 e = redirect_edge_and_branch (single_succ_edge (preheaderbb), headerbb);
2347 /* Remove the exit phis from the old basic block. Make sure to set
2348 PHI_RESULT to null so it doesn't get released. */
2349 while (phi_nodes (olddest) != NULL)
2351 SET_PHI_RESULT (phi_nodes (olddest), NULL);
2352 remove_phi_node (phi_nodes (olddest), NULL);
2355 /* and add them back to the new basic block. */
2356 while (VEC_length (tree, phis) != 0)
2360 def = VEC_pop (tree, phis);
2361 phiname = VEC_pop (tree, phis);
2362 phi = create_phi_node (phiname, preheaderbb);
2363 add_phi_arg (phi, def, single_pred_edge (preheaderbb));
2365 flush_pending_stmts (e);
2367 bodybb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
2368 latchbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
2369 make_edge (headerbb, bodybb, EDGE_FALLTHRU);
2370 then_label = build1 (GOTO_EXPR, void_type_node, tree_block_label (latchbb));
2371 else_label = build1 (GOTO_EXPR, void_type_node, tree_block_label (olddest));
2372 cond_stmt = build (COND_EXPR, void_type_node,
2373 build (NE_EXPR, boolean_type_node,
2376 then_label, else_label);
2377 bsi = bsi_start (bodybb);
2378 bsi_insert_after (&bsi, cond_stmt, BSI_NEW_STMT);
2379 e = make_edge (bodybb, olddest, EDGE_FALSE_VALUE);
2380 make_edge (bodybb, latchbb, EDGE_TRUE_VALUE);
2381 make_edge (latchbb, headerbb, EDGE_FALLTHRU);
2383 /* Update the loop structures. */
2384 newloop = duplicate_loop (loops, loop, olddest->loop_father);
2385 newloop->header = headerbb;
2386 newloop->latch = latchbb;
2387 newloop->single_exit = e;
2388 add_bb_to_loop (latchbb, newloop);
2389 add_bb_to_loop (bodybb, newloop);
2390 add_bb_to_loop (headerbb, newloop);
2391 set_immediate_dominator (CDI_DOMINATORS, bodybb, headerbb);
2392 set_immediate_dominator (CDI_DOMINATORS, headerbb, preheaderbb);
2393 set_immediate_dominator (CDI_DOMINATORS, preheaderbb,
2394 loop->single_exit->src);
2395 set_immediate_dominator (CDI_DOMINATORS, latchbb, bodybb);
2396 set_immediate_dominator (CDI_DOMINATORS, olddest, bodybb);
2397 /* Create the new iv. */
2398 ivvar = create_tmp_var (integer_type_node, "perfectiv");
2399 add_referenced_tmp_var (ivvar);
2400 standard_iv_increment_position (newloop, &bsi, &insert_after);
2401 create_iv (VEC_index (tree, lbounds, 0),
2402 build_int_cst (integer_type_node, VEC_index (int, steps, 0)),
2403 ivvar, newloop, &bsi, insert_after, &ivvar, &ivvarinced);
2405 /* Create the new upper bound. This may be not just a variable, so we copy
2406 it to one just in case. */
2408 exit_condition = get_loop_exit_condition (newloop);
2409 uboundvar = create_tmp_var (integer_type_node, "uboundvar");
2410 add_referenced_tmp_var (uboundvar);
2411 stmt = build (MODIFY_EXPR, void_type_node, uboundvar,
2412 VEC_index (tree, ubounds, 0));
2413 uboundvar = make_ssa_name (uboundvar, stmt);
2414 TREE_OPERAND (stmt, 0) = uboundvar;
2417 bsi_insert_after (&bsi, stmt, BSI_SAME_STMT);
2419 bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
2421 COND_EXPR_COND (exit_condition) = build (GE_EXPR,
2426 bbs = get_loop_body (loop);
2427 /* Now replace the induction variable in the moved statements with the
2428 correct loop induction variable. */
2429 oldivvar = VEC_index (tree, loopivs, 0);
2430 for (i = 0; i < loop->num_nodes; i++)
2432 block_stmt_iterator tobsi = bsi_last (bodybb);
2433 if (bbs[i]->loop_father == loop)
2435 /* Note that the bsi only needs to be explicitly incremented
2436 when we don't move something, since it is automatically
2437 incremented when we do. */
2438 for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi);)
2440 tree stmt = bsi_stmt (bsi);
2441 if (stmt == exit_condition
2442 || not_interesting_stmt (stmt)
2443 || stmt_is_bumper_for_loop (loop, stmt))
2448 replace_uses_of_x_with_y (stmt, oldivvar, ivvar);
2449 bsi_move_before (&bsi, &tobsi);
2454 return perfect_nest_p (loop);
2457 /* Return true if TRANS is a legal transformation matrix that respects
2458 the dependence vectors in DISTS and DIRS. The conservative answer
2461 "Wolfe proves that a unimodular transformation represented by the
2462 matrix T is legal when applied to a loop nest with a set of
2463 lexicographically non-negative distance vectors RDG if and only if
2464 for each vector d in RDG, (T.d >= 0) is lexicographically positive.
2465 i.e.: if and only if it transforms the lexicographically positive
2466 distance vectors to lexicographically positive vectors. Note that
2467 a unimodular matrix must transform the zero vector (and only it) to
2468 the zero vector." S.Muchnick. */
2471 lambda_transform_legal_p (lambda_trans_matrix trans,
2473 varray_type dependence_relations)
2476 lambda_vector distres;
2477 struct data_dependence_relation *ddr;
2479 #if defined ENABLE_CHECKING
2480 if (LTM_COLSIZE (trans) != nb_loops
2481 || LTM_ROWSIZE (trans) != nb_loops)
2485 /* When there is an unknown relation in the dependence_relations, we
2486 know that it is no worth looking at this loop nest: give up. */
2487 ddr = (struct data_dependence_relation *)
2488 VARRAY_GENERIC_PTR (dependence_relations, 0);
2491 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
2494 distres = lambda_vector_new (nb_loops);
2496 /* For each distance vector in the dependence graph. */
2497 for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
2499 ddr = (struct data_dependence_relation *)
2500 VARRAY_GENERIC_PTR (dependence_relations, i);
2502 /* Don't care about relations for which we know that there is no
2503 dependence, nor about read-read (aka. output-dependences):
2504 these data accesses can happen in any order. */
2505 if (DDR_ARE_DEPENDENT (ddr) == chrec_known
2506 || (DR_IS_READ (DDR_A (ddr)) && DR_IS_READ (DDR_B (ddr))))
2509 /* Conservatively answer: "this transformation is not valid". */
2510 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
2513 /* If the dependence could not be captured by a distance vector,
2514 conservatively answer that the transform is not valid. */
2515 if (DDR_DIST_VECT (ddr) == NULL)
2518 /* Compute trans.dist_vect */
2519 lambda_matrix_vector_mult (LTM_MATRIX (trans), nb_loops, nb_loops,
2520 DDR_DIST_VECT (ddr), distres);
2522 if (!lambda_vector_lexico_pos (distres, nb_loops))