Re: bug in dominance algorithm

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

Hi,

On Wed, 13 Jun 2001, Jan Hubicka wrote:

> it looks like there is a bug in our dominance tree computation.
> In case I have two basic blocks with no successors, they are always
> postdominating each other, that is IMO false.
> Can someone more familiar with the algorithm check it?

OK, once more, and this time publically (I know, I should have written the
following in dominance.c as comments, and I'll do this as time permits):

dominators are defined for _reachable_ nodes in a CFG.
Likewise postdominators are defined for nodes from which EXIT is
reachable.

I.e. asking for postdominators for blocks, from which EXIT isn't reachable
(as is the case if they have no successors at all) invokes undefined
behaviour.  In the dominator case the code even abort()'s (so the
prerequisite for dominance.c is a clean CFG without any unreachable BB's)
if some nodes aren't reachable.  For the postdom case this isn't usefull,
as also in nice and clean CFGs there can be blocks without successors
(e.g. blocks ending with an _exit() call), so there the code basically
builds a DFS forest (instead of a tree) and goes on from there.  The
effect is, that for nodes without a path to EXIT the postdom often is the
nearest node common to all paths away from that node.  For nodes without
successor at all, this of course is crippled.

So, your observed behaviour is neither wrong nor right, it is undefined.
What do you need this for?  (I mean postdoms for reverse-unreachable
blocks)


Ciao,
Michael.