# 9.5.4 逃逸分析

## 遍历有向图

当数据流有向图构建完成之后，编译器便会基于该结构进行逃逸分析。编译器首先遍历所有顶点，依次分析指向该顶点的路径（Path）上的所有顶点是否需要逃逸，编译器内部通过两个 LIFO Queue 来实现该双重循环。入口函数 `walkAll()` 也是外层循环，其代码如下：

```go
func (b *batch) walkAll() {
    todo := make([]*location, 0, len(b.allLocs)+1)
    enqueue := func(loc *location) {
        if !loc.queued {
            todo = append(todo, loc)
            loc.queued = true
        }
    }

    // 将所有的顶点压入队列
    for _, loc := range b.allLocs {
        enqueue(loc)
    }
    // 将代表堆地址的顶点压入队列
    enqueue(&b.heapLoc)

    var walkgen uint32
    // 从队列尾部开始遍历队列，并调用方法 walkOne 对当前顶点进行分析
    for len(todo) > 0 {
        root := todo[len(todo)-1]
        todo = todo[:len(todo)-1]
        root.queued = false

        walkgen++
        b.walkOne(root, walkgen, enqueue)
    }
}
```

该方法用于构建外层队列，内层循环及分析逻辑在方法 `walkOne()` 中。可以发现入队函数 `enqueue()` 也作为参数传递给了 `walkOne()`, 这意味着对顶点 `root` 的分析过程中，有可能会将某些顶点再次压入队列（这里说再次是因为前面通过遍历 b.allLocs 列表，已经将所有的顶点压入队列了）。

方法 `walkOne()` 以参数 `root` 为根节点，逐个分析指向该顶点的路径（Path）上的所有顶点，例如路径：root <- A … <- P … <- Z 中，如果 `root` 需要逃逸，而 `root` 实际上持有的是 `P` 的指针的话，那么 `P` 也需要逃逸。而此时我们就需要通过参数 `enqueue` 将顶点 `P` 再次压入外层队列，因为 `walkOne()` 只分析 `root` 与路径上各个顶点的关系，如果我们发现路径上某节点 `P` 需要逃逸的话，那么就有必要将 `P` 作为根节点再次进行分析（可能外围队列之前已经遍历过顶点 `P` 了，而当时 `P` 可能不需要逃逸，所以这里是再次分析），所以我们需要将顶点 `P` 再次压入外层队列。

内部队列的作用是让我们能够遍历指向根节点 `root` 路径上的所有顶点，抛开逃逸分析的逻辑，构建以及遍历逻辑如下：

```go
func (b *batch) walkOne(root *location, walkgen uint32, enqueue func(*location)) {
    root.walkgen = walkgen
    root.derefs = 0
    root.dst = nil

    todo := []*location{root} // LIFO queue
    // 遍历队列
    for len(todo) > 0 {
        l := todo[len(todo)-1]
        todo = todo[:len(todo)-1]

        // 删除对 l 进行逃逸分析的代码

        // 在 for 循环末尾将指向该顶点的所有顶点压入队列
        for i, edge := range l.edges {
            if edge.src.escapes {
                continue
            }
            d := derefs + edge.derefs
            if edge.src.walkgen != walkgen || edge.src.derefs > d {
                edge.src.walkgen = walkgen
                edge.src.derefs = d
                edge.src.dst = l
                edge.src.dstEdgeIdx = i
                todo = append(todo, edge.src)
            }
        }
    }
}
```

对每一个顶点的逃逸分析都发生在内层循环中，弄清楚了整个有向图的遍历方式之后，我们可以看看对于根节点 `root` 路径上的某节点 `l` 如何进行逃逸分析了。

## 逃逸分析逻辑

简单来说，对于根节点 `root` 及其路径上的节点 `l`, 如果下列两个关系均满足的话，那么 `l` 就需要逃逸：

1. &#x20;`root` 的生命周期长于 `l` \
   判断该逻辑的方法是 `batch.outlives()`, 其代码如下：

   ```
   // outlives reports whether values stored in l may survive beyond
   // other's lifetime if stack allocated.
   func (b *batch) outlives(l, other *location) bool {
       // The heap outlives everything.
       if l.escapes {
           return true
       }

       // We don't know what callers do with returned values, so
       // pessimistically we need to assume they flow to the heap and
       // outlive everything too.
       if l.isName(ir.PPARAMOUT) {
           // Exception: Directly called closures can return
           // locations allocated outside of them without forcing
           // them to the heap. For example:
           //
           //    var u int  // okay to stack allocate
           //    *(func() *int { return &u }()) = 42
           if containsClosure(other.curfn, l.curfn) && l.curfn.ClosureCalled() {
               return false
           }

           return true
       }

       // If l and other are within the same function, then l
       // outlives other if it was declared outside other's loop
       // scope. For example:
       //
       //    var l *int
       //    for {
       //        l = new(int)
       //    }
       if l.curfn == other.curfn && l.loopDepth < other.loopDepth {
           return true
       }

       // If other is declared within a child closure of where l is
       // declared, then l outlives it. For example:
       //
       //    var l *int
       //    func() {
       //        l = new(int)
       //    }
       if containsClosure(l.curfn, other.curfn) {
           return true
       }

       return false
   }
   ```

   该函数的实现还是比较清晰的，特别的可以看到：对于函数的返回值，由于无法知道函数调用者会如何处理返回值，所以当root节点为函数返回值时，编译器会保守得返回true。
