8 ms·

Go compiler internals: Adding a new statement to Go

234 points by soheilpro 7y ago

dawkins 7y ago
That was a fun read. Very interesting. I have noticed that the AST nodes don't have a parent reference. I wonder how it knows for example when encountering a "continue LABEL" that the code is nested maybe deeply in a loop with that label. The only way I would think of is traversing the tree up but I think there is no way of doing this. How do they do it?
- azhenley 7y ago
  I don’t know how the Go compiler works but one solution is for each scope level to have a symbol table with a reference to the parent level’s table. So you can traverse up for symbols.
- uryga 7y ago
  i recently hacked together my first simple compiler and the way i handled stuff like break/continue is that every loop pushed a "context" onto a stack, so when the compiler encounters a break/continue it just looks into the context to find the label it should jump to. could be similar
- Crinus 7y ago
  Based on [1] (where continue is handled) and [2] (the branch statement type), looks like the target is simply passed to the function. This is a recursive descent parser, so passing the target down the statement handling stack is trivial (and indeed, this is what happens for for[3]). [1] https://github.com/golang/go/blob/master/src/cmd/compile/internal/syntax/branches.go#L218 https://github.com/golang/go/blob/master/src/cmd/compile/int... ("ctx" is a "targets" struct containing two entries, one for which statement 'break' targets and another for which statement 'continue' targets). [2] https://github.com/golang/go/blob/master/src/cmd/compile/internal/syntax/nodes.go#L360 https://github.com/golang/go/blob/master/src/cmd/compile/int... [3] https://github.com/golang/go/blob/master/src/cmd/compile/internal/syntax/branches.go#L293 https://github.com/golang/go/blob/master/src/cmd/compile/int... (the targets{s, s} passed to innerBlock is then passed to blockBranches - s is the for statement node itself). As a sidenote, it is interesting how easy Go reads even though i never wrote a single line of Go myself (though i do write a lot of C and Object Pascal and the code patterns look similar).
  - dawkins 7y ago
    Now that you have pointed where it is, it really looks easy to understand how it works. Thank you!
- barrkel 7y ago
  Context from higher up the tree can easily be passed down when recursively processing, as others mention. As to why do that, there are several reasons. It's fiddly to construct trees when you need to patch the children with parent references. The most natural thing to do is create the children (usually via recursive parse) then construct the parent. If you then need to patch the children with a reference to their parent, it's more work. It also means your nodes can't be immutable (but they're often not wholly immutable anyway for other reasons, like annotating during passes that add semantic information). It's easier to reason about tree manipulations when you only have downward pointers. For example, maybe you want to rewrite a common subexpression with a reference to a temporary, and reuse one of the common trees as the RHS on the assignment to the temporary. It's more effort if you need to patch both ways on the link, rather than just grab the tree and slot it into the assignment. (It's possible that you have DAGs rather than trees, and have children with shared parents, but I think this isn't worth any extra representative or compression that it gives you because passes will want to mutate those nodes, and meeting the same nodes more than once makes invariants more complex.) Finally, more interesting traversals, following control or data flow, can cut across and jump between tree branches, so parent links don't necessarily help you there either. It helps that most languages don't have parse trees which would stress the runtime stack when processing recursively, outside of machine-generated code (and correspondingly, it's not that hard to get a stack overflow error or equivalent "too much nesting" error if you generate code targeting that failure mode).
kstenerud 7y ago
The go compiler is surprisingly easy to modify! I made a modification that allows it to issue warnings instead of errors for unused imports, variables, etc [1]. It was a fun little exercise :) [1] https://github.com/kstenerud/go https://github.com/kstenerud/go
- mavelikara 7y ago
  This is the commit in question: https://github.com/kstenerud/go/commit/334e03f12c9c94fe6adedfcbac105a4c9c19aba3 https://github.com/kstenerud/go/commit/334e03f12c9c94fe6aded.... Cool mod!
- saagarjha 7y ago
  Now if only this got merged into mailine ;)
  - dullgiulio 7y ago
    Why? The idea that warnings are errors is pretty important actually. Now, unused imports are mostly harmless (alright, they are not because of init), but they keep unrelated commits clean without needing ad-hoc linting or IDE functionality.
    - kstenerud 7y ago
      It's explained in the use case: https://github.com/kstenerud/go#use-case https://github.com/kstenerud/go#use-case Use Case The use case for warnings is the exploratory development or debugging phases, where you really don't care about leaving unused things lying around for the time being (for example, temporarily commenting something out), and would rather that the compiler just got out of your way until you've got something ready to compile normally and commit. Usage go build -gcflags=-warnunused somefile.go go test -gcflags=-warnunused When you're done with your exploratory/debugging phase, simply build or test without the flag: go build somefile.go go test Compiling without the flags will fail on unused things as normal.
      - 7y ago
