9.3 算法思路

编译器对函数中的静态数据流进行分析，以此来判断变量是否需要逃逸。

什么是静态数据流呢？函数变量以及变量之间的赋值操作构成了一个有向图，该图的顶点（Vertex）代表变量，边（Edge）代表赋值语句，方向（Direction）代表数据流向。例如下列代码：

type T struct {
    Name string
}

func escapeAnalysis(arg T) (*T, bool) {
    l1 := arg
    l1.Name = "Golang"

    l2 := &l1
    l3 := *l2
    return &l3, arg.Name == "Java"
}

该函数内变量形成的有向图如下：

Escape Analysis Vars

其中 ~r1 与 ~r2 为编译器内部为函数返回值取的变量名。上图中我们为每条边加了一个权重，该权重的计算方式为： derefs = 引用解析次数（Dereferences）- 取地址次数（Addressing） ，即赋值语句右侧 * 操作减去 & 操作的数目。参见下面例子：

p = &q      // Derefs: -1
p = q       // Derefs: 0
p = *q      // Derefs: 1
p = **&**&q // Derefs: 2

由于 &x 本身是不可寻址（non-addressable）的，所以任何边的权重最小值只能是 -1. 上图体现的便是该函数内局部变量的数据流。

上一节我们讨论过造成局部变量逃逸的根本原因由指向该变量的指针引起，这也是上图中权重算法的根本原因：对任何变量A，以及直接指向该变量的任意顶点B, 我们都需要知道 A 是否持有的是 B 的指针。如果是的话，那么当 A 逃逸时，B 也必然需要逃逸。例如上图中的路径：l3 -> ~r1, 其中 ~r1 作为返回值需要逃逸，此时 l3 到 ~r1 边的权重为 -1, 意味着将 l3 赋值给 ~r1 时取了地址，即 ~r1 拿到的是 l3 的指针，因此 l3 也必须逃逸；但 l2 -> l3 的权重为 1, 所以即使 l3 逃逸了，l2 也不需要逃逸，由于 l2 不需要逃逸，即便 l1 -> l2 的权重为 -1, l1 也不需要逃逸。

我们再将该思路进行推广：在一条赋值链 A <- B <- … <- X <- Y 中，如果 A 逃逸，赋值链上各级可能应用了解析操作（*），也可能是取址操作（&），这样导致的结果可能是 A 最终持有的是 X 的指针，那么我们的算法就必须让 X 逃逸，而 X 与 A 之间的所有变量则可能并不需要逃逸。例如下列代码：

type T struct {
    Name string
}

func escapeAnalysis() **T {
    var t T
    l1 := &t
    l2 := &l1
    l3 := &l2
    l4 := *l3

    return l4
}

函数的数据流有向图为：

Escape Analysis - Static Data Stream

通过赋值链我们可以发现，返回值 ~r1 实际持有的是 l1 的指针，而 l1 又持有 t 的指针，所以该函数中最终逃逸变量是 l1 与 t, 而中间的 l4, l3, l2 则不会逃逸。在逃逸分析一节我们会详细分析实现细节。