2. &#x20;`root` 持有的指针链包含 `l` \
   这里我们引入了“指针链条”这个词，对于赋值关系：a = \&b, b = \&c, c = \&d, 那么我们就说赋值链 a <- b <- c <- d 中从 a 到 d 是一个指针链条。显然，如果 a 需要逃逸的话，整个赋值链上的所有变量都需要逃逸。

   &#x20;对应到有向图上， `root` 持有的指针链条是否包含 `l` 是通过有向图中 `l` 到 `root` 路径上的各个边的权重（Derefs）来确定的。此处我们定义 `W(a, b)` 为赋值链 a <- … <- b 中 b 相对于 a 的总权重。对于如下调用链：<br>

![Escape Analysis Assignment Chain](/files/-Maq0_9jEb-b5HZAowpP)

W(\~r1, l2) = 0 + 1 + -1 = 0, 所以 \~r1 实际持有的指针链中没有包含 l2；而 W(\~r1, l1) = W(\~r1, l2) +   -1 = -1, 表明 \~r1 实际持有的是 l1 的指针。

&#x20;由于 Go 语言中表达式 `&l` 本身是不可寻址的，即 &\&l 为非法表达式，因此在计算 W(a, b) 时，不能简单得将整个路径上所有边的权重（Derefs）直接加起来，例如上图中，我们不能说 W(\~r1, t) = -2，因为根据[算法思路](/9.-golang-bian-yi-qi-tao-yi-fen-xi/9.3-suan-fa-si-lu.md)中提到的权重计算方法，-2 代表的意义是 &\&t 这样的操作，这也不符合实际情况。所以对于赋值链 root <- … <- x <- t，当 W(root, x) = -1 时，我们规定 W(root, t) = min(-1, -1 + W(x, t)), 由此可以推论出对于任意两个顶点a 与 b, W(a, b) 的最小值为 -1. 如果 W(a, b) = -1, 我们就知道 b 在 a 的指针链中，对于逃逸分析而言这就够了。

&#x20;但 Go 中解引用操作（\*）却可以多次应用，例如 \*\*\*x 是合法的表达式，代表着对 x 所持有的指针进行三次解引用操作，因此对于赋值链 root <- … <- x <- t, 如果 W(root, x) >= 0, 那么易得 W(root, t) = W(root, x) + W(x, t)

{% hint style="info" %}
在计算赋值链的权重时，不会出现 w(a, b) < -1 的情况实际上并不是一种规定，而是一种结果。虽然在上图的链条 l3<-l2<-l1<-t 中每条边的权重都是 -1, 但并不能说 W(l3, t) = -3, 因为 l3 并没有对 t 取三次地址，而是对 l2 取了一次地址，然后 l2 又对 l1 取了一次地址，这样依次下去。因此 W(l3, t) 本身就应该等于 -1, 代表着这条赋值链的最终效果就是对 t 取了一次地址。

总体来说就是在一条赋值链中，取址运算（&）的效果是不会传递并叠加的，不管有多少中间变量存在，Go 的按值拷贝（copy-by-value）特性保证了每次取址操作的对象都是一个新的变量。

但运算符 ~~\*~~ 的效果却是可以传递和叠加的，所以如果权重为正，总赋值链的总权重直接相加即可。
{% endhint %}

&#x20;基于以上两点的分析，在内层队列循环中，逃逸分析的代码可以精简成如下如下样子：

```go
func (b *batch) walkOne(root *location, walkgen uint32, enqueue func(*location)) {
    root.walkgen = walkgen
    root.derefs = 0
    root.dst = nil

    todo := []*location{root} // LIFO queue
    for len(todo) > 0 {
        l := todo[len(todo)-1]
        derefs := l.derefs

        // If l.derefs < 0, then l's address flows to root.
        addressOf := derefs < 0

        if addressOf {
            // For a flow path like "root = &l; l = x",
            // l's address flows to root, but x's does
            // not. We recognize this by lower bounding
            // derefs at 0.
            derefs = 0
        }

        if b.outlives(root, l) {
            if addressOf && !l.escapes {
                l.escapes = true
                enqueue(l)
                continue
            }
        }

        // 删除掉构建内部队列的代码
    }
}
```

## 示例分析

我们来看看如下代码的逃逸分析：

```go
package main

type T struct {
    Name string
}

func GetT() **T {
    var t T
    l1 := &t
    l2 := &l1
    r3 := l1
    r4 :=&r3

    var l4 **T
    l4 = l2
    l4 = r4

    return l4
}
```

函数 `GetT()` 的数据流有向图为：

![Escape Analysis Steps](/files/-Maq0d6ONXYBYytnwRYE)

我们在这里只标记了分析出逃逸结果的几条路径，编译器分别根据路径 A, B, C 分析出 r3, l1 与 t 需要逃逸。将以上代码保存至 main.go, 通过命令 `go tool compile -G=3 -l -m -json "0,file:///tmp/main.json" main.go` 可以得出同样结论：

> ```
> main.go:8:6: moved to heap: t
> main.go:9:2: moved to heap: l1
> main.go:11:2: moved to heap: r3
> ```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://gocompiler.shizhz.me/9.-golang-bian-yi-qi-tao-yi-fen-xi/9.5.4-tao-yi-fen-xi.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.