/* 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"
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
}
/* Perform Fourier-Motzkin elimination to calculate the bounds of the
- auxillary nest.
+ 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:
lambda_matrix A, B, A1, B1;
lambda_vector a, a1;
lambda_matrix invertedtrans;
- int determinant, depth, invariants, size;
+ int depth, invariants, size;
int i, j;
lambda_loop loop;
lambda_linear_expression expression;
/* 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);
/* Compute the loop bounds for the target space, using the bounds of
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 auxillary nest, to get the new loop bounds. The sign of
+ 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. */
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))
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;
int stepint;
int extra = 0;
tree lboundvar, uboundvar, uboundresult;
- use_optype uses;
/* 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)
{
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_and_outer_loops (loop, TREE_OPERAND (test, 1)))
- VEC_safe_push (tree, *invariants, 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_safe_push (tree, *invariants, 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.
*/
*invariants, extra);
uboundresult = build (PLUS_EXPR, TREE_TYPE (uboundvar), uboundvar,
build_int_cst (TREE_TYPE (uboundvar), extra));
- VEC_safe_push (tree, *uboundvars, uboundresult);
- VEC_safe_push (tree, *lboundvars, lboundvar);
- VEC_safe_push (int, *steps, stepint);
+ 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))
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 = NULL;
- VEC (tree) *uboundvars = NULL;
- VEC (tree) *lboundvars = NULL;
- VEC (int) *steps = NULL;
+ 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;
&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)
lboundvars, uboundvars, steps, *inductionvars))
{
if (dump_file)
- fprintf (dump_file, "Not a perfect loop nest and couldn't convert to one.\n");
- return NULL;
+ 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");
-
-
+ 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
static tree
lbv_to_gcc_expression (lambda_body_vector lbv,
- tree type, VEC (tree) *induction_vars,
- tree * stmts_to_insert)
+ tree type, VEC(tree,heap) *induction_vars,
+ tree *stmts_to_insert)
{
tree stmts, stmt, resvar, name;
tree iv;
/* 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, type, iv, coeffmult)));
+ fold_build2 (MULT_EXPR, type, iv, coeffmult));
newname = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = newname;
lle_to_gcc_expression (lambda_linear_expression lle,
lambda_linear_expression offset,
tree type,
- VEC(tree) *induction_vars,
- VEC(tree) *invariants,
- enum tree_code wrap, tree * stmts_to_insert)
+ 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;
tree iv, invar;
- VEC(tree) *results = NULL;
+ 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 ();
{
coeff = build_int_cst (type,
LLE_COEFFICIENTS (lle)[i]);
- mult = fold (build (MULT_EXPR, type, iv, coeff));
+ mult = fold_build2 (MULT_EXPR, type, iv, coeff);
}
/* newname = mult */
else
{
coeff = build_int_cst (type, invcoeff);
- mult = fold (build (MULT_EXPR, type, invar, coeff));
+ mult = fold_build2 (MULT_EXPR, type, invar, coeff);
}
/* newname = mult */
/* 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, type, name,
- build_int_cst (type, LLE_DENOMINATOR (lle))));
- else if (wrap == MIN_EXPR)
- stmt = build (MODIFY_EXPR, void_type_node, resvar,
- build (FLOOR_DIV_EXPR, type, name,
- build_int_cst (type, 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
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
}
+ VEC_free (tree, heap, results);
+
*stmts_to_insert = stmts;
return name;
}
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 = NULL;
+ VEC(tree,heap) *new_ivs = NULL;
tree oldiv;
block_stmt_iterator bsi;
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);
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];
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 (type, LL_STEP (newloop)),
- ivvar, temp, &bsi, false, &ivvar,
- &ivvarinced);
+ 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. */
COND_EXPR_COND (exitcond) = build (testtype,
boolean_type_node,
newupperbound, ivvarinced);
- modify_stmt (exitcond);
+ update_stmt (exitcond);
VEC_replace (tree, new_ivs, i, ivvar);
i++;
for (i = 0; VEC_iterate (tree, old_ivs, i, oldiv); i++)
{
- int j;
- 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)
{
- tree stmt = immediate_use (imm, j);
+ tree stmt = USE_STMT (imm_use);
use_operand_p use_p;
ssa_op_iter iter;
gcc_assert (TREE_CODE (stmt) != PHI_NODE);
expression. */
bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
propagate_value (use_p, newiv);
- modify_stmt (stmt);
+ 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;
+ 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 true;
}
-/* Replace the USES of tree X in STMT with tree Y */
+/* Replace the USES of X in STMT, or uses with the same step as X with Y. */
static void
-replace_uses_of_x_with_y (tree stmt, tree x, tree y)
+replace_uses_equiv_to_x_with_y (struct loop *loop, tree stmt, tree x,
+ int xstep, tree y)
{
- use_optype uses = STMT_USE_OPS (stmt);
- size_t i;
- for (i = 0; i < NUM_USES (uses); i++)
+ ssa_op_iter iter;
+ use_operand_p use_p;
+
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
{
- if (USE_OP (uses, i) == x)
- SET_USE_OP (uses, i, y);
+ 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);
}
}
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) == op)
+ if (use == op)
return true;
}
return false;
}
+/* Return true if STMT is an exit PHI for LOOP */
+
+static bool
+exit_phi_for_loop_p (struct loop *loop, tree stmt)
+{
+
+ 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 (!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 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 oldivvar, ivvar, ivvarinced;
- VEC (tree) *phis = NULL;
+ VEC(tree,heap) *phis = NULL;
if (!can_convert_to_perfect_nest (loop, loopivs))
return false;
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);
+ e = redirect_edge_and_branch (single_succ_edge (preheaderbb), headerbb);
- /* Remove the exit phis from the old basic block. */
+ /* 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)
- remove_phi_node (phi_nodes (olddest), NULL, olddest);
+ {
+ SET_PHI_RESULT (phi_nodes (olddest), NULL);
+ remove_phi_node (phi_nodes (olddest), NULL);
+ }
- /* and add them to the new basic block. */
+ /* and add them back to the new basic block. */
while (VEC_length (tree, phis) != 0)
{
tree def;
def = VEC_pop (tree, phis);
phiname = VEC_pop (tree, phis);
phi = create_phi_node (phiname, preheaderbb);
- add_phi_arg (&phi, def, EDGE_PRED (preheaderbb, 0));
- }
+ add_phi_arg (phi, def, single_pred_edge (preheaderbb));
+ }
flush_pending_stmts (e);
- unmark_all_for_rewrite ();
+ VEC_free (tree, heap, phis);
bodybb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
latchbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
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);
+
+ 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);
-
- bbs = get_loop_body (loop);
- /* Now replace the induction variable in the moved statements with the
- correct loop induction variable. */
+ 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 = 0; i < loop->num_nodes; i++)
+ 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, oldivvar, 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. */
OSDN Git Service
