/* Loop transformation code generation
- Copyright (C) 2003, 2004, 2005, 2006 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.
VEC(tree,heap) *);
/* Lattice stuff that is internal to the code generation algorithm. */
-typedef struct
+typedef struct lambda_lattice_s
{
/* Lattice base matrix. */
lambda_matrix base;
{
lambda_body_vector ret;
- ret = ggc_alloc (sizeof (*ret));
+ ret = GGC_NEW (struct lambda_body_vector_s);
LBV_COEFFICIENTS (ret) = lambda_vector_new (size);
LBV_SIZE (ret) = size;
LBV_DENOMINATOR (ret) = 1;
{
lambda_linear_expression ret;
- ret = ggc_alloc_cleared (sizeof (*ret));
+ ret = GGC_CNEW (struct lambda_linear_expression_s);
LLE_COEFFICIENTS (ret) = lambda_vector_new (dim);
LLE_CONSTANT (ret) = 0;
lambda_loopnest_new (int depth, int invariants)
{
lambda_loopnest ret;
- ret = ggc_alloc (sizeof (*ret));
+ ret = GGC_NEW (struct lambda_loopnest_s);
- LN_LOOPS (ret) = ggc_alloc_cleared (depth * sizeof (lambda_loop));
+ LN_LOOPS (ret) = GGC_CNEWVEC (lambda_loop, depth);
LN_DEPTH (ret) = depth;
LN_INVARIANTS (ret) = invariants;
lambda_lattice_new (int depth, int invariants)
{
lambda_lattice ret;
- ret = ggc_alloc (sizeof (*ret));
+ ret = GGC_NEW (struct lambda_lattice_s);
LATTICE_BASE (ret) = lambda_matrix_new (depth, depth);
LATTICE_ORIGIN (ret) = lambda_vector_new (depth);
LATTICE_ORIGIN_INVARIANTS (ret) = lambda_matrix_new (depth, invariants);
{
if (is_gimple_min_invariant (op))
return true;
- if (loop->depth == 0)
+ if (loop_depth (loop) == 0)
return true;
if (!expr_invariant_in_loop_p (loop, op))
return false;
- if (loop->outer
- && !invariant_in_loop_and_outer_loops (loop->outer, op))
+ if (!invariant_in_loop_and_outer_loops (loop_outer (loop), op))
return false;
return true;
}
tree type, VEC(tree,heap) *induction_vars,
tree *stmts_to_insert)
{
- tree stmts, stmt, resvar, name;
- tree iv;
- size_t i;
- tree_stmt_iterator tsi;
+ int k;
+ tree resvar;
+ tree expr = build_linear_expr (type, LBV_COEFFICIENTS (lbv), induction_vars);
+
+ k = LBV_DENOMINATOR (lbv);
+ gcc_assert (k != 0);
+ if (k != 1)
+ expr = fold_build2 (CEIL_DIV_EXPR, type, expr, build_int_cst (type, k));
- /* Create a statement list and a linear expression temporary. */
- stmts = alloc_stmt_list ();
resvar = create_tmp_var (type, "lbvtmp");
add_referenced_var (resvar);
-
- /* Start at 0. */
- 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);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
-
- for (i = 0; VEC_iterate (tree, induction_vars, i, iv); i++)
- {
- if (LBV_COEFFICIENTS (lbv)[i] != 0)
- {
- tree newname;
- tree coeffmult;
-
- /* newname = coefficient * induction_variable */
- coeffmult = build_int_cst (type, LBV_COEFFICIENTS (lbv)[i]);
- 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;
- fold_stmt (&stmt);
- tsi = tsi_last (stmts);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
-
- /* name = 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);
- tsi = tsi_last (stmts);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
-
- }
- }
-
- /* Handle any denominator that occurs. */
- if (LBV_DENOMINATOR (lbv) != 1)
- {
- tree denominator = build_int_cst (type, LBV_DENOMINATOR (lbv));
- 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);
- tsi = tsi_last (stmts);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
- }
- *stmts_to_insert = stmts;
- return name;
+ return force_gimple_operand (fold (expr), stmts_to_insert, true, resvar);
}
/* Convert a linear expression from coefficient and constant form to a
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;
+ int k;
+ tree resvar;
+ tree expr = NULL_TREE;
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 ();
- resvar = create_tmp_var (type, "lletmp");
- add_referenced_var (resvar);
- /* Build up the linear expressions, and put the variable representing the
- result in the results array. */
+ /* Build up the linear expressions. */
for (; lle != NULL; lle = LLE_NEXT (lle))
{
- /* Start at name = 0. */
- 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);
- tsi = tsi_last (stmts);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
-
- /* First do the induction variables.
- at the end, name = name + all the induction variables added
- together. */
- for (i = 0; VEC_iterate (tree, induction_vars, i, iv); i++)
- {
- if (LLE_COEFFICIENTS (lle)[i] != 0)
- {
- tree newname;
- tree mult;
- tree coeff;
+ expr = build_linear_expr (type, LLE_COEFFICIENTS (lle), induction_vars);
+ expr = fold_build2 (PLUS_EXPR, type, expr,
+ build_linear_expr (type,
+ LLE_INVARIANT_COEFFICIENTS (lle),
+ invariants));
+
+ k = LLE_CONSTANT (lle);
+ if (k)
+ expr = fold_build2 (PLUS_EXPR, type, expr, build_int_cst (type, k));
+
+ k = LLE_CONSTANT (offset);
+ if (k)
+ expr = fold_build2 (PLUS_EXPR, type, expr, build_int_cst (type, k));
+
+ k = LLE_DENOMINATOR (lle);
+ if (k != 1)
+ expr = fold_build2 (wrap == MAX_EXPR ? CEIL_DIV_EXPR : FLOOR_DIV_EXPR,
+ type, expr, build_int_cst (type, k));
+
+ expr = fold (expr);
+ VEC_safe_push (tree, heap, results, expr);
+ }
- /* mult = induction variable * coefficient. */
- if (LLE_COEFFICIENTS (lle)[i] == 1)
- {
- mult = VEC_index (tree, induction_vars, i);
- }
- else
- {
- coeff = build_int_cst (type,
- LLE_COEFFICIENTS (lle)[i]);
- mult = fold_build2 (MULT_EXPR, type, iv, coeff);
- }
+ gcc_assert (expr);
- /* newname = 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 = tsi_last (stmts);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
-
- /* name = 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);
- tsi = tsi_last (stmts);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
- }
- }
+ /* We may need to wrap the results in a MAX_EXPR or MIN_EXPR. */
+ if (VEC_length (tree, results) > 1)
+ {
+ size_t i;
+ tree op;
- /* Handle our invariants.
- At the end, we have name = name + result of adding all multiplied
- invariants. */
- for (i = 0; VEC_iterate (tree, invariants, i, invar); i++)
- {
- if (LLE_INVARIANT_COEFFICIENTS (lle)[i] != 0)
- {
- tree newname;
- tree mult;
- tree coeff;
- int invcoeff = LLE_INVARIANT_COEFFICIENTS (lle)[i];
- /* mult = invariant * coefficient */
- if (invcoeff == 1)
- {
- mult = invar;
- }
- else
- {
- coeff = build_int_cst (type, invcoeff);
- mult = fold_build2 (MULT_EXPR, type, invar, coeff);
- }
+ expr = VEC_index (tree, results, 0);
+ for (i = 1; VEC_iterate (tree, results, i, op); i++)
+ expr = fold_build2 (wrap, type, expr, op);
+ }
- /* newname = 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 = tsi_last (stmts);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
-
- /* name = 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);
- tsi = tsi_last (stmts);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
- }
- }
+ VEC_free (tree, heap, results);
- /* Now handle the constant.
- name = name + constant. */
- if (LLE_CONSTANT (lle) != 0)
- {
- 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);
- tsi = tsi_last (stmts);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
- }
+ resvar = create_tmp_var (type, "lletmp");
+ add_referenced_var (resvar);
+ return force_gimple_operand (fold (expr), stmts_to_insert, true, resvar);
+}
- /* Now handle the offset.
- name = name + linear offset. */
- if (LLE_CONSTANT (offset) != 0)
- {
- 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);
- tsi = tsi_last (stmts);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
- }
+/* Remove the induction variable defined at IV_STMT. */
- /* Handle any denominator that occurs. */
- if (LLE_DENOMINATOR (lle) != 1)
+static void
+remove_iv (tree iv_stmt)
+{
+ if (TREE_CODE (iv_stmt) == PHI_NODE)
+ {
+ int i;
+
+ for (i = 0; i < PHI_NUM_ARGS (iv_stmt); i++)
{
- stmt = build_int_cst (type, LLE_DENOMINATOR (lle));
- 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_OPERAND (stmt, 0) = name;
- tsi = tsi_last (stmts);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
+ tree stmt;
+ imm_use_iterator imm_iter;
+ tree arg = PHI_ARG_DEF (iv_stmt, i);
+ bool used = false;
+
+ if (TREE_CODE (arg) != SSA_NAME)
+ continue;
+
+ FOR_EACH_IMM_USE_STMT (stmt, imm_iter, arg)
+ if (stmt != iv_stmt)
+ used = true;
+
+ if (!used)
+ remove_iv (SSA_NAME_DEF_STMT (arg));
}
- VEC_safe_push (tree, heap, results, name);
- }
- /* Again, out of laziness, we don't handle this case yet. It's not
- hard, it just hasn't occurred. */
- gcc_assert (VEC_length (tree, results) <= 2);
-
- /* We may need to wrap the results in a MAX_EXPR or MIN_EXPR. */
- if (VEC_length (tree, results) > 1)
- {
- tree op1 = VEC_index (tree, results, 0);
- tree op2 = VEC_index (tree, results, 1);
- 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);
- tsi_link_after (&tsi, stmt, TSI_CONTINUE_LINKING);
+ remove_phi_node (iv_stmt, NULL_TREE, true);
}
+ else
+ {
+ block_stmt_iterator bsi = bsi_for_stmt (iv_stmt);
- VEC_free (tree, heap, results);
-
- *stmts_to_insert = stmts;
- return name;
+ bsi_remove (&bsi, true);
+ release_defs (iv_stmt);
+ }
}
+
/* Transform a lambda loopnest NEW_LOOPNEST, which had TRANSFORM applied to
it, back into gcc code. This changes the
loops, their induction variables, and their bodies, so that they
type,
new_ivs,
invariants, MAX_EXPR, &stmts);
- bsi_insert_on_edge (loop_preheader_edge (temp), stmts);
- bsi_commit_edge_inserts ();
+
+ if (stmts)
+ {
+ bsi_insert_on_edge (loop_preheader_edge (temp), stmts);
+ bsi_commit_edge_inserts ();
+ }
/* Build the new upper bound and insert its statements in the
basic block of the exit condition */
newupperbound = lle_to_gcc_expression (LL_UPPER_BOUND (newloop),
exit = single_exit (temp);
exitcond = get_loop_exit_condition (temp);
bb = bb_for_stmt (exitcond);
- bsi = bsi_start (bb);
- bsi_insert_after (&bsi, stmts, BSI_NEW_STMT);
+ bsi = bsi_after_labels (bb);
+ if (stmts)
+ bsi_insert_before (&bsi, stmts, BSI_NEW_STMT);
/* Create the new iv. */
test, and let redundancy elimination sort it out. */
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);
+ 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);
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);
+ if (stmts)
+ {
+ bsi = bsi_for_stmt (stmt);
+ 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);
}
+
+ /* Remove the now unused induction variable. */
+ remove_iv (oldiv_stmt);
}
VEC_free (tree, heap, new_ivs);
}
/* 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);
+ in.base.from = use;
+ h = (struct tree_map *) htab_find_with_hash (replacements, &in, in.hash);
if (h != NULL)
{
SET_USE (use_p, h->to);
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);
+ val = force_gimple_operand_bsi (firstbsi, val, false, NULL,
+ true, BSI_SAME_STMT);
+ setstmt = build_gimple_modify_stmt (var, val);
var = make_ssa_name (var, setstmt);
- TREE_OPERAND (setstmt, 0) = var;
+ 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 = GGC_NEW (struct tree_map);
h->hash = in.hash;
- h->from = use;
+ 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);
imm_use_iterator imm_iter;
use_operand_p use_p;
- 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;
- 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 (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
return false;
- 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 (loop, USE_STMT (use_p)))
{
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)
+ 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 = TREE_OPERAND (stmt, 0);
+ tree op0 = GIMPLE_STMT_OPERAND (stmt, 0);
tree scev = instantiate_parameters
(loop, analyze_scalar_evolution (loop, op0));
{
tree arg_stmt = SSA_NAME_DEF_STMT (arg);
- if (bb_for_stmt (arg_stmt)->loop_father
- == loop->inner)
+ if (bb_for_stmt (arg_stmt)
+ && (bb_for_stmt (arg_stmt)->loop_father
+ == loop->inner))
goto fail;
}
}
{
basic_block *bbs;
tree exit_condition;
- tree then_label, else_label, cond_stmt;
+ tree cond_stmt;
basic_block preheaderbb, headerbb, bodybb, latchbb, olddest;
int i;
block_stmt_iterator bsi, firstbsi;
}
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)
bodybb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
latchbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
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 = build3 (COND_EXPR, void_type_node,
build2 (NE_EXPR, boolean_type_node,
integer_one_node,
integer_zero_node),
- then_label, else_label);
+ NULL_TREE, NULL_TREE);
bsi = bsi_start (bodybb);
bsi_insert_after (&bsi, cond_stmt, BSI_NEW_STMT);
e = make_edge (bodybb, olddest, EDGE_FALSE_VALUE);
newloop = duplicate_loop (loop, olddest->loop_father);
newloop->header = headerbb;
newloop->latch = latchbb;
- 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, preheaderbb,
single_exit (loop)->src);
set_immediate_dominator (CDI_DOMINATORS, latchbb, bodybb);
- set_immediate_dominator (CDI_DOMINATORS, olddest, bodybb);
+ set_immediate_dominator (CDI_DOMINATORS, olddest,
+ recompute_dominator (CDI_DOMINATORS, olddest));
/* Create the new iv. */
oldivvar = VEC_index (tree, loopivs, 0);
ivvar = create_tmp_var (TREE_TYPE (oldivvar), "perfectiv");
exit_condition = get_loop_exit_condition (newloop);
uboundvar = create_tmp_var (integer_type_node, "uboundvar");
add_referenced_var (uboundvar);
- stmt = build2 (MODIFY_EXPR, void_type_node, uboundvar,
- VEC_index (tree, ubounds, 0));
+ 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);