eliben 7y ago
Thanks for posting this :) Part 2 is http://eli.thegreenplace.net/2019/go-compiler-internals-adding-a-new-statement-to-go-part-2/ http://eli.thegreenplace.net/2019/go-compiler-internals-addi...
person_of_color 7y ago
Why didn't they use LLVM?
- saagarjha 7y ago
  Does https://golang.org/doc/faq#What_compiler_technology_is_used_to_build_the_compilers https://golang.org/doc/faq#What_compiler_technology_is_used_... answer your question (I interpreted it as "why doesn't the Go compiler use LLVM?")?
- edflsafoiewq 7y ago
  LLVM is very slow.
  - kspp 7y ago
    It seems to be fast enough for SQL JIT-compiler in PostgreSQL 11+ and shader compilation in the *nix OpenGL stack (mesa), both of which are sort-of-realtime systems.
    - sanxiyn 7y ago
      There is an ongoing work to move Mesa away from LLVM because LLVM is slow.
    - vkazanov 7y ago
      Can't say anything about shaders but I do know a thing or two about database queries: 1. Queries are often repeated, i.e. most of backend DBs get the same requests over and over again. Even a slow jit compiler is fine here as things just get cached. 2. Queries usually take some time to complete, and this offsets the jit-related latency. Also, Postgres has a very limited kind of jit compilation, i.e. for expressions only. Notice that javascript jit compilers usually have a multi-tiered compilation. That's because proper compilation takes time, and sometimes it is more efficient to just do some basic template jiting (or no additional compilation) instead of firing the heavy guns. None of them use LLVM, btw.
      - 7y ago
saagarjha 7y ago
Question: does the Go compiler run meaningful optimization passes? I didn't really see it mentioned here, and given that I hear that the compiler is super fast I'm not sure if it does…
- Crinus 7y ago
  From a quick look at the repository it looks like there are optimizations performed: this code[1] seems to perform function inlining at the AST level, this code[2] converts the AST to SSA form which is generally meant to be used for optimizations, the SSA directory[3] contains a bunch of optimizations like common subexpression elimination[4], deadcode elimination[5], useless branch elimination[6] and other stuff (just browse around the files, they have comments about what they do). The SSA seems to contain both generic and machine-specific opcodes (basically instructions for the latter) with the former being converted to the latter using a bunch of rule tables[7] which seem to contain both generic-to-native transforms as well as peephole optimization rules (these are converted to go source code, most likely the huge files in the parent directory). Finally there seem to be a few optimizations in the machine-specific code generator (e.g. [8]). Of course it really depends on your definition of "meaningful", but i think that as long as it isn't equal to "as many optimizations known to humankind as possible, everything else be damned", the compiler looks to perform a decent amount of them. At least for me it passes the subjectively vague "meaningful" check :-P. [1] https://github.com/golang/go/blob/master/src/cmd/compile/internal/gc/inl.go https://github.com/golang/go/blob/master/src/cmd/compile/int... [2] https://github.com/golang/go/blob/master/src/cmd/compile/internal/gc/ssa.go https://github.com/golang/go/blob/master/src/cmd/compile/int... [3] https://github.com/golang/go/tree/master/src/cmd/compile/internal/ssa https://github.com/golang/go/tree/master/src/cmd/compile/int... [4] https://github.com/golang/go/blob/master/src/cmd/compile/internal/ssa/cse.go https://github.com/golang/go/blob/master/src/cmd/compile/int... https://github.com/golang/go/blob/master/src/cmd/compile/internal/ssa/zcse.go https://github.com/golang/go/blob/master/src/cmd/compile/int... [5] https://github.com/golang/go/blob/master/src/cmd/compile/internal/ssa/deadcode.go https://github.com/golang/go/blob/master/src/cmd/compile/int... [6] https://github.com/golang/go/blob/master/src/cmd/compile/internal/ssa/fuse.go https://github.com/golang/go/blob/master/src/cmd/compile/int... [7] https://github.com/golang/go/tree/master/src/cmd/compile/internal/ssa/gen https://github.com/golang/go/tree/master/src/cmd/compile/int... [8] https://github.com/golang/go/blob/master/src/cmd/compile/internal/amd64/ssa.go#L413 https://github.com/golang/go/blob/master/src/cmd/compile/int...
