[譯] 添加一個新語句到Golang編譯器內(nèi)部-第二部分

原文鏈接

這是探討Go編譯器的兩部分系列文章中的第二篇。 在第一部分中，我們通過構(gòu)建定制版本的編譯器向Go語言添加了一條新語句。 為此，我們按照此圖介紹了編譯器的前五個階段：

image.png

在"rewrite AST"階段，最終將until 降級(lower)到 for；具體來說，在編譯器進(jìn)行SSA轉(zhuǎn)換和代碼生成之前，在gc/walk.go中， 已經(jīng)完成了對until的轉(zhuǎn)換。

在本部分中，我們將嘗試另外一種方式--在編譯器的SSA和代碼生成階段中處理新增的until語句。

SSA

在gc編譯器運行 walk轉(zhuǎn)換后，會調(diào)用gc/ssa.go 文件中的buildssa 將AST轉(zhuǎn)換為靜態(tài)單分配（SSA）形式的新中間表示（IR）。

SSA(static single assignment form)是什么意思，為什么編譯器要這樣做?讓我們從第一個問題開始;我推薦閱讀上面鏈接的SSA維基百科頁面和其他資源，但這里是一個快速解釋。

靜態(tài)單一分配意味著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被分配了多次。 如果將此代碼段轉(zhuǎn)換為SSA，我們可能會得到類似以下內(nèi)容的信息：

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

注意每個分配如何獲得唯一的變量名。 當(dāng)x重新分配了另一個值時，將創(chuàng)建一個新名稱x_1。 您可能想知道這在一般情況下是如何工作的……這樣的代碼會發(fā)生什么呢

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

如果我們簡單地將第二個賦值重命名為x_1 = 2，那么use將使用什么值？ x或x_1或...？

為了處理這種重要情況，SSA形式的IR具有特殊的phi（originally phony）功能，可根據(jù)其來自的代碼路徑來選擇一個值。 它看起來像這樣：

image.png

該phi節(jié)點由編譯器用來在分析和優(yōu)化此類IR時維護(hù)SSA，并在稍后階段由實際的機器代碼代替。

SSA名稱的靜態(tài)部分起著類似于靜態(tài)類型的作用。 這意味著在查看源代碼時（在編譯時或靜態(tài)地）每個名稱的分配都是唯一的，而在運行時可能會多次發(fā)生。 如果上面顯示的代碼示例處于循環(huán)中，則實際的x_1 = 2分配可能發(fā)生多次。

現(xiàn)在我們對什么是SSA有了基本的了解，接下來的問題是為什么。

優(yōu)化是編譯器后端的重要組成部分，后端通常是專門為促進(jìn)有效和高效的優(yōu)化而構(gòu)造的。 再次查看此代碼片段：

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

并假設(shè)編譯器要運行一個非常常見的優(yōu)化-常量傳播(constant propagation)； 也就是說，它希望在x = 1分配后用1替換x的所有用法。 怎么會這樣呢？ 它不能只找到賦值后對x的所有引用，因為x可以重寫為其他內(nèi)容（如我們的示例）。

考慮這個代碼片段

z = x + y

通常，編譯器必須執(zhí)行數(shù)據(jù)流分析才能找到：

  1. x和y指的是哪個定義。 在存在控制流的情況下，這并不容易，需要進(jìn)行優(yōu)勢分析(dominance analysis)。

  2. 在此定義之后使用z時，同樣具有挑戰(zhàn)性。

就時間和空間而言，這種分析的創(chuàng)建和維護(hù)成本很高。 而且，必須在每次優(yōu)化后（至少部分）重新運行它。

SSA提供了一個很好的選擇。 如果z = x + y在SSA中，則我們立即知道x和y所引用的定義（只能有一個?。?，并且我們立即知道在哪里使用z（此語句之后對z的所有引用）。 在SSA中，用法和定義在IR中進(jìn)行了編碼，并且優(yōu)化不會違反不變性。

Go編譯器中的SSA

我們繼續(xù)描述Go編譯器中如何構(gòu)造和使用SSA。 SSA是Go中一個相對較新的功能。除了將AST轉(zhuǎn)換為SSA的大量代碼（位于gc/ssa.go中）外，其大部分代碼都位于ssa中。

ssa目錄中的README文件是Go SSA的非常有用的說明-請閱讀一下！

Go SSA實現(xiàn)也有一些“我”見過的最好的編譯器工具。通過設(shè)置GOSSAFUNC環(huán)境變量，我們將獲得一個HTML頁面，其中包含所有編譯階段以及每個編譯階段之后的IR，因此我們可以輕松地檢測出需要進(jìn)行哪些優(yōu)化。 附加設(shè)置可以在每次通過時將控制流圖繪制為SVG。

讓我們研究一下從AST為該代碼段創(chuàng)建的初始SSA：

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

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

我將打印輸出移出usefor的原因是為了使SSA的結(jié)果更干凈。使用-l進(jìn)行編譯以禁用內(nèi)聯(lián)，使得保留sayhi()的函數(shù)調(diào)用（由于常量字符串，內(nèi)聯(lián)對fmt.Println的調(diào)用會生成更多代碼）。

