On Tue, Dec 8, 2015 at 3:23 PM, Richard Biener
<[email protected]> wrote:
> On Tue, Dec 8, 2015 at 7:15 AM, Jeff Law <[email protected]> wrote:
>>
>> First in the series. This merely refactors code from tree-ssa-sccvn.c into
>> domwalk.c so that other walkers can use it as they see fit.
>>
>>
>> There's an initialization function which sets all edges to executable.
>>
>> There's a test function to see if a block is reachable.
>>
>> There's a propagation function to propagate the unreachable property to
>> edges.
>>
>> Finally a function to clear m_unreachable_dom. I consider this a wart.
>> Essentially that data member contains the highest unreachable block in the
>> dominator tree. Once we've finished processing that block's children, we
>> need to clear the member. Ideally clients wouldn't need to call this member
>> function.
>>
>> Bikeshedding on the members names is encouraged. And if someone has a
>> clean, simple way to ensure that the m_unreachable_dom member gets cleared
>> regardless of whether or not a client has its own after_dom_children
>> callback, I'd love to hear it.
>
> I wonder if it makes more sense to integrate this with the domwalker
> itself. Add
> a constructor flag to it and do everything in itself. By letting the
> before_dom_children
> return a taken edge (or NULL if unknown) it can drive the outgoing edge
> marking.
> And the domwalk worker would simply not recurse to dom children for
> unreachable
> blocks.
So interface-wise do
Index: gcc/domwalk.h
===================================================================
--- gcc/domwalk.h (revision 231396)
+++ gcc/domwalk.h (working copy)
@@ -30,13 +30,16 @@ along with GCC; see the file COPYING3.
class dom_walker
{
public:
- dom_walker (cdi_direction direction) : m_dom_direction (direction) {}
+ dom_walker (cdi_direction direction,
+ bool skip_unreachable_blocks = false)
+ : m_dom_direction (direction),
+ m_skip_unreachable_blocks (skip_unreachable_blocks) {}
/* 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) {}
+ virtual edge before_dom_children (basic_block) {}
/* Function to call after the recursive walk of the dominator children. */
virtual void after_dom_children (basic_block) {}
@@ -47,6 +50,7 @@ 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;
+ const bool m_skip_unreachable_blocks;
};
#endif
and simply inline all the code into dom_walker::walk.
Richard.
> Richard.
>
>> OK for trunk?
>>
>>
>> Jeff
>>
>> commit 5e53fefae0373768b98d51d5746d43f36cecbe2a
>> Author: Jeff Law <[email protected]>
>> Date: Mon Dec 7 11:32:58 2015 -0700
>>
>> * domwalk.h (dom_walker::init_edge_executable): New method.
>> (dom_walker::maybe_clear_unreachable_dom): Likewise.
>> (dom_walker::bb_reachable): Likewise.
>> (dom_walker::propagate_unreachable_to_edges): Likewise.
>> (dom_walker::m_unreachable_dom): New private data member.
>> * domwalk.c: Include dumpfile.h.
>> (dom_walker::init_edge_executable): New method.
>> (dom_walker::maybe_clear_unreachable_dom): Likewise.
>> (dom_walker::bb_reachable): Likewise. Factored out of
>> tree-ssa-sccvn.c
>> (dom_walker::propagate_unreachable_to_edges): Likewise.
>> * 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.
>> (sccvn_dom_walker::before_dom_children): Similarly.
>> (run_scc_vn): Likewise.
>>
>> diff --git a/gcc/domwalk.c b/gcc/domwalk.c
>> index 167fc38..feb6478 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,93 @@ cmp_bb_postorder (const void *a, const void *b)
>> return 1;
>> }
>>
>> +/* Mark all edges in the CFG as possibly being executable. */
>> +
>> +void
>> +dom_walker::init_edge_executable (struct function *fun)
>> +{
>> + basic_block bb;
>> + FOR_ALL_BB_FN (bb, fun)
>> + {
>> + 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 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;
>> +}
>> +
>> +/* When we propagate the unreachable property to edges, we
>> + also arrange to track the highest block in the dominator
>> + walk which was unreachable. We can use that to identify
>> + more unreachable blocks.
>> +
>> + When we finish processing the dominator children for that
>> + highest unreachable block, we need to make sure to clear
>> + that recorded highest block unreachable block in the
>> + dominator tree. */
>> +
>> +void
>> +dom_walker::maybe_clear_unreachable_dom (basic_block bb)
>> +{
>> + if (m_unreachable_dom == bb)
>> + m_unreachable_dom = NULL;
>> +}
>> +
>> /* Recursively walk the dominator tree.
>> BB is the basic block we are currently visiting. */
>>
>> diff --git a/gcc/domwalk.h b/gcc/domwalk.h
>> index 71a7c47..d6b37a2 100644
>> --- a/gcc/domwalk.h
>> +++ b/gcc/domwalk.h
>> @@ -30,7 +30,8 @@ along with GCC; see the file COPYING3. If not see
>> class dom_walker
>> {
>> public:
>> - dom_walker (cdi_direction direction) : m_dom_direction (direction) {}
>> + dom_walker (cdi_direction direction) : m_dom_direction (direction),
>> + m_unreachable_dom (NULL) {}
>>
>> /* Walk the dominator tree. */
>> void walk (basic_block);
>> @@ -41,12 +42,41 @@ public:
>> /* Function to call after the recursive walk of the dominator children.
>> */
>> virtual void after_dom_children (basic_block) {}
>>
>> + /* The next several methods support discovering unreachable blocks
>> + and edges in the CFG during the dominator walk. Using these routines
>> + is totally optional and only makes sense if your walker can change
>> + the state of a block/edge to unreachable/unexecutable and your walker
>> + can exploit that information to optimize better. */
>> +
>> + /* Set EDGE_EXECUTABLE for every edge in the CFG. This must be done
>> + before walking begins. */
>> + void init_edge_executable (struct function *);
>> +
>> + /* Query whether or not the given block is reachable or not.
>> +
>> + Typically used in the before_dom_children callback. */
>> + 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);
>> +
>> + /* This is a bit of a wart. We need to conditionally clear a bit of
>> + state after we have process the dominator children.
>> +
>> + I'd prefer to hide this detail within domwalk, but right now it
>> + bleeds out into the clients. */
>> + void maybe_clear_unreachable_dom (basic_block);
>> +
>> private:
>> /* This is the direction of the dominator tree we want to walk. i.e.,
>> if it is set to CDI_DOMINATORS, then we walk the dominator tree,
>> if it is set to CDI_POST_DOMINATORS, then we walk the post
>> dominator tree. */
>> const ENUM_BITFIELD (cdi_direction) m_dom_direction : 2;
>> + basic_block m_unreachable_dom;
>> };
>>
>> #endif
>> diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
>> index 2014ee7..dbd61c9 100644
>> --- a/gcc/tree-ssa-sccvn.c
>> +++ b/gcc/tree-ssa-sccvn.c
>> @@ -4207,8 +4207,7 @@ 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), fail (false), cond_stack (vNULL) {}
>> ~sccvn_dom_walker ();
>>
>> virtual void before_dom_children (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,8 +4299,7 @@ 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;
>> + this->maybe_clear_unreachable_dom (bb);
>>
>> while (!cond_stack.is_empty ()
>> && cond_stack.last ().first == bb)
>> @@ -4327,45 +4324,11 @@ sccvn_dom_walker::before_dom_children (basic_block
>> bb)
>> 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)
>> + /* If BB is not reachable, then propagate that property to edges, but
>> + do not process this block any further. */
>> + if (!this->bb_reachable (cfun, bb))
>> {
>> - 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;
>> -
>> + this->propagate_unreachable_to_edges (bb, dump_file, dump_flags);
>> return;
>> }
>>
>> @@ -4519,7 +4482,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,18 +4511,10 @@ 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;
>> + walker.init_edge_executable (cfun);
>> walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
>> if (walker.fail)
>> {
>>
