Draft some slides introducing Golang compiler internals

[Wei....@arm.com]

Hi

Recently, I draft some slides (as attached) introducing Golang compiler internals to my colleagues.

The slides aim to provide some basic descriptions about main stages and some simple examples (target at arm64) for intuitive grasp.

I would appreciate it if you can provide some feedback or suggestions to improve the slides.

I also hope the slides can help asking some basic questions for newcomers.

Thanks

Wei Xiao

[John McKown]

​Very interesting. I don't know much about compiler theory, but this might be very helpful for me to have a better understanding.​

--

I have a theory that it's impossible to prove anything, but I can't prove it.

Maranatha! <><
John McKown

[Brad Fitzpatrick]

Nice.

Note that Slide 18 "Go SSA Viewer" is suddenly talking about an unrelated SSA package. The x/tools/go/ssa package predates the Go compiler having an SSA form, and the Go compiler uses a totally different SSA package & representation.

--
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[David Chase]

Regarding "SSA Viewer", a side effect of GOSSAFUNC=foo is creation of ssa.html in the directory containing the source for function/method foo.

Clicking on values or blocks in your browser will cause them to be highlighted across phases.

I don't know if this helps, but I wrote a one-page "implementor's overview" to try to provide more context to compiler and runtime people new to (this implementation of) Go, and to help answer some obvious "but why don't you do X?" questions.  Your slides (which are excellent) correspond to the last paragraph.

================

Go is a simple compiled programming language.  It is intended to be easy to learn, easy to deploy, and relatively easy to understand code written in Go.  Go’s design also addresses some problems observed in Google-scale C++ programs: dependencies between Go packages are strictly layered (no cycles), there is no preprocessor, and the default linking mode is static. As a general rule, Go tries to present a few-knobs interface to users. One GC knob, one threading knob, effectively one compiler knob.

Go’s threading model is “Green” or “M-on-N”; in Go itself the thread-like entities are called goroutines, and these are what is multiplexed onto OS threads.  Goroutines don’t have user-visible thread-local storage, don’t support priorities, and don’t yet support any sort of processor affinity.  It’s possible for goroutines to communicate through shared memory, but use of channels is preferred.  Goroutines are intended to be very lightweight; 100,000 goroutines on a phone-class computer should be possible.  Because of this, goroutine stacks are initially allocated small and are dynamically resized (copied into larger and larger pieces of contiguous storage) as necessary.

Scheduling of goroutines is “cooperative”, meaning that it is enforced with compiler-inserted safepoints and at certain points in the runtime system.  Blocking (network) I/O calls are virtualized to avoid blocking an OS thread.  In practice this means that only a small number of OS threads are needed to run a large number of goroutines.

The Go garbage collector is precise, (currently) non-generational, concurrent, parallel, and imposes very small pause times; normally under 100µs (this relies on write barriers enabled during GC).  Garbage collections are initiated before heap limits are reached, with the goal that devoting 25% of available CPU to GC will allow the GC to finish just as the heap limit is reached. If a goroutine allocates at a higher-than-expected rate during a garbage collection, it may be drafted to perform additional GC work proportional to its excess allocation.  Heap objects are never relocated, but stacks can be if they grow or shrink.  The garbage collector also handles interior pointers correctly.  Native code has limited access to Go pointers.

Pointers have no tags and objects have no headers; pointers within objects are located using bitmaps initialized at object allocation time.  The Go equivalent of Java “Object” or C “void*” is “interface{}”, which contains both a pointer to the actual object and the type of that object.  The Go library makes ample and elegant use of reflection on interface types.

The Go compiler (gc) is descended from a simple compiler written in C, now converted to Go, and currently being refined and enhanced.  The front end produces AST which is checked, transformed, and subject to some optimizations. Notably, the AST analysis includes an interprocedural ad hoc escape analysis to convert (some) heap allocations to stack allocations.  The compiler then converts AST to SSA, to which various SSA-style optimizations are applied.  The Go community is sensitive to compile times, so the optimizations performed are chosen and coded carefully.  The calling convention is currently non-ABI, in memory, mostly because of inertia and constraints imposed by stack growth and garbage collection.

================

[Robert Griesemer]

In your slides you mention the lexer and parser as go/scanner and go/parser: Those are used by various tools (gofmt, gotype, etc.) but they are not used by the compiler (cmd/compile).

The compiler uses a new internal package called syntax (cmd/compile/internal/syntax) which contains a new lexer, parser, and AST, all in one package. These are similar to the go/* packages, but streamlined and faster.

The compiler receives ASTs from the syntax package which are then translated into the existing compiler-internal node structure (by cmd/compile/internal/gc/noder.go). In other words, there are two syntax trees, the new one generated by the syntax package (modern, light-weight), and the (older) one in the compiler, based on the Node data structure. The reason for this is that at some point we might want to replace the Nodes data structure with something more modern and light-weight.

You may want to update your slides accordingly.

- gri

On Thu, Dec 21, 2017 at 2:44 AM, <Wei....@arm.com> wrote:

--

[ilya....@intel.com]

Very nice!

Maybe mentions options that  provide insight into compiler decisions, such as 

-d=ssa/<phase>/stats, -m -m etc.

[Wei....@arm.com]

Ok, I will remove the slide to void confusing readers.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+...@googlegroups.com.

[Wei....@arm.com]

Thanks for the great "implementor's overview" !

It provides a whole picture about Golang background, philosophy, design and implementation.

Besides compiler improvement, I think there are also a lot of runtime improvement opportunities for arm64, especially with its new architecture features such as:

1. New instructions (such as atomic) to better support Goroutine scheduling for large scale parallel system (with 128-core, 256-core or even more-core ARM processors).

2. Scalable Vector Extension (SVE) to optimise Go basic functions (such as string compare and index) and computation-intensive works.

3. Transaction memory for better Go garbage collector.

As for Go ABI, It would be friendly to arm64 (with a lot of registers) if at some point in the future Golang can switch to new ABI passing parameter via registers just like GCC.

We'd like to contribute to the new ABI development if needed.

Thanks

Wei Xiao

To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "golang-dev" group.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+...@googlegroups.com.

[Wei....@arm.com]

I'll add the options.

Thanks for the suggestions!

[Wei....@arm.com]

Thanks for the detailed explanations.

I will update the slides according to your comments.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+...@googlegroups.com.

[Wei....@arm.com]

The refined slides are attached.

Any comments are welcome!

Thanks

Wei Xiao

[dek...@google.com]

Hi Wei,

I believe the latest PDF you attached is missing Robert's note on the updated locations of the lexer/parser/AST. 

Kind regards,

Jean

[Wei....@arm.com]

Hi Jean,

Thanks for the comments!

Actually, I meant to introduce lexer & parser inside both go/* packages and syntax package since developers may be interested in the ones in go/* packages which can be invoked from Go programs.

I know that compiler uses the ones of syntax package but original slides seem to confuse readers on it.

So I add a separate page to explain the package: syntax and hope the page can make it clear.

The 3rd version is as attached.

Thanks

Wei Xiao