这是Go编译器探险两篇文章中的第二篇。在第一部分中，我们通过构建自定义版本的编译器向Go语言添加了一个新语句。为此，我们已经涵盖了编译器图表中的前五个阶段。

我们最终是通过在“重写AST”阶段将until修改为for来实现的，在walk/stmt.go中进行了一些类似的工作，然后编译器才进入SSA转换阶段和代码生成阶段。

在本篇文章中，我们将通过在整个编译流程的后期来处理新的 until 语句来覆盖编译器的完整流程。

SSA

在gc运行walk转换之后，它会调用Compile（位于ssagen/pgen.go中）将AST转换为新的中间表示形式（IR），它采用静态单赋值（SSA）格式^[1]。

SSA是什么意思，编译器为什么要这样做？别着急，我们一个一个来。

我们先从第一个问题开始：什么是SSA?

我建议阅读上面链接的SSA维基百科页面和其他资源，懒得看也没关系，我在这里简单解释一下：

静态单赋值意味着IR中的每个变量只被赋值一次。考虑下面的伪代码：

x = 1
y = 7
// 使用 x 和 y 进行一些操作
x = y
y = func()
// 使用 x 和 y 进行更多操作

这不是SSA，因为变量x和y被多次赋值。如果我们将此片段转换为SSA，可能会得到类似以下的结果：

x = 1
y = 7
// 使用 x 和 y 进行一些操作
x_1 = y
y_1 = func()
// 使用 x_1 和 y_1 进行更多操作

请注意每个任务都有一个唯一的变量名。当x被重新赋值为不同的值时，会创建一个新的名称x_1。您可能想知道这在一般情况下如何工作…像这样的代码会发生什么：

x = 1
if condition: x = 2
use(x)

如果我们只是将第二个赋值重命名为x_1 = 2的话，那么use会使用哪个变量？x还是x_1或其他？为了处理这种情况，SSA形式中的IR具有特殊的phi（originally phony）函数，根据它来自哪条代码路径选择一个值。它看起来像这样：

这个phi节点被编译器用于在分析和优化IR时维护SSA，并在在后续阶段中使用机器码将其替换。

SSA(静态单赋值)的”静态”部分起到了类似于静态类型检查的作用；它意味着在查看源代码时（在编译时，或静态时），每个名称的赋值是唯一的，而在运行时，它可以发生多次。如果上面的示例代码位于循环中，则实际x_1 = 2这个赋值可能会发生多次。

现在我们已经基本了解了什么是SSA，下一个问题是为什么要使用它。

优化是编译器后端^[2]的重要组成部分，而后端通常被结构化以便于方便优化。我们再次查看这段代码片段：

x = 1
if condition: x = 2
use(x)

假设编译器想要运行一个非常常见的优化 – 常量传播(constant propagation)。也就是说，它想要在 x = 1 赋值之后将所有对 x 的使用替换为 1。它该如何处理？它不能只是找到赋值后所有对 x 的引用，因为 x 可能会被重写成其他东西（就像我们的例子一样）。

考虑这个片段：

z = x + y

在一般情况下，编译器必须执行数据流分析来查找：

x和y所引用的定义。在控制流存在的情况下，这并不容易，并且需要优势分析(dominance analysis)。
z在此定义之后被使用的位置，这同样具有挑战性。这种分析在时间和空间方面都开销很大，并且需要经常重新（或部分地）运行以进行维护。

SSA提供了一个很好的替代方法。如果z = x + y是在SSA中，则我们立即知道x和y所引用的定义（只能有一个！），并且我们立即知道z被使用的位置（该语句后所有对z的引用）。在SSA中，使用和定义被编码为IR，而且优化不会违反不变性。

Go编译器中的SSA

我们继续来看SSA在Go编译器中是如何构建和使用的。SSA在1.7^[3]版本中被添加到Go中。它的大部分代码位于ssa/和ssagen/目录下（请记住，所有这些路径都是相对于Go源码目录中src/cmd/internal/compile/的）。ssa目录中的README文件非常有用，可以用来了解一下Go SSA。

