Home » forums » LtU Forum

SSA vs. CPS (and ANF?)

If SSA and CPS (and ANF?) are provably equivalent, why does SSA seem much more popular than CPS in current language compiler implementation?

Any info, history, background, pointers to other discussions, etc. greatly appreciated.

Also, what is the current "state of the art" for CPS conversion? I think my resources - "Compiling with Continuations" and a 90's edition of EOPL - are quite dated. Moreover, I'd *love* to study a good treatment of CPS conversion and optimization that handles assignment.

Many thanks.

By scottmcl at 2009-06-19 16:26 | LtU Forum | previous forum topic | next forum topic | other blogs | 13605 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

This is the last paper I

This is the last paper I came across.

By naasking at Fri, 2009-06-19 16:31 | login or register to post comments

Essence six years on, ten years on

Story: Retrospective: The Essence of Compiling with Continuations.

Postscript — Link fixed, thx Matt M

By Charles Stewart at Fri, 2009-06-19 18:32 | login or register to post comments

Actual link

Here

By Matt M at Fri, 2009-06-19 18:44 | login or register to post comments

Danvy - Nielsen on CPS conversion

The paper "A first-order one-pass CPS transformation" shows a bunch of different CPS transforms and puts them in context.

> why does SSA seem much more popular than CPS in current language compiler implementation?

CPS reifies the continuations; compiler writers of imperative languages don't seem to need that.

By Dimitris Vardoulakis at Sat, 2009-06-20 11:28 | login or register to post comments

Thanks all

What are the "canonical" papers or books on SSA?

Scott

By scottmcl at Mon, 2009-06-22 21:04 | login or register to post comments

Not all easy to get

Kennet Zadeck gave a talk on the history of SSA earlier this year that with luck will turn into a nice history paper. Three papers mentioned there of historical interest that I've tried to get hold of but can't:

  • Cytron, Lowry & Zadeck, 1986. Code Motion of Control Structures in High-Level Languages. pp. 70-85 of Proc. POPL #13.
  • Cytron & Ferrante, 1987. What's In a Name? -or- The Value of Renaming for Parallelism Detection and Storage Allocation. pp. 19-27. Proc. International Conference on Parallel Processing.
  • Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, F. Kenneth Zadeck, 1989. An Efficient Method of Computing Static Single Assignment Form. pp. 25-35 of Proc. POPL #16.

The 1991 ToPLAS version of the 1989 paper is available, with the same title. This would count as a canonical paper.

I'm guessing you have the Kelsey paper already, but for the sake of completeness it's the subject of the Pure imperative programming story.

By Charles Stewart at Tue, 2009-06-23 08:36 | login or register to post comments

SSA Bibliography

The SSA Bibliography has links to other classic papers.

By michaelw at Tue, 2009-06-23 18:33 | login or register to post comments

Equivalence implications

If SSA and CPS (and ANF?) are provably equivalent, why does SSA seem much more popular than CPS in current language compiler implementation?

To answer indirectly, note that proofs of equivalence are not proofs of convenient equivalence. The lambda calculus is equivalent to turing machines, but TM's are rarely sugared into usable programming practice. The LC stands straight and tall in Haskell, and can easily be seen behind the curtain of ML- and Lisp-derivatives. Regular expressions and finite automata are equivalent; the former is generally easy on the user's eyes, the latter superior for machine execution.
Thus, equivalence actually cuts the other way than you are questioning; since they're computationally equivalent, other factors control the choice of implementation. As most programs are a few intermediate variables away from SSA to start with, I'd imagine there is little motivation to translate to CPS. Also, any language without explicit CPS machinery would need enormous translational overhead.

This is not to dissuade you from exploring the matter, of course. If you're interested in typing, your next step might be to look into the Howard-Curry Isomorphism. That one has a bit more use as an actual equivalence, such as in theorem provers.

By Chad Wellington at Tue, 2009-06-23 20:01 | login or register to post comments