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

101–106 of 106 posts

Re: Why SSA?

#101

Post by titzer »

pubby wrote: post #87
titzer wrote: post #45

Earlier quoted context omitted.

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…

A huge benefit of the sea of nodes representation, at least how I envisioned it and we implemented in the early days of TurboFan, is that branch folding, load elimination, and all of the other forward dataflow analyses that do monotonic reductions can be combined into a single pass that operates on the IR in the optimal order and can iterate to a fix point efficiently.

Re: Why SSA?

#102

Post by torginus »

LegionMammal978 wrote: post #66
JonChesterfield wrote: post #65

Earlier quoted context omitted.

That "tail recursion" is a thing in it's own right is more a sign of people getting their implementation wrong than anything else. Specifically, if calling a function at the end of your current function _doesn't_ clean up the call stack first, what you've got is a space leak. That C's ABI on various architectures gives you this behaviour is a bad thing. The space leak sucks there too. You get functions with a tailcal…

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…

I am dense but don't see the issue. I would assume that functions being called with pointers to the stack of the currently executing function would be ineligible for tail recursion.

Re: Why SSA?

#103

Post by torginus »

hunterpayne wrote: post #95
toast0 wrote: post #19

Earlier quoted context omitted.

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

I think functional just means that there's no undefined behavior. SSA shows that you can compile a procedural language to mostly functional constructs, and functional languages likewise have introduced things like mutation, where you can write to variables as if they were mutable and the compiler figures it out for you.

On the issue of copy-to-modify, if you can prove the old copy will never be used after you modify it, it's perfectly safe to implement it as an in place modification.

How do you prove/enforce this? With tracking ownership+lifetimes, like Rust does. In fact I'd argue that this makes Rust a functional language (no UD), and Rust isn't slow.

Re: Why SSA?

#104

Post by DannyBee »

jcranmer wrote: post #33
DannyBee wrote: post #31

Earlier quoted context omitted.

The motivation and reason it works is also wrong anyway. Like i get it's a gentle intro, but i think there are ways to accomplish that without being egregiously history rewriting ;) Ken zadeck was my office mate for years, so this is my recollection, but it's also been a few decades, so sorry for any errors :) The reason of why it works is definitely wrong - they weren't even using rewriting forms of SSA, and didn't…

I'm extremely uncertain of my history here, but my recollection is that SSA wasn't seen as practical until the development of the dominance frontier algorithm for inserting phi nodes, which seems to be 1991.

Yes - ironically, this was actually the serendipitous part - wegman and zadeck were walking and saw cytron working on a whiteboard at the end of the hall (at watson research, all the halls had open whiteboard areas at the end of each hall), and realized he had solved/or was working on the same problem they were having.

Re: Why SSA?

#105

Post by hunterpayne »

torginus wrote: post #103
hunterpayne wrote: post #95

Earlier quoted context omitted.

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

I think functional just means that there's no undefined behavior. SSA shows that you can compile a procedural language to mostly functional constructs, and functional languages likewise have introduced things like mutation, where you can write to variables as if they were mutable and the compiler figures it out for you. On the issue of copy-to-modify, if you can prove the old copy will never be used after you modify…

Nit...Functional means there are no side effects. Side effects are defined, they just aren't easy to reason about.

I do want to point out the expected result of almost every single program an app dev has ever been paid to do is entirely defined as a collection of side effects. For example all I/O is a side effect. I know people have crammed I/O into frameworks and defined them as pure, but that's mostly handwaving.

Post reply on HN