←back to thread

Why SSA Compilers?

(mcyoung.xyz)
160 points transpute | 1 comments | | HN request time: 0.581s | source
Show context
zachixer ◴[] No.45675783[source]
Every time I see a clean SSA explainer like this, I’m reminded that the “simplicity” of SSA only exists because we’ve decided mutation is evil. It’s not that SSA is simpler — it’s that we’ve engineered our entire optimization pipeline around pretending state doesn’t exist.

It’s a brilliant illusion that works… until you hit aliasing, memory models, or concurrency, and suddenly the beautiful DAG collapses into a pile of phi nodes and load/store hell.

replies(8): >>45675858 #>>45675871 #>>45676050 #>>45676212 #>>45676222 #>>45676288 #>>45678531 #>>45678840 #
achierius ◴[] No.45675871[source]
You have it backwards. Modern compilers don't use SSA because it's "simpler", we use it because it enables very fast data-flow optimizations (constant prop, CSE, register allocation, etc.) that would otherwise require a lot of state. It doesn't "pretend state doesn't exist", it's actually exactly what makes it possible/practical for the compiler to handle changes in state.

As some evidence to the second point: Haskell is a language that does enforce immutability, but it's compiler, GHC, does not use SSA for main IR -- it uses a "spineless tagless g-machine" graph representation that does, in fact, rely on that immutability. SSA only happens later once it's lowered to a mutating form. If your variables aren't mutated, then you don't even need to transform them to SSA!

Of course, you're welcome to try something else, people certainly have -- take a look at how V8's move to Sea-of-Nodes has gone for them.

replies(3): >>45676333 #>>45676374 #>>45679131 #
1. mananaysiempre ◴[] No.45676374[source]
To appreciate the “fast” part, nothing beats reading though LuaJIT’s lj_opt_fold.c, none of which would work without SSA.

Of course, LuaJIT is cheating, because compared to most compilers it has redefined the problem to handling exactly two control-flow graphs (a line and a line followed by a loop), so most of the usual awkward parts of SSA simply do not apply. But isn’t creatively redefining the problem the software engineer’s main tool?..