/* High-level loop manipulation functions.
- Copyright (C) 2004, 2005 Free Software Foundation, Inc.
+ Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
This file is part of GCC.
}
else
{
- if (!tree_expr_nonnegative_p (step)
+ bool ovf;
+
+ if (!tree_expr_nonnegative_warnv_p (step, &ovf)
&& may_negate_without_overflow_p (step))
{
incr_op = MINUS_EXPR;
if (stmts)
bsi_insert_on_edge_immediate (pe, stmts);
- stmt = build2_gimple (GIMPLE_MODIFY_STMT, va,
- build2 (incr_op, TREE_TYPE (base), vb, step));
+ stmt = build_gimple_modify_stmt (va,
+ build2 (incr_op, TREE_TYPE (base),
+ vb, step));
SSA_NAME_DEF_STMT (va) = stmt;
if (after)
bsi_insert_after (incr_pos, stmt, BSI_NEW_STMT);
void
rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
{
- bitmap loop_exits = get_loops_exits ();
+ bitmap loop_exits;
bitmap *use_blocks;
unsigned i, old_num_ssa_names;
- bitmap names_to_rename = BITMAP_ALLOC (NULL);
+ bitmap names_to_rename;
+
+ if (!current_loops)
+ return;
+
+ loop_exits = get_loops_exits ();
+ names_to_rename = BITMAP_ALLOC (NULL);
/* If the pass has caused the SSA form to be out-of-date, update it
now. */
/* Fix up all the names found to be used outside their original
loops. */
update_ssa (TODO_update_ssa);
+
+ current_loops->state |= LOOP_CLOSED_SSA;
}
/* Check invariants of the loop closed ssa form for the USE in BB. */
bb = single_pred (loop->latch);
last = last_stmt (bb);
- if (TREE_CODE (last) != COND_EXPR)
+ if (!last
+ || TREE_CODE (last) != COND_EXPR)
return NULL;
exit = EDGE_SUCC (bb, 0);
return true;
}
-/* Build if (COND) goto THEN_LABEL; else goto ELSE_LABEL; */
-
-static tree
-build_if_stmt (tree cond, tree then_label, tree else_label)
-{
- return build3 (COND_EXPR, void_type_node,
- cond,
- build1 (GOTO_EXPR, void_type_node, then_label),
- build1 (GOTO_EXPR, void_type_node, else_label));
-}
-
/* Returns true if we can unroll LOOP FACTOR times. Number
of iterations of the loop is returned in NITER. */
*exit_bound = bound;
}
+/* Scales the frequencies of all basic blocks in LOOP that are strictly
+ dominated by BB by NUM/DEN. */
+
+static void
+scale_dominated_blocks_in_loop (struct loop *loop, basic_block bb,
+ int num, int den)
+{
+ basic_block son;
+
+ if (den == 0)
+ return;
+
+ for (son = first_dom_son (CDI_DOMINATORS, bb);
+ son;
+ son = next_dom_son (CDI_DOMINATORS, son))
+ {
+ if (!flow_bb_inside_loop_p (loop, son))
+ continue;
+ scale_bbs_frequencies_int (&son, 1, num, den);
+ scale_dominated_blocks_in_loop (loop, son, num, den);
+ }
+}
+
/* Unroll LOOP FACTOR times. DESC describes number of iterations of LOOP.
EXIT is the exit of the loop to that DESC corresponds.
transform_callback transform,
void *data)
{
- tree dont_exit, exit_if, ctr_before, ctr_after;
+ tree exit_if, ctr_before, ctr_after;
tree enter_main_cond, exit_base, exit_step, exit_bound;
enum tree_code exit_cmp;
tree phi_old_loop, phi_new_loop, phi_rest, init, next, new_init, var;
struct loop *new_loop;
basic_block rest, exit_bb;
edge old_entry, new_entry, old_latch, precond_edge, new_exit;
- edge new_nonexit;
+ edge new_nonexit, e;
block_stmt_iterator bsi;
use_operand_p op;
bool ok;
unsigned est_niter, prob_entry, scale_unrolled, scale_rest, freq_e, freq_h;
- unsigned new_est_niter;
+ unsigned new_est_niter, i, prob;
unsigned irr = loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP;
sbitmap wont_exit;
+ VEC (edge, heap) *to_remove = NULL;
est_niter = expected_loop_iterations (loop);
determine_exit_conditions (loop, desc, factor,
new_est_niter = 5;
}
- /* Prepare the cfg and update the phi nodes. */
+ /* Prepare the cfg and update the phi nodes. Move the loop exit to the
+ loop latch (and make its condition dummy, for the moment). */
rest = loop_preheader_edge (new_loop)->src;
precond_edge = single_pred_edge (rest);
split_edge (loop_latch_edge (loop));
exit_bb = single_pred (loop->latch);
- /* For the moment, make it appear that the new exit edge cannot
- be taken. */
+ /* Since the exit edge will be removed, the frequency of all the blocks
+ in the loop that are dominated by it must be scaled by
+ 1 / (1 - exit->probability). */
+ scale_dominated_blocks_in_loop (loop, exit->src,
+ REG_BR_PROB_BASE,
+ REG_BR_PROB_BASE - exit->probability);
+
bsi = bsi_last (exit_bb);
- exit_if = build_if_stmt (boolean_true_node,
- tree_block_label (loop->latch),
- tree_block_label (rest));
+ exit_if = build3 (COND_EXPR, void_type_node, boolean_true_node,
+ NULL_TREE, NULL_TREE);
+
bsi_insert_after (&bsi, exit_if, BSI_NEW_STMT);
new_exit = make_edge (exit_bb, rest, EDGE_FALSE_VALUE | irr);
rescan_loop_exit (new_exit, true, false);
- new_exit->count = 0;
- new_exit->probability = 0;
+
+ /* Set the probability of new exit to the same of the old one. Fix
+ the frequency of the latch block, by scaling it back by
+ 1 - exit->probability. */
+ new_exit->count = exit->count;
+ new_exit->probability = exit->probability;
new_nonexit = single_pred_edge (loop->latch);
+ new_nonexit->probability = REG_BR_PROB_BASE - exit->probability;
new_nonexit->flags = EDGE_TRUE_VALUE;
+ new_nonexit->count -= exit->count;
+ if (new_nonexit->count < 0)
+ new_nonexit->count = 0;
+ scale_bbs_frequencies_int (&loop->latch, 1, new_nonexit->probability,
+ REG_BR_PROB_BASE);
old_entry = loop_preheader_edge (loop);
new_entry = loop_preheader_edge (new_loop);
SET_USE (op, new_init);
}
+ remove_path (exit);
+
/* Transform the loop. */
if (transform)
(*transform) (loop, data);
- /* Unroll the loop and remove the old exits. */
- dont_exit = ((exit->flags & EDGE_TRUE_VALUE)
- ? boolean_false_node
- : boolean_true_node);
- exit_if = last_stmt (exit->src);
- COND_EXPR_COND (exit_if) = dont_exit;
- update_stmt (exit_if);
-
+ /* Unroll the loop and remove the exits in all iterations except for the
+ last one. */
wont_exit = sbitmap_alloc (factor);
sbitmap_ones (wont_exit);
+ RESET_BIT (wont_exit, factor - 1);
+
ok = tree_duplicate_loop_to_header_edge
(loop, loop_latch_edge (loop), factor - 1,
- wont_exit, exit, NULL, DLTHE_FLAG_UPDATE_FREQ);
+ wont_exit, new_exit, &to_remove, DLTHE_FLAG_UPDATE_FREQ);
free (wont_exit);
gcc_assert (ok);
+
+ for (i = 0; VEC_iterate (edge, to_remove, i, e); i++)
+ {
+ ok = remove_path (e);
+ gcc_assert (ok);
+ }
+ VEC_free (edge, heap, to_remove);
update_ssa (TODO_update_ssa);
/* Ensure that the frequencies in the loop match the new estimated
rest->frequency += EDGE_FREQUENCY (new_exit);
new_nonexit = single_pred_edge (loop->latch);
+ prob = new_nonexit->probability;
new_nonexit->probability = REG_BR_PROB_BASE - new_exit->probability;
+ new_nonexit->count = exit_bb->count - new_exit->count;
+ if (new_nonexit->count < 0)
+ new_nonexit->count = 0;
scale_bbs_frequencies_int (&loop->latch, 1, new_nonexit->probability,
- REG_BR_PROB_BASE);
+ prob);
/* Finally create the new counter for number of iterations and add the new
exit instruction. */
OSDN Git Service
