【翻译】Go 编译器理解: 新增一个关键字语句-Part2

这是介绍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将会使用 xx_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. xy在什么地方定义的。在存在控制流的情况下,这并不容易,需要进行“优势”分析。

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

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

SSA提供了一个很好的选择。如果SSA中有z = x + y,我们会立即知道xy定义的地方(且只能是一个),并且我们会立即知道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.gopasses切片中找到,并且可以在同一文件的passOrder切片中对它们的运行顺序进行一些修改。对于现代编译器而言,优化是相当标准的。降低针对特定体系结构的指令选择,以及寄存器分配。

有关这些 passes 的更多详细信息,请参见SSA READMEthis 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
not found!