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

91–100 of 106 posts

Re: Why SSA?

#91

Post by vidarh »

anonymousDan wrote: post #83
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

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.

I don't really follow LLVM. I find it too big and convoluted for the stuff I'm doing.

Re: Why SSA?

#92

Post by pbiggar »

mananaysiempre wrote: post #90
pbiggar wrote: post #68

Earlier quoted context omitted.

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 thin…

Oh for sure, I was agreeing with you. The target audience is academics.

For non-experts, I love "Engineering a Compiler" by Cooper and Torczon.

Re: Why SSA?

#93

Post by pizlonator »

zozbot234 wrote: post #88
pizlonator wrote: post #85

Earlier quoted context omitted.

> 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 u…

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

By that argument, every store instruction is an "argument". And basic block arguments and lambda calculus are equivalent to people storing and loading to memory willy nilly.

As I said before, these equivalence claims are so nonsensical because if you take the arguments to their limits, you end up with all languages being equivalent to one another

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

All of those things that Phi-at-top-of-blocks works with also work in the Phi/Upsilon world

Re: Why SSA?

#94

Post by LegionMammal978 »

JonChesterfield wrote: post #67
LegionMammal978 wrote: post #66

Earlier quoted context omitted.

If you want automatic implicit tail calls for literally everything, then you need a solution for { FooObject foo = FooObject(123); return foo.bar(); } ending up in a UAF when FooObject::bar() tries accessing the receiver "this". Or any other case of the tail function accessing a pointer to something the caller has put on the stack. Short of some kind of crazy dependency tracking (or shoving stuff onto the heap and us…

Good example. It's a little clearer if desugared: { FooObject foo = FooObject(123); return FooObject::bar(&foo); } The foo object needs to be somewhere that the address of it means something, because C++ passes 'this' by pointer. The answer to this is to look at the current stack frame, shuffle everything that needs to stay alive to one end of it, move the stack pointer to deallocate the rest and then jump to bar, wh…

> where bar is now responsible for deallocating N bytes of stack before it continues onwards.

That doesn't really seem feasible in general? For a function with pointer parameters, the compiler would need to generate a new version for every possible stack offset left by its callers. And this could be indefinitely large, if, e.g., the caller builds a linked list on the stack before passing it to a function, or if the escape analysis fails to prove that some stack pointers are no longer in use.

Also, in C++/Rust/etc., the stack objects can also have destructors that must run, and so the callee must remember which destructors it needs to run before deallocating those objects and returning. One generic way to do this would be to also pass an address to a shim that calls the destructors in the correct order, but at that point you've literally just reinvented return addresses.

In general, it can make sense for a compiler to shrinkwrap the stack to an extent, and to automatically use tail calls when it can prove it makes no difference, but ultimately you're going to have to make the programmer do it one way or another. And if you're going to make the programmer manually track the lifetimes differently than they would for any other function call, it's much clearer to have an explicit tail call indication.

Re: Why SSA?

#95

Post by hunterpayne »

toast0 wrote: post #19
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.

1) You are just pretending globals don't exist. Some problems are best modeled with global variables. Many are not, but when you need a global, you need a global. Forcing people to copy globals around because you won't admit this doesn't really help.

2) The main bottleneck in the vast majority of code is memory accesses (also called memory pressure). This is why most optimizing compilers don't really change the overall speed of code much these days. You are optimizing the wrong thing and in the process increasing the memory pressure. You can either as a field keep ignoring this 25 years after hardware changed to make memory accesses the bottleneck, or you can keep making fad languages that fewer and fewer people use. The second choice has the added cost of degrading how most devs view CS in general.

PS The reason compiler writers like FP is because its a good way to write a compiler. This isn't true of almost anything else in software outside of the classroom.

PPS I say this as someone currently writing a compiler in an FP language (for a unique use but its still a compiler)

Re: Why SSA?

#96

Post by hunterpayne »

dominicrose wrote: post #79
mrkeen wrote: post #52

Earlier quoted context omitted.

> we’ve decided mutation is evil The functional programmers have decided mutability is evil. The imperative programmers have not. We functional programmers do crazy stuff and pretend we're not on real hardware - a new variable instead of mutating (how wasteful!) and infinite registers (what real-world machine supports that!?). Anyway, there's plenty of room for alternatives to SSA/CPS/ANF. It's always possible to com…

Functional programming is actually good for performance. Clojure uses "Persistent data structure", which has its own Wikipedia page. You can have a very complex object, like a long and wide JSON with several levels of indentation. If you want to modify a tiny part of this object, you won't waste memory or time. The object won't be copied entirely. The parts that haven't changed will be reused. This is only possible b…

> Functional programming is actually good for performance.

No, no it is not. I really wish people would stop repeating this lie. The main bottleneck in high performance code is (almost always) memory pressure. FP increases memory pressure as does immutability. No amount of clever CPU instruction optimization will ever overcome this. Compiler writers think this is the case because FP code is much easier to optimize (and compilers are easier to write in FP). What they don't seem to understand is that they are optimizing the wrong thing (instruction count instead of memory access count).

If I was wrong about this, nobody would ever use Python (an interpreted language) in production because it would be many times slower. Its only 50% slower because memory is the bottleneck, not how many subtle optimizations the compiler can find.

PS Nobody should ever use an interpreted language in prod, but the real reason is security and it should be performance too.

Re: Why SSA?

#97

Post by antonvs »

pizlonator wrote: post #86
titzer wrote: post #75

Earlier quoted context omitted.

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…

As I pointed out in another comment, the equivalence is really just about the fact that SSA, CPS, and ANF all name each intermediate value once and avoid mutation. The rest is implementation details.

That's certainly true of "every one of the dozens of passes made basically an entire copy of it" - that's just a choice of how to implement it, which is an obvious choice if one is coming at it from a functional angle.

These kinds of approaches aren't always as inefficient as one might naively imagine, because there are usually tradeoffs involved - look at Haskell for example, which is capable of producing very performant code despite being largely purely functional. Often, the performance is gained because of the purely functional source code allowing for optimizations during compilation, like stream fusion and so on.

Re: Why SSA?

#98

Post by rurban »

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…

> "simplicity” of SSA only exists because we’ve decided mutation is evil

And SICP is still relevant, even more so today with concurrency problems all over. If in Intel Chips, threads with locking solutions, or multi-processing. Shared state should not exist, and functional languages did win there.

Re: Why SSA?

#99

Post by cryptonector »

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…

In particular one thing that needs to be stated is that the primary alternative to SSA is CPS (continuation passing style) transformation. The two are roughly equivalent (at least in so far as both can be used to build compilers for the same languages), but with CPS you have to do more work to avoid ending up with lots of closure allocations that are really not necessary, so SSA feels more natural. I like to think about CPS though.

Re: Why SSA?

#100

Post by cryptonector »

JonChesterfield wrote: post #58
aatd86 wrote: post #11

Earlier quoted context omitted.

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

CPS has book keeping related to nested structures whereas SSA has the dominator tree. CPS is usually higher order and SSA usually first order. As in the continuation you're passing in CPS is probably a closure with some state attached. In SSA you'd have expanded that to pass a function and some explicit state argument, making the allocation explicit. I think the big thing in favour of CPS was it came first but I coul…

> CPS has book keeping related to nested structures whereas SSA has the dominator tree.

CPS compilers have to do a lot of work to get rid of pessimization due to unnecessary closures. Inlining, contification, and lambda lifting are some of the things they have to do. IIUC SSA compilers don't have to do that, which is their main advantage (i.e., they are naturally faster).

Post reply on HN