/* Control flow functions for trees.
- Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
+ Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>
This file is part of GCC.
static edge tree_redirect_edge_and_branch (edge, basic_block);
static edge tree_try_redirect_by_replacing_jump (edge, basic_block);
static void split_critical_edges (void);
+static bool remove_fallthru_edge (VEC(edge) *);
/* Various helpers. */
static inline bool stmt_starts_bb_p (tree, tree);
static int tree_verify_flow_info (void);
static void tree_make_forwarder_block (edge);
-static bool thread_jumps (void);
-static bool tree_forwarder_block_p (basic_block);
+static bool tree_forwarder_block_p (basic_block, bool);
static void tree_cfg2vcg (FILE *);
/* Flowgraph optimization and cleanup. */
static edge find_taken_edge_switch_expr (basic_block, tree);
static tree find_case_label_for_value (tree, tree);
static bool phi_alternatives_equal (basic_block, edge, edge);
+static bool cleanup_forwarder_blocks (void);
/*---------------------------------------------------------------------------
statements in it. */
make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU);
- /* Traverse basic block array placing edges. */
+ /* Traverse the basic block array placing edges. */
FOR_EACH_BB (bb)
{
tree first = first_stmt (bb);
retval = cleanup_control_flow ();
retval |= delete_unreachable_blocks ();
- /* thread_jumps can redirect edges out of SWITCH_EXPRs, which can get
- expensive. So we want to enable recording of edge to CASE_LABEL_EXPR
- mappings around the call to thread_jumps. */
+ /* cleanup_forwarder_blocks can redirect edges out of SWITCH_EXPRs,
+ which can get expensive. So we want to enable recording of edge
+ to CASE_LABEL_EXPR mappings around the call to
+ cleanup_forwarder_blocks. */
start_recording_case_labels ();
- retval |= thread_jumps ();
+ retval |= cleanup_forwarder_blocks ();
end_recording_case_labels ();
#ifdef ENABLE_CHECKING
{
gcc_assert (!cleanup_control_flow ());
gcc_assert (!delete_unreachable_blocks ());
- gcc_assert (!thread_jumps ());
+ gcc_assert (!cleanup_forwarder_blocks ());
}
#endif
/* Merging the blocks creates no new opportunities for the other
optimizations, so do it here. */
- merge_seq_blocks ();
+ retval |= merge_seq_blocks ();
compact_blocks ();
if (EDGE_SUCC (a, 0)->dest != b)
return false;
- if (b == EXIT_BLOCK_PTR)
- return false;
-
if (EDGE_COUNT (b->preds) > 1)
return false;
+ if (b == EXIT_BLOCK_PTR)
+ return false;
+
/* If A ends by a statement causing exceptions or something similar, we
cannot merge the blocks. */
stmt = last_stmt (a);
if (EXPR_HAS_LOCATION (stmt))
{
location_t loc = EXPR_LOCATION (stmt);
- warning ("%Hwill never be executed", &loc);
- return true;
+ if (LOCATION_LINE (loc) > 0)
+ {
+ warning ("%Hwill never be executed", &loc);
+ return true;
+ }
}
switch (TREE_CODE (stmt))
then_clause = COND_EXPR_THEN (*stmt_p);
else_clause = COND_EXPR_ELSE (*stmt_p);
- cond = COND_EXPR_COND (*stmt_p);
+ cond = fold (COND_EXPR_COND (*stmt_p));
/* If neither arm does anything at all, we can remove the whole IF. */
if (!TREE_SIDE_EFFECTS (then_clause) && !TREE_SIDE_EFFECTS (else_clause))
&& FORCED_LABEL (LABEL_EXPR_LABEL (stmt)))
{
basic_block new_bb = bb->prev_bb;
- block_stmt_iterator new_bsi = bsi_after_labels (new_bb);
+ block_stmt_iterator new_bsi = bsi_start (new_bb);
bsi_remove (&i);
- bsi_insert_after (&new_bsi, stmt, BSI_NEW_STMT);
+ bsi_insert_before (&new_bsi, stmt, BSI_NEW_STMT);
}
else
{
since this way we lose warnings for gotos in the original
program that are indeed unreachable. */
if (TREE_CODE (stmt) != GOTO_EXPR && EXPR_HAS_LOCATION (stmt) && !loc)
+ {
+ source_locus t;
+
#ifdef USE_MAPPED_LOCATION
- loc = EXPR_LOCATION (stmt);
+ t = EXPR_LOCATION (stmt);
#else
- loc = EXPR_LOCUS (stmt);
+ t = EXPR_LOCUS (stmt);
#endif
+ if (t && LOCATION_LINE (*t) > 0)
+ loc = t;
+ }
}
/* If requested, give a warning that the first statement in the
basic_block bb;
block_stmt_iterator bsi;
bool retval = false;
- tree stmt;
+ tree stmt, call;
FOR_EACH_BB (bb)
{
if (TREE_CODE (stmt) == COND_EXPR
|| TREE_CODE (stmt) == SWITCH_EXPR)
retval |= cleanup_control_expr_graph (bb, bsi);
+
+ /* Check for indirect calls that have been turned into
+ noreturn calls. */
+ call = get_call_expr_in (stmt);
+ if (call != 0
+ && (call_expr_flags (call) & ECF_NORETURN) != 0
+ && remove_fallthru_edge (bb->succs))
+ {
+ free_dominance_info (CDI_DOMINATORS);
+ retval = true;
+ }
}
return retval;
}
return retval;
}
+/* Remove any fallthru edge from EV. Return true if an edge was removed. */
+
+static bool
+remove_fallthru_edge (VEC(edge) *ev)
+{
+ edge_iterator ei;
+ edge e;
+
+ FOR_EACH_EDGE (e, ei, ev)
+ if ((e->flags & EDGE_FALLTHRU) != 0)
+ {
+ remove_edge (e);
+ return true;
+ }
+ return false;
+}
/* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
predicate VAL, return the edge that will be taken out of the block.
static bool
phi_alternatives_equal (basic_block dest, edge e1, edge e2)
{
- tree phi, val1, val2;
- int n1, n2;
+ int n1 = e1->dest_idx;
+ int n2 = e2->dest_idx;
+ tree phi;
for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
{
- n1 = phi_arg_from_edge (phi, e1);
- n2 = phi_arg_from_edge (phi, e2);
-
- gcc_assert (n1 >= 0);
- gcc_assert (n2 >= 0);
+ tree val1 = PHI_ARG_DEF (phi, n1);
+ tree val2 = PHI_ARG_DEF (phi, n2);
- val1 = PHI_ARG_DEF (phi, n1);
- val2 = PHI_ARG_DEF (phi, n2);
+ gcc_assert (val1 != NULL_TREE);
+ gcc_assert (val2 != NULL_TREE);
- if (!operand_equal_p (val1, val2, 0))
+ if (!operand_equal_for_phi_arg_p (val1, val2))
return false;
}
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. */
+/* Similar to bsi_insert_on_edge+bsi_commit_edge_inserts. If a new
+ block has to be created, it is returned. */
basic_block
bsi_insert_on_edge_immediate (edge e, tree stmt)
gcc_assert (result == PHI_RESULT (phi));
- add_phi_arg (&phi, arg, new_edge);
+ add_phi_arg (phi, arg, new_edge);
}
PENDING_STMT (old_edge) = NULL;
{
basic_block new_bb, after_bb, dest, src;
edge new_edge, e;
- edge_iterator ei;
/* Abnormal edges cannot be split. */
gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
/* Place the new block in the block list. Try to keep the new block
near its "logical" location. This is of most help to humans looking
at debugging dumps. */
- FOR_EACH_EDGE (e, ei, dest->preds)
- if (e->src->next_bb == dest)
- break;
- if (!e)
- after_bb = dest->prev_bb;
- else
+ if (dest->prev_bb && find_edge (dest->prev_bb, dest))
after_bb = edge_in->src;
+ else
+ after_bb = dest->prev_bb;
new_bb = create_empty_bb (after_bb);
new_bb->frequency = EDGE_FREQUENCY (edge_in);
/* Callback for walk_tree, check that all elements with address taken are
- properly noticed as such. */
+ properly noticed as such. The DATA is an int* that is 1 if TP was seen
+ inside a PHI node. */
static tree
verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
{
tree t = *tp, x;
+ bool in_phi = (data != NULL);
if (TYPE_P (t))
*walk_subtrees = 0;
break;
case ADDR_EXPR:
+ /* ??? tree-ssa-alias.c may have overlooked dead PHI nodes, missing
+ dead PHIs that take the address of something. But if the PHI
+ result is dead, the fact that it takes the address of anything
+ is irrelevant. Because we can not tell from here if a PHI result
+ is dead, we just skip this check for PHIs altogether. This means
+ we may be missing "valid" checks, but what can you do?
+ This was PR19217. */
+ if (in_phi)
+ break;
+
/* Skip any references (they will be checked when we recurse down the
tree) and ensure that any variable used as a prefix is marked
addressable. */
for (x = TREE_OPERAND (t, 0);
- (handled_component_p (x)
- || TREE_CODE (x) == REALPART_EXPR
- || TREE_CODE (x) == IMAGPART_EXPR);
+ handled_component_p (x);
x = TREE_OPERAND (x, 0))
;
that determine where to reference is either a constant or a variable,
verify that the base is valid, and then show we've already checked
the subtrees. */
- while (TREE_CODE (t) == REALPART_EXPR || TREE_CODE (t) == IMAGPART_EXPR
- || handled_component_p (t))
+ while (handled_component_p (t))
{
if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
CHECK_OP (2, "Invalid COMPONENT_REF offset operator");
gimple invariants if they overflowed. */
|| CONSTANT_CLASS_P (t)
|| is_gimple_min_invariant (t)
- || TREE_CODE (t) == SSA_NAME)
+ || TREE_CODE (t) == SSA_NAME
+ || t == error_mark_node)
return true;
if (TREE_CODE (t) == CASE_LABEL_EXPR)
err |= true;
}
- addr = walk_tree (&t, verify_expr, NULL, NULL);
+ addr = walk_tree (&t, verify_expr, (void *) 1, NULL);
if (addr)
{
debug_generic_stmt (addr);
{
bool found_ctrl_stmt = false;
+ stmt = NULL_TREE;
+
/* Skip labels on the start of basic block. */
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
- if (TREE_CODE (bsi_stmt (bsi)) != LABEL_EXPR)
+ tree prev_stmt = stmt;
+
+ stmt = bsi_stmt (bsi);
+
+ if (TREE_CODE (stmt) != LABEL_EXPR)
break;
- if (label_to_block (LABEL_EXPR_LABEL (bsi_stmt (bsi))) != bb)
+ if (prev_stmt && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
+ {
+ error ("Nonlocal label %s is not first "
+ "in a sequence of labels in bb %d",
+ IDENTIFIER_POINTER (DECL_NAME (LABEL_EXPR_LABEL (stmt))),
+ bb->index);
+ err = 1;
+ }
+
+ if (label_to_block (LABEL_EXPR_LABEL (stmt)) != bb)
{
- tree stmt = bsi_stmt (bsi);
error ("Label %s to block does not match in bb %d\n",
IDENTIFIER_POINTER (DECL_NAME (LABEL_EXPR_LABEL (stmt))),
bb->index);
err = 1;
}
- if (decl_function_context (LABEL_EXPR_LABEL (bsi_stmt (bsi)))
+ if (decl_function_context (LABEL_EXPR_LABEL (stmt))
!= current_function_decl)
{
- tree stmt = bsi_stmt (bsi);
error ("Label %s has incorrect context in bb %d\n",
IDENTIFIER_POINTER (DECL_NAME (LABEL_EXPR_LABEL (stmt))),
bb->index);
if (label_bb->aux != (void *)2)
{
- error ("Missing edge %i->%i\n",
+ error ("Missing edge %i->%i",
bb->index, label_bb->index);
err = 1;
}
new_phi = create_phi_node (var, bb);
SSA_NAME_DEF_STMT (var) = new_phi;
SET_PHI_RESULT (phi, make_ssa_name (SSA_NAME_VAR (var), phi));
- add_phi_arg (&new_phi, PHI_RESULT (phi), fallthru);
+ add_phi_arg (new_phi, PHI_RESULT (phi), fallthru);
}
/* Ensure that the PHI node chain is in the same order. */
ENTRY_BLOCK_PTR. */
static bool
-tree_forwarder_block_p (basic_block bb)
+tree_forwarder_block_p (basic_block bb, bool phi_wanted)
{
block_stmt_iterator bsi;
/* BB must have a single outgoing edge. */
if (EDGE_COUNT (bb->succs) != 1
- /* BB can not have any PHI nodes. This could potentially be
- relaxed early in compilation if we re-rewrote the variables
- appearing in any PHI nodes in forwarder blocks. */
- || phi_nodes (bb)
+ /* If PHI_WANTED is false, BB must not have any PHI nodes.
+ Otherwise, BB must have PHI nodes. */
+ || (phi_nodes (bb) != NULL_TREE) != phi_wanted
/* BB may not be a predecessor of EXIT_BLOCK_PTR. */
|| EDGE_SUCC (bb, 0)->dest == EXIT_BLOCK_PTR
+ /* Nor should this be an infinite loop. */
+ || EDGE_SUCC (bb, 0)->dest == bb
/* BB may not have an abnormal outgoing edge. */
|| (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL))
return false;
gcc_assert (bb != ENTRY_BLOCK_PTR);
#endif
- if (find_edge (ENTRY_BLOCK_PTR, bb))
- return false;
-
- /* Now walk through the statements. We can ignore labels, anything else
- means this is not a forwarder block. */
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ /* Now walk through the statements backward. We can ignore labels,
+ anything else means this is not a forwarder block. */
+ for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
}
}
+ if (find_edge (ENTRY_BLOCK_PTR, bb))
+ return false;
+
return true;
}
-/* Thread jumps from BB. */
+/* Return true if BB has at least one abnormal incoming edge. */
+
+static inline bool
+has_abnormal_incoming_edge_p (basic_block bb)
+{
+ edge e;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ if (e->flags & EDGE_ABNORMAL)
+ return true;
+
+ return false;
+}
+
+/* Removes forwarder block BB. Returns false if this failed. If a new
+ forwarder block is created due to redirection of edges, it is
+ stored to worklist. */
static bool
-thread_jumps_from_bb (basic_block bb)
+remove_forwarder_block (basic_block bb, basic_block **worklist)
{
+ edge succ = EDGE_SUCC (bb, 0), e, s;
+ basic_block dest = succ->dest;
+ tree label;
+ tree phi;
edge_iterator ei;
- edge e;
- bool retval = false;
+ block_stmt_iterator bsi, bsi_to;
+ bool seen_abnormal_edge = false;
- /* Examine each of our block's successors to see if it is
- forwardable. */
- for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
+ /* We check for infinite loops already in tree_forwarder_block_p.
+ However it may happen that the infinite loop is created
+ afterwards due to removal of forwarders. */
+ if (dest == bb)
+ return false;
+
+ /* If the destination block consists of a nonlocal label, do not merge
+ it. */
+ label = first_stmt (dest);
+ if (label
+ && TREE_CODE (label) == LABEL_EXPR
+ && DECL_NONLOCAL (LABEL_EXPR_LABEL (label)))
+ return false;
+
+ /* If there is an abnormal edge to basic block BB, but not into
+ dest, problems might occur during removal of the phi node at out
+ of ssa due to overlapping live ranges of registers.
+
+ If there is an abnormal edge in DEST, the problems would occur
+ anyway since cleanup_dead_labels would then merge the labels for
+ two different eh regions, and rest of exception handling code
+ does not like it.
+
+ So if there is an abnormal edge to BB, proceed only if there is
+ no abnormal edge to DEST and there are no phi nodes in DEST. */
+ if (has_abnormal_incoming_edge_p (bb))
{
- int freq;
- gcov_type count;
- edge last, old;
- basic_block dest, tmp, curr, old_dest;
- tree phi;
- int arg;
+ seen_abnormal_edge = true;
- /* If the edge is abnormal or its destination is not
- forwardable, then there's nothing to do. */
- if ((e->flags & EDGE_ABNORMAL)
- || !bb_ann (e->dest)->forwardable)
- {
- ei_next (&ei);
- continue;
- }
+ if (has_abnormal_incoming_edge_p (dest)
+ || phi_nodes (dest) != NULL_TREE)
+ return false;
+ }
- /* Now walk through as many forwarder blocks as possible to find
- the ultimate destination we want to thread our jump to. */
- last = EDGE_SUCC (e->dest, 0);
- bb_ann (e->dest)->forwardable = 0;
- for (dest = EDGE_SUCC (e->dest, 0)->dest;
- bb_ann (dest)->forwardable;
- last = EDGE_SUCC (dest, 0),
- dest = EDGE_SUCC (dest, 0)->dest)
- bb_ann (dest)->forwardable = 0;
-
- /* Reset the forwardable marks to 1. */
- for (tmp = e->dest;
- tmp != dest;
- tmp = EDGE_SUCC (tmp, 0)->dest)
- bb_ann (tmp)->forwardable = 1;
-
- if (dest == e->dest)
+ /* If there are phi nodes in DEST, and some of the blocks that are
+ predecessors of BB are also predecessors of DEST, check that the
+ phi node arguments match. */
+ if (phi_nodes (dest))
+ {
+ FOR_EACH_EDGE (e, ei, bb->preds)
{
- ei_next (&ei);
- continue;
+ s = find_edge (e->src, dest);
+ if (!s)
+ continue;
+
+ if (!phi_alternatives_equal (dest, succ, s))
+ return false;
}
+ }
- old = find_edge (bb, dest);
- if (old)
+ /* Redirect the edges. */
+ for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
+ {
+ if (e->flags & EDGE_ABNORMAL)
{
- /* If there already is an edge, check whether the values in
- phi nodes differ. */
- if (!phi_alternatives_equal (dest, last, old))
- {
- /* The previous block is forwarder. Redirect our jump
- to that target instead since we know it has no PHI
- nodes that will need updating. */
- dest = last->src;
-
- /* That might mean that no forwarding at all is
- possible. */
- if (dest == e->dest)
- {
- ei_next (&ei);
- continue;
- }
-
- old = find_edge (bb, dest);
- }
+ /* If there is an abnormal edge, redirect it anyway, and
+ move the labels to the new block to make it legal. */
+ s = redirect_edge_succ_nodup (e, dest);
}
+ else
+ s = redirect_edge_and_branch (e, dest);
- /* Perform the redirection. */
- retval = true;
- count = e->count;
- freq = EDGE_FREQUENCY (e);
- old_dest = e->dest;
- e = redirect_edge_and_branch (e, dest);
-
- /* Update the profile. */
- if (profile_status != PROFILE_ABSENT)
- for (curr = old_dest;
- curr != dest;
- curr = EDGE_SUCC (curr, 0)->dest)
- {
- curr->frequency -= freq;
- if (curr->frequency < 0)
- curr->frequency = 0;
- curr->count -= count;
- if (curr->count < 0)
- curr->count = 0;
- EDGE_SUCC (curr, 0)->count -= count;
- if (EDGE_SUCC (curr, 0)->count < 0)
- EDGE_SUCC (curr, 0)->count = 0;
- }
-
- if (!old)
+ if (s == e)
{
- /* Update PHI nodes. We know that the new argument should
- have the same value as the argument associated with LAST.
- Otherwise we would have changed our target block
- above. */
+ /* Create arguments for the phi nodes, since the edge was not
+ here before. */
for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
- {
- arg = phi_arg_from_edge (phi, last);
- gcc_assert (arg >= 0);
- add_phi_arg (&phi, PHI_ARG_DEF (phi, arg), e);
- }
+ add_phi_arg (phi, PHI_ARG_DEF (phi, succ->dest_idx), s);
}
-
- /* 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)
+ else
{
- tmp = EDGE_SUCC (old_dest, 0)->dest;
-
- if (EDGE_COUNT (old_dest->preds) > 0)
- break;
-
- delete_basic_block (old_dest);
+ /* The source basic block might become a forwarder. We know
+ that it was not a forwarder before, since it used to have
+ at least two outgoing edges, so we may just add it to
+ worklist. */
+ if (tree_forwarder_block_p (s->src, false))
+ *(*worklist)++ = s->src;
}
+ }
- /* Update the dominators. */
- if (dom_info_available_p (CDI_DOMINATORS))
- {
- /* 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 edge S --> A over
- edge A --> B then is
-
- if (idom (B) == A
- && !dominated_by (S, B))
- idom (B) = idom (A);
- recount_idom (A); */
-
- for (; old_dest != dest; old_dest = tmp)
- {
- basic_block dom;
-
- tmp = EDGE_SUCC (old_dest, 0)->dest;
-
- if (get_immediate_dominator (CDI_DOMINATORS, tmp) == old_dest
- && !dominated_by_p (CDI_DOMINATORS, bb, tmp))
- {
- dom = get_immediate_dominator (CDI_DOMINATORS, old_dest);
- set_immediate_dominator (CDI_DOMINATORS, tmp, dom);
- }
+ if (seen_abnormal_edge)
+ {
+ /* Move the labels to the new block, so that the redirection of
+ the abnormal edges works. */
- dom = recount_dominator (CDI_DOMINATORS, old_dest);
- set_immediate_dominator (CDI_DOMINATORS, old_dest, dom);
- }
+ bsi_to = bsi_start (dest);
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
+ {
+ label = bsi_stmt (bsi);
+ gcc_assert (TREE_CODE (label) == LABEL_EXPR);
+ bsi_remove (&bsi);
+ bsi_insert_before (&bsi_to, label, BSI_CONTINUE_LINKING);
}
}
- return retval;
-}
+ /* Update the dominators. */
+ if (dom_info_available_p (CDI_DOMINATORS))
+ {
+ basic_block dom, dombb, domdest;
+ dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
+ domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
+ if (domdest == bb)
+ {
+ /* Shortcut to avoid calling (relatively expensive)
+ nearest_common_dominator unless necessary. */
+ dom = dombb;
+ }
+ else
+ dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
+
+ set_immediate_dominator (CDI_DOMINATORS, dest, dom);
+ }
-/* Thread jumps over empty statements.
+ /* And kill the forwarder block. */
+ delete_basic_block (bb);
- This code should _not_ thread over obviously equivalent conditions
- as that requires nontrivial updates to the SSA graph.
+ return true;
+}
- As a precondition, we require that all basic blocks be reachable.
- That is, there should be no opportunities left for
- delete_unreachable_blocks. */
+/* Removes forwarder blocks. */
static bool
-thread_jumps (void)
+cleanup_forwarder_blocks (void)
{
basic_block bb;
- bool retval = false;
- basic_block *worklist = xmalloc (sizeof (basic_block) * last_basic_block);
+ bool changed = false;
+ basic_block *worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
basic_block *current = worklist;
FOR_EACH_BB (bb)
{
- bb_ann (bb)->forwardable = tree_forwarder_block_p (bb);
- bb->flags &= ~BB_VISITED;
+ if (tree_forwarder_block_p (bb, false))
+ *current++ = bb;
}
- /* We pretend to have ENTRY_BLOCK_PTR in WORKLIST. This way,
- ENTRY_BLOCK_PTR will never be entered into WORKLIST. */
- ENTRY_BLOCK_PTR->flags |= BB_VISITED;
-
- /* Initialize WORKLIST by putting non-forwarder blocks that
- immediately precede forwarder blocks because those are the ones
- that we know we can thread jumps from. We use BB_VISITED to
- indicate whether a given basic block is in WORKLIST or not,
- thereby avoiding duplicates in WORKLIST. */
- FOR_EACH_BB (bb)
+ while (current != worklist)
{
- edge_iterator ei;
- edge e;
+ bb = *--current;
+ changed |= remove_forwarder_block (bb, ¤t);
+ }
- /* We are not interested in finding non-forwarder blocks
- directly. We want to find non-forwarder blocks as
- predecessors of a forwarder block. */
- if (!bb_ann (bb)->forwardable)
- continue;
+ free (worklist);
+ return changed;
+}
- /* Now we know BB is a forwarder block. Visit each of its
- incoming edges and add to WORKLIST all non-forwarder blocks
- among BB's predecessors. */
- FOR_EACH_EDGE (e, ei, bb->preds)
+/* Merge the PHI nodes at BB into those at BB's sole successor. */
+
+static void
+remove_forwarder_block_with_phi (basic_block bb)
+{
+ edge succ = EDGE_SUCC (bb, 0);
+ basic_block dest = succ->dest;
+ tree label;
+ basic_block dombb, domdest, dom;
+
+ /* We check for infinite loops already in tree_forwarder_block_p.
+ However it may happen that the infinite loop is created
+ afterwards due to removal of forwarders. */
+ if (dest == bb)
+ return;
+
+ /* If the destination block consists of a nonlocal label, do not
+ merge it. */
+ label = first_stmt (dest);
+ if (label
+ && TREE_CODE (label) == LABEL_EXPR
+ && DECL_NONLOCAL (LABEL_EXPR_LABEL (label)))
+ return;
+
+ /* Redirect each incoming edge to BB to DEST. */
+ while (EDGE_COUNT (bb->preds) > 0)
+ {
+ edge e = EDGE_PRED (bb, 0), s;
+ tree phi;
+
+ s = find_edge (e->src, dest);
+ if (s)
{
- /* We don't want to put a duplicate into WORKLIST. */
- if ((e->src->flags & BB_VISITED) == 0
- /* We are not interested in threading jumps from a forwarder
- block. */
- && !bb_ann (e->src)->forwardable)
+ /* We already have an edge S from E->src to DEST. If S and
+ E->dest's sole successor edge have the same PHI arguments
+ at DEST, redirect S to DEST. */
+ if (phi_alternatives_equal (dest, s, succ))
{
- e->src->flags |= BB_VISITED;
- *current++ = e->src;
+ e = redirect_edge_and_branch (e, dest);
+ PENDING_STMT (e) = NULL_TREE;
+ continue;
}
+
+ /* PHI arguments are different. Create a forwarder block by
+ splitting E so that we can merge PHI arguments on E to
+ DEST. */
+ e = EDGE_SUCC (split_edge (e), 0);
}
- }
- /* Now let's drain WORKLIST. */
- while (worklist != current)
- {
- bb = *--current;
+ s = redirect_edge_and_branch (e, dest);
- /* BB is no longer in WORKLIST, so clear BB_VISITED. */
- bb->flags &= ~BB_VISITED;
+ /* redirect_edge_and_branch must not create a new edge. */
+ gcc_assert (s == e);
- if (thread_jumps_from_bb (bb))
+ /* Add to the PHI nodes at DEST each PHI argument removed at the
+ destination of E. */
+ for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
{
- retval = true;
+ tree def = PHI_ARG_DEF (phi, succ->dest_idx);
- if (tree_forwarder_block_p (bb))
+ if (TREE_CODE (def) == SSA_NAME)
{
- edge_iterator ej;
- edge f;
-
- bb_ann (bb)->forwardable = true;
+ tree var;
- /* Attempts to thread through BB may have been blocked
- because BB was not a forwarder block before. Now
- that BB is a forwarder block, we should revisit BB's
- predecessors. */
- FOR_EACH_EDGE (f, ej, bb->preds)
+ /* If DEF is one of the results of PHI nodes removed during
+ redirection, replace it with the PHI argument that used
+ to be on E. */
+ for (var = PENDING_STMT (e); var; var = TREE_CHAIN (var))
{
- /* We don't want to put a duplicate into WORKLIST. */
- if ((f->src->flags & BB_VISITED) == 0
- /* We are not interested in threading jumps from a
- forwarder block. */
- && !bb_ann (f->src)->forwardable)
+ tree old_arg = TREE_PURPOSE (var);
+ tree new_arg = TREE_VALUE (var);
+
+ if (def == old_arg)
{
- f->src->flags |= BB_VISITED;
- *current++ = f->src;
+ def = new_arg;
+ break;
}
}
}
+
+ add_phi_arg (phi, def, s);
}
+
+ PENDING_STMT (e) = NULL;
}
- ENTRY_BLOCK_PTR->flags &= ~BB_VISITED;
+ /* Update the dominators. */
+ dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
+ domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
+ if (domdest == bb)
+ {
+ /* Shortcut to avoid calling (relatively expensive)
+ nearest_common_dominator unless necessary. */
+ dom = dombb;
+ }
+ else
+ dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
- free (worklist);
+ set_immediate_dominator (CDI_DOMINATORS, dest, dom);
+
+ /* Remove BB since all of BB's incoming edges have been redirected
+ to DEST. */
+ delete_basic_block (bb);
+}
- return retval;
+/* This pass merges PHI nodes if one feeds into another. For example,
+ suppose we have the following:
+
+ goto <bb 9> (<L9>);
+
+<L8>:;
+ tem_17 = foo ();
+
+ # tem_6 = PHI <tem_17(8), tem_23(7)>;
+<L9>:;
+
+ # tem_3 = PHI <tem_6(9), tem_2(5)>;
+<L10>:;
+
+ Then we merge the first PHI node into the second one like so:
+
+ goto <bb 9> (<L10>);
+
+<L8>:;
+ tem_17 = foo ();
+
+ # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
+<L10>:;
+*/
+
+static void
+merge_phi_nodes (void)
+{
+ basic_block *worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
+ basic_block *current = worklist;
+ basic_block bb;
+
+ calculate_dominance_info (CDI_DOMINATORS);
+
+ /* Find all PHI nodes that we may be able to merge. */
+ FOR_EACH_BB (bb)
+ {
+ basic_block dest;
+
+ /* Look for a forwarder block with PHI nodes. */
+ if (!tree_forwarder_block_p (bb, true))
+ continue;
+
+ dest = EDGE_SUCC (bb, 0)->dest;
+
+ /* We have to feed into another basic block with PHI
+ nodes. */
+ if (!phi_nodes (dest)
+ /* We don't want to deal with a basic block with
+ abnormal edges. */
+ || has_abnormal_incoming_edge_p (bb))
+ continue;
+
+ if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
+ {
+ /* If BB does not dominate DEST, then the PHI nodes at
+ DEST must be the only users of the results of the PHI
+ nodes at BB. */
+ *current++ = bb;
+ }
+ }
+
+ /* Now let's drain WORKLIST. */
+ while (current != worklist)
+ {
+ bb = *--current;
+ remove_forwarder_block_with_phi (bb);
+ }
+
+ free (worklist);
}
+static bool
+gate_merge_phi (void)
+{
+ return 1;
+}
+
+struct tree_opt_pass pass_merge_phi = {
+ "mergephi", /* name */
+ gate_merge_phi, /* gate */
+ merge_phi_nodes, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_TREE_MERGE_PHI, /* tv_id */
+ PROP_cfg | PROP_ssa, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func | TODO_ggc_collect /* todo_flags_finish */
+ | TODO_verify_ssa,
+ 0 /* letter */
+};
/* Return a non-special label in the head of basic block BLOCK.
Create one if it doesn't exist. */
case SWITCH_EXPR:
{
tree cases = get_cases_for_edge (e, stmt);
- edge e2 = find_edge (e->src, dest);
/* If we have a list of cases associated with E, then use it
as it's a lot faster than walking the entire case vector. */
if (cases)
{
+ edge e2 = find_edge (e->src, dest);
tree last, first;
first = cases;
gcc_assert (PHI_RESULT (phi) == PHI_RESULT (phi_copy));
def = PHI_ARG_DEF_FROM_EDGE (phi, e);
- add_phi_arg (&phi_copy, def, e_copy);
+ add_phi_arg (phi_copy, def, e_copy);
}
}
}
tree name = ssa_name (ver);
phi = create_phi_node (name, exit->dest);
- add_phi_arg (&phi, name, exit);
- add_phi_arg (&phi, name, exit_copy);
+ add_phi_arg (phi, name, exit);
+ add_phi_arg (phi, name, exit_copy);
SSA_NAME_DEF_STMT (name) = phi;
}
/* If we see "return;" in some basic block, then we do reach the end
without returning a value. */
else if (warn_return_type
+ && !TREE_NO_WARNING (cfun->decl)
&& EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
&& !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
{
locus = &cfun->function_end_locus;
warning ("%Hcontrol reaches end of non-void function", locus);
#endif
+ TREE_NO_WARNING (cfun->decl) = 1;
break;
}
}
OSDN Git Service
