Re: [RFA] [PATCH] [PR tree-optimization/68619] Avoid direct cfg cleanups in tree-ssa-dom.c [1/3]

[Jeff Law]

On 12/08/2015 07:27 AM, Richard Biener wrote:


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

[ ... ]
Close :-)

If skip_unreachable_blocks is true, then we want the walker to 
initialize EDGE_EXECUTABLE automatically.  So we drop the member 
initialization and constructor body from domwalk.h and instead have a 
ctor in domwalk.c where we can initialize the private members and set 
EDGE_EXECUTABLE as needed.


My first iteration let the clients clear EDGE_EXECUTABLE as they found 
conditionals that could be optimized.  That was pretty clean and 
localized in sccvn & dom.


If we have the before_dom_children return the taken edge, then we have 
to twiddle all the clients due to the api change in before_dom_children. 
 .  There's ~18 in total, so it's not too bad.


2 of the 18 clearly need to use the skip_unreachable_blocks capability 
(dom and sccvn).  2 others might be able to use it (tree-ssa-pre.c and 
tree-ssa-propagate.c)  I converted dom and sccvn, but not pre and the 
generic propagation engine.


I can submit the iteration which lets clients clear EDGE_EXECUTABLE, or 
the iteration where the clients return the taken edge (or NULL) from the 
before_dom_children callback.


Either is fine with me, so if you have a preference, let me know.

jeff

Re: [RFA] [PATCH] [PR tree-optimization/68619] Avoid direct cfg cleanups in tree-ssa-dom.c [1/3]

[Richard Biener]

On Wed, Dec 9, 2015 at 9:31 AM, Jeff Law  wrote:
> On 12/08/2015 07:27 AM, Richard Biener wrote:
>>>
>>>
>>> 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
>
> [ ... ]
> Close :-)
>
> If skip_unreachable_blocks is true, then we want the walker to initialize
> EDGE_EXECUTABLE automatically.  So we drop the member initialization and
> constructor body from domwalk.h and instead have a ctor in domwalk.c where
> we can initialize the private members and set EDGE_EXECUTABLE as needed.
>
> My first iteration let the clients clear EDGE_EXECUTABLE as they found
> conditionals that could be optimized.  That was pretty clean and localized
> in sccvn & dom.
>
> If we have the before_dom_children return the taken edge, then we have to
> twiddle all the clients due to the api change in before_dom_children.  .
> There's ~18 in total, so it's not too bad.
>
> 2 of the 18 clearly need to use the skip_unreachable_blocks capability (dom
> and sccvn).  2 others might be able to use it (tree-ssa-pre.c and
> tree-ssa-propagate.c)  I converted dom and sccvn, but not pre and the
> generic propagation engine.
>
> I can submit the iteration which lets clients clear EDGE_EXECUTABLE, or the
> iteration where the clients return the taken edge (or NULL) from the
> before_dom_children callback.
>
> Either is fine with me, so if you have a preference, let me know.

Return the taken edge.

Richard.

> jeff

[RFA] [PATCH] [PR tree-optimization/68619] Avoid direct cfg cleanups in tree-ssa-dom.c [1/3] v2

[Jeff Law]

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 
Date:   Mon Dec 7 11:32:58 2015 -0700

2015-12-05  Jeff Law  

* 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 &= 

Re: [RFA] [PATCH] [PR tree-optimization/68619] Avoid direct cfg cleanups in tree-ssa-dom.c [1/3]

[Richard Biener]

On Tue, Dec 8, 2015 at 7:15 AM, Jeff Law  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.

Richard.

> OK for trunk?
>
>
> Jeff
>
> commit 5e53fefae0373768b98d51d5746d43f36cecbe2a
> Author: Jeff Law 
> 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;
> +   }
> +}
> +

Re: [RFA] [PATCH] [PR tree-optimization/68619] Avoid direct cfg cleanups in tree-ssa-dom.c [1/3]

[Richard Biener]

On Tue, Dec 8, 2015 at 3:23 PM, Richard Biener
 wrote:
> On Tue, Dec 8, 2015 at 7:15 AM, Jeff Law  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 
>> 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.  */
>> +  

Re: [RFA] [PATCH] [PR tree-optimization/68619] Avoid direct cfg cleanups in tree-ssa-dom.c [1/3]

[Trevor Saunders]

On Mon, Dec 07, 2015 at 11:15:33PM -0700, Jeff Law 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.

Hmm, I expect you thought about this, but why not always see if we need
to clear it before calling after_dom_children () ?  I think that would
amount to an extra compare of a register and cached memory (we're just
about to use the vtable pointer anyway) so I expect that wouldn't effect
performance significantly.

Thinking about this more I wonder if we could move more of this into the
dom walker, and skip calling before / after dom_children on unreachable
blocks all together.  That would seem to work for sccvn, but I'm not
sure about what tree-ssa-dom.c is doing with the mark pushing and
clearing.

Trev

Re: [RFA] [PATCH] [PR tree-optimization/68619] Avoid direct cfg cleanups in tree-ssa-dom.c [1/3]

[Jeff Law]

On 12/08/2015 07:23 AM, Richard Biener wrote:


I wonder if it makes more sense to integrate this with the domwalker
itself.
I seriously considered that.  Essentially, letting the optimizer concern 
itself merely with asking for the improved domwalk and clearing 
EDGE_EXECUTABLE when the optimizer finds a conditional it can collapse. 
 Bury the rest entirely within domwalk.c.


It shouldn't be hard to prototype on top of the refactoring I've already 
done.


jeff

Re: [RFA] [PATCH] [PR tree-optimization/68619] Avoid direct cfg cleanups in tree-ssa-dom.c [1/3]

[Jeff Law]

On 12/08/2015 08:36 AM, Trevor Saunders wrote:


Thinking about this more I wonder if we could move more of this into the
dom walker, and skip calling before / after dom_children on unreachable
blocks all together.  That would seem to work for sccvn, but I'm not
sure about what tree-ssa-dom.c is doing with the mark pushing and
clearing.
Total brain lock, it hit when I got Richi's message, dumping it in the 
walker itself is the obvious choice.


jeff

[RFA] [PATCH] [PR tree-optimization/68619] Avoid direct cfg cleanups in tree-ssa-dom.c [1/3]

[Jeff Law]

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.


OK for trunk?


Jeff
commit 5e53fefae0373768b98d51d5746d43f36cecbe2a
Author: Jeff Law 
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