New SSA Back End for the Go Compiler (2015)

https://docs.google.com/document/d/1szwabPJJc4J-igUZU4ZKprOrNRNJug2JPD8OYi3i1K0/edit

by gjvc • 10 years ago

78 97 10 years ago

docs.google.com

dantillberg2• 10 years ago

Previous discussion: https://news.ycombinator.com/item?id=9099744

jheriko4• 10 years ago

i do wonder why they didn't go with llvm...

dantillberg2• 10 years ago

Russ Cox shared his thoughts on this a while back: https://news.ycombinator.com/item?id=8817990

tomp• 10 years ago

It's answered in the post:

A common question that comes up is “why not just convert to the IR of {llvm,gcc,...} and go from there?” I think there are 3 major reasons:

- Compiler speed. I intend our SSA IR, and the optimizer passes implemented on top of that IR, to be fast by design. We’ll aim for linear-time algorithms wherever possible. The backends of other possible compilers weren’t really designed with fast compile speed in mind.

- Runtime information. The runtime needs accurate maps of stack frames for both GC and stack copying, something that is not available from standard backends today.

- An additional dependence. Do we want a {llvm,gcc,...} backend as a prerequisite for building Go? (Note that this would only be an issue for those developing Go, not those writing Go programs.)

I’m happy to be convinced otherwise - maybe we should throw our effort into getting frame maps out of {llvm,gcc,...} and figuring out how to configure the backend (e.g. which optimizations to turn on) to make it compile quickly.

DannyBee6• 10 years ago

Note, for the record, none of these are correct except for the last one:

1. LLVM's SSA based compiler currently uses more linear time algorithms than Go's SSA backend (IE phi placement, etc), and in more places. So yeah. While parts of LLVM definitely could be sped up (particularly the backend), it was originally designed with fast compile speed in mind, just like go! Given how many years it's taken so far, you easily could have gotten the same thing out of LLVM. Would it have been more work? Probably, but not much. Are the other reasons not to do it? Yes. But the idea that their compiler is somehow the only one designed with fast compile time in mind is, honestly, pretty arrogant

2. Stack maps have been supported for quite a while, and statepoint support now exists and is used by real people in real places.

But i'll also just point out he's never actually asked, or talked to the LLVM folks about it (search the mailing list, see if you can find any mail about it).

Note: I honestly don't care whether they write their own compiler or not. I suspect it's better for them to do it because of the community they want to build, because of how much control they want over their toolchain, etc.

But i'm not a fan of saying "someone else's infrastructure sucks, so we are doing it", when

1. That's not the real reason as far as i can tell

2. People are using, in production, the very things they claim don't exist (and they've been told this, it turns out)

3. Answers about linear time algorithms are honestly just BS.

naasking• 10 years ago

- Runtime information. The runtime needs accurate maps of stack frames for both GC and stack copying, something that is not available from standard backends today.

DannyBee addressed most of these points, however I just wanted to note that even if LLVM didn't provide stack maps, it's easy to recover stack information using lazy pointer stacks [1]

