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

81–90 of 106 posts

Re: Why SSA?

#81

Post by fooker »

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 not about hiding states.

It's about naming intermediate states so you can refer to them in some way.

Re: Why SSA?

#82

Post by fooker »

antonvs wrote: post #29
achierius wrote: post #16

Earlier quoted context omitted.

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: Haskel…

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

The major issue is that approximately one person in the world understands it well enough to make it work in practice, and that kind of tech debt can't really be pushed too far.

Re: Why SSA?

#83

Post by anonymousDan »

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

As someone who knows a bit about SSA, what do you make of LLVM's design decision not to use SSA for memory but only registers (i.e. it doesn't have memory SSA)? It has always confused me a bit as to why this was done.

Re: Why SSA?

#84

Post by fooker »

pizlonator wrote: post #70
JonChesterfield wrote: post #57

Earlier quoted context omitted.

Phi/Upsilon is even more obviously equivalent to blocks with parameters than phi nodes were. It's storing to a "shadow variable" that you "load from" in the phi, i.e. it's exactly the same "store to ABI specified location in caller, load from it in callee" as a function call.

> Phi/Upsilon is even more obviously equivalent to blocks with parameters than phi nodes were Then you don't understand Phi/Upsilon

It does seem to rhyme with how function calls work under the hood.

When people say equivalent, it is usually not in the mathematical sense, which would be meaningless here because all forms are turing complete anyway.

Take equivalent as--similarity that helps you understand A given you know B, and perhaps some of the wisdom from B translates to A.

Re: Why SSA?

#85

Post by pizlonator »

fooker wrote: post #84
pizlonator wrote: post #70

Earlier quoted context omitted.

> Phi/Upsilon is even more obviously equivalent to blocks with parameters than phi nodes were Then you don't understand Phi/Upsilon

It does seem to rhyme with how function calls work under the hood. When people say equivalent, it is usually not in the mathematical sense, which would be meaningless here because all forms are turing complete anyway. Take equivalent as--similarity that helps you understand A given you know B, and perhaps some of the wisdom from B translates to A.

> It does seem to rhyme with how function calls work under the hood.

You're just overindexing on the fact that block "arguments" are called "arguments". In SSA with block arguments, you can pass data to a block without passing it as an argument. The arguments are just a way of expressing Phis.

And in Phi/Upsilon, this is valid:

    MyBlock:
        X = Whatever(...)
        Upsilon(X, ^Y)
        Y = Phi()
Note how I'm using an upsilon to set the shadow variable of a Phi that's in the same block. You can't do that with block arguments.

These things just aren't the same at all. Saying that they are the same just shows that you don't get it.

> When people say equivalent, it is usually not in the mathematical sense, which would be meaningless here because all forms are turing complete anyway.

But they're not equivalent even in a mathematical sense.

> Take equivalent as--similarity that helps you understand A given you know B, and perhaps some of the wisdom from B translates to A.

If you want to understand these things, then focus on how they are so very different rather than brain damaging yourself into thinking they are similar

Re: Why SSA?

#86

Post by pizlonator »

titzer wrote: post #75
antonvs wrote: post #73

Earlier quoted context omitted.

I've never actually looked at that compiler, so can't comment on it, but have you read Appel's "Compiling with Continuations"? It motivates and explains the process very clearly. Add ANF into the mix and it's a very straightforward, well-defined system - much more so than SSA.

The author of that compiler used that book as a reference in developing it; that book was open on his desk daily. It had an immutable IR and literally every one of the dozens of passes made basically an entire copy of it. Needless to say, that was slow and memory hungry. It was difficult to follow the transformation passes unless well-versed in CPS. We replaced that with a clone of the C1 compiler, C1X, which was bas…

> It had an immutable IR and literally every one of the dozens of passes made basically an entire copy of it.

Yeah, this is what CPS is really all about. It's not like SSA at all.

Also, it's just a dumb way to write a compiler, and so nobody does that to themselves anymore, now that SSA is widely known.

The goofy "hot" takes about how CPS and SSA are the same are usually written by CPS apologists who want to make the rest of us believe that their work on CPS is somehow relevant when it really isn't

Re: Why SSA?

#87

Post by pubby »

titzer wrote: post #45
pubby wrote: post #18

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…

