Why SSA Compilers?

The shocking truth is that SSA is functional! That's right, the compiler for your favourite imperative language actually optimizes functional programs. See, for example, https://www.jantar.org/papers/chakravarty03perspective.pdf. In fact, SSA, continuation passing style, and ANF are basically the same thing.

My experience with SSA is extremely limited, so that might be a stupid question. But does that remain true once memory enters the picture?

The llvm tutorials I played with (admittedly a long time ago) made it seem like "just allocate everything and trust mem2reg" basically abstracted SSA pretty completely from a user pov.

No they're not.

The essence of functional languages is that names are created by lambdas, labmdas are first class, and names might not alias themselves (within the same scope, two references to X may be referencing two instances of X that have different values).

The essence of SSA is that names must-alias themselves (X referenced twice in the same scope will definitely give the same value).

There are lots of other interesting differences.

But perhaps the most important difference is just that when folks implement SSA, or CPS, or ANF, they end up with things that look radically different with little opportunity for skills transfer (if you're an SSA compiler hacker then you'll feel like a fish out of water in a CPS compiler).

Folks like to write these "cute" papers that say things that sound nice but aren't really true.

The same thing I don't know... but a long time ago, I remember reading that SSA and CPS were isomorphic. Basically CPS being used for functional languages.

edit: actually even discussed on here

CPS is formally equivalent to SSA, is it not? What are advantages of using CPS o... | Hacker News https://share.google/PkSUW97GIknkag7WY

The whole ad-hoc mechanism of phi-nodes in SSA can be replaced by local blocks with parameters. A block that can take parameters is not that different conceptually from a lambda.

If you're hell bent on functional style, you can represent memory writes as ((Address, Value, X) -> X), where X is a compile-time-only linear type representing the current memory state, which can be manipulated like any other SSA variable. It makes some things more elegant, like two reads of the same address naturally being the same value (as long as it's reading from the same memory state). Doesn't help at all with aliasing analysis or write reordering though so I don't think any serious compilers do this.

Local blocks with parameters is the gross way to do it. The right way to do it is Phi/Upsilon form.

https://gist.github.com/pizlonator/cf1e72b8600b1437dda8153ea...

But even if you used block arguments, it's so very different from a lambda. Lambdas allow dynamic creation of variables, while SSA doesn't. Therefore, in SSA, variables must-alias themselves, while in the lambda calculus they don't. If you think that a block that takes arguments is the same as a lambda because you're willing to ignore such huge differences, then what's the limiting principle that would make you say that two languages really are different from one another?

Remember, all Turing complete languages are "conceptually the same" in the sense that you can compile them to one another

I've never been more confused than working on Maxine VM's CPS optimizing compiler.

The sea-of-nodes representation renames memory as just another dependence edge in a somewhat analogous manner.

I think you're asking if SSA is still a functional language in the presence of mutation of memory. Both Scheme and ML (of Standard ML and OCaml fame, not machine learning) allow mutation, so mutation doesn't seem to disqualify a language from being functional.

This naturally leads to the question "what is a functional language?" I've written my thoughts on what FP is at [1]. I argue that FP is about local reasoning and composition. The former is most relevant here: local reasoning means it's easy to reason about code. This is exactly why SSA is used in compiler: it makes it easy for the compiler to reason about code and therefore which optimizations are valid. This is the same argument given in these comments: https://news.ycombinator.com/item?id=45674568 and https://news.ycombinator.com/item?id=45678483

[1]: https://noelwelsh.com/posts/what-and-why-fp/