/* Create the edges of the flowgraph. */
make_edges ();
+ cleanup_dead_labels ();
/* Debugging dumps. */
e->goto_locus = EXPR_LOCUS (COND_EXPR_ELSE (entry));
#endif
}
+
+ /* We do not need the gotos anymore. */
+ COND_EXPR_THEN (entry) = NULL_TREE;
+ COND_EXPR_ELSE (entry) = NULL_TREE;
}
to do early because it allows us to group case labels before creating
the edges for the CFG, and it speeds up block statement iterators in
all passes later on.
- We only run this pass once, running it more than once is probably not
- profitable. */
+ We rerun this pass after CFG is created, to get rid of the labels that
+ are no longer referenced. After then we do not run it any more, since
+ (almost) no new labels should be created. */
/* A map from basic block index to the leading label of that block. */
-static tree *label_for_bb;
+static struct label_record
+{
+ /* The label. */
+ tree label;
+
+ /* True if the label is referenced from somewhere. */
+ bool used;
+} *label_for_bb;
/* Callback for for_each_eh_region. Helper for cleanup_dead_labels. */
static void
if (! bb)
return;
- new_label = label_for_bb[bb->index];
+ new_label = label_for_bb[bb->index].label;
+ label_for_bb[bb->index].used = true;
set_eh_region_tree_label (region, new_label);
}
}
main_block_label (tree label)
{
basic_block bb = label_to_block (label);
+ tree main_label = label_for_bb[bb->index].label;
/* label_to_block possibly inserted undefined label into the chain. */
- if (!label_for_bb[bb->index])
- label_for_bb[bb->index] = label;
- return label_for_bb[bb->index];
+ if (!main_label)
+ {
+ label_for_bb[bb->index].label = label;
+ main_label = label;
+ }
+
+ label_for_bb[bb->index].used = true;
+ return main_label;
}
/* Cleanup redundant labels. This is a three-step process:
cleanup_dead_labels (void)
{
basic_block bb;
- label_for_bb = XCNEWVEC (tree, last_basic_block);
+ label_for_bb = XCNEWVEC (struct label_record, last_basic_block);
/* Find a suitable label for each block. We use the first user-defined
label if there is one, or otherwise just the first label we see. */
/* If we have not yet seen a label for the current block,
remember this one and see if there are more labels. */
- if (! label_for_bb[bb->index])
+ if (!label_for_bb[bb->index].label)
{
- label_for_bb[bb->index] = label;
+ label_for_bb[bb->index].label = label;
continue;
}
/* If we did see a label for the current block already, but it
is an artificially created label, replace it if the current
label is a user defined label. */
- if (! DECL_ARTIFICIAL (label)
- && DECL_ARTIFICIAL (label_for_bb[bb->index]))
+ if (!DECL_ARTIFICIAL (label)
+ && DECL_ARTIFICIAL (label_for_bb[bb->index].label))
{
- label_for_bb[bb->index] = label;
+ label_for_bb[bb->index].label = label;
break;
}
}
true_branch = COND_EXPR_THEN (stmt);
false_branch = COND_EXPR_ELSE (stmt);
- GOTO_DESTINATION (true_branch)
- = main_block_label (GOTO_DESTINATION (true_branch));
- GOTO_DESTINATION (false_branch)
- = main_block_label (GOTO_DESTINATION (false_branch));
+ if (true_branch)
+ GOTO_DESTINATION (true_branch)
+ = main_block_label (GOTO_DESTINATION (true_branch));
+ if (false_branch)
+ GOTO_DESTINATION (false_branch)
+ = main_block_label (GOTO_DESTINATION (false_branch));
break;
}
FOR_EACH_BB (bb)
{
block_stmt_iterator i;
- tree label_for_this_bb = label_for_bb[bb->index];
+ tree label_for_this_bb = label_for_bb[bb->index].label;
- if (! label_for_this_bb)
+ if (!label_for_this_bb)
continue;
+ /* If the main label of the block is unused, we may still remove it. */
+ if (!label_for_bb[bb->index].used)
+ label_for_this_bb = NULL;
+
for (i = bsi_start (bb); !bsi_end_p (i); )
{
tree label, stmt = bsi_stmt (i);
tree rhs;
fold_stmt_inplace (stmt);
+ if (cfgcleanup_altered_bbs)
+ bitmap_set_bit (cfgcleanup_altered_bbs, bb_for_stmt (stmt)->index);
/* FIXME. This should go in pop_stmt_changes. */
rhs = get_rhs (stmt);
last = tsi_last (bb_stmt_list (a));
tsi_link_after (&last, bb_stmt_list (b), TSI_NEW_STMT);
set_bb_stmt_list (b, NULL_TREE);
+
+ if (cfgcleanup_altered_bbs)
+ bitmap_set_bit (cfgcleanup_altered_bbs, a->index);
}
return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
}
-
-/* Add gotos that used to be represented implicitly in the CFG. */
-
-void
-disband_implicit_edges (void)
-{
- basic_block bb;
- block_stmt_iterator last;
- edge e;
- edge_iterator ei;
- tree stmt, label;
-
- FOR_EACH_BB (bb)
- {
- last = bsi_last (bb);
- stmt = last_stmt (bb);
-
- if (stmt && TREE_CODE (stmt) == COND_EXPR)
- {
- /* Remove superfluous gotos from COND_EXPR branches. Moved
- from cfg_remove_useless_stmts here since it violates the
- invariants for tree--cfg correspondence and thus fits better
- here where we do it anyway. */
- e = find_edge (bb, bb->next_bb);
- if (e)
- {
- if (e->flags & EDGE_TRUE_VALUE)
- COND_EXPR_THEN (stmt) = build_empty_stmt ();
- else if (e->flags & EDGE_FALSE_VALUE)
- COND_EXPR_ELSE (stmt) = build_empty_stmt ();
- else
- gcc_unreachable ();
- e->flags |= EDGE_FALLTHRU;
- }
-
- continue;
- }
-
- if (stmt && TREE_CODE (stmt) == RETURN_EXPR)
- {
- /* Remove the RETURN_EXPR if we may fall though to the exit
- instead. */
- gcc_assert (single_succ_p (bb));
- gcc_assert (single_succ (bb) == EXIT_BLOCK_PTR);
-
- if (bb->next_bb == EXIT_BLOCK_PTR
- && !TREE_OPERAND (stmt, 0))
- {
- bsi_remove (&last, true);
- single_succ_edge (bb)->flags |= EDGE_FALLTHRU;
- }
- continue;
- }
-
- /* There can be no fallthru edge if the last statement is a control
- one. */
- if (stmt && is_ctrl_stmt (stmt))
- continue;
-
- /* Find a fallthru edge and emit the goto if necessary. */
- FOR_EACH_EDGE (e, ei, bb->succs)
- if (e->flags & EDGE_FALLTHRU)
- break;
-
- if (!e || e->dest == bb->next_bb)
- continue;
-
- gcc_assert (e->dest != EXIT_BLOCK_PTR);
- label = tree_block_label (e->dest);
-
- stmt = build1 (GOTO_EXPR, void_type_node, label);
-#ifdef USE_MAPPED_LOCATION
- SET_EXPR_LOCATION (stmt, e->goto_locus);
-#else
- SET_EXPR_LOCUS (stmt, e->goto_locus);
-#endif
- bsi_insert_after (&last, stmt, BSI_NEW_STMT);
- e->flags &= ~EDGE_FALLTHRU;
- }
-}
-
/* Remove block annotations and other datastructures. */
void
return new_bb;
}
-
-/* Return true when BB has label LABEL in it. */
-
-static bool
-has_label_p (basic_block bb, tree label)
-{
- block_stmt_iterator bsi;
-
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- {
- tree stmt = bsi_stmt (bsi);
-
- if (TREE_CODE (stmt) != LABEL_EXPR)
- return false;
- if (LABEL_EXPR_LABEL (stmt) == label)
- return true;
- }
- return false;
-}
-
-
/* Callback for walk_tree, check that all elements with address taken are
properly noticed as such. The DATA is an int* that is 1 if TP was seen
inside a PHI node. */
{
edge true_edge;
edge false_edge;
- if (TREE_CODE (COND_EXPR_THEN (stmt)) != GOTO_EXPR
- || TREE_CODE (COND_EXPR_ELSE (stmt)) != GOTO_EXPR)
+
+ if (COND_EXPR_THEN (stmt) != NULL_TREE
+ || COND_EXPR_ELSE (stmt) != NULL_TREE)
{
- error ("structured COND_EXPR at the end of bb %d", bb->index);
+ error ("COND_EXPR with code in branches at the end of bb %d",
+ bb->index);
err = 1;
}
bb->index);
err = 1;
}
-
- if (!has_label_p (true_edge->dest,
- GOTO_DESTINATION (COND_EXPR_THEN (stmt))))
- {
- error ("%<then%> label does not match edge at end of bb %d",
- bb->index);
- err = 1;
- }
-
- if (!has_label_p (false_edge->dest,
- GOTO_DESTINATION (COND_EXPR_ELSE (stmt))))
- {
- error ("%<else%> label does not match edge at end of bb %d",
- bb->index);
- err = 1;
- }
}
break;
}
}
- if (dom_computed[CDI_DOMINATORS] >= DOM_NO_FAST_QUERY)
+ if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
verify_dominators (CDI_DOMINATORS);
return err;
switch (stmt ? TREE_CODE (stmt) : ERROR_MARK)
{
case COND_EXPR:
- stmt = (e->flags & EDGE_TRUE_VALUE
- ? COND_EXPR_THEN (stmt)
- : COND_EXPR_ELSE (stmt));
- GOTO_DESTINATION (stmt) = label;
+ /* For COND_EXPR, we only need to redirect the edge. */
break;
case GOTO_EXPR:
if (loop->header == entry->dest)
{
copying_header = true;
- loop->copy = loop->outer;
+ loop->copy = loop_outer (loop);
if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
return false;
struct move_stmt_d d;
unsigned old_len, new_len;
+ /* Remove BB from dominance structures. */
+ delete_from_dominance_info (CDI_DOMINATORS, bb);
+
/* Link BB to the new linked list. */
move_block_after (bb, after);
/* Grow DEST_CFUN's basic block array if needed. */
cfg = dest_cfun->cfg;
cfg->x_n_basic_blocks++;
- if (bb->index > cfg->x_last_basic_block)
- cfg->x_last_basic_block = bb->index;
+ if (bb->index >= cfg->x_last_basic_block)
+ cfg->x_last_basic_block = bb->index + 1;
old_len = VEC_length (basic_block, cfg->x_basic_block_info);
if ((unsigned) cfg->x_last_basic_block >= old_len)
}
VEC_replace (basic_block, cfg->x_basic_block_info,
- cfg->x_last_basic_block, bb);
+ bb->index, bb);
/* The statements in BB need to be associated with a new TREE_BLOCK.
Labels need to be associated with a new label-to-block map. */
return changed;
}
+/* Stores all basic blocks dominated by BB to DOM_BBS. */
+
+static void
+get_all_dominated_blocks (basic_block bb, VEC (basic_block, heap) **dom_bbs)
+{
+ basic_block son;
+
+ VEC_safe_push (basic_block, heap, *dom_bbs, bb);
+ for (son = first_dom_son (CDI_DOMINATORS, bb);
+ son;
+ son = next_dom_son (CDI_DOMINATORS, son))
+ get_all_dominated_blocks (son, dom_bbs);
+}
+
+/* Removes edge E and all the blocks dominated by it, and updates dominance
+ information. The IL in E->src needs to be updated separately.
+ If dominance info is not available, only the edge E is removed.*/
+
+void
+remove_edge_and_dominated_blocks (edge e)
+{
+ VEC (basic_block, heap) *bbs_to_remove = NULL;
+ VEC (basic_block, heap) *bbs_to_fix_dom = NULL;
+ bitmap df, df_idom;
+ edge f;
+ edge_iterator ei;
+ bool none_removed = false;
+ unsigned i;
+ basic_block bb, dbb;
+ bitmap_iterator bi;
+
+ if (!dom_info_available_p (CDI_DOMINATORS))
+ {
+ remove_edge (e);
+ return;
+ }
+
+ /* No updating is needed for edges to exit. */
+ if (e->dest == EXIT_BLOCK_PTR)
+ {
+ if (cfgcleanup_altered_bbs)
+ bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
+ remove_edge (e);
+ return;
+ }
+
+ /* First, we find the basic blocks to remove. If E->dest has a predecessor
+ that is not dominated by E->dest, then this set is empty. Otherwise,
+ all the basic blocks dominated by E->dest are removed.
+
+ Also, to DF_IDOM we store the immediate dominators of the blocks in
+ the dominance frontier of E (i.e., of the successors of the
+ removed blocks, if there are any, and of E->dest otherwise). */
+ FOR_EACH_EDGE (f, ei, e->dest->preds)
+ {
+ if (f == e)
+ continue;
+
+ if (!dominated_by_p (CDI_DOMINATORS, f->src, e->dest))
+ {
+ none_removed = true;
+ break;
+ }
+ }
+
+ df = BITMAP_ALLOC (NULL);
+ df_idom = BITMAP_ALLOC (NULL);
+
+ if (none_removed)
+ bitmap_set_bit (df_idom,
+ get_immediate_dominator (CDI_DOMINATORS, e->dest)->index);
+ else
+ {
+ get_all_dominated_blocks (e->dest, &bbs_to_remove);
+ for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
+ {
+ FOR_EACH_EDGE (f, ei, bb->succs)
+ {
+ if (f->dest != EXIT_BLOCK_PTR)
+ bitmap_set_bit (df, f->dest->index);
+ }
+ }
+ for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
+ bitmap_clear_bit (df, bb->index);
+
+ EXECUTE_IF_SET_IN_BITMAP (df, 0, i, bi)
+ {
+ bb = BASIC_BLOCK (i);
+ bitmap_set_bit (df_idom,
+ get_immediate_dominator (CDI_DOMINATORS, bb)->index);
+ }
+ }
+
+ if (cfgcleanup_altered_bbs)
+ {
+ /* Record the set of the altered basic blocks. */
+ bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
+ bitmap_ior_into (cfgcleanup_altered_bbs, df);
+ }
+
+ /* Remove E and the cancelled blocks. */
+ if (none_removed)
+ remove_edge (e);
+ else
+ {
+ for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
+ delete_basic_block (bb);
+ }
+
+ /* Update the dominance information. The immediate dominator may change only
+ for blocks whose immediate dominator belongs to DF_IDOM:
+
+ Suppose that idom(X) = Y before removal of E and idom(X) != Y after the
+ removal. Let Z the arbitrary block such that idom(Z) = Y and
+ Z dominates X after the removal. Before removal, there exists a path P
+ from Y to X that avoids Z. Let F be the last edge on P that is
+ removed, and let W = F->dest. Before removal, idom(W) = Y (since Y
+ dominates W, and because of P, Z does not dominate W), and W belongs to
+ the dominance frontier of E. Therefore, Y belongs to DF_IDOM. */
+ EXECUTE_IF_SET_IN_BITMAP (df_idom, 0, i, bi)
+ {
+ bb = BASIC_BLOCK (i);
+ for (dbb = first_dom_son (CDI_DOMINATORS, bb);
+ dbb;
+ dbb = next_dom_son (CDI_DOMINATORS, dbb))
+ VEC_safe_push (basic_block, heap, bbs_to_fix_dom, dbb);
+ }
+
+ iterate_fix_dominators (CDI_DOMINATORS,
+ VEC_address (basic_block, bbs_to_fix_dom),
+ VEC_length (basic_block, bbs_to_fix_dom));
+
+ BITMAP_FREE (df);
+ BITMAP_FREE (df_idom);
+ VEC_free (basic_block, heap, bbs_to_remove);
+ VEC_free (basic_block, heap, bbs_to_fix_dom);
+}
+
/* Purge dead EH edges from basic block BB. */
bool
{
if (e->flags & EDGE_EH)
{
- remove_edge (e);
+ remove_edge_and_dominated_blocks (e);
changed = true;
}
else
ei_next (&ei);
}
- /* Removal of dead EH edges might change dominators of not
- just immediate successors. E.g. when bb1 is changed so that
- it no longer can throw and bb1->bb3 and bb1->bb4 are dead
- eh edges purged by this function in:
- 0
- / \
- v v
- 1-->2
- / \ |
- v v |
- 3-->4 |
- \ v
- --->5
- |
- -
- idom(bb5) must be recomputed. For now just free the dominance
- info. */
- if (changed)
- free_dominance_info (CDI_DOMINATORS);
-
return changed;
}
SECOND_HEAD is the destination of the THEN and FIRST_HEAD is
the destination of the ELSE part. */
static void
-tree_lv_add_condition_to_bb (basic_block first_head, basic_block second_head,
- basic_block cond_bb, void *cond_e)
+tree_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED,
+ basic_block second_head ATTRIBUTE_UNUSED,
+ basic_block cond_bb, void *cond_e)
{
block_stmt_iterator bsi;
- tree goto1 = NULL_TREE;
- tree goto2 = NULL_TREE;
tree new_cond_expr = NULL_TREE;
tree cond_expr = (tree) cond_e;
edge e0;
/* 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);
+ new_cond_expr = build3 (COND_EXPR, void_type_node, cond_expr,
+ NULL_TREE, NULL_TREE);
/* Add new cond in cond_bb. */
bsi = bsi_start (cond_bb);
OSDN Git Service
