8.4.1 遍历调用链

函数的调用关系形成了一个有向图（Directed Graph），在对函数进行内联操作时，我们需要反向对函数的调用链进行分析。例如函数的调用链是 A()->B()-C(), 则我们需要先分析能否将 C 内联到 B 内，再分析是否能将 B 内联到 A 中。

遍历函数的逻辑封装在文件 cmd/compile/internal/ir/scc.go 中，该文件内封装了自底向上遍历函数 AST 的方法。SCC 的全称是 Strongly connected components，一个 SCC 是由有向图的节点构成的子集，其中任意两个节点之间都至少有一条连通的路径。例如下面的有向图内有三个 SCC:

SCC - 图片来自维基百科

对于函数调用链形成的有向图，该文件中的函数会自底向上找出每个 SCC, 然后依次传递给分析函数进行处理。遍历函数的签名如下：

func VisitFuncsBottomUp(list []Node, analyze func(list []*Func, recursive bool)) {
    // Ignore function body
}

对于参数 list 中的每个函数节点，函数会将找出的 SCC 依次传递给 analyze 函数进行处理。对于如下代码：

func B() {
    println("B")
}

func A() {
    println("A")
    B()
}

func C() {
    println("C")
    D()
}

func D() {
    println("D")
    C()
}

func main() {
    A()
    C()
}

整个函数的调用关系图如下：

Func Call Stack & SCC

每种颜色的函数都形成一个 SCC, 处理的顺序是：{B}, {A}, {C, D}, {main}.