gldev3 7y ago
What about generics?

234 points by soheilpro 7y ago

That was a fun read. Very interesting. I have noticed that the AST nodes don't have a parent reference. I wonder how it knows for example when encountering a "continue LABEL" that the code is nested maybe deeply in a loop with that label. The only way I would think of is traversing the tree up but I think there is no way of doing this. How do they do it?

azhenley 7y ago
I don’t know how the Go compiler works but one solution is for each scope level to have a symbol table with a reference to the parent level’s table. So you can traverse up for symbols.
uryga 7y ago
i recently hacked together my first simple compiler and the way i handled stuff like break/continue is that every loop pushed a "context" onto a stack, so when the compiler encounters a break/continue it just looks into the context to find the label it should jump to. could be similar
Crinus 7y ago
Based on [1] (where continue is handled) and [2] (the branch statement type), looks like the target is simply passed to the function. This is a recursive descent parser, so passing the target down the statement handling stack is trivial (and indeed, this is what happens for for[3]). [1] https://github.com/golang/go/blob/master/src/cmd/compile/internal/syntax/branches.go#L218 https://github.com/golang/go/blob/master/src/cmd/compile/int... ("ctx" is a "targets" struct containing two entries, one for which statement 'break' targets and another for which statement 'continue' targets). [2] https://github.com/golang/go/blob/master/src/cmd/compile/internal/syntax/nodes.go#L360 https://github.com/golang/go/blob/master/src/cmd/compile/int... [3] https://github.com/golang/go/blob/master/src/cmd/compile/internal/syntax/branches.go#L293 https://github.com/golang/go/blob/master/src/cmd/compile/int... (the targets{s, s} passed to innerBlock is then passed to blockBranches - s is the for statement node itself). As a sidenote, it is interesting how easy Go reads even though i never wrote a single line of Go myself (though i do write a lot of C and Object Pascal and the code patterns look similar).
- dawkins 7y ago
  Now that you have pointed where it is, it really looks easy to understand how it works. Thank you!
barrkel 7y ago
Context from higher up the tree can easily be passed down when recursively processing, as others mention. As to why do that, there are several reasons. It's fiddly to construct trees when you need to patch the children with parent references. The most natural thing to do is create the children (usually via recursive parse) then construct the parent. If you then need to patch the children with a reference to their parent, it's more work. It also means your nodes can't be immutable (but they're often not wholly immutable anyway for other reasons, like annotating during passes that add semantic information). It's easier to reason about tree manipulations when you only have downward pointers. For example, maybe you want to rewrite a common subexpression with a reference to a temporary, and reuse one of the common trees as the RHS on the assignment to the temporary. It's more effort if you need to patch both ways on the link, rather than just grab the tree and slot it into the assignment. (It's possible that you have DAGs rather than trees, and have children with shared parents, but I think this isn't worth any extra representative or compression that it gives you because passes will want to mutate those nodes, and meeting the same nodes more than once makes invariants more complex.) Finally, more interesting traversals, following control or data flow, can cut across and jump between tree branches, so parent links don't necessarily help you there either. It helps that most languages don't have parse trees which would stress the runtime stack when processing recursively, outside of machine-generated code (and correspondingly, it's not that hard to get a stack overflow error or equivalent "too much nesting" error if you generate code targeting that failure mode).

kstenerud 7y ago

The go compiler is surprisingly easy to modify! I made a modification that allows it to issue warnings instead of errors for unused imports, variables, etc [1]. It was a fun little exercise :) [1] https://github.com/kstenerud/go https://github.com/kstenerud/go

mavelikara 7y ago
This is the commit in question: https://github.com/kstenerud/go/commit/334e03f12c9c94fe6adedfcbac105a4c9c19aba3 https://github.com/kstenerud/go/commit/334e03f12c9c94fe6aded.... Cool mod!
saagarjha 7y ago
Now if only this got merged into mailine ;)
- dullgiulio 7y ago
  Why? The idea that warnings are errors is pretty important actually. Now, unused imports are mostly harmless (alright, they are not because of init), but they keep unrelated commits clean without needing ad-hoc linting or IDE functionality.
  - kstenerud 7y ago
    It's explained in the use case: https://github.com/kstenerud/go#use-case https://github.com/kstenerud/go#use-case Use Case The use case for warnings is the exploratory development or debugging phases, where you really don't care about leaving unused things lying around for the time being (for example, temporarily commenting something out), and would rather that the compiler just got out of your way until you've got something ready to compile normally and commit. Usage go build -gcflags=-warnunused somefile.go go test -gcflags=-warnunused When you're done with your exploratory/debugging phase, simply build or test without the flag: go build somefile.go go test Compiling without the flags will fail on unused things as normal.
    - 7y ago

