5 ms·

New SSA Back End for the Go Compiler

59 points by rjammala 12y ago

rayiner 12y ago
If you're wondering what the heck SSA is: http://www.cs.rice.edu/~keith/512/2013/Lectures http://www.cs.rice.edu/~keith/512/2013/Lectures. Specifically this one: http://www.cs.rice.edu/~keith/512/2013/Lectures/11InfoChainsToSSA-1up.pdf http://www.cs.rice.edu/~keith/512/2013/Lectures/11InfoChains.... The folks at Rice have the most approachable material on program optimization I've come across.
- DanWaterworth 12y ago
  I found this one helpful: http://wingolog.org/archives/2011/07/12/static-single-assignment-for-functional-programmers http://wingolog.org/archives/2011/07/12/static-single-assign...
- 0xdeadbeefbabe 12y ago
  Is IR instruction representation?
  - mseepgood 12y ago
    Intermediate representation: http://en.wikipedia.org/wiki/Intermediate_language#Intermediate_representation http://en.wikipedia.org/wiki/Intermediate_language#Intermedi...
  - Hemospectrum 12y ago
    Almost: Intermediate representation. "Intermediate" because its primary purpose is communication between different phases of a compiler in a serializable form. Some compilers actually have multiple IRs for different stages; for example, GHC will first turn Haskell code into "Core," followed by STG, C--, and LLVM IR.
- __david__ 12y ago
  Also, Wikipedia has a very good article on it. Got me the basics in a clear, concise way: https://en.wikipedia.org/wiki/Static_single_assignment_form https://en.wikipedia.org/wiki/Static_single_assignment_form
- munificent 12y ago
  > The folks at Rice have the most approachable material on program optimization I've come across. What a funny bit of synchronicity. I just started reading Cooper and Torczon's "Engineering a Compiler" and, though I've just gotten started, it seems really awesome so far. They're pretty clear that the book is focused heavily on optimization and back-end, which is exactly what I was looking for.
  - rayiner 12y ago
    EaC is great. The Rice papers linked in Coopers' lectures, e.g. Simpson's thesis on value-numbering, are the basis for some of the book's original material, and are a great supplement.
pcwalton 12y ago
> Runtime information.[n] The runtime needs accurate maps of stack frames for both GC and stack copying, something that is not available from standard backends today. This is now incorrect as far as LLVM is concerned. LLVM has experimental support for late safepoint placement (contributed by Azul), which allows copying GC and relocating stacks: http://llvm.org/docs/Statepoints.html http://llvm.org/docs/Statepoints.html
- jevinskie 12y ago
  llgo is already a thing: https://github.com/go-llvm/llgo https://github.com/go-llvm/llgo
riobard 12y ago
OT: every time a popular Google doc is shared I see this banner at the top saying that "Wow, this file is really popular! Some tools might be unavailable until the crowd clears." with the option to try again or dismiss the message. I'm wondering what tools I am missing given that this is basically a read-only view?
- rictic 12y ago
  Google docs urls that end in /edit will try and figure out what rights you have to the document and give you tools corresponding to those rights (to edit the doc, to share it, to add comments, to add suggestions, etc). Google docs that end in /preview just show the read-only view. When a doc becomes super popular, sometimes /edit will redirect to /preview.
cornewut 12y ago
I'm sorry, I misread it as "New NSA backdoor".
torrance 12y ago
"A common question that comes up is “why not just convert to the IR of {llvm,gcc,...} and go from there?” [...] 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." Wouldn't this be worthwhile just to be able to use some of the LLVM tools (debuggers, performance analysers, etv.) alone? Not to mention optionally being able to compile with more expensive optimisations.
- jsd1982 12y ago
  LLVM and its tools are implemented in C++. The Go team just underwent a large effort to remove their dependency on C code. A reasonable assertion can be made that given this C code removal, a large and complex C++ dependency like LLVM is unlikely to be in their sights for inclusion into the compiler. Perhaps this wouldn't be an /entirely/ unreasonable to do; I can imagine a `cgo` binding to LLVM existing for this purpose. Speaking of which, I wonder what the fate of `cgo` is with this compiler code migration from C to Go.
  - andrewchambers 12y ago
    LLVM already has official go bindings in the main repo, also, the llgo go compiler uses these bindings. Unfortunately building it all was a pain for me, and the resulting binary was 80 megs which seemed a bit ridiculous (Go had to statically link all of llvm into one monolith).
- deleted 12y ago
  [deleted]
- andrewchambers 12y ago
  Llvm takes longer to clone in git than downloading and building the entire go tool chain from scratch. A full build with llvm plus clang takes 30 minutes or so on my pc. A full go build takes 10 seconds. The go team is small and fast. Taking on that kind of baggage is unnecessary.
