/* High-level loop manipulation functions.
- Copyright (C) 2004 Free Software Foundation, Inc.
+ Copyright (C) 2004, 2005 Free Software Foundation, Inc.
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-pass.h"
#include "cfglayout.h"
#include "tree-scalar-evolution.h"
+#include "params.h"
/* Creates an induction variable with value BASE + STEP * iteration in LOOP.
It is expected that neither BASE nor STEP are shared with other expressions
(unless the sharing rules allow this). Use VAR as a base var_decl for it
(if NULL, a new temporary will be created). The increment will occur at
- INCR_POS (after it if AFTER is true, before it otherwise). The ssa versions
+ INCR_POS (after it if AFTER is true, before it otherwise). INCR_POS and
+ AFTER can be computed using standard_iv_increment_position. The ssa versions
of the variable before and after increment will be stored in VAR_BEFORE and
VAR_AFTER (unless they are NULL). */
tree stmt, initial, step1, stmts;
tree vb, va;
enum tree_code incr_op = PLUS_EXPR;
+ edge pe = loop_preheader_edge (loop);
if (!var)
{
var = create_tmp_var (TREE_TYPE (base), "ivtmp");
- add_referenced_tmp_var (var);
+ add_referenced_var (var);
}
vb = make_ssa_name (var, NULL_TREE);
{
if (TYPE_UNSIGNED (TREE_TYPE (step)))
{
- step1 = fold (build1 (NEGATE_EXPR, TREE_TYPE (step), step));
+ step1 = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
if (tree_int_cst_lt (step1, step))
{
incr_op = MINUS_EXPR;
&& may_negate_without_overflow_p (step))
{
incr_op = MINUS_EXPR;
- step = fold (build1 (NEGATE_EXPR, TREE_TYPE (step), step));
+ step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
}
}
}
- stmt = build2 (MODIFY_EXPR, void_type_node, va,
- build2 (incr_op, TREE_TYPE (base),
- vb, step));
+ /* Gimplify the step if necessary. We put the computations in front of the
+ loop (i.e. the step should be loop invariant). */
+ step = force_gimple_operand (step, &stmts, true, var);
+ if (stmts)
+ bsi_insert_on_edge_immediate (pe, stmts);
+
+ stmt = build2_gimple (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);
initial = force_gimple_operand (base, &stmts, true, var);
if (stmts)
- {
- edge pe = loop_preheader_edge (loop);
-
- bsi_insert_on_edge_immediate_loop (pe, stmts);
- }
+ bsi_insert_on_edge_immediate (pe, stmts);
stmt = create_phi_node (vb, loop->header);
SSA_NAME_DEF_STMT (vb) = stmt;
- add_phi_arg (&stmt, initial, loop_preheader_edge (loop));
- add_phi_arg (&stmt, va, loop_latch_edge (loop));
+ add_phi_arg (stmt, initial, loop_preheader_edge (loop));
+ add_phi_arg (stmt, va, loop_latch_edge (loop));
}
/* Add exit phis for the USE on EXIT. */
return;
phi = create_phi_node (use, exit);
-
+ create_new_def_for (PHI_RESULT (phi), phi, PHI_RESULT_PTR (phi));
FOR_EACH_EDGE (e, ei, exit->preds)
- add_phi_arg (&phi, use, e);
-
- SSA_NAME_DEF_STMT (use) = def_stmt;
+ add_phi_arg (phi, use, e);
}
/* Add exit phis for VAR that is used in LIVEIN.
basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
bitmap_iterator bi;
- bitmap_clear_bit (livein, def_bb->index);
+ if (is_gimple_reg (var))
+ bitmap_clear_bit (livein, def_bb->index);
+ else
+ bitmap_set_bit (livein, def_bb->index);
- def = BITMAP_XMALLOC ();
+ def = BITMAP_ALLOC (NULL);
bitmap_set_bit (def, def_bb->index);
compute_global_livein (livein, def);
- BITMAP_XFREE (def);
+ BITMAP_FREE (def);
EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index, bi)
{
static bitmap
get_loops_exits (void)
{
- bitmap exits = BITMAP_XMALLOC ();
+ bitmap exits = BITMAP_ALLOC (NULL);
basic_block bb;
edge e;
edge_iterator ei;
/* For USE in BB, if it is used outside of the loop it is defined in,
mark it for rewrite. Record basic block BB where it is used
- to USE_BLOCKS. */
+ to USE_BLOCKS. Record the ssa name index to NEED_PHIS bitmap. */
static void
-find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks)
+find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks,
+ bitmap need_phis)
{
unsigned ver;
basic_block def_bb;
if (TREE_CODE (use) != SSA_NAME)
return;
+ /* We don't need to keep virtual operands in loop-closed form. */
+ if (!is_gimple_reg (use))
+ return;
+
ver = SSA_NAME_VERSION (use);
def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use));
if (!def_bb)
return;
if (!use_blocks[ver])
- use_blocks[ver] = BITMAP_XMALLOC ();
+ use_blocks[ver] = BITMAP_ALLOC (NULL);
bitmap_set_bit (use_blocks[ver], bb->index);
- if (!flow_bb_inside_loop_p (def_loop, bb))
- mark_for_rewrite (use);
+ bitmap_set_bit (need_phis, ver);
}
/* For uses in STMT, mark names that are used outside of the loop they are
defined to rewrite. Record the set of blocks in that the ssa
- names are defined to USE_BLOCKS. */
+ names are defined to USE_BLOCKS and the ssa names themselves to
+ NEED_PHIS. */
static void
-find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks)
+find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks, bitmap need_phis)
{
ssa_op_iter iter;
tree var;
basic_block bb = bb_for_stmt (stmt);
- get_stmt_operands (stmt);
-
- FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
- find_uses_to_rename_use (bb, var, use_blocks);
+ FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES)
+ find_uses_to_rename_use (bb, var, use_blocks, need_phis);
}
+/* Marks names that are used in BB and outside of the loop they are
+ defined in for rewrite. Records the set of blocks in that the ssa
+ names are defined to USE_BLOCKS. Record the SSA names that will
+ need exit PHIs in NEED_PHIS. */
+
+static void
+find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis)
+{
+ block_stmt_iterator bsi;
+ edge e;
+ edge_iterator ei;
+ tree phi;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
+ find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e),
+ use_blocks, need_phis);
+
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks, need_phis);
+}
+
/* Marks names that are used outside of the loop they are defined in
for rewrite. Records the set of blocks in that the ssa
- names are defined to USE_BLOCKS. */
+ names are defined to USE_BLOCKS. If CHANGED_BBS is not NULL,
+ scan only blocks in this set. */
static void
-find_uses_to_rename (bitmap *use_blocks)
+find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis)
{
basic_block bb;
- block_stmt_iterator bsi;
- tree phi;
- unsigned i;
+ unsigned index;
+ bitmap_iterator bi;
- FOR_EACH_BB (bb)
+ if (changed_bbs && !bitmap_empty_p (changed_bbs))
{
- for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
- for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
- find_uses_to_rename_use (PHI_ARG_EDGE (phi, i)->src,
- PHI_ARG_DEF (phi, i), use_blocks);
-
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks);
+ EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi)
+ {
+ find_uses_to_rename_bb (BASIC_BLOCK (index), use_blocks, need_phis);
+ }
+ }
+ else
+ {
+ FOR_EACH_BB (bb)
+ {
+ find_uses_to_rename_bb (bb, use_blocks, need_phis);
+ }
}
}
Looking from the outer loop with the normal SSA form, the first use of k
is not well-behaved, while the second one is an induction variable with
- base 99 and step 1. */
+ base 99 and step 1.
+
+ If CHANGED_BBS is not NULL, we look for uses outside loops only in
+ the basic blocks in this set.
+
+ UPDATE_FLAG is used in the call to update_ssa. See
+ TODO_update_ssa* for documentation. */
void
-rewrite_into_loop_closed_ssa (void)
+rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
{
bitmap loop_exits = get_loops_exits ();
bitmap *use_blocks;
- unsigned i;
- bitmap names_to_rename;
+ unsigned i, old_num_ssa_names;
+ bitmap names_to_rename = BITMAP_ALLOC (NULL);
- gcc_assert (!any_marked_for_rewrite_p ());
+ /* If the pass has caused the SSA form to be out-of-date, update it
+ now. */
+ update_ssa (update_flag);
- use_blocks = xcalloc (num_ssa_names, sizeof (bitmap));
+ old_num_ssa_names = num_ssa_names;
+ use_blocks = XCNEWVEC (bitmap, old_num_ssa_names);
/* Find the uses outside loops. */
- find_uses_to_rename (use_blocks);
+ find_uses_to_rename (changed_bbs, use_blocks, names_to_rename);
- /* Add the phi nodes on exits of the loops for the names we need to
+ /* Add the PHI nodes on exits of the loops for the names we need to
rewrite. */
- names_to_rename = marked_ssa_names ();
add_exit_phis (names_to_rename, use_blocks, loop_exits);
- for (i = 0; i < num_ssa_names; i++)
- BITMAP_XFREE (use_blocks[i]);
+ for (i = 0; i < old_num_ssa_names; i++)
+ BITMAP_FREE (use_blocks[i]);
free (use_blocks);
- BITMAP_XFREE (loop_exits);
- BITMAP_XFREE (names_to_rename);
+ BITMAP_FREE (loop_exits);
+ BITMAP_FREE (names_to_rename);
- /* Do the rewriting. */
- rewrite_ssa_into_ssa ();
+ /* Fix up all the names found to be used outside their original
+ loops. */
+ update_ssa (TODO_update_ssa);
}
/* Check invariants of the loop closed ssa form for the USE in BB. */
tree def;
basic_block def_bb;
- if (TREE_CODE (use) != SSA_NAME)
+ if (TREE_CODE (use) != SSA_NAME || !is_gimple_reg (use))
return;
def = SSA_NAME_DEF_STMT (use);
ssa_op_iter iter;
tree var;
- get_stmt_operands (stmt);
-
FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES)
check_loop_closed_ssa_use (bb, var);
}
tree phi;
unsigned i;
- verify_ssa ();
+ if (current_loops == NULL)
+ return;
+
+ verify_ssa (false);
FOR_EACH_BB (bb)
{
split_loop_exit_edge (edge exit)
{
basic_block dest = exit->dest;
- basic_block bb = loop_split_edge_with (exit, NULL);
+ basic_block bb = split_edge (exit);
tree phi, new_phi, new_name, name;
use_operand_p op_p;
for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
{
- op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, EDGE_SUCC (bb, 0));
+ op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, single_succ_edge (bb));
name = USE_FROM_PTR (op_p);
- /* If the argument of the phi node is a constant, we do not need
+ /* If the argument of the PHI node is a constant, we do not need
to keep it inside loop. */
if (TREE_CODE (name) != SSA_NAME)
continue;
/* Otherwise create an auxiliary phi node that will copy the value
- of the ssa name out of the loop. */
+ of the SSA name out of the loop. */
new_name = duplicate_ssa_name (name, NULL);
new_phi = create_phi_node (new_name, bb);
SSA_NAME_DEF_STMT (new_name) = new_phi;
- add_phi_arg (&new_phi, name, exit);
+ add_phi_arg (new_phi, name, exit);
SET_USE (op_p, new_name);
}
}
-/* Insert statement STMT to the edge E and update the loop structures.
- Returns the newly created block (if any). */
-
-basic_block
-bsi_insert_on_edge_immediate_loop (edge e, tree stmt)
-{
- basic_block src, dest, new_bb;
- struct loop *loop_c;
-
- src = e->src;
- dest = e->dest;
-
- loop_c = find_common_loop (src->loop_father, dest->loop_father);
-
- new_bb = bsi_insert_on_edge_immediate (e, stmt);
-
- if (!new_bb)
- return NULL;
-
- add_bb_to_loop (new_bb, loop_c);
- if (dest->loop_father->latch == src)
- dest->loop_father->latch = new_bb;
-
- return new_bb;
-}
-
/* Returns the basic block in that statements should be emitted for induction
variables incremented at the end of the LOOP. */
basic_block bb;
edge exit;
- if (EDGE_COUNT (loop->latch->preds) > 1)
+ if (!single_pred_p (loop->latch))
return NULL;
- bb = EDGE_PRED (loop->latch, 0)->src;
+ bb = single_pred (loop->latch);
last = last_stmt (bb);
if (TREE_CODE (last) != COND_EXPR)
return NULL;
unsigned i;
for (i = first_new_block; i < (unsigned) last_basic_block; i++)
- BASIC_BLOCK (i)->rbi->duplicated = 1;
+ BASIC_BLOCK (i)->flags |= BB_DUPLICATED;
for (i = first_new_block; i < (unsigned) last_basic_block; i++)
add_phi_args_after_copy_bb (BASIC_BLOCK (i));
for (i = first_new_block; i < (unsigned) last_basic_block; i++)
- BASIC_BLOCK (i)->rbi->duplicated = 0;
+ BASIC_BLOCK (i)->flags &= ~BB_DUPLICATED;
}
-/* Renames variables in the area copied by tree_duplicate_loop_to_header_edge.
- FIRST_NEW_BLOCK is the first block in the copied area. DEFINITIONS is
- a bitmap of all ssa names defined inside the loop. */
-
-static void
-rename_variables (unsigned first_new_block, bitmap definitions)
-{
- unsigned i, copy_number = 0;
- basic_block bb;
- htab_t ssa_name_map = NULL;
-
- for (i = first_new_block; i < (unsigned) last_basic_block; i++)
- {
- bb = BASIC_BLOCK (i);
-
- /* We assume that first come all blocks from the first copy, then all
- blocks from the second copy, etc. */
- if (copy_number != (unsigned) bb->rbi->copy_number)
- {
- allocate_ssa_names (definitions, &ssa_name_map);
- copy_number = bb->rbi->copy_number;
- }
-
- rewrite_to_new_ssa_names_bb (bb, ssa_name_map);
- }
-
- htab_delete (ssa_name_map);
-}
-
-/* Sets SSA_NAME_DEF_STMT for results of all phi nodes in BB. */
-
-static void
-set_phi_def_stmts (basic_block bb)
-{
- tree phi;
- for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
- SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = phi;
-}
+/* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also
+ updates the PHI nodes at start of the copied region. In order to
+ achieve this, only loops whose exits all lead to the same location
+ are handled.
-/* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also updates
- ssa. In order to achieve this, only loops whose exits all lead to the same
- location are handled.
-
- FIXME: we create some degenerate phi nodes that could be avoided by copy
- propagating them instead. Unfortunately this is not completely
- straightforward due to problems with constant folding. */
+ Notice that we do not completely update the SSA web after
+ duplication. The caller is responsible for calling update_ssa
+ after the loop has been duplicated. */
bool
tree_duplicate_loop_to_header_edge (struct loop *loop, edge e,
- struct loops *loops,
unsigned int ndupl, sbitmap wont_exit,
edge orig, edge *to_remove,
unsigned int *n_to_remove, int flags)
{
unsigned first_new_block;
- basic_block bb;
- unsigned i;
- bitmap definitions;
- if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES))
+ if (!(current_loops->state & LOOPS_HAVE_SIMPLE_LATCHES))
return false;
- if (!(loops->state & LOOPS_HAVE_PREHEADERS))
+ if (!(current_loops->state & LOOPS_HAVE_PREHEADERS))
return false;
#ifdef ENABLE_CHECKING
verify_loop_closed_ssa ();
#endif
- gcc_assert (!any_marked_for_rewrite_p ());
-
first_new_block = last_basic_block;
- if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit,
+ if (!duplicate_loop_to_header_edge (loop, e, ndupl, wont_exit,
orig, to_remove, n_to_remove, flags))
return false;
/* Copy the phi node arguments. */
copy_phi_node_args (first_new_block);
- /* Rename the variables. */
- definitions = marked_ssa_names ();
- rename_variables (first_new_block, definitions);
- unmark_all_for_rewrite ();
- BITMAP_XFREE (definitions);
-
- /* For some time we have the identical ssa names as results in multiple phi
- nodes. When phi node is resized, it sets SSA_NAME_DEF_STMT of its result
- to the new copy. This means that we cannot easily ensure that the ssa
- names defined in those phis are pointing to the right one -- so just
- recompute SSA_NAME_DEF_STMT for them. */
-
- for (i = first_new_block; i < (unsigned) last_basic_block; i++)
- {
- bb = BASIC_BLOCK (i);
- set_phi_def_stmts (bb);
- if (bb->rbi->copy_number == 1)
- set_phi_def_stmts (bb->rbi->original);
- }
-
scev_reset ();
-#ifdef ENABLE_CHECKING
- verify_loop_closed_ssa ();
-#endif
return true;
}
-/*---------------------------------------------------------------------------
- Loop versioning
- ---------------------------------------------------------------------------*/
-
-/* Adjust phi nodes for 'first' basic block. 'second' basic block is a copy
- of 'first'. Both of them are dominated by 'new_head' basic block. When
- 'new_head' was created by 'second's incoming edge it received phi arguments
- on the edge by split_edge(). Later, additional edge 'e' was created to
- connect 'new_head' and 'first'. Now this routine adds phi args on this
- additional edge 'e' that new_head to second edge received as part of edge
- splitting.
-*/
+/* Build if (COND) goto THEN_LABEL; else goto ELSE_LABEL; */
-static void
-lv_adjust_loop_header_phi (basic_block first, basic_block second,
- basic_block new_head, edge e)
+static tree
+build_if_stmt (tree cond, tree then_label, tree else_label)
{
- tree phi1, phi2;
+ return build3 (COND_EXPR, void_type_node,
+ cond,
+ build1 (GOTO_EXPR, void_type_node, then_label),
+ build1 (GOTO_EXPR, void_type_node, else_label));
+}
- /* Browse all 'second' basic block phi nodes and add phi args to
- edge 'e' for 'first' head. PHI args are always in correct order. */
+/* Returns true if we can unroll LOOP FACTOR times. Number
+ of iterations of the loop is returned in NITER. */
- for (phi2 = phi_nodes (second), phi1 = phi_nodes (first);
- phi2 && phi1;
- phi2 = PHI_CHAIN (phi2), phi1 = PHI_CHAIN (phi1))
- {
- int i;
- for (i = 0; i < PHI_NUM_ARGS (phi2); i++)
- {
- if (PHI_ARG_EDGE (phi2, i)->src == new_head)
- {
- tree def = PHI_ARG_DEF (phi2, i);
- add_phi_arg (&phi1, def, e);
- }
- }
- }
-}
+bool
+can_unroll_loop_p (struct loop *loop, unsigned factor,
+ struct tree_niter_desc *niter)
+{
+ edge exit;
-/* Adjust entry edge for lv.
-
- e is an incoming edge.
+ /* Check whether unrolling is possible. We only want to unroll loops
+ for that we are able to determine number of iterations. We also
+ want to split the extra iterations of the loop from its end,
+ therefore we require that the loop has precisely one
+ exit. */
- --- edge e ---- > [second_head]
+ exit = single_dom_exit (loop);
+ if (!exit)
+ return false;
- Split it and insert new conditional expression and adjust edges.
-
- --- edge e ---> [cond expr] ---> [first_head]
- |
- +---------> [second_head]
+ if (!number_of_iterations_exit (loop, exit, niter, false)
+ || niter->cmp == ERROR_MARK
+ /* Scalar evolutions analysis might have copy propagated
+ the abnormal ssa names into these expressions, hence
+ emitting the computations based on them during loop
+ unrolling might create overlapping life ranges for
+ them, and failures in out-of-ssa. */
+ || contains_abnormal_ssa_name_p (niter->may_be_zero)
+ || contains_abnormal_ssa_name_p (niter->control.base)
+ || contains_abnormal_ssa_name_p (niter->control.step)
+ || contains_abnormal_ssa_name_p (niter->bound))
+ return false;
-*/
-
-static basic_block
-lv_adjust_loop_entry_edge (basic_block first_head,
- basic_block second_head,
- edge e,
- tree cond_expr)
-{
- block_stmt_iterator bsi;
- basic_block new_head = NULL;
- tree goto1 = NULL_TREE;
- tree goto2 = NULL_TREE;
- tree new_cond_expr = NULL_TREE;
- edge e0, e1;
-
- gcc_assert (e->dest == second_head);
-
- /* Split edge 'e'. This will create a new basic block, where we can
- insert conditional expr. */
- new_head = split_edge (e);
-
- /* Build new conditional expr */
- goto1 = build1 (GOTO_EXPR, void_type_node, tree_block_label (first_head));
- goto2 = build1 (GOTO_EXPR, void_type_node, tree_block_label (second_head));
- new_cond_expr = build3 (COND_EXPR, void_type_node, cond_expr, goto1, goto2);
-
- /* Add new cond. in new head. */
- bsi = bsi_start (new_head);
- bsi_insert_after (&bsi, new_cond_expr, BSI_NEW_STMT);
-
- /* Adjust edges appropriately to connect new head with first head
- as well as second head. */
- e0 = EDGE_SUCC (new_head, 0);
- e0->flags &= ~EDGE_FALLTHRU;
- e0->flags |= EDGE_FALSE_VALUE;
- e1 = make_edge (new_head, first_head, EDGE_TRUE_VALUE);
- set_immediate_dominator (CDI_DOMINATORS, first_head, new_head);
- set_immediate_dominator (CDI_DOMINATORS, second_head, new_head);
-
- /* Adjust loop header phi nodes. */
- lv_adjust_loop_header_phi (first_head, second_head, new_head, e1);
-
- return new_head;
-}
+ /* And of course, we must be able to duplicate the loop. */
+ if (!can_duplicate_loop_p (loop))
+ return false;
-/* Main entry point for Loop Versioning transformation.
-
-This transformation given a condition and a loop, creates
--if (condition) { loop_copy1 } else { loop_copy2 },
-where loop_copy1 is the loop transformed in one way, and loop_copy2
-is the loop transformed in another way (or unchanged). 'condition'
-may be a run time test for things that were not resolved by static
-analysis (overlapping ranges (anti-aliasing), alignment, etc.). */
-
-struct loop *
-tree_ssa_loop_version (struct loops *loops, struct loop * loop,
- tree cond_expr, basic_block *condition_bb)
-{
- edge entry, latch_edge, exit, true_edge, false_edge;
- basic_block first_head, second_head;
- int irred_flag;
- struct loop *nloop;
+ /* The final loop should be small enough. */
+ if (tree_num_loop_insns (loop) * factor
+ > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS))
+ return false;
- /* CHECKME: Loop versioning does not handle nested loop at this point. */
- if (loop->inner)
- return NULL;
+ return true;
+}
- /* Record entry and latch edges for the loop */
- entry = loop_preheader_edge (loop);
+/* Determines the conditions that control execution of LOOP unrolled FACTOR
+ times. DESC is number of iterations of LOOP. ENTER_COND is set to
+ condition that must be true if the main loop can be entered.
+ EXIT_BASE, EXIT_STEP, EXIT_CMP and EXIT_BOUND are set to values describing
+ how the exit from the unrolled loop should be controlled. */
- /* Note down head of loop as first_head. */
- first_head = entry->dest;
+static void
+determine_exit_conditions (struct loop *loop, struct tree_niter_desc *desc,
+ unsigned factor, tree *enter_cond,
+ tree *exit_base, tree *exit_step,
+ enum tree_code *exit_cmp, tree *exit_bound)
+{
+ tree stmts;
+ tree base = desc->control.base;
+ tree step = desc->control.step;
+ tree bound = desc->bound;
+ tree type = TREE_TYPE (base);
+ tree bigstep, delta;
+ tree min = lower_bound_in_type (type, type);
+ tree max = upper_bound_in_type (type, type);
+ enum tree_code cmp = desc->cmp;
+ tree cond = boolean_true_node, assum;
+
+ *enter_cond = boolean_false_node;
+ *exit_base = NULL_TREE;
+ *exit_step = NULL_TREE;
+ *exit_cmp = ERROR_MARK;
+ *exit_bound = NULL_TREE;
+ gcc_assert (cmp != ERROR_MARK);
+
+ /* We only need to be correct when we answer question
+ "Do at least FACTOR more iterations remain?" in the unrolled loop.
+ Thus, transforming BASE + STEP * i <> BOUND to
+ BASE + STEP * i < BOUND is ok. */
+ if (cmp == NE_EXPR)
+ {
+ if (tree_int_cst_sign_bit (step))
+ cmp = GT_EXPR;
+ else
+ cmp = LT_EXPR;
+ }
+ else if (cmp == LT_EXPR)
+ {
+ gcc_assert (!tree_int_cst_sign_bit (step));
+ }
+ else if (cmp == GT_EXPR)
+ {
+ gcc_assert (tree_int_cst_sign_bit (step));
+ }
+ else
+ gcc_unreachable ();
+
+ /* The main body of the loop may be entered iff:
+
+ 1) desc->may_be_zero is false.
+ 2) it is possible to check that there are at least FACTOR iterations
+ of the loop, i.e., BOUND - step * FACTOR does not overflow.
+ 3) # of iterations is at least FACTOR */
+
+ if (!zero_p (desc->may_be_zero))
+ cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
+ invert_truthvalue (desc->may_be_zero),
+ cond);
+
+ bigstep = fold_build2 (MULT_EXPR, type, step,
+ build_int_cst_type (type, factor));
+ delta = fold_build2 (MINUS_EXPR, type, bigstep, step);
+ if (cmp == LT_EXPR)
+ assum = fold_build2 (GE_EXPR, boolean_type_node,
+ bound,
+ fold_build2 (PLUS_EXPR, type, min, delta));
+ else
+ assum = fold_build2 (LE_EXPR, boolean_type_node,
+ bound,
+ fold_build2 (PLUS_EXPR, type, max, delta));
+ cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond);
- /* Duplicate loop. */
- irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
- entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
- if (!tree_duplicate_loop_to_header_edge (loop, entry, loops, 1,
- NULL, NULL, NULL, NULL, 0))
+ bound = fold_build2 (MINUS_EXPR, type, bound, delta);
+ assum = fold_build2 (cmp, boolean_type_node, base, bound);
+ cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond);
+
+ cond = force_gimple_operand (unshare_expr (cond), &stmts, false, NULL_TREE);
+ if (stmts)
+ bsi_insert_on_edge_immediate (loop_preheader_edge (loop), stmts);
+ /* cond now may be a gimple comparison, which would be OK, but also any
+ other gimple rhs (say a && b). In this case we need to force it to
+ operand. */
+ if (!is_gimple_condexpr (cond))
{
- entry->flags |= irred_flag;
- return NULL;
+ cond = force_gimple_operand (cond, &stmts, true, NULL_TREE);
+ if (stmts)
+ bsi_insert_on_edge_immediate (loop_preheader_edge (loop), stmts);
}
+ *enter_cond = cond;
- /* After duplication entry edge now points to new loop head block.
- Note down new head as second_head. */
- second_head = entry->dest;
+ base = force_gimple_operand (unshare_expr (base), &stmts, true, NULL_TREE);
+ if (stmts)
+ bsi_insert_on_edge_immediate (loop_preheader_edge (loop), stmts);
+ bound = force_gimple_operand (unshare_expr (bound), &stmts, true, NULL_TREE);
+ if (stmts)
+ bsi_insert_on_edge_immediate (loop_preheader_edge (loop), stmts);
- /* Split loop entry edge and insert new block with cond expr. */
- *condition_bb = lv_adjust_loop_entry_edge (first_head, second_head, entry,
- cond_expr);
+ *exit_base = base;
+ *exit_step = bigstep;
+ *exit_cmp = cmp;
+ *exit_bound = bound;
+}
- latch_edge = EDGE_SUCC (loop->latch->rbi->copy, 0);
-
- extract_true_false_edges_from_block (*condition_bb, &true_edge, &false_edge);
- nloop = loopify (loops,
- latch_edge,
- EDGE_PRED (loop->header->rbi->copy, 0),
- *condition_bb, true_edge, false_edge,
- false /* Do not redirect all edges. */);
-
- exit = loop->single_exit;
- if (exit)
- nloop->single_exit = find_edge (exit->src->rbi->copy, exit->dest);
-
- /* loopify redirected latch_edge. Update its PENDING_STMTS. */
- flush_pending_stmts (latch_edge);
-
- /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS. */
- extract_true_false_edges_from_block (*condition_bb, &true_edge, &false_edge);
- flush_pending_stmts (false_edge);
-
- /* Adjust irreducible flag. */
- if (irred_flag)
+/* Unroll LOOP FACTOR times. DESC describes number of iterations of LOOP.
+ EXIT is the exit of the loop to that DESC corresponds.
+
+ If N is number of iterations of the loop and MAY_BE_ZERO is the condition
+ under that loop exits in the first iteration even if N != 0,
+
+ while (1)
+ {
+ x = phi (init, next);
+
+ pre;
+ if (st)
+ break;
+ post;
+ }
+
+ becomes (with possibly the exit conditions formulated a bit differently,
+ avoiding the need to create a new iv):
+
+ if (MAY_BE_ZERO || N < FACTOR)
+ goto rest;
+
+ do
+ {
+ x = phi (init, next);
+
+ pre;
+ post;
+ pre;
+ post;
+ ...
+ pre;
+ post;
+ N -= FACTOR;
+
+ } while (N >= FACTOR);
+
+ rest:
+ init' = phi (init, x);
+
+ while (1)
+ {
+ x = phi (init', next);
+
+ pre;
+ if (st)
+ break;
+ post;
+ } */
+
+void
+tree_unroll_loop (struct loop *loop, unsigned factor,
+ edge exit, struct tree_niter_desc *desc)
+{
+ tree dont_exit, 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 nonexit, new_nonexit;
+ block_stmt_iterator bsi;
+ use_operand_p op;
+ bool ok;
+ unsigned est_niter;
+ unsigned irr = loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP;
+ sbitmap wont_exit;
+
+ est_niter = expected_loop_iterations (loop);
+ determine_exit_conditions (loop, desc, factor,
+ &enter_main_cond, &exit_base, &exit_step,
+ &exit_cmp, &exit_bound);
+
+ new_loop = loop_version (loop, enter_main_cond, NULL, true);
+ gcc_assert (new_loop != NULL);
+ update_ssa (TODO_update_ssa);
+
+ /* Unroll the loop and remove the old exits. */
+ dont_exit = ((exit->flags & EDGE_TRUE_VALUE)
+ ? boolean_false_node
+ : boolean_true_node);
+ if (exit == EDGE_SUCC (exit->src, 0))
+ nonexit = EDGE_SUCC (exit->src, 1);
+ else
+ nonexit = EDGE_SUCC (exit->src, 0);
+ nonexit->probability = REG_BR_PROB_BASE;
+ exit->probability = 0;
+ nonexit->count += exit->count;
+ exit->count = 0;
+ exit_if = last_stmt (exit->src);
+ COND_EXPR_COND (exit_if) = dont_exit;
+ update_stmt (exit_if);
+
+ wont_exit = sbitmap_alloc (factor);
+ sbitmap_ones (wont_exit);
+ ok = tree_duplicate_loop_to_header_edge
+ (loop, loop_latch_edge (loop), factor - 1,
+ wont_exit, NULL, NULL, NULL, DLTHE_FLAG_UPDATE_FREQ);
+ free (wont_exit);
+ gcc_assert (ok);
+ update_ssa (TODO_update_ssa);
+
+ /* Prepare the cfg and update the phi nodes. */
+ 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);
+
+ new_exit = make_edge (exit_bb, rest, EDGE_FALSE_VALUE | irr);
+ new_exit->count = loop_preheader_edge (loop)->count;
+ est_niter = est_niter / factor + 1;
+ new_exit->probability = REG_BR_PROB_BASE / est_niter;
+
+ new_nonexit = single_pred_edge (loop->latch);
+ new_nonexit->flags = EDGE_TRUE_VALUE;
+ new_nonexit->probability = REG_BR_PROB_BASE - new_exit->probability;
+
+ old_entry = loop_preheader_edge (loop);
+ new_entry = loop_preheader_edge (new_loop);
+ old_latch = loop_latch_edge (loop);
+ for (phi_old_loop = phi_nodes (loop->header),
+ phi_new_loop = phi_nodes (new_loop->header);
+ phi_old_loop;
+ phi_old_loop = PHI_CHAIN (phi_old_loop),
+ phi_new_loop = PHI_CHAIN (phi_new_loop))
{
- (*condition_bb)->flags |= BB_IRREDUCIBLE_LOOP;
- loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP;
- loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP;
- EDGE_PRED ((*condition_bb), 0)->flags |= EDGE_IRREDUCIBLE_LOOP;
+ init = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_entry);
+ op = PHI_ARG_DEF_PTR_FROM_EDGE (phi_new_loop, new_entry);
+ gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op)));
+ next = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_latch);
+
+ /* Prefer using original variable as a base for the new ssa name.
+ This is necessary for virtual ops, and useful in order to avoid
+ losing debug info for real ops. */
+ if (TREE_CODE (next) == SSA_NAME)
+ var = SSA_NAME_VAR (next);
+ else if (TREE_CODE (init) == SSA_NAME)
+ var = SSA_NAME_VAR (init);
+ else
+ {
+ var = create_tmp_var (TREE_TYPE (init), "unrinittmp");
+ add_referenced_var (var);
+ }
+
+ new_init = make_ssa_name (var, NULL_TREE);
+ phi_rest = create_phi_node (new_init, rest);
+ SSA_NAME_DEF_STMT (new_init) = phi_rest;
+
+ add_phi_arg (phi_rest, init, precond_edge);
+ add_phi_arg (phi_rest, next, new_exit);
+ SET_USE (op, new_init);
}
- /* At this point condition_bb is loop predheader with two successors,
- first_head and second_head. Make sure that loop predheader has only
- one successor. */
- loop_split_edge_with (loop_preheader_edge (loop), NULL);
- loop_split_edge_with (loop_preheader_edge (nloop), NULL);
+ /* Finally create the new counter for number of iterations and add the new
+ exit instruction. */
+ bsi = bsi_last (exit_bb);
+ create_iv (exit_base, exit_step, NULL_TREE, loop,
+ &bsi, true, &ctr_before, &ctr_after);
+ exit_if = build_if_stmt (build2 (exit_cmp, boolean_type_node, ctr_after,
+ exit_bound),
+ tree_block_label (loop->latch),
+ tree_block_label (rest));
+ bsi_insert_after (&bsi, exit_if, BSI_NEW_STMT);
- return nloop;
+#ifdef ENABLE_CHECKING
+ verify_flow_info ();
+ verify_dominators (CDI_DOMINATORS);
+ verify_loop_structure ();
+ verify_loop_closed_ssa ();
+#endif
}
OSDN Git Service
