Static Single Assignment (TOPLAS Oct '91 paper questions)

I have some questions about the Cytron, et. al. paper "Efficiently Computing
Static Single Assignment Form and the Control Dependence Graph" appearing in
ACM TOPLAS 13(4):451-490.


Question #1:


On page 480 the commentary on data structures used in the algorithm for
dead code elimination (figure 17) mentions a structure called '"ipdom(B)'
is used. The definition is "the basic block that immediately
postdominates block B". However, i don't see any explicit mention of
'ipdom' in figure 17. My interpretation is that 'ipdom' is used in
synthesizing 'CD^-1(B)' from the RCGF using the algorithm in figure 10 (as
described in figure 14). The question is: does this seem correct?


Question #2:


Theorem 4 states:
"For programs comprised of straight-line code, if-then-else, and while-do
constructs, the dominance frontier of any CFG node contains as most two
nodes."


Unfortunately, programs also consist of Pascal-like CASE constructs and
repeat-until constructs. The latter can easily be transformed into a
while-do construct without loss of efficiency at the expense of some code
size increase. The former can also be transformed to a cascade of
if-then-else constructs, but this seems to introduce potential run-time
efficiency loss when a jump table would be the preferred implementation.


I don't think there's any fundamental changes to the algorthmic complexity
by the introduction of case constructs. Programs don't consist solely of
case constructs. It seems that instead of a fixed number of nodes for the
dominance frontier (two), one could use a dynamically-sized array.


Comments, suggestions?


Question #3:


Some languages (C, Oberon) support a predefined routine 'halt' or 'exit'
which terminates execution of a program when encountered at run-time. Such
a statement, technically speaking, such a node in the CFG would not have a
edge HaltNode -> Exit. It seems that it won't hurt to have such an edge
just to keep everything working the way it's supposed to. Can anyone think
of problems with this approach?


Thanks in advance!


            Chuck Lins, Oberon-2 Paladin. lins@apple.com
--

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