/* Loop transformation code generation
- Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
Contributed by Daniel Berlin <dberlin@dberlin.org>
This file is part of GCC.
#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) *,
+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);
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);
during this process. */
lambda_loopnest
-gcc_loopnest_to_lambda_loopnest (struct loops *currloops,
- struct loop * loop_nest,
+gcc_loopnest_to_lambda_loopnest (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))
+ if (!perfect_nestify (loop_nest, lboundvars, uboundvars, steps,
+ *inductionvars))
{
if (dump_file)
fprintf (dump_file,
fprintf (dump_file,
"Successfully converted loop nest to perfect loop nest.\n");
}
+
ret = lambda_loopnest_new (depth, 2 * depth);
+
for (i = 0; VEC_iterate (lambda_loop, loops, i, newloop); i++)
LN_LOOPS (ret)[i] = newloop;
+
fail:
VEC_free (lambda_loop, heap, loops);
VEC_free (tree, heap, uboundvars);
/* 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 = build_gimple_modify_stmt (resvar,
+ fold_convert (type, integer_zero_node));
name = make_ssa_name (resvar, stmt);
- TREE_OPERAND (stmt, 0) = name;
+ GIMPLE_STMT_OPERAND (stmt, 0) = name;
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
/* newname = coefficient * induction_variable */
coeffmult = build_int_cst (type, LBV_COEFFICIENTS (lbv)[i]);
- stmt = build (MODIFY_EXPR, void_type_node, resvar,
- fold_build2 (MULT_EXPR, type, iv, coeffmult));
+ stmt = build_gimple_modify_stmt (resvar,
+ fold_build2 (MULT_EXPR, type,
+ iv, coeffmult));
newname = make_ssa_name (resvar, stmt);
- TREE_OPERAND (stmt, 0) = newname;
+ GIMPLE_STMT_OPERAND (stmt, 0) = newname;
fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
/* name = name + newname */
- stmt = build (MODIFY_EXPR, void_type_node, resvar,
- build (PLUS_EXPR, type, name, newname));
+ stmt = build_gimple_modify_stmt (resvar,
+ build2 (PLUS_EXPR, type,
+ name, newname));
name = make_ssa_name (resvar, stmt);
- TREE_OPERAND (stmt, 0) = name;
+ GIMPLE_STMT_OPERAND (stmt, 0) = name;
fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
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 = build_gimple_modify_stmt (resvar,
+ build2 (CEIL_DIV_EXPR, type,
+ name, denominator));
name = make_ssa_name (resvar, stmt);
- TREE_OPERAND (stmt, 0) = name;
+ GIMPLE_STMT_OPERAND (stmt, 0) = name;
fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
/* 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 = build_gimple_modify_stmt (resvar,
+ fold_convert (type, integer_zero_node));
name = make_ssa_name (resvar, stmt);
- TREE_OPERAND (stmt, 0) = name;
+ GIMPLE_STMT_OPERAND (stmt, 0) = name;
fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
}
/* newname = mult */
- stmt = build (MODIFY_EXPR, void_type_node, resvar, mult);
+ stmt = build_gimple_modify_stmt (resvar, mult);
newname = make_ssa_name (resvar, stmt);
- TREE_OPERAND (stmt, 0) = newname;
+ GIMPLE_STMT_OPERAND (stmt, 0) = newname;
fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
/* name = name + newname */
- stmt = build (MODIFY_EXPR, void_type_node, resvar,
- build (PLUS_EXPR, type, name, newname));
+ stmt = build_gimple_modify_stmt (resvar,
+ build2 (PLUS_EXPR, type,
+ name, newname));
name = make_ssa_name (resvar, stmt);
- TREE_OPERAND (stmt, 0) = name;
+ GIMPLE_STMT_OPERAND (stmt, 0) = name;
fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
}
/* newname = mult */
- stmt = build (MODIFY_EXPR, void_type_node, resvar, mult);
+ stmt = build_gimple_modify_stmt (resvar, mult);
newname = make_ssa_name (resvar, stmt);
- TREE_OPERAND (stmt, 0) = newname;
+ GIMPLE_STMT_OPERAND (stmt, 0) = newname;
fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
/* name = name + newname */
- stmt = build (MODIFY_EXPR, void_type_node, resvar,
- build (PLUS_EXPR, type, name, newname));
+ stmt = build_gimple_modify_stmt (resvar,
+ build2 (PLUS_EXPR, type,
+ name, newname));
name = make_ssa_name (resvar, stmt);
- TREE_OPERAND (stmt, 0) = name;
+ GIMPLE_STMT_OPERAND (stmt, 0) = name;
fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
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))));
+ tree incr = build_int_cst (type, LLE_CONSTANT (lle));
+ stmt = build_gimple_modify_stmt (resvar, build2 (PLUS_EXPR, type,
+ name, incr));
name = make_ssa_name (resvar, stmt);
- TREE_OPERAND (stmt, 0) = name;
+ GIMPLE_STMT_OPERAND (stmt, 0) = name;
fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
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))));
+ tree incr = build_int_cst (type, LLE_CONSTANT (offset));
+ stmt = build_gimple_modify_stmt (resvar, build2 (PLUS_EXPR, type,
+ name, incr));
name = make_ssa_name (resvar, stmt);
- TREE_OPERAND (stmt, 0) = name;
+ GIMPLE_STMT_OPERAND (stmt, 0) = name;
fold_stmt (&stmt);
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
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 = build_gimple_modify_stmt (resvar, stmt);
/* name = {ceil, floor}(name/denominator) */
name = make_ssa_name (resvar, stmt);
- TREE_OPERAND (stmt, 0) = name;
+ GIMPLE_STMT_OPERAND (stmt, 0) = name;
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
}
{
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 = build_gimple_modify_stmt (resvar, build2 (wrap, type, op1, op2));
name = make_ssa_name (resvar, stmt);
- TREE_OPERAND (stmt, 0) = name;
+ GIMPLE_STMT_OPERAND (stmt, 0) = name;
tsi = tsi_last (stmts);
tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
}
/* 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 = build_gimple_modify_stmt (SSA_NAME_VAR (ivvar), inc_stmt);
ivvarinced = make_ssa_name (SSA_NAME_VAR (ivvar), inc_stmt);
- TREE_OPERAND (inc_stmt, 0) = ivvarinced;
+ GIMPLE_STMT_OPERAND (inc_stmt, 0) = ivvarinced;
bsi = bsi_for_stmt (exitcond);
bsi_insert_before (&bsi, inc_stmt, BSI_SAME_STMT);
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);
-
- }
- }
+
+ /* 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);
+
+ FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
+ propagate_value (use_p, newiv);
+ update_stmt (stmt);
}
}
VEC_free (tree, heap, new_ivs);
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 && 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);
- }
-}
+ 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.base.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 = build_gimple_modify_stmt (var, val);
+ var = make_ssa_name (var, setstmt);
+ GIMPLE_STMT_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->base.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);
+ gcc_assert (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)
- || !expr_invariant_in_loop_p (inner, TREE_OPERAND (stmt, 1)))
+ || !expr_invariant_in_loop_p (inner, GIMPLE_STMT_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))
+ FOR_EACH_IMM_USE_FAST (use_p, imm_iter, GIMPLE_STMT_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, GIMPLE_STMT_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) == GIMPLE_MODIFY_STMT)
+ {
+ 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 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)
}
/* Transform the loop nest into a perfect nest, if possible.
- LOOPS is the current struct loops *
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
Return FALSE if we can't make this loop into a perfect nest. */
static bool
-perfect_nestify (struct loops *loops,
- struct loop *loop,
+perfect_nestify (struct loop *loop,
VEC(tree,heap) *lbounds,
VEC(tree,heap) *ubounds,
VEC(int,heap) *steps,
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. */
}
e = redirect_edge_and_branch (single_succ_edge (preheaderbb), headerbb);
- /* Remove the exit phis from the old basic block. Make sure to set
- PHI_RESULT to null so it doesn't get released. */
+ /* Remove the exit phis from the old basic block. */
while (phi_nodes (olddest) != NULL)
- {
- SET_PHI_RESULT (phi_nodes (olddest), NULL);
- remove_phi_node (phi_nodes (olddest), NULL);
- }
+ remove_phi_node (phi_nodes (olddest), NULL, false);
/* and add them back to the new basic block. */
while (VEC_length (tree, phis) != 0)
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);
make_edge (latchbb, headerbb, EDGE_FALLTHRU);
/* Update the loop structures. */
- newloop = duplicate_loop (loops, loop, olddest->loop_father);
+ newloop = duplicate_loop (loop, olddest->loop_father);
newloop->header = headerbb;
newloop->latch = latchbb;
- newloop->single_exit = 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 = build_gimple_modify_stmt (uboundvar, VEC_index (tree, ubounds, 0));
uboundvar = make_ssa_name (uboundvar, stmt);
- TREE_OPERAND (stmt, 0) = uboundvar;
+ GIMPLE_STMT_OPERAND (stmt, 0) = uboundvar;
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);
+ 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;
}
OSDN Git Service
