Re: Static Single Assignment (TOPLAS Oct '91 paper questions) (Preston Briggs)
Sun, 19 Jan 1992 17:45:04 GMT

          From comp.compilers

Related articles
Static Single Assignment (TOPLAS Oct '91 paper questions) (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) (1992-01-19)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Preston Briggs)
Keywords: optimize, design
Organization: Rice University, Houston
References: 92-01-061
Date: Sun, 19 Jan 1992 17:45:04 GMT

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

Preston Briggs

Post a followup to this message

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