有想過如何為 Go 語言增加一個語句嗎？

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

go compiler flow

在"rewrite AST"階段前，我們實現(xiàn)了 until 到 for 的轉(zhuǎn)換；具體來說，在gc/walk.go^[1]文件中，在編譯器進行 SSA 轉(zhuǎn)換和代碼生成之前，就已進行了類似的轉(zhuǎn)換。

在這一部分中，我們將通過在編譯流程中處理新的 until 關(guān)鍵字來覆蓋編譯器的剩余階段。

SSA

在 GC 運行 walk 變換后，它調(diào)用 buildssa(gc/ssa.go^[2])函數(shù)將 AST 轉(zhuǎn)換為靜態(tài)單賦值(SSA)形式^[3]的中間表示。

SSA 是什么意思，為什么編譯器會這樣做？讓我們從第一個問題開始；我建議閱讀上面鏈接的 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ù)其來自哪個代碼路徑來選擇一個值。它看起來是這樣的：

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

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

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

優(yōu)化是編譯器后端的重要組成部分[1^[4]]，并且通常對后端進行結(jié)構(gòu)化以促進有效和高效的優(yōu)化。再次查看此代碼段：

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

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

考慮以下代碼片段：

z?=?x?+?y

一般情況下，編譯器必須執(zhí)行數(shù)據(jù)流分析才能找到：

1. x 和 y 指的是哪個定義？存在控制語句情況下，這并不容易，并且還需要進行優(yōu)勢分析（dominance analysis）。
2. 在此定義之后使用 z 時，同樣具有挑戰(zhàn)性。

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

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

Go 編譯器中的 SSA

我們繼續(xù)描述 Go 編譯器中如何構(gòu)造和使用 SSA。SSA 是 Go 的一個相對較新的功能^[5]。除了將 AST 轉(zhuǎn)換為 SSA 的大量代碼(gc/ssa.go^[6])，其它大部分代碼都位于ssa^[7]目錄中，ssa 目錄中的 README 文件是對 Go SSA 的非常有用的說明，請閱讀一下！

Go SSA 實現(xiàn)還擁有我見過的一些最好的編譯器工具（已經(jīng)在編譯器上工作了很多年）。通過設(shè)置 GOSSAFUNC 環(huán)境變量，我們將獲得一個 HTML 頁面，其中包含所有編譯階段以及每個編譯階段之后的 IR，因此我們可以輕松地檢索出需要進行哪些優(yōu)化。額外的設(shè)置可以將控制流程圖繪制成 SVG。

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

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

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

我將移除打印輸出函數(shù)的原因是為了使輸出的 SSA 更簡潔。使用-l 進行編譯以禁用內(nèi)聯(lián)，這將導(dǎo)致對 sayhi()的微小調(diào)用（由于常量字符串而生成更多的代碼，對 fmt.Println()[2^[8]]的調(diào)用會生成更多代碼）。

產(chǎn)生的 SSA 為：

b1:

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

????b2:?←?b1?b4

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

????b3:?←?b2

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

????b4:?←?b3
????Plain?→?b2?(10)

????b5:?←?b2

????????v13?(14)?=?Copy??v14
????Ret?v13

這里要注意的有趣部分是：

• bN 是控制流圖的基本塊。
• Phi 節(jié)點是顯式的。最有趣的是對 v5 的分配。這恰恰是分配給 i 的選擇器；一條路徑來自 V4（初始化），從另一個 v10（在 i--）內(nèi)循環(huán)中。
• 出于本練習(xí)的目的，請忽略帶有的節(jié)點。Go 有一種有趣的方式來顯式地在其 IR 中傳播內(nèi)存狀態(tài)，在這篇文章中我們不討論它。如果感興趣，請參閱前面提到的 README 以了解更多詳細信息。

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

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

與往常一樣，我們的代碼將以 for 語句的處理為模型。首先，讓我們從控制流程圖開始應(yīng)該如何尋找 until 語句：

現(xiàn)在我們只需要在代碼中構(gòu)建這個 CFG。提醒：我們在第 1 部分^[9]中添加的新 AST 節(jié)點類型為 OUNTIL。我們將在 gc/ssa.go 中的state.stmt^[10]方法中添加一個新的分支語句，以將具有 OUNTIL 操作的 AST 節(jié)點轉(zhuǎn)換為 SSA。case 塊和注釋的命名應(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)一完成。

實際上，這是我們要做的全部工作，直到在編譯器的最后階段執(zhí)行語句為止！如果我們運行編譯器-像以前一樣在此代碼上轉(zhuǎn)儲 SSA：

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

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

正如預(yù)期的那樣，我們將獲得 SSA，該 SSA 在結(jié)構(gòu)上等效于條件為否的 for 循環(huán)的 SSA 。

轉(zhuǎn)換 SSA

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

1. 執(zhí)行優(yōu)化
2. 將其降低到更接近機器代碼的形式

