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_P(int);
-DEF_VEC_ALLOC_P(int,heap);
+DEF_VEC_I(int);
+DEF_VEC_ALLOC_I(int,heap);
static bool perfect_nestify (struct loops *,
struct loop *, VEC(tree,heap) *,
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);
add_referenced_tmp_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);
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);
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);
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. */
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)
{
ssa_op_iter iter;
use_operand_p use_p;
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
{
- if (USE_FROM_PTR (use_p) == x)
+ 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);
}
}
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 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;
+
+ 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;
+
+ 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;
+ }
+ }
+ 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
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++)
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, or after the inner loop,
+ then see if we can place it back where it came from.
+ This means that we will propagate casts and other
+ cheap invariant operations *back* into or after
+ 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)
+ || 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
+ 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))
}
Return FALSE if we can't make this loop into a perfect nest. */
+
static bool
perfect_nestify (struct loops *loops,
struct loop *loop,
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;
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);
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);
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)),
+ 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
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));
+ 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);
- bbs = get_loop_body (loop);
- /* Now replace the induction variable in the moved statements with the
- correct loop induction variable. */
+ 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);)
- {
- ssa_op_iter i;
- tree n, stmt = bsi_stmt (bsi);
+ /* If this is true, we are *before* the inner loop.
+ If this isn't true, we are *after* it.
- if (stmt == exit_condition
- || not_interesting_stmt (stmt)
- || stmt_is_bumper_for_loop (loop, stmt))
- {
- bsi_next (&bsi);
- continue;
- }
+ 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.
- replace_uses_of_x_with_y (stmt, oldivvar, ivvar);
- bsi_move_before (&bsi, &tobsi);
+ 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 the statement has any virtual operands, they may
- need to be rewired because the original loop may
- still reference them. */
- FOR_EACH_SSA_TREE_OPERAND (n, stmt, i, SSA_OP_ALL_VIRTUALS)
- mark_sym_for_renaming (SSA_NAME_VAR (n));
+ if (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;
+ }
+
+ /* Make copies of this statement to put it back next
+ to its uses. */
+ 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;
+ tree newname;
+ tree newstmt;
+
+ newstmt = unshare_expr (stmt);
+ tobsi = bsi_after_labels (bb_for_stmt (imm_stmt));
+ newname = TREE_OPERAND (newstmt, 0);
+ newname = SSA_NAME_VAR (newname);
+ newname = make_ssa_name (newname, newstmt);
+ TREE_OPERAND (newstmt, 0) = newname;
+ SET_USE (use_p, TREE_OPERAND (newstmt, 0));
+ bsi_insert_before (&tobsi, newstmt, BSI_SAME_STMT);
+ update_stmt (newstmt);
+ update_stmt (imm_stmt);
+ }
+ }
+ if (!bsi_end_p (bsi))
+ bsi_prev (&bsi);
+ }
}
+ else
+ {
+ /* Note that the bsi only needs to be explicitly incremented
+ when we don't move something, since it is automatically
+ incremented when we do. */
+ for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi);)
+ {
+ ssa_op_iter i;
+ tree n, stmt = bsi_stmt (bsi);
+
+ 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));
+ }
+ }
+
}
}
int nb_loops,
varray_type dependence_relations)
{
- unsigned int i;
+ unsigned int i, j;
lambda_vector distres;
struct data_dependence_relation *ddr;
/* 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
