[comp.compilers] use-def chains

preston@titan.rice.edu (Preston Briggs) (09/19/89)

Howdy,

I'm curious about how many people actually build
use-def chains for optimization.

(That is, for each variable reference, a list of all the instructions
 that might have set the variable.  Alternatively, def-use chains
 link a definition with all the uses.)

They are mentioned often in the literature, but seem expensive in
time and space to build.  On the other hand, Wegman and Zadeck (and
others) have been playing with a form called Static Single Assignment
(SSA) which seems reasonably space efficient.  They also have methods
to construct the form quickly, at least for reducible flow graphs.

So, any experience out there?  I'm especially interested in
space-efficient representations (think BIG fortran routines), so
ideas for compact representation are welcome too.

Thanks,
Preston Briggs
preston@titan.rice.edu
-- 
Send compilers articles to compilers@ima.isc.com or, perhaps, Levine@YALE.EDU
{ decvax | harvard | yale | bbn }!ima.  Meta-mail to ima!compilers-request.
Please send responses to the author of the message, not the poster.

johnson@cs.uiuc.edu (Ralph Johnson) (09/21/89)

Static single assignment is very nice.  We have been using it in our
Smalltalk compiler and it has worked out well.  It might store the
same information as use-def chains, but it stores it in a form that
is much easier to access and maintain.  I don't worry about space,
because our routines are small, so I can't comment on that, but the
speed claims seem to be accurate.

Ralph Johnson
[From Ralph Johnson <johnson@cs.uiuc.edu>]
-- 
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus}!esegue.  Meta-mail to compilers-request@esegue.
Please send responses to the author of the message, not the poster.

preston@rice.edu (Preston Briggs) (09/27/89)

In article <1989Sep20.193824.999@esegue.segue.boston.ma.us> you write:
>Static single assignment is very nice.  We have been using it in our

Several people wrote in response to my original query (Thanks!).
Many wondered about references to static single assignment (SSA).
Here's the ref's I know of, for general consumption:

	Alpern, Wegman, Zadeck
	"Detecting equality of values in programs"
	Proceedings of 15th POPL, 1988

	Rosen, Wegman, Zadeck
	"Global value numbers and redundant computations"
	Proceedings of 15th POPL, 1988

	Cytron, Ferrante, Rosen, Wegman, Zadeck
	"An efficient method of computing static single assignment form"
	Proceedings of 16th POPL, 1989

where POPL is Principles of Programming Languages.

The last paper is a way to compute the form.  The others are ways to
use it.  Generally, SSA seems like a feasible replacement for use-def
or def-use chains in (perhaps) any application.  In many cases, it
seems to lead to asymptotic time improvements.

Preston Briggs
[From Preston Briggs <preston@rice.edu>]
-- 
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus}!esegue.  Meta-mail to compilers-request@esegue.
Please send responses to the author of the message, not the poster.