12 ms·

New SSA Back End for the Go Compiler (2015)

78 points by gjvc 11y ago

dantillberg 11y ago
Previous discussion: https://news.ycombinator.com/item?id=9099744 https://news.ycombinator.com/item?id=9099744
jheriko 11y ago
i do wonder why they didn't go with llvm...
- dantillberg 11y ago
  Russ Cox shared his thoughts on this a while back: https://news.ycombinator.com/item?id=8817990 https://news.ycombinator.com/item?id=8817990
- tomp 11y 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.
  - DannyBee 11y 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.
    - danieldk 11y ago
      Agreed. Though another argument in favor was not cited: the SSA backend is in Go, so that means that anyone who knows Go can also hack on the SSA backend. With LLVM, they would have to know Go's internals and C++. Of course, there is also gccgo and llgo, so once the SSA backend is in stable Go, useful comparisons can be made.
      - disposeofnick9 11y ago
        Using llvm might introduce a dependency, but it also gives all the LLVM advantages/disadvantages across platforms for "free" (some work, fewer reinvented wheels) and more toolchain utilities.
      - jheriko 11y ago
        i think that this is a gimmick rather than a reason. languages that have their own tools built with themselves are cool... but it has zero practical value imo. the number of C/C++ programmers interested in Go and capable of contributing meaningfully far outweighs the number of programmers who do not know C/C++ and are interested in Go
  - naasking 11y 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.9799 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.158....
  - jheriko 11y 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 11y 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 11y 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 https://en.wikipedia.org/wiki/Static_single_assignment_form
- DanWaterworth 11y ago
  Yes. SSA intermediate representations are now common in compilers. Many will have been exposed to SSA via LLVM.
willtim 11y 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 11y ago
  It's not a functional language...
  - willtim 11y 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.
- profquail 11y 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 https://en.wikipedia.org/wiki/A-normal_form
  - tonfa 11y 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.
    - willtim 11y ago
      This paper discusses going from SSA to ANF: http://tinyurl.com/j25xy5t http://tinyurl.com/j25xy5t
    - profquail 11y ago
      ANF is mostly used in functional compilers, but there are plenty of functional languages which aren't purely functional (e.g., Scheme, SML, OCaml) -- which is why I'm wondering if it could be adapted for a more imperative language like go.
sievebrain 11y 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 11y 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.
  - sievebrain 11y 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 11y ago
  Original Go compiler was based on plan 9 C compiler (http://plan9.bell-labs.com/sys/doc/compiler.html 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.
  - sievebrain 11y 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.

78 points by gjvc 11y ago

dantillberg 11y ago

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

jheriko 11y ago

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

dantillberg 11y ago
Russ Cox shared his thoughts on this a while back: https://news.ycombinator.com/item?id=8817990 https://news.ycombinator.com/item?id=8817990
tomp 11y 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.
- DannyBee 11y 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.
  - danieldk 11y ago
    Agreed. Though another argument in favor was not cited: the SSA backend is in Go, so that means that anyone who knows Go can also hack on the SSA backend. With LLVM, they would have to know Go's internals and C++. Of course, there is also gccgo and llgo, so once the SSA backend is in stable Go, useful comparisons can be made.
    - disposeofnick9 11y ago
      Using llvm might introduce a dependency, but it also gives all the LLVM advantages/disadvantages across platforms for "free" (some work, fewer reinvented wheels) and more toolchain utilities.
    - jheriko 11y ago
      i think that this is a gimmick rather than a reason. languages that have their own tools built with themselves are cool... but it has zero practical value imo. the number of C/C++ programmers interested in Go and capable of contributing meaningfully far outweighs the number of programmers who do not know C/C++ and are interested in Go
- naasking 11y 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.9799 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.158....
- jheriko 11y 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 11y 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 11y 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 https://en.wikipedia.org/wiki/Static_single_assignment_form

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

willtim 11y 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 11y ago
It's not a functional language...
- willtim 11y 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.
profquail 11y 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 https://en.wikipedia.org/wiki/A-normal_form
- tonfa 11y 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.
  - willtim 11y ago
    This paper discusses going from SSA to ANF: http://tinyurl.com/j25xy5t http://tinyurl.com/j25xy5t
  - profquail 11y ago
    ANF is mostly used in functional compilers, but there are plenty of functional languages which aren't purely functional (e.g., Scheme, SML, OCaml) -- which is why I'm wondering if it could be adapted for a more imperative language like go.

sievebrain 11y 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 11y 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.
- sievebrain 11y 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 11y ago
Original Go compiler was based on plan 9 C compiler (http://plan9.bell-labs.com/sys/doc/compiler.html 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.
- sievebrain 11y 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.