Re: Dominance frontier example in Engineering a Compiler

Rayiner,


I think there is a mistake in the example.


> I'm a little confused about the dominance frontier example given in
> section 9.2 of Cooper & Torczon's "Engineering a Compiler". The
> example in question is reproduced on page 12 of these slides:
> http://www.cs.rice.edu/~keith/512/Lectures/08SSA.pdf
>
> When I run the algorithm they give on the example CFG, I end up with
> B1 in its own dominance frontier. This makes sense, since B1 dominates
> a predecessor of itself (B7), but does not strictly dominate itself.
> However, the worked example shows the dominance frontier of B being
> empty. The book explains this by saying something along the lines of
> "the compiler notices that B7's immediate dominator is B1, so it adds
> B1 to DF(B7) and to no other node", but does not explain why the
> algorithm terminates its backtracking before B1, instead of continuing
> up the dominator tree to B0.


You have noticed the mistake exactly. Using the version of the
algorithm that is on wikipedia (http://en.wikipedia.org/wiki/
Static_single_assignment_form), the following steps occur while
visiting B1:


// for each node b
b = B1
// if the number of predecessors of b >= 2
# preds for B1 is 2


// for each p in pred[b]
for each p in pred[B1]
runner = B7


// while runner is not idom(b)
B7 is not idom(B1), B0 is idom(B1)


// add b to runner's DF set
DF(B7) = {B1}


// runner = idom(runner)
runner = idom(B7) = B1


// while runner is not idom(b)
B1 is not idom(B1)


// add b to runner's DF set
DF(B1) = {B1}
...


Nodes can definitely be in their own dominance frontier. As
illustration why it is sometimes necessary, consider the following
statements in B0 and B1 of the example we are discussing:


B0
x = ...


B1
... = x
x = ...


B1 must be in its own dominance frontier so that a phi function for x
is placed at the top of B1.


-Michelle


=======================================
    Michelle Mills Strout
    Assistant Professor


    Colorado State University
    Computer Science Department
    1873 Campus Delivery
    Fort Collins, CO 80523-1873


    (970) 491-7026
    mstrout@cs.colostate.edu
=======================================

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