Re: bug in dominance algorithm

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

Hi,

On Fri, 15 Jun 2001, Jan Hubicka wrote:

> > 2) B is the entry to a noreturn section (i.e. B is postdominated by a
> >    noreturn block, without being one itself), for this dominance info in
> >    the above way can be used.
> This is what I am shooting for!
> Thanks a ton!

Hmm, below is a patch (only the essential parts) to do something like
this.  It essentially links all successorless nodes to EXIT.  Tell me, if
it works like you want (it bootstraps without regressions on x86).

Nonetheless I'm still not sure, this is the right or at least a good
approach.  The problem is (are?) not the reverse-unreachable (revun)
blocks in itself, but their connection to normal blocks with paths to
exit.  If we link the revun sections to EXIT, we essentially provide a
shortcut way to EXIT even for nodes with normal paths to EXIT.  The paths
leaving a normal node can be classified into two disjoint sets, those only
over nodes also having paths to EXIT, and those over a revun section
directly to EXIT.  This disjointness and the shortcut make the immediate
postdom of many nodes connected to revun blocks be EXIT.  This includes
blocks directly connected to revun sections (by one edge), as well as
blocks connected to revun section over a path, which does not contain the
immediate postdom of that block.  I might call them border nodes.

This could be changed, if we sort of ignore revun sections for postdom
calculation for normal nodes.  But I fear this will be even worse;
suppose:
A-->B
|
v
C-->EXIT

If we now ignore {B} for postdom(A), we have postdom(A)==C.  If we now had
a clever optimization which moves code from A to C (based on the
assumption, that all paths leaving A to EXIT also go over C, which is a
correct assumption) we could break code in B which may work with results
initially carried in A.  This of course is because our assumption in
itself was correct, but not applicable, because there are not only paths
to EXIT which leave A.

This in mind, and the fact, that EXIT can hold no code, it seems correct
to have postdom(A)==EXIT, which basically means, postdom(A) is nearly
useless.  But I see no correct way around this, also in the light of
meaning of postdoms:  after all, even revun sections somehow are exited.
This exit is kind of nirvana, but exists and is disjoint from all other
nodes in the CFG.  EXIT seems to be a good choice althoug slightly
incorrect.  Normally one would need a NIRWANA (;-)) node as landing zone,
and then border nodes land in EXIT and NIRWANA, which ultimately means,
that theyself have no still no postdom (right now they have EXIT, which
also is only a pseudo postdom).

Somehow by writing this mail I reassured myself, that linking revun
sections to EXIT is right, even if not nice to border blocks.  Somebody
disagree?  Better ideas?


Ciao,
Michael.