Dominance frontier example in "Engineering a Compiler"

Rayiner Hashem <rayiner@gmail.com>
Tue, 19 Jun 2007 07:05:40 -0700

          From comp.compilers

Related articles
Dominance frontier example in "Engineering a Compiler" rayiner@gmail.com (Rayiner Hashem) (2007-06-19)
Re: Dominance frontier example in "Engineering a Compiler" klvnraju@gmail.com (Raj) (2007-07-03)
Re: Dominance frontier example in "Engineering a Compiler" rayiner@gmail.com (Rayiner Hashem) (2007-07-03)
Re: Dominance frontier example in Engineering a Compiler mstrout@cs.colostate.edu (Michelle Strout) (2007-07-05)
| List of all articles for this month |

From: Rayiner Hashem <rayiner@gmail.com>
Newsgroups: comp.compilers
Date: Tue, 19 Jun 2007 07:05:40 -0700
Organization: Compilers Central
Keywords: analysis, question
Posted-Date: 19 Jun 2007 10:29:21 EDT

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.


Post a followup to this message

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