# Re: A question about Dominators

## Jeremy Wright <jeremy.wright@merant.com>20 Dec 2001 00:39:53 -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: Jeremy Wright Newsgroups: comp.compilers Date: 20 Dec 2001 00:39:53 -0500 Organization: Micro Focus References: 01-12-067 Keywords: analysis Posted-Date: 20 Dec 2001 00:39:53 EST

Robert Sherry wrote:
>
> The following paragraph is from the book Advanced Compiler Design
> Implementation by Steven S. Muchnick. I can be found on page 182.
>
> We give two approaches to computing the set of dominators of each node
> in a flowgraph. The basic idea of the first approach is that 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.
>
> I believe that the above statement is incorrect. Please consider the
> following flowgraph.
> Nodes{ a, b, c, d, e }
> Edges{ (a,c), (a,d), (c,e), (d,e), (e,b) )
> a is the start node
>
> In this case, a dominates b. However, it violates the if and only if given
> above since b has a unique predecessor. The believe the correct statement
> would be:
>
> The basic idea of the first approach is that 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.

I think the last phrase should read "c equals a or a dominates c"
which of course simplifies to "a dominates c".

Consider
N = { a, b, c}
E = { (a,b), (a,c) }
G = < N, E, a >

a is an immediate predecessor of b, but not a unique predecessor.

Remember though that this is an English description of an algorithm -
not a formal express of the algorithm, or a definition of the
dominator relation.

Post a followup to this message