Go SSA 的实现还拥有一些我见过的最好的编译器工具（原作者已经从事编译器多年）。通过设置 GOSSAFUNC 环境变量，我们可以获得一个 HTML 页面，其中包含所有编译阶段和每个阶段后的 IR，如果我们有需要的话，可以轻松地查看是哪个优化出了问题。

我们来研究AST创建时的初始SSA，针对这段代码片段：

func usefor() {
    i := 4
    for !(i == 0) {
        i--
        sayhi()
    }
}

func sayhi() {
    fmt.Println("Hello, for!")
}

我将打印输出移动到sayhi函数中的原因是为了使SSA结果更加清晰。使用 -l 编译以禁用内联，这会留下一个很小的函数 sayhi() 的调用（fmt.Println 会生成很多的代码，因为字符串常量）。

生成的SSA如下:

b1:

        v1 (?) = InitMem <mem>
        v2 (?) = SP <uintptr>
        v3 (?) = SB <uintptr>
        v4 (?) = Const64 <int> [4] (i[int])
        v6 (?) = Const64 <int> [0]
        v9 (?) = Const64 <int> [1]
    Plain → b2 (10)

    b2: ← b1 b4

        v5 (10) = Phi <int> v4 v10 (i[int])
        v14 (14) = Phi <mem> v1 v12
        v7 (10) = Eq64 <bool> v5 v6
    If v7 → b5 b3 (unlikely) (10)

    b3: ← b2

        v8 (11) = Copy <int> v5 (i[int])
        v10 (11) = Sub64 <int> v8 v9 (i[int])
        v11 (12) = Copy <mem> v14
        v12 (12) = StaticCall <mem> {"".sayhi} v11
    Plain → b4 (12)

    b4: ← b3
    Plain → b2 (10)

    b5: ← b2

        v13 (14) = Copy <mem> v14
    Ret v13

这里需要注意的部分是：

bN 是控制流图的基本块。
Phi 节点是显式的。最有趣的一个是对 v5 的赋值。这正好是选择器分配到 i 中；一条路径来自于 v4（初始化程序），另一条路径来自于循环体内部的 v10（i–）。
忽略带有 <mem> 标记的节点，因为在此练习中我们不处理 Go 在其 IR 中传播内存状态的方式。如果感兴趣，请参阅上述 README 获取更多详细信息。

顺便提一下，这里的for循环正是我们想要将until语句转换成的形式。

将 `until`的AST节点转换为SSA

像之前一样，我们的代码将以处理for语句为模型。首先我们看until语句的控制流程图应该是什么样子：

现在我们只需要在代码中构建这个CFG。提醒一下：我们在第一部分添加的新AST节点类型是OUNTIL。我们将在ssagen/stmt.go中的state.stmt方法中添加一个新的switch子句，以便将带有OUNTIL操作符的AST节点转换为SSA形式。块和注释的命名应该使得跟踪代码变得容易，并提供与上面显示的CFG之间的关联。

case ir.OUNTIL:
    // OUNTIL: until Ninit; Left { Nbody }
    // cond (Left); body (Nbody)
    n := n.(*ir.UntilStmt)
    bCond := s.f.NewBlock(ssa.BlockPlain)
    bBody := s.f.NewBlock(ssa.BlockPlain)
    bEnd := s.f.NewBlock(ssa.BlockPlain)

    bBody.Pos = n.Pos()

    // first, entry jump to the condition
    b := s.endBlock()
    b.AddEdgeTo(bCond)
    // generate code to test condition
    s.startBlock(bCond)
    if n.Cond != nil {
        s.condBranch(n.Cond, bEnd, bBody, 1)
    } else {
        b := s.endBlock()
        b.Kind = ssa.BlockPlain
        b.AddEdgeTo(bBody)
    }

    // set up for continue/break in body
    prevContinue := s.continueTo
    prevBreak := s.breakTo
    s.continueTo = bCond
    s.breakTo = bEnd
    var lab *ssaLabel
    if sym := n.Label; sym != nil {
        // labeled until loop
        lab = s.label(sym)
        lab.continueTarget = bCond
        lab.breakTarget = bEnd
    }

    // generate body
    s.startBlock(bBody)
    s.stmtList(n.Body)

    // tear down continue/break
    s.continueTo = prevContinue
    s.breakTo = prevBreak
    if lab != nil {
        lab.continueTarget = nil
        lab.breakTarget = nil
    }

    // done with body, goto cond
    if b := s.endBlock(); b != nil {
        b.AddEdgeTo(bCond)
    }

    s.startBlock(bEnd)

