Re: Static Single Assignment (TOPLAS Oct '91 paper questions)

Chuck Lins <chuck_lins1@gateway.qm.apple.com> writes:


>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.


>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
>[CASE statements] 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.


They state the theorem carefully because they can only prove so much. The
goal isn't to prove that a particular data structure is adequate for the
dominance frontiers; instead they are try to show that in _most_ cases,
the size of the dominance frontiers is linear in the size of the input
code, which is a strong argument for the practicality of their data
structures.


They admit that their proof of linearity doesn't hold if REPEAT-UNTILs or
CASEs or ASSIGNED GOTOs ... are allowed, but we still get warm feelings
for the majority of our code.


>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?


If your compiler doesn't recognize that certain routines may not return
(such as you HALT example, or calls to exit() in C, or calls to a
user-defined routines containing a call to exit), it won't hurt
correctness to treat these as ordinary calls, but you can lose
opportunities for optimization.


Therefore, any node that _must_ cause control flow to exit the body of the
routine should have an edge to the Exit node. This includes RETURNs,
EXITs, and HALTs. Similarly, if a routine has multiple entry points (a la
Fortran), each entrance should have an edge from the Start node.


Preston Briggs
--

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