block_stmt_iterator *incr_pos, bool after,
tree *var_before, tree *var_after)
{
- tree stmt, initial, step1;
+ tree stmt, initial, step1, stmts;
tree vb, va;
enum tree_code incr_op = PLUS_EXPR;
else
bsi_insert_before (incr_pos, stmt, BSI_NEW_STMT);
- initial = base;
+ 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;
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)
+ FOR_EACH_EDGE (e, ei, exit->preds)
add_phi_arg (&phi, use, e);
SSA_NAME_DEF_STMT (use) = def_stmt;
bitmap def;
int index;
basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
+ bitmap_iterator bi;
bitmap_clear_bit (livein, def_bb->index);
compute_global_livein (livein, def);
BITMAP_XFREE (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. */
bitmap exits = BITMAP_XMALLOC ();
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))
{
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);
-
- vuses = VUSE_OPS (ann);
- for (i = 0; i < NUM_VUSES (vuses); i++)
- find_uses_to_rename_use (bb, VUSE_OP (vuses, i),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);
+ 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);
}
/* Marks names that are used outside of the loop they are defined in
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));
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. */
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 = TREE_CHAIN (phi))
+ {
+ op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, EDGE_SUCC (bb, 0));
+
+ 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 (EDGE_COUNT (loop->latch->preds) > 1)
+ return NULL;
+
+ bb = EDGE_PRED (loop->latch, 0)->src;
+ 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 = TREE_CHAIN (phi))
+ SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = phi;
+}
+
+/* The same ad 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_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.
+*/
+
+static void
+lv_adjust_loop_header_phi (basic_block first, basic_block second,
+ basic_block new_head, edge e)
+{
+ tree phi1, phi2;
+
+ /* Browse all 'second' basic block phi nodes and add phi args to
+ edge 'e' for 'first' head. PHI args are always in correct order. */
+
+ for (phi2 = phi_nodes (second), phi1 = phi_nodes (first);
+ phi2 && phi1;
+ phi2 = TREE_CHAIN (phi2), phi1 = TREE_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);
+ }
+ }
+ }
+}
+
+/* Adjust entry edge for lv.
+
+ e is a incoming edge.
+
+ --- edge e ---- > [second_head]
+
+ Split it and insert new conditional expression and adjust edges.
+
+ --- edge e ---> [cond expr] ---> [first_head]
+ |
+ +---------> [second_head]
+
+*/
+
+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;
+}
+
+/* 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;
+
+ /* CHECKME: Loop versioning does not handle nested loop at this point. */
+ if (loop->inner)
+ return NULL;
+
+ /* Record entry and latch edges for the loop */
+ entry = loop_preheader_edge (loop);
+
+ /* Note down head of loop as first_head. */
+ first_head = entry->dest;
+
+ /* 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))
+ {
+ entry->flags |= irred_flag;
+ return NULL;
+ }
+
+ /* After duplication entry edge now points to new loop head block.
+ Note down new head as second_head. */
+ second_head = entry->dest;
+
+ /* 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);
+
+ 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)
+ {
+ (*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;
+ }
+
+ /* 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);
+
+ return nloop;
+}
OSDN Git Service
