[HN Gopher] Why SSA Compilers?
___________________________________________________________________
Why SSA Compilers?
Author : transpute
Score : 61 points
Date : 2025-10-22 20:13 UTC (2 hours ago)
(HTM) web link (mcyoung.xyz)
(TXT) w3m dump (mcyoung.xyz)
| rdtsc wrote:
| I like the style of the blog but a minor nit I'd change is have a
| definition what SSA is right at the top. It discusses SSA for
| quite a while "SSA is a property of intermediate representations
| (IRs)", "it's frequently used" and only 10 paragraphs down
| actually defines what SSA is
|
| > SSA stands for "static single assignment", and was developed in
| the 80s as a way to enhance the existing three-argument code
| (where every statement is in the form x = y op z) so that every
| program was circuit-like, using a very similar procedure to the
| one described above.
|
| I understand it's one of those "well if you don't know what it
| is, the post is not for you" but I think it's a nice article and
| could get people who are not familiar with the details interested
| in it
|
| > The reason this works so well is because we took a function
| with mutation, and converted it into a combinatorial circuit, a
| type of digital logic circuit that has no state, and which is
| very easy to analyze.
|
| That's an interesting insight, it made sense to me. I only dealt
| with SSA when decompiling bytecode or debugging compiler issues,
| and never knew why it was needed, but that sort of made it click.
| vidarh wrote:
| This post is frankly one of the most convoluted discussions of
| SSA I've read. There's lots of info there, but I'd frankly
| suggest going back and look at a paper on implementing it. I
| think I first came across SSA in a paper adding it to Wirths
| Oberon compiler, and it was much more accessible.
|
| Edit: It was this paper by Brandis and Mossenbock:
| https://share.google/QNoV9G8yMBWQJqC82
| jhallenworld wrote:
| Also I recommend Bob Morgan's book:
|
| https://turbo51.com/download/Building-an-Optimizing-
| Compile-...
| Rochus wrote:
| Indeed a great book; I even have a paper copy.
|
| The SSA book is also pretty good: https://web.archive.org/w
| eb/20201111210448/https://ssabook.g...
| jchw wrote:
| Honestly, I think it's just something you either like or
| don't. If all you were trying to do was understand SSA, I
| agree this blog post is probably inefficient at that
| particular task, but often blog posts are entertainment as
| much as education, so meandering through a bunch of different
| things along the way is part of the deal. Personally I
| thought there were a lot of pretty interesting insights that
| I haven't seen a lot of discussion about in other places,
| though I will admit I mostly learned about SSA from Wikipedia
| and from people yelling about compilers online.
| Rochus wrote:
| Thanks for the link. Looks like an interesting paper. Here is
| the original reference:
| https://dl.acm.org/doi/10.1145/197320.197331.
|
| And here is a better readable postscript version: https://web
| .archive.org/web/20170706013237/ftp://ftp.ssw.uni...
| strbean wrote:
| I learned a bit about SSA in a compiler course. Among many
| other things, it is crucial for register assignment. You want
| to know each distinct value that will exist, and the lifetimes
| of those values, in order to give each a register. Then, if
| have more distinct values existing at one time than you have
| registers, you have to push stuff to the stack.
| noelwelsh wrote:
| 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.
| Chabsff wrote:
| 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.
| pizlonator wrote:
| 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.
| aatd86 wrote:
| 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
| mbauman wrote:
| Forget compilers, SSA is an immensely valuable readability
| improvement for humans, too.
| zachixer wrote:
| 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.
| vidarh wrote:
| SSA is appealing because you can defer the load/store hell
| until _after_ a bunch of optimizations, though, and a lot of
| those optimizations becomes a lot easier to reason about when
| you get to pretend state doesn 't exist.
| achierius wrote:
| 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.
| toast0 wrote:
| > pretending state doesn't exist.
|
| As a fan of a functional language, immutability doesn't mean
| state doesn't exist. You keep state with assignment --- in SSA,
| every piece of state has a new name.
|
| If you want to keep state beyond the scope of a function, you
| have to return it, or call another function with it (and hope
| you have tail call elimination). Or, stash it in a mutable
| escape hatch.
| KeplerBoy wrote:
| Smallest of nitpicks: the depicted multiplier is a 2 bit
| multiplier. A one bit multiplier is just an and gate.
| pubby wrote:
| I like this article a lot but it doesn't answer the question of
| "Why SSA?".
|
| Sure, a graph representation is nice, but that isn't a unique
| property of SSA. You can have graph IRs that aren't SSA at all.
|
| And sure, SSA makes some optimizations easy, but it also makes
| other operations more difficult. When you consider that, plus the
| fact that going into and out of SSA is quite involved, it doesn't
| seem like SSA is worth the fuss.
|
| So why SSA?
|
| Well, it turns out compilers have sequencing issues. If you view
| compilation as a series of small code transformations, your
| representation goes from A -> B, then B -> C, then C -> D and so
| on. At least, that's how it works for non-optimizing compilers.
|
| For optimizing compilers however, passes want to loop. Whenever
| an optimization is found, previous passes should be run again
| with new inputs... if possible. The easiest way to ensure this is
| to make all optimizations input and output the same
| representation. So A -> B is no good. We want A -> A: a singular
| representation.
|
| So if we want a singular representation, let's pick a good one
| right? One that works reasonably well for most things. That's why
| SSA is useful: it's a decently good singular representation we
| can use for every pass.
| ivanjermakov wrote:
| Static single assignment (SSA)
___________________________________________________________________
(page generated 2025-10-22 23:00 UTC)