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

41–50 of 106 posts

Re: Why SSA?

#41

Post by ebiederm »

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 the basic block with arguments variation there is no going in and out of SSA.

Re: Why SSA?

#42

Post by rdtsc »

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

Thank you. That’s a great explanation.

Re: Why SSA?

#43

Post by MeetingsBrowser »

mbauman wrote: post #10

Forget compilers, SSA is an immensely valuable readability improvement for humans, too.

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

Re: Why SSA?

#44

Post by tonfa »

tylerhou wrote: post #28
strbean wrote: post #7

Earlier quoted context omitted.

I learned a bit about SSA in a compiler course. Among many other things, it is crucial for register assignment. You want to know each distinct value that will exist, and the lifetimes of those values, in order to give each a register. Then, if have more distinct values existing at one time than you have registers, you have to push stuff to the stack.

It is not critical for register assignment -- in fact, SSA makes register assignment more difficult (see the swap problem; the lost copy problem). Lifetime analysis is important for register assignment, and SSA can make lifetime analysis easier, but plenty of non-SSA compilers (lower-tier JIT compilers often do not use SSA because SSA is heavyweight) are able to register allocate just fine without it.

One nice thing is that it makes register assignment polynomial (the coloring of SSA variables graph is polynomial since it's not an arbitrary graph).

Re: Why SSA?

#45

Post by titzer »

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 single pass and they all benefit each other. Without SSA, you have every single transformation tripping over itself to deal with names from the source program and introducing transformations that might confuse other analyses.

I know we teach different compiler optimizations at different stages, but it's really important to realize that all of them need to work together and that having each as a separate pass is a good way to fail at the phase ordering problem.

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

Re: Why SSA?

#46

Post by titzer »

pizlonator wrote: post #8
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.

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.

Re: Why SSA?

#47

Post by titzer »

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.

SSA isn't (primarily) concerned with memory, it's concerned with local variables. It completely virtualizes the storage of local variables--in fact, all intermediate computations. By connecting computations through dataflow edges and not storage, it removes ordering (except that induced by dependence edges) from consideration.

It is, after all, what CPUs do under the hood with register renaming! They are doing dynamic SSA, a trick they stole from us compiler people!

Re: Why SSA?

#48

Post by titzer »

PhilipRoman wrote: post #35
Chabsff wrote: post #5

Earlier quoted context omitted.

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.

If you're hell bent on functional style, you can represent memory writes as ((Address, Value, X) -> X), where X is a compile-time-only linear type representing the current memory state, which can be manipulated like any other SSA variable. It makes some things more elegant, like two reads of the same address naturally being the same value (as long as it's reading from the same memory state). Doesn't help at all with…

The sea-of-nodes representation renames memory as just another dependence edge in a somewhat analogous manner.

Re: Why SSA?

#49

Post by noelwelsh »

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.

I think you're asking if SSA is still a functional language in the presence of mutation of memory. Both Scheme and ML (of Standard ML and OCaml fame, not machine learning) allow mutation, so mutation doesn't seem to disqualify a language from being functional.

This naturally leads to the question "what is a functional language?" I've written my thoughts on what FP is at [1]. I argue that FP is about local reasoning and composition. The former is most relevant here: local reasoning means it's easy to reason about code. This is exactly why SSA is used in compiler: it makes it easy for the compiler to reason about code and therefore which optimizations are valid. This is the same argument given in these comments: https://news.ycombinator.com/item?id=45674568 and https://news.ycombinator.com/item?id=45678483

[1]: https://noelwelsh.com/posts/what-and-why-fp/

Re: Why SSA?

#50

Post by penguin_booze »

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

This only contains the first 3 chapters.
Post reply on HN