Re: bug in dominance algorithm

[Michael Matz <matzmich at cs dot tu-berlin dot de>]

Hi,

On Thu, 14 Jun 2001, Richard Henderson wrote:

> On Fri, Jun 15, 2001 at 07:59:10AM +0200, Michael Matz wrote:
> > Nevertheless note, that we _never_ get this any better for blocks without
> > _any_ successors.  For those postdoms really have no sane meaning ...
>
> Well, to me it seems more sane to say that there is no block that
> post-dominates them,

Yep, that's the pessimistic view.  Yes, it also is the correct one.

> as opposed to the current situation observed
> by Jan that all blocks with no successors post-dominate all other
> blocks with no successors.

And this of course is the nonsense approach (but nevertheless the
behaviour of the old code).

But there is a middle way, which is slightly incorrect but IMHO gives more
interesting information.  Suppose the following graph:

A-->C
|   |\
v   v \
B   D-->E-->F
|
v
EXIT

In some way, E could be seen as the immediate postdom of C, and also F
postdominating C, D and E.  The "interesting information" I talked about
is here, that "no matter which path is taken from C, nodes E and F are
reached".  These kind of questions are the ones which usually are answered
by dominance, so I think this is valuable information, even if strictly
incorrect.  I.e. I would like to mark nodes without successors as being
invalid for dominance questions, and otherwise provide the "dominators"
and, may be, a way to distinguish reverse-unreachable node from normal
ones.


Ciao,
Michael.