1<!--- 2// Copyright 2018 The Go Authors. All rights reserved. 3// Use of this source code is governed by a BSD-style 4// license that can be found in the LICENSE file. 5--> 6 7## Introduction to the Go compiler's SSA backend 8 9This package contains the compiler's Static Single Assignment form component. If 10you're not familiar with SSA, its [Wikipedia 11article](https://en.wikipedia.org/wiki/Static_single_assignment_form) is a good 12starting point. 13 14It is recommended that you first read [cmd/compile/README.md](../../README.md) 15if you are not familiar with the Go compiler already. That document gives an 16overview of the compiler, and explains what is SSA's part and purpose in it. 17 18### Key concepts 19 20The names described below may be loosely related to their Go counterparts, but 21note that they are not equivalent. For example, a Go block statement has a 22variable scope, yet SSA has no notion of variables nor variable scopes. 23 24It may also be surprising that values and blocks are named after their unique 25sequential IDs. They rarely correspond to named entities in the original code, 26such as variables or function parameters. The sequential IDs also allow the 27compiler to avoid maps, and it is always possible to track back the values to Go 28code using debug and position information. 29 30#### Values 31 32Values are the basic building blocks of SSA. Per SSA's very definition, a 33value is defined exactly once, but it may be used any number of times. A value 34mainly consists of a unique identifier, an operator, a type, and some arguments. 35 36An operator or `Op` describes the operation that computes the value. The 37semantics of each operator can be found in `gen/*Ops.go`. For example, `OpAdd8` 38takes two value arguments holding 8-bit integers and results in their addition. 39Here is a possible SSA representation of the addition of two `uint8` values: 40 41 // var c uint8 = a + b 42 v4 = Add8 <uint8> v2 v3 43 44A value's type will usually be a Go type. For example, the value in the example 45above has a `uint8` type, and a constant boolean value will have a `bool` type. 46However, certain types don't come from Go and are special; below we will cover 47`memory`, the most common of them. 48 49See [value.go](value.go) for more information. 50 51#### Memory types 52 53`memory` represents the global memory state. An `Op` that takes a memory 54argument depends on that memory state, and an `Op` which has the memory type 55impacts the state of memory. This ensures that memory operations are kept in the 56right order. For example: 57 58 // *a = 3 59 // *b = *a 60 v10 = Store <mem> {int} v6 v8 v1 61 v14 = Store <mem> {int} v7 v8 v10 62 63Here, `Store` stores its second argument (of type `int`) into the first argument 64(of type `*int`). The last argument is the memory state; since the second store 65depends on the memory value defined by the first store, the two stores cannot be 66reordered. 67 68See [cmd/compile/internal/types/type.go](../types/type.go) for more information. 69 70#### Blocks 71 72A block represents a basic block in the control flow graph of a function. It is, 73essentially, a list of values that define the operation of this block. Besides 74the list of values, blocks mainly consist of a unique identifier, a kind, and a 75list of successor blocks. 76 77The simplest kind is a `plain` block; it simply hands the control flow to 78another block, thus its successors list contains one block. 79 80Another common block kind is the `exit` block. These have a final value, called 81control value, which must return a memory state. This is necessary for functions 82to return some values, for example - the caller needs some memory state to 83depend on, to ensure that it receives those return values correctly. 84 85The last important block kind we will mention is the `if` block. It has a single 86control value that must be a boolean value, and it has exactly two successor 87blocks. The control flow is handed to the first successor if the bool is true, 88and to the second otherwise. 89 90Here is a sample if-else control flow represented with basic blocks: 91 92 // func(b bool) int { 93 // if b { 94 // return 2 95 // } 96 // return 3 97 // } 98 b1: 99 v1 = InitMem <mem> 100 v2 = SP <uintptr> 101 v5 = Addr <*int> {~r1} v2 102 v6 = Arg <bool> {b} 103 v8 = Const64 <int> [2] 104 v12 = Const64 <int> [3] 105 If v6 -> b2 b3 106 b2: <- b1 107 v10 = VarDef <mem> {~r1} v1 108 v11 = Store <mem> {int} v5 v8 v10 109 Ret v11 110 b3: <- b1 111 v14 = VarDef <mem> {~r1} v1 112 v15 = Store <mem> {int} v5 v12 v14 113 Ret v15 114 115<!--- 116TODO: can we come up with a shorter example that still shows the control flow? 117--> 118 119See [block.go](block.go) for more information. 120 121#### Functions 122 123A function represents a function declaration along with its body. It mainly 124consists of a name, a type (its signature), a list of blocks that form its body, 125and the entry block within said list. 126 127When a function is called, the control flow is handed to its entry block. If the 128function terminates, the control flow will eventually reach an exit block, thus 129ending the function call. 130 131Note that a function may have zero or multiple exit blocks, just like a Go 132function can have any number of return points, but it must have exactly one 133entry point block. 134 135Also note that some SSA functions are autogenerated, such as the hash functions 136for each type used as a map key. 137 138For example, this is what an empty function can look like in SSA, with a single 139exit block that returns an uninteresting memory state: 140 141 foo func() 142 b1: 143 v1 = InitMem <mem> 144 Ret v1 145 146See [func.go](func.go) for more information. 147 148### Compiler passes 149 150Having a program in SSA form is not very useful on its own. Its advantage lies 151in how easy it is to write optimizations that modify the program to make it 152better. The way the Go compiler accomplishes this is via a list of passes. 153 154Each pass transforms a SSA function in some way. For example, a dead code 155elimination pass will remove blocks and values that it can prove will never be 156executed, and a nil check elimination pass will remove nil checks which it can 157prove to be redundant. 158 159Compiler passes work on one function at a time, and by default run sequentially 160and exactly once. 161 162The `lower` pass is special; it converts the SSA representation from being 163machine-independent to being machine-dependent. That is, some abstract operators 164are replaced with their non-generic counterparts, potentially reducing or 165increasing the final number of values. 166 167<!--- 168TODO: Probably explain here why the ordering of the passes matters, and why some 169passes like deadstore have multiple variants at different stages. 170--> 171 172See the `passes` list defined in [compile.go](compile.go) for more information. 173 174### Playing with SSA 175 176A good way to see and get used to the compiler's SSA in action is via 177`GOSSAFUNC`. For example, to see func `Foo`'s initial SSA form and final 178generated assembly, one can run: 179 180 GOSSAFUNC=Foo go build 181 182The generated `ssa.html` file will also contain the SSA func at each of the 183compile passes, making it easy to see what each pass does to a particular 184program. You can also click on values and blocks to highlight them, to help 185follow the control flow and values. 186 187<!--- 188TODO: need more ideas for this section 189--> 190 191### Hacking on SSA 192 193While most compiler passes are implemented directly in Go code, some others are 194code generated. This is currently done via rewrite rules, which have their own 195syntax and are maintained in `gen/*.rules`. Simpler optimizations can be written 196easily and quickly this way, but rewrite rules are not suitable for more complex 197optimizations. 198 199To read more on rewrite rules, have a look at the top comments in 200[gen/generic.rules](gen/generic.rules) and [gen/rulegen.go](gen/rulegen.go). 201 202Similarly, the code to manage operators is also code generated from 203`gen/*Ops.go`, as it is easier to maintain a few tables than a lot of code. 204After changing the rules or operators, see [gen/README](gen/README) for 205instructions on how to generate the Go code again. 206 207<!--- 208TODO: more tips and info could likely go here 209--> 210