While iterating optimizations is nice, I think you missed the main point of SSA. SSA makes dataflow between operations explicit; it completely eliminates the original (incidental) names from programs. Because of that, all dataflow problems (particularly forward dataflow problems) get vastly simpler. With SSA you can throw basically all forward dataflow problems (particularly with monotonic transformations) into a sin…

You're very correct but I suppose I was really answering why compilers centralize around SSA. It's a bold choice to choose one data structure for everything, and that requires more motivation than, "it makes certain optimizations really easy". Because again, it makes other stuff harder.

>And going further with the sea-of-nodes representation just makes them all more powerful; I really do recommend reading Cliff Click's thesis.

We might have to agree to disagree on this one. I actually found sea of nodes to be a boneheaded idea. It makes one or two optimizations a little more elegant but everything else a huge pain in the ass. At least, that was my experience.

Re: Why SSA?

#88

Post by zozbot234 »

pizlonator wrote: post #85
fooker wrote: post #84

Earlier quoted context omitted.

It does seem to rhyme with how function calls work under the hood. When people say equivalent, it is usually not in the mathematical sense, which would be meaningless here because all forms are turing complete anyway. Take equivalent as--similarity that helps you understand A given you know B, and perhaps some of the wisdom from B translates to A.

> It does seem to rhyme with how function calls work under the hood. You're just overindexing on the fact that block "arguments" are called "arguments". In SSA with block arguments, you can pass data to a block without passing it as an argument. The arguments are just a way of expressing Phis. And in Phi/Upsilon, this is valid: MyBlock: X = Whatever(...) Upsilon(X, ^Y) Y = Phi() Note how I'm using an upsilon to set t…

> You're just overindexing on the fact that block "arguments" are called "arguments"

But that's what it is. Briefly stated, your "upsilon" is just picking the 'actual' argument for the 'formal' parameter in a matching "phi". That's exactly what a function call does, and this holds even though you've intentionally decoupled the "upsilon" and "phi" nodes from any control-flow "jump" construct.

> Note how I'm using an upsilon to set the shadow variable of a Phi that's in the same block. You can't do that with block arguments.

Classically, the phi node would sit at the top of a block anyway, and this arrangement helps significantly in computing dominator set properties, renaming and use-def chains etc. etc. Giving up that property makes everything more awkward, including proofs of correctness for transformations, minimality, etc.

Re: Why SSA?

#89

Post by cestith »

penguin_booze wrote: post #50
jhallenworld wrote: post #6

Earlier quoted context omitted.

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

This only contains the first 3 chapters.

Google says there’s no eBook available, for what that’s worth.

https://books.google.com/books/about/Building_an_Optimizing_...

Yet Amazon says it’s on Kindle. https://www.amazon.com/Building-Optimizing-Compiler-Bob-Morg...

Re: Why SSA?

#90

Post by mananaysiempre »

pbiggar wrote: post #68
mananaysiempre wrote: post #23

Earlier quoted context omitted.

I’ve found the SSA book to be... unforgiving in its difficulty. Not in the sense that I thought it to be a bad book but rather in that I was getting the feeling that a dilettante in compilers like me wasn’t the target audience.

I was involved in making the book. It is very much a book for academics, and came out of an academic conference bringing together people working at the forefront of SSA-based research.

I mean, once again, I’m not really complaining about the book. It’s fairly mathy, sure, but so what. I also actually welcome that it’s a coherent book rather than a bunch of papers in a trenchcoat or a menagerie of neat things people have thought of (*cough* Paxos variants).

It’s rather that it’s a bit unusual in that it’s a coherent book whose prerequisites (on top of an old-timey compilers course, say) I don’t think actually exist in book form (I’d love to be proven wrong, as that’s likely what I need to read). The introductory part does make it self-contained in a sense, but it’s more like those grad-level maths books that include a definitions chapter or three: technically you don’t need to know any of that stuff beforehand, true, but in reality if it does more for you than just fill a few gaps and fix terminology, then you’re not going to have a good time with the rest. Again, just my experience, I don’t know if that’s what you were going for.

If there was a criticism implied in my initial comment, it’s that I think that the kind of person that goes looking for literature recommendations in this thread isn’t going to have a good time with it, either; so at the very least they should know what they’re signing up for. But I don’t think you’re really disagreeing with that part?..

Post reply on HN