SSA is Functional Programming (1998) [pdf] | Hacker News Reader

SSA is Functional Programming (1998) [pdf]

cs.princeton.edu

54 pointsatombender23 comments

(This paper gets rediscovered by HN every so often, there are interesting discussions on past threads)

While Appel is definitely a smart guy (he's been working in the field for a very long time), this is kind of the limit of taking something that was done to be eminently practical reasons and trying to turn it into a theoretical masterpiece. In the time period in which he did it, he did it because SSA was super-popular and he was trying to repopularize functional programming, AFAICT. Note also: The functional guys never proved anything about any of the time bounds/etc below - because that was never their goal.

SSA was created and thought about for a simple reason: To make dataflow problems faster in compilers.

So saying they are doing exactly the same thing is also a bit silly in the sense that one of them is trying to make compilers faster, and don't actually care how they do it - if they could wave a wand, they would have. The other group had very very different goals. They wouldn't have particularly cared if you could make the compilers faster, they were trying to make programming better. (This is a rough generalization, of course).

Zadeck[1] certainly understood SSA was functional, they just didn't really care, it wasn't particularly relevant to interests :)

The analogy also breaks down really heavily once you start to extend SSA.

This is why SSA and other things went in the direction they did afterwards - extensions towards faster/better dataflow.

It's worth understanding a little history (which i am going to do off the top of my head and probably get a few details wrong - sorry. I'm also going to generalize a little bit, because it's hard to summarize an entire field's development in a few paragraphs)

In the 70's, we had a problem. We had discovered and built generalized frameworks for analysis of programs[2]: General bitvector dataflow (which was what was done in the 70's and early eighties) has proven timebounds, and they are not good. It was being worked on by some of the smartest people i've ever had the honor of meeting (Aho, Ullman, Allen, Tarjan, Kennedy, etc).

For general dataflow problems, those timebounds are N^3[3]. You can prove that, the way it was done, if you could solve it faster, you get yourself a faster algorithm for transitive closure/boolean matrix multiplication. That's the point at which practical people tend to go "well shit we're screwed"

Then some of these folks proved that a class of dataflow problems (which included a lot people wanted to do) known as RAPID problems could be solved in linear number of steps. This brought overall time to N^2 for those problems. These are the analysis/optimization you generally saw in compilers for many years until SSA took over. N^2 was somewhat fine because of the state of the kinds of programs being compiled and the limitations people were willing to accept in things like "number of variables allowed per function" at the time.

At this point, the world split, with various people going down the path of trying to find more general frameworks that expand that class of problems, others sticking with rapid problems, and a small number going off and trying ways that looked different from the way current dataflow problems were done.

Zadeck (who created that part of SSA) is arguably in the latter category. His thesis was on partitioned variable approaches, which are basically "instead of one large dataflow graph, make one per variable that can be computed faster"[4].

