/* 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.
#include "cfglayout.h"
#include "tree-scalar-evolution.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). 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). */
+
+void
+create_iv (tree base, tree step, tree var, struct loop *loop,
+ block_stmt_iterator *incr_pos, bool after,
+ tree *var_before, tree *var_after)
+{
+ tree stmt, initial, step1, stmts;
+ tree vb, va;
+ enum tree_code incr_op = PLUS_EXPR;
+
+ if (!var)
+ {
+ var = create_tmp_var (TREE_TYPE (base), "ivtmp");
+ add_referenced_tmp_var (var);
+ }
+
+ vb = make_ssa_name (var, NULL_TREE);
+ if (var_before)
+ *var_before = vb;
+ va = make_ssa_name (var, NULL_TREE);
+ if (var_after)
+ *var_after = va;
+
+ /* For easier readability of the created code, produce MINUS_EXPRs
+ when suitable. */
+ if (TREE_CODE (step) == INTEGER_CST)
+ {
+ if (TYPE_UNSIGNED (TREE_TYPE (step)))
+ {
+ step1 = fold (build1 (NEGATE_EXPR, TREE_TYPE (step), step));
+ if (tree_int_cst_lt (step1, step))
+ {
+ incr_op = MINUS_EXPR;
+ step = step1;
+ }
+ }
+ else
+ {
+ if (!tree_expr_nonnegative_p (step)
+ && may_negate_without_overflow_p (step))
+ {
+ incr_op = MINUS_EXPR;
+ 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));
+ SSA_NAME_DEF_STMT (va) = stmt;
+ if (after)
+ bsi_insert_after (incr_pos, stmt, BSI_NEW_STMT);
+ else
+ bsi_insert_before (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);
+ }
+
+ 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 exit phis for the USE on EXIT. */
static void
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))
phi = create_phi_node (use, exit);
- for (e = exit->pred; e; e = e->pred_next)
- add_phi_arg (&phi, use, e);
+ FOR_EACH_EDGE (e, ei, exit->preds)
+ add_phi_arg (phi, use, e);
SSA_NAME_DEF_STMT (use) = def_stmt;
}
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);
- 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))
{
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))
static void
find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks)
{
- use_optype uses;
- vuse_optype vuses;
- v_may_def_optype v_may_defs;
- stmt_ann_t ann;
- unsigned i;
+ ssa_op_iter iter;
+ tree var;
basic_block bb = bb_for_stmt (stmt);
get_stmt_operands (stmt);
- ann = stmt_ann (stmt);
- uses = USE_OPS (ann);
- for (i = 0; i < NUM_USES (uses); i++)
- find_uses_to_rename_use (bb, USE_OP (uses, i), 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);
+}
- vuses = VUSE_OPS (ann);
- for (i = 0; i < NUM_VUSES (vuses); i++)
- find_uses_to_rename_use (bb, VUSE_OP (vuses, i),use_blocks);
+/* 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. */
- v_may_defs = V_MAY_DEF_OPS (ann);
- for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
- find_uses_to_rename_use (bb, V_MAY_DEF_OP (v_may_defs, i), use_blocks);
-}
+static void
+find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks)
+{
+ 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);
+
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks);
+}
+
/* 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)
{
basic_block bb;
- block_stmt_iterator bsi;
- tree phi;
- unsigned i;
+ unsigned index;
+ bitmap_iterator bi;
- FOR_EACH_BB (bb)
+ if (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);
+ }
+ }
+ else
+ {
+ FOR_EACH_BB (bb)
+ {
+ find_uses_to_rename_bb (bb, use_blocks);
+ }
}
}
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. */
void
-rewrite_into_loop_closed_ssa (void)
+rewrite_into_loop_closed_ssa (bitmap changed_bbs)
{
bitmap loop_exits = get_loops_exits ();
bitmap *use_blocks;
unsigned i;
bitmap names_to_rename;
- if (any_marked_for_rewrite_p ())
- abort ();
+ gcc_assert (!any_marked_for_rewrite_p ());
use_blocks = xcalloc (num_ssa_names, sizeof (bitmap));
/* Find the uses outside loops. */
- find_uses_to_rename (use_blocks);
+ find_uses_to_rename (changed_bbs, use_blocks);
+
+ if (!any_marked_for_rewrite_p ())
+ {
+ free (use_blocks);
+ BITMAP_FREE (loop_exits);
+ return;
+ }
/* Add the phi nodes on exits of the loops for the names we need to
rewrite. */
add_exit_phis (names_to_rename, use_blocks, loop_exits);
for (i = 0; i < num_ssa_names; i++)
- BITMAP_XFREE (use_blocks[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 ();
def = SSA_NAME_DEF_STMT (use);
def_bb = bb_for_stmt (def);
- if (def_bb
- && !flow_bb_inside_loop_p (def_bb->loop_father, bb))
- abort ();
+ gcc_assert (!def_bb
+ || flow_bb_inside_loop_p (def_bb->loop_father, bb));
}
/* Checks invariants of loop closed ssa form in statement STMT in BB. */
static void
check_loop_closed_ssa_stmt (basic_block bb, tree stmt)
{
- use_optype uses;
- vuse_optype vuses;
- v_may_def_optype v_may_defs;
- stmt_ann_t ann;
- unsigned i;
+ ssa_op_iter iter;
+ tree var;
get_stmt_operands (stmt);
- ann = stmt_ann (stmt);
-
- uses = USE_OPS (ann);
- for (i = 0; i < NUM_USES (uses); i++)
- check_loop_closed_ssa_use (bb, USE_OP (uses, i));
- vuses = VUSE_OPS (ann);
- for (i = 0; i < NUM_VUSES (vuses); i++)
- check_loop_closed_ssa_use (bb, VUSE_OP (vuses, i));
-
- v_may_defs = V_MAY_DEF_OPS (ann);
- for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
- check_loop_closed_ssa_use (bb, V_MAY_DEF_OP (v_may_defs, i));
+ FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES)
+ check_loop_closed_ssa_use (bb, var);
}
/* Checks that invariants of the loop closed ssa form are preserved. */
tree phi;
unsigned i;
- verify_ssa ();
+ 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));
check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi));
}
}
+
+/* Split loop exit edge EXIT. The things are a bit complicated by a need to
+ preserve the loop closed ssa form. */
+
+void
+split_loop_exit_edge (edge exit)
+{
+ basic_block dest = exit->dest;
+ basic_block bb = loop_split_edge_with (exit, NULL);
+ 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, single_succ_edge (bb));
+
+ name = USE_FROM_PTR (op_p);
+
+ /* 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. */
+ 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);
+ 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
+ip_end_pos (struct loop *loop)
+{
+ return loop->latch;
+}
+
+/* Returns the basic block in that statements should be emitted for induction
+ variables incremented just before exit condition of a LOOP. */
+
+basic_block
+ip_normal_pos (struct loop *loop)
+{
+ tree last;
+ basic_block bb;
+ edge exit;
+
+ if (!single_pred_p (loop->latch))
+ return NULL;
+
+ bb = single_pred (loop->latch);
+ last = last_stmt (bb);
+ if (TREE_CODE (last) != COND_EXPR)
+ return NULL;
+
+ exit = EDGE_SUCC (bb, 0);
+ if (exit->dest == loop->latch)
+ exit = EDGE_SUCC (bb, 1);
+
+ if (flow_bb_inside_loop_p (loop, exit->dest))
+ return NULL;
+
+ return bb;
+}
+
+/* Stores the standard position for induction variable increment in LOOP
+ (just before the exit condition if it is available and latch block is empty,
+ end of the latch block otherwise) to BSI. INSERT_AFTER is set to true if
+ the increment should be inserted after *BSI. */
+
+void
+standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi,
+ bool *insert_after)
+{
+ basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop);
+ tree last = last_stmt (latch);
+
+ if (!bb
+ || (last && TREE_CODE (last) != LABEL_EXPR))
+ {
+ *bsi = bsi_last (latch);
+ *insert_after = true;
+ }
+ else
+ {
+ *bsi = bsi_last (bb);
+ *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;
+}
+
+/* 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
+ 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. */
+
+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))
+ return false;
+ if (!(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,
+ 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);
+
+ /* Rename the variables. */
+ definitions = marked_ssa_names ();
+ rename_variables (first_new_block, definitions);
+ unmark_all_for_rewrite ();
+ BITMAP_FREE (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;
+}
+
OSDN Git Service