如果你想知道n.Init在哪里处理 – 它是在switch之前统一处理所有类型节点的。

还有一件事，我们应该删除我们添加到walk/stmt.go的AST重写，不再将UntilStmt节点重写为ForStmt，因为我们已经教会了SSA层直接处理until。因此，walkUntil变成：

func walkUntil(n *ir.UntilStmt) ir.Node {
    if n.Cond != nil {
        init := ir.TakeInit(n.Cond)
        walkStmtList(init)
        n.Cond = walkExpr(n.Cond, &init)
        n.Cond = ir.InitExpr(init, n.Cond)
    }

    walkStmtList(n.Body)
    return n
}

就是这样！如果我们以现在的代码为基础运行编译器，像以前一样转储SSA的话：

func useuntil() {
    i := 4
    until i == 0 {
        i--
        sayhi()
    }
}

func sayhi() {
    fmt.Println("Hello, for!")
}

我们将得到一个与我们在for循环中使用的带有否定条件的SSA结构等效的结果，这正是我们所期望看到的。

SSA转换

在构建初始SSA之后，编译器会对SSA IR进行一系列的处理：

执行优化
将其降低到更接近机器代码的形式

所有的优化步骤都可以在ssa/compile.go文件中的passesslice中找到，一些关于它们运行顺序的限制则在同一文件中的passOrder slice中。这些优化对于现代编译器来说是相当标准的。降低指令选择特定架构进行编译和寄存器分配。

有关这些内容的更多详细信息，请参阅 SSA README^[4] 和这篇文章^[5]，其中介绍了 SSA 优化规则的有趣细节。

生成机器码

最后，编译器调用genssa（在genssa/ssa.go中）从SSA IR生成机器代码。我们不需要修改任何代码，因为我们为until语句生成的SSA由编译器中其他地方使用的组件组成–我们不需要添加新的指令类型。

但是，研究useuntil函数生成的机器代码具有教育意义。Go具有自己的汇编语法^[6]和历史渊源。我不会在这里详细介绍所有细节，但以下是一个带注释（带＃注释）的汇编转储文件，应该相对容易跟踪。我删除了一些垃圾收集器指令（PCDATA和FUNCDATA），以使内容更短：

"".useuntil STEXT size=76 args=0x0 locals=0x10
  0x0000 00000 (useuntil.go:5)  TEXT  "".useuntil(SB), ABIInternal, $16-0

  # Function prologue

  0x0000 00000 (useuntil.go:5)  MOVQ  (TLS), CX
  0x0009 00009 (useuntil.go:5)  CMPQ  SP, 16(CX)
  0x000d 00013 (useuntil.go:5)  JLS  69
  0x000f 00015 (useuntil.go:5)  SUBQ  $16, SP
  0x0013 00019 (useuntil.go:5)  MOVQ  BP, 8(SP)
  0x0018 00024 (useuntil.go:5)  LEAQ  8(SP), BP

  # AX will be used to hold 'i', the loop counter; it’s initialized
  # with the constant 4. Then, unconditional jump to the 'cond' block.

  0x001d 00029 (useuntil.go:5)  MOVL  $4, AX
  0x0022 00034 (useuntil.go:7)  JMP  62

  # The end block is here, it executes the function epilogue and returns.

  0x0024 00036 (<unknown line number>)  MOVQ  8(SP), BP
  0x0029 00041 (<unknown line number>)  ADDQ  $16, SP
  0x002d 00045 (<unknown line number>)  RET

  # This is the loop body. AX is saved on the stack, so as to
  # avoid being clobbered by "sayhi" (this is the caller-saved
  # calling convention). Then "sayhi" is called.

  0x002e 00046 (useuntil.go:7)  MOVQ  AX, "".i(SP)
  0x0032 00050 (useuntil.go:9)  CALL  "".sayhi(SB)

  # Restore AX (i) from the stack and decrement it.

  0x0037 00055 (useuntil.go:8)  MOVQ  "".i(SP), AX
  0x003b 00059 (useuntil.go:8)  DECQ  AX

  # The cond block is here. AX == 0 is tested, and if it’s true, jump to
  # the end block. Otherwise, it jumps to the loop body.

  0x003e 00062 (useuntil.go:7)  TESTQ  AX, AX
  0x0041 00065 (useuntil.go:7)  JEQ  36
  0x0043 00067 (useuntil.go:7)  JMP  46
  0x0045 00069 (useuntil.go:7)  NOP
  0x0045 00069 (useuntil.go:5)  CALL  runtime.morestack_noctxt(SB)
  0x004a 00074 (useuntil.go:5)  JMP  0

