←back to thread

Why SSA Compilers?

(mcyoung.xyz)
158 points transpute | 2 comments | | HN request time: 0.555s | source
Show context
noelwelsh ◴[] No.45675013[source]
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.
replies(3): >>45675172 #>>45675361 #>>45675764 #
pizlonator ◴[] No.45675361[source]
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.

replies(2): >>45676259 #>>45678499 #
1. zozbot234 ◴[] No.45676259[source]
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.
replies(1): >>45676785 #
2. pizlonator ◴[] No.45676785[source]
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