/* Loop transformation code generation
- Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005, 2006 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 "tree-scalar-evolution.h"
#include "vec.h"
#include "lambda.h"
+#include "vecprim.h"
/* This loop nest code generation is based on non-singular matrix
math.
Fourier-Motzkin elimination is used to compute the bounds of the base space
of the lattice. */
-DEF_VEC_I(int);
-DEF_VEC_ALLOC_I(int,heap);
-
static bool perfect_nestify (struct loops *,
struct loop *, VEC(tree,heap) *,
VEC(tree,heap) *, VEC(int,heap) *,
static lambda_lattice lambda_lattice_compute_base (lambda_loopnest);
static tree find_induction_var_from_exit_cond (struct loop *);
+static bool can_convert_to_perfect_nest (struct loop *);
/* Create a new lambda body vector. */
return ret;
}
-/* Compute the greatest common denominator of two numbers (A and B) using
- Euclid's algorithm. */
-
-static int
-gcd (int a, int b)
-{
-
- int x, y, z;
-
- x = abs (a);
- y = abs (b);
-
- while (x > 0)
- {
- z = y % x;
- y = x;
- x = z;
- }
-
- return (y);
-}
-
-/* Compute the greatest common denominator of a VECTOR of SIZE numbers. */
-
-static int
-gcd_vector (lambda_vector vector, int size)
-{
- int i;
- int gcd1 = 0;
-
- if (size > 0)
- {
- gcd1 = vector[0];
- for (i = 1; i < size; i++)
- gcd1 = gcd (gcd1, vector[i]);
- }
- return gcd1;
-}
-
/* Compute the least common multiple of two numbers A and B . */
-static int
-lcm (int a, int b)
+int
+least_common_multiple (int a, int b)
{
return (abs (a) * abs (b) / gcd (a, b));
}
{
if (A[k][i] < 0)
{
- multiple = lcm (A[j][i], A[k][i]);
+ multiple = least_common_multiple (A[j][i], A[k][i]);
f1 = multiple / A[j][i];
f2 = -1 * multiple / A[k][i];
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. */
+ using Fourier-Motzkin elimination to figure out the bounds. */
static lambda_loopnest
lambda_compute_auxillary_space (lambda_loopnest nest,
lambda_matrix_add_mc (B, 1, B1, -1, B1, size, invariants);
/* Now compute the auxiliary space bounds by first inverting U, multiplying
- it by A1, then performing fourier motzkin. */
+ it by A1, then performing Fourier-Motzkin. */
invertedtrans = lambda_matrix_new (depth, depth);
LN_LOOPS (target_nest)[i] = target_loop;
/* Computes the gcd of the coefficients of the linear part. */
- gcd1 = gcd_vector (target[i], i);
+ gcd1 = lambda_vector_gcd (target[i], i);
/* Include the denominator in the GCD. */
gcd1 = gcd (gcd1, determinant);
}
/* Find the gcd and divide by it here, rather than doing it
at the tree level. */
- gcd1 = gcd_vector (LLE_COEFFICIENTS (target_expr), depth);
- gcd2 = gcd_vector (LLE_INVARIANT_COEFFICIENTS (target_expr),
- invariants);
+ gcd1 = lambda_vector_gcd (LLE_COEFFICIENTS (target_expr), depth);
+ gcd2 = lambda_vector_gcd (LLE_INVARIANT_COEFFICIENTS (target_expr),
+ invariants);
gcd1 = gcd (gcd1, gcd2);
gcd1 = gcd (gcd1, LLE_CONSTANT (target_expr));
gcd1 = gcd (gcd1, LLE_DENOMINATOR (target_expr));
}
/* Find the gcd and divide by it here, instead of at the
tree level. */
- gcd1 = gcd_vector (LLE_COEFFICIENTS (target_expr), depth);
- gcd2 = gcd_vector (LLE_INVARIANT_COEFFICIENTS (target_expr),
- invariants);
+ gcd1 = lambda_vector_gcd (LLE_COEFFICIENTS (target_expr), depth);
+ gcd2 = lambda_vector_gcd (LLE_INVARIANT_COEFFICIENTS (target_expr),
+ invariants);
gcd1 = gcd (gcd1, gcd2);
gcd1 = gcd (gcd1, LLE_CONSTANT (target_expr));
gcd1 = gcd (gcd1, LLE_DENOMINATOR (target_expr));
ubound = gcc_tree_to_linear_expression (depth, uboundvar,
outerinductionvars,
*invariants, extra);
- uboundresult = build (PLUS_EXPR, TREE_TYPE (uboundvar), uboundvar,
- build_int_cst (TREE_TYPE (uboundvar), extra));
+ uboundresult = build2 (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);
lambda_loopnest
gcc_loopnest_to_lambda_loopnest (struct loops *currloops,
- struct loop * loop_nest,
+ struct loop *loop_nest,
VEC(tree,heap) **inductionvars,
- VEC(tree,heap) **invariants,
- bool need_perfect_nest)
+ VEC(tree,heap) **invariants)
{
lambda_loopnest ret = NULL;
- struct loop *temp;
- int depth = 0;
+ struct loop *temp = loop_nest;
+ int depth = depth_of_nest (loop_nest);
size_t i;
VEC(lambda_loop,heap) *loops = NULL;
VEC(tree,heap) *uboundvars = NULL;
VEC(int,heap) *steps = NULL;
lambda_loop newloop;
tree inductionvar = NULL;
-
- depth = depth_of_nest (loop_nest);
- temp = loop_nest;
+ bool perfect_nest = perfect_nest_p (loop_nest);
+
+ if (!perfect_nest && !can_convert_to_perfect_nest (loop_nest))
+ goto fail;
+
while (temp)
{
newloop = gcc_loop_to_lambda_loop (temp, depth, invariants,
&lboundvars, &uboundvars,
&steps);
if (!newloop)
- return NULL;
+ goto fail;
+
VEC_safe_push (tree, heap, *inductionvars, inductionvar);
VEC_safe_push (lambda_loop, heap, loops, newloop);
temp = temp->inner;
}
- if (need_perfect_nest)
+
+ if (!perfect_nest)
{
if (!perfect_nestify (currloops, loop_nest,
lboundvars, uboundvars, steps, *inductionvars))
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);
/* Create a statement list and a linear expression temporary. */
stmts = alloc_stmt_list ();
resvar = create_tmp_var (type, "lbvtmp");
- add_referenced_tmp_var (resvar);
+ add_referenced_var (resvar);
/* Start at 0. */
- stmt = build (MODIFY_EXPR, void_type_node, resvar, integer_zero_node);
+ stmt = build2 (MODIFY_EXPR, void_type_node, resvar, integer_zero_node);
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
tsi = tsi_last (stmts);
/* 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)));
+ stmt = build2 (MODIFY_EXPR, void_type_node, resvar,
+ fold_build2 (MULT_EXPR, type, iv, coeffmult));
newname = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = newname;
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
/* name = name + newname */
- stmt = build (MODIFY_EXPR, void_type_node, resvar,
- build (PLUS_EXPR, type, name, newname));
+ stmt = build2 (MODIFY_EXPR, void_type_node, resvar,
+ build2 (PLUS_EXPR, type, name, newname));
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
fold_stmt (&stmt);
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, type, name, denominator));
+ stmt = build2 (MODIFY_EXPR, void_type_node, resvar,
+ build2 (CEIL_DIV_EXPR, type, name, denominator));
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
fold_stmt (&stmt);
/* Create a statement list and a linear expression temporary. */
stmts = alloc_stmt_list ();
resvar = create_tmp_var (type, "lletmp");
- add_referenced_tmp_var (resvar);
+ add_referenced_var (resvar);
/* Build up the linear expressions, and put the variable representing the
result in the results array. */
for (; lle != NULL; lle = LLE_NEXT (lle))
{
/* Start at name = 0. */
- stmt = build (MODIFY_EXPR, void_type_node, resvar, integer_zero_node);
+ stmt = build2 (MODIFY_EXPR, void_type_node, resvar, integer_zero_node);
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
fold_stmt (&stmt);
{
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 */
- stmt = build (MODIFY_EXPR, void_type_node, resvar, mult);
+ stmt = build2 (MODIFY_EXPR, void_type_node, resvar, mult);
newname = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = newname;
fold_stmt (&stmt);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
/* name = name + newname */
- stmt = build (MODIFY_EXPR, void_type_node, resvar,
- build (PLUS_EXPR, type, name, newname));
+ stmt = build2 (MODIFY_EXPR, void_type_node, resvar,
+ build2 (PLUS_EXPR, type, name, newname));
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
fold_stmt (&stmt);
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 */
- stmt = build (MODIFY_EXPR, void_type_node, resvar, mult);
+ stmt = build2 (MODIFY_EXPR, void_type_node, resvar, mult);
newname = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = newname;
fold_stmt (&stmt);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
/* name = name + newname */
- stmt = build (MODIFY_EXPR, void_type_node, resvar,
- build (PLUS_EXPR, type, name, newname));
+ stmt = build2 (MODIFY_EXPR, void_type_node, resvar,
+ build2 (PLUS_EXPR, type, name, newname));
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
fold_stmt (&stmt);
name = name + constant. */
if (LLE_CONSTANT (lle) != 0)
{
- stmt = build (MODIFY_EXPR, void_type_node, resvar,
- build (PLUS_EXPR, type, name,
- build_int_cst (type, LLE_CONSTANT (lle))));
+ stmt = build2 (MODIFY_EXPR, void_type_node, resvar,
+ build2 (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);
name = name + linear offset. */
if (LLE_CONSTANT (offset) != 0)
{
- stmt = build (MODIFY_EXPR, void_type_node, resvar,
- build (PLUS_EXPR, type, name,
- build_int_cst (type, LLE_CONSTANT (offset))));
+ stmt = build2 (MODIFY_EXPR, void_type_node, resvar,
+ build2 (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);
if (LLE_DENOMINATOR (lle) != 1)
{
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);
+ stmt = build2 (wrap == MAX_EXPR ? CEIL_DIV_EXPR : FLOOR_DIV_EXPR,
+ type, name, stmt);
+ stmt = build2 (MODIFY_EXPR, void_type_node, resvar, stmt);
/* name = {ceil, floor}(name/denominator) */
name = make_ssa_name (resvar, stmt);
{
tree op1 = VEC_index (tree, results, 0);
tree op2 = VEC_index (tree, results, 1);
- stmt = build (MODIFY_EXPR, void_type_node, resvar,
- build (wrap, type, op1, op2));
+ stmt = build2 (MODIFY_EXPR, void_type_node, resvar,
+ build2 (wrap, type, op1, op2));
name = make_ssa_name (resvar, stmt);
TREE_OPERAND (stmt, 0) = name;
tsi = tsi_last (stmts);
/* First, build the new induction variable temporary */
ivvar = create_tmp_var (type, "lnivtmp");
- add_referenced_tmp_var (ivvar);
+ add_referenced_var (ivvar);
VEC_safe_push (tree, heap, new_ivs, ivvar);
type,
new_ivs,
invariants, MIN_EXPR, &stmts);
- exit = temp->single_exit;
+ exit = single_exit (temp);
exitcond = get_loop_exit_condition (temp);
bb = bb_for_stmt (exitcond);
bsi = bsi_start (bb);
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);
+ inc_stmt = build2 (PLUS_EXPR, type,
+ ivvar, build_int_cst (type, LL_STEP (newloop)));
+ inc_stmt = build2 (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);
if (exit->flags & EDGE_FALSE_VALUE)
testtype = swap_tree_comparison (testtype);
- COND_EXPR_COND (exitcond) = build (testtype,
- boolean_type_node,
- newupperbound, ivvarinced);
+ COND_EXPR_COND (exitcond) = build2 (testtype,
+ boolean_type_node,
+ newupperbound, ivvarinced);
update_stmt (exitcond);
VEC_replace (tree, new_ivs, i, ivvar);
for (i = 0; VEC_iterate (tree, old_ivs, i, oldiv); i++)
{
imm_use_iterator imm_iter;
- use_operand_p imm_use;
+ use_operand_p use_p;
tree oldiv_def;
tree oldiv_stmt = SSA_NAME_DEF_STMT (oldiv);
+ tree stmt;
if (TREE_CODE (oldiv_stmt) == PHI_NODE)
oldiv_def = PHI_RESULT (oldiv_stmt);
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 = USE_STMT (imm_use);
- use_operand_p use_p;
- ssa_op_iter iter;
+ FOR_EACH_IMM_USE_STMT (stmt, imm_iter, oldiv_def)
+ {
+ tree newiv, stmts;
+ lambda_body_vector lbv, newlbv;
+
gcc_assert (TREE_CODE (stmt) != PHI_NODE);
- FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
- {
- if (USE_FROM_PTR (use_p) == oldiv)
- {
- tree newiv, stmts;
- 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;
-
- 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);
- 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. */
+ /* 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;
+
+ 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);
-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;
+ FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
+ propagate_value (use_p, newiv);
+ update_stmt (stmt);
+ }
}
- return true;
+ VEC_free (tree, heap, new_ivs);
}
-
/* Return TRUE if this is not interesting statement from the perspective of
determining if we have a perfect loop nest. */
return true;
}
-/* Replace the USES of X in STMT, or uses with the same step as X with Y. */
+/* Replace the USES of X in STMT, or uses with the same step as X with Y.
+ YINIT is the initial value of Y, REPLACEMENTS is a hash table to
+ avoid creating duplicate temporaries and FIRSTBSI is statement
+ iterator where new temporaries should be inserted at the beginning
+ of body basic block. */
static void
replace_uses_equiv_to_x_with_y (struct loop *loop, tree stmt, tree x,
- int xstep, tree y)
+ int xstep, tree y, tree yinit,
+ htab_t replacements,
+ block_stmt_iterator *firstbsi)
{
ssa_op_iter iter;
use_operand_p use_p;
{
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)
- step = evolution_part_in_loop_num (access_fn, loop->num);
- if ((step && int_cst_value (step) == xstep)
- || USE_FROM_PTR (use_p) == x)
- SET_USE (use_p, y);
- }
-}
+ tree scev, init, val, var, setstmt;
+ struct tree_map *h, in;
+ void **loc;
-/* Return TRUE if STMT uses tree OP in it's uses. */
+ /* Replace uses of X with Y right away. */
+ if (use == x)
+ {
+ SET_USE (use_p, y);
+ continue;
+ }
-static bool
-stmt_uses_op (tree stmt, tree op)
-{
- ssa_op_iter iter;
- tree use;
+ scev = instantiate_parameters (loop,
+ analyze_scalar_evolution (loop, use));
- FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
- {
- if (use == op)
- return true;
+ if (scev == NULL || scev == chrec_dont_know)
+ continue;
+
+ step = evolution_part_in_loop_num (scev, loop->num);
+ if (step == NULL
+ || step == chrec_dont_know
+ || TREE_CODE (step) != INTEGER_CST
+ || int_cst_value (step) != xstep)
+ continue;
+
+ /* Use REPLACEMENTS hash table to cache already created
+ temporaries. */
+ in.hash = htab_hash_pointer (use);
+ in.from = use;
+ h = htab_find_with_hash (replacements, &in, in.hash);
+ if (h != NULL)
+ {
+ SET_USE (use_p, h->to);
+ continue;
+ }
+
+ /* USE which has the same step as X should be replaced
+ with a temporary set to Y + YINIT - INIT. */
+ init = initial_condition_in_loop_num (scev, loop->num);
+ gcc_assert (init != NULL && init != chrec_dont_know);
+ if (TREE_TYPE (use) == TREE_TYPE (y))
+ {
+ val = fold_build2 (MINUS_EXPR, TREE_TYPE (y), init, yinit);
+ val = fold_build2 (PLUS_EXPR, TREE_TYPE (y), y, val);
+ if (val == y)
+ {
+ /* If X has the same type as USE, the same step
+ and same initial value, it can be replaced by Y. */
+ SET_USE (use_p, y);
+ continue;
+ }
+ }
+ else
+ {
+ val = fold_build2 (MINUS_EXPR, TREE_TYPE (y), y, yinit);
+ val = fold_convert (TREE_TYPE (use), val);
+ val = fold_build2 (PLUS_EXPR, TREE_TYPE (use), val, init);
+ }
+
+ /* Create a temporary variable and insert it at the beginning
+ of the loop body basic block, right after the PHI node
+ which sets Y. */
+ var = create_tmp_var (TREE_TYPE (use), "perfecttmp");
+ add_referenced_var (var);
+ val = force_gimple_operand_bsi (firstbsi, val, false, NULL);
+ setstmt = build2 (MODIFY_EXPR, void_type_node, var, val);
+ var = make_ssa_name (var, setstmt);
+ TREE_OPERAND (setstmt, 0) = var;
+ bsi_insert_before (firstbsi, setstmt, BSI_SAME_STMT);
+ update_stmt (setstmt);
+ SET_USE (use_p, var);
+ h = ggc_alloc (sizeof (struct tree_map));
+ h->hash = in.hash;
+ h->from = use;
+ h->to = var;
+ loc = htab_find_slot_with_hash (replacements, h, in.hash, INSERT);
+ gcc_assert ((*(struct tree_map **)loc) == NULL);
+ *(struct tree_map **) loc = h;
}
- return false;
}
/* Return true if STMT is an exit PHI for LOOP */
if (TREE_CODE (stmt) != PHI_NODE
|| PHI_NUM_ARGS (stmt) != 1
- || bb_for_stmt (stmt) != loop->single_exit->dest)
+ || bb_for_stmt (stmt) != single_exit (loop)->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. */
+/* Return true if STMT can be put back into the loop INNER, by
+ copying it to the beginning of that loop and changing the uses. */
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)))
if (!flow_bb_inside_loop_p (inner, immbb))
return false;
- if (use_bb == NULL)
- use_bb = immbb;
- else if (immbb != use_bb)
+ }
+ }
+ 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)
+{
+ imm_use_iterator imm_iter;
+ use_operand_p use_p;
+
+ if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
+ return false;
+
+ FOR_EACH_IMM_USE_FAST (use_p, imm_iter, TREE_OPERAND (stmt, 0))
+ {
+ if (!exit_phi_for_loop_p (loop, USE_STMT (use_p)))
+ {
+ basic_block immbb = bb_for_stmt (USE_STMT (use_p));
+
+ if (!dominated_by_p (CDI_DOMINATORS,
+ immbb,
+ loop->inner->header)
+ && !can_put_in_inner_loop (loop->inner, stmt))
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
- occur after the inner loop. */
+
+/* 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. */
static bool
-can_convert_to_perfect_nest (struct loop *loop,
- VEC(tree,heap) *loopivs)
+can_convert_to_perfect_nest (struct loop *loop)
{
basic_block *bbs;
tree exit_condition, phi;
{
for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi))
{
- 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; VEC_iterate (tree, loopivs, j, iv); j++)
- if (stmt_uses_op (stmt, iv))
- goto fail;
-
- /* 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;
+
+ /* If this is a scalar operation that can be put back
+ into the inner loop, or after the inner loop, through
+ copying, then do so. This works on the theory that
+ any amount of scalar code we have to reduplicate
+ into or after the loops is less expensive that the
+ win we get from rearranging the memory walk
+ the loop is doing so that it has better
+ cache behavior. */
+ if (TREE_CODE (stmt) == MODIFY_EXPR)
+ {
+ use_operand_p use_a, use_b;
+ imm_use_iterator imm_iter;
+ ssa_op_iter op_iter, op_iter1;
+ tree op0 = TREE_OPERAND (stmt, 0);
+ tree scev = instantiate_parameters
+ (loop, analyze_scalar_evolution (loop, op0));
+
+ /* If the IV is simple, it can be duplicated. */
+ if (!automatically_generated_chrec_p (scev))
+ {
+ tree step = evolution_part_in_loop_num (scev, loop->num);
+ if (step && step != chrec_dont_know
+ && TREE_CODE (step) == INTEGER_CST)
+ continue;
+ }
+
+ /* The statement should not define a variable used
+ in the inner loop. */
+ if (TREE_CODE (op0) == SSA_NAME)
+ FOR_EACH_IMM_USE_FAST (use_a, imm_iter, op0)
+ if (bb_for_stmt (USE_STMT (use_a))->loop_father
+ == loop->inner)
+ goto fail;
+
+ FOR_EACH_SSA_USE_OPERAND (use_a, stmt, op_iter, SSA_OP_USE)
+ {
+ tree node, op = USE_FROM_PTR (use_a);
+
+ /* The variables should not be used in both loops. */
+ FOR_EACH_IMM_USE_FAST (use_b, imm_iter, op)
+ if (bb_for_stmt (USE_STMT (use_b))->loop_father
+ == loop->inner)
+ goto fail;
+
+ /* 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)
+ FOR_EACH_PHI_ARG (use_b, node, op_iter1, SSA_OP_USE)
+ {
+ tree arg = USE_FROM_PTR (use_b);
+
+ if (TREE_CODE (arg) == SSA_NAME)
+ {
+ tree arg_stmt = SSA_NAME_DEF_STMT (arg);
+
+ if (bb_for_stmt (arg_stmt)->loop_father
+ == loop->inner)
+ goto fail;
+ }
+ }
+ }
+
+ if (can_put_in_inner_loop (loop->inner, stmt)
+ || can_put_after_inner_loop (loop, 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
/* 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;
+ exitdest = single_exit (loop)->dest;
for (phi = phi_nodes (exitdest); phi; phi = PHI_CHAIN (phi))
if (PHI_NUM_ARGS (phi) != 1)
tree then_label, else_label, cond_stmt;
basic_block preheaderbb, headerbb, bodybb, latchbb, olddest;
int i;
- block_stmt_iterator bsi;
+ block_stmt_iterator bsi, firstbsi;
bool insert_after;
edge e;
struct loop *newloop;
tree stmt;
tree oldivvar, ivvar, ivvarinced;
VEC(tree,heap) *phis = NULL;
+ htab_t replacements = NULL;
- if (!can_convert_to_perfect_nest (loop, loopivs))
- return false;
-
- /* Create the new loop */
-
- olddest = loop->single_exit->dest;
- preheaderbb = loop_split_edge_with (loop->single_exit, 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. */
make_edge (headerbb, bodybb, EDGE_FALLTHRU);
then_label = build1 (GOTO_EXPR, void_type_node, tree_block_label (latchbb));
else_label = build1 (GOTO_EXPR, void_type_node, tree_block_label (olddest));
- cond_stmt = build (COND_EXPR, void_type_node,
- build (NE_EXPR, boolean_type_node,
- integer_one_node,
- integer_zero_node),
- then_label, else_label);
+ cond_stmt = build3 (COND_EXPR, void_type_node,
+ build2 (NE_EXPR, boolean_type_node,
+ integer_one_node,
+ integer_zero_node),
+ then_label, else_label);
bsi = bsi_start (bodybb);
bsi_insert_after (&bsi, cond_stmt, BSI_NEW_STMT);
e = make_edge (bodybb, olddest, EDGE_FALSE_VALUE);
newloop = duplicate_loop (loops, loop, olddest->loop_father);
newloop->header = headerbb;
newloop->latch = latchbb;
- newloop->single_exit = e;
+ set_single_exit (newloop, e);
add_bb_to_loop (latchbb, newloop);
add_bb_to_loop (bodybb, 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,
- loop->single_exit->src);
+ single_exit (loop)->src);
set_immediate_dominator (CDI_DOMINATORS, latchbb, bodybb);
set_immediate_dominator (CDI_DOMINATORS, olddest, bodybb);
/* Create the new iv. */
oldivvar = VEC_index (tree, loopivs, 0);
ivvar = create_tmp_var (TREE_TYPE (oldivvar), "perfectiv");
- add_referenced_tmp_var (ivvar);
+ add_referenced_var (ivvar);
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)),
exit_condition = get_loop_exit_condition (newloop);
uboundvar = create_tmp_var (integer_type_node, "uboundvar");
- add_referenced_tmp_var (uboundvar);
- stmt = build (MODIFY_EXPR, void_type_node, uboundvar,
- VEC_index (tree, ubounds, 0));
+ add_referenced_var (uboundvar);
+ stmt = build2 (MODIFY_EXPR, void_type_node, uboundvar,
+ VEC_index (tree, ubounds, 0));
uboundvar = make_ssa_name (uboundvar, stmt);
TREE_OPERAND (stmt, 0) = uboundvar;
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);
+ COND_EXPR_COND (exit_condition) = build2 (GE_EXPR,
+ boolean_type_node,
+ 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);
/* 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);
for (i = loop->num_nodes - 1; i >= 0 ; i--)
{
block_stmt_iterator tobsi = bsi_last (bodybb);
if (dominated_by_p (CDI_DOMINATORS, loop->inner->header, bbs[i]))
{
- for (bsi = bsi_last (bbs[i]); !bsi_end_p (bsi);)
+ block_stmt_iterator header_bsi
+ = bsi_after_labels (loop->inner->header);
+
+ for (bsi = bsi_start (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);
+ bsi_next (&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);
- }
- }
+
+ bsi_move_before (&bsi, &header_bsi);
}
}
else
continue;
}
- replace_uses_equiv_to_x_with_y (loop, stmt,
- oldivvar,
- VEC_index (int, steps, 0),
- ivvar);
+ 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);
/* If the statement has any virtual operands, they may
}
free (bbs);
+ htab_delete (replacements);
return perfect_nest_p (loop);
}
bool
lambda_transform_legal_p (lambda_trans_matrix trans,
int nb_loops,
- varray_type dependence_relations)
+ VEC (ddr_p, heap) *dependence_relations)
{
- unsigned int i;
+ unsigned int i, j;
lambda_vector distres;
struct data_dependence_relation *ddr;
/* When there is an unknown relation in the dependence_relations, we
know that it is no worth looking at this loop nest: give up. */
- ddr = (struct data_dependence_relation *)
- VARRAY_GENERIC_PTR (dependence_relations, 0);
+ ddr = VEC_index (ddr_p, dependence_relations, 0);
if (ddr == NULL)
return true;
if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
distres = lambda_vector_new (nb_loops);
/* For each distance vector in the dependence graph. */
- for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
+ for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
{
- ddr = (struct data_dependence_relation *)
- 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):
these data accesses can happen in any order. */
/* 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)
+ if (DDR_NUM_DIST_VECTS (ddr) == 0)
return false;
/* Compute trans.dist_vect */
- lambda_matrix_vector_mult (LTM_MATRIX (trans), nb_loops, nb_loops,
- DDR_DIST_VECT (ddr), distres);
+ for (j = 0; j < DDR_NUM_DIST_VECTS (ddr); j++)
+ {
+ 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))
- return false;
+ if (!lambda_vector_lexico_pos (distres, nb_loops))
+ return false;
+ }
}
return true;
}