/* 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.
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)
{
}
}
+ /* 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_loop (pe, stmts);
+
stmt = build2 (MODIFY_EXPR, void_type_node, va,
build2 (incr_op, TREE_TYPE (base),
vb, step));
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_loop (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. */
basic_block def_bb = bb_for_stmt (def_stmt);
struct loop *def_loop;
edge e;
+ edge_iterator ei;
/* Check that some of the edges entering the EXIT block exits a loop in
that USE is defined. */
- for (e = exit->pred; e; e = e->pred_next)
+ FOR_EACH_EDGE (e, ei, exit->preds)
{
def_loop = find_common_loop (def_bb->loop_father, e->src->loop_father);
if (!flow_bb_inside_loop_p (def_loop, e->dest))
return;
phi = create_phi_node (use, exit);
-
- for (e = exit->pred; e; e = e->pred_next)
- add_phi_arg (&phi, use, e);
-
- SSA_NAME_DEF_STMT (use) = def_stmt;
+ 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);
}
/* Add exit phis for VAR that is used in LIVEIN.
add_exit_phis_var (tree var, bitmap livein, bitmap exits)
{
bitmap def;
- int index;
+ unsigned index;
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,
- add_exit_phis_edge (BASIC_BLOCK (index), var));
+ EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index, bi)
+ {
+ add_exit_phis_edge (BASIC_BLOCK (index), var);
+ }
}
/* Add exit phis for the names marked in NAMES_TO_RENAME.
add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits)
{
unsigned i;
+ bitmap_iterator bi;
- EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i,
+ EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
{
add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits);
- });
+ }
}
/* Returns a bitmap of all loop exit edge targets. */
static bitmap
get_loops_exits (void)
{
- bitmap exits = BITMAP_XMALLOC ();
+ bitmap exits = BITMAP_ALLOC (NULL);
basic_block bb;
edge e;
+ edge_iterator ei;
FOR_EACH_BB (bb)
{
- for (e = bb->pred; e; e = e->pred_next)
+ FOR_EACH_EDGE (e, ei, bb->preds)
if (e->src != ENTRY_BLOCK_PTR
&& !flow_bb_inside_loop_p (e->src->loop_father, bb))
{
/* 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)
- find_uses_to_rename_use (bb, var, use_blocks);
+ 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, 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 = TREE_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 = xcalloc (old_num_ssa_names, sizeof (bitmap));
/* 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)
+ FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
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)
{
- for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src,
PHI_ARG_DEF (phi, i));
tree phi, new_phi, new_name, name;
use_operand_p op_p;
- for (phi = phi_nodes (dest); phi; phi = TREE_CHAIN (phi))
+ for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
{
- op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, bb->succ);
+ op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, single_succ_edge (bb));
name = USE_FROM_PTR (op_p);
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);
}
}
basic_block bb;
edge exit;
- if (loop->latch->pred->pred_next)
+ if (!single_pred_p (loop->latch))
return NULL;
- bb = loop->latch->pred->src;
+ bb = single_pred (loop->latch);
last = last_stmt (bb);
if (TREE_CODE (last) != COND_EXPR)
return NULL;
- exit = bb->succ;
+ exit = EDGE_SUCC (bb, 0);
if (exit->dest == loop->latch)
- exit = exit->succ_next;
+ exit = EDGE_SUCC (bb, 1);
if (flow_bb_inside_loop_p (loop, exit->dest))
return NULL;
*insert_after = false;
}
}
+
+/* Copies phi node arguments for duplicated blocks. The index of the first
+ duplicated block is FIRST_NEW_BLOCK. */
+
+static void
+copy_phi_node_args (unsigned first_new_block)
+{
+ unsigned i;
+
+ for (i = first_new_block; i < (unsigned) last_basic_block; i++)
+ BASIC_BLOCK (i)->rbi->duplicated = 1;
+
+ 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;
+}
+
+
+/* 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.
+
+ 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;
+
+ if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES))
+ return false;
+ if (!(loops->state & LOOPS_HAVE_PREHEADERS))
+ return false;
+
+#ifdef ENABLE_CHECKING
+ verify_loop_closed_ssa ();
+#endif
+
+ first_new_block = last_basic_block;
+ if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit,
+ orig, to_remove, n_to_remove, flags))
+ return false;
+
+ /* Readd the removed phi args for e. */
+ flush_pending_stmts (e);
+
+ /* Copy the phi node arguments. */
+ copy_phi_node_args (first_new_block);
+
+ scev_reset ();
+
+ return true;
+}
projects / thirdparty / gcc.git / blobdiff