This is the refactoring part of the patch -- essentially bits move from
tree-ssa-sccvn into domwalk so that other domwalk clients can benefit
from the ability to detect unreachable blocks and propagate unreachable
edge properties.
This also fixes up tree-ssa-sccvn to use the new bits from domwalk.
commit 0485724b3e1c80ed1d4c3f4d263f6675cebe27a7
Author: Jeff Law <l...@redhat.com>
Date: Mon Dec 7 11:32:58 2015 -0700
2015-12-05 Jeff Law <l...@redhat.com>
* domwalk.h (dom_walker::dom_walker): Add new argument
skip_unreachable_blocks. Don't provide empty constructor body.
(dom_walker::before_dom_children): Change return type.
(dom_walker::bb_reachable): Declare new private method.
(dom_walker::propagate_unreachable_to_edges): Likewise.
(dom_walker::m_unreachable_dom): Declare new private data member.
(dom_walker::m_skip_unreachable_blocks): Likewise.
* domwalk.c: Include dumpfile.h.
(dom_walker::dom_walker): New constructor. Initialize private data
members. If needed, set EDGE_EXECUTABLE for all edges in the CFG,
extracted from tree-ssa-sccvn.c.
(dom_walker::bb_reachable): New method extracted from tree-ssa-sccvn.c
(dom_walker::propagate_unreachable_to_edges): Likewise.
(dom_walker::walk): Only call before_dom_children on reachable
blocks. If before_dom_children returns an edge, then clear
EDGE_EXECUTABLE for all other outgoing edges from the same block.
For unreachable blocks, call propagate_unreachable_to_edges.
Similarly, only call after_dom_children on reachable blocks. For
unreachable blocks, conditionally clear m_unreachable_dom.
* tree-ssa-sccvn.c (sccvn_dom_walker::unreachable_dom): Remove
private data member.
(sccvn_dom_walker::after_dom_children): Use methods from dom_walker
class.
(run_scc_vn): Likewise.
(sccvn_dom_walker::before_dom_children): Likewise. Return the taken
outgoing edge if a COND, SWITCH, or GOTO are optimized.
diff --git a/gcc/domwalk.c b/gcc/domwalk.c
index 167fc38..2332191 100644
--- a/gcc/domwalk.c
+++ b/gcc/domwalk.c
@@ -24,6 +24,7 @@ along with GCC; see the file COPYING3. If not see
#include "backend.h"
#include "cfganal.h"
#include "domwalk.h"
+#include "dumpfile.h"
/* This file implements a generic walker for dominator trees.
@@ -142,6 +143,91 @@ cmp_bb_postorder (const void *a, const void *b)
return 1;
}
+/* Constructor for a dom walker.
+
+ If SKIP_UNREACHBLE_BLOCKS is true, then we need to set
+ EDGE_EXECUTABLE on every edge in the CFG. */
+dom_walker::dom_walker (cdi_direction direction,
+ bool skip_unreachable_blocks)
+ : m_dom_direction (direction),
+ m_skip_unreachable_blocks (skip_unreachable_blocks),
+ m_unreachable_dom (NULL)
+{
+ /* If we are not skipping unreachable blocks, then there is nothing
+ to do. */
+ if (!m_skip_unreachable_blocks)
+ return;
+
+ basic_block bb;
+ FOR_ALL_BB_FN (bb, cfun)
+ {
+ edge_iterator ei;
+ edge e;
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ e->flags |= EDGE_EXECUTABLE;
+ }
+}
+
+/* Return TRUE if BB is reachable, false otherwise. */
+
+bool
+dom_walker::bb_reachable (struct function *fun, basic_block bb)
+{
+ /* If we're not skipping unreachable blocks, then assume everything
+ is reachable. */
+ if (!m_skip_unreachable_blocks)
+ return true;
+
+ /* If any of the predecessor edges that do not come from blocks dominated
+ by us are still marked as possibly executable consider this block
+ reachable. */
+ bool reachable = false;
+ if (!m_unreachable_dom)
+ {
+ reachable = bb == ENTRY_BLOCK_PTR_FOR_FN (fun);
+ edge_iterator ei;
+ edge e;
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ if (!dominated_by_p (CDI_DOMINATORS, e->src, bb))
+ reachable |= (e->flags & EDGE_EXECUTABLE);
+ }
+
+ return reachable;
+}
+
+/* BB has been determined to be unreachable. Propagate that property
+ to incoming and outgoing edges of BB as appropriate. */
+
+void
+dom_walker::propagate_unreachable_to_edges (basic_block bb,
+ FILE *dump_file,
+ int dump_flags)
+{
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Marking all outgoing edges of unreachable "
+ "BB %d as not executable\n", bb->index);
+
+ edge_iterator ei;
+ edge e;
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ e->flags &= ~EDGE_EXECUTABLE;
+
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Marking backedge from BB %d into "
+ "unreachable BB %d as not executable\n",
+ e->src->index, bb->index);
+ e->flags &= ~EDGE_EXECUTABLE;
+ }
+ }
+
+ if (!m_unreachable_dom)
+ m_unreachable_dom = bb;
+}
+
/* Recursively walk the dominator tree.
BB is the basic block we are currently visiting. */
@@ -171,9 +257,23 @@ dom_walker::walk (basic_block bb)
|| bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
|| bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
{
+
/* Callback for subclasses to do custom things before we have walked
the dominator children, but before we walk statements. */
- before_dom_children (bb);
+ if (this->bb_reachable (cfun, bb))
+ {
+ edge taken_edge = before_dom_children (bb);
+ if (taken_edge)
+ {
+ edge_iterator ei;
+ edge e;
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (e != taken_edge)
+ e->flags &= ~EDGE_EXECUTABLE;
+ }
+ }
+ else
+ propagate_unreachable_to_edges (bb, dump_file, dump_flags);
/* Mark the current BB to be popped out of the recursion stack
once children are processed. */
@@ -203,7 +303,10 @@ dom_walker::walk (basic_block bb)
/* Callback allowing subclasses to do custom things after we have
walked dominator children, but before we walk statements. */
- after_dom_children (bb);
+ if (bb_reachable (cfun, bb))
+ after_dom_children (bb);
+ else if (m_unreachable_dom == bb)
+ m_unreachable_dom = NULL;
}
if (sp)
bb = worklist[--sp];
diff --git a/gcc/domwalk.h b/gcc/domwalk.h
index 71a7c47..7c4a534 100644
--- a/gcc/domwalk.h
+++ b/gcc/domwalk.h
@@ -30,13 +30,26 @@ along with GCC; see the file COPYING3. If not see
class dom_walker
{
public:
- dom_walker (cdi_direction direction) : m_dom_direction (direction) {}
+ /* Use SKIP_UNREACHBLE_BLOCKS = true when your client can discover
+ that some edges are not executable.
+
+ If a client can discover that a COND, SWITCH or GOTO has a static
+ target in the before_dom_children callback, the taken edge should
+ be returned. The generic walker will clear EDGE_EXECUTABLE on all
+ edges it can determine are not executable. */
+ dom_walker (cdi_direction direction, bool skip_unreachable_blocks = false);
/* Walk the dominator tree. */
void walk (basic_block);
- /* Function to call before the recursive walk of the dominator children. */
- virtual void before_dom_children (basic_block) {}
+ /* Function to call before the recursive walk of the dominator children.
+
+ Return value is the always taken edge if the block has multiple outgoing
+ edges, NULL otherwise. When skipping unreachable blocks, the walker
+ uses the taken edge information to clear EDGE_EXECUTABLE on the other
+ edges, exposing unreachable blocks. A NULL return value means all
+ outgoing edges should still be considered executable. */
+ virtual edge before_dom_children (basic_block) { return NULL; }
/* Function to call after the recursive walk of the dominator children. */
virtual void after_dom_children (basic_block) {}
@@ -47,6 +60,18 @@ private:
if it is set to CDI_POST_DOMINATORS, then we walk the post
dominator tree. */
const ENUM_BITFIELD (cdi_direction) m_dom_direction : 2;
+ bool m_skip_unreachable_blocks;
+ basic_block m_unreachable_dom;
+
+ /* Query whether or not the given block is reachable or not. */
+ bool bb_reachable (struct function *, basic_block);
+
+ /* Given an unreachable block, propagate that property to outgoing
+ and possibly incoming edges for the block. Typically called after
+ determining a block is unreachable in the before_dom_children
+ callback. */
+ void propagate_unreachable_to_edges (basic_block, FILE *, int);
+
};
#endif
diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
index 2014ee7..1d1c3e3 100644
--- a/gcc/tree-ssa-sccvn.c
+++ b/gcc/tree-ssa-sccvn.c
@@ -4207,11 +4207,10 @@ class sccvn_dom_walker : public dom_walker
{
public:
sccvn_dom_walker ()
- : dom_walker (CDI_DOMINATORS), fail (false), unreachable_dom (NULL),
- cond_stack (vNULL) {}
+ : dom_walker (CDI_DOMINATORS, true), fail (false), cond_stack (vNULL) {}
~sccvn_dom_walker ();
- virtual void before_dom_children (basic_block);
+ virtual edge before_dom_children (basic_block);
virtual void after_dom_children (basic_block);
void record_cond (basic_block,
@@ -4220,7 +4219,6 @@ public:
enum tree_code code, tree lhs, tree rhs, bool value);
bool fail;
- basic_block unreachable_dom;
vec<std::pair <basic_block, std::pair <vn_nary_op_t, vn_nary_op_t> > >
cond_stack;
};
@@ -4301,9 +4299,6 @@ sccvn_dom_walker::record_conds (basic_block bb,
void
sccvn_dom_walker::after_dom_children (basic_block bb)
{
- if (unreachable_dom == bb)
- unreachable_dom = NULL;
-
while (!cond_stack.is_empty ()
&& cond_stack.last ().first == bb)
{
@@ -4318,56 +4313,14 @@ sccvn_dom_walker::after_dom_children (basic_block bb)
/* Value number all statements in BB. */
-void
+edge
sccvn_dom_walker::before_dom_children (basic_block bb)
{
edge e;
edge_iterator ei;
if (fail)
- return;
-
- /* If any of the predecessor edges that do not come from blocks dominated
- by us are still marked as possibly executable consider this block
- reachable. */
- bool reachable = false;
- if (!unreachable_dom)
- {
- reachable = bb == ENTRY_BLOCK_PTR_FOR_FN (cfun);
- FOR_EACH_EDGE (e, ei, bb->preds)
- if (!dominated_by_p (CDI_DOMINATORS, e->src, bb))
- reachable |= (e->flags & EDGE_EXECUTABLE);
- }
-
- /* If the block is not reachable all outgoing edges are not
- executable. Neither are incoming edges with src dominated by us. */
- if (!reachable)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "Marking all outgoing edges of unreachable "
- "BB %d as not executable\n", bb->index);
-
- FOR_EACH_EDGE (e, ei, bb->succs)
- e->flags &= ~EDGE_EXECUTABLE;
-
- FOR_EACH_EDGE (e, ei, bb->preds)
- {
- if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "Marking backedge from BB %d into "
- "unreachable BB %d as not executable\n",
- e->src->index, bb->index);
- e->flags &= ~EDGE_EXECUTABLE;
- }
- }
-
- /* Record the most dominating unreachable block. */
- if (!unreachable_dom)
- unreachable_dom = bb;
-
- return;
- }
+ return NULL;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Visiting BB %d\n", bb->index);
@@ -4428,7 +4381,7 @@ sccvn_dom_walker::before_dom_children (basic_block bb)
&& !DFS (res))
{
fail = true;
- return;
+ return NULL;
}
}
for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
@@ -4441,20 +4394,20 @@ sccvn_dom_walker::before_dom_children (basic_block bb)
&& !DFS (op))
{
fail = true;
- return;
+ return NULL;
}
}
/* Finally look at the last stmt. */
gimple *stmt = last_stmt (bb);
if (!stmt)
- return;
+ return NULL;
enum gimple_code code = gimple_code (stmt);
if (code != GIMPLE_COND
&& code != GIMPLE_SWITCH
&& code != GIMPLE_GOTO)
- return;
+ return NULL;
if (dump_file && (dump_flags & TDF_DETAILS))
{
@@ -4497,19 +4450,17 @@ sccvn_dom_walker::before_dom_children (basic_block bb)
gcc_unreachable ();
}
if (!val)
- return;
+ return NULL;
edge taken = find_taken_edge (bb, vn_valueize (val));
if (!taken)
- return;
+ return NULL;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Marking all edges out of BB %d but (%d -> %d) as "
"not executable\n", bb->index, bb->index, taken->dest->index);
- FOR_EACH_EDGE (e, ei, bb->succs)
- if (e != taken)
- e->flags &= ~EDGE_EXECUTABLE;
+ return taken;
}
/* Do SCCVN. Returns true if it finished, false if we bailed out
@@ -4519,7 +4470,6 @@ sccvn_dom_walker::before_dom_children (basic_block bb)
bool
run_scc_vn (vn_lookup_kind default_vn_walk_kind_)
{
- basic_block bb;
size_t i;
default_vn_walk_kind = default_vn_walk_kind_;
@@ -4549,15 +4499,6 @@ run_scc_vn (vn_lookup_kind default_vn_walk_kind_)
}
}
- /* Mark all edges as possibly executable. */
- FOR_ALL_BB_FN (bb, cfun)
- {
- edge_iterator ei;
- edge e;
- FOR_EACH_EDGE (e, ei, bb->succs)
- e->flags |= EDGE_EXECUTABLE;
- }
-
/* Walk all blocks in dominator order, value-numbering stmts
SSA defs and decide whether outgoing edges are not executable. */
sccvn_dom_walker walker;
