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

71–80 of 106 posts

Re: Why SSA?

#71

Post by esrauch »

tylerhou wrote: post #24
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…

Here's a concise explanation of SSA. Regular (imperative) code is hard to optimize because in general statements are not pure -- if a statement has side effects, then it might not preserve the behavior to optimize that statement by, for example: 1. Removing that statement (dead code elimination) 2. Deduplicating that statement (available expressions) 3. Reordering that statement with other statements (hoisting; loop-…

> Given that the author works at an AI accelerator company

I actually believe he works at Buf.build and his resume is stale, the author previously posted about their Go Protobuf parser hyperpb which is a Buf project.

Maybe still "author recently worked at an AI accelerator company" though.

Re: Why SSA?

#72

Post by superlopuh »

Chabsff wrote: post #5
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.

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.

In MLIR, there are two representations of memory, `tensor` and `memref`, which enables you to do some high-level things[0] in SSA before "bufferizing" to memrefs, which are eventually lowered to LLVM pointers.

[0]: https://mlir.llvm.org/docs/Dialects/TensorOps/

Re: Why SSA?

#73

Post by antonvs »

titzer wrote: post #46
pizlonator wrote: post #8

Earlier quoted context omitted.

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

I've never been more confused than working on Maxine VM's CPS optimizing compiler.

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.

Re: Why SSA?

#74

Post by MeetingsBrowser »

James_K wrote: post #64
MeetingsBrowser wrote: post #43

Earlier quoted context omitted.

Why have while (c when you could have %2 = alloca i32, align 4 %3 = alloca i32, align 4 store i32 %0, ptr %3, align 4 br label %4, !dbg !18 4: %5 = load i32, ptr %3, align 4, !dbg !19 %6 = icmp slt i32 %5, 10, !dbg !20 br i1 %6, label %7, label %10, !dbg !18 7: %8 = load i32, ptr %3, align 4, !dbg !21 %9 = mul nsw i32 %8, 3, !dbg !21 store i32 %9, ptr %3, align 4, !dbg !21 br label %4, !dbg !18

The second code snippet doesn't use SSA. It just translates the first loop into IR and mangles the variable names. Here is an SSA version of that in the Scheme language. (let loop ((c c)) (if ( Notice that this is stateless and also returns the final value of “c” from the loop. People who use the below style have tended to find that it is much easier to reason about for more complicated looping structures.

I intended it to be mostly a joke. Many people equate LLVM IR with SSA.

I might even argue that easy to read and easy to reason about are opposites.

For the most part, languages like Python and Ruby can be very easy to read but difficult to understand precisely what actually happens at runtime.

Things like LLVM IR are much more explicit, making it easier to reason about but extremely difficult to read.

Maybe somewhere between is "pure" side effect free functional programs.

Re: Why SSA?

#75

Post by titzer »

antonvs wrote: post #73
titzer wrote: post #46

Earlier quoted context omitted.

I've never been more confused than working on Maxine VM's CPS optimizing compiler.

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 basically just a Java rewrite. C1X supposedly still exists in MaxineVM, but has been superceded by the Graal compiler in Truffle/Graal, which is a hybrid CFG/sea-of-nodes style compiler based on SSA.

Re: Why SSA?

#76

Post by titzer »

pizlonator wrote: post #37
zozbot234 wrote: post #25

Earlier quoted context omitted.

The whole ad-hoc mechanism of phi-nodes in SSA can be replaced by local blocks with parameters. A block that can take parameters is not that different conceptually from a lambda.

Local blocks with parameters is the gross way to do it. The right way to do it is Phi/Upsilon form. https://gist.github.com/pizlonator/cf1e72b8600b1437dda8153ea... But even if you used block arguments, it's so very different from a lambda. Lambdas allow dynamic creation of variables, while SSA doesn't. Therefore, in SSA, variables must-alias themselves, while in the lambda calculus they don't. If you think that a blo…

In CS-411 we teach both SSA and parameterized blocks, with more emphasis on SSA. IMHO the main advantage is that phis are connected to their "call" sites and argument values. Blocks aren't first class, there's no need to decouple the names of their inputs from the actual inputs. SSA makes those dataflow connections explicit, which is obviously superior.

Re: Why SSA?

#78

Post by mhh__ »

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…

Is it that we think it's evil or that it's easier to deal with while guaranteeing some SSA-like pattern in the code? It's a fairly easy thing to agree to maintain, whereas if you are more jazzy with it you can end up with either very fiddly passes or just constantly running DFA

Re: Why SSA?

#79

Post by dominicrose »

mrkeen wrote: post #52
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…

> 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 because the objects are immutable. If they were mutable, you wouldn't be able to trust that the parts that haven't changed won't change in the future. This means you can share these parts. This is good for memory and for parallelism.

If you're building a React app in JS, React has to check if the object has changed deeply. If you're doing a React app with Clojure, this check is actually disabled. React will only use a single === comparison to know wether two objects are different or not, and this is basically an integer comparison (like a memory address comparison).

Re: Why SSA?

#80

Post by UncleEntity »

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…

It's funny, I've been working on a CPS (continuation passing style) graph optimizer loosly based on Cliff Click's thesis and when I show it to the robots they're like "yeah, that's academic fluffery, it'll never fly" to try inflate my ego a bit until I explain how it actually works then they're "wait, that's actually possible ...and a good idea".

His 'optimization as a constraint solving problem' thing is actually pretty powerful and it just so happens I've been fiddling with a Projective Dynamics constraint solver (which is what the VM is for, to define the constraints) whivh I can abuse to optimize CPS graphs so... take that Robots!

Post reply on HN