# Re: A question about Dominators

## sweeks@acm.org (Stephen Weeks)20 Dec 2001 00:38:48 -0500

From comp.compilers

Related articles
A question about Dominators rsherry8@home.com (Robert Sherry) (2001-12-15)
Re:A question about Dominators kvinay@ip.eth.net (kvinay) (2001-12-20)
Re: A question about Dominators vbdis@aol.com (2001-12-20)
Re: A question about Dominators Martin.Ward@durham.ac.uk (2001-12-20)
Re: A question about Dominators sweeks@acm.org (2001-12-20)
Re: A question about Dominators jeremy.wright@merant.com (Jeremy Wright) (2001-12-20)
| List of all articles for this month |

 From: sweeks@acm.org (Stephen Weeks) Newsgroups: comp.compilers Date: 20 Dec 2001 00:38:48 -0500 Organization: http://groups.google.com/ References: 01-12-067 Keywords: analysis Posted-Date: 20 Dec 2001 00:38:48 EST

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.

Post a followup to this message