1 /* Loop transformation code generation
2 Copyright (C) 2003, 2004, 2005, 2006 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, 51 Franklin Street, Fifth Floor, Boston, MA
24 #include "coretypes.h"
30 #include "basic-block.h"
31 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
38 #include "tree-chrec.h"
39 #include "tree-data-ref.h"
40 #include "tree-pass.h"
41 #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
118 static bool perfect_nestify (struct loop
*, VEC(tree
,heap
) *,
119 VEC(tree
,heap
) *, VEC(int,heap
) *,
121 /* Lattice stuff that is internal to the code generation algorithm. */
125 /* Lattice base matrix. */
127 /* Lattice 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. */
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)
143 static bool lle_equal (lambda_linear_expression
, lambda_linear_expression
,
145 static lambda_lattice
lambda_lattice_new (int, int);
146 static lambda_lattice
lambda_lattice_compute_base (lambda_loopnest
);
148 static tree
find_induction_var_from_exit_cond (struct loop
*);
149 static bool can_convert_to_perfect_nest (struct loop
*);
151 /* Create a new lambda body vector. */
154 lambda_body_vector_new (int size
)
156 lambda_body_vector ret
;
158 ret
= ggc_alloc (sizeof (*ret
));
159 LBV_COEFFICIENTS (ret
) = lambda_vector_new (size
);
160 LBV_SIZE (ret
) = size
;
161 LBV_DENOMINATOR (ret
) = 1;
165 /* Compute the new coefficients for the vector based on the
166 *inverse* of the transformation matrix. */
169 lambda_body_vector_compute_new (lambda_trans_matrix transform
,
170 lambda_body_vector vect
)
172 lambda_body_vector temp
;
175 /* Make sure the matrix is square. */
176 gcc_assert (LTM_ROWSIZE (transform
) == LTM_COLSIZE (transform
));
178 depth
= LTM_ROWSIZE (transform
);
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
);
190 /* Print out a lambda body vector. */
193 print_lambda_body_vector (FILE * outfile
, lambda_body_vector body
)
195 print_lambda_vector (outfile
, LBV_COEFFICIENTS (body
), LBV_SIZE (body
));
198 /* Return TRUE if two linear expressions are equal. */
201 lle_equal (lambda_linear_expression lle1
, lambda_linear_expression lle2
,
202 int depth
, int invariants
)
206 if (lle1
== NULL
|| lle2
== NULL
)
208 if (LLE_CONSTANT (lle1
) != LLE_CONSTANT (lle2
))
210 if (LLE_DENOMINATOR (lle1
) != LLE_DENOMINATOR (lle2
))
212 for (i
= 0; i
< depth
; i
++)
213 if (LLE_COEFFICIENTS (lle1
)[i
] != LLE_COEFFICIENTS (lle2
)[i
])
215 for (i
= 0; i
< invariants
; i
++)
216 if (LLE_INVARIANT_COEFFICIENTS (lle1
)[i
] !=
217 LLE_INVARIANT_COEFFICIENTS (lle2
)[i
])
222 /* Create a new linear expression with dimension DIM, and total number
223 of invariants INVARIANTS. */
225 lambda_linear_expression
226 lambda_linear_expression_new (int dim
, int invariants
)
228 lambda_linear_expression ret
;
230 ret
= ggc_alloc_cleared (sizeof (*ret
));
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
;
241 /* Print out a linear expression EXPR, with SIZE coefficients, to OUTFILE.
242 The starting letter used for variable names is START. */
245 print_linear_expression (FILE * outfile
, lambda_vector expr
, int size
,
250 for (i
= 0; i
< size
; i
++)
257 fprintf (outfile
, "-");
260 else if (expr
[i
] > 0)
261 fprintf (outfile
, " + ");
263 fprintf (outfile
, " - ");
264 if (abs (expr
[i
]) == 1)
265 fprintf (outfile
, "%c", start
+ i
);
267 fprintf (outfile
, "%d%c", abs (expr
[i
]), start
+ i
);
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
278 print_lambda_linear_expression (FILE * outfile
,
279 lambda_linear_expression expr
,
280 int depth
, int invariants
, char start
)
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
),
288 fprintf (outfile
, " denominator: %d\n", LLE_DENOMINATOR (expr
));
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
297 print_lambda_loop (FILE * outfile
, lambda_loop loop
, int depth
,
298 int invariants
, char start
)
301 lambda_linear_expression expr
;
305 expr
= LL_LINEAR_OFFSET (loop
);
306 step
= LL_STEP (loop
);
307 fprintf (outfile
, " step size = %d \n", step
);
311 fprintf (outfile
, " linear offset: \n");
312 print_lambda_linear_expression (outfile
, expr
, depth
, invariants
,
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
);
324 /* Create a new loop nest structure with DEPTH loops, and INVARIANTS as the
325 number of invariants. */
328 lambda_loopnest_new (int depth
, int invariants
)
331 ret
= ggc_alloc (sizeof (*ret
));
333 LN_LOOPS (ret
) = ggc_alloc_cleared (depth
* sizeof (lambda_loop
));
334 LN_DEPTH (ret
) = depth
;
335 LN_INVARIANTS (ret
) = invariants
;
340 /* Print a lambda loopnest structure, NEST, to OUTFILE. The starting
341 character to use for loop names is given by START. */
344 print_lambda_loopnest (FILE * outfile
, lambda_loopnest nest
, char start
)
347 for (i
= 0; i
< LN_DEPTH (nest
); i
++)
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");
356 /* Allocate a new lattice structure of DEPTH x DEPTH, with INVARIANTS number
359 static lambda_lattice
360 lambda_lattice_new (int depth
, int invariants
)
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
;
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. */
379 static lambda_lattice
380 lambda_lattice_compute_base (lambda_loopnest nest
)
383 int depth
, invariants
;
388 lambda_linear_expression expression
;
390 depth
= LN_DEPTH (nest
);
391 invariants
= LN_INVARIANTS (nest
);
393 ret
= lambda_lattice_new (depth
, invariants
);
394 base
= LATTICE_BASE (ret
);
395 for (i
= 0; i
< depth
; i
++)
397 loop
= LN_LOOPS (nest
)[i
];
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. */
404 for (j
= 0; j
< depth
; j
++)
407 LATTICE_ORIGIN (ret
)[i
] = 0;
408 for (j
= 0; j
< invariants
; j
++)
409 LATTICE_ORIGIN_INVARIANTS (ret
)[i
][j
] = 0;
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);
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
]);
425 for (j
= i
+ 1; j
< depth
; j
++)
428 /* Origin for this loop is the constant of the lower bound
430 LATTICE_ORIGIN (ret
)[i
] = LLE_CONSTANT (expression
);
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
];
442 /* Compute the least common multiple of two numbers A and B . */
445 least_common_multiple (int a
, int b
)
447 return (abs (a
) * abs (b
) / gcd (a
, b
));
450 /* Perform Fourier-Motzkin elimination to calculate the bounds of the
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.
465 In our case, each time we eliminate, we construct part of the bound from
466 the ith variable, then delete the ith variable.
468 Remember the constant are in our vector a, our coefficient matrix is A,
469 and our invariant coefficient matrix is B.
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. */
477 static lambda_loopnest
478 compute_nest_using_fourier_motzkin (int size
,
486 int multiple
, f1
, f2
;
488 lambda_linear_expression expression
;
490 lambda_loopnest auxillary_nest
;
491 lambda_matrix swapmatrix
, A1
, B1
;
492 lambda_vector swapvector
, a1
;
495 A1
= lambda_matrix_new (128, depth
);
496 B1
= lambda_matrix_new (128, invariants
);
497 a1
= lambda_vector_new (128);
499 auxillary_nest
= lambda_loopnest_new (depth
, invariants
);
501 for (i
= depth
- 1; i
>= 0; i
--)
503 loop
= lambda_loop_new ();
504 LN_LOOPS (auxillary_nest
)[i
] = loop
;
507 for (j
= 0; j
< size
; j
++)
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
);
515 for (k
= 0; k
< i
; k
++)
516 LLE_COEFFICIENTS (expression
)[k
] = A
[j
][k
];
518 for (k
= 0; k
< invariants
; k
++)
519 LLE_INVARIANT_COEFFICIENTS (expression
)[k
] = -1 * B
[j
][k
];
521 LLE_DENOMINATOR (expression
) = -1 * A
[j
][i
];
522 LLE_CONSTANT (expression
) = -1 * a
[j
];
524 /* Ignore if identical to the existing lower bound. */
525 if (!lle_equal (LL_LOWER_BOUND (loop
),
526 expression
, depth
, invariants
))
528 LLE_NEXT (expression
) = LL_LOWER_BOUND (loop
);
529 LL_LOWER_BOUND (loop
) = expression
;
533 else if (A
[j
][i
] > 0)
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
];
541 for (k
= 0; k
< invariants
; k
++)
542 LLE_INVARIANT_COEFFICIENTS (expression
)[k
] = B
[j
][k
];
544 LLE_DENOMINATOR (expression
) = A
[j
][i
];
545 LLE_CONSTANT (expression
) = a
[j
];
547 /* Ignore if identical to the existing upper bound. */
548 if (!lle_equal (LL_UPPER_BOUND (loop
),
549 expression
, depth
, invariants
))
551 LLE_NEXT (expression
) = LL_UPPER_BOUND (loop
);
552 LL_UPPER_BOUND (loop
) = expression
;
558 /* This portion creates a new system of linear inequalities by deleting
559 the i'th variable, reducing the system by one variable. */
561 for (j
= 0; j
< size
; j
++)
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. */
568 lambda_vector_copy (A
[j
], A1
[newsize
], depth
);
569 lambda_vector_copy (B
[j
], B1
[newsize
], invariants
);
573 else if (A
[j
][i
] > 0)
575 for (k
= 0; k
< size
; k
++)
579 multiple
= least_common_multiple (A
[j
][i
], A
[k
][i
]);
580 f1
= multiple
/ A
[j
][i
];
581 f2
= -1 * multiple
/ A
[k
][i
];
583 lambda_vector_add_mc (A
[j
], f1
, A
[k
], f2
,
585 lambda_vector_add_mc (B
[j
], f1
, B
[k
], f2
,
586 B1
[newsize
], invariants
);
587 a1
[newsize
] = f1
* a
[j
] + f2
* a
[k
];
609 return auxillary_nest
;
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
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
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. */
627 static lambda_loopnest
628 lambda_compute_auxillary_space (lambda_loopnest nest
,
629 lambda_trans_matrix trans
)
631 lambda_matrix A
, B
, A1
, B1
;
633 lambda_matrix invertedtrans
;
634 int depth
, invariants
, size
;
637 lambda_linear_expression expression
;
638 lambda_lattice lattice
;
640 depth
= LN_DEPTH (nest
);
641 invariants
= LN_INVARIANTS (nest
);
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);
650 A1
= lambda_matrix_new (128, depth
);
651 B1
= lambda_matrix_new (128, invariants
);
652 a1
= lambda_vector_new (128);
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. */
659 for (i
= 0; i
< depth
; i
++)
661 loop
= LN_LOOPS (nest
)[i
];
663 /* First we do the lower bound. */
664 if (LL_STEP (loop
) > 0)
665 expression
= LL_LOWER_BOUND (loop
);
667 expression
= LL_UPPER_BOUND (loop
);
669 for (; expression
!= NULL
; expression
= LLE_NEXT (expression
))
671 /* Fill in the coefficient. */
672 for (j
= 0; j
< i
; j
++)
673 A
[size
][j
] = LLE_COEFFICIENTS (expression
)[j
];
675 /* And the invariant coefficient. */
676 for (j
= 0; j
< invariants
; j
++)
677 B
[size
][j
] = LLE_INVARIANT_COEFFICIENTS (expression
)[j
];
679 /* And the constant. */
680 a
[size
] = LLE_CONSTANT (expression
);
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
);
686 for (j
= 0; j
< invariants
; j
++)
690 /* Need to increase matrix sizes above. */
691 gcc_assert (size
<= 127);
695 /* Then do the exact same thing for the upper bounds. */
696 if (LL_STEP (loop
) > 0)
697 expression
= LL_UPPER_BOUND (loop
);
699 expression
= LL_LOWER_BOUND (loop
);
701 for (; expression
!= NULL
; expression
= LLE_NEXT (expression
))
703 /* Fill in the coefficient. */
704 for (j
= 0; j
< i
; j
++)
705 A
[size
][j
] = LLE_COEFFICIENTS (expression
)[j
];
707 /* And the invariant coefficient. */
708 for (j
= 0; j
< invariants
; j
++)
709 B
[size
][j
] = LLE_INVARIANT_COEFFICIENTS (expression
)[j
];
711 /* And the constant. */
712 a
[size
] = LLE_CONSTANT (expression
);
714 /* Convert z <= (2x+3y+2+b)/4 to -2x-3y+4z <= 2+b. */
715 for (j
= 0; j
< i
; j
++)
717 A
[size
][i
] = LLE_DENOMINATOR (expression
);
719 /* Need to increase matrix sizes above. */
720 gcc_assert (size
<= 127);
725 /* Compute the lattice base x = base * y + origin, where y is the
727 lattice
= lambda_lattice_compute_base (nest
);
729 /* Ax <= a + B then becomes ALy <= a+B - A*origin. L is the lattice base */
732 lambda_matrix_mult (A
, LATTICE_BASE (lattice
), A1
, size
, depth
, depth
);
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
);
738 /* B1 = B - A * origin invariant. */
739 lambda_matrix_mult (A
, LATTICE_ORIGIN_INVARIANTS (lattice
), B1
, size
, depth
,
741 lambda_matrix_add_mc (B
, 1, B1
, -1, B1
, size
, invariants
);
743 /* Now compute the auxiliary space bounds by first inverting U, multiplying
744 it by A1, then performing Fourier-Motzkin. */
746 invertedtrans
= lambda_matrix_new (depth
, depth
);
748 /* Compute the inverse of U. */
749 lambda_matrix_inverse (LTM_MATRIX (trans
),
750 invertedtrans
, depth
);
753 lambda_matrix_mult (A1
, invertedtrans
, A
, size
, depth
, depth
);
755 return compute_nest_using_fourier_motzkin (size
, depth
, invariants
,
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. */
767 static lambda_loopnest
768 lambda_compute_target_space (lambda_loopnest auxillary_nest
,
769 lambda_trans_matrix H
, lambda_vector stepsigns
)
771 lambda_matrix inverse
, H1
;
772 int determinant
, i
, j
;
776 lambda_loopnest target_nest
;
777 int depth
, invariants
;
778 lambda_matrix target
;
780 lambda_loop auxillary_loop
, target_loop
;
781 lambda_linear_expression expression
, auxillary_expr
, target_expr
, tmp_expr
;
783 depth
= LN_DEPTH (auxillary_nest
);
784 invariants
= LN_INVARIANTS (auxillary_nest
);
786 inverse
= lambda_matrix_new (depth
, depth
);
787 determinant
= lambda_matrix_inverse (LTM_MATRIX (H
), inverse
, depth
);
789 /* H1 is H excluding its diagonal. */
790 H1
= lambda_matrix_new (depth
, depth
);
791 lambda_matrix_copy (LTM_MATRIX (H
), H1
, depth
, depth
);
793 for (i
= 0; i
< depth
; i
++)
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
);
800 target_nest
= lambda_loopnest_new (depth
, invariants
);
802 for (i
= 0; i
< depth
; i
++)
805 /* Get a new loop structure. */
806 target_loop
= lambda_loop_new ();
807 LN_LOOPS (target_nest
)[i
] = target_loop
;
809 /* Computes the gcd of the coefficients of the linear part. */
810 gcd1
= lambda_vector_gcd (target
[i
], i
);
812 /* Include the denominator in the GCD. */
813 gcd1
= gcd (gcd1
, determinant
);
815 /* Now divide through by the gcd. */
816 for (j
= 0; j
< i
; j
++)
817 target
[i
][j
] = target
[i
][j
] / gcd1
;
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
),
825 LL_LINEAR_OFFSET (target_loop
) = expression
;
828 /* For each loop, compute the new bounds from H. */
829 for (i
= 0; i
< depth
; i
++)
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
];
836 /* First we do the lower bound. */
837 auxillary_expr
= LL_LOWER_BOUND (auxillary_loop
);
839 for (; auxillary_expr
!= NULL
;
840 auxillary_expr
= LLE_NEXT (auxillary_expr
))
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
,
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
),
854 lambda_vector_mult_const (LLE_INVARIANT_COEFFICIENTS (target_expr
),
855 LLE_INVARIANT_COEFFICIENTS (target_expr
),
857 LLE_DENOMINATOR (target_expr
) = LLE_DENOMINATOR (auxillary_expr
);
859 if (!lambda_vector_zerop (LLE_COEFFICIENTS (target_expr
), depth
))
861 LLE_CONSTANT (target_expr
) = LLE_CONSTANT (target_expr
)
863 lambda_vector_mult_const (LLE_INVARIANT_COEFFICIENTS
865 LLE_INVARIANT_COEFFICIENTS
866 (target_expr
), invariants
,
868 LLE_DENOMINATOR (target_expr
) =
869 LLE_DENOMINATOR (target_expr
) * determinant
;
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
),
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
,
889 LLE_NEXT (target_expr
) = LL_LOWER_BOUND (target_loop
);
890 LL_LOWER_BOUND (target_loop
) = target_expr
;
893 /* Now do the upper bound. */
894 auxillary_expr
= LL_UPPER_BOUND (auxillary_loop
);
896 for (; auxillary_expr
!= NULL
;
897 auxillary_expr
= LLE_NEXT (auxillary_expr
))
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
,
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
),
910 lambda_vector_mult_const (LLE_INVARIANT_COEFFICIENTS (target_expr
),
911 LLE_INVARIANT_COEFFICIENTS (target_expr
),
913 LLE_DENOMINATOR (target_expr
) = LLE_DENOMINATOR (auxillary_expr
);
915 if (!lambda_vector_zerop (LLE_COEFFICIENTS (target_expr
), depth
))
917 LLE_CONSTANT (target_expr
) = LLE_CONSTANT (target_expr
)
919 lambda_vector_mult_const (LLE_INVARIANT_COEFFICIENTS
921 LLE_INVARIANT_COEFFICIENTS
922 (target_expr
), invariants
,
924 LLE_DENOMINATOR (target_expr
) =
925 LLE_DENOMINATOR (target_expr
) * determinant
;
927 /* Find the gcd and divide by it here, instead of at the
929 gcd1
= lambda_vector_gcd (LLE_COEFFICIENTS (target_expr
), depth
);
930 gcd2
= lambda_vector_gcd (LLE_INVARIANT_COEFFICIENTS (target_expr
),
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
,
945 LLE_NEXT (target_expr
) = LL_UPPER_BOUND (target_loop
);
946 LL_UPPER_BOUND (target_loop
) = target_expr
;
950 for (i
= 0; i
< depth
; i
++)
952 target_loop
= LN_LOOPS (target_nest
)[i
];
953 /* If necessary, exchange the upper and lower bounds and negate
955 if (stepsigns
[i
] < 0)
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
;
966 /* Compute the step signs of TRANS, using TRANS and stepsigns. Return the new
970 lambda_compute_step_signs (lambda_trans_matrix trans
, lambda_vector stepsigns
)
972 lambda_matrix matrix
, H
;
974 lambda_vector newsteps
;
975 int i
, j
, factor
, minimum_column
;
978 matrix
= LTM_MATRIX (trans
);
979 size
= LTM_ROWSIZE (trans
);
980 H
= lambda_matrix_new (size
, size
);
982 newsteps
= lambda_vector_new (size
);
983 lambda_vector_copy (stepsigns
, newsteps
, size
);
985 lambda_matrix_copy (matrix
, H
, size
, size
);
987 for (j
= 0; j
< size
; j
++)
991 for (i
= j
; i
< size
; i
++)
993 lambda_matrix_col_negate (H
, size
, i
);
994 while (lambda_vector_first_nz (row
, size
, j
+ 1) < size
)
996 minimum_column
= lambda_vector_min_nz (row
, size
, j
);
997 lambda_matrix_col_exchange (H
, size
, j
, minimum_column
);
1000 newsteps
[j
] = newsteps
[minimum_column
];
1001 newsteps
[minimum_column
] = temp
;
1003 for (i
= j
+ 1; i
< size
; i
++)
1005 factor
= row
[i
] / row
[j
];
1006 lambda_matrix_col_add (H
, size
, j
, i
, -1 * factor
);
1013 /* Transform NEST according to TRANS, and return the new loopnest.
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. */
1024 lambda_loopnest_transform (lambda_loopnest nest
, lambda_trans_matrix trans
)
1026 lambda_loopnest auxillary_nest
, target_nest
;
1028 int depth
, invariants
;
1030 lambda_lattice lattice
;
1031 lambda_trans_matrix trans1
, H
, U
;
1033 lambda_linear_expression expression
;
1034 lambda_vector origin
;
1035 lambda_matrix origin_invariants
;
1036 lambda_vector stepsigns
;
1039 depth
= LN_DEPTH (nest
);
1040 invariants
= LN_INVARIANTS (nest
);
1042 /* Keep track of the signs of the loop steps. */
1043 stepsigns
= lambda_vector_new (depth
);
1044 for (i
= 0; i
< depth
; i
++)
1046 if (LL_STEP (LN_LOOPS (nest
)[i
]) > 0)
1052 /* Compute the lattice base. */
1053 lattice
= lambda_lattice_compute_base (nest
);
1054 trans1
= lambda_trans_matrix_new (depth
, depth
);
1056 /* Multiply the transformation matrix by the lattice base. */
1058 lambda_matrix_mult (LTM_MATRIX (trans
), LATTICE_BASE (lattice
),
1059 LTM_MATRIX (trans1
), depth
, depth
, depth
);
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
),
1067 /* Compute the auxiliary loop nest's space from the unimodular
1069 auxillary_nest
= lambda_compute_auxillary_space (nest
, U
);
1071 /* Compute the loop step signs from the old step signs and the
1072 transformation matrix. */
1073 stepsigns
= lambda_compute_step_signs (trans1
, stepsigns
);
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
);
1085 for (i
= 0; i
< depth
; i
++)
1087 loop
= LN_LOOPS (target_nest
)[i
];
1088 expression
= LL_LINEAR_OFFSET (loop
);
1089 if (lambda_vector_zerop (LLE_COEFFICIENTS (expression
), depth
))
1092 f
= LLE_DENOMINATOR (expression
);
1094 LLE_CONSTANT (expression
) += f
* origin
[i
];
1096 for (j
= 0; j
< invariants
; j
++)
1097 LLE_INVARIANT_COEFFICIENTS (expression
)[j
] +=
1098 f
* origin_invariants
[i
][j
];
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. */
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
)
1117 lambda_linear_expression lle
= NULL
;
1118 switch (TREE_CODE (expr
))
1122 lle
= lambda_linear_expression_new (depth
, 2 * depth
);
1123 LLE_CONSTANT (lle
) = TREE_INT_CST_LOW (expr
);
1125 LLE_CONSTANT (lle
) += extra
;
1127 LLE_DENOMINATOR (lle
) = 1;
1134 for (i
= 0; VEC_iterate (tree
, outerinductionvars
, i
, iv
); i
++)
1137 if (SSA_NAME_VAR (iv
) == SSA_NAME_VAR (expr
))
1139 lle
= lambda_linear_expression_new (depth
, 2 * depth
);
1140 LLE_COEFFICIENTS (lle
)[i
] = 1;
1142 LLE_CONSTANT (lle
) = extra
;
1144 LLE_DENOMINATOR (lle
) = 1;
1147 for (i
= 0; VEC_iterate (tree
, invariants
, i
, invar
); i
++)
1150 if (SSA_NAME_VAR (invar
) == SSA_NAME_VAR (expr
))
1152 lle
= lambda_linear_expression_new (depth
, 2 * depth
);
1153 LLE_INVARIANT_COEFFICIENTS (lle
)[i
] = 1;
1155 LLE_CONSTANT (lle
) = extra
;
1156 LLE_DENOMINATOR (lle
) = 1;
1168 /* Return the depth of the loopnest NEST */
1171 depth_of_nest (struct loop
*nest
)
1183 /* Return true if OP is invariant in LOOP and all outer loops. */
1186 invariant_in_loop_and_outer_loops (struct loop
*loop
, tree op
)
1188 if (is_gimple_min_invariant (op
))
1190 if (loop
->depth
== 0)
1192 if (!expr_invariant_in_loop_p (loop
, op
))
1195 && !invariant_in_loop_and_outer_loops (loop
->outer
, op
))
1200 /* Generate a lambda loop from a gcc loop LOOP. Return the new lambda loop,
1201 or NULL if it could not be converted.
1202 DEPTH is the depth of the loop.
1203 INVARIANTS is a pointer to the array of loop invariants.
1204 The induction variable for this loop should be stored in the parameter
1206 OUTERINDUCTIONVARS is an array of induction variables for outer loops. */
1209 gcc_loop_to_lambda_loop (struct loop
*loop
, int depth
,
1210 VEC(tree
,heap
) ** invariants
,
1211 tree
* ourinductionvar
,
1212 VEC(tree
,heap
) * outerinductionvars
,
1213 VEC(tree
,heap
) ** lboundvars
,
1214 VEC(tree
,heap
) ** uboundvars
,
1215 VEC(int,heap
) ** steps
)
1219 tree access_fn
, inductionvar
;
1221 lambda_loop lloop
= NULL
;
1222 lambda_linear_expression lbound
, ubound
;
1226 tree lboundvar
, uboundvar
, uboundresult
;
1228 /* Find out induction var and exit condition. */
1229 inductionvar
= find_induction_var_from_exit_cond (loop
);
1230 exit_cond
= get_loop_exit_condition (loop
);
1232 if (inductionvar
== NULL
|| exit_cond
== NULL
)
1234 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1236 "Unable to convert loop: Cannot determine exit condition or induction variable for loop.\n");
1240 test
= TREE_OPERAND (exit_cond
, 0);
1242 if (SSA_NAME_DEF_STMT (inductionvar
) == NULL_TREE
)
1245 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1247 "Unable to convert loop: Cannot find PHI node for induction variable\n");
1252 phi
= SSA_NAME_DEF_STMT (inductionvar
);
1253 if (TREE_CODE (phi
) != PHI_NODE
)
1255 phi
= SINGLE_SSA_TREE_OPERAND (phi
, SSA_OP_USE
);
1259 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1261 "Unable to convert loop: Cannot find PHI node for induction variable\n");
1266 phi
= SSA_NAME_DEF_STMT (phi
);
1267 if (TREE_CODE (phi
) != PHI_NODE
)
1270 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1272 "Unable to convert loop: Cannot find PHI node for induction variable\n");
1278 /* The induction variable name/version we want to put in the array is the
1279 result of the induction variable phi node. */
1280 *ourinductionvar
= PHI_RESULT (phi
);
1281 access_fn
= instantiate_parameters
1282 (loop
, analyze_scalar_evolution (loop
, PHI_RESULT (phi
)));
1283 if (access_fn
== chrec_dont_know
)
1285 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1287 "Unable to convert loop: Access function for induction variable phi is unknown\n");
1292 step
= evolution_part_in_loop_num (access_fn
, loop
->num
);
1293 if (!step
|| step
== chrec_dont_know
)
1295 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1297 "Unable to convert loop: Cannot determine step of loop.\n");
1301 if (TREE_CODE (step
) != INTEGER_CST
)
1304 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1306 "Unable to convert loop: Step of loop is not integer.\n");
1310 stepint
= TREE_INT_CST_LOW (step
);
1312 /* Only want phis for induction vars, which will have two
1314 if (PHI_NUM_ARGS (phi
) != 2)
1316 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1318 "Unable to convert loop: PHI node for induction variable has >2 arguments\n");
1322 /* Another induction variable check. One argument's source should be
1323 in the loop, one outside the loop. */
1324 if (flow_bb_inside_loop_p (loop
, PHI_ARG_EDGE (phi
, 0)->src
)
1325 && flow_bb_inside_loop_p (loop
, PHI_ARG_EDGE (phi
, 1)->src
))
1328 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1330 "Unable to convert loop: PHI edges both inside loop, or both outside loop.\n");
1335 if (flow_bb_inside_loop_p (loop
, PHI_ARG_EDGE (phi
, 0)->src
))
1337 lboundvar
= PHI_ARG_DEF (phi
, 1);
1338 lbound
= gcc_tree_to_linear_expression (depth
, lboundvar
,
1339 outerinductionvars
, *invariants
,
1344 lboundvar
= PHI_ARG_DEF (phi
, 0);
1345 lbound
= gcc_tree_to_linear_expression (depth
, lboundvar
,
1346 outerinductionvars
, *invariants
,
1353 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1355 "Unable to convert loop: Cannot convert lower bound to linear expression\n");
1359 /* One part of the test may be a loop invariant tree. */
1360 VEC_reserve (tree
, heap
, *invariants
, 1);
1361 if (TREE_CODE (TREE_OPERAND (test
, 1)) == SSA_NAME
1362 && invariant_in_loop_and_outer_loops (loop
, TREE_OPERAND (test
, 1)))
1363 VEC_quick_push (tree
, *invariants
, TREE_OPERAND (test
, 1));
1364 else if (TREE_CODE (TREE_OPERAND (test
, 0)) == SSA_NAME
1365 && invariant_in_loop_and_outer_loops (loop
, TREE_OPERAND (test
, 0)))
1366 VEC_quick_push (tree
, *invariants
, TREE_OPERAND (test
, 0));
1368 /* The non-induction variable part of the test is the upper bound variable.
1370 if (TREE_OPERAND (test
, 0) == inductionvar
)
1371 uboundvar
= TREE_OPERAND (test
, 1);
1373 uboundvar
= TREE_OPERAND (test
, 0);
1376 /* We only size the vectors assuming we have, at max, 2 times as many
1377 invariants as we do loops (one for each bound).
1378 This is just an arbitrary number, but it has to be matched against the
1380 gcc_assert (VEC_length (tree
, *invariants
) <= (unsigned int) (2 * depth
));
1383 /* We might have some leftover. */
1384 if (TREE_CODE (test
) == LT_EXPR
)
1385 extra
= -1 * stepint
;
1386 else if (TREE_CODE (test
) == NE_EXPR
)
1387 extra
= -1 * stepint
;
1388 else if (TREE_CODE (test
) == GT_EXPR
)
1389 extra
= -1 * stepint
;
1390 else if (TREE_CODE (test
) == EQ_EXPR
)
1391 extra
= 1 * stepint
;
1393 ubound
= gcc_tree_to_linear_expression (depth
, uboundvar
,
1395 *invariants
, extra
);
1396 uboundresult
= build2 (PLUS_EXPR
, TREE_TYPE (uboundvar
), uboundvar
,
1397 build_int_cst (TREE_TYPE (uboundvar
), extra
));
1398 VEC_safe_push (tree
, heap
, *uboundvars
, uboundresult
);
1399 VEC_safe_push (tree
, heap
, *lboundvars
, lboundvar
);
1400 VEC_safe_push (int, heap
, *steps
, stepint
);
1403 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1405 "Unable to convert loop: Cannot convert upper bound to linear expression\n");
1409 lloop
= lambda_loop_new ();
1410 LL_STEP (lloop
) = stepint
;
1411 LL_LOWER_BOUND (lloop
) = lbound
;
1412 LL_UPPER_BOUND (lloop
) = ubound
;
1416 /* Given a LOOP, find the induction variable it is testing against in the exit
1417 condition. Return the induction variable if found, NULL otherwise. */
1420 find_induction_var_from_exit_cond (struct loop
*loop
)
1422 tree expr
= get_loop_exit_condition (loop
);
1425 if (expr
== NULL_TREE
)
1427 if (TREE_CODE (expr
) != COND_EXPR
)
1429 test
= TREE_OPERAND (expr
, 0);
1430 if (!COMPARISON_CLASS_P (test
))
1433 /* Find the side that is invariant in this loop. The ivar must be the other
1436 if (expr_invariant_in_loop_p (loop
, TREE_OPERAND (test
, 0)))
1437 ivarop
= TREE_OPERAND (test
, 1);
1438 else if (expr_invariant_in_loop_p (loop
, TREE_OPERAND (test
, 1)))
1439 ivarop
= TREE_OPERAND (test
, 0);
1443 if (TREE_CODE (ivarop
) != SSA_NAME
)
1448 DEF_VEC_P(lambda_loop
);
1449 DEF_VEC_ALLOC_P(lambda_loop
,heap
);
1451 /* Generate a lambda loopnest from a gcc loopnest LOOP_NEST.
1452 Return the new loop nest.
1453 INDUCTIONVARS is a pointer to an array of induction variables for the
1454 loopnest that will be filled in during this process.
1455 INVARIANTS is a pointer to an array of invariants that will be filled in
1456 during this process. */
1459 gcc_loopnest_to_lambda_loopnest (struct loop
*loop_nest
,
1460 VEC(tree
,heap
) **inductionvars
,
1461 VEC(tree
,heap
) **invariants
)
1463 lambda_loopnest ret
= NULL
;
1464 struct loop
*temp
= loop_nest
;
1465 int depth
= depth_of_nest (loop_nest
);
1467 VEC(lambda_loop
,heap
) *loops
= NULL
;
1468 VEC(tree
,heap
) *uboundvars
= NULL
;
1469 VEC(tree
,heap
) *lboundvars
= NULL
;
1470 VEC(int,heap
) *steps
= NULL
;
1471 lambda_loop newloop
;
1472 tree inductionvar
= NULL
;
1473 bool perfect_nest
= perfect_nest_p (loop_nest
);
1475 if (!perfect_nest
&& !can_convert_to_perfect_nest (loop_nest
))
1480 newloop
= gcc_loop_to_lambda_loop (temp
, depth
, invariants
,
1481 &inductionvar
, *inductionvars
,
1482 &lboundvars
, &uboundvars
,
1487 VEC_safe_push (tree
, heap
, *inductionvars
, inductionvar
);
1488 VEC_safe_push (lambda_loop
, heap
, loops
, newloop
);
1494 if (!perfect_nestify (loop_nest
, lboundvars
, uboundvars
, steps
,
1499 "Not a perfect loop nest and couldn't convert to one.\n");
1504 "Successfully converted loop nest to perfect loop nest.\n");
1507 ret
= lambda_loopnest_new (depth
, 2 * depth
);
1509 for (i
= 0; VEC_iterate (lambda_loop
, loops
, i
, newloop
); i
++)
1510 LN_LOOPS (ret
)[i
] = newloop
;
1513 VEC_free (lambda_loop
, heap
, loops
);
1514 VEC_free (tree
, heap
, uboundvars
);
1515 VEC_free (tree
, heap
, lboundvars
);
1516 VEC_free (int, heap
, steps
);
1521 /* Convert a lambda body vector LBV to a gcc tree, and return the new tree.
1522 STMTS_TO_INSERT is a pointer to a tree where the statements we need to be
1523 inserted for us are stored. INDUCTION_VARS is the array of induction
1524 variables for the loop this LBV is from. TYPE is the tree type to use for
1525 the variables and trees involved. */
1528 lbv_to_gcc_expression (lambda_body_vector lbv
,
1529 tree type
, VEC(tree
,heap
) *induction_vars
,
1530 tree
*stmts_to_insert
)
1532 tree stmts
, stmt
, resvar
, name
;
1535 tree_stmt_iterator tsi
;
1537 /* Create a statement list and a linear expression temporary. */
1538 stmts
= alloc_stmt_list ();
1539 resvar
= create_tmp_var (type
, "lbvtmp");
1540 add_referenced_var (resvar
);
1543 stmt
= build2 (MODIFY_EXPR
, void_type_node
, resvar
, integer_zero_node
);
1544 name
= make_ssa_name (resvar
, stmt
);
1545 TREE_OPERAND (stmt
, 0) = name
;
1546 tsi
= tsi_last (stmts
);
1547 tsi_link_after (&tsi
, stmt
, TSI_CONTINUE_LINKING
);
1549 for (i
= 0; VEC_iterate (tree
, induction_vars
, i
, iv
); i
++)
1551 if (LBV_COEFFICIENTS (lbv
)[i
] != 0)
1556 /* newname = coefficient * induction_variable */
1557 coeffmult
= build_int_cst (type
, LBV_COEFFICIENTS (lbv
)[i
]);
1558 stmt
= build2 (MODIFY_EXPR
, void_type_node
, resvar
,
1559 fold_build2 (MULT_EXPR
, type
, iv
, coeffmult
));
1561 newname
= make_ssa_name (resvar
, stmt
);
1562 TREE_OPERAND (stmt
, 0) = newname
;
1564 tsi
= tsi_last (stmts
);
1565 tsi_link_after (&tsi
, stmt
, TSI_CONTINUE_LINKING
);
1567 /* name = name + newname */
1568 stmt
= build2 (MODIFY_EXPR
, void_type_node
, resvar
,
1569 build2 (PLUS_EXPR
, type
, name
, newname
));
1570 name
= make_ssa_name (resvar
, stmt
);
1571 TREE_OPERAND (stmt
, 0) = name
;
1573 tsi
= tsi_last (stmts
);
1574 tsi_link_after (&tsi
, stmt
, TSI_CONTINUE_LINKING
);
1579 /* Handle any denominator that occurs. */
1580 if (LBV_DENOMINATOR (lbv
) != 1)
1582 tree denominator
= build_int_cst (type
, LBV_DENOMINATOR (lbv
));
1583 stmt
= build2 (MODIFY_EXPR
, void_type_node
, resvar
,
1584 build2 (CEIL_DIV_EXPR
, type
, name
, denominator
));
1585 name
= make_ssa_name (resvar
, stmt
);
1586 TREE_OPERAND (stmt
, 0) = name
;
1588 tsi
= tsi_last (stmts
);
1589 tsi_link_after (&tsi
, stmt
, TSI_CONTINUE_LINKING
);
1591 *stmts_to_insert
= stmts
;
1595 /* Convert a linear expression from coefficient and constant form to a
1597 Return the tree that represents the final value of the expression.
1598 LLE is the linear expression to convert.
1599 OFFSET is the linear offset to apply to the expression.
1600 TYPE is the tree type to use for the variables and math.
1601 INDUCTION_VARS is a vector of induction variables for the loops.
1602 INVARIANTS is a vector of the loop nest invariants.
1603 WRAP specifies what tree code to wrap the results in, if there is more than
1604 one (it is either MAX_EXPR, or MIN_EXPR).
1605 STMTS_TO_INSERT Is a pointer to the statement list we fill in with
1606 statements that need to be inserted for the linear expression. */
1609 lle_to_gcc_expression (lambda_linear_expression lle
,
1610 lambda_linear_expression offset
,
1612 VEC(tree
,heap
) *induction_vars
,
1613 VEC(tree
,heap
) *invariants
,
1614 enum tree_code wrap
, tree
*stmts_to_insert
)
1616 tree stmts
, stmt
, resvar
, name
;
1618 tree_stmt_iterator tsi
;
1620 VEC(tree
,heap
) *results
= NULL
;
1622 gcc_assert (wrap
== MAX_EXPR
|| wrap
== MIN_EXPR
);
1624 /* Create a statement list and a linear expression temporary. */
1625 stmts
= alloc_stmt_list ();
1626 resvar
= create_tmp_var (type
, "lletmp");
1627 add_referenced_var (resvar
);
1629 /* Build up the linear expressions, and put the variable representing the
1630 result in the results array. */
1631 for (; lle
!= NULL
; lle
= LLE_NEXT (lle
))
1633 /* Start at name = 0. */
1634 stmt
= build2 (MODIFY_EXPR
, void_type_node
, resvar
, integer_zero_node
);
1635 name
= make_ssa_name (resvar
, stmt
);
1636 TREE_OPERAND (stmt
, 0) = name
;
1638 tsi
= tsi_last (stmts
);
1639 tsi_link_after (&tsi
, stmt
, TSI_CONTINUE_LINKING
);
1641 /* First do the induction variables.
1642 at the end, name = name + all the induction variables added
1644 for (i
= 0; VEC_iterate (tree
, induction_vars
, i
, iv
); i
++)
1646 if (LLE_COEFFICIENTS (lle
)[i
] != 0)
1652 /* mult = induction variable * coefficient. */
1653 if (LLE_COEFFICIENTS (lle
)[i
] == 1)
1655 mult
= VEC_index (tree
, induction_vars
, i
);
1659 coeff
= build_int_cst (type
,
1660 LLE_COEFFICIENTS (lle
)[i
]);
1661 mult
= fold_build2 (MULT_EXPR
, type
, iv
, coeff
);
1664 /* newname = mult */
1665 stmt
= build2 (MODIFY_EXPR
, void_type_node
, resvar
, mult
);
1666 newname
= make_ssa_name (resvar
, stmt
);
1667 TREE_OPERAND (stmt
, 0) = newname
;
1669 tsi
= tsi_last (stmts
);
1670 tsi_link_after (&tsi
, stmt
, TSI_CONTINUE_LINKING
);
1672 /* name = name + newname */
1673 stmt
= build2 (MODIFY_EXPR
, void_type_node
, resvar
,
1674 build2 (PLUS_EXPR
, type
, name
, newname
));
1675 name
= make_ssa_name (resvar
, stmt
);
1676 TREE_OPERAND (stmt
, 0) = name
;
1678 tsi
= tsi_last (stmts
);
1679 tsi_link_after (&tsi
, stmt
, TSI_CONTINUE_LINKING
);
1683 /* Handle our invariants.
1684 At the end, we have name = name + result of adding all multiplied
1686 for (i
= 0; VEC_iterate (tree
, invariants
, i
, invar
); i
++)
1688 if (LLE_INVARIANT_COEFFICIENTS (lle
)[i
] != 0)
1693 int invcoeff
= LLE_INVARIANT_COEFFICIENTS (lle
)[i
];
1694 /* mult = invariant * coefficient */
1701 coeff
= build_int_cst (type
, invcoeff
);
1702 mult
= fold_build2 (MULT_EXPR
, type
, invar
, coeff
);
1705 /* newname = mult */
1706 stmt
= build2 (MODIFY_EXPR
, void_type_node
, resvar
, mult
);
1707 newname
= make_ssa_name (resvar
, stmt
);
1708 TREE_OPERAND (stmt
, 0) = newname
;
1710 tsi
= tsi_last (stmts
);
1711 tsi_link_after (&tsi
, stmt
, TSI_CONTINUE_LINKING
);
1713 /* name = name + newname */
1714 stmt
= build2 (MODIFY_EXPR
, void_type_node
, resvar
,
1715 build2 (PLUS_EXPR
, type
, name
, newname
));
1716 name
= make_ssa_name (resvar
, stmt
);
1717 TREE_OPERAND (stmt
, 0) = name
;
1719 tsi
= tsi_last (stmts
);
1720 tsi_link_after (&tsi
, stmt
, TSI_CONTINUE_LINKING
);
1724 /* Now handle the constant.
1725 name = name + constant. */
1726 if (LLE_CONSTANT (lle
) != 0)
1728 stmt
= build2 (MODIFY_EXPR
, void_type_node
, resvar
,
1729 build2 (PLUS_EXPR
, type
, name
,
1730 build_int_cst (type
, LLE_CONSTANT (lle
))));
1731 name
= make_ssa_name (resvar
, stmt
);
1732 TREE_OPERAND (stmt
, 0) = name
;
1734 tsi
= tsi_last (stmts
);
1735 tsi_link_after (&tsi
, stmt
, TSI_CONTINUE_LINKING
);
1738 /* Now handle the offset.
1739 name = name + linear offset. */
1740 if (LLE_CONSTANT (offset
) != 0)
1742 stmt
= build2 (MODIFY_EXPR
, void_type_node
, resvar
,
1743 build2 (PLUS_EXPR
, type
, name
,
1744 build_int_cst (type
, LLE_CONSTANT (offset
))));
1745 name
= make_ssa_name (resvar
, stmt
);
1746 TREE_OPERAND (stmt
, 0) = name
;
1748 tsi
= tsi_last (stmts
);
1749 tsi_link_after (&tsi
, stmt
, TSI_CONTINUE_LINKING
);
1752 /* Handle any denominator that occurs. */
1753 if (LLE_DENOMINATOR (lle
) != 1)
1755 stmt
= build_int_cst (type
, LLE_DENOMINATOR (lle
));
1756 stmt
= build2 (wrap
== MAX_EXPR
? CEIL_DIV_EXPR
: FLOOR_DIV_EXPR
,
1758 stmt
= build2 (MODIFY_EXPR
, void_type_node
, resvar
, stmt
);
1760 /* name = {ceil, floor}(name/denominator) */
1761 name
= make_ssa_name (resvar
, stmt
);
1762 TREE_OPERAND (stmt
, 0) = name
;
1763 tsi
= tsi_last (stmts
);
1764 tsi_link_after (&tsi
, stmt
, TSI_CONTINUE_LINKING
);
1766 VEC_safe_push (tree
, heap
, results
, name
);
1769 /* Again, out of laziness, we don't handle this case yet. It's not
1770 hard, it just hasn't occurred. */
1771 gcc_assert (VEC_length (tree
, results
) <= 2);
1773 /* We may need to wrap the results in a MAX_EXPR or MIN_EXPR. */
1774 if (VEC_length (tree
, results
) > 1)
1776 tree op1
= VEC_index (tree
, results
, 0);
1777 tree op2
= VEC_index (tree
, results
, 1);
1778 stmt
= build2 (MODIFY_EXPR
, void_type_node
, resvar
,
1779 build2 (wrap
, type
, op1
, op2
));
1780 name
= make_ssa_name (resvar
, stmt
);
1781 TREE_OPERAND (stmt
, 0) = name
;
1782 tsi
= tsi_last (stmts
);
1783 tsi_link_after (&tsi
, stmt
, TSI_CONTINUE_LINKING
);
1786 VEC_free (tree
, heap
, results
);
1788 *stmts_to_insert
= stmts
;
1792 /* Transform a lambda loopnest NEW_LOOPNEST, which had TRANSFORM applied to
1793 it, back into gcc code. This changes the
1794 loops, their induction variables, and their bodies, so that they
1795 match the transformed loopnest.
1796 OLD_LOOPNEST is the loopnest before we've replaced it with the new
1798 OLD_IVS is a vector of induction variables from the old loopnest.
1799 INVARIANTS is a vector of loop invariants from the old loopnest.
1800 NEW_LOOPNEST is the new lambda loopnest to replace OLD_LOOPNEST with.
1801 TRANSFORM is the matrix transform that was applied to OLD_LOOPNEST to get
1805 lambda_loopnest_to_gcc_loopnest (struct loop
*old_loopnest
,
1806 VEC(tree
,heap
) *old_ivs
,
1807 VEC(tree
,heap
) *invariants
,
1808 lambda_loopnest new_loopnest
,
1809 lambda_trans_matrix transform
)
1814 VEC(tree
,heap
) *new_ivs
= NULL
;
1817 block_stmt_iterator bsi
;
1821 transform
= lambda_trans_matrix_inverse (transform
);
1822 fprintf (dump_file
, "Inverse of transformation matrix:\n");
1823 print_lambda_trans_matrix (dump_file
, transform
);
1825 depth
= depth_of_nest (old_loopnest
);
1826 temp
= old_loopnest
;
1830 lambda_loop newloop
;
1833 tree ivvar
, ivvarinced
, exitcond
, stmts
;
1834 enum tree_code testtype
;
1835 tree newupperbound
, newlowerbound
;
1836 lambda_linear_expression offset
;
1841 oldiv
= VEC_index (tree
, old_ivs
, i
);
1842 type
= TREE_TYPE (oldiv
);
1844 /* First, build the new induction variable temporary */
1846 ivvar
= create_tmp_var (type
, "lnivtmp");
1847 add_referenced_var (ivvar
);
1849 VEC_safe_push (tree
, heap
, new_ivs
, ivvar
);
1851 newloop
= LN_LOOPS (new_loopnest
)[i
];
1853 /* Linear offset is a bit tricky to handle. Punt on the unhandled
1855 offset
= LL_LINEAR_OFFSET (newloop
);
1857 gcc_assert (LLE_DENOMINATOR (offset
) == 1 &&
1858 lambda_vector_zerop (LLE_COEFFICIENTS (offset
), depth
));
1860 /* Now build the new lower bounds, and insert the statements
1861 necessary to generate it on the loop preheader. */
1862 newlowerbound
= lle_to_gcc_expression (LL_LOWER_BOUND (newloop
),
1863 LL_LINEAR_OFFSET (newloop
),
1866 invariants
, MAX_EXPR
, &stmts
);
1867 bsi_insert_on_edge (loop_preheader_edge (temp
), stmts
);
1868 bsi_commit_edge_inserts ();
1869 /* Build the new upper bound and insert its statements in the
1870 basic block of the exit condition */
1871 newupperbound
= lle_to_gcc_expression (LL_UPPER_BOUND (newloop
),
1872 LL_LINEAR_OFFSET (newloop
),
1875 invariants
, MIN_EXPR
, &stmts
);
1876 exit
= single_exit (temp
);
1877 exitcond
= get_loop_exit_condition (temp
);
1878 bb
= bb_for_stmt (exitcond
);
1879 bsi
= bsi_start (bb
);
1880 bsi_insert_after (&bsi
, stmts
, BSI_NEW_STMT
);
1882 /* Create the new iv. */
1884 standard_iv_increment_position (temp
, &bsi
, &insert_after
);
1885 create_iv (newlowerbound
,
1886 build_int_cst (type
, LL_STEP (newloop
)),
1887 ivvar
, temp
, &bsi
, insert_after
, &ivvar
,
1890 /* Unfortunately, the incremented ivvar that create_iv inserted may not
1891 dominate the block containing the exit condition.
1892 So we simply create our own incremented iv to use in the new exit
1893 test, and let redundancy elimination sort it out. */
1894 inc_stmt
= build2 (PLUS_EXPR
, type
,
1895 ivvar
, build_int_cst (type
, LL_STEP (newloop
)));
1896 inc_stmt
= build2 (MODIFY_EXPR
, void_type_node
, SSA_NAME_VAR (ivvar
),
1898 ivvarinced
= make_ssa_name (SSA_NAME_VAR (ivvar
), inc_stmt
);
1899 TREE_OPERAND (inc_stmt
, 0) = ivvarinced
;
1900 bsi
= bsi_for_stmt (exitcond
);
1901 bsi_insert_before (&bsi
, inc_stmt
, BSI_SAME_STMT
);
1903 /* Replace the exit condition with the new upper bound
1906 testtype
= LL_STEP (newloop
) >= 0 ? LE_EXPR
: GE_EXPR
;
1908 /* We want to build a conditional where true means exit the loop, and
1909 false means continue the loop.
1910 So swap the testtype if this isn't the way things are.*/
1912 if (exit
->flags
& EDGE_FALSE_VALUE
)
1913 testtype
= swap_tree_comparison (testtype
);
1915 COND_EXPR_COND (exitcond
) = build2 (testtype
,
1917 newupperbound
, ivvarinced
);
1918 update_stmt (exitcond
);
1919 VEC_replace (tree
, new_ivs
, i
, ivvar
);
1925 /* Rewrite uses of the old ivs so that they are now specified in terms of
1928 for (i
= 0; VEC_iterate (tree
, old_ivs
, i
, oldiv
); i
++)
1930 imm_use_iterator imm_iter
;
1931 use_operand_p use_p
;
1933 tree oldiv_stmt
= SSA_NAME_DEF_STMT (oldiv
);
1936 if (TREE_CODE (oldiv_stmt
) == PHI_NODE
)
1937 oldiv_def
= PHI_RESULT (oldiv_stmt
);
1939 oldiv_def
= SINGLE_SSA_TREE_OPERAND (oldiv_stmt
, SSA_OP_DEF
);
1940 gcc_assert (oldiv_def
!= NULL_TREE
);
1942 FOR_EACH_IMM_USE_STMT (stmt
, imm_iter
, oldiv_def
)
1945 lambda_body_vector lbv
, newlbv
;
1947 gcc_assert (TREE_CODE (stmt
) != PHI_NODE
);
1949 /* Compute the new expression for the induction
1951 depth
= VEC_length (tree
, new_ivs
);
1952 lbv
= lambda_body_vector_new (depth
);
1953 LBV_COEFFICIENTS (lbv
)[i
] = 1;
1955 newlbv
= lambda_body_vector_compute_new (transform
, lbv
);
1957 newiv
= lbv_to_gcc_expression (newlbv
, TREE_TYPE (oldiv
),
1959 bsi
= bsi_for_stmt (stmt
);
1960 /* Insert the statements to build that
1962 bsi_insert_before (&bsi
, stmts
, BSI_SAME_STMT
);
1964 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
1965 propagate_value (use_p
, newiv
);
1969 VEC_free (tree
, heap
, new_ivs
);
1972 /* Return TRUE if this is not interesting statement from the perspective of
1973 determining if we have a perfect loop nest. */
1976 not_interesting_stmt (tree stmt
)
1978 /* Note that COND_EXPR's aren't interesting because if they were exiting the
1979 loop, we would have already failed the number of exits tests. */
1980 if (TREE_CODE (stmt
) == LABEL_EXPR
1981 || TREE_CODE (stmt
) == GOTO_EXPR
1982 || TREE_CODE (stmt
) == COND_EXPR
)
1987 /* Return TRUE if PHI uses DEF for it's in-the-loop edge for LOOP. */
1990 phi_loop_edge_uses_def (struct loop
*loop
, tree phi
, tree def
)
1993 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
1994 if (flow_bb_inside_loop_p (loop
, PHI_ARG_EDGE (phi
, i
)->src
))
1995 if (PHI_ARG_DEF (phi
, i
) == def
)
2000 /* Return TRUE if STMT is a use of PHI_RESULT. */
2003 stmt_uses_phi_result (tree stmt
, tree phi_result
)
2005 tree use
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
2007 /* This is conservatively true, because we only want SIMPLE bumpers
2008 of the form x +- constant for our pass. */
2009 return (use
== phi_result
);
2012 /* STMT is a bumper stmt for LOOP if the version it defines is used in the
2013 in-loop-edge in a phi node, and the operand it uses is the result of that
2016 i_3 = PHI (0, i_29); */
2019 stmt_is_bumper_for_loop (struct loop
*loop
, tree stmt
)
2023 imm_use_iterator iter
;
2024 use_operand_p use_p
;
2026 def
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_DEF
);
2030 FOR_EACH_IMM_USE_FAST (use_p
, iter
, def
)
2032 use
= USE_STMT (use_p
);
2033 if (TREE_CODE (use
) == PHI_NODE
)
2035 if (phi_loop_edge_uses_def (loop
, use
, def
))
2036 if (stmt_uses_phi_result (stmt
, PHI_RESULT (use
)))
2044 /* Return true if LOOP is a perfect loop nest.
2045 Perfect loop nests are those loop nests where all code occurs in the
2046 innermost loop body.
2047 If S is a program statement, then
2056 is not a perfect loop nest because of S1.
2064 is a perfect loop nest.
2066 Since we don't have high level loops anymore, we basically have to walk our
2067 statements and ignore those that are there because the loop needs them (IE
2068 the induction variable increment, and jump back to the top of the loop). */
2071 perfect_nest_p (struct loop
*loop
)
2079 bbs
= get_loop_body (loop
);
2080 exit_cond
= get_loop_exit_condition (loop
);
2081 for (i
= 0; i
< loop
->num_nodes
; i
++)
2083 if (bbs
[i
]->loop_father
== loop
)
2085 block_stmt_iterator bsi
;
2086 for (bsi
= bsi_start (bbs
[i
]); !bsi_end_p (bsi
); bsi_next (&bsi
))
2088 tree stmt
= bsi_stmt (bsi
);
2089 if (stmt
== exit_cond
2090 || not_interesting_stmt (stmt
)
2091 || stmt_is_bumper_for_loop (loop
, stmt
))
2099 /* See if the inner loops are perfectly nested as well. */
2101 return perfect_nest_p (loop
->inner
);
2105 /* Replace the USES of X in STMT, or uses with the same step as X with Y.
2106 YINIT is the initial value of Y, REPLACEMENTS is a hash table to
2107 avoid creating duplicate temporaries and FIRSTBSI is statement
2108 iterator where new temporaries should be inserted at the beginning
2109 of body basic block. */
2112 replace_uses_equiv_to_x_with_y (struct loop
*loop
, tree stmt
, tree x
,
2113 int xstep
, tree y
, tree yinit
,
2114 htab_t replacements
,
2115 block_stmt_iterator
*firstbsi
)
2118 use_operand_p use_p
;
2120 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
2122 tree use
= USE_FROM_PTR (use_p
);
2123 tree step
= NULL_TREE
;
2124 tree scev
, init
, val
, var
, setstmt
;
2125 struct tree_map
*h
, in
;
2128 /* Replace uses of X with Y right away. */
2135 scev
= instantiate_parameters (loop
,
2136 analyze_scalar_evolution (loop
, use
));
2138 if (scev
== NULL
|| scev
== chrec_dont_know
)
2141 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2143 || step
== chrec_dont_know
2144 || TREE_CODE (step
) != INTEGER_CST
2145 || int_cst_value (step
) != xstep
)
2148 /* Use REPLACEMENTS hash table to cache already created
2150 in
.hash
= htab_hash_pointer (use
);
2152 h
= htab_find_with_hash (replacements
, &in
, in
.hash
);
2155 SET_USE (use_p
, h
->to
);
2159 /* USE which has the same step as X should be replaced
2160 with a temporary set to Y + YINIT - INIT. */
2161 init
= initial_condition_in_loop_num (scev
, loop
->num
);
2162 gcc_assert (init
!= NULL
&& init
!= chrec_dont_know
);
2163 if (TREE_TYPE (use
) == TREE_TYPE (y
))
2165 val
= fold_build2 (MINUS_EXPR
, TREE_TYPE (y
), init
, yinit
);
2166 val
= fold_build2 (PLUS_EXPR
, TREE_TYPE (y
), y
, val
);
2169 /* If X has the same type as USE, the same step
2170 and same initial value, it can be replaced by Y. */
2177 val
= fold_build2 (MINUS_EXPR
, TREE_TYPE (y
), y
, yinit
);
2178 val
= fold_convert (TREE_TYPE (use
), val
);
2179 val
= fold_build2 (PLUS_EXPR
, TREE_TYPE (use
), val
, init
);
2182 /* Create a temporary variable and insert it at the beginning
2183 of the loop body basic block, right after the PHI node
2185 var
= create_tmp_var (TREE_TYPE (use
), "perfecttmp");
2186 add_referenced_var (var
);
2187 val
= force_gimple_operand_bsi (firstbsi
, val
, false, NULL
);
2188 setstmt
= build2 (MODIFY_EXPR
, void_type_node
, var
, val
);
2189 var
= make_ssa_name (var
, setstmt
);
2190 TREE_OPERAND (setstmt
, 0) = var
;
2191 bsi_insert_before (firstbsi
, setstmt
, BSI_SAME_STMT
);
2192 update_stmt (setstmt
);
2193 SET_USE (use_p
, var
);
2194 h
= ggc_alloc (sizeof (struct tree_map
));
2198 loc
= htab_find_slot_with_hash (replacements
, h
, in
.hash
, INSERT
);
2199 gcc_assert ((*(struct tree_map
**)loc
) == NULL
);
2200 *(struct tree_map
**) loc
= h
;
2204 /* Return true if STMT is an exit PHI for LOOP */
2207 exit_phi_for_loop_p (struct loop
*loop
, tree stmt
)
2210 if (TREE_CODE (stmt
) != PHI_NODE
2211 || PHI_NUM_ARGS (stmt
) != 1
2212 || bb_for_stmt (stmt
) != single_exit (loop
)->dest
)
2218 /* Return true if STMT can be put back into the loop INNER, by
2219 copying it to the beginning of that loop and changing the uses. */
2222 can_put_in_inner_loop (struct loop
*inner
, tree stmt
)
2224 imm_use_iterator imm_iter
;
2225 use_operand_p use_p
;
2227 gcc_assert (TREE_CODE (stmt
) == MODIFY_EXPR
);
2228 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
)
2229 || !expr_invariant_in_loop_p (inner
, TREE_OPERAND (stmt
, 1)))
2232 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, TREE_OPERAND (stmt
, 0))
2234 if (!exit_phi_for_loop_p (inner
, USE_STMT (use_p
)))
2236 basic_block immbb
= bb_for_stmt (USE_STMT (use_p
));
2238 if (!flow_bb_inside_loop_p (inner
, immbb
))
2245 /* Return true if STMT can be put *after* the inner loop of LOOP. */
2247 can_put_after_inner_loop (struct loop
*loop
, tree stmt
)
2249 imm_use_iterator imm_iter
;
2250 use_operand_p use_p
;
2252 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
2255 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, TREE_OPERAND (stmt
, 0))
2257 if (!exit_phi_for_loop_p (loop
, USE_STMT (use_p
)))
2259 basic_block immbb
= bb_for_stmt (USE_STMT (use_p
));
2261 if (!dominated_by_p (CDI_DOMINATORS
,
2263 loop
->inner
->header
)
2264 && !can_put_in_inner_loop (loop
->inner
, stmt
))
2273 /* Return TRUE if LOOP is an imperfect nest that we can convert to a
2274 perfect one. At the moment, we only handle imperfect nests of
2275 depth 2, where all of the statements occur after the inner loop. */
2278 can_convert_to_perfect_nest (struct loop
*loop
)
2281 tree exit_condition
, phi
;
2283 block_stmt_iterator bsi
;
2284 basic_block exitdest
;
2286 /* Can't handle triply nested+ loops yet. */
2287 if (!loop
->inner
|| loop
->inner
->inner
)
2290 bbs
= get_loop_body (loop
);
2291 exit_condition
= get_loop_exit_condition (loop
);
2292 for (i
= 0; i
< loop
->num_nodes
; i
++)
2294 if (bbs
[i
]->loop_father
== loop
)
2296 for (bsi
= bsi_start (bbs
[i
]); !bsi_end_p (bsi
); bsi_next (&bsi
))
2298 tree stmt
= bsi_stmt (bsi
);
2300 if (stmt
== exit_condition
2301 || not_interesting_stmt (stmt
)
2302 || stmt_is_bumper_for_loop (loop
, stmt
))
2305 /* If this is a scalar operation that can be put back
2306 into the inner loop, or after the inner loop, through
2307 copying, then do so. This works on the theory that
2308 any amount of scalar code we have to reduplicate
2309 into or after the loops is less expensive that the
2310 win we get from rearranging the memory walk
2311 the loop is doing so that it has better
2313 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
2315 use_operand_p use_a
, use_b
;
2316 imm_use_iterator imm_iter
;
2317 ssa_op_iter op_iter
, op_iter1
;
2318 tree op0
= TREE_OPERAND (stmt
, 0);
2319 tree scev
= instantiate_parameters
2320 (loop
, analyze_scalar_evolution (loop
, op0
));
2322 /* If the IV is simple, it can be duplicated. */
2323 if (!automatically_generated_chrec_p (scev
))
2325 tree step
= evolution_part_in_loop_num (scev
, loop
->num
);
2326 if (step
&& step
!= chrec_dont_know
2327 && TREE_CODE (step
) == INTEGER_CST
)
2331 /* The statement should not define a variable used
2332 in the inner loop. */
2333 if (TREE_CODE (op0
) == SSA_NAME
)
2334 FOR_EACH_IMM_USE_FAST (use_a
, imm_iter
, op0
)
2335 if (bb_for_stmt (USE_STMT (use_a
))->loop_father
2339 FOR_EACH_SSA_USE_OPERAND (use_a
, stmt
, op_iter
, SSA_OP_USE
)
2341 tree node
, op
= USE_FROM_PTR (use_a
);
2343 /* The variables should not be used in both loops. */
2344 FOR_EACH_IMM_USE_FAST (use_b
, imm_iter
, op
)
2345 if (bb_for_stmt (USE_STMT (use_b
))->loop_father
2349 /* The statement should not use the value of a
2350 scalar that was modified in the loop. */
2351 node
= SSA_NAME_DEF_STMT (op
);
2352 if (TREE_CODE (node
) == PHI_NODE
)
2353 FOR_EACH_PHI_ARG (use_b
, node
, op_iter1
, SSA_OP_USE
)
2355 tree arg
= USE_FROM_PTR (use_b
);
2357 if (TREE_CODE (arg
) == SSA_NAME
)
2359 tree arg_stmt
= SSA_NAME_DEF_STMT (arg
);
2361 if (bb_for_stmt (arg_stmt
)->loop_father
2368 if (can_put_in_inner_loop (loop
->inner
, stmt
)
2369 || can_put_after_inner_loop (loop
, stmt
))
2373 /* Otherwise, if the bb of a statement we care about isn't
2374 dominated by the header of the inner loop, then we can't
2375 handle this case right now. This test ensures that the
2376 statement comes completely *after* the inner loop. */
2377 if (!dominated_by_p (CDI_DOMINATORS
,
2379 loop
->inner
->header
))
2385 /* We also need to make sure the loop exit only has simple copy phis in it,
2386 otherwise we don't know how to transform it into a perfect nest right
2388 exitdest
= single_exit (loop
)->dest
;
2390 for (phi
= phi_nodes (exitdest
); phi
; phi
= PHI_CHAIN (phi
))
2391 if (PHI_NUM_ARGS (phi
) != 1)
2402 /* Transform the loop nest into a perfect nest, if possible.
2403 LOOP is the loop nest to transform into a perfect nest
2404 LBOUNDS are the lower bounds for the loops to transform
2405 UBOUNDS are the upper bounds for the loops to transform
2406 STEPS is the STEPS for the loops to transform.
2407 LOOPIVS is the induction variables for the loops to transform.
2409 Basically, for the case of
2411 FOR (i = 0; i < 50; i++)
2413 FOR (j =0; j < 50; j++)
2420 This function will transform it into a perfect loop nest by splitting the
2421 outer loop into two loops, like so:
2423 FOR (i = 0; i < 50; i++)
2425 FOR (j = 0; j < 50; j++)
2431 FOR (i = 0; i < 50; i ++)
2436 Return FALSE if we can't make this loop into a perfect nest. */
2439 perfect_nestify (struct loop
*loop
,
2440 VEC(tree
,heap
) *lbounds
,
2441 VEC(tree
,heap
) *ubounds
,
2442 VEC(int,heap
) *steps
,
2443 VEC(tree
,heap
) *loopivs
)
2446 tree exit_condition
;
2447 tree then_label
, else_label
, cond_stmt
;
2448 basic_block preheaderbb
, headerbb
, bodybb
, latchbb
, olddest
;
2450 block_stmt_iterator bsi
, firstbsi
;
2453 struct loop
*newloop
;
2457 tree oldivvar
, ivvar
, ivvarinced
;
2458 VEC(tree
,heap
) *phis
= NULL
;
2459 htab_t replacements
= NULL
;
2461 /* Create the new loop. */
2462 olddest
= single_exit (loop
)->dest
;
2463 preheaderbb
= split_edge (single_exit (loop
));
2464 headerbb
= create_empty_bb (EXIT_BLOCK_PTR
->prev_bb
);
2466 /* Push the exit phi nodes that we are moving. */
2467 for (phi
= phi_nodes (olddest
); phi
; phi
= PHI_CHAIN (phi
))
2469 VEC_reserve (tree
, heap
, phis
, 2);
2470 VEC_quick_push (tree
, phis
, PHI_RESULT (phi
));
2471 VEC_quick_push (tree
, phis
, PHI_ARG_DEF (phi
, 0));
2473 e
= redirect_edge_and_branch (single_succ_edge (preheaderbb
), headerbb
);
2475 /* Remove the exit phis from the old basic block. Make sure to set
2476 PHI_RESULT to null so it doesn't get released. */
2477 while (phi_nodes (olddest
) != NULL
)
2479 SET_PHI_RESULT (phi_nodes (olddest
), NULL
);
2480 remove_phi_node (phi_nodes (olddest
), NULL
);
2483 /* and add them back to the new basic block. */
2484 while (VEC_length (tree
, phis
) != 0)
2488 def
= VEC_pop (tree
, phis
);
2489 phiname
= VEC_pop (tree
, phis
);
2490 phi
= create_phi_node (phiname
, preheaderbb
);
2491 add_phi_arg (phi
, def
, single_pred_edge (preheaderbb
));
2493 flush_pending_stmts (e
);
2494 VEC_free (tree
, heap
, phis
);
2496 bodybb
= create_empty_bb (EXIT_BLOCK_PTR
->prev_bb
);
2497 latchbb
= create_empty_bb (EXIT_BLOCK_PTR
->prev_bb
);
2498 make_edge (headerbb
, bodybb
, EDGE_FALLTHRU
);
2499 then_label
= build1 (GOTO_EXPR
, void_type_node
, tree_block_label (latchbb
));
2500 else_label
= build1 (GOTO_EXPR
, void_type_node
, tree_block_label (olddest
));
2501 cond_stmt
= build3 (COND_EXPR
, void_type_node
,
2502 build2 (NE_EXPR
, boolean_type_node
,
2505 then_label
, else_label
);
2506 bsi
= bsi_start (bodybb
);
2507 bsi_insert_after (&bsi
, cond_stmt
, BSI_NEW_STMT
);
2508 e
= make_edge (bodybb
, olddest
, EDGE_FALSE_VALUE
);
2509 make_edge (bodybb
, latchbb
, EDGE_TRUE_VALUE
);
2510 make_edge (latchbb
, headerbb
, EDGE_FALLTHRU
);
2512 /* Update the loop structures. */
2513 newloop
= duplicate_loop (loop
, olddest
->loop_father
);
2514 newloop
->header
= headerbb
;
2515 newloop
->latch
= latchbb
;
2516 set_single_exit (newloop
, e
);
2517 add_bb_to_loop (latchbb
, newloop
);
2518 add_bb_to_loop (bodybb
, newloop
);
2519 add_bb_to_loop (headerbb
, newloop
);
2520 set_immediate_dominator (CDI_DOMINATORS
, bodybb
, headerbb
);
2521 set_immediate_dominator (CDI_DOMINATORS
, headerbb
, preheaderbb
);
2522 set_immediate_dominator (CDI_DOMINATORS
, preheaderbb
,
2523 single_exit (loop
)->src
);
2524 set_immediate_dominator (CDI_DOMINATORS
, latchbb
, bodybb
);
2525 set_immediate_dominator (CDI_DOMINATORS
, olddest
, bodybb
);
2526 /* Create the new iv. */
2527 oldivvar
= VEC_index (tree
, loopivs
, 0);
2528 ivvar
= create_tmp_var (TREE_TYPE (oldivvar
), "perfectiv");
2529 add_referenced_var (ivvar
);
2530 standard_iv_increment_position (newloop
, &bsi
, &insert_after
);
2531 create_iv (VEC_index (tree
, lbounds
, 0),
2532 build_int_cst (TREE_TYPE (oldivvar
), VEC_index (int, steps
, 0)),
2533 ivvar
, newloop
, &bsi
, insert_after
, &ivvar
, &ivvarinced
);
2535 /* Create the new upper bound. This may be not just a variable, so we copy
2536 it to one just in case. */
2538 exit_condition
= get_loop_exit_condition (newloop
);
2539 uboundvar
= create_tmp_var (integer_type_node
, "uboundvar");
2540 add_referenced_var (uboundvar
);
2541 stmt
= build2 (MODIFY_EXPR
, void_type_node
, uboundvar
,
2542 VEC_index (tree
, ubounds
, 0));
2543 uboundvar
= make_ssa_name (uboundvar
, stmt
);
2544 TREE_OPERAND (stmt
, 0) = uboundvar
;
2547 bsi_insert_after (&bsi
, stmt
, BSI_SAME_STMT
);
2549 bsi_insert_before (&bsi
, stmt
, BSI_SAME_STMT
);
2551 COND_EXPR_COND (exit_condition
) = build2 (GE_EXPR
,
2555 update_stmt (exit_condition
);
2556 replacements
= htab_create_ggc (20, tree_map_hash
,
2558 bbs
= get_loop_body_in_dom_order (loop
);
2559 /* Now move the statements, and replace the induction variable in the moved
2560 statements with the correct loop induction variable. */
2561 oldivvar
= VEC_index (tree
, loopivs
, 0);
2562 firstbsi
= bsi_start (bodybb
);
2563 for (i
= loop
->num_nodes
- 1; i
>= 0 ; i
--)
2565 block_stmt_iterator tobsi
= bsi_last (bodybb
);
2566 if (bbs
[i
]->loop_father
== loop
)
2568 /* If this is true, we are *before* the inner loop.
2569 If this isn't true, we are *after* it.
2571 The only time can_convert_to_perfect_nest returns true when we
2572 have statements before the inner loop is if they can be moved
2573 into the inner loop.
2575 The only time can_convert_to_perfect_nest returns true when we
2576 have statements after the inner loop is if they can be moved into
2577 the new split loop. */
2579 if (dominated_by_p (CDI_DOMINATORS
, loop
->inner
->header
, bbs
[i
]))
2581 block_stmt_iterator header_bsi
2582 = bsi_after_labels (loop
->inner
->header
);
2584 for (bsi
= bsi_start (bbs
[i
]); !bsi_end_p (bsi
);)
2586 tree stmt
= bsi_stmt (bsi
);
2588 if (stmt
== exit_condition
2589 || not_interesting_stmt (stmt
)
2590 || stmt_is_bumper_for_loop (loop
, stmt
))
2596 bsi_move_before (&bsi
, &header_bsi
);
2601 /* Note that the bsi only needs to be explicitly incremented
2602 when we don't move something, since it is automatically
2603 incremented when we do. */
2604 for (bsi
= bsi_start (bbs
[i
]); !bsi_end_p (bsi
);)
2607 tree n
, stmt
= bsi_stmt (bsi
);
2609 if (stmt
== exit_condition
2610 || not_interesting_stmt (stmt
)
2611 || stmt_is_bumper_for_loop (loop
, stmt
))
2617 replace_uses_equiv_to_x_with_y
2618 (loop
, stmt
, oldivvar
, VEC_index (int, steps
, 0), ivvar
,
2619 VEC_index (tree
, lbounds
, 0), replacements
, &firstbsi
);
2621 bsi_move_before (&bsi
, &tobsi
);
2623 /* If the statement has any virtual operands, they may
2624 need to be rewired because the original loop may
2625 still reference them. */
2626 FOR_EACH_SSA_TREE_OPERAND (n
, stmt
, i
, SSA_OP_ALL_VIRTUALS
)
2627 mark_sym_for_renaming (SSA_NAME_VAR (n
));
2635 htab_delete (replacements
);
2636 return perfect_nest_p (loop
);
2639 /* Return true if TRANS is a legal transformation matrix that respects
2640 the dependence vectors in DISTS and DIRS. The conservative answer
2643 "Wolfe proves that a unimodular transformation represented by the
2644 matrix T is legal when applied to a loop nest with a set of
2645 lexicographically non-negative distance vectors RDG if and only if
2646 for each vector d in RDG, (T.d >= 0) is lexicographically positive.
2647 i.e.: if and only if it transforms the lexicographically positive
2648 distance vectors to lexicographically positive vectors. Note that
2649 a unimodular matrix must transform the zero vector (and only it) to
2650 the zero vector." S.Muchnick. */
2653 lambda_transform_legal_p (lambda_trans_matrix trans
,
2655 VEC (ddr_p
, heap
) *dependence_relations
)
2658 lambda_vector distres
;
2659 struct data_dependence_relation
*ddr
;
2661 gcc_assert (LTM_COLSIZE (trans
) == nb_loops
2662 && LTM_ROWSIZE (trans
) == nb_loops
);
2664 /* When there is an unknown relation in the dependence_relations, we
2665 know that it is no worth looking at this loop nest: give up. */
2666 ddr
= VEC_index (ddr_p
, dependence_relations
, 0);
2669 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
2672 distres
= lambda_vector_new (nb_loops
);
2674 /* For each distance vector in the dependence graph. */
2675 for (i
= 0; VEC_iterate (ddr_p
, dependence_relations
, i
, ddr
); i
++)
2677 /* Don't care about relations for which we know that there is no
2678 dependence, nor about read-read (aka. output-dependences):
2679 these data accesses can happen in any order. */
2680 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
2681 || (DR_IS_READ (DDR_A (ddr
)) && DR_IS_READ (DDR_B (ddr
))))
2684 /* Conservatively answer: "this transformation is not valid". */
2685 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
2688 /* If the dependence could not be captured by a distance vector,
2689 conservatively answer that the transform is not valid. */
2690 if (DDR_NUM_DIST_VECTS (ddr
) == 0)
2693 /* Compute trans.dist_vect */
2694 for (j
= 0; j
< DDR_NUM_DIST_VECTS (ddr
); j
++)
2696 lambda_matrix_vector_mult (LTM_MATRIX (trans
), nb_loops
, nb_loops
,
2697 DDR_DIST_VECT (ddr
, j
), distres
);
2699 if (!lambda_vector_lexico_pos (distres
, nb_loops
))