nulltype 12y ago
Is a 10% speedup optimistic? I find it odd that the hand-optimized assembly prototype had no detectable speed difference.

59 points by rjammala 12y ago

If you're wondering what the heck SSA is: http://www.cs.rice.edu/~keith/512/2013/Lectures http://www.cs.rice.edu/~keith/512/2013/Lectures. Specifically this one: http://www.cs.rice.edu/~keith/512/2013/Lectures/11InfoChainsToSSA-1up.pdf http://www.cs.rice.edu/~keith/512/2013/Lectures/11InfoChains.... The folks at Rice have the most approachable material on program optimization I've come across.

DanWaterworth 12y ago
I found this one helpful: http://wingolog.org/archives/2011/07/12/static-single-assignment-for-functional-programmers http://wingolog.org/archives/2011/07/12/static-single-assign...
0xdeadbeefbabe 12y ago
Is IR instruction representation?
- mseepgood 12y ago
  Intermediate representation: http://en.wikipedia.org/wiki/Intermediate_language#Intermediate_representation http://en.wikipedia.org/wiki/Intermediate_language#Intermedi...
- Hemospectrum 12y ago
  Almost: Intermediate representation. "Intermediate" because its primary purpose is communication between different phases of a compiler in a serializable form. Some compilers actually have multiple IRs for different stages; for example, GHC will first turn Haskell code into "Core," followed by STG, C--, and LLVM IR.
__david__ 12y ago
Also, Wikipedia has a very good article on it. Got me the basics in a clear, concise way: https://en.wikipedia.org/wiki/Static_single_assignment_form https://en.wikipedia.org/wiki/Static_single_assignment_form
munificent 12y ago
> The folks at Rice have the most approachable material on program optimization I've come across. What a funny bit of synchronicity. I just started reading Cooper and Torczon's "Engineering a Compiler" and, though I've just gotten started, it seems really awesome so far. They're pretty clear that the book is focused heavily on optimization and back-end, which is exactly what I was looking for.
- rayiner 12y ago
  EaC is great. The Rice papers linked in Coopers' lectures, e.g. Simpson's thesis on value-numbering, are the basis for some of the book's original material, and are a great supplement.

pcwalton 12y ago

> Runtime information.[n] The runtime needs accurate maps of stack frames for both GC and stack copying, something that is not available from standard backends today. This is now incorrect as far as LLVM is concerned. LLVM has experimental support for late safepoint placement (contributed by Azul), which allows copying GC and relocating stacks: http://llvm.org/docs/Statepoints.html http://llvm.org/docs/Statepoints.html

jevinskie 12y ago
llgo is already a thing: https://github.com/go-llvm/llgo https://github.com/go-llvm/llgo

riobard 12y ago

OT: every time a popular Google doc is shared I see this banner at the top saying that "Wow, this file is really popular! Some tools might be unavailable until the crowd clears." with the option to try again or dismiss the message. I'm wondering what tools I am missing given that this is basically a read-only view?

rictic 12y ago
Google docs urls that end in /edit will try and figure out what rights you have to the document and give you tools corresponding to those rights (to edit the doc, to share it, to add comments, to add suggestions, etc). Google docs that end in /preview just show the read-only view. When a doc becomes super popular, sometimes /edit will redirect to /preview.

cornewut 12y ago

I'm sorry, I misread it as "New NSA backdoor".

torrance 12y ago

"A common question that comes up is “why not just convert to the IR of {llvm,gcc,...} and go from there?” [...] 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." Wouldn't this be worthwhile just to be able to use some of the LLVM tools (debuggers, performance analysers, etv.) alone? Not to mention optionally being able to compile with more expensive optimisations.

jsd1982 12y ago
LLVM and its tools are implemented in C++. The Go team just underwent a large effort to remove their dependency on C code. A reasonable assertion can be made that given this C code removal, a large and complex C++ dependency like LLVM is unlikely to be in their sights for inclusion into the compiler. Perhaps this wouldn't be an /entirely/ unreasonable to do; I can imagine a `cgo` binding to LLVM existing for this purpose. Speaking of which, I wonder what the fate of `cgo` is with this compiler code migration from C to Go.
- andrewchambers 12y ago
  LLVM already has official go bindings in the main repo, also, the llgo go compiler uses these bindings. Unfortunately building it all was a pain for me, and the resulting binary was 80 megs which seemed a bit ridiculous (Go had to statically link all of llvm into one monolith).
deleted 12y ago
[deleted]
andrewchambers 12y ago
Llvm takes longer to clone in git than downloading and building the entire go tool chain from scratch. A full build with llvm plus clang takes 30 minutes or so on my pc. A full go build takes 10 seconds. The go team is small and fast. Taking on that kind of baggage is unnecessary.

nulltype 12y ago

Is a 10% speedup optimistic? I find it odd that the hand-optimized assembly prototype had no detectable speed difference.