/* Loop transformation code generation
- Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
+ Free Software Foundation, Inc.
Contributed by Daniel Berlin <dberlin@dberlin.org>
This file is part of GCC.
-
+
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.
-
+
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
-
+
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
#include "target.h"
#include "rtl.h"
#include "basic-block.h"
-#include "diagnostic.h"
+#include "diagnostic-core.h"
#include "obstack.h"
#include "tree-flow.h"
#include "tree-dump.h"
/* This loop nest code generation is based on non-singular matrix
math.
-
+
A little terminology and a general sketch of the algorithm. See "A singular
loop transformation framework based on non-singular matrices" by Wei Li and
Keshav Pingali for formal proofs that the various statements below are
- correct.
+ correct.
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 an integral combinations of a set
- of basis vectors.
+ of basis vectors.
A loop iteration space is dense if every integer point between the loop
bounds is a point in the iteration space. Every loop with a step of 1
therefore has a dense iteration space.
for i = 1 to 3, step 1 is a dense iteration space.
-
+
A loop iteration space is sparse if it is not dense. That is, the iteration
- space skips integer points that are within the loop bounds.
+ space skips integer points that are within the loop bounds.
for i = 1 to 3, step 2 is a sparse iteration space, because the integer point
2 is skipped.
space using min/max and floor/ceil.
For a dense source space, we take the transformation matrix, decompose it
- into a lower triangular part (H) and a unimodular part (U).
+ into a lower triangular part (H) and a unimodular part (U).
We then compute the auxiliary space from the unimodular part (source loop
nest . U = auxiliary space) , which has two important properties:
1. It traverses the iterations in the same lexicographic order as the source
space.
2. It is a dense space when the source is a dense space (even if the target
space is going to be sparse).
-
+
Given the auxiliary space, we use the lower triangular part to compute the
bounds in the target space by simple matrix multiplication.
The gaps in the target space (IE the new loop step sizes) will be the
are closed under composition, this is okay). We can then use the base space
(which is dense) plus the composed transformation matrix, to compute the rest
of the transform using the dense space algorithm above.
-
+
In other words, our sparse source space (B) is decomposed into a dense base
space (A), and a matrix (L) that transforms A into B, such that A.L = B.
We then compute the composition of L and the user transformation matrix (T),
so that T is now a transform from A to the result, instead of from B to the
- result.
+ result.
IE A.(LT) = result instead of B.T = result
Since A is now a dense source space, we can use the dense source space
algorithm above to compute the result of applying transform (LT) to A.
Fourier-Motzkin elimination is used to compute the bounds of the base space
of the lattice. */
-static bool perfect_nestify (struct loop *, VEC(tree,heap) *,
+static bool perfect_nestify (struct loop *, VEC(tree,heap) *,
VEC(tree,heap) *, VEC(int,heap) *,
VEC(tree,heap) *);
/* Lattice stuff that is internal to the code generation algorithm. */
static lambda_lattice lambda_lattice_compute_base (lambda_loopnest,
struct obstack *);
-static tree find_induction_var_from_exit_cond (struct loop *);
static bool can_convert_to_perfect_nest (struct loop *);
+/* Create a new lambda loop in LAMBDA_OBSTACK. */
+
+static lambda_loop
+lambda_loop_new (struct obstack * lambda_obstack)
+{
+ lambda_loop result = (lambda_loop)
+ obstack_alloc (lambda_obstack, sizeof (struct lambda_loop_s));
+ memset (result, 0, sizeof (struct lambda_loop_s));
+ return result;
+}
+
/* Create a new lambda body vector. */
lambda_body_vector
{
lambda_body_vector ret;
- ret = (lambda_body_vector)obstack_alloc (lambda_obstack, sizeof (*ret));
+ ret = (lambda_body_vector) obstack_alloc (lambda_obstack,
+ sizeof (*ret));
LBV_COEFFICIENTS (ret) = lambda_vector_new (size);
LBV_SIZE (ret) = size;
LBV_DENOMINATOR (ret) = 1;
}
/* Print a lambda loop structure LOOP to OUTFILE. The depth/number of
- coefficients is given by DEPTH, the number of invariants is
+ coefficients is given by DEPTH, the number of invariants is
given by INVARIANTS, and the character to start variable names with is given
by START. */
{
lambda_lattice ret
= (lambda_lattice)obstack_alloc (lambda_obstack, sizeof (*ret));
- LATTICE_BASE (ret) = lambda_matrix_new (depth, depth);
+ LATTICE_BASE (ret) = lambda_matrix_new (depth, depth, lambda_obstack);
LATTICE_ORIGIN (ret) = lambda_vector_new (depth);
- LATTICE_ORIGIN_INVARIANTS (ret) = lambda_matrix_new (depth, invariants);
+ LATTICE_ORIGIN_INVARIANTS (ret) = lambda_matrix_new (depth, invariants,
+ lambda_obstack);
LATTICE_DIMENSION (ret) = depth;
LATTICE_INVARIANTS (ret) = invariants;
return ret;
/* 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
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.
-
+ 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.
-
+ 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
+static lambda_loopnest
compute_nest_using_fourier_motzkin (int size,
- int depth,
+ int depth,
int invariants,
lambda_matrix A,
lambda_matrix B,
lambda_vector swapvector, a1;
int newsize;
- A1 = lambda_matrix_new (128, depth);
- B1 = lambda_matrix_new (128, invariants);
+ A1 = lambda_matrix_new (128, depth, lambda_obstack);
+ B1 = lambda_matrix_new (128, invariants, lambda_obstack);
a1 = lambda_vector_new (128);
auxillary_nest = lambda_loopnest_new (depth, invariants, lambda_obstack);
for (i = depth - 1; i >= 0; i--)
{
- loop = lambda_loop_new ();
+ loop = lambda_loop_new (lambda_obstack);
LN_LOOPS (auxillary_nest)[i] = loop;
LL_STEP (loop) = 1;
if (A[j][i] < 0)
{
/* Any linear expression in the matrix with a coefficient less
- than 0 becomes part of the new lower bound. */
+ than 0 becomes part of the new lower bound. */
expression = lambda_linear_expression_new (depth, invariants,
lambda_obstack);
else if (A[j][i] > 0)
{
/* Any linear expression with a coefficient greater than 0
- becomes part of the new upper bound. */
+ becomes part of the new upper bound. */
expression = lambda_linear_expression_new (depth, invariants,
lambda_obstack);
for (k = 0; k < i; k++)
}
/* Compute the loop bounds for the auxiliary space NEST.
- Input system used is Ax <= b. TRANS is the unimodular transformation.
- Given the original nest, this function will
+ 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.
+ 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
+ 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.
/* 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 must not go over this limit. */
- A = lambda_matrix_new (128, depth);
- B = lambda_matrix_new (128, invariants);
+ A = lambda_matrix_new (128, depth, lambda_obstack);
+ B = lambda_matrix_new (128, invariants, lambda_obstack);
a = lambda_vector_new (128);
- A1 = lambda_matrix_new (128, depth);
- B1 = lambda_matrix_new (128, invariants);
+ A1 = lambda_matrix_new (128, depth, lambda_obstack);
+ B1 = lambda_matrix_new (128, invariants, lambda_obstack);
a1 = lambda_vector_new (128);
/* Store the bounds in the equation matrix A, constant vector a, and
size++;
/* Need to increase matrix sizes above. */
gcc_assert (size <= 127);
-
+
}
/* Then do the exact same thing for the upper bounds. */
/* Now compute the auxiliary space bounds by first inverting U, multiplying
it by A1, then performing Fourier-Motzkin. */
- invertedtrans = lambda_matrix_new (depth, depth);
+ invertedtrans = lambda_matrix_new (depth, depth, lambda_obstack);
/* Compute the inverse of U. */
lambda_matrix_inverse (LTM_MATRIX (trans),
- invertedtrans, depth);
+ invertedtrans, depth, lambda_obstack);
/* A = A1 inv(U). */
lambda_matrix_mult (A1, invertedtrans, A, size, depth, depth);
}
/* Compute the loop bounds for the target space, using the bounds of
- the auxiliary nest AUXILLARY_NEST, and the triangular matrix H.
+ 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
depth = LN_DEPTH (auxillary_nest);
invariants = LN_INVARIANTS (auxillary_nest);
- inverse = lambda_matrix_new (depth, depth);
- determinant = lambda_matrix_inverse (LTM_MATRIX (H), inverse, depth);
+ inverse = lambda_matrix_new (depth, depth, lambda_obstack);
+ determinant = lambda_matrix_inverse (LTM_MATRIX (H), inverse, depth,
+ lambda_obstack);
/* H1 is H excluding its diagonal. */
- H1 = lambda_matrix_new (depth, depth);
+ H1 = lambda_matrix_new (depth, depth, lambda_obstack);
lambda_matrix_copy (LTM_MATRIX (H), H1, depth, depth);
for (i = 0; i < depth; i++)
H1[i][i] = 0;
/* Computes the linear offsets of the loop bounds. */
- target = lambda_matrix_new (depth, depth);
+ target = lambda_matrix_new (depth, depth, lambda_obstack);
lambda_matrix_mult (H1, inverse, target, depth, depth, depth);
target_nest = lambda_loopnest_new (depth, invariants, lambda_obstack);
{
/* Get a new loop structure. */
- target_loop = lambda_loop_new ();
+ target_loop = lambda_loop_new (lambda_obstack);
LN_LOOPS (target_nest)[i] = target_loop;
/* Computes the gcd of the coefficients of the linear part. */
result. */
static lambda_vector
-lambda_compute_step_signs (lambda_trans_matrix trans, lambda_vector stepsigns)
+lambda_compute_step_signs (lambda_trans_matrix trans,
+ lambda_vector stepsigns,
+ struct obstack * lambda_obstack)
{
lambda_matrix matrix, H;
int size;
matrix = LTM_MATRIX (trans);
size = LTM_ROWSIZE (trans);
- H = lambda_matrix_new (size, size);
+ H = lambda_matrix_new (size, size, lambda_obstack);
newsteps = lambda_vector_new (size);
lambda_vector_copy (stepsigns, newsteps, size);
1. Computing a lattice base for the transformation
2. Composing the dense base with the specified transformation (TRANS)
3. Decomposing the combined transformation into a lower triangular portion,
- and a unimodular portion.
+ and a unimodular portion.
4. Computing the auxiliary nest using the unimodular portion.
5. Computing the target nest using the auxiliary nest and the lower
- triangular portion. */
+ triangular portion. */
lambda_loopnest
lambda_loopnest_transform (lambda_loopnest nest, lambda_trans_matrix trans,
/* Compute the lattice base. */
lattice = lambda_lattice_compute_base (nest, lambda_obstack);
- trans1 = lambda_trans_matrix_new (depth, depth);
+ trans1 = lambda_trans_matrix_new (depth, depth, lambda_obstack);
/* Multiply the transformation matrix by the lattice base. */
LTM_MATRIX (trans1), depth, depth, depth);
/* Compute the Hermite normal form for the new transformation matrix. */
- H = lambda_trans_matrix_new (depth, depth);
- U = lambda_trans_matrix_new (depth, depth);
+ H = lambda_trans_matrix_new (depth, depth, lambda_obstack);
+ U = lambda_trans_matrix_new (depth, depth, lambda_obstack);
lambda_matrix_hermite (LTM_MATRIX (trans1), depth, LTM_MATRIX (H),
LTM_MATRIX (U));
/* Compute the auxiliary loop nest's space from the unimodular
portion. */
- auxillary_nest = lambda_compute_auxillary_space (nest, U, lambda_obstack);
+ auxillary_nest = lambda_compute_auxillary_space (nest, U,
+ lambda_obstack);
/* Compute the loop step signs from the old step signs and the
transformation matrix. */
- stepsigns = lambda_compute_step_signs (trans1, stepsigns);
+ stepsigns = lambda_compute_step_signs (trans1, stepsigns,
+ lambda_obstack);
/* Compute the target loop nest space from the auxiliary nest and
the lower triangular matrix H. */
target_nest = lambda_compute_target_space (auxillary_nest, H, stepsigns,
lambda_obstack);
origin = lambda_vector_new (depth);
- origin_invariants = lambda_matrix_new (depth, invariants);
+ origin_invariants = lambda_matrix_new (depth, invariants, lambda_obstack);
lambda_matrix_vector_mult (LTM_MATRIX (trans), depth, depth,
LATTICE_ORIGIN (lattice), origin);
lambda_matrix_mult (LTM_MATRIX (trans), LATTICE_ORIGIN_INVARIANTS (lattice),
/* Return the depth of the loopnest NEST */
-static int
+static int
depth_of_nest (struct loop *nest)
{
size_t depth = 0;
VEC(tree,heap) * outerinductionvars,
VEC(tree,heap) ** lboundvars,
VEC(tree,heap) ** uboundvars,
- VEC(int,heap) ** steps,
+ VEC(int,heap) ** steps,
struct obstack * lambda_obstack)
{
- tree phi;
- tree exit_cond;
+ gimple phi;
+ gimple exit_cond;
tree access_fn, inductionvar;
tree step;
lambda_loop lloop = NULL;
lambda_linear_expression lbound, ubound;
- tree test;
+ tree test_lhs, test_rhs;
int stepint;
int extra = 0;
tree lboundvar, uboundvar, uboundresult;
return NULL;
}
- test = TREE_OPERAND (exit_cond, 0);
-
- if (SSA_NAME_DEF_STMT (inductionvar) == NULL_TREE)
+ if (SSA_NAME_DEF_STMT (inductionvar) == NULL)
{
if (dump_file && (dump_flags & TDF_DETAILS))
}
phi = SSA_NAME_DEF_STMT (inductionvar);
- if (TREE_CODE (phi) != PHI_NODE)
+ if (gimple_code (phi) != GIMPLE_PHI)
{
- phi = SINGLE_SSA_TREE_OPERAND (phi, SSA_OP_USE);
- if (!phi)
+ tree op = SINGLE_SSA_TREE_OPERAND (phi, SSA_OP_USE);
+ if (!op)
{
if (dump_file && (dump_flags & TDF_DETAILS))
return NULL;
}
- phi = SSA_NAME_DEF_STMT (phi);
- if (TREE_CODE (phi) != PHI_NODE)
+ phi = SSA_NAME_DEF_STMT (op);
+ if (gimple_code (phi) != GIMPLE_PHI)
{
-
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
"Unable to convert loop: Cannot find PHI node for induction variable\n");
return NULL;
}
-
}
/* The induction variable name/version we want to put in the array is the
/* Only want phis for induction vars, which will have two
arguments. */
- if (PHI_NUM_ARGS (phi) != 2)
+ if (gimple_phi_num_args (phi) != 2)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
/* Another induction variable check. One argument's source should be
in the loop, one outside the loop. */
- if (flow_bb_inside_loop_p (loop, PHI_ARG_EDGE (phi, 0)->src)
- && flow_bb_inside_loop_p (loop, PHI_ARG_EDGE (phi, 1)->src))
+ if (flow_bb_inside_loop_p (loop, gimple_phi_arg_edge (phi, 0)->src)
+ && flow_bb_inside_loop_p (loop, gimple_phi_arg_edge (phi, 1)->src))
{
if (dump_file && (dump_flags & TDF_DETAILS))
return NULL;
}
- if (flow_bb_inside_loop_p (loop, PHI_ARG_EDGE (phi, 0)->src))
+ if (flow_bb_inside_loop_p (loop, gimple_phi_arg_edge (phi, 0)->src))
{
lboundvar = PHI_ARG_DEF (phi, 1);
lbound = gcc_tree_to_linear_expression (depth, lboundvar,
outerinductionvars, *invariants,
0, lambda_obstack);
}
-
+
if (!lbound)
{
}
/* 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_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_and_outer_loops (loop, TREE_OPERAND (test, 0)))
- VEC_quick_push (tree, *invariants, TREE_OPERAND (test, 0));
-
+ test_lhs = gimple_cond_lhs (exit_cond);
+ test_rhs = gimple_cond_rhs (exit_cond);
+
+ if (TREE_CODE (test_rhs) == SSA_NAME
+ && invariant_in_loop_and_outer_loops (loop, test_rhs))
+ VEC_quick_push (tree, *invariants, test_rhs);
+ else if (TREE_CODE (test_lhs) == SSA_NAME
+ && invariant_in_loop_and_outer_loops (loop, test_lhs))
+ VEC_quick_push (tree, *invariants, test_lhs);
+
/* The non-induction variable part of the test is the upper bound variable.
*/
- if (TREE_OPERAND (test, 0) == inductionvar)
- uboundvar = TREE_OPERAND (test, 1);
+ if (test_lhs == inductionvar)
+ uboundvar = test_rhs;
else
- uboundvar = TREE_OPERAND (test, 0);
-
+ uboundvar = test_lhs;
/* We only size the vectors assuming we have, at max, 2 times as many
invariants as we do loops (one for each bound).
This is just an arbitrary number, but it has to be matched against the
code below. */
gcc_assert (VEC_length (tree, *invariants) <= (unsigned int) (2 * depth));
-
+
/* We might have some leftover. */
- if (TREE_CODE (test) == LT_EXPR)
+ if (gimple_cond_code (exit_cond) == LT_EXPR)
extra = -1 * stepint;
- else if (TREE_CODE (test) == NE_EXPR)
+ else if (gimple_cond_code (exit_cond) == NE_EXPR)
extra = -1 * stepint;
- else if (TREE_CODE (test) == GT_EXPR)
+ else if (gimple_cond_code (exit_cond) == GT_EXPR)
extra = -1 * stepint;
- else if (TREE_CODE (test) == EQ_EXPR)
+ else if (gimple_cond_code (exit_cond) == EQ_EXPR)
extra = 1 * stepint;
-
+
ubound = gcc_tree_to_linear_expression (depth, uboundvar,
outerinductionvars,
*invariants, extra, lambda_obstack);
return NULL;
}
- lloop = lambda_loop_new ();
+ lloop = lambda_loop_new (lambda_obstack);
LL_STEP (lloop) = stepint;
LL_LOWER_BOUND (lloop) = lbound;
LL_UPPER_BOUND (lloop) = ubound;
/* Given a LOOP, find the induction variable it is testing against in the exit
condition. Return the induction variable if found, NULL otherwise. */
-static tree
+tree
find_induction_var_from_exit_cond (struct loop *loop)
{
- tree expr = get_loop_exit_condition (loop);
+ gimple expr = get_loop_exit_condition (loop);
tree ivarop;
- tree test;
- if (expr == NULL_TREE)
+ tree test_lhs, test_rhs;
+ if (expr == NULL)
return NULL_TREE;
- if (TREE_CODE (expr) != COND_EXPR)
- return NULL_TREE;
- test = TREE_OPERAND (expr, 0);
- if (!COMPARISON_CLASS_P (test))
+ if (gimple_code (expr) != GIMPLE_COND)
return NULL_TREE;
+ test_lhs = gimple_cond_lhs (expr);
+ test_rhs = gimple_cond_rhs (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);
- else if (expr_invariant_in_loop_p (loop, TREE_OPERAND (test, 1)))
- ivarop = TREE_OPERAND (test, 0);
+
+ if (expr_invariant_in_loop_p (loop, test_lhs))
+ ivarop = test_rhs;
+ else if (expr_invariant_in_loop_p (loop, test_rhs))
+ ivarop = test_lhs;
else
return NULL_TREE;
DEF_VEC_ALLOC_P(lambda_loop,heap);
/* Generate a lambda loopnest from a gcc loopnest LOOP_NEST.
- Return the new loop nest.
+ Return the new loop nest.
INDUCTIONVARS is a pointer to an array of induction variables for the
loopnest that will be filled in during this process.
INVARIANTS is a pointer to an array of invariants that will be filled in
{
if (dump_file)
fprintf (dump_file,
- "Not a perfect loop nest and couldn't convert to one.\n");
+ "Not a perfect loop nest and couldn't convert to one.\n");
goto fail;
}
else if (dump_file)
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.
+/* 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. TYPE is the tree type to use for
the variables and trees involved. */
static tree
-lbv_to_gcc_expression (lambda_body_vector lbv,
- tree type, VEC(tree,heap) *induction_vars,
- tree *stmts_to_insert)
+lbv_to_gcc_expression (lambda_body_vector lbv,
+ tree type, VEC(tree,heap) *induction_vars,
+ gimple_seq *stmts_to_insert)
{
int k;
tree resvar;
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.
+ 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
tree type,
VEC(tree,heap) *induction_vars,
VEC(tree,heap) *invariants,
- enum tree_code wrap, tree *stmts_to_insert)
+ enum tree_code wrap, gimple_seq *stmts_to_insert)
{
int k;
tree resvar;
{
expr = build_linear_expr (type, LLE_COEFFICIENTS (lle), induction_vars);
expr = fold_build2 (PLUS_EXPR, type, expr,
- build_linear_expr (type,
+ build_linear_expr (type,
LLE_INVARIANT_COEFFICIENTS (lle),
invariants));
/* Remove the induction variable defined at IV_STMT. */
void
-remove_iv (tree iv_stmt)
+remove_iv (gimple iv_stmt)
{
- if (TREE_CODE (iv_stmt) == PHI_NODE)
+ gimple_stmt_iterator si = gsi_for_stmt (iv_stmt);
+
+ if (gimple_code (iv_stmt) == GIMPLE_PHI)
{
- int i;
+ unsigned i;
- for (i = 0; i < PHI_NUM_ARGS (iv_stmt); i++)
+ for (i = 0; i < gimple_phi_num_args (iv_stmt); i++)
{
- tree stmt;
+ gimple stmt;
imm_use_iterator imm_iter;
- tree arg = PHI_ARG_DEF (iv_stmt, i);
+ tree arg = gimple_phi_arg_def (iv_stmt, i);
bool used = false;
if (TREE_CODE (arg) != SSA_NAME)
continue;
FOR_EACH_IMM_USE_STMT (stmt, imm_iter, arg)
- if (stmt != iv_stmt)
+ if (stmt != iv_stmt && !is_gimple_debug (stmt))
used = true;
if (!used)
remove_iv (SSA_NAME_DEF_STMT (arg));
}
- remove_phi_node (iv_stmt, NULL_TREE, true);
+ remove_phi_node (&si, true);
}
else
{
- block_stmt_iterator bsi = bsi_for_stmt (iv_stmt);
-
- bsi_remove (&bsi, true);
- release_defs (iv_stmt);
+ gsi_remove (&si, true);
+ release_defs (iv_stmt);
}
}
/* Transform a lambda loopnest NEW_LOOPNEST, which had TRANSFORM applied to
it, back into gcc code. This changes the
loops, their induction variables, and their bodies, so that they
- match the transformed loopnest.
+ match the transformed loopnest.
OLD_LOOPNEST is the loopnest before we've replaced it with the new
loopnest.
OLD_IVS is a vector of induction variables from the old loopnest.
INVARIANTS is a vector of loop invariants from the old loopnest.
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
+ TRANSFORM is the matrix transform that was applied to OLD_LOOPNEST to get
NEW_LOOPNEST. */
-void
+void
lambda_loopnest_to_gcc_loopnest (struct loop *old_loopnest,
VEC(tree,heap) *old_ivs,
VEC(tree,heap) *invariants,
- VEC(tree,heap) **remove_ivs,
+ VEC(gimple,heap) **remove_ivs,
lambda_loopnest new_loopnest,
lambda_trans_matrix transform,
struct obstack * lambda_obstack)
{
struct loop *temp;
size_t i = 0;
- int j;
+ unsigned j;
size_t depth = 0;
VEC(tree,heap) *new_ivs = NULL;
tree oldiv;
- block_stmt_iterator bsi;
+ gimple_stmt_iterator bsi;
- transform = lambda_trans_matrix_inverse (transform);
+ transform = lambda_trans_matrix_inverse (transform, lambda_obstack);
if (dump_file)
{
lambda_loop newloop;
basic_block bb;
edge exit;
- tree ivvar, ivvarinced, exitcond, stmts;
+ tree ivvar, ivvarinced;
+ gimple exitcond;
+ gimple_seq stmts;
enum tree_code testtype;
tree newupperbound, newlowerbound;
lambda_linear_expression offset;
tree type;
bool insert_after;
- tree inc_stmt;
+ gimple inc_stmt;
oldiv = VEC_index (tree, old_ivs, i);
type = TREE_TYPE (oldiv);
/* 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. */
+ stmts = NULL;
newlowerbound = lle_to_gcc_expression (LL_LOWER_BOUND (newloop),
LL_LINEAR_OFFSET (newloop),
type,
if (stmts)
{
- bsi_insert_on_edge (loop_preheader_edge (temp), stmts);
- bsi_commit_edge_inserts ();
+ gsi_insert_seq_on_edge (loop_preheader_edge (temp), stmts);
+ gsi_commit_edge_inserts ();
}
/* Build the new upper bound and insert its statements in the
basic block of the exit condition */
+ stmts = NULL;
newupperbound = lle_to_gcc_expression (LL_UPPER_BOUND (newloop),
LL_LINEAR_OFFSET (newloop),
type,
invariants, MIN_EXPR, &stmts);
exit = single_exit (temp);
exitcond = get_loop_exit_condition (temp);
- bb = bb_for_stmt (exitcond);
- bsi = bsi_after_labels (bb);
+ bb = gimple_bb (exitcond);
+ bsi = gsi_after_labels (bb);
if (stmts)
- bsi_insert_before (&bsi, stmts, BSI_NEW_STMT);
+ gsi_insert_seq_before (&bsi, stmts, GSI_NEW_STMT);
/* Create the new iv. */
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 = build2 (PLUS_EXPR, type,
- ivvar, build_int_cst (type, LL_STEP (newloop)));
- inc_stmt = build_gimple_modify_stmt (SSA_NAME_VAR (ivvar), inc_stmt);
+ inc_stmt = gimple_build_assign_with_ops (PLUS_EXPR, SSA_NAME_VAR (ivvar),
+ ivvar,
+ build_int_cst (type, LL_STEP (newloop)));
+
ivvarinced = make_ssa_name (SSA_NAME_VAR (ivvar), inc_stmt);
- GIMPLE_STMT_OPERAND (inc_stmt, 0) = ivvarinced;
- bsi = bsi_for_stmt (exitcond);
- bsi_insert_before (&bsi, inc_stmt, BSI_SAME_STMT);
+ gimple_assign_set_lhs (inc_stmt, ivvarinced);
+ bsi = gsi_for_stmt (exitcond);
+ gsi_insert_before (&bsi, inc_stmt, GSI_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) = build2 (testtype,
- boolean_type_node,
- newupperbound, ivvarinced);
+ gimple_cond_set_condition (exitcond, testtype, newupperbound, ivvarinced);
update_stmt (exitcond);
VEC_replace (tree, new_ivs, i, ivvar);
imm_use_iterator imm_iter;
use_operand_p use_p;
tree oldiv_def;
- tree oldiv_stmt = SSA_NAME_DEF_STMT (oldiv);
- tree stmt;
+ gimple oldiv_stmt = SSA_NAME_DEF_STMT (oldiv);
+ gimple stmt;
- if (TREE_CODE (oldiv_stmt) == PHI_NODE)
+ if (gimple_code (oldiv_stmt) == GIMPLE_PHI)
oldiv_def = PHI_RESULT (oldiv_stmt);
else
oldiv_def = SINGLE_SSA_TREE_OPERAND (oldiv_stmt, SSA_OP_DEF);
FOR_EACH_IMM_USE_STMT (stmt, imm_iter, oldiv_def)
{
- tree newiv, stmts;
+ tree newiv;
+ gimple_seq stmts;
lambda_body_vector lbv, newlbv;
+ if (is_gimple_debug (stmt))
+ continue;
+
/* Compute the new expression for the induction
variable. */
depth = VEC_length (tree, new_ivs);
lbv = lambda_body_vector_new (depth, lambda_obstack);
LBV_COEFFICIENTS (lbv)[i] = 1;
-
+
newlbv = lambda_body_vector_compute_new (transform, lbv,
lambda_obstack);
+ stmts = NULL;
newiv = lbv_to_gcc_expression (newlbv, TREE_TYPE (oldiv),
new_ivs, &stmts);
- if (stmts && TREE_CODE (stmt) != PHI_NODE)
+ if (stmts && gimple_code (stmt) != GIMPLE_PHI)
{
- bsi = bsi_for_stmt (stmt);
- bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
+ bsi = gsi_for_stmt (stmt);
+ gsi_insert_seq_before (&bsi, stmts, GSI_SAME_STMT);
}
FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
propagate_value (use_p, newiv);
- if (stmts && TREE_CODE (stmt) == PHI_NODE)
- for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
- if (PHI_ARG_DEF (stmt, j) == newiv)
- bsi_insert_on_edge (PHI_ARG_EDGE (stmt, j), stmts);
+ if (stmts && gimple_code (stmt) == GIMPLE_PHI)
+ for (j = 0; j < gimple_phi_num_args (stmt); j++)
+ if (gimple_phi_arg_def (stmt, j) == newiv)
+ gsi_insert_seq_on_edge (gimple_phi_arg_edge (stmt, j), stmts);
update_stmt (stmt);
}
/* Remove the now unused induction variable. */
- VEC_safe_push (tree, heap, *remove_ivs, oldiv_stmt);
+ VEC_safe_push (gimple, heap, *remove_ivs, oldiv_stmt);
}
VEC_free (tree, heap, new_ivs);
}
determining if we have a perfect loop nest. */
static bool
-not_interesting_stmt (tree stmt)
+not_interesting_stmt (gimple stmt)
{
/* Note that COND_EXPR's aren't interesting because if they were exiting the
loop, we would have already failed the number of exits tests. */
- if (TREE_CODE (stmt) == LABEL_EXPR
- || TREE_CODE (stmt) == GOTO_EXPR
- || TREE_CODE (stmt) == COND_EXPR)
+ if (gimple_code (stmt) == GIMPLE_LABEL
+ || gimple_code (stmt) == GIMPLE_GOTO
+ || gimple_code (stmt) == GIMPLE_COND
+ || is_gimple_debug (stmt))
return true;
return false;
}
/* Return TRUE if PHI uses DEF for it's in-the-loop edge for LOOP. */
static bool
-phi_loop_edge_uses_def (struct loop *loop, tree phi, tree def)
+phi_loop_edge_uses_def (struct loop *loop, gimple phi, tree def)
{
- int i;
- for (i = 0; i < PHI_NUM_ARGS (phi); i++)
- if (flow_bb_inside_loop_p (loop, PHI_ARG_EDGE (phi, i)->src))
+ unsigned i;
+ for (i = 0; i < gimple_phi_num_args (phi); i++)
+ if (flow_bb_inside_loop_p (loop, gimple_phi_arg_edge (phi, i)->src))
if (PHI_ARG_DEF (phi, i) == def)
return true;
return false;
/* Return TRUE if STMT is a use of PHI_RESULT. */
static bool
-stmt_uses_phi_result (tree stmt, tree phi_result)
+stmt_uses_phi_result (gimple stmt, tree phi_result)
{
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. */
return (use == phi_result);
/* STMT is a bumper stmt for LOOP if the version it defines is used in the
in-loop-edge in a phi node, and the operand it uses is the result of that
- phi node.
+ phi node.
I.E. i_29 = i_3 + 1
i_3 = PHI (0, i_29); */
static bool
-stmt_is_bumper_for_loop (struct loop *loop, tree stmt)
+stmt_is_bumper_for_loop (struct loop *loop, gimple stmt)
{
- tree use;
+ gimple use;
tree def;
imm_use_iterator iter;
use_operand_p use_p;
-
+
def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
if (!def)
return false;
FOR_EACH_IMM_USE_FAST (use_p, iter, def)
{
use = USE_STMT (use_p);
- if (TREE_CODE (use) == PHI_NODE)
+ if (gimple_code (use) == GIMPLE_PHI)
{
if (phi_loop_edge_uses_def (loop, use, def))
if (stmt_uses_phi_result (stmt, PHI_RESULT (use)))
return true;
- }
+ }
}
return false;
}
innermost loop body.
If S is a program statement, then
- i.e.
+ i.e.
DO I = 1, 20
S1
DO J = 1, 20
END DO
END DO
is not a perfect loop nest because of S1.
-
+
DO I = 1, 20
DO J = 1, 20
S1
...
END DO
- END DO
- is a perfect loop nest.
+ END DO
+ is a perfect loop nest.
Since we don't have high level loops anymore, we basically have to walk our
statements and ignore those that are there because the loop needs them (IE
{
basic_block *bbs;
size_t i;
- tree exit_cond;
+ gimple exit_cond;
/* Loops at depth 0 are perfect nests. */
if (!loop->inner)
{
if (bbs[i]->loop_father == loop)
{
- block_stmt_iterator bsi;
+ gimple_stmt_iterator bsi;
- for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi))
+ for (bsi = gsi_start_bb (bbs[i]); !gsi_end_p (bsi); gsi_next (&bsi))
{
- tree stmt = bsi_stmt (bsi);
+ gimple stmt = gsi_stmt (bsi);
- if (TREE_CODE (stmt) == COND_EXPR
+ if (gimple_code (stmt) == GIMPLE_COND
&& exit_cond != stmt)
goto non_perfectly_nested;
of body basic block. */
static void
-replace_uses_equiv_to_x_with_y (struct loop *loop, tree stmt, tree x,
+replace_uses_equiv_to_x_with_y (struct loop *loop, gimple stmt, tree x,
int xstep, tree y, tree yinit,
htab_t replacements,
- block_stmt_iterator *firstbsi)
+ gimple_stmt_iterator *firstbsi)
{
ssa_op_iter iter;
use_operand_p use_p;
{
tree use = USE_FROM_PTR (use_p);
tree step = NULL_TREE;
- tree scev, init, val, var, setstmt;
+ tree scev, init, val, var;
+ gimple setstmt;
struct tree_map *h, in;
void **loc;
which sets Y. */
var = create_tmp_var (TREE_TYPE (use), "perfecttmp");
add_referenced_var (var);
- val = force_gimple_operand_bsi (firstbsi, val, false, NULL,
- true, BSI_SAME_STMT);
- setstmt = build_gimple_modify_stmt (var, val);
+ val = force_gimple_operand_gsi (firstbsi, val, false, NULL,
+ true, GSI_SAME_STMT);
+ setstmt = gimple_build_assign (var, val);
var = make_ssa_name (var, setstmt);
- GIMPLE_STMT_OPERAND (setstmt, 0) = var;
- bsi_insert_before (firstbsi, setstmt, BSI_SAME_STMT);
+ gimple_assign_set_lhs (setstmt, var);
+ gsi_insert_before (firstbsi, setstmt, GSI_SAME_STMT);
update_stmt (setstmt);
SET_USE (use_p, var);
- h = GGC_NEW (struct tree_map);
+ h = ggc_alloc_tree_map ();
h->hash = in.hash;
h->base.from = use;
h->to = var;
/* Return true if STMT is an exit PHI for LOOP */
static bool
-exit_phi_for_loop_p (struct loop *loop, tree stmt)
+exit_phi_for_loop_p (struct loop *loop, gimple stmt)
{
-
- if (TREE_CODE (stmt) != PHI_NODE
- || PHI_NUM_ARGS (stmt) != 1
- || bb_for_stmt (stmt) != single_exit (loop)->dest)
+ if (gimple_code (stmt) != GIMPLE_PHI
+ || gimple_phi_num_args (stmt) != 1
+ || gimple_bb (stmt) != single_exit (loop)->dest)
return false;
-
+
return true;
}
copying it to the beginning of that loop and changing the uses. */
static bool
-can_put_in_inner_loop (struct loop *inner, tree stmt)
+can_put_in_inner_loop (struct loop *inner, gimple stmt)
{
imm_use_iterator imm_iter;
use_operand_p use_p;
-
- gcc_assert (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
- if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)
- || !expr_invariant_in_loop_p (inner, GIMPLE_STMT_OPERAND (stmt, 1)))
+
+ gcc_assert (is_gimple_assign (stmt));
+ if (gimple_vuse (stmt)
+ || !stmt_invariant_in_loop_p (inner, stmt))
return false;
-
- FOR_EACH_IMM_USE_FAST (use_p, imm_iter, GIMPLE_STMT_OPERAND (stmt, 0))
+
+ FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_assign_lhs (stmt))
{
if (!exit_phi_for_loop_p (inner, USE_STMT (use_p)))
{
- basic_block immbb = bb_for_stmt (USE_STMT (use_p));
+ basic_block immbb = gimple_bb (USE_STMT (use_p));
if (!flow_bb_inside_loop_p (inner, immbb))
return false;
}
}
- return true;
+ return true;
}
/* Return true if STMT can be put *after* the inner loop of LOOP. */
+
static bool
-can_put_after_inner_loop (struct loop *loop, tree stmt)
+can_put_after_inner_loop (struct loop *loop, gimple stmt)
{
imm_use_iterator imm_iter;
use_operand_p use_p;
- if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
+ if (gimple_vuse (stmt))
return false;
-
- FOR_EACH_IMM_USE_FAST (use_p, imm_iter, GIMPLE_STMT_OPERAND (stmt, 0))
+
+ FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_assign_lhs (stmt))
{
if (!exit_phi_for_loop_p (loop, USE_STMT (use_p)))
{
- basic_block immbb = bb_for_stmt (USE_STMT (use_p));
-
+ basic_block immbb = gimple_bb (USE_STMT (use_p));
+
if (!dominated_by_p (CDI_DOMINATORS,
immbb,
loop->inner->header)
it has better cache behavior. */
static bool
-cannot_convert_modify_to_perfect_nest (tree stmt, struct loop *loop)
+cannot_convert_modify_to_perfect_nest (gimple stmt, struct loop *loop)
{
-
use_operand_p use_a, use_b;
imm_use_iterator imm_iter;
ssa_op_iter op_iter, op_iter1;
- tree op0 = GIMPLE_STMT_OPERAND (stmt, 0);
+ tree op0 = gimple_assign_lhs (stmt);
/* The statement should not define a variable used in the inner
loop. */
if (TREE_CODE (op0) == SSA_NAME
&& !can_duplicate_iv (op0, loop))
FOR_EACH_IMM_USE_FAST (use_a, imm_iter, op0)
- if (bb_for_stmt (USE_STMT (use_a))->loop_father
- == loop->inner)
+ if (gimple_bb (USE_STMT (use_a))->loop_father == loop->inner)
return true;
FOR_EACH_SSA_USE_OPERAND (use_a, stmt, op_iter, SSA_OP_USE)
{
- tree node, op = USE_FROM_PTR (use_a);
+ gimple node;
+ tree op = USE_FROM_PTR (use_a);
/* The variables should not be used in both loops. */
if (!can_duplicate_iv (op, loop))
FOR_EACH_IMM_USE_FAST (use_b, imm_iter, op)
- if (bb_for_stmt (USE_STMT (use_b))->loop_father
- == loop->inner)
+ if (gimple_bb (USE_STMT (use_b))->loop_father == loop->inner)
return true;
/* The statement should not use the value of a scalar that was
modified in the loop. */
node = SSA_NAME_DEF_STMT (op);
- if (TREE_CODE (node) == PHI_NODE)
+ if (gimple_code (node) == GIMPLE_PHI)
FOR_EACH_PHI_ARG (use_b, node, op_iter1, SSA_OP_USE)
- {
- tree arg = USE_FROM_PTR (use_b);
+ {
+ tree arg = USE_FROM_PTR (use_b);
- if (TREE_CODE (arg) == SSA_NAME)
- {
- tree arg_stmt = SSA_NAME_DEF_STMT (arg);
+ if (TREE_CODE (arg) == SSA_NAME)
+ {
+ gimple arg_stmt = SSA_NAME_DEF_STMT (arg);
- if (bb_for_stmt (arg_stmt)
- && (bb_for_stmt (arg_stmt)->loop_father
- == loop->inner))
- return true;
- }
- }
+ if (gimple_bb (arg_stmt)
+ && (gimple_bb (arg_stmt)->loop_father == loop->inner))
+ return true;
+ }
+ }
}
return false;
}
-
/* Return true when BB contains statements that can harm the transform
to a perfect loop nest. */
static bool
cannot_convert_bb_to_perfect_nest (basic_block bb, struct loop *loop)
{
- block_stmt_iterator bsi;
- tree exit_condition = get_loop_exit_condition (loop);
+ gimple_stmt_iterator bsi;
+ gimple exit_condition = get_loop_exit_condition (loop);
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- {
- tree stmt = bsi_stmt (bsi);
+ for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+ {
+ gimple stmt = gsi_stmt (bsi);
if (stmt == exit_condition
|| not_interesting_stmt (stmt)
|| stmt_is_bumper_for_loop (loop, stmt))
continue;
- if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
+ if (is_gimple_assign (stmt))
{
if (cannot_convert_modify_to_perfect_nest (stmt, loop))
return true;
- if (can_duplicate_iv (GIMPLE_STMT_OPERAND (stmt, 0), loop))
+ if (can_duplicate_iv (gimple_assign_lhs (stmt), loop))
continue;
if (can_put_in_inner_loop (loop->inner, stmt)
right now. This test ensures that the statement comes
completely *after* the inner loop. */
if (!dominated_by_p (CDI_DOMINATORS,
- bb_for_stmt (stmt),
+ gimple_bb (stmt),
loop->inner->header))
return true;
}
return false;
}
+
/* Return TRUE if LOOP is an imperfect nest that we can convert to a
perfect one. At the moment, we only handle imperfect nests of
depth 2, where all of the statements occur after the inner loop. */
can_convert_to_perfect_nest (struct loop *loop)
{
basic_block *bbs;
- tree phi;
size_t i;
+ gimple_stmt_iterator si;
/* Can't handle triply nested+ loops yet. */
if (!loop->inner || loop->inner->inner)
return false;
-
+
bbs = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
if (bbs[i]->loop_father == loop
/* 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. */
- for (phi = phi_nodes (single_exit (loop)->dest); phi; phi = PHI_CHAIN (phi))
- if (PHI_NUM_ARGS (phi) != 1)
+ for (si = gsi_start_phis (single_exit (loop)->dest);
+ !gsi_end_p (si);
+ gsi_next (&si))
+ if (gimple_phi_num_args (gsi_stmt (si)) != 1)
goto fail;
-
+
free (bbs);
return true;
-
+
fail:
free (bbs);
return false;
}
+
+DEF_VEC_I(source_location);
+DEF_VEC_ALLOC_I(source_location,heap);
+
/* Transform the loop nest into a perfect nest, if possible.
LOOP is the loop nest to transform into a perfect nest
LBOUNDS are the lower bounds for the loops to transform
UBOUNDS are the upper bounds for the loops to transform
STEPS is the STEPS for the loops to transform.
LOOPIVS is the induction variables for the loops to transform.
-
+
Basically, for the case of
FOR (i = 0; i < 50; i++)
<whatever>
}
}
-
+
FOR (i = 0; i < 50; i ++)
{
<some code>
VEC(tree,heap) *loopivs)
{
basic_block *bbs;
- tree exit_condition;
- tree cond_stmt;
+ gimple exit_condition;
+ gimple cond_stmt;
basic_block preheaderbb, headerbb, bodybb, latchbb, olddest;
int i;
- block_stmt_iterator bsi, firstbsi;
+ gimple_stmt_iterator bsi, firstbsi;
bool insert_after;
edge e;
struct loop *newloop;
- tree phi;
+ gimple phi;
tree uboundvar;
- tree stmt;
+ gimple stmt;
tree oldivvar, ivvar, ivvarinced;
VEC(tree,heap) *phis = NULL;
+ VEC(source_location,heap) *locations = NULL;
htab_t replacements = NULL;
/* Create the new loop. */
olddest = single_exit (loop)->dest;
preheaderbb = split_edge (single_exit (loop));
headerbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
-
+
/* Push the exit phi nodes that we are moving. */
- for (phi = phi_nodes (olddest); phi; phi = PHI_CHAIN (phi))
+ for (bsi = gsi_start_phis (olddest); !gsi_end_p (bsi); gsi_next (&bsi))
{
+ phi = gsi_stmt (bsi);
VEC_reserve (tree, heap, phis, 2);
+ VEC_reserve (source_location, heap, locations, 1);
VEC_quick_push (tree, phis, PHI_RESULT (phi));
VEC_quick_push (tree, phis, PHI_ARG_DEF (phi, 0));
+ VEC_quick_push (source_location, locations,
+ gimple_phi_arg_location (phi, 0));
}
e = redirect_edge_and_branch (single_succ_edge (preheaderbb), headerbb);
/* Remove the exit phis from the old basic block. */
- while (phi_nodes (olddest) != NULL)
- remove_phi_node (phi_nodes (olddest), NULL, false);
+ for (bsi = gsi_start_phis (olddest); !gsi_end_p (bsi); )
+ remove_phi_node (&bsi, false);
/* and add them back to the new basic block. */
while (VEC_length (tree, phis) != 0)
{
tree def;
tree phiname;
+ source_location locus;
def = VEC_pop (tree, phis);
- phiname = VEC_pop (tree, phis);
+ phiname = VEC_pop (tree, phis);
+ locus = VEC_pop (source_location, locations);
phi = create_phi_node (phiname, preheaderbb);
- add_phi_arg (phi, def, single_pred_edge (preheaderbb));
+ add_phi_arg (phi, def, single_pred_edge (preheaderbb), locus);
}
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);
- cond_stmt = build3 (COND_EXPR, void_type_node,
- build2 (NE_EXPR, boolean_type_node,
- integer_one_node,
- integer_zero_node),
- NULL_TREE, NULL_TREE);
- bsi = bsi_start (bodybb);
- bsi_insert_after (&bsi, cond_stmt, BSI_NEW_STMT);
+ make_edge (headerbb, bodybb, EDGE_FALLTHRU);
+ cond_stmt = gimple_build_cond (NE_EXPR, integer_one_node, integer_zero_node,
+ NULL_TREE, NULL_TREE);
+ bsi = gsi_start_bb (bodybb);
+ gsi_insert_after (&bsi, cond_stmt, GSI_NEW_STMT);
e = make_edge (bodybb, olddest, EDGE_FALSE_VALUE);
make_edge (bodybb, latchbb, EDGE_TRUE_VALUE);
make_edge (latchbb, headerbb, EDGE_FALLTHRU);
/* Update the loop structures. */
- newloop = duplicate_loop (loop, olddest->loop_father);
+ newloop = duplicate_loop (loop, olddest->loop_father);
newloop->header = headerbb;
newloop->latch = latchbb;
add_bb_to_loop (latchbb, newloop);
add_bb_to_loop (headerbb, newloop);
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, preheaderbb,
single_exit (loop)->src);
set_immediate_dominator (CDI_DOMINATORS, latchbb, bodybb);
set_immediate_dominator (CDI_DOMINATORS, olddest,
standard_iv_increment_position (newloop, &bsi, &insert_after);
create_iv (VEC_index (tree, lbounds, 0),
build_int_cst (TREE_TYPE (oldivvar), VEC_index (int, steps, 0)),
- ivvar, newloop, &bsi, insert_after, &ivvar, &ivvarinced);
+ 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. */
exit_condition = get_loop_exit_condition (newloop);
- uboundvar = create_tmp_var (integer_type_node, "uboundvar");
+ uboundvar = create_tmp_var (TREE_TYPE (VEC_index (tree, ubounds, 0)),
+ "uboundvar");
add_referenced_var (uboundvar);
- stmt = build_gimple_modify_stmt (uboundvar, VEC_index (tree, ubounds, 0));
+ stmt = gimple_build_assign (uboundvar, VEC_index (tree, ubounds, 0));
uboundvar = make_ssa_name (uboundvar, stmt);
- GIMPLE_STMT_OPERAND (stmt, 0) = uboundvar;
+ gimple_assign_set_lhs (stmt, uboundvar);
if (insert_after)
- bsi_insert_after (&bsi, stmt, BSI_SAME_STMT);
+ gsi_insert_after (&bsi, stmt, GSI_SAME_STMT);
else
- bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
+ gsi_insert_before (&bsi, stmt, GSI_SAME_STMT);
update_stmt (stmt);
- COND_EXPR_COND (exit_condition) = build2 (GE_EXPR,
- boolean_type_node,
- uboundvar,
- ivvarinced);
+ gimple_cond_set_condition (exit_condition, GE_EXPR, uboundvar, ivvarinced);
update_stmt (exit_condition);
replacements = htab_create_ggc (20, tree_map_hash,
tree_map_eq, NULL);
- bbs = get_loop_body_in_dom_order (loop);
+ 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);
- firstbsi = bsi_start (bodybb);
+ firstbsi = gsi_start_bb (bodybb);
for (i = loop->num_nodes - 1; i >= 0 ; i--)
{
- block_stmt_iterator tobsi = bsi_last (bodybb);
+ gimple_stmt_iterator tobsi = gsi_last_bb (bodybb);
if (bbs[i]->loop_father == loop)
{
/* If this is true, we are *before* the inner loop.
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.
+ 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
if (dominated_by_p (CDI_DOMINATORS, loop->inner->header, bbs[i]))
{
- block_stmt_iterator header_bsi
- = bsi_after_labels (loop->inner->header);
+ gimple_stmt_iterator header_bsi
+ = gsi_after_labels (loop->inner->header);
- for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi);)
- {
- tree stmt = bsi_stmt (bsi);
+ for (bsi = gsi_start_bb (bbs[i]); !gsi_end_p (bsi);)
+ {
+ gimple stmt = gsi_stmt (bsi);
if (stmt == exit_condition
|| not_interesting_stmt (stmt)
|| stmt_is_bumper_for_loop (loop, stmt))
{
- bsi_next (&bsi);
+ gsi_next (&bsi);
continue;
}
- bsi_move_before (&bsi, &header_bsi);
+ gsi_move_before (&bsi, &header_bsi);
}
}
else
- {
+ {
/* 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);
-
+ for (bsi = gsi_start_bb (bbs[i]); !gsi_end_p (bsi);)
+ {
+ gimple stmt = gsi_stmt (bsi);
+
if (stmt == exit_condition
|| not_interesting_stmt (stmt)
|| stmt_is_bumper_for_loop (loop, stmt))
{
- bsi_next (&bsi);
+ gsi_next (&bsi);
continue;
}
-
- replace_uses_equiv_to_x_with_y
+
+ replace_uses_equiv_to_x_with_y
(loop, stmt, oldivvar, VEC_index (int, steps, 0), ivvar,
VEC_index (tree, lbounds, 0), replacements, &firstbsi);
- bsi_move_before (&bsi, &tobsi);
-
+ gsi_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));
+ if (gimple_vuse (stmt))
+ mark_sym_for_renaming (gimple_vop (cfun));
}
}
-
+
}
}
the zero vector." S.Muchnick. */
bool
-lambda_transform_legal_p (lambda_trans_matrix trans,
+lambda_transform_legal_p (lambda_trans_matrix trans,
int nb_loops,
VEC (ddr_p, heap) *dependence_relations)
{
/* 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_NUM_DIST_VECTS (ddr) == 0)
/* Compute trans.dist_vect */
for (j = 0; j < DDR_NUM_DIST_VECTS (ddr); j++)
{
- lambda_matrix_vector_mult (LTM_MATRIX (trans), nb_loops, nb_loops,
+ lambda_matrix_vector_mult (LTM_MATRIX (trans), nb_loops, nb_loops,
DDR_DIST_VECT (ddr, j), distres);
if (!lambda_vector_lexico_pos (distres, nb_loops))
for (j = 0; j < DR_NUM_DIMENSIONS (data_reference); j++)
lambda_collect_parameters_from_af (DR_ACCESS_FN (data_reference, j),
parameter_set, parameters);
+ pointer_set_destroy (parameter_set);
}
/* Translates BASE_EXPR to vector CY. AM is needed for inferring
case MULT_EXPR:
if (TREE_CODE (TREE_OPERAND (base_expr, 0)) == INTEGER_CST)
- result = av_for_af_base (TREE_OPERAND (base_expr, 1),
+ result = av_for_af_base (TREE_OPERAND (base_expr, 1),
cy, am, cst *
int_cst_value (TREE_OPERAND (base_expr, 0)));
else if (TREE_CODE (TREE_OPERAND (base_expr, 1)) == INTEGER_CST)
static bool
build_access_matrix (data_reference_p data_reference,
- VEC (tree, heap) *parameters, int loop_nest_num)
+ VEC (tree, heap) *parameters,
+ VEC (loop_p, heap) *nest,
+ struct obstack * lambda_obstack)
{
- struct access_matrix *am = GGC_NEW (struct access_matrix);
+ struct access_matrix *am = (struct access_matrix *)
+ obstack_alloc(lambda_obstack, sizeof (struct access_matrix));
unsigned i, ndim = DR_NUM_DIMENSIONS (data_reference);
- struct loop *loop = bb_for_stmt (DR_STMT (data_reference))->loop_father;
- struct loop *loop_nest = get_loop (loop_nest_num);
- unsigned nivs = loop_depth (loop) - loop_depth (loop_nest) + 1;
+ unsigned nivs = VEC_length (loop_p, nest);
unsigned lambda_nb_columns;
- lambda_vector_vec_p matrix;
- AM_LOOP_NEST_NUM (am) = loop_nest_num;
+ AM_LOOP_NEST (am) = nest;
AM_NB_INDUCTION_VARS (am) = nivs;
AM_PARAMETERS (am) = parameters;
lambda_nb_columns = AM_NB_COLUMNS (am);
- matrix = VEC_alloc (lambda_vector, heap, lambda_nb_columns);
- AM_MATRIX (am) = matrix;
+ AM_MATRIX (am) = VEC_alloc (lambda_vector, gc, ndim);
for (i = 0; i < ndim; i++)
{
if (!av_for_af (access_function, access_vector, am))
return false;
- VEC_safe_push (lambda_vector, heap, matrix, access_vector);
+ VEC_quick_push (lambda_vector, AM_MATRIX (am), access_vector);
}
DR_ACCESS_MATRIX (data_reference) = am;
bool
lambda_compute_access_matrices (VEC (data_reference_p, heap) *datarefs,
VEC (tree, heap) *parameters,
- int loop_nest_num)
+ VEC (loop_p, heap) *nest,
+ struct obstack * lambda_obstack)
{
data_reference_p dataref;
unsigned ix;
for (ix = 0; VEC_iterate (data_reference_p, datarefs, ix, dataref); ix++)
- if (!build_access_matrix (dataref, parameters, loop_nest_num))
+ if (!build_access_matrix (dataref, parameters, nest, lambda_obstack))
return false;
return true;