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@xxxxxxxxxxxxxxxx
=======================================

.