Re: A question about Dominators

Martin.Ward@durham.ac.uk (Martin Ward)20 Dec 2001 00:37:32 -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: Martin.Ward@durham.ac.uk (Martin Ward) Newsgroups: comp.compilers Date: 20 Dec 2001 00:37:32 -0500 Organization: Compilers Central References: 01-12-067 Keywords: analysis, books Posted-Date: 20 Dec 2001 00:37:32 EST

Robert Sherry <rsherry8@home.com> writes:
> 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 think that the last part should be "if c is not equal to a then
a dominates c", in which case it would be a correct definition
of the *immediate* dominator.

> 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.

a dominates b in this graph, but e is the immediate dominator of b.

> 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.

This definition is also flawed. Consider the graph:

Nodes{ a, b, c }
Edges{ (a,b), (a,c), (c,b) }

Then a is not the unique predecessor of b (so the first part fails),
and b has a predecessor equal to a, so the second part also fails.

But a clearly dominates b.

Appel ("Modern Compiler Implementation in C") in Section 18.1
on page 413 gives a simple pair of equations for dominators
which basically say that "start" is the only dominator of the start
node, and for all other nodes n, the dominators for n are n plus
the nodes which dominate all predecessors of n:

Dom[start] = {start}

and

Dom[n] = {n} \union ( \Intersection_{p \in pred[n]} Dom[p] )

for n not equal to start.

It seems appropriate here to plug the latest release of the
FermaT Program Transformation System which includes perl modules
for fast computation of immediate dominators, control dependencies
and Static Single Assignment form. It also includes new transformations
for computing SSA form and for forwards and backwards slicing of WSL
using dataflow analysis. See:

http://www.cse.dmu.ac.uk/~mward/martin/software/

Martin

Martin.Ward@durham.ac.uk http://www.cse.dmu.ac.uk/~mward/ Erdos number: 4

Post a followup to this message