←back to thread

Why SSA Compilers?

(mcyoung.xyz)
158 points transpute | 7 comments | | HN request time: 0.957s | source | bottom
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 #
1. 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 #
2. antonvs ◴[] No.45676333[source]
> take a look at how V8's move to Sea-of-Nodes has gone for them.

Are you implying it hasn't gone well? I thought it bought some performance at least. What are the major issues? Any sources I can follow up on?

replies(1): >>45676673 #
3. 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?..

4. kibwen ◴[] No.45676673[source]
V8 blog post from March: "Land ahoy: leaving the Sea of Nodes" https://v8.dev/blog/leaving-the-sea-of-nodes
replies(2): >>45676772 #>>45679135 #
5. antonvs ◴[] No.45676772{3}[source]
Fascinating, thanks!
6. pjmlp ◴[] No.45679131[source]
Meanwhile Java Hotspot, where Sea-of-Nodes was originally made mainstream, and GraalVM are doing just fine.

The author of Sea-of-Nodes approach is quite critic of V8's decision, as one would expect.

https://www.youtube.com/watch?v=Zo801M9E--M

7. pjmlp ◴[] No.45679135{3}[source]
Feedback from sea of nodes algorithm creator, https://www.youtube.com/watch?v=Zo801M9E--M