/* Loop transformation code generation
- Copyright (C) 2003, 2004 Free Software Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
Contributed by Daniel Berlin <dberlin@dberlin.org>
This file is part of GCC.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to the Free
- Software Foundation, 59 Temple Place - Suite 330, Boston, MA
- 02111-1307, USA. */
+ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+ 02110-1301, USA. */
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
-#include "errors.h"
#include "ggc.h"
#include "tree.h"
#include "target.h"
Keshav Pingali for formal proofs that the various statements below are
correct.
- A loop iteration space are the points traversed by the loop. A point in the
+ A loop iteration space represents the points traversed by the loop. A point in the
iteration space can be represented by a vector of size <loop depth>. You can
- therefore represent the iteration space as a integral combinations of a set
+ therefore represent the iteration space as an integral combinations of a set
of basis vectors.
A loop iteration space is dense if every integer point between the loop
Fourier-Motzkin elimination is used to compute the bounds of the base space
of the lattice. */
-
-
-DEF_VEC_GC_P(int);
+DEF_VEC_I(int);
+DEF_VEC_ALLOC_I(int,heap);
static bool perfect_nestify (struct loops *,
- struct loop *, VEC (tree) *,
- VEC (tree) *, VEC (int) *, VEC (tree) *);
+ struct loop *, VEC(tree,heap) *,
+ VEC(tree,heap) *, VEC(int,heap) *,
+ VEC(tree,heap) *);
/* Lattice stuff that is internal to the code generation algorithm. */
typedef struct
}
/* Allocate a new lattice structure of DEPTH x DEPTH, with INVARIANTS number
- of invariants. */
+ of invariants. */
static lambda_lattice
lambda_lattice_new (int depth, int invariants)
/* Otherwise, we need the lower bound expression (which must
be an affine function) to determine the base. */
expression = LL_LOWER_BOUND (loop);
- gcc_assert (expression && LLE_NEXT (expression)
+ gcc_assert (expression && !LLE_NEXT (expression)
&& LLE_DENOMINATOR (expression) == 1);
/* The lower triangular portion of the base is going to be the
return (abs (a) * abs (b) / gcd (a, b));
}
+/* Perform Fourier-Motzkin elimination to calculate the bounds of the
+ auxiliary nest.
+ Fourier-Motzkin is a way of reducing systems of linear inequalities so that
+ it is easy to calculate the answer and bounds.
+ A sketch of how it works:
+ Given a system of linear inequalities, ai * xj >= bk, you can always
+ rewrite the constraints so they are all of the form
+ a <= x, or x <= b, or x >= constant for some x in x1 ... xj (and some b
+ in b1 ... bk, and some a in a1...ai)
+ You can then eliminate this x from the non-constant inequalities by
+ rewriting these as a <= b, x >= constant, and delete the x variable.
+ You can then repeat this for any remaining x variables, and then we have
+ an easy to use variable <= constant (or no variables at all) form that we
+ can construct our bounds from.
+
+ In our case, each time we eliminate, we construct part of the bound from
+ the ith variable, then delete the ith variable.
+
+ Remember the constant are in our vector a, our coefficient matrix is A,
+ and our invariant coefficient matrix is B.
+
+ SIZE is the size of the matrices being passed.
+ DEPTH is the loop nest depth.
+ INVARIANTS is the number of loop invariants.
+ A, B, and a are the coefficient matrix, invariant coefficient, and a
+ vector of constants, respectively. */
+
+static lambda_loopnest
+compute_nest_using_fourier_motzkin (int size,
+ int depth,
+ int invariants,
+ lambda_matrix A,
+ lambda_matrix B,
+ lambda_vector a)
+{
+
+ int multiple, f1, f2;
+ int i, j, k;
+ lambda_linear_expression expression;
+ lambda_loop loop;
+ lambda_loopnest auxillary_nest;
+ lambda_matrix swapmatrix, A1, B1;
+ lambda_vector swapvector, a1;
+ int newsize;
+
+ A1 = lambda_matrix_new (128, depth);
+ B1 = lambda_matrix_new (128, invariants);
+ a1 = lambda_vector_new (128);
+
+ auxillary_nest = lambda_loopnest_new (depth, invariants);
+
+ for (i = depth - 1; i >= 0; i--)
+ {
+ loop = lambda_loop_new ();
+ LN_LOOPS (auxillary_nest)[i] = loop;
+ LL_STEP (loop) = 1;
+
+ for (j = 0; j < size; j++)
+ {
+ if (A[j][i] < 0)
+ {
+ /* Any linear expression in the matrix with a coefficient less
+ than 0 becomes part of the new lower bound. */
+ expression = lambda_linear_expression_new (depth, invariants);
+
+ for (k = 0; k < i; k++)
+ LLE_COEFFICIENTS (expression)[k] = A[j][k];
+
+ for (k = 0; k < invariants; k++)
+ LLE_INVARIANT_COEFFICIENTS (expression)[k] = -1 * B[j][k];
+
+ LLE_DENOMINATOR (expression) = -1 * A[j][i];
+ LLE_CONSTANT (expression) = -1 * a[j];
+
+ /* Ignore if identical to the existing lower bound. */
+ if (!lle_equal (LL_LOWER_BOUND (loop),
+ expression, depth, invariants))
+ {
+ LLE_NEXT (expression) = LL_LOWER_BOUND (loop);
+ LL_LOWER_BOUND (loop) = expression;
+ }
+
+ }
+ else if (A[j][i] > 0)
+ {
+ /* Any linear expression with a coefficient greater than 0
+ becomes part of the new upper bound. */
+ expression = lambda_linear_expression_new (depth, invariants);
+ for (k = 0; k < i; k++)
+ LLE_COEFFICIENTS (expression)[k] = -1 * A[j][k];
+
+ for (k = 0; k < invariants; k++)
+ LLE_INVARIANT_COEFFICIENTS (expression)[k] = B[j][k];
+
+ LLE_DENOMINATOR (expression) = A[j][i];
+ LLE_CONSTANT (expression) = a[j];
+
+ /* Ignore if identical to the existing upper bound. */
+ if (!lle_equal (LL_UPPER_BOUND (loop),
+ expression, depth, invariants))
+ {
+ LLE_NEXT (expression) = LL_UPPER_BOUND (loop);
+ LL_UPPER_BOUND (loop) = expression;
+ }
+
+ }
+ }
+
+ /* This portion creates a new system of linear inequalities by deleting
+ the i'th variable, reducing the system by one variable. */
+ newsize = 0;
+ for (j = 0; j < size; j++)
+ {
+ /* If the coefficient for the i'th variable is 0, then we can just
+ eliminate the variable straightaway. Otherwise, we have to
+ multiply through by the coefficients we are eliminating. */
+ if (A[j][i] == 0)
+ {
+ lambda_vector_copy (A[j], A1[newsize], depth);
+ lambda_vector_copy (B[j], B1[newsize], invariants);
+ a1[newsize] = a[j];
+ newsize++;
+ }
+ else if (A[j][i] > 0)
+ {
+ for (k = 0; k < size; k++)
+ {
+ if (A[k][i] < 0)
+ {
+ multiple = lcm (A[j][i], A[k][i]);
+ f1 = multiple / A[j][i];
+ f2 = -1 * multiple / A[k][i];
+
+ lambda_vector_add_mc (A[j], f1, A[k], f2,
+ A1[newsize], depth);
+ lambda_vector_add_mc (B[j], f1, B[k], f2,
+ B1[newsize], invariants);
+ a1[newsize] = f1 * a[j] + f2 * a[k];
+ newsize++;
+ }
+ }
+ }
+ }
+
+ swapmatrix = A;
+ A = A1;
+ A1 = swapmatrix;
+
+ swapmatrix = B;
+ B = B1;
+ B1 = swapmatrix;
+
+ swapvector = a;
+ a = a1;
+ a1 = swapvector;
+
+ size = newsize;
+ }
+
+ return auxillary_nest;
+}
+
/* Compute the loop bounds for the auxiliary space NEST.
- Input system used is Ax <= b. TRANS is the unimodular transformation. */
+ Input system used is Ax <= b. TRANS is the unimodular transformation.
+ Given the original nest, this function will
+ 1. Convert the nest into matrix form, which consists of a matrix for the
+ coefficients, a matrix for the
+ invariant coefficients, and a vector for the constants.
+ 2. Use the matrix form to calculate the lattice base for the nest (which is
+ a dense space)
+ 3. Compose the dense space transform with the user specified transform, to
+ get a transform we can easily calculate transformed bounds for.
+ 4. Multiply the composed transformation matrix times the matrix form of the
+ loop.
+ 5. Transform the newly created matrix (from step 4) back into a loop nest
+ using fourier motzkin elimination to figure out the bounds. */
static lambda_loopnest
lambda_compute_auxillary_space (lambda_loopnest nest,
lambda_trans_matrix trans)
{
- lambda_matrix A, B, A1, B1, temp0;
- lambda_vector a, a1, temp1;
+ lambda_matrix A, B, A1, B1;
+ lambda_vector a, a1;
lambda_matrix invertedtrans;
- int determinant, depth, invariants, size, newsize;
- int i, j, k;
- lambda_loopnest auxillary_nest;
+ int depth, invariants, size;
+ int i, j;
lambda_loop loop;
lambda_linear_expression expression;
lambda_lattice lattice;
- int multiple, f1, f2;
-
depth = LN_DEPTH (nest);
invariants = LN_INVARIANTS (nest);
/* Unfortunately, we can't know the number of constraints we'll have
ahead of time, but this should be enough even in ridiculous loop nest
- cases. We abort if we go over this limit. */
+ cases. We must not go over this limit. */
A = lambda_matrix_new (128, depth);
B = lambda_matrix_new (128, invariants);
a = lambda_vector_new (128);
invertedtrans = lambda_matrix_new (depth, depth);
/* Compute the inverse of U. */
- determinant = lambda_matrix_inverse (LTM_MATRIX (trans),
- invertedtrans, depth);
+ lambda_matrix_inverse (LTM_MATRIX (trans),
+ invertedtrans, depth);
/* A = A1 inv(U). */
lambda_matrix_mult (A1, invertedtrans, A, size, depth, depth);
- /* Perform Fourier-Motzkin elimination to calculate the bounds of the
- auxillary nest.
- Fourier-Motzkin is a way of reducing systems of linear inequality so that
- it is easy to calculate the answer and bounds.
- A sketch of how it works:
- Given a system of linear inequalities, ai * xj >= bk, you can always
- rewrite the constraints so they are all of the form
- a <= x, or x <= b, or x >= constant for some x in x1 ... xj (and some b
- in b1 ... bk, and some a in a1...ai)
- You can then eliminate this x from the non-constant inequalities by
- rewriting these as a <= b, x >= constant, and delete the x variable.
- You can then repeat this for any remaining x variables, and then we have
- an easy to use variable <= constant (or no variables at all) form that we
- can construct our bounds from.
-
- In our case, each time we eliminate, we construct part of the bound from
- the ith variable, then delete the ith variable.
-
- Remember the constant are in our vector a, our coefficient matrix is A,
- and our invariant coefficient matrix is B */
-
- /* Swap B and B1, and a1 and a. */
- temp0 = B1;
- B1 = B;
- B = temp0;
-
- temp1 = a1;
- a1 = a;
- a = temp1;
-
- auxillary_nest = lambda_loopnest_new (depth, invariants);
-
- for (i = depth - 1; i >= 0; i--)
- {
- loop = lambda_loop_new ();
- LN_LOOPS (auxillary_nest)[i] = loop;
- LL_STEP (loop) = 1;
-
- for (j = 0; j < size; j++)
- {
- if (A[j][i] < 0)
- {
- /* Lower bound. */
- expression = lambda_linear_expression_new (depth, invariants);
-
- for (k = 0; k < i; k++)
- LLE_COEFFICIENTS (expression)[k] = A[j][k];
- for (k = 0; k < invariants; k++)
- LLE_INVARIANT_COEFFICIENTS (expression)[k] = -1 * B[j][k];
- LLE_DENOMINATOR (expression) = -1 * A[j][i];
- LLE_CONSTANT (expression) = -1 * a[j];
- /* Ignore if identical to the existing lower bound. */
- if (!lle_equal (LL_LOWER_BOUND (loop),
- expression, depth, invariants))
- {
- LLE_NEXT (expression) = LL_LOWER_BOUND (loop);
- LL_LOWER_BOUND (loop) = expression;
- }
-
- }
- else if (A[j][i] > 0)
- {
- /* Upper bound. */
- expression = lambda_linear_expression_new (depth, invariants);
- for (k = 0; k < i; k++)
- LLE_COEFFICIENTS (expression)[k] = -1 * A[j][k];
- LLE_CONSTANT (expression) = a[j];
-
- for (k = 0; k < invariants; k++)
- LLE_INVARIANT_COEFFICIENTS (expression)[k] = B[j][k];
-
- LLE_DENOMINATOR (expression) = A[j][i];
- /* Ignore if identical to the existing upper bound. */
- if (!lle_equal (LL_UPPER_BOUND (loop),
- expression, depth, invariants))
- {
- LLE_NEXT (expression) = LL_UPPER_BOUND (loop);
- LL_UPPER_BOUND (loop) = expression;
- }
-
- }
- }
- /* creates a new system by deleting the i'th variable. */
- newsize = 0;
- for (j = 0; j < size; j++)
- {
- if (A[j][i] == 0)
- {
- lambda_vector_copy (A[j], A1[newsize], depth);
- lambda_vector_copy (B[j], B1[newsize], invariants);
- a1[newsize] = a[j];
- newsize++;
- }
- else if (A[j][i] > 0)
- {
- for (k = 0; k < size; k++)
- {
- if (A[k][i] < 0)
- {
- multiple = lcm (A[j][i], A[k][i]);
- f1 = multiple / A[j][i];
- f2 = -1 * multiple / A[k][i];
-
- lambda_vector_add_mc (A[j], f1, A[k], f2,
- A1[newsize], depth);
- lambda_vector_add_mc (B[j], f1, B[k], f2,
- B1[newsize], invariants);
- a1[newsize] = f1 * a[j] + f2 * a[k];
- newsize++;
- }
- }
- }
- }
-
- temp0 = A;
- A = A1;
- A1 = temp0;
-
- temp0 = B;
- B = B1;
- B1 = temp0;
-
- temp1 = a;
- a = a1;
- a1 = temp1;
-
- size = newsize;
- }
-
- return auxillary_nest;
+ return compute_nest_using_fourier_motzkin (size, depth, invariants,
+ A, B1, a1);
}
/* Compute the loop bounds for the target space, using the bounds of
- the auxiliary nest AUXILLARY_NEST, and the triangular matrix H. This is
- done by matrix multiplication and then transformation of the new matrix
- back into linear expression form.
+ the auxiliary nest AUXILLARY_NEST, and the triangular matrix H.
+ The target space loop bounds are computed by multiplying the triangular
+ matrix H by the auxiliary nest, to get the new loop bounds. The sign of
+ the loop steps (positive or negative) is then used to swap the bounds if
+ the loop counts downwards.
Return the target loopnest. */
static lambda_loopnest
2. Composing the dense base with the specified transformation (TRANS)
3. Decomposing the combined transformation into a lower triangular portion,
and a unimodular portion.
- 4. Computing the auxillary nest using the unimodular portion.
- 5. Computing the target nest using the auxillary nest and the lower
+ 4. Computing the auxiliary nest using the unimodular portion.
+ 5. Computing the target nest using the auxiliary nest and the lower
triangular portion. */
lambda_loopnest
static lambda_linear_expression
gcc_tree_to_linear_expression (int depth, tree expr,
- VEC(tree) *outerinductionvars,
- VEC(tree) *invariants, int extra)
+ VEC(tree,heap) *outerinductionvars,
+ VEC(tree,heap) *invariants, int extra)
{
lambda_linear_expression lle = NULL;
switch (TREE_CODE (expr))
lle = lambda_linear_expression_new (depth, 2 * depth);
LLE_CONSTANT (lle) = TREE_INT_CST_LOW (expr);
if (extra != 0)
- LLE_CONSTANT (lle) = extra;
+ LLE_CONSTANT (lle) += extra;
LLE_DENOMINATOR (lle) = 1;
}
return lle;
}
+/* Return the depth of the loopnest NEST */
+
+static int
+depth_of_nest (struct loop *nest)
+{
+ size_t depth = 0;
+ while (nest)
+ {
+ depth++;
+ nest = nest->inner;
+ }
+ return depth;
+}
+
+
/* Return true if OP is invariant in LOOP and all outer loops. */
static bool
-invariant_in_loop (struct loop *loop, tree op)
+invariant_in_loop_and_outer_loops (struct loop *loop, tree op)
{
if (is_gimple_min_invariant (op))
return true;
if (loop->depth == 0)
return true;
- if (TREE_CODE (op) == SSA_NAME)
- {
- tree def;
- def = SSA_NAME_DEF_STMT (op);
- if (TREE_CODE (SSA_NAME_VAR (op)) == PARM_DECL
- && IS_EMPTY_STMT (def))
- return true;
- if (IS_EMPTY_STMT (def))
- return false;
- if (loop->outer
- && !invariant_in_loop (loop->outer, op))
- return false;
- return !flow_bb_inside_loop_p (loop, bb_for_stmt (def));
- }
- return false;
+ if (!expr_invariant_in_loop_p (loop, op))
+ return false;
+ if (loop->outer
+ && !invariant_in_loop_and_outer_loops (loop->outer, op))
+ return false;
+ return true;
}
/* Generate a lambda loop from a gcc loop LOOP. Return the new lambda loop,
static lambda_loop
gcc_loop_to_lambda_loop (struct loop *loop, int depth,
- VEC (tree) ** invariants,
+ VEC(tree,heap) ** invariants,
tree * ourinductionvar,
- VEC (tree) * outerinductionvars,
- VEC (tree) ** lboundvars,
- VEC (tree) ** uboundvars,
- VEC (int) ** steps)
+ VEC(tree,heap) * outerinductionvars,
+ VEC(tree,heap) ** lboundvars,
+ VEC(tree,heap) ** uboundvars,
+ VEC(int,heap) ** steps)
{
tree phi;
tree exit_cond;
tree test;
int stepint;
int extra = 0;
- tree lboundvar, uboundvar;
- use_optype uses;
+ tree lboundvar, uboundvar, uboundresult;
/* Find out induction var and exit condition. */
inductionvar = find_induction_var_from_exit_cond (loop);
phi = SSA_NAME_DEF_STMT (inductionvar);
if (TREE_CODE (phi) != PHI_NODE)
{
- get_stmt_operands (phi);
- uses = STMT_USE_OPS (phi);
-
- if (!uses)
+ phi = SINGLE_SSA_TREE_OPERAND (phi, SSA_OP_USE);
+ if (!phi)
{
if (dump_file && (dump_flags & TDF_DETAILS))
return NULL;
}
- phi = USE_OP (uses, 0);
phi = SSA_NAME_DEF_STMT (phi);
if (TREE_CODE (phi) != PHI_NODE)
{
}
}
+
/* The induction variable name/version we want to put in the array is the
result of the induction variable phi node. */
*ourinductionvar = PHI_RESULT (phi);
access_fn = instantiate_parameters
(loop, analyze_scalar_evolution (loop, PHI_RESULT (phi)));
- if (!access_fn)
+ if (access_fn == chrec_dont_know)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
- "Unable to convert loop: Access function for induction variable phi is NULL\n");
+ "Unable to convert loop: Access function for induction variable phi is unknown\n");
return NULL;
}
return NULL;
}
/* One part of the test may be a loop invariant tree. */
+ VEC_reserve (tree, heap, *invariants, 1);
if (TREE_CODE (TREE_OPERAND (test, 1)) == SSA_NAME
- && invariant_in_loop (loop, TREE_OPERAND (test, 1)))
- VEC_safe_push (tree, *invariants, TREE_OPERAND (test, 1));
+ && invariant_in_loop_and_outer_loops (loop, TREE_OPERAND (test, 1)))
+ VEC_quick_push (tree, *invariants, TREE_OPERAND (test, 1));
else if (TREE_CODE (TREE_OPERAND (test, 0)) == SSA_NAME
- && invariant_in_loop (loop, TREE_OPERAND (test, 0)))
- VEC_safe_push (tree, *invariants, TREE_OPERAND (test, 0));
+ && invariant_in_loop_and_outer_loops (loop, TREE_OPERAND (test, 0)))
+ VEC_quick_push (tree, *invariants, TREE_OPERAND (test, 0));
/* The non-induction variable part of the test is the upper bound variable.
*/
extra = -1 * stepint;
else if (TREE_CODE (test) == GT_EXPR)
extra = -1 * stepint;
-
- ubound = gcc_tree_to_linear_expression (depth,
- uboundvar,
+ else if (TREE_CODE (test) == EQ_EXPR)
+ extra = 1 * stepint;
+
+ ubound = gcc_tree_to_linear_expression (depth, uboundvar,
outerinductionvars,
*invariants, extra);
- VEC_safe_push (tree, *uboundvars, build (PLUS_EXPR, integer_type_node,
- uboundvar,
- build_int_cst (integer_type_node, extra)));
- VEC_safe_push (tree, *lboundvars, lboundvar);
- VEC_safe_push (int, *steps, stepint);
+ uboundresult = build (PLUS_EXPR, TREE_TYPE (uboundvar), uboundvar,
+ build_int_cst (TREE_TYPE (uboundvar), extra));
+ VEC_safe_push (tree, heap, *uboundvars, uboundresult);
+ VEC_safe_push (tree, heap, *lboundvars, lboundvar);
+ VEC_safe_push (int, heap, *steps, stepint);
if (!ubound)
{
-
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
"Unable to convert loop: Cannot convert upper bound to linear expression\n");
test = TREE_OPERAND (expr, 0);
if (!COMPARISON_CLASS_P (test))
return NULL_TREE;
- /* This is a guess. We say that for a <,!=,<= b, a is the induction
- variable.
- For >, >=, we guess b is the induction variable.
- If we are wrong, it'll fail the rest of the induction variable tests, and
- everything will be fine anyway. */
- switch (TREE_CODE (test))
- {
- case LT_EXPR:
- case LE_EXPR:
- case NE_EXPR:
- ivarop = TREE_OPERAND (test, 0);
- break;
- case GT_EXPR:
- case GE_EXPR:
+
+ /* Find the side that is invariant in this loop. The ivar must be the other
+ side. */
+
+ if (expr_invariant_in_loop_p (loop, TREE_OPERAND (test, 0)))
ivarop = TREE_OPERAND (test, 1);
- break;
- default:
- gcc_unreachable();
- }
+ else if (expr_invariant_in_loop_p (loop, TREE_OPERAND (test, 1)))
+ ivarop = TREE_OPERAND (test, 0);
+ else
+ return NULL_TREE;
+
if (TREE_CODE (ivarop) != SSA_NAME)
return NULL_TREE;
return ivarop;
}
-DEF_VEC_GC_P(lambda_loop);
+DEF_VEC_P(lambda_loop);
+DEF_VEC_ALLOC_P(lambda_loop,heap);
+
/* Generate a lambda loopnest from a gcc loopnest LOOP_NEST.
Return the new loop nest.
INDUCTIONVARS is a pointer to an array of induction variables for the
lambda_loopnest
gcc_loopnest_to_lambda_loopnest (struct loops *currloops,
struct loop * loop_nest,
- VEC (tree) **inductionvars,
- VEC (tree) **invariants,
+ VEC(tree,heap) **inductionvars,
+ VEC(tree,heap) **invariants,
bool need_perfect_nest)
{
- lambda_loopnest ret;
+ lambda_loopnest ret = NULL;
struct loop *temp;
int depth = 0;
size_t i;
- VEC (lambda_loop) *loops;
- VEC (tree) *uboundvars;
- VEC (tree) *lboundvars;
- VEC (int) *steps;
+ VEC(lambda_loop,heap) *loops = NULL;
+ VEC(tree,heap) *uboundvars = NULL;
+ VEC(tree,heap) *lboundvars = NULL;
+ VEC(int,heap) *steps = NULL;
lambda_loop newloop;
tree inductionvar = NULL;
-
- temp = loop_nest;
- while (temp)
- {
- depth++;
- temp = temp->inner;
- }
- loops = VEC_alloc (lambda_loop, 1);
- *inductionvars = VEC_alloc (tree, 1);
- *invariants = VEC_alloc (tree, 1);
- lboundvars = VEC_alloc (tree, 1);
- uboundvars = VEC_alloc (tree, 1);
- steps = VEC_alloc (int, 1);
+
+ depth = depth_of_nest (loop_nest);
temp = loop_nest;
while (temp)
{
&steps);
if (!newloop)
return NULL;
- VEC_safe_push (tree, *inductionvars, inductionvar);
- VEC_safe_push (lambda_loop, loops, newloop);
+ VEC_safe_push (tree, heap, *inductionvars, inductionvar);
+ VEC_safe_push (lambda_loop, heap, loops, newloop);
temp = temp->inner;
}
- if (need_perfect_nest
- && !perfect_nestify (currloops, loop_nest,
- lboundvars, uboundvars, steps, *inductionvars))
+ if (need_perfect_nest)
{
- if (dump_file)
- fprintf (dump_file, "Not a perfect nest and couldn't convert to one.\n");
- return NULL;
+ if (!perfect_nestify (currloops, loop_nest,
+ lboundvars, uboundvars, steps, *inductionvars))
+ {
+ if (dump_file)
+ fprintf (dump_file,
+ "Not a perfect loop nest and couldn't convert to one.\n");
+ goto fail;
+ }
+ else if (dump_file)
+ fprintf (dump_file,
+ "Successfully converted loop nest to perfect loop nest.\n");
}
ret = lambda_loopnest_new (depth, 2 * depth);
for (i = 0; VEC_iterate (lambda_loop, loops, i, newloop); i++)
LN_LOOPS (ret)[i] = newloop;
-
+ fail:
+ VEC_free (lambda_loop, heap, loops);
+ VEC_free (tree, heap, uboundvars);
+ VEC_free (tree, heap, lboundvars);
+ VEC_free (int, heap, steps);
+
return ret;
-
}
/* Convert a lambda body vector LBV to a gcc tree, and return the new tree.
STMTS_TO_INSERT is a pointer to a tree where the statements we need to be
inserted for us are stored. INDUCTION_VARS is the array of induction
- variables for the loop this LBV is from. */
+ variables for the loop this LBV is from. TYPE is the tree type to use for
+ the variables and trees involved. */
static tree
-lbv_to_gcc_expression (lambda_body_vector lbv,
- VEC (tree) *induction_vars, tree * stmts_to_insert)
+lbv_to_gcc_expression (lambda_body_vector lbv,
+ tree type, VEC(tree,heap) *induction_vars,
+ tree *stmts_to_insert)
{
tree stmts, stmt, resvar, name;
+ tree iv;
size_t i;
tree_stmt_iterator tsi;
/* Create a statement list and a linear expression temporary. */
stmts = alloc_stmt_list ();
- resvar = create_tmp_var (integer_type_node, "lbvtmp");
+ resvar = create_tmp_var (type, "lbvtmp");
add_referenced_tmp_var (resvar);
/* Start at 0. */
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
- for (i = 0; i < VEC_length (tree ,induction_vars) ; i++)
+ for (i = 0; VEC_iterate (tree, induction_vars, i, iv); i++)
{
if (LBV_COEFFICIENTS (lbv)[i] != 0)
{
tree newname;
-
+ tree coeffmult;
+
/* newname = coefficient * induction_variable */
+ coeffmult = build_int_cst (type, LBV_COEFFICIENTS (lbv)[i]);
stmt = build (MODIFY_EXPR, void_type_node, resvar,
- fold (build (MULT_EXPR, integer_type_node,
- VEC_index (tree, induction_vars, i),
- build_int_cst (integer_type_node,
- LBV_COEFFICIENTS (lbv)[i]))));
+ fold_build2 (MULT_EXPR, type, iv, coeffmult));
+
newname = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = newname;
+ fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
+
/* name = name + newname */
stmt = build (MODIFY_EXPR, void_type_node, resvar,
- build (PLUS_EXPR, integer_type_node, name, newname));
+ build (PLUS_EXPR, type, name, newname));
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
+ fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
+
}
}
/* Handle any denominator that occurs. */
if (LBV_DENOMINATOR (lbv) != 1)
{
+ tree denominator = build_int_cst (type, LBV_DENOMINATOR (lbv));
stmt = build (MODIFY_EXPR, void_type_node, resvar,
- build (CEIL_DIV_EXPR, integer_type_node,
- name, build_int_cst (integer_type_node,
- LBV_DENOMINATOR (lbv))));
+ build (CEIL_DIV_EXPR, type, name, denominator));
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
+ fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
}
Return the tree that represents the final value of the expression.
LLE is the linear expression to convert.
OFFSET is the linear offset to apply to the expression.
+ TYPE is the tree type to use for the variables and math.
INDUCTION_VARS is a vector of induction variables for the loops.
INVARIANTS is a vector of the loop nest invariants.
WRAP specifies what tree code to wrap the results in, if there is more than
static tree
lle_to_gcc_expression (lambda_linear_expression lle,
lambda_linear_expression offset,
- VEC(tree) *induction_vars,
- VEC(tree) *invariants,
- enum tree_code wrap, tree * stmts_to_insert)
+ tree type,
+ VEC(tree,heap) *induction_vars,
+ VEC(tree,heap) *invariants,
+ enum tree_code wrap, tree *stmts_to_insert)
{
tree stmts, stmt, resvar, name;
size_t i;
tree_stmt_iterator tsi;
- VEC(tree) *results;
+ tree iv, invar;
+ VEC(tree,heap) *results = NULL;
+ gcc_assert (wrap == MAX_EXPR || wrap == MIN_EXPR);
name = NULL_TREE;
/* Create a statement list and a linear expression temporary. */
stmts = alloc_stmt_list ();
- resvar = create_tmp_var (integer_type_node, "lletmp");
+ resvar = create_tmp_var (type, "lletmp");
add_referenced_tmp_var (resvar);
- results = VEC_alloc (tree, 1);
/* Build up the linear expressions, and put the variable representing the
result in the results array. */
stmt = build (MODIFY_EXPR, void_type_node, resvar, integer_zero_node);
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
+ fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
/* First do the induction variables.
at the end, name = name + all the induction variables added
together. */
- for (i = 0; i < VEC_length (tree ,induction_vars); i++)
+ for (i = 0; VEC_iterate (tree, induction_vars, i, iv); i++)
{
if (LLE_COEFFICIENTS (lle)[i] != 0)
{
}
else
{
- coeff = build_int_cst (integer_type_node,
+ coeff = build_int_cst (type,
LLE_COEFFICIENTS (lle)[i]);
- mult = fold (build (MULT_EXPR, integer_type_node,
- VEC_index (tree, induction_vars, i),
- coeff));
+ mult = fold_build2 (MULT_EXPR, type, iv, coeff);
}
/* newname = mult */
stmt = build (MODIFY_EXPR, void_type_node, resvar, mult);
newname = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = newname;
+ fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
/* name = name + newname */
stmt = build (MODIFY_EXPR, void_type_node, resvar,
- build (PLUS_EXPR, integer_type_node,
- name, newname));
+ build (PLUS_EXPR, type, name, newname));
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
+ fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
}
/* Handle our invariants.
At the end, we have name = name + result of adding all multiplied
invariants. */
- for (i = 0; i < VEC_length (tree, invariants); i++)
+ for (i = 0; VEC_iterate (tree, invariants, i, invar); i++)
{
if (LLE_INVARIANT_COEFFICIENTS (lle)[i] != 0)
{
tree newname;
tree mult;
tree coeff;
-
+ int invcoeff = LLE_INVARIANT_COEFFICIENTS (lle)[i];
/* mult = invariant * coefficient */
- if (LLE_INVARIANT_COEFFICIENTS (lle)[i] == 1)
+ if (invcoeff == 1)
{
- mult = VEC_index (tree, invariants, i);
+ mult = invar;
}
else
{
- coeff = build_int_cst (integer_type_node,
- LLE_INVARIANT_COEFFICIENTS (lle)[i]);
- mult = fold (build (MULT_EXPR, integer_type_node,
- VEC_index (tree, invariants, i),
- coeff));
+ coeff = build_int_cst (type, invcoeff);
+ mult = fold_build2 (MULT_EXPR, type, invar, coeff);
}
/* newname = mult */
stmt = build (MODIFY_EXPR, void_type_node, resvar, mult);
newname = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = newname;
+ fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
/* name = name + newname */
stmt = build (MODIFY_EXPR, void_type_node, resvar,
- build (PLUS_EXPR, integer_type_node,
- name, newname));
+ build (PLUS_EXPR, type, name, newname));
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
+ fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
}
if (LLE_CONSTANT (lle) != 0)
{
stmt = build (MODIFY_EXPR, void_type_node, resvar,
- build (PLUS_EXPR, integer_type_node,
- name, build_int_cst (integer_type_node,
- LLE_CONSTANT (lle))));
+ build (PLUS_EXPR, type, name,
+ build_int_cst (type, LLE_CONSTANT (lle))));
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
+ fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
}
if (LLE_CONSTANT (offset) != 0)
{
stmt = build (MODIFY_EXPR, void_type_node, resvar,
- build (PLUS_EXPR, integer_type_node,
- name, build_int_cst (integer_type_node,
- LLE_CONSTANT (offset))));
+ build (PLUS_EXPR, type, name,
+ build_int_cst (type, LLE_CONSTANT (offset))));
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
+ fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
}
/* Handle any denominator that occurs. */
if (LLE_DENOMINATOR (lle) != 1)
{
- if (wrap == MAX_EXPR)
- stmt = build (MODIFY_EXPR, void_type_node, resvar,
- build (CEIL_DIV_EXPR, integer_type_node,
- name, build_int_cst (integer_type_node,
- LLE_DENOMINATOR (lle))));
- else if (wrap == MIN_EXPR)
- stmt = build (MODIFY_EXPR, void_type_node, resvar,
- build (FLOOR_DIV_EXPR, integer_type_node,
- name, build_int_cst (integer_type_node,
- LLE_DENOMINATOR (lle))));
- else
- gcc_unreachable();
+ stmt = build_int_cst (type, LLE_DENOMINATOR (lle));
+ stmt = build (wrap == MAX_EXPR ? CEIL_DIV_EXPR : FLOOR_DIV_EXPR,
+ type, name, stmt);
+ stmt = build (MODIFY_EXPR, void_type_node, resvar, stmt);
/* name = {ceil, floor}(name/denominator) */
name = make_ssa_name (resvar, stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
}
- VEC_safe_push (tree, results, name);
+ VEC_safe_push (tree, heap, results, name);
}
/* Again, out of laziness, we don't handle this case yet. It's not
tree op1 = VEC_index (tree, results, 0);
tree op2 = VEC_index (tree, results, 1);
stmt = build (MODIFY_EXPR, void_type_node, resvar,
- build (wrap, integer_type_node, op1, op2));
+ build (wrap, type, op1, op2));
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
}
+ VEC_free (tree, heap, results);
+
*stmts_to_insert = stmts;
return name;
}
NEW_LOOPNEST is the new lambda loopnest to replace OLD_LOOPNEST with.
TRANSFORM is the matrix transform that was applied to OLD_LOOPNEST to get
NEW_LOOPNEST. */
+
void
lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest,
- VEC(tree) *old_ivs,
- VEC(tree) *invariants,
+ VEC(tree,heap) *old_ivs,
+ VEC(tree,heap) *invariants,
lambda_loopnest new_loopnest,
lambda_trans_matrix transform)
{
-
struct loop *temp;
size_t i = 0;
size_t depth = 0;
- VEC(tree) *new_ivs;
+ VEC(tree,heap) *new_ivs = NULL;
+ tree oldiv;
+
block_stmt_iterator bsi;
if (dump_file)
fprintf (dump_file, "Inverse of transformation matrix:\n");
print_lambda_trans_matrix (dump_file, transform);
}
- temp = old_loopnest;
- new_ivs = VEC_alloc (tree, 1);
- while (temp)
- {
- temp = temp->inner;
- depth++;
- }
+ depth = depth_of_nest (old_loopnest);
temp = old_loopnest;
while (temp)
{
lambda_loop newloop;
basic_block bb;
+ edge exit;
tree ivvar, ivvarinced, exitcond, stmts;
enum tree_code testtype;
tree newupperbound, newlowerbound;
lambda_linear_expression offset;
+ tree type;
+ bool insert_after;
+ tree inc_stmt;
+
+ oldiv = VEC_index (tree, old_ivs, i);
+ type = TREE_TYPE (oldiv);
+
/* First, build the new induction variable temporary */
- ivvar = create_tmp_var (integer_type_node, "lnivtmp");
+ ivvar = create_tmp_var (type, "lnivtmp");
add_referenced_tmp_var (ivvar);
- VEC_safe_push (tree, new_ivs, ivvar);
+ VEC_safe_push (tree, heap, new_ivs, ivvar);
newloop = LN_LOOPS (new_loopnest)[i];
/* Linear offset is a bit tricky to handle. Punt on the unhandled
cases for now. */
offset = LL_LINEAR_OFFSET (newloop);
-
+
gcc_assert (LLE_DENOMINATOR (offset) == 1 &&
lambda_vector_zerop (LLE_COEFFICIENTS (offset), depth));
-
+
/* Now build the new lower bounds, and insert the statements
necessary to generate it on the loop preheader. */
newlowerbound = lle_to_gcc_expression (LL_LOWER_BOUND (newloop),
LL_LINEAR_OFFSET (newloop),
+ type,
new_ivs,
invariants, MAX_EXPR, &stmts);
bsi_insert_on_edge (loop_preheader_edge (temp), stmts);
- bsi_commit_edge_inserts (NULL);
+ bsi_commit_edge_inserts ();
/* Build the new upper bound and insert its statements in the
basic block of the exit condition */
newupperbound = lle_to_gcc_expression (LL_UPPER_BOUND (newloop),
LL_LINEAR_OFFSET (newloop),
+ type,
new_ivs,
invariants, MIN_EXPR, &stmts);
+ exit = temp->single_exit;
exitcond = get_loop_exit_condition (temp);
bb = bb_for_stmt (exitcond);
bsi = bsi_start (bb);
bsi_insert_after (&bsi, stmts, BSI_NEW_STMT);
- /* Create the new iv, and insert it's increment on the latch
- block. */
+ /* Create the new iv. */
- bb = EDGE_PRED (temp->latch, 0)->src;
- bsi = bsi_last (bb);
+ standard_iv_increment_position (temp, &bsi, &insert_after);
create_iv (newlowerbound,
- build_int_cst (integer_type_node, LL_STEP (newloop)),
- ivvar, temp, &bsi, false, &ivvar,
- &ivvarinced);
+ build_int_cst (type, LL_STEP (newloop)),
+ ivvar, temp, &bsi, insert_after, &ivvar,
+ NULL);
+
+ /* Unfortunately, the incremented ivvar that create_iv inserted may not
+ dominate the block containing the exit condition.
+ So we simply create our own incremented iv to use in the new exit
+ test, and let redundancy elimination sort it out. */
+ inc_stmt = build (PLUS_EXPR, type,
+ ivvar, build_int_cst (type, LL_STEP (newloop)));
+ inc_stmt = build (MODIFY_EXPR, void_type_node, SSA_NAME_VAR (ivvar),
+ inc_stmt);
+ ivvarinced = make_ssa_name (SSA_NAME_VAR (ivvar), inc_stmt);
+ TREE_OPERAND (inc_stmt, 0) = ivvarinced;
+ bsi = bsi_for_stmt (exitcond);
+ bsi_insert_before (&bsi, inc_stmt, BSI_SAME_STMT);
/* Replace the exit condition with the new upper bound
comparison. */
+
testtype = LL_STEP (newloop) >= 0 ? LE_EXPR : GE_EXPR;
+
+ /* We want to build a conditional where true means exit the loop, and
+ false means continue the loop.
+ So swap the testtype if this isn't the way things are.*/
+
+ if (exit->flags & EDGE_FALSE_VALUE)
+ testtype = swap_tree_comparison (testtype);
+
COND_EXPR_COND (exitcond) = build (testtype,
boolean_type_node,
- ivvarinced, newupperbound);
- modify_stmt (exitcond);
+ newupperbound, ivvarinced);
+ update_stmt (exitcond);
VEC_replace (tree, new_ivs, i, ivvar);
i++;
temp = temp->inner;
}
-
+
/* Rewrite uses of the old ivs so that they are now specified in terms of
the new ivs. */
- temp = old_loopnest;
- for (i = 0; i < VEC_length (tree, old_ivs); i++)
+
+ for (i = 0; VEC_iterate (tree, old_ivs, i, oldiv); i++)
{
- int j;
- tree oldiv = VEC_index (tree, old_ivs, i);
- dataflow_t imm = get_immediate_uses (SSA_NAME_DEF_STMT (oldiv));
- for (j = 0; j < num_immediate_uses (imm); j++)
+ imm_use_iterator imm_iter;
+ use_operand_p imm_use;
+ tree oldiv_def;
+ tree oldiv_stmt = SSA_NAME_DEF_STMT (oldiv);
+
+ if (TREE_CODE (oldiv_stmt) == PHI_NODE)
+ oldiv_def = PHI_RESULT (oldiv_stmt);
+ else
+ oldiv_def = SINGLE_SSA_TREE_OPERAND (oldiv_stmt, SSA_OP_DEF);
+ gcc_assert (oldiv_def != NULL_TREE);
+
+ FOR_EACH_IMM_USE_SAFE (imm_use, imm_iter, oldiv_def)
{
- size_t k;
- tree stmt = immediate_use (imm, j);
- use_optype uses;
- get_stmt_operands (stmt);
- uses = STMT_USE_OPS (stmt);
- for (k = 0; k < NUM_USES (uses); k++)
+ tree stmt = USE_STMT (imm_use);
+ use_operand_p use_p;
+ ssa_op_iter iter;
+ gcc_assert (TREE_CODE (stmt) != PHI_NODE);
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
{
- use_operand_p use = USE_OP_PTR (uses, k);
- if (USE_FROM_PTR (use) == oldiv)
+ if (USE_FROM_PTR (use_p) == oldiv)
{
tree newiv, stmts;
- lambda_body_vector lbv;
+ lambda_body_vector lbv, newlbv;
/* Compute the new expression for the induction
variable. */
depth = VEC_length (tree, new_ivs);
lbv = lambda_body_vector_new (depth);
LBV_COEFFICIENTS (lbv)[i] = 1;
- lbv = lambda_body_vector_compute_new (transform, lbv);
- newiv = lbv_to_gcc_expression (lbv, new_ivs, &stmts);
- bsi = stmt_for_bsi (stmt);
+
+ newlbv = lambda_body_vector_compute_new (transform, lbv);
+
+ newiv = lbv_to_gcc_expression (newlbv, TREE_TYPE (oldiv),
+ new_ivs, &stmts);
+ bsi = bsi_for_stmt (stmt);
/* Insert the statements to build that
expression. */
bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
- SET_USE (use, newiv);
- modify_stmt (stmt);
+ propagate_value (use_p, newiv);
+ update_stmt (stmt);
}
}
}
}
+ VEC_free (tree, heap, new_ivs);
}
-
-/* Returns true when the vector V is lexicographically positive, in
- other words, when the first nonzero element is positive. */
-
-static bool
-lambda_vector_lexico_pos (lambda_vector v,
- unsigned n)
-{
- unsigned i;
- for (i = 0; i < n; i++)
- {
- if (v[i] == 0)
- continue;
- if (v[i] < 0)
- return false;
- if (v[i] > 0)
- return true;
- }
- return true;
-}
-
-
/* Return TRUE if this is not interesting statement from the perspective of
determining if we have a perfect loop nest. */
static bool
stmt_uses_phi_result (tree stmt, tree phi_result)
{
- use_optype uses = STMT_USE_OPS (stmt);
+ tree use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
/* This is conservatively true, because we only want SIMPLE bumpers
- of the form x +- constant for our pass. */
- if (NUM_USES (uses) != 1)
- return false;
- if (USE_OP (uses, 0) == phi_result)
- return true;
-
- return false;
+ of the form x +- constant for our pass. */
+ return (use == phi_result);
}
/* STMT is a bumper stmt for LOOP if the version it defines is used in the
{
tree use;
tree def;
- def_optype defs = STMT_DEF_OPS (stmt);
- dataflow_t imm;
- int i;
+ imm_use_iterator iter;
+ use_operand_p use_p;
- if (NUM_DEFS (defs) != 1)
+ def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
+ if (!def)
return false;
- def = DEF_OP (defs, 0);
- imm = get_immediate_uses (stmt);
- for (i = 0; i < num_immediate_uses (imm); i++)
+
+ FOR_EACH_IMM_USE_FAST (use_p, iter, def)
{
- use = immediate_use (imm, i);
+ use = USE_STMT (use_p);
if (TREE_CODE (use) == PHI_NODE)
{
if (phi_loop_edge_uses_def (loop, use, def))
}
return false;
}
+
+
/* Return true if LOOP is a perfect loop nest.
Perfect loop nests are those loop nests where all code occurs in the
innermost loop body.
return true;
}
-
-/* Add phi args using PENDINT_STMT list. */
+/* Replace the USES of X in STMT, or uses with the same step as X with Y. */
static void
-nestify_update_pending_stmts (edge e)
+replace_uses_equiv_to_x_with_y (struct loop *loop, tree stmt, tree x,
+ int xstep, tree y)
{
- basic_block dest;
- tree phi, arg, def;
-
- if (!PENDING_STMT (e))
- return;
-
- dest = e->dest;
+ ssa_op_iter iter;
+ use_operand_p use_p;
- for (phi = phi_nodes (dest), arg = PENDING_STMT (e);
- phi;
- phi = TREE_CHAIN (phi), arg = TREE_CHAIN (arg))
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
{
- def = TREE_VALUE (arg);
- add_phi_arg (&phi, def, e);
+ tree use = USE_FROM_PTR (use_p);
+ tree step = NULL_TREE;
+ tree access_fn = NULL_TREE;
+
+
+ access_fn = instantiate_parameters
+ (loop, analyze_scalar_evolution (loop, use));
+ if (access_fn != NULL_TREE && access_fn != chrec_dont_know)
+ step = evolution_part_in_loop_num (access_fn, loop->num);
+ if ((step && step != chrec_dont_know
+ && TREE_CODE (step) == INTEGER_CST
+ && int_cst_value (step) == xstep)
+ || USE_FROM_PTR (use_p) == x)
+ SET_USE (use_p, y);
}
-
- PENDING_STMT (e) = NULL;
}
-/* Replace the USES of tree X in STMT with tree Y */
+/* Return TRUE if STMT uses tree OP in it's uses. */
-static void
-replace_uses_of_x_with_y (tree stmt, tree x, tree y)
+static bool
+stmt_uses_op (tree stmt, tree op)
{
- use_optype uses = STMT_USE_OPS (stmt);
- size_t i;
- for (i = 0; i < NUM_USES (uses); i++)
+ ssa_op_iter iter;
+ tree use;
+
+ FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
{
- if (USE_OP (uses, i) == x)
- SET_USE_OP (uses, i, y);
+ if (use == op)
+ return true;
}
+ return false;
}
-/* Return TRUE if STMT uses tree OP in it's uses. */
+/* Return true if STMT is an exit PHI for LOOP */
static bool
-stmt_uses_op (tree stmt, tree op)
+exit_phi_for_loop_p (struct loop *loop, tree stmt)
{
- use_optype uses = STMT_USE_OPS (stmt);
- size_t i;
- for (i = 0; i < NUM_USES (uses); i++)
+
+ if (TREE_CODE (stmt) != PHI_NODE
+ || PHI_NUM_ARGS (stmt) != 1
+ || bb_for_stmt (stmt) != loop->single_exit->dest)
+ return false;
+
+ return true;
+}
+
+/* Return true if STMT can be put back into INNER, a loop by moving it to the
+ beginning of that loop. */
+
+static bool
+can_put_in_inner_loop (struct loop *inner, tree stmt)
+{
+ imm_use_iterator imm_iter;
+ use_operand_p use_p;
+ basic_block use_bb = NULL;
+
+ gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR);
+ if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)
+ || !expr_invariant_in_loop_p (inner, TREE_OPERAND (stmt, 1)))
+ return false;
+
+ /* We require that the basic block of all uses be the same, or the use be an
+ exit phi. */
+ FOR_EACH_IMM_USE_FAST (use_p, imm_iter, TREE_OPERAND (stmt, 0))
{
- if (USE_OP (uses, i) == op)
- return true;
+ if (!exit_phi_for_loop_p (inner, USE_STMT (use_p)))
+ {
+ basic_block immbb = bb_for_stmt (USE_STMT (use_p));
+
+ if (!flow_bb_inside_loop_p (inner, immbb))
+ return false;
+ if (use_bb == NULL)
+ use_bb = immbb;
+ else if (immbb != use_bb)
+ return false;
+ }
}
- return false;
+ return true;
+
}
+
/* Return TRUE if LOOP is an imperfect nest that we can convert to a perfect
one. LOOPIVS is a vector of induction variables, one per loop.
ATM, we only handle imperfect nests of depth 2, where all of the statements
static bool
can_convert_to_perfect_nest (struct loop *loop,
- VEC (tree) *loopivs)
+ VEC(tree,heap) *loopivs)
{
basic_block *bbs;
- tree exit_condition;
+ tree exit_condition, phi;
size_t i;
block_stmt_iterator bsi;
+ basic_block exitdest;
/* Can't handle triply nested+ loops yet. */
if (!loop->inner || loop->inner->inner)
return false;
- /* We only handle moving the after-inner-body statements right now, so make
- sure all the statements we need to move are located in that position. */
bbs = get_loop_body (loop);
exit_condition = get_loop_exit_condition (loop);
for (i = 0; i < loop->num_nodes; i++)
{
size_t j;
tree stmt = bsi_stmt (bsi);
+ tree iv;
+
if (stmt == exit_condition
|| not_interesting_stmt (stmt)
|| stmt_is_bumper_for_loop (loop, stmt))
continue;
/* If the statement uses inner loop ivs, we == screwed. */
- for (j = 1; j < VEC_length (tree, loopivs); j++)
- if (stmt_uses_op (stmt, VEC_index (tree, loopivs, j)))
- {
- free (bbs);
- return false;
- }
+ for (j = 1; VEC_iterate (tree, loopivs, j, iv); j++)
+ if (stmt_uses_op (stmt, iv))
+ goto fail;
- /* If the bb of a statement we care about isn't dominated by
- the header of the inner loop, then we are also screwed. */
+ /* If this is a simple operation like a cast that is invariant
+ in the inner loop, only used there, and we can place it
+ there, then it's not going to hurt us.
+ This means that we will propagate casts and other cheap
+ invariant operations *back*
+ into the inner loop if we can interchange the loop, on the
+ theory that we are going to gain a lot more by interchanging
+ the loop than we are by leaving some invariant code there for
+ some other pass to clean up. */
+ if (TREE_CODE (stmt) == MODIFY_EXPR
+ && is_gimple_cast (TREE_OPERAND (stmt, 1))
+ && can_put_in_inner_loop (loop->inner, stmt))
+ continue;
+
+ /* Otherwise, if the bb of a statement we care about isn't
+ dominated by the header of the inner loop, then we can't
+ handle this case right now. This test ensures that the
+ statement comes completely *after* the inner loop. */
if (!dominated_by_p (CDI_DOMINATORS,
bb_for_stmt (stmt),
loop->inner->header))
- {
- free (bbs);
- return false;
- }
+ goto fail;
}
}
- }
+ }
+
+ /* We also need to make sure the loop exit only has simple copy phis in it,
+ otherwise we don't know how to transform it into a perfect nest right
+ now. */
+ exitdest = loop->single_exit->dest;
+
+ for (phi = phi_nodes (exitdest); phi; phi = PHI_CHAIN (phi))
+ if (PHI_NUM_ARGS (phi) != 1)
+ goto fail;
+
+ free (bbs);
return true;
+
+ fail:
+ free (bbs);
+ return false;
}
/* Transform the loop nest into a perfect nest, if possible.
}
Return FALSE if we can't make this loop into a perfect nest. */
+
static bool
perfect_nestify (struct loops *loops,
struct loop *loop,
- VEC (tree) *lbounds,
- VEC (tree) *ubounds,
- VEC (int) *steps,
- VEC (tree) *loopivs)
+ VEC(tree,heap) *lbounds,
+ VEC(tree,heap) *ubounds,
+ VEC(int,heap) *steps,
+ VEC(tree,heap) *loopivs)
{
basic_block *bbs;
tree exit_condition;
tree then_label, else_label, cond_stmt;
basic_block preheaderbb, headerbb, bodybb, latchbb, olddest;
- size_t i;
+ int i;
block_stmt_iterator bsi;
+ bool insert_after;
edge e;
struct loop *newloop;
tree phi;
tree uboundvar;
tree stmt;
- tree ivvar, ivvarinced;
- VEC (tree) *phis;
+ tree oldivvar, ivvar, ivvarinced;
+ VEC(tree,heap) *phis = NULL;
if (!can_convert_to_perfect_nest (loop, loopivs))
return false;
- phis = VEC_alloc (tree, 1);
-
/* Create the new loop */
olddest = loop->single_exit->dest;
preheaderbb = loop_split_edge_with (loop->single_exit, NULL);
headerbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
- /* This is done because otherwise, it will release the ssa_name too early
- when the edge gets redirected and it will get reused, causing the use of
- the phi node to get rewritten. */
-
+ /* Push the exit phi nodes that we are moving. */
for (phi = phi_nodes (olddest); phi; phi = PHI_CHAIN (phi))
{
- /* These should be simple exit phi copies. */
- if (PHI_NUM_ARGS (phi) != 1)
- return false;
- VEC_safe_push (tree, phis, PHI_RESULT (phi));
- VEC_safe_push (tree, phis, PHI_ARG_DEF (phi, 0));
- mark_for_rewrite (PHI_RESULT (phi));
+ VEC_reserve (tree, heap, phis, 2);
+ VEC_quick_push (tree, phis, PHI_RESULT (phi));
+ VEC_quick_push (tree, phis, PHI_ARG_DEF (phi, 0));
}
- e = redirect_edge_and_branch (EDGE_SUCC (preheaderbb, 0), headerbb);
- unmark_all_for_rewrite ();
- bb_ann (olddest)->phi_nodes = NULL;
- /* Add back the old exit phis. */
+ e = redirect_edge_and_branch (single_succ_edge (preheaderbb), headerbb);
+
+ /* Remove the exit phis from the old basic block. Make sure to set
+ PHI_RESULT to null so it doesn't get released. */
+ while (phi_nodes (olddest) != NULL)
+ {
+ SET_PHI_RESULT (phi_nodes (olddest), NULL);
+ remove_phi_node (phi_nodes (olddest), NULL);
+ }
+
+ /* and add them back to the new basic block. */
while (VEC_length (tree, phis) != 0)
{
tree def;
tree phiname;
def = VEC_pop (tree, phis);
- phiname = VEC_pop (tree, phis);
-
+ phiname = VEC_pop (tree, phis);
phi = create_phi_node (phiname, preheaderbb);
- add_phi_arg (&phi, def, EDGE_PRED (preheaderbb, 0));
- }
-
- nestify_update_pending_stmts (e);
+ add_phi_arg (phi, def, single_pred_edge (preheaderbb));
+ }
+ flush_pending_stmts (e);
+ VEC_free (tree, heap, phis);
+
bodybb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
latchbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
make_edge (headerbb, bodybb, EDGE_FALLTHRU);
add_bb_to_loop (latchbb, newloop);
add_bb_to_loop (bodybb, newloop);
add_bb_to_loop (headerbb, newloop);
- add_bb_to_loop (preheaderbb, olddest->loop_father);
set_immediate_dominator (CDI_DOMINATORS, bodybb, headerbb);
set_immediate_dominator (CDI_DOMINATORS, headerbb, preheaderbb);
set_immediate_dominator (CDI_DOMINATORS, preheaderbb,
set_immediate_dominator (CDI_DOMINATORS, latchbb, bodybb);
set_immediate_dominator (CDI_DOMINATORS, olddest, bodybb);
/* Create the new iv. */
- ivvar = create_tmp_var (integer_type_node, "perfectiv");
+ oldivvar = VEC_index (tree, loopivs, 0);
+ ivvar = create_tmp_var (TREE_TYPE (oldivvar), "perfectiv");
add_referenced_tmp_var (ivvar);
- bsi = bsi_last (EDGE_PRED (newloop->latch, 0)->src);
+ standard_iv_increment_position (newloop, &bsi, &insert_after);
create_iv (VEC_index (tree, lbounds, 0),
- build_int_cst (integer_type_node,
- VEC_index (int, steps, 0)),
- ivvar, newloop, &bsi, false, &ivvar, &ivvarinced);
+ build_int_cst (TREE_TYPE (oldivvar), VEC_index (int, steps, 0)),
+ ivvar, newloop, &bsi, insert_after, &ivvar, &ivvarinced);
/* Create the new upper bound. This may be not just a variable, so we copy
it to one just in case. */
VEC_index (tree, ubounds, 0));
uboundvar = make_ssa_name (uboundvar, stmt);
TREE_OPERAND (stmt, 0) = uboundvar;
- bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
- COND_EXPR_COND (exit_condition) = build (LE_EXPR,
- boolean_type_node,
- ivvarinced,
- uboundvar);
- bbs = get_loop_body (loop);
- /* Now replace the induction variable in the moved statements with the
- correct loop induction variable. */
- for (i = 0; i < loop->num_nodes; i++)
+ if (insert_after)
+ bsi_insert_after (&bsi, stmt, BSI_SAME_STMT);
+ else
+ bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
+ update_stmt (stmt);
+ COND_EXPR_COND (exit_condition) = build (GE_EXPR,
+ boolean_type_node,
+ uboundvar,
+ ivvarinced);
+ update_stmt (exit_condition);
+ bbs = get_loop_body_in_dom_order (loop);
+ /* Now move the statements, and replace the induction variable in the moved
+ statements with the correct loop induction variable. */
+ oldivvar = VEC_index (tree, loopivs, 0);
+ for (i = loop->num_nodes - 1; i >= 0 ; i--)
{
block_stmt_iterator tobsi = bsi_last (bodybb);
if (bbs[i]->loop_father == loop)
{
- /* Note that the bsi only needs to be explicitly incremented
- when we don't move something, since it is automatically
- incremented when we do. */
- for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi);)
+ /* If this is true, we are *before* the inner loop.
+ If this isn't true, we are *after* it.
+
+ The only time can_convert_to_perfect_nest returns true when we
+ have statements before the inner loop is if they can be moved
+ into the inner loop.
+
+ The only time can_convert_to_perfect_nest returns true when we
+ have statements after the inner loop is if they can be moved into
+ the new split loop. */
+
+ if (dominated_by_p (CDI_DOMINATORS, loop->inner->header, bbs[i]))
+ {
+ for (bsi = bsi_last (bbs[i]); !bsi_end_p (bsi);)
+ {
+ use_operand_p use_p;
+ imm_use_iterator imm_iter;
+ tree stmt = bsi_stmt (bsi);
+
+ if (stmt == exit_condition
+ || not_interesting_stmt (stmt)
+ || stmt_is_bumper_for_loop (loop, stmt))
+ {
+ if (!bsi_end_p (bsi))
+ bsi_prev (&bsi);
+ continue;
+ }
+ /* Move this statement back into the inner loop.
+ This looks a bit confusing, but we are really just
+ finding the first non-exit phi use and moving the
+ statement to the beginning of that use's basic
+ block. */
+ FOR_EACH_IMM_USE_SAFE (use_p, imm_iter,
+ TREE_OPERAND (stmt, 0))
+ {
+ tree imm_stmt = USE_STMT (use_p);
+ if (!exit_phi_for_loop_p (loop->inner, imm_stmt))
+ {
+ block_stmt_iterator tobsi = bsi_after_labels (bb_for_stmt (imm_stmt));
+ bsi_move_after (&bsi, &tobsi);
+ update_stmt (stmt);
+ BREAK_FROM_SAFE_IMM_USE (imm_iter);
+ }
+ }
+ }
+ }
+ else
{
- tree stmt = bsi_stmt (bsi);
- if (stmt == exit_condition
- || not_interesting_stmt (stmt)
- || stmt_is_bumper_for_loop (loop, stmt))
- {
- bsi_next (&bsi);
- continue;
+ /* Note that the bsi only needs to be explicitly incremented
+ when we don't move something, since it is automatically
+ incremented when we do. */
+ for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi);)
+ {
+ ssa_op_iter i;
+ tree n, stmt = bsi_stmt (bsi);
+
+ if (stmt == exit_condition
+ || not_interesting_stmt (stmt)
+ || stmt_is_bumper_for_loop (loop, stmt))
+ {
+ bsi_next (&bsi);
+ continue;
+ }
+
+ replace_uses_equiv_to_x_with_y (loop, stmt,
+ oldivvar,
+ VEC_index (int, steps, 0),
+ ivvar);
+ bsi_move_before (&bsi, &tobsi);
+
+ /* If the statement has any virtual operands, they may
+ need to be rewired because the original loop may
+ still reference them. */
+ FOR_EACH_SSA_TREE_OPERAND (n, stmt, i, SSA_OP_ALL_VIRTUALS)
+ mark_sym_for_renaming (SSA_NAME_VAR (n));
}
- replace_uses_of_x_with_y (stmt,
- VEC_index (tree, loopivs, 0),
- ivvar);
- bsi_move_before (&bsi, &tobsi);
}
+
}
}
+
free (bbs);
- flow_loops_find (loops, LOOP_ALL);
return perfect_nest_p (loop);
}
lambda_vector distres;
struct data_dependence_relation *ddr;
-#if defined ENABLE_CHECKING
- if (LTM_COLSIZE (trans) != nb_loops
- || LTM_ROWSIZE (trans) != nb_loops)
- abort ();
-#endif
+ gcc_assert (LTM_COLSIZE (trans) == nb_loops
+ && LTM_ROWSIZE (trans) == nb_loops);
/* When there is an unknown relation in the dependence_relations, we
know that it is no worth looking at this loop nest: give up. */
for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
{
ddr = (struct data_dependence_relation *)
- VARRAY_GENERIC_PTR (dependence_relations, i);
-
-
+ VARRAY_GENERIC_PTR (dependence_relations, i);
/* Don't care about relations for which we know that there is no
dependence, nor about read-read (aka. output-dependences):
if (DDR_ARE_DEPENDENT (ddr) == chrec_known
|| (DR_IS_READ (DDR_A (ddr)) && DR_IS_READ (DDR_B (ddr))))
continue;
+
/* Conservatively answer: "this transformation is not valid". */
if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
return false;
+
+ /* If the dependence could not be captured by a distance vector,
+ conservatively answer that the transform is not valid. */
+ if (DDR_DIST_VECT (ddr) == NULL)
+ return false;
/* Compute trans.dist_vect */
lambda_matrix_vector_mult (LTM_MATRIX (trans), nb_loops, nb_loops,
OSDN Git Service
