static void tree_merge_blocks (basic_block, basic_block);
static bool tree_can_merge_blocks_p (basic_block, basic_block);
static void remove_bb (basic_block);
-static void group_case_labels (void);
-static void cleanup_dead_labels (void);
static bool cleanup_control_flow (void);
static bool cleanup_control_expr_graph (basic_block, block_stmt_iterator);
static edge find_taken_edge_cond_expr (basic_block, tree);
/* Initialize the basic block array. */
init_flow ();
+ profile_status = PROFILE_ABSENT;
n_basic_blocks = 0;
last_basic_block = 0;
VARRAY_BB_INIT (basic_block_info, initial_cfg_capacity, "basic_block_info");
PROP_cfg, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_verify_stmts /* todo_flags_finish */
+ TODO_verify_stmts, /* todo_flags_finish */
+ 0 /* letter */
};
/* Search the CFG for any computed gotos. If found, factor them to a
/* We do not care about fake edges, so remove any that the CFG
builder inserted for completeness. */
- remove_fake_edges ();
+ remove_fake_exit_edges ();
/* Clean up the graph and warn for unreachable code. */
cleanup_tree_cfg ();
make_ctrl_stmt_edges (basic_block bb)
{
tree last = last_stmt (bb);
- tree first = first_stmt (bb);
#if defined ENABLE_CHECKING
if (last == NULL_TREE)
abort();
#endif
- if (TREE_CODE (first) == LABEL_EXPR
- && DECL_NONLOCAL (LABEL_EXPR_LABEL (first)))
- make_edge (ENTRY_BLOCK_PTR, bb, EDGE_ABNORMAL);
-
switch (TREE_CODE (last))
{
case GOTO_EXPR:
/* Remove unreachable blocks and other miscellaneous clean up work. */
-void
+bool
cleanup_tree_cfg (void)
{
bool something_changed = true;
+ bool retval = false;
timevar_push (TV_TREE_CLEANUP_CFG);
while (something_changed)
{
something_changed = cleanup_control_flow ();
- something_changed |= thread_jumps ();
something_changed |= delete_unreachable_blocks ();
+ something_changed |= thread_jumps ();
+ retval |= something_changed;
}
/* Merging the blocks creates no new opportunities for the other
verify_flow_info ();
#endif
timevar_pop (TV_TREE_CLEANUP_CFG);
+ return retval;
}
tree old_label = get_eh_region_tree_label (region);
if (old_label)
{
- tree new_label = label_for_bb[label_to_block (old_label)->index];
+ tree new_label;
+ basic_block bb = label_to_block (old_label);
+
+ /* ??? After optimizing, there may be EH regions with labels
+ that have already been removed from the function body, so
+ there is no basic block for them. */
+ if (! bb)
+ return;
+
+ new_label = label_for_bb[bb->index];
set_eh_region_tree_label (region, new_label);
}
}
2) Redirect all references to labels to the leading labels.
3) Cleanup all useless labels. */
-static void
+void
cleanup_dead_labels (void)
{
basic_block bb;
same label.
Eg. three separate entries 1: 2: 3: become one entry 1..3: */
-static void
+void
group_case_labels (void)
{
basic_block bb;
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func /* todo_flags_finish */
+ TODO_dump_func, /* todo_flags_finish */
+ 0 /* letter */
};
continue;
}
- /* Invalidate the var if we encounter something that could modify it. */
+ /* Invalidate the var if we encounter something that could modify it.
+ Likewise for the value it was previously set to. Note that we only
+ consider values that are either a VAR_DECL or PARM_DECL so we
+ can test for conflict very simply. */
if (TREE_CODE (stmt) == ASM_EXPR
- || TREE_CODE (stmt) == VA_ARG_EXPR
|| (TREE_CODE (stmt) == MODIFY_EXPR
&& (TREE_OPERAND (stmt, 0) == var
- || TREE_OPERAND (stmt, 0) == val
- || TREE_CODE (TREE_OPERAND (stmt, 1)) == VA_ARG_EXPR)))
+ || TREE_OPERAND (stmt, 0) == val)))
return;
bsi_next (&bsi);
/* Given a control block BB and a predicate VAL, return the edge that
will be taken out of the block. If VAL does not match a unique
- edge, NULL is returned. */
+ edge, NULL is returned. */
edge
find_taken_edge (basic_block bb, tree val)
}
-/* Computing the Dominance Frontier:
-
- As described in Morgan, section 3.5, this may be done simply by
- walking the dominator tree bottom-up, computing the frontier for
- the children before the parent. When considering a block B,
- there are two cases:
-
- (1) A flow graph edge leaving B that does not lead to a child
- of B in the dominator tree must be a block that is either equal
- to B or not dominated by B. Such blocks belong in the frontier
- of B.
-
- (2) Consider a block X in the frontier of one of the children C
- of B. If X is not equal to B and is not dominated by B, it
- is in the frontier of B. */
-
-static void
-compute_dominance_frontiers_1 (bitmap *frontiers, basic_block bb, sbitmap done)
-{
- edge e;
- basic_block c;
-
- SET_BIT (done, bb->index);
-
- /* Do the frontier of the children first. Not all children in the
- dominator tree (blocks dominated by this one) are children in the
- CFG, so check all blocks. */
- for (c = first_dom_son (CDI_DOMINATORS, bb);
- c;
- c = next_dom_son (CDI_DOMINATORS, c))
- {
- if (! TEST_BIT (done, c->index))
- compute_dominance_frontiers_1 (frontiers, c, done);
- }
-
- /* Find blocks conforming to rule (1) above. */
- for (e = bb->succ; e; e = e->succ_next)
- {
- if (e->dest == EXIT_BLOCK_PTR)
- continue;
- if (get_immediate_dominator (CDI_DOMINATORS, e->dest) != bb)
- bitmap_set_bit (frontiers[bb->index], e->dest->index);
- }
-
- /* Find blocks conforming to rule (2). */
- for (c = first_dom_son (CDI_DOMINATORS, bb);
- c;
- c = next_dom_son (CDI_DOMINATORS, c))
- {
- int x;
-
- EXECUTE_IF_SET_IN_BITMAP (frontiers[c->index], 0, x,
- {
- if (get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (x)) != bb)
- bitmap_set_bit (frontiers[bb->index], x);
- });
- }
-}
-
-
-void
-compute_dominance_frontiers (bitmap *frontiers)
-{
- sbitmap done = sbitmap_alloc (last_basic_block);
-
- timevar_push (TV_DOM_FRONTIERS);
-
- sbitmap_zero (done);
-
- compute_dominance_frontiers_1 (frontiers, ENTRY_BLOCK_PTR->succ->dest, done);
-
- sbitmap_free (done);
-
- timevar_pop (TV_DOM_FRONTIERS);
-}
-
-
-
/*---------------------------------------------------------------------------
Debugging functions
---------------------------------------------------------------------------*/
bool
simple_goto_p (tree expr)
{
- return (TREE_CODE (expr) == GOTO_EXPR
- && TREE_CODE (GOTO_DESTINATION (expr)) == LABEL_DECL
- && (decl_function_context (GOTO_DESTINATION (expr))
- == current_function_decl));
+ return (TREE_CODE (expr) == GOTO_EXPR
+ && TREE_CODE (GOTO_DESTINATION (expr)) == LABEL_DECL);
}
}
}
+/* Finds iterator for STMT. */
+
+extern block_stmt_iterator
+stmt_for_bsi (tree stmt)
+{
+ block_stmt_iterator bsi;
+
+ for (bsi = bsi_start (bb_for_stmt (stmt)); !bsi_end_p (bsi); bsi_next (&bsi))
+ if (bsi_stmt (bsi) == stmt)
+ return bsi;
+
+ abort ();
+}
/* Insert statement (or statement list) T before the statement
pointed-to by iterator I. M specifies how to update iterator I
bsi_insert_before (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
{
set_bb_for_stmt (t, i->bb);
- modify_stmt (t);
tsi_link_before (&i->tsi, t, m);
+ modify_stmt (t);
}
bsi_insert_after (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
{
set_bb_for_stmt (t, i->bb);
- modify_stmt (t);
tsi_link_after (&i->tsi, t, m);
+ modify_stmt (t);
}
{
tree t = bsi_stmt (*i);
set_bb_for_stmt (t, NULL);
- modify_stmt (t);
tsi_delink (&i->tsi);
}
In all cases, the returned *BSI points to the correct location. The
return value is true if insertion should be done after the location,
- or false if it should be done before the location. */
+ or false if it should be done before the location. If new basic block
+ has to be created, it is stored in *NEW_BB. */
static bool
-tree_find_edge_insert_loc (edge e, block_stmt_iterator *bsi)
+tree_find_edge_insert_loc (edge e, block_stmt_iterator *bsi,
+ basic_block *new_bb)
{
basic_block dest, src;
tree tmp;
/* Otherwise, create a new basic block, and split this edge. */
dest = split_edge (e);
+ if (new_bb)
+ *new_bb = dest;
e = dest->pred;
goto restart;
}
PENDING_STMT (e) = NULL_TREE;
- if (tree_find_edge_insert_loc (e, &bsi))
+ if (tree_find_edge_insert_loc (e, &bsi, NULL))
bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
else
bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
append_to_statement_list (stmt, &PENDING_STMT (e));
}
+/* Similar to bsi_insert_on_edge+bsi_commit_edge_inserts. If new block has to
+ be created, it is returned. */
+
+basic_block
+bsi_insert_on_edge_immediate (edge e, tree stmt)
+{
+ block_stmt_iterator bsi;
+ basic_block new_bb = NULL;
+
+ if (PENDING_STMT (e))
+ abort ();
+
+ if (tree_find_edge_insert_loc (e, &bsi, &new_bb))
+ bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
+ else
+ bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
+
+ return new_bb;
+}
/*---------------------------------------------------------------------------
Tree specific functions for CFG manipulation
thread_jumps (void)
{
edge e, next, last, old;
- basic_block bb, dest, tmp;
+ basic_block bb, dest, tmp, old_dest, dom;
tree phi;
int arg;
bool retval = false;
/* Perform the redirection. */
retval = true;
+ old_dest = e->dest;
e = redirect_edge_and_branch (e, dest);
- /* TODO -- updating dominators in this case is simple. */
- free_dominance_info (CDI_DOMINATORS);
-
if (!old)
{
/* Update PHI nodes. We know that the new argument should
add_phi_arg (&phi, PHI_ARG_DEF (phi, arg), e);
}
}
+
+ /* Update the dominators. */
+ if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
+ {
+ /* Remove the unreachable blocks (observe that if all blocks
+ were reachable before, only those in the path we threaded
+ over and did not have any predecessor outside of the path
+ become unreachable). */
+ for (; old_dest != dest; old_dest = tmp)
+ {
+ tmp = old_dest->succ->dest;
+
+ if (old_dest->pred)
+ break;
+
+ delete_basic_block (old_dest);
+ }
+ /* If the dominator of the destination was in the path, set its
+ dominator to the start of the redirected edge. */
+ if (get_immediate_dominator (CDI_DOMINATORS, old_dest) == NULL)
+ set_immediate_dominator (CDI_DOMINATORS, old_dest, bb);
+
+ /* Now proceed like if we forwarded just over one edge at a time.
+ Algorithm for forwarding over edge A --> B then is
+
+ if (idom (B) == A)
+ idom (B) = idom (A);
+ recount_idom (A); */
+
+ for (; old_dest != dest; old_dest = tmp)
+ {
+ tmp = old_dest->succ->dest;
+
+ if (get_immediate_dominator (CDI_DOMINATORS, tmp) == old_dest)
+ {
+ dom = get_immediate_dominator (CDI_DOMINATORS, old_dest);
+ set_immediate_dominator (CDI_DOMINATORS, tmp, dom);
+ }
+
+ dom = recount_dominator (CDI_DOMINATORS, old_dest);
+ set_immediate_dominator (CDI_DOMINATORS, old_dest, dom);
+ }
+ }
}
/* Reset the forwardable bit on our block since it's no longer in
{
basic_block new_bb;
block_stmt_iterator bsi, bsi_tgt;
+ tree phi, val;
+ ssa_op_iter op_iter;
new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
+
+ for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ {
+ mark_for_rewrite (PHI_RESULT (phi));
+ }
+
bsi_tgt = bsi_start (new_bb);
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
if (TREE_CODE (stmt) == LABEL_EXPR)
continue;
+ /* Record the definitions. */
+ get_stmt_operands (stmt);
+
+ FOR_EACH_SSA_TREE_OPERAND (val, stmt, op_iter, SSA_OP_ALL_DEFS)
+ mark_for_rewrite (val);
+
copy = unshare_expr (stmt);
/* Copy also the virtual operands. */
if (basic_block_info)
{
/* Make a CFG based dump. */
+ check_bb_profile (ENTRY_BLOCK_PTR, file);
if (!ignore_topmost_bind)
fprintf (file, "{\n");
dump_generic_bb (file, bb, 2, flags);
fprintf (file, "}\n");
+ check_bb_profile (EXIT_BLOCK_PTR, file);
}
else
{
PROP_no_crit_edges, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func, /* todo_flags_finish */
+ TODO_dump_func, /* todo_flags_finish */
+ 0 /* letter */
};
+
+\f
+/* Return EXP if it is a valid GIMPLE rvalue, else gimplify it into
+ a temporary, make sure and register it to be renamed if necessary,
+ and finally return the temporary. Put the statements to compute
+ EXP before the current statement in BSI. */
+
+tree
+gimplify_val (block_stmt_iterator *bsi, tree type, tree exp)
+{
+ tree t, new_stmt, orig_stmt;
+
+ if (is_gimple_val (exp))
+ return exp;
+
+ t = make_rename_temp (type, NULL);
+ new_stmt = build (MODIFY_EXPR, type, t, exp);
+
+ orig_stmt = bsi_stmt (*bsi);
+ SET_EXPR_LOCUS (new_stmt, EXPR_LOCUS (orig_stmt));
+ TREE_BLOCK (new_stmt) = TREE_BLOCK (orig_stmt);
+
+ bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
+
+ return t;
+}
+
+/* Build a ternary operation and gimplify it. Emit code before BSI.
+ Return the gimple_val holding the result. */
+
+tree
+gimplify_build3 (block_stmt_iterator *bsi, enum tree_code code,
+ tree type, tree a, tree b, tree c)
+{
+ tree ret;
+
+ ret = fold (build3 (code, type, a, b, c));
+ STRIP_NOPS (ret);
+
+ return gimplify_val (bsi, type, ret);
+}
+
+/* Build a binary operation and gimplify it. Emit code before BSI.
+ Return the gimple_val holding the result. */
+
+tree
+gimplify_build2 (block_stmt_iterator *bsi, enum tree_code code,
+ tree type, tree a, tree b)
+{
+ tree ret;
+
+ ret = fold (build2 (code, type, a, b));
+ STRIP_NOPS (ret);
+
+ return gimplify_val (bsi, type, ret);
+}
+
+/* Build a unary operation and gimplify it. Emit code before BSI.
+ Return the gimple_val holding the result. */
+
+tree
+gimplify_build1 (block_stmt_iterator *bsi, enum tree_code code, tree type,
+ tree a)
+{
+ tree ret;
+
+ ret = fold (build1 (code, type, a));
+ STRIP_NOPS (ret);
+
+ return gimplify_val (bsi, type, ret);
+}
+
+
\f
/* Emit return warnings. */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- 0 /* todo_flags_finish */
+ 0, /* todo_flags_finish */
+ 0 /* letter */
};
#include "gt-tree-cfg.h"
OSDN Git Service
