Go: Introduction to the Escape Analysis

ℹ️ This article is based on Go 1.13.

The escape analysis one of the phases of the Go compiler. It analyses the source code and determines what variables should be allocated on the stack and which ones should escape to the heap.

Static analysis

Go statically defines what should be heap or stack-allocated during the compilation phase. This analysis is available via the flag -gcflags="-m" when compiling and/or running your code thanks to go run or go build. Here is a simple example:

func main() {
   num := getRandom()
   println(*num)
}

//go:noinline
func getRandom() *int {
   tmp := rand.Intn(100)

   return &tmp
}

Running the escape analysis shows us tmp escapes to the heap:

./main.go:12:2: moved to heap: tmp

The first step of the static analysis is building the Abstract Syntax Tree of the source code, allowing Go to understand where assignments and allocations are done along with variables addressing and dereferencing. Here is an example of the previous code:

However, for the escape analysis, we can remove the noises produced by the AST and get a simpler version of this tree:

Since the tree exposes the defined variables — represented by NAME — and operations on pointer — represented by ADDR or DEREF, it gives all information to Go to perform its escape analysis. Once the tree is built and the functions and parameters parsed, Go can now apply the escape analysis logic to see what should be heap or stack-allocated.

Outlive the stack frame

While running the escape analysis and traversing the functions from AST graph — marked, Go looks for variables that outlive the current stack frame and therefore need to be heap-allocated. Let’s first define what outlive means by representing the stack frame of the previous example if there is no heap allocation. Here is the stack growing downward when calling the two functions:

Then, any variable created in the function getRandom will not be accessible when the stack frame of the function becomes invalid, i.e., when the program will return from the function:

In this case, the variable num cannot point to a variable allocated on a previous stack. In this case, Go must allocate the variable on the heap, making sure it will outlive the stack frame:

The variable tmp now contains the address of the allocated memory to the stack and can be safely copied from a stack frame to another one. However, the returned values are not the only ones that can outlive. Here are the rules:

• Any returned value outlives the function since the called function does not know the value.
• Variables declared outside a loop outlive the assignment within the loop:

func main() {
   var l *int
   for i := 0; i < 10; i++ {
      l = new(int)
      *l = i
   }
   println(*l)
}

./main.go:6:10: new(int) escapes to heap

• Variables declared outside a closure outlive the assignment within the closure:

func main() {
   var l *int
   func() {
      l = new(int)
      *l = 1
   }()
   println(*l)
}

./main.go:8:3: new(int) escapes to heap

The second part of the escape analysis consist of determining how it manipulates the pointer, helping to understand what could stay on the stack.

Addressing and dereference

Building a weighted graph representing addressing/dereference counts allows Go to optimize the stack allocation. Let’s analyze an example to understand how it works:

func main() {
   n := getAnyNumber()
   println(*n)
}

//go:noinline
func getAnyNumber() *int {
   l := new(int)
   *l = 42

   m := &l
   n := &m
   o := **n

   return o
}

Running the escape analysis shows that the allocation escapes to the heap:

./main.go:10:10: new(int) escapes to heap

Here is the AST code generated in a simpler version:

Go defines the allocation by building the weighted graph. Each dereferencing, represented by * in the code or DEREF in the nodes, increase the weight by 1. Each addressing operation, represented by & in the code or ADDR in the nodes, decrease the weight by 1.

Here is the sequence defined by the escape analysis:

variable o has a weight of 0, o has an edge to n
variable n has a weight of 2, n has an edge to m
variable m has a weight of 1, m has an edge to l
variable l has a weight of 0, l has an edge to new(int)
variable new(int) has a weight of -1

Each variable ending up with a negative count escapes to the heap if it outlives the current stack frame. Since the returned value outlives the stack frame of its function and gets a negative count through its edges, the allocation escapes to the heap.

Building this graph allows Go to understand which variable should stay on the stack despite it outliving the stack. Here is another basic example:

func main() {
   num := func1()
   println(*num)
}

//go:noinline
func func1() *int {
   n1 := func2()
   *n1++

   return n1
}

//go:noinline
func func2() *int {
   n2 := rand.Intn(99)

   return &n2
}

./main.go:20:2: moved to heap: n2

The variable n1 outlives the stack frame, but its weight is not negative since func1 does not refer to its address at any place. However, n2 outlives and gets dereferenced; Go can safely allocate it on the heap.