The Design of the Go Assembler

Gophercon
12 July 2016

Rob Pike
Google
@rob_pike
[[http://golang.org/s/plusrob][+RobPikeTheHuman]]
http://golang.org/

* Presentation on youtube.com

Video is [[https://www.youtube.com/watch?v=KINIAgRpkDA][here]].


* Motivation
 
_Why_Learn_Assembler_Language?_

_The_most_important_single_thing_to_realize_about_assembler_language_is_that_it_enables_the_programmer_to_use_all_System/360_machine_functions_as_if_he_were_coding_in_System/360_machine_language._

— A Programmer's Introduction to IBM System/360 Assembler Language, 1970, page 4

* We still need assembly language

Once it was all you needed, then high-level languages like FORTRAN and COBOL came along.

But still needed today:

- environment bootstrap (operating system and program startup, runtime)
- low-level library code such as stack management and context switching
- performance (`math/big`)
- access to features not exposed in language such as crypto instructions

Also, perhaps most important: It's how we talk about the machine.

Knowing assembly, even a little, means understanding computers better.

* What does it look like?

Some examples...

* IBM System/360

.code asm/360.s.txt

* Apollo 11 Guidance Computer

.code asm/apollo.s.txt

* PDP-10

.code asm/pdp10.s.txt

(From the MIT PDP-10 Info file)

* PDP-11

.code asm/pdp11.s.txt

(From Unix v6 `as/as13.s`)

* Motorola 68000

.code asm/68000.s.txt

(From Wikipedia)             

* CRAY-1

.code asm/cray1.s.txt

(From Robert Griesemer's PhD thesis)


* Common structure

Columnar layout with function and variable declarations, labels, instructions.

Instructions:

	subroutine header
	label:
		instruction operand...	; comment
		...

Operands:

	register
	literal constant
	address
	register indirection (register as address)
	...

There are exceptions such as Cray (`A5` `A5+A14`) but they aren't conceptually different.

CPUs are all pretty much the same.

* Use that commonality

We can use the common structure of all assemblers (CPUs, really) to construct a common grammar for all architectures.

This realization took some time.

The seeds were planted long ago.

* Plan 9 assembly

Around 1986, Ken Thompson wrote a C compiler for the National 32000 (Sequent SMP).
Compiler generated pseudo-code, linker did instruction assignment.

The "assembler" was just a way to write that pseudo-code textually.

	MOVW    $0, var

might become (hypothetical example)

	XORW    R1, R1
	STORE   R1, var

Note assembler emits the `MOVW`; the linker generates `XORW` and `STORE`.
We call this _instruction_selection_.

Or consider `RET`, which becomes `RET` or `JMP` `LR` or `JMP` `(R31)` or ...

The assembler is just a way to hand-write the output the compiler produces.
(Compiler does not feed assembler, unlike in many other systems.)

* The pieces

.image asm/arch1.png

* The Plan 9 assemblers

Assembler for each architecture was a separate C program with a Yacc grammar,
adapted and partially rewritten for every architecture.

`8a`, `6a`, `va` etc. corresponding to `8c`, `6c` `vc`, etc.
(One-letter codes: `8` for 386, `6` for AMD64, `v` for MIPS, etc.)

All very similar up front but different in detail.

The earliest Go implementations used this design, adding Go compilers `8g`, `6g` but using the Plan 9 assemblers unchanged.

The separation of (compiler/assembler)⇒linker allowed the Go linker to do more, including helping boot the runtime.

* Go 1.3: Rearrange the pieces

Goal: Move to a pure Go implementation.
Preparation started in Go 1.3

New library that (in part) does instruction selection: `"liblink"` (as of 1.5, `"obj"`).
Call it from the compiler.

Thus the first part of the old linker is now in the compiler.
The compiler now emits (mostly) real instructions, not pseudo-instructions.

Result: Slower compiler, but faster build.
Instruction selection for library code done once, not every time you link a program.

Assemblers also use `obj`.

For both compiler and assembler, the _input_ is unchanged.
In fact the whole _process_ is the same, just arranged differently.

* The old pieces

.image asm/arch1.png


* The new pieces

.image asm/arch2.png


* Go 1.5: C must Go

More prep in Go 1.4, then in Go 1.5, all tooling moved to Go.

Compiler and linker machine-translated from C to Go.
The old `liblink` became a new suite of libraries, `obj/...`:

- `cmd/internal/obj`  (portable part)
- `cmd/internal/obj/x86`    (architecture-specific part)
- `cmd/internal/obj/arm`    (architecture-specific part)
- ...
 
Previous presentations about this work:

- Russ Cox at Gophercon 2014 (out of date): [[youtube.com/watch?v=QIE5nV5fDwA]]
- Rob Pike at Gopherfest 2015: [[youtube.com/watch?v=cF1zJYkBW4A]]
* Go 1.5: Compiler and linker as single programs

The many compilers (`6g`, `8g` etc.) were replaced with a single tool: `compile`.
`GOOS` and `GOARCH` (only!) specify the target operating system and architecture.

	GOOS=darwin GOARCH=arm go tool compile prog.go

Same for the linker: `6l`, `8l`, etc. become `go` `tool` `link`.

How can a single binary handle all these architectures?

Only one input language, only one output generator (the `obj` library).
The target is configured when the tool starts.

* Go 1.5 Assembler

Unlike the old compilers, which shared much code, the old assemblers were all different programs.
(Although they were very similar inside, they shared almost no code.)

Proposal: Write a single `go` `tool` `asm` from scratch in Go, replacing all the old assemblers.

`GOOS` and `GOARCH` tell you what the target is.

But assembly language isn't Go. Every machine has a different assembly language.

Well, not really! Not quite universal across machines, but ...

* An example program

Look at the generated assembly for this simple program:

.code asm/add.go.txt

For each architecture, with some noise edited out:

* 32-bit x86 (386)

.code asm/386.s.txt

* 64-bit x86 (amd64)

.code asm/amd64.s.txt

* 32-bit arm

.code asm/arm.s.txt

* 64-bit arm (arm64)

.code asm/arm64.s.txt

* S390 (s390x)

.code asm/s390x.s.txt

* 64-bit MIPS (mips64)

.code asm/mips64.s.txt

* 64-bit Power (ppc64le)

.code asm/ppc64le.s.txt

* Common grammar

They all look the same. (Partly by design, partly because they _are_ the same.)

The only significant variation is the names of instructions and registers.
Many details hidden, such as what `RET` is. (It's a pseudo-instruction.)

(Offsets are determined by size of `int`, among other things.)

The fortuitous syntax originated in Ken's National 32000 assembler.

With common syntax and the `obj` library, can build a single assembler for all CPUs.

* Aside: Downside

Not the same assembly notation as the manufacturers'.
Can be offputting to outsiders.

On the other hand, this approach uses the same notation on all machines.
New architectures can arrive without creating or learning new notation.

A tradeoff worth making.

* Design of the Go 1.5 assembler

The apotheosis of assemblers.

New program, entirely in Go.

Common lexer and parser across all architectures.
Each instruction parsed into an instruction description.
That becomes a data structure passed to the new `obj` library.

The core of the assembler has very little per-machine information.
Instead, tables are constructed at run time, flavored by `$GOARCH`.

An internal package, `cmd/asm/internal/arch`, creates these tables on the fly.
Machine details are loaded from `obj`.

* An example: initializing the 386

.code asm/arch386._go /^import/,$

Parser just does string matching to find the instruction.

* An example: ADDW on 386

Given an assembly run with `GOOS=386`, the instruction

	ADDW AX, BX

is parsed into in a data structure schematically like:

	&obj.Prog{
		As: arch.Instructions["ADDW"],
		From: obj.Addr{Reg: arch.Register["AX"]},
		To: obj.Addr{Reg: arch.Register["BX"]},
		...
	}

That gets passed to the `obj` library for encoding as a 386 instruction.

This is a purely mechanical process devoid of semantics.

* Validation

Assembler does some validation:

- lexical and syntactic correctness
- operand syntax
- (with some variation. e.g.: `[R2,R5,R8,g]` only legal on ARM)

But all semantic checking is done by the `obj` library.

If it can be turned into real instructions, it's legal!

* Testing

New assembler was tested against the old (C-written) ones.

A/B testing at the bit level: Same input must give same output.
Also reworked some parts of `obj` packages for better diagnostics and debugging.

Did `386` first, then `amd64`, `arm`, and `ppc`. Each was easier than the last.

No hardware manuals were opened during this process.

* Result

One Go program replaces many C/Yacc programs, so it's easier to maintain.
As a Go program it can have proper tests.

Dependent on `obj`, so correctness and completeness are relatively simple to guarantee.

New assembler almost 100% compatible with previous ones.
Incompatibilities were mostly inconsistencies.

Portability is easy now.

A new instruction set just needs connecting it up with the `obj` library,
plus a minor amount of architecture-specific tuning and validation.

Several architectures have been added since the assembler was created,
most by the open source community.

* Tables

To a large extent, the assembler is now table-driven.
Can we generate those tables?

The disassemblers (used by `go` `tool` `pprof`) are created by machine processing of PDFs.
The architecture definition is machine-readable, so use it!

Plan to go the other way:

Read in a PDF, write out `obj` library definitions and bind to assembler.
Why write by hand when you can automate?

Hope to have this working soon; basics are already in place.

Result: a largely machine-generated assembler.

* Conclusion

Assembly language is essentially the same everywhere.

Use that to build a *true* common assembly language.

Customize it on the fly using dynamically loaded tables.

And one day: create those tables automatically.


A portable solution to a especially non-portable problem.