你可能已经注意到了，“cond”块移动到了函数的末尾，这不是它最开始在SSA中的位置，为什么呢？

答案是“循环旋转(loop rotate)”传递运行于SSA的最后阶段。该传递重新排列块，使得主体直接流入条件语句，避免每次迭代都进行额外跳转。如果您感兴趣，请参见ssa/looprotate.go获取更多详细信息。

总结

在这两篇文章中，我们通过以两种不同的方式实现新语句来研究了Go编译器。当然，这只是冰山一角，但我希望它提供了一个良好的起点，让你自己开始探索。

最后说明：我们已经构建了一个工作编译器，但其他Go工具无法识别新的until关键字。不幸的是在现阶段，Go工具使用大多数不同路径解析Go代码，并且与Go编译器本身没有共享此代码。我将在未来的文章中更详细地介绍如何使用工具处理Go代码。

附录 – 重现这些结果

要复制我们在本文中使用的Go工具链版本，您可以从第1部分开始，并按照本文的代码一步一步坐下来。您也可以直接从我的分支中获取adduntil-119-part2^[7]。

要获取编译过程中生成的SSA并将其放入一个方便的HTML文件中，请在构建工具链后运行以下命令：

GOSSAFUNC=useuntil <src checkout>/bin/go tool compile -l useuntil.go

然后就可以在浏览器中打开ssa.html了。如果您还想查看某个传递的CFG，请在函数名称后面添加传递名称，用冒号分隔；例如GOSSAFUNC=useuntil:number_lines。

要获取机器代码表示，请运行：

<src checkout>/bin/go tool compile -l -S useuntil.go

-S告诉编译器将汇编源代码发送到标准输出；-l禁用内联，这会通过内联fmt.Println调用来混淆主循环。

原文地址: https://eli.thegreenplace.net/2019/go-compiler-internals-adding-a-new-statement-to-go-part-2/

译者对编译器后端不是很熟悉，因此本篇翻译质量相较于上半篇可能有所下降，推荐有能力的同学去阅读原文

参考资料

[1]

静态单赋值格式: https://en.wikipedia.org/wiki/Static_single_assignment_form

[2]

编译器前后端: “我特意避免在文章中过多地使用“前端”和“后端”这两个术语。这些术语含义不清，但通常情况下，“前端”是指编译开始直到AST构建完成的所有内容，而“后端”则是处理更接近机器而非原始语言表示的阶段。当然，在中间还有很多部分，经常会被人叫做“中间层（middle-end）”。在复杂的大型编译器中，你会听到关于“前端的后端”、“后端的前端”以及类似混合使用了“中间”的说法。在Go语言中这一情况并不是太糟糕，并且边界相对清晰明确。AST与输入语言在句法上非常接近，而SSA则不是如此。从AST转换为SSA是用来绘制Go编译器前/后端分界线的好方法。”

[3]

Go1.7: https://blog.golang.org/go1.7

[4]

SSA README: https://github.com/golang/go/blob/master/src/cmd/compile/internal/ssa/README.md

[5]

Go SSA规则: https://quasilyte.dev/blog/post/go_ssa_rules/

[6]

Go的汇编语法: https://golang.org/doc/asm

[7]

文章代码: https://github.com/eliben/go/tree/adduntil-119-part2