|Static Single Assignment (TOPLAS Oct '91 paper questions) email@example.com (Chuck Lins) (1992-01-15)|
|Re: Static Single Assignment (TOPLAS Oct '91 paper questions) grover@brahmand.Eng.Sun.COM (1992-01-16)|
|Re: Static Single Assignment (TOPLAS Oct '91 paper questions) firstname.lastname@example.org (1992-01-19)|
|From:||email@example.com (Preston Briggs)|
|Organization:||Rice University, Houston|
|Date:||Sun, 19 Jan 1992 17:45:04 GMT|
Chuck Lins <firstname.lastname@example.org> 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
>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
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.
Return to the
Search the comp.compilers archives again.