Re: A question about Dominators

Muchnick's condition:
> node a dominates node b if and only if a=b or a is the unique
> immediate predecessor of b or b has more then one immediate
> predecessor and for all immediate predecessors c of b, c is not equal
> to a and a dominates c.


Sherry's condition:
> node a dominates node b if and only if a=b or a is the unique
> immediate predecessor of b or for all immediate predecessors c of b, c
> is not equal to a and a dominates c.


Here is a counterexample.


Nodes{ r, a, b, c }
Edges{ (r,a), (a,b), (a,c), (c,b) }
r is the start node


In this graph, a dominates b, but a != b, a is not the unique
immediate predecessor of b, and a is an immediate predecessor of b.
Hence Muchnick's condition is violated. Sherry's condition is
violated for the same reason -- a is an immediate predecessor of b,
but not the unique one.


A property that is easy to verify and similar to both of the above
conditions is the following:


    a dom b iff (a = b or for all immediate predecessors c of b, a dom c)


This corresponds well with the pseudocode on Muchnick page 182. BTW,
it also is the basis for the pseudocode on page 671 of the Dragon
book, which gives the same algorithm.

Return to the comp.compilers page.
Search the comp.compilers archives again.