Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why SSA?

mcyoung.xyz

Post reply on HN
Print view View original

11–20 of 106 posts

Re: Why SSA?

#11

Post by aatd86 »

noelwelsh wrote: post #3

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.

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

Re: Why SSA?

#12

Post by zachixer »

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.

Re: Why SSA?

#14

Post by Rochus »

vidarh wrote: post #4
rdtsc wrote: post #2

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…

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 Mössenböck: https://share.google/QNoV9G8yMBWQJqC82

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...

Re: Why SSA?

#15

Post by vidarh »

zachixer wrote: post #12

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…

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.

Re: Why SSA?

#16

Post by achierius »

zachixer wrote: post #12

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…

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.

Re: Why SSA?

#17

Post by Rochus »

jhallenworld wrote: post #6
vidarh wrote: post #4

Earlier quoted context omitted.

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 Mössenböck: https://share.google/QNoV9G8yMBWQJqC82

Also I recommend Bob Morgan's book: https://turbo51.com/download/Building-an-Optimizing-Compile-...

Indeed a great book; I even have a paper copy.

The SSA book is also pretty good: https://web.archive.org/web/20201111210448/https://ssabook.g...

Re: Why SSA?

#18

Post by pubby »

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.

Re: Why SSA?

#19

Post by toast0 »

zachixer wrote: post #12

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…

> 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.

Post reply on HN