This is the essence of SSA, and interestingly is not constrained by the bitvector time bound i gave you above (he told me he basically had to argue about this to everyone he ever met because they wouldn't believe it).

Which brings us back around to why SSA exists: To take classes of problems that were constrained by the proven time bounds of bitvector dataflow, making them N^2 overall (or worse), unconstrain them by enabling sparse formulations that could be done in linear time.

That's it.

There were other attempts outside of SSA, that did not involve actual renaming forms, SSA just caught on because it was simple and handled the stuff people wanted to do at the time (IMHO).

SSA can be generalized in a way that does this for other classes of problems too:

https://homepages.dcc.ufmg.br/~fernando/classes/dcc888/readi...

(There are also sparse evaluation graphs, but they are slower and don't generalize as well, as the paper goes into).

In essence: SSA can be shown to be part of a general class of linear time transforms to program representations that make other dataflow analysis/optimization linear time.

In the end, it's relationship to functional programming is coincidental at best, and in practice, somewhat more tenuous than described here.

[1] Full disclosure: He was my officemate at IBM research for a few years.

[2] If you've never read up on Frances Allen, she's amazing and basically created the field of automatic program optimization. As she would tell you, it builds on a lot of pieces of work of others, but ... The papers she wrote are completely approachable and still relevant today.

[3] It is usually referred to by the number of bitvevtor operations in earlier literature, and those are assumed to be constant time because they are for small bitmaps. So it's usually listed as N^2.

[4] He also hated bitvectors because he is dyslexic, and trying to debug strings of 1s and 0s where the position is important was kind of a nightmare.

The relationship is not that tenuous. The slogan "SSA is functional programming" means something very specific: dominance relationships in SSA are in one-to-one correspondence with nested scope of letrec-based abstract syntax trees (let's call it LRAST). LRASTs support sparse analysis. The connection is quite close: transformations on SSA are in one-to-one correspondence with transformations on LRASTs (e.g. phi elimination is called lambda dropping).

You could imagine a SSA intermediate representation that also stores the dominator tree, and where each transformation of IR needs to update the dominator tree so that it stays in sync with the IR. That's what functional language compilers were doing.

Although they are formally equivalent, SSA is better than LRAST because some transformations that are easy on SSA are difficult on LRAST. A simple and local transformation on SSA, such as common subexpression elimination, may change dominance relationships and therefore requires restructuring of nested scopes in the LRAST. There have been a lot of papers in the functional programming literature about doing that kind of restructuring for transformations that are trivial on SSA. This is one of the reasons why the optimisations done by SSA based compilers are usually more advanced than those done by LRAST based compilers. The result of this paper was that some functional language compilers switched to SSA. MLton for example.

Awesome comment! Quick follow-up question:

"If you've never read up on Frances Allen, she's amazing and basically created the field of automatic program optimization. As she would tell you, it builds on a lot of pieces of work of others, but ... The papers she wrote are completely approachable and still relevant today."

I've never heard of her or maybe just saw Allen on a paper. Which are the must-read works so I can catch up and share them with others?

I remember her from the provocative comments in the interview quoted here. She said the C language was horrible for the the field of optimizing compilers:

https://news.ycombinator.com/item?id=15581319

By 1960, we had a long list of amazing languages: Lisp, APL, Fortran, COBOL, Algol 60. These are higher-level than C. We have seriously regressed, since C developed. C has destroyed our ability to advance the state of the art in automatic optimization, automatic parallelization, automatic mapping of a high-level language to the machine.

To build on top of this. Here is the PL.8 paper, the PL/I variant that IBM used for their RISC research.

"An overview of the PL.8 compiler"

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.453...

An optimizing compiler that is pretty much LLVM in 1982.

Her paper on control flow analyis written in 1970 is a better intro to flow analysis than most compiler books you will find today (IMHO): http://www.cs.columbia.edu/~suman/secure_sw_devel/p1-allen.p...

Though it covers intervals, which no longer are used due to other abstractions being found to be better later on.

That was a great compiler group. I had the privilege of doing a short internship there one summer. Remember Lisp/VM? Lots of good people there. And many great stories about Fran Allen as well.

Can you or anyone find some of those discussions in past threads? I searched and couldn't.

I came across the article in another thread [1], and found the idea very interesting that Static Single Assignment (SSA) as an optimization can be viewed as an intermediate language that is functional.

In other words, a language such as Go or Rust that optimizes a program into SSA form sort of turns itself into a functional language in the process, and lessons learned from functional languages can be applied here.

[1] https://news.ycombinator.com/item?id=18799434

The Remill [1] machine code to LLVM bitcode binary translator lifts procedural code into an SSA form (LLVM's) and abstracts over the modelled program's memory using small step semantics that also benefits from SSA form. The way it works is that "memory" is just another value, and writes to memory are applied through function calls which return the new value of memory, and reads to memory are calls which accept the current memory value. This document describes it visually [2].

[1] https://github.com/trailofbits/remill

[2] https://github.com/trailofbits/remill/blob/master/docs/LIFE_...

Has anyone tried to define a subset of Python, JS, C, Go, etc. that is SSA and actually write programs in it?

Is it annoying or natural? I feel like I mostly do it in python but I have no way to machine-check it.

Is the problem that you can’t do any aliasing of mutable containers? That is useful for many problems.

Yes, mutation of containers is definitely a problem. The natural semantics in SSA is something like container' = F(container, key, value). But of course this functional semantics straightaway diverges from the physical realization we expect as programmers, namely not a new thing called container', but the original container whose state has changed.

SSA is terribly overworked. It was a great formulation for certain compiler problems. To my mind, the problem for which it was perfectly suited was value numbering. Doing it in SSA form made it not only fast, but gave it a deeper power, as it became possible to easily "reach back" to deeper levels of input to an expression. But for a reason that's unclear to me, it was pushed into all kinds of applications where it's much less obvious that it's a good choice. Treating it as a programming language (lol) is, I guess, kind of the limit of wishful thinking about its universality.

Hm that is an interesting viewpoint. It seems like compilers are converging on it though? LLVM and GCC both use it.

I recall this talk being good:

GopherCon 2017: Keith Randall - Generating Better Machine Code with SSA

https://www.youtube.com/watch?v=uTMvKVma5ms&t=1s

Go has built-in mutable containers, and no const, yet they still use SSA. Is there a real alternative?

I guess it is mainly for speeding up code that uses a lot of integers and doubles and so forth, and not code that uses a lot of strings and containers?

>> Go has built-in mutable containers, and no const, yet they still use SSA.

Right, as you say, compilers are converging on SSA, and almost all languages have mutable containers. All it means is that there's a mismatch between the semantics of the IL and the semantics of the language. That's a fairly common situation; there are lots of semantics (like concurrency and associated memory consistency) that can't be captured in an IL as they occur in reality, in the language being compiled. It's just a thing that has to be worked around.

I tend to write C++ in a sort of limited SSA form a lot of the time: almost all local variables and parameters const, class members all initialized in the constructor initializer list, mutation confined to small functions or lambdas. If you're not familiar with const in C++, using it for locals and parameters gives you compiler checking that you're not modifying variables after assignment. This is one of the biggest things I miss from C++ when writing C#.

Containers can make things a bit trickier but using algorithms and confining most mutation to helper functions makes it doable a lot of the time. The new ranges library being standardized for C++ 20 makes it more convenient to use containers in this style.

I am with you on const.

I tried something along those lines with a language called "radian", which was explicitly inspired by the Appel paper. I let the domain expire a while ago so all the design discussion is gone, but you can see the remnants of the project here: http://www.github.com/marssaxman/radian.git

It was not a strict subset of anything, but it was heavily inspired by Python. The goal was to constrain the language such that every for-loop could be decomposed into a map-reduce over an lazy iterator, so that the runtime could transparently schedule computation across all available cores.

It all worked out well enough, and nothing feels more natural than coding in a language designed precisely to suit one's individual taste; but the idiosyncratic requirements of the memory and processor model meant there was very little opportunity to reuse existing library code, and I wound up spending most of my time on yak-shaving expeditions and getting very little done.

I got around the mutable containers problem by not having any; the language included, as primitives, an ordered container based on finger trees and an associative container based on... hm... AVL trees maybe? It's been a while.

The issue is mostly the need for phi nodes everywhere for "true" SSA.

Might get away with something like- and I cite Rust here because I know it well, but these features are probably from ML-

> let x = if foo { 1 } else { 2 };

Loops are trickier- maybe you could write them as "unfolds"- where the loop body is effectively a fn foo(T) -> T, where T is a struct containing all the variables "modified" by the loop. Then evaluate iteratively, starting from the live values on entry. On exit, the live values are the result of the final invocation

Yeah now I remember from reading this paper a few weeks ago: An important point is that SSA is not executable!!! The Phi nodes need to be removed I suppose.

I will have to read this paper about Appel to see how that comes into play.

SSA form cannot be directly interpreted in order to generate code. Therefore it must be destructed before compilation can continue. This involves using an algorithm that converts phi-functions into appropriately-placed copy instructions.

Intermediate representations in imperative compilers: A survey

https://scholar.google.com/scholar?cluster=15761365096026414...

Like with parallel DFS, I always look for anything people say is not possible. Here's my first hit on Google with a super-quick skim indicating it runs with phi instructions:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.74....

May or may not be what you're looking for. Probably interesting nonetheless.

Thanks, that does look interesting. The fact that interpreting SSA requires a paper means it's nontrivial, which lends credence to the original statement :) In the abstract it says they present a variant of SSA. I will take a look.

Phi functions are a syntactical hack which can be avoided by allowing a basic block that would contain a "phi function" to instead take parameters (similar to the ANF representation). It's a lot more principled than the "phi" hack, but still quite simple and intuitive.

I saw somewhere a short paper presenting a syntax to write programs in essentially SSA directly, which I think was sort of like that, but it's not coming up in a quick search. I'd thought it was by Anton Ertl.

FWIW, I used this idea (extended basic blocks are functions with m arguments and n results) in https://github.com/darius/idel with a Forth-like syntax back in 2001.

Reply on news.ycombinator.com