[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.158....

jheriko4• 10 years ago

sorry i missed your reply at the time, but DannyBee's comment is very close to what i would have said in response thankfully. :)

wund• 10 years ago

Just as an experiment I cleaned up the runtime function mapaccess1_fast64 by hand in assembly and made it 29% smaller and with a speed improvement too small to measure.

This doesn't sound very exciting.

charlieegan3• 10 years ago

I was wondering what SSA meant, I think I'm right in saying this is the correct wikipedia page: https://en.wikipedia.org/wiki/Static_single_assignment_form

DanWaterworth• 10 years ago

Yes. SSA intermediate representations are now common in compilers. Many will have been exposed to SSA via LLVM.

willtim8• 10 years ago

I find it somewhat ironic that most mainstream compilers now transform imperative code into a functional language in order to reason about the code.

richardwhiuk• 10 years ago

It's not a functional language...

willtim8• 10 years ago

There is no rigorous definition of functional programming. But SSA is trying to achieve similar goals. Google the paper "SSA is functional programming" by Andrew Appel if you want to know more.

profquail2• 10 years ago

I wonder if it'd make more sense for the go compiler developers to use ANF (A-normal form [0]) instead of SSA? ANF is less well-known outside of language research but seems like it'd be a better fit given the design of golang.

[0] https://en.wikipedia.org/wiki/A-normal_form

tonfa• 10 years ago

Doesn't seem easy to translate to it from an imperative language, the wiki page says it's used in functional compilers. Are there examples of ANF used for imperative languages?

SSA is fairly well studied, there are many algorithms to transform an IR into SSA and also lots of algorithms for optimizing programs in SSA form.

Joof2• 10 years ago

SSA is extremely well studied and algorithms for it are fast.

Joof2• 10 years ago

Its not that ironic. SSA has the property that it's interference graphs are chordal and thus can be colored (an NP problem) in polynomial time. Aka, we can do optimal register allocation really fast. Among other benefits.

It doesn't matter how it's structured, just that it's faster.

willtim8• 10 years ago

That's just one advantage of many. Without SSA, you can't even constant fold without doing dataflow analysis. So I would say the structure is very important, that's why everyone is using it now.

geodel6• 10 years ago

Well many functional programing languages have compilers/VM written in C/C++. So it is not ironic but simply use what works for now.

willtim8• 10 years ago

C/C++ is not a good choice for writing a compiler. I do not know of any modern functional language compiler that is written in C/C++. But what does this have to do with SSA?

catnaroek3• 10 years ago

What is typically implemented in C and C++ is runtime systems, not compilers.

chubot2• 10 years ago

And then your CPU does it again! After all that work, your compiler outputs a totally ordered stream of instructions; then the CPU tries to figure out data dependencies in hardware and execute instructions out of order and in parallel.

It seems as though C-like imperative languages and x86 are baked in forever... but the world is actually parallel.

willtim8• 10 years ago

Excellent point!

marssaxman2• 10 years ago

I've recently been thinking that we are looking at a situation analogous to the one Ben Franklin was in when he identified the two types of electrical charge as "positive" or "negative" pressure in the "electrical fluid" - he took a guess, which happened to be wrong, and ever since we have been stuck describing a surplus of electrons as "negative" and a deficit as "positive". This is no obstacle for the experienced but will remain an eternal hangup for beginners.

By analogy, of course, I am suggesting that the Church model of computation might have served us better as a foundation than the Turing model has done, since it seems that everything's turning up lambdas as the technology S-curve for silicon computers continues to flatten out.

trsohmers5• 10 years ago

Unless you have a VLIW based architecture and the compiler takes care of the dependencies and hazard checking in software... then you are able to have dramatically simpler hardware (reducing area and power), along with faster performance!

Wait another month and a half and I'll be getting around to writing my blog post in support of VLIW, and why previous attempts have failed miserably.

nickpsecurity8• 10 years ago

And then the CPU itself is a bunch of wires running in parallel with careful synchronization to pretend to be a serial or barely parallel (multicore) machine. ;)

munificent• 10 years ago

I wouldn't describe SSA as "a functional language". It was originally designed as an IR for imperative languages, not functional ones. (The functional folks prefer CPS, which really is a functional language.)

I think one could read too much into the "single-assignment" part of SSA. Sure, functional languages don't tend to rebind variables either, but that's really all SSA has in common with them.

I'm familiar with Appel's "SSA is a functional language" article, but the vibe I got was more than he was trying to build some bridges between the SSA and CPS camps to try to get some cross-pollination going and knowldge sharing between them.

I think he could have just as easily called it "CPS is an imperative language", but my hunch is the FP folks are more persnickety and wouldn't have swallowed that as easily as imperative folks would accept the other title.

willtim8• 10 years ago

Like Appel, I wasn't entirely serious about it being a "functional language", but I think the point still stands, it is a major step towards a more mathematical program representation ("variables" instead of "assignables"). And just like "functional programming", the primary goal is ease of reasoning.

CPS is typically used to handle imperative control structures by impure functional programming languages, so it should indeed be of interest to imperative compiler authors.

willtim8• 10 years ago

The paper "A Correspondence between Continuation Passing Style and Static Single Assignment" by Kelsey, suggests SSA has a lot more in common with functional programming than you seem to believe it has.

sievebrain5• 10 years ago

Why was the Go compiler not based on SSA form originally? Isn't that kind of an embarrassment? All industrial compilers I'm aware of completed their transition to SSA ~15 years ago ... it seems bizarre that a compiler for a language started in 2009 wouldn't have been that way from the start.

steveklabnik• 10 years ago

Alternative viewpoint: go has also accomplished a lot of its goals for years without needing this. It could reasonably be viewed as a premature optimization.

sievebrain5• 10 years ago

It's a pretty big architectural change to any compiler, and when all other major compilers have paid that refactoring cost, it's very strange to want to go through the transition pain instead of just doing SSA up front like LLVM did.

kjksf• 10 years ago

Original Go compiler was based on plan 9 C compiler (http://plan9.bell-labs.com/sys/doc/compiler.html) because Ken Thompson and Rob Pike (co)designed and (co)implemented those compilers and they were 2 out of 3 original Go designers/implementers.

Those compilers are at least 16 years old so Pike and Thompson aren't as incompetent as you think them to be.

sievebrain5• 10 years ago

That just changes the question to why did they base their compiler on an obscure 16 year old codebase? I can guess that the answer is familiarity, but, that doesn't change the negative impact of a low tech compiler on the user base.

New SSA Back End for the Go Compiler (2015)

Related Stories