產(chǎn)生的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節(jié)點是明確的。 最有趣的是分配給v5。 這正是選擇器分配給i的情況； 一條路徑來自v4（初始化程序），另一個路徑來自體循環(huán)內(nèi)部的v10 (i--)。
  • 出于本練習(xí)的目的，請忽略帶有<mem>的節(jié)點。Go有一種有趣的方式可以在其IR中顯式傳播內(nèi)存狀態(tài)，在本文中我們將不涉及。 如果有興趣，請參見上述自述文件以了解更多詳細(xì)信息。

順便說一句，這里的for循環(huán)正是我們想要將until語句轉(zhuǎn)換成的形式。

將until AST節(jié)點轉(zhuǎn)換為SSA

像往常一樣，我們的代碼將基于for語句的處理進(jìn)行建模。首先，讓我們粗略地描述一下控制流圖應(yīng)該如何處理until語句

image.png

現(xiàn)在我們只需要在代碼中構(gòu)建這個CFG。提醒:我們在第1部分中添加的新AST節(jié)點類型是OUNTIL。

我們將在gc/ssa.go中的state.stmt方法中添加一個新的switch子句，以將具有OUNTIL的AST節(jié)點轉(zhuǎn)換為SSA。塊和注釋的命名應(yīng)使代碼易于閱讀，并與上面顯示的CFG相關(guān)。

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之前完成，對于所有節(jié)點類型都是統(tǒng)一的。
事實上，這就是我們在編譯器的最后階段對于until語句所要做的一切。如果我們對于如下代碼，運行編譯器獲取SSA：

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

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

我們將得到SSA，它在結(jié)構(gòu)上與for循環(huán)相同，條件為負(fù)數(shù)，正如預(yù)期的那樣。

SSA變換

構(gòu)造初始SSA之后，編譯器會在SSA IR上執(zhí)行以下較長的遍歷過程：

  1. 執(zhí)行優(yōu)化
  2. 將其lower為更接近機器代碼的形式
    可以在ssa/compile.go的passsslice 中找到所有pass，并且在同一文件的passOrder slice 中可以限制它們的運行順序。 對于現(xiàn)代編譯器而言，優(yōu)化是相當(dāng)標(biāo)準(zhǔn)的。lower還包括針對我們正在編譯的特定體系結(jié)構(gòu)的指令選擇以及寄存器分配。
    有關(guān)這些pass的其他詳細(xì)信息，請參見SSA自述文件以及這篇博客，其中詳細(xì)介紹了如何指定SSA優(yōu)化規(guī)則。

生成機器碼

最后，編譯器調(diào)用gc/ssa.go文件中的genssa，從SSA IR發(fā)出機器代碼。
我們不需要修改任何代碼，因為until語句生成的ssa 由在編譯器中其他位置使用的構(gòu)建塊組成，我們也不需要添加新的指令類型。
然而，這對于我們研究useuntil函數(shù)的代碼生成具有指導(dǎo)意義。Go有其歷史根源的Plan9匯編語法。我不會在這里進(jìn)行所有詳細(xì)介紹，但是以下是帶注釋的（帶有＃注釋）反匯編文件，應(yīng)該比較容易理解。我刪除了一些垃圾回收器的指令（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

如果您仔細(xì)觀察的話，您可能已經(jīng)注意到cond塊移到了函數(shù)的末尾，而不是它最初在SSA表示中的位置。為什么會這樣？
答案是在最后階段在SSA上運行“l(fā)oop rotate” pass。 此pass對塊進(jìn)行重新排序，使主體直接流入cond，避免每次迭代產(chǎn)生額外的跳躍。 如果您有興趣，請參閱ssa/looprotate.go了解更多詳細(xì)信息。

結(jié)論

就是這樣!在這兩篇文章中，我們通過兩種不同的方式實現(xiàn)一個新的語句，學(xué)習(xí)了Go編譯器的一些內(nèi)部原理。當(dāng)然，這只是冰山一角，但我希望它為您開始自己的探索提供了一個良好的起點。
最后一點：我們在這里構(gòu)建了一個可運行的編譯器，但是Go工具都無法識別新的until關(guān)鍵字。不幸的是，此時Go工具使用了完全不同的路徑來解析Go代碼，并且沒有與Go編譯器本身共享此代碼。在以后的文章中，我將詳細(xì)介紹如何使用工具處理Go代碼。

附錄-重現(xiàn)這些結(jié)果

為了重現(xiàn)我們在這里結(jié)束的Go工具鏈的版本，您可以從第1部分開始，還原walk.go中的AST轉(zhuǎn)換代碼，然后添加上述的AST-> SSA轉(zhuǎn)換。
或者，您也可以從我的項目中獲取adduntil2分支。
構(gòu)建工具鏈后運行以下命令，可以在一個HTML文件中獲取所有SSA和代碼生成pass的SSA
GOSSAFUNC=useuntil <src checkout>/bin/go tool compile -l useuntil.go
然后在瀏覽器中打開ssa.html。 如果您還想查看CFG的某些pass，請在函數(shù)名后添加pass名，以:分隔。 例如

GOSSAFUNC = useuntil：number_lines。
要獲取反匯編代碼，請運行
<src checkout>/bin/go tool compile -l -S useuntil.go

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容