Re: A question about Dominators

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

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