这是介绍Go编译器系列的第二篇，在第1部分中，我们在Go中添加了一个新的关键词语句，通过构建修改版本的编译器来支持该关键字。为此，我们按照此图介绍了编译器的前五个阶段：

在最后，我们是通过在＂重写AST＂阶段将其替换为for来实现until。另外，在gc/walk.go中，其他类似的转换也是在编译器进行SSA转换和代码生成之前完成的。

在这一部分中，我们将通过在编译流程中处理新的until语句来介绍编译器的其余阶段。

SSA

在gc运行walk转换后，它调用buildssa（在gc/ssa.go中）将AST转换为新的中间表示（intermediate representation (IR)），其形式为静态单赋值（SSA）形式。

注：一个Go程序元素只有包、类型、函数、变量和常量 （packages, types, functions, variables and constants）这五种。ssa定义了的他们的数据结构，使用函数体的静态单赋值（ssa）形式中间表示（IR）。

SSA是什么意思？为什么编译器会将AST转为SSA？让我们从第一个问题开始；我建议阅读上面链接的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 （最初为 phony ）功能，可以根据其来自的代码路径来选择一个值。它看起来像这样：

当分析和优化此类IR时，编译器使用该phi节点来维护SSA，并在以后的阶段用实际的机器代码代替。

SSA名称的static 部分起着与 static类型中类似的作用；这意味着在查看源代码时（在编译时或静态），每个名称的赋值都是唯一的，但是在运行时可能会多次发生。例如上面显示的代码示例处于循环中，则实际的x_1 = 2赋值可能会发生多次。

既然我们对什么是SSA有一个基本的了解，那么下一个问题就是为什么编译器会将AST转为SSA。

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

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

并假设编译器要运行一个非常通用的优化-常数传播 （ constant propagation），该优化希望在x = 1赋值后用1替换所有使用x的地方。这需要怎么做呢？它不能在赋值之后找到对x的所有引用进行替换，因为x可以重写为其他内容（x = 2）。

请考虑以下代码段：

z = x + y

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

1. x和y在什么地方定义的。在存在控制流的情况下，这并不容易，需要进行“优势”分析。

2. 在定义之后使用z的地方，这同样具有挑战性。

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

SSA提供了一个很好的选择。如果SSA中有z = x + y，我们会立即知道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，因此，如果需要，我们可以轻松地检测出哪个优化出错了。附加设置可以绘制每次pass时的控制流图。

让我们研究一下如何从下述代码的AST中创建初始SSA：

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

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

我将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]) // 第一次循环，选择V4
        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语句的控制流图 ：

现在，我们只需要用代码构建此控制流图 。提醒：我们在第1部分中添加了新的AST节点类型OUNTIL。我们将在gc/ssa.go中的state.stmt方法中添加一个新的switch分支，以将OUNTIL的AST节点转换为SSA。代码块和注释的命名应使代码易于阅读，并与上面显示的控制流图中命名相关。

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

  // 首先 ，上一个 Block结束块 连接到当前的 CondBlock块
  // first, entry jump to the condition
  b := s.endBlock()
  b.AddEdgeTo(bCond)
  // 开始生成 CondBlock
  // generate code to test condition
  s.startBlock(bCond)
  if n.Left != nil {
    // left 不为空，直接使用condBranch，if for 都使用这个函数
    s.condBranch(n.Left, bEnd, bBody, 1)
  } else {
    // left 为空 无限循环。直接结束生成代码
    b := s.endBlock() 
    b.Kind = ssa.BlockPlain
    b.AddEdgeTo(bBody) // 添加到 Body的连接
  }

  // 设置 continue/break 
  // 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
  }

  // 开始 生成 Body代码
  // generate body
  s.startBlock(bBody)
  s.stmtList(n.Nbody)
  
  // 拆除 continue/break，这里是置为上一个 prevContinue和 prevBreak
  // 因为有循环嵌套
  // 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，该SSA在结构上等同于条件为 for的循环所用的SSA。

SSA transformations 变换

构造了初始SSA之后，编译器会在SSA IR上执行以下一系列漫长的遍历操作：

1. 执行优化
2. 将其转换为更接近机器代码的形式

所有 passes 都可以在ssa/compile.go的passes切片中找到，并且可以在同一文件的passOrder切片中对它们的运行顺序进行一些修改。对于现代编译器而言，优化是相当标准的。降低针对特定体系结构的指令选择，以及寄存器分配。

有关这些 passes 的更多详细信息，请参见SSA README和this post，其中详细介绍了如何指定SSA优化规则。

生成机器码

最后，编译器调用genssa（在gc/ssa.go中）从SSA IR中生成机器代码。我们不必修改任何代码，因为我们为until语句生成的SSA构造块，是编译器已经实现的，我们不添加新的指令类型。

但是，研究useuntil函数生成的机器代码是有学习知道意义的。 Go具有自己的汇编语法。我不会在这里讨论所有细节，但是下面是带注释的（带有＃注释）汇编实现，应该很容易阅读。我删除了一些垃圾回收器（garbage collector）的指令（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 会对块进行重新排序，以使 body flows直接流入cond，从而避免每次迭代产生额外的跳跃。如果您有兴趣，请参见ssa/looprotate.go了解更多详细信息。

结论

在这两篇文章中，我们以两种不同的方式实现了一条新语句，从而了解了Go编译器的一些内部结构。当然，这只是冰山一角，但我希望它为您自己开始探索提供了一个良好的起点。

最后一点：我们在这里构建了一个可运行的编译器，但是Go工具都无法识别新的until关键字。不幸的是，此时Go工具使用了完全不同的方法来解析Go代码，并且没有与Go编译器本身共享此代码（例如gopls ，golint，所以不能针对新关键字自动实现自动补全之类的功能）。我将在以后的文章中详细介绍如何使用工具处理Go代码。

附录-复现这些结果

要重现我们最终在此处使用的Go工具链的版本，您可以从第1部分开始，在 walk.go中还原 AST 转换代码，然后添加上述 AST-> SSA转换。或者，您也可以从我的仓库上抓取adduntil2分支。

要获得从所有SSA的untilSSA，并在单个方便的HTML文件中传递代码生成，请在构建新编译器后运行以下命令：

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

然后在浏览器中打开ssa.html。如果您还想查看控制流图的某些 pass，请在函数名后添加 pass 名，并以:分隔。 例如 GOSSAFUNC=useuntil:number_lines.

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

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