所有這些都可以在在 ssa/compile.go 中的passes^[11]切片以及它們運行順序的一些限制passOrder^[12]切片中找到。這些優(yōu)化對于現(xiàn)代編譯器來說是相當(dāng)標準的。降低由我們正在編譯的特定體系結(jié)構(gòu)的指令選擇以及寄存器分配。

有關(guān)這些遍的更多詳細信息，請參見SSA README^[13]和這篇帖子^[14]，其中詳細介紹了如何指定 SSA 優(yōu)化規(guī)則。

生成機器碼

最后，編譯器調(diào)用 genssa 函數(shù)(gc/ssa.go^[15])從 SSA IR 發(fā)出機器代碼。我們不必修改任何代碼，因為 until 語句包含在編譯器其他地方使用的構(gòu)造塊，我們才為之發(fā)出的 SSA-我們不添加新的指令類型，等等。

但是，研究的 useuntil 函數(shù)生成的機器代碼對我們是有指導(dǎo)意義的。Go 有自己的具有歷史根源的匯編語法^[16]。我不會在這里討論所有細節(jié)，但是以下是帶注釋的（帶有＃注釋）程序集轉(zhuǎn)儲，應(yīng)該相當(dā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?()??MOVQ??8(SP),?BP
??0x0029?00041?()??ADDQ??$16,?SP
??0x002d?00045?()??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

如果您注意的話，您可能已經(jīng)注意到“cond”塊移到了函數(shù)的末尾，而不是最初在 SSA 表示中的位置。是什么賦予的？

答案是，“l(fā)oop rotate”遍歷將在 SSA 的最末端運行。此遍歷對塊重新排序，以使主體直接流入 cond，從而避免每次迭代產(chǎn)生額外的跳躍。如果您有興趣，請參閱ssa/looprotate.go^[17]了解更多詳細信息。

結(jié)論

就是這樣！在這兩篇文章中，我們以兩種不同的方式實現(xiàn)了一條新語句，從而知道了 Go 編譯器的內(nèi)部結(jié)構(gòu)。當(dāng)然，這只是冰山一角，但我希望它為您自己開始探索提供了一個良好的起點。

最后一點：我們在這里構(gòu)建了一個可運行的編譯器，但是 Go 工具都無法識別新的 until 關(guān)鍵字。不幸的是，此時 Go 工具使用了完全不同的路徑來解析 Go 代碼，并且沒有與 Go 編譯器本身共享此代碼。我將在以后的文章中詳細介紹如何使用工具處理 Go 代碼。

附錄-復(fù)制這些結(jié)果

要重現(xiàn)我們到此為止的 Go 工具鏈的版本，您可以從第 1 部分開始 ，還原 walk.go 中的 AST 轉(zhuǎn)換代碼，然后添加上述的 AST 到 SSA 轉(zhuǎn)換?；蛘撸部梢詮?span style="font-weight: bold;color: #ff3502;">我的 fork 中^[18]獲取adduntil2 分支^[19]。

要獲得所有 SSA 的 SSA，并在單個方便的 HTML 文件中傳遞代碼生成，請在構(gòu)建工具鏈后運行以下命令：

GOSSAFUNC=useuntil?/bin/go?tool?compile?-l?useuntil.go

然后在瀏覽器中打開 ssa.html。如果您還想查看 CFG 的某些通行證，請在函數(shù)名后添加通行名，以：分隔。例如 GOSSAFUNC = useuntil：number_lines。

要獲取匯編代碼碼，請運行：

/bin/go?tool?compile?-l?-S?useuntil.go

[1] 我特別嘗試避免在這些帖子中過多地講“前端”和“后端”。這些術(shù)語是重載和不精確的，但通常前端是在構(gòu)造 AST 之前發(fā)生的所有事情，而后端是在表示形式上更接近于機器而不是原始語言的階段。當(dāng)然，這在中間位置留有很多地方，并且 中間端也被廣泛使用（盡管毫無意義）來描述中間發(fā)生的一切。

在大型和復(fù)雜的編譯器中，您會聽到有關(guān)“前端的后端”和“后端的前端”以及類似的帶有“中間”的混搭的信息。

在 Go 中，情況不是很糟糕，并且邊界已明確明確地確定。AST 在語法上接近輸入語言，而 SSA 在語法上接近。從 AST 到 SSA 的轉(zhuǎn)換非常適合作為 Go 編譯器的前/后拆分。

[2] -S 告訴編譯器將程序集源代碼轉(zhuǎn)儲到 stdout；-l 禁用內(nèi)聯(lián)，這會通過內(nèi)聯(lián) fmt.Println 的調(diào)用而使主循環(huán)有些模糊。

via: https://eli.thegreenplace.net/2019/go-compiler-internals-adding-a-new-statement-to-go-part-2/

作者：Eli Bendersky^[20]譯者：keob^[21]校對：@unknwon^[22]

本文由 GCTT^[23] 原創(chuàng)編譯，Go 中文網(wǎng)^[24] 榮譽推出

參考資料