Paul Smith

SSA visualization

Go 1.7—out today!—features an new SSA-based compiler backend. SSA is a method of describing low-level operations like loads and stores that roughly map to machine instructions, with the special difference that SSA acts as though it has infinite number of registers. This is not especially interesting on its own, except that it enables a class of well-understood optimization passes that make the resulting binary smaller in code size and faster. The new release of Go is an indication the implementation is maturing and starting to take advantage of techniques and practices adopted in the wider world of compiler technology.

In addition to the performance benefits of the new SSA-based backend, there is a suite of new tools that allow a developer to interact with the SSA machinery. One such tool outputs the intermediate SSA statements, optimization passes, and resulting Go-flavored assembly. This is done by setting the environment GOSSAFUNC to the name of a function to disassemble when using the go tool, for example:

$ GOSSAFUNC=main go build

This invocation will output to the terminal, but the more interesting artifact is an HTML file, named ssa.html, written out to the current directory. Open the file in your web browser and you’ll see something like:

screenshot of SSA

What you are looking at is a table with many columns extending to the right, each one except for the first and last representing an optimization pass over the preceding SSA form. (I counted 37 separate passes.) The first column is the the compiler’s initial, unoptimized SSA output, and the last column is the Go-flavored assembly that will be turned into machine code for the final compiled binary executable or shared library.

anim gif of scrolling through SSA

While this can look intimidating to the uninitiated, SSA is relatively simple by design -- each line represents a either a value being assigned the result of an instruction (i.e., one of the infinite number of registers), or a label of a "basic block" (a set of statements, aka, the things between curly braces in source code), or the exit of a basic block which jumps execution to a different basic block (eg., control flow like an if-statement or returning from a function call).

For example:

v4 = Const64 <int> [42]

Means assign the 64-bit integer constant value 42 to the register labeled v4.

b5: ← b4
  v15 = Copy <mem> v14
  v16 = StaticCall <mem> {runtime.printnl} v15
Call v16 → b6

Means b5 is the label for a basic block with two statements. It concludes with an exit Call instruction, taking program execution to another basic block, b6, when returning from the function call that produces the v16 value.

The tokens like Const64, Copy, and StaticCall are analogous to assembly instructions like MOV and LEA.

One special operation is Phi, or a "Phi node". Notice that a Phi node takes two arguments, which are two values. Also notice that a basic block with a Phi node has two basic block labels next to its own label, unlike every other basic block:

b3: ← b1 b2
   v20 = Phi <int> v4 v6
   ...

This is an interesting construct and it relates to program control flow. A basic block is defined by having a single entry and a single exit point, and having a set of statements that execute sequentially (i.e., no branching logic) in between. And "SSA" stands for "single static assignment", which means that each value is assigned one and only one time. But what do you do if you have a reference to a variable that could have different values depending on which branch of an if statement the program took? A Phi node is a way of resolving this apparent contradiction. Since each branch of an if statement by definition assigns to a unique value, a Phi node coalesces them into the final value depending on which branch was actually taken. So you can think of it as the run-time retrieval of a value based on some condition. This is why the block has two dependencies at the top rather than just one.

Let’s write a silly program to motivate some examples:

package main

func main() {
	x := 5

	if 1 < 0 {
		x = -42
	}

	println(x)
}

Let’s start with the initial basic block, b1:

b1:
  v1 = InitMem <mem>
  v2 = SP <uintptr>
  v3 = SB <uintptr>
  v4 = Const64 <int> [5]
  v5 = ConstBool <bool> [false]
  v6 = Const64 <int> [-42]
  v11 = OffPtr <*int64> [0] v2
If v5 → b2 b3

After some program initialization, v4 is the assignment to the local var x in our code of the constant 5. Go knows at compile-time that 1 < 0 is always false so it just assigns false to v5. v6 is the assignment of -42 to x that will happen during program execution.

At the end we have the basic block exit, If v5 → b2 b3. This tests the truth value of v5 to decide whether to jump program execution to either b2 (if true) or b3 (if false). This is similar to the following chunk of assembly:

    JNZ b2
b3:
  ...
b2:
  ...

One nice thing about the Go SSA HTML view is you can click on any token in the SSA form and it will highlight the references to and from that element.

clicking on SSA elements

We can see from the different colors how the control flow will go. You can visually connect the blocks of code that will execute and the assignments, function calls, and additional branching that will result.

Clicking on the Phi node and its dependencies, you can see from where the possible values come from in previous control flow.

highlighted Phi node

Moving on, the function call prints out the integer value is in the following basic block:

b4: ← b3
  v9 = Copy <int> v20
  v10 = Copy <int64> v9
  v12 = Copy <mem> v8
  v13 = Store <mem> [8] v11 v10 v12
  v14 = StaticCall <mem> {runtime.printint} [8] v13
Call v14 → b5

The StaticCall instruction invokes the function from the Go runtime that is specialized to format integer values and print them to the terminal. One interesting thing to note is that the preamble to call sets some things up in memory, the location of which is fed to the printint function. If you notice, v11 refers back to the value set in b1, which is a pointer offset from v2, which was set from the stack pointer SP near the top of the program initialization. Which makes sense, because the generate assembly language needs concrete memory locations to address when invoking functions taking pointers.

There’s much more to investigate here, including the particular optimization passes, and tracing how individual instructions make their way through to the final assembly or are eliminated. But hopefully this has given you an introduction into SSA and how it maps to constructs in your applications.