[译] 添加一个新语句到Golang编译器内部-第二部分

原文链接

这是探讨Go编译器的两部分系列文章中的第二篇。 在 第一部分 中，我们通过构建定制版本的编译器向Go语言添加了一条新语句。 为此，我们按照此图介绍了编译器的前五个阶段：

在"rewrite AST"阶段，最终将 until 降级(lower)到 for ；具体来说，在编译器进行 SSA 转换和代码生成之前，在 gc/walk.go 中， 已经完成了对 until 的转换。

在本部分中，我们将尝试另外一种方式--在编译器的 SSA 和代码生成阶段中处理新增的 until 语句。

SSA

在 gc 编译器运行 walk 转换后，会调用 gc/ssa.go 文件中的 buildssa 将AST转换为 静态单分配（SSA）形式 的新中间表示（IR）。

SSA (static single assignment form)是什么意思，为什么编译器要这样做?让我们从第一个问题开始;我推荐阅读上面链接的SSA维基百科页面和其他资源，但这里是一个快速解释。

静态单一分配意味着IR中分配的每个变量仅分配一次。 考虑以下伪IR：

x = 1
y = 7
// do stuff with x and y
x = y
y = func()
// do more stuff with x and y

这不是SSA，因为名称 x 和 y 被分配了多次。 如果将此代码段转换为SSA，我们可能会得到类似以下内容的信息：

x = 1
y = 7
// do stuff with x and y
x_1 = y
y_1 = func()
// do more stuff with x_1 and 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有了基本的了解，接下来的问题是为什么。

优化是编译器后端的重要组成部分，后端通常是专门为促进有效和高效的优化而构造的。 再次查看此代码片段：

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

并假设编译器要运行一个非常常见的优化-常量传播( constant propagation )； 也就是说，它希望在 x = 1 分配后用 1 替换x的所有用法。 怎么会这样呢？ 它不能只找到赋值后对 x 的所有引用，因为 x 可以重写为其他内容（如我们的示例）。

考虑这个代码片段

z = x + y

通常，编译器必须执行数据流分析才能找到：

1. x 和 y 指的是哪个定义。 在存在控制流的情况下，这并不容易，需要进行优势分析( dominance analysis)。

2. 在此定义之后使用z时，同样具有挑战性。

就时间和空间而言，这种分析的创建和维护成本很高。 而且，必须在每次优化后（至少部分）重新运行它。

SSA 提供了一个很好的选择。 如果 z = x + y 在 SSA 中，则我们立即知道 x 和 y 所引用的定义（只能有一个！），并且我们立即知道在哪里使用 z （此语句之后对 z 的所有引用）。 在 SSA 中，用法和定义在 IR 中进行了编码，并且优化不会违反不变性。

Go编译器中的SSA

我们继续描述Go编译器中如何构造和使用 SSA 。 SSA 是Go中一个 相对较新的功能 。除了将 AST 转换为 SSA 的大量代码（位于 gc/ssa.go 中）外，其大部分代码都位于 ssa 中。

ssa 目录中的 README 文件是 Go SSA 的非常有用的说明-请阅读一下！

Go SSA 实现也有一些“我”见过的最好的编译器工具。通过设置 GOSSAFUNC 环境变量，我们将获得一个HTML页面，其中包含所有编译阶段以及每个编译阶段之后的 IR ，因此我们可以轻松地检测出需要进行哪些优化。 附加设置可以在每次通过时将控制流图绘制为SVG。

让我们研究一下从 AST 为该代码段创建的初始 SSA ：

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

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

我将打印输出移出 usefor 的原因是为了使 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 中显式传播内存状态，在本文中我们将不涉及。 如果有兴趣，请参见上述自述文件以了解更多详细信息。

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

将 until AST节点转换为SSA

像往常一样，我们的代码将基于 for 语句的处理进行建模。首先，让我们粗略地描述一下控制流图应该如何处理 until 语句

现在我们只需要在代码中构建这个CFG。提醒:我们在第1部分中添加的新 AST 节点类型是 OUNTIL 。

我们将在 gc/ssa.go 中的 state.stmt 方法中添加一个新的 switch 子句，以将具有 OUNTIL 的 AST 节点转换为 SSA 。块和注释的命名应使代码易于阅读，并与上面显示的CFG相关。

case OUNTIL:
  // OUNTIL: until Ninit; Left { Nbody }
  // cond (Left); body (Nbody)
  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.Left != nil {
    s.condBranch(n.Left, 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
  lab := s.labeledNodes[n]
  if lab != nil {
    // labeled until loop
    lab.continueTarget = bCond
    lab.breakTarget = bEnd
  }

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

  // 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.Ninit 的处理位置-它在 switch 之前完成，对于所有节点类型都是统一的。

事实上，这就是我们在编译器的最后阶段对于 until 语句所要做的一切。如果我们对于如下代码，运行编译器获取 SSA ：

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

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

我们将得到SSA，它在结构上与 for 循环相同，条件为负数，正如预期的那样。

SSA变换

构造初始 SSA 之后，编译器会在 SSA IR 上执行以下较长的遍历过程：

1. 执行优化
2. 将其 lower 为更接近机器代码的形式
   可以在 ssa/compile.go 的 passs slice 中找到所有 pass ，并且在同一文件的 passOrder slice 中可以限制它们的运行顺序。 对于现代编译器而言，优化是相当标准的。 lower 还包括针对我们正在编译的特定体系结构的指令选择以及寄存器分配。
   有关这些 pass 的其他详细信息，请参见 SSA自述文件 以及 这篇博客 ，其中详细介绍了如何指定 SSA 优化规则。

生成机器码

最后，编译器调用 gc/ssa.go 文件中的 genssa ，从 SSA IR 发出机器代码。

我们不需要修改任何代码，因为 until 语句生成的 ssa 由在编译器中其他位置使用的构建块组成，我们也不需要添加新的指令类型。

然而，这对于我们研究 useuntil 函数的代码生成具有指导意义。Go有其历史根源的 Plan9汇编语法 。我不会在这里进行所有详细介绍，但是以下是带注释的（带有＃注释）反汇编文件，应该比较容易理解。我删除了一些垃圾回收器的指令（ 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 表示中的位置。为什么会这样？

答案是在最后阶段在 SSA 上运行“loop rotate” pass 。 此 pass 对块进行重新排序，使主体直接流入 cond ，避免每次迭代产生额外的跳跃。 如果您有兴趣，请参阅 ssa/looprotate.go 了解更多详细信息。

结论

就是这样!在这两篇文章中，我们通过两种不同的方式实现一个新的语句，学习了Go编译器的一些内部原理。当然，这只是冰山一角，但我希望它为您开始自己的探索提供了一个良好的起点。

最后一点：我们在这里构建了一个可运行的编译器，但是Go工具都无法识别新的 until 关键字。不幸的是，此时Go工具使用了完全不同的路径来解析Go代码，并且没有与Go编译器本身共享此代码。在以后的文章中，我将详细介绍如何使用工具处理Go代码。

附录-重现这些结果

GOSSAFUNC = useuntil：number_lines 。

要获取反汇编代码，请运行

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