eliben 7y ago

Thanks for posting this :) Part 2 is http://eli.thegreenplace.net/2019/go-compiler-internals-adding-a-new-statement-to-go-part-2/ http://eli.thegreenplace.net/2019/go-compiler-internals-addi...

person_of_color 7y ago

Why didn't they use LLVM?

saagarjha 7y ago
Does https://golang.org/doc/faq#What_compiler_technology_is_used_to_build_the_compilers https://golang.org/doc/faq#What_compiler_technology_is_used_... answer your question (I interpreted it as "why doesn't the Go compiler use LLVM?")?
edflsafoiewq 7y ago
LLVM is very slow.
- kspp 7y ago
  It seems to be fast enough for SQL JIT-compiler in PostgreSQL 11+ and shader compilation in the *nix OpenGL stack (mesa), both of which are sort-of-realtime systems.
  - sanxiyn 7y ago
    There is an ongoing work to move Mesa away from LLVM because LLVM is slow.
  - vkazanov 7y ago
    Can't say anything about shaders but I do know a thing or two about database queries: 1. Queries are often repeated, i.e. most of backend DBs get the same requests over and over again. Even a slow jit compiler is fine here as things just get cached. 2. Queries usually take some time to complete, and this offsets the jit-related latency. Also, Postgres has a very limited kind of jit compilation, i.e. for expressions only. Notice that javascript jit compilers usually have a multi-tiered compilation. That's because proper compilation takes time, and sometimes it is more efficient to just do some basic template jiting (or no additional compilation) instead of firing the heavy guns. None of them use LLVM, btw.
    - 7y ago

saagarjha 7y ago

Question: does the Go compiler run meaningful optimization passes? I didn't really see it mentioned here, and given that I hear that the compiler is super fast I'm not sure if it does…

Crinus 7y ago
From a quick look at the repository it looks like there are optimizations performed: this code[1] seems to perform function inlining at the AST level, this code[2] converts the AST to SSA form which is generally meant to be used for optimizations, the SSA directory[3] contains a bunch of optimizations like common subexpression elimination[4], deadcode elimination[5], useless branch elimination[6] and other stuff (just browse around the files, they have comments about what they do). The SSA seems to contain both generic and machine-specific opcodes (basically instructions for the latter) with the former being converted to the latter using a bunch of rule tables[7] which seem to contain both generic-to-native transforms as well as peephole optimization rules (these are converted to go source code, most likely the huge files in the parent directory). Finally there seem to be a few optimizations in the machine-specific code generator (e.g. [8]). Of course it really depends on your definition of "meaningful", but i think that as long as it isn't equal to "as many optimizations known to humankind as possible, everything else be damned", the compiler looks to perform a decent amount of them. At least for me it passes the subjectively vague "meaningful" check :-P. [1] https://github.com/golang/go/blob/master/src/cmd/compile/internal/gc/inl.go https://github.com/golang/go/blob/master/src/cmd/compile/int... [2] https://github.com/golang/go/blob/master/src/cmd/compile/internal/gc/ssa.go https://github.com/golang/go/blob/master/src/cmd/compile/int... [3] https://github.com/golang/go/tree/master/src/cmd/compile/internal/ssa https://github.com/golang/go/tree/master/src/cmd/compile/int... [4] https://github.com/golang/go/blob/master/src/cmd/compile/internal/ssa/cse.go https://github.com/golang/go/blob/master/src/cmd/compile/int... https://github.com/golang/go/blob/master/src/cmd/compile/internal/ssa/zcse.go https://github.com/golang/go/blob/master/src/cmd/compile/int... [5] https://github.com/golang/go/blob/master/src/cmd/compile/internal/ssa/deadcode.go https://github.com/golang/go/blob/master/src/cmd/compile/int... [6] https://github.com/golang/go/blob/master/src/cmd/compile/internal/ssa/fuse.go https://github.com/golang/go/blob/master/src/cmd/compile/int... [7] https://github.com/golang/go/tree/master/src/cmd/compile/internal/ssa/gen https://github.com/golang/go/tree/master/src/cmd/compile/int... [8] https://github.com/golang/go/blob/master/src/cmd/compile/internal/amd64/ssa.go#L413 https://github.com/golang/go/blob/master/src/cmd/compile/int...

gldev3 7y ago

What about generics?