漫談 Go 語言編譯器（01）

開場白

我（史斌）曾在 Gopher China 2020 大會上分享過《Go 語言編譯器簡介》（https://github.com/gopherchina/conference/tree/master/2020）。當時僅僅是泛泛的瀏覽了一下 Go 編譯器，但其實每一頁 PPT 都能單獨展開講。因此我準備寫一系列文章，把當時未能詳細闡述的內容補充一下。

歡迎轉載擴散，但請標註原創出自公衆號："Golang Contributor Club"。

**爲什麼學習編譯器
**

第四個好處是：編譯器會是未來的一個熱門行業。因爲美國的制裁，當下是國內芯片行業的春天，加強中國芯的建設已經成爲一個政治任務。而處理器（CPU/GPU/NPU/TPU/.../xPU）作爲芯片領域的重要分支，是需要編譯器支持的。當前國內編譯器領域嚴重缺人，因爲入門難度高，起薪自然比其它容易入門的領域高。（我的團隊長期招人，歡迎砸簡歷。）

第五個好處是：你可以基於 Go 編譯器定製自己的編程語言。Go 編譯器從 go-1.7 開始已經實現模塊化，這意味着你可以自己設計一個全新的編程語言（甚至不兼容 Go 語法），藉助 Go 編譯器編譯成一個可執行程序。

閱讀前的準備

雖然本系列的定位是科普文，但是我也不準備從最基本的正則表達式，語法樹，有向圖等最基礎的知識講起；因此假設讀者有一定的知識基礎。

在這個前提下，我希望你看過我在 Gopher China 2020 上的講座，並閱讀過 PPT（https://github.com/gopherchina/conference/tree/master/2020）。

除此之外，我希望你閱讀過柴樹杉大神寫的《Go 語法樹入門》（https://github.com/chai2010/go-ast-book），這是關於編譯前端非常優秀的入門書籍。在此基礎上，本系列的重點是講解編譯中端和後端。

坦白地說，編譯器確實是最難入門的領域；同時也是最難寫科普文的領域：專業人士看了覺得淺顯，沒相關基礎的讀者看了覺得雲山霧罩。雖然如此，我還是想挑戰一下。希望能收到讀者更多反饋，我會據此調節講解的內容。

基礎知識回顧

目前成熟的生產環境用的編譯器，都是基於久經考驗的前中後三階段架構。

其中前端將高級語言的源代碼翻譯成 IR（Intermediate Representation）序列，並傳遞給中端；中端對輸入的原始 IR 序列做通用優化，並輸出優化後的 IR 序列給後端；後端接收中端傳來的 IR 序列，將其映射成真正的彙編指令序列，並做進一步和硬件相關的特殊優化。最終經過鏈接生成可執行程序。

這種架構的第一個好處是：新的高級語言無需支持所有的硬件，僅需生成 IR 即可；新的硬件無需適配所有的高級編程語言，僅需適配 IR 即可。從因果關係上看，前端和後端各自都是一個子編譯器，前端把高級語言編譯成 IR 序列，IR 對於前端就是（僞）彙編；而後端把 IR 編譯成真彙編，IR 對於後端就是（僞）高級語言。

這種架構的第二個好處是：避免重複性的優化。例如把'a*8'優化成'a<<3'在所有的硬件上都適用。因此沒必要每個後端都做一遍，把這個優化放在中端一次性完成即可。

這種架構的第三個好處是：針對 SSA（Single Static Assignment）形態的 IR，已經有無數計算機科學家做了大量細緻的研究，有非常成熟的優化算法可以借鑑。編譯原理最經典的教材龍書的作者，就因爲在此領域的開創性貢獻獲得了 2021 年度的圖靈獎。

Go 編譯器

Go 編譯器在 go-1.7 之前，採用的是非常老舊的語法樹（AST）覆蓋的編譯技術，從 go-1.7 開始逐步採用更主流的基於 SSA-IR 的前中後三階段編譯技術。雖然 Go 編譯器無需支持別的高級編程語言，但是上述的第二點和第三點好處仍然適用。

一個額外的好處是，Go 編譯器的中端和後端被做成了獨立的庫 "golang.org/x/tools/go/ssa"。這就意味着，你可以自己寫一個新的語言前端（甚至不兼容 Go 語法），並調用 Go 的 ssa 庫，生成可執行程序；甚至於你自己定義的編程語言可以無縫地調用其它 Go 的代碼；進一步，你可以藉助於 Go 的生態系統打造自己的編程語言！類似於 Scala 語言和 Java 語言的關係。

SSA-IR

SSA-IR（Single Static Assignment）是一種介於高級語言和彙編語言的中間形態的僞語言，從高級語言角度看，它是（僞）彙編；而從真正的彙編語言角度看，它是（僞）高級語言。

顧名思義，SSA（Single Static Assignment）的兩大要點是：

例如有如下 Go 源代碼：

func foo(a, b int) int {
  c := 8
  return a*4 + b*c
}

它改寫成 SSA 形式是：

func foo(a, b int) int {
  c := 8
  t0 := a * 4
  t1 := b * c
  t2 := t0 + t1
  return t2
}

它被中端優化後的 SSA 形式是：

func foo(a, b int) int {
  t0 := a << 2
  t1 := b << 3
  t2 := t0 + t1
  return t2
}

說到這裏，敏感的讀者可能會問：如果只有賦值，那麼程序豈不是隻有順序結構，而分支結構和循環結構是如何支持的？因此這裏要提前劇透一點，Go 編譯器的 IR 不僅有 SSA，還有 if-goto 指令；Go 語言的 if 語句和 for 循環語句，都是會被編譯成 if-goto 指令。事實上在結構化編程（順序 / 分支 / 循環）概念出現之前，就是因爲 goto 語句的濫用而導致了 1960 年代的第一次軟件工程危機。說白了程序運行實際上還是依賴 goto，而 if/for 語句只是爲了讓程序更具有可讀性，減少潛在 bug。下面是一個小例子：

func foo(a, b int) int {
  if (a > b) {
    return a + b
  } else {
    return a - b
}

它被編譯器前端翻譯成 IR 後是如下形態（注意：if-goto-else-goto 是一個整體的單條指令，條件 / 真目的地 / 假目的地是它的三個操作數，就像除法指令有被除數和除數兩個操作數一樣）：

func foo(a, b int) int {
  c := a > b
  if (c) goto _true; else goto _false;
_true:
  t0 := a + b
  return t0
_false:
  t1 := a - b
  return t1
}

後續文章會逐步對 Go 的 IR 做完整的介紹。這裏舉兩個最簡單的例子，便於讀者快速瞭解 IR 的核心概念和常見形態。

實操

Go 編譯器提供了完備的調試手段，正好我們可以借用過來展示 Go 編譯器的內部工作流程。本系列文章使用 go-1.14.15 做演示，請讀者安裝此版本。

下面用一個例子 test.go：

// test.go
package main
func foo(a, b int) int {
  c := 8
  return a*4 + b*c
}
func main() {
  println(foo(100, 150))
}

使用如下命令編譯，在得到可執行目標程序的同時，還會得到一個額外的 ssa.html，這個 ssa.html 就記錄了 Go 編譯器的工作流程和各階段的中間結果。其中 GOSSAFUNC 環境變量用於指定需要被調試的函數，本例中是 foo。

$ GOSSAFUNC=foo go build a.go
# command-line-arguments
dumped SSA to ./ssa.html

打開 ssa.html，可以看到編譯 foo 函數一共經過了 40 多道工序。

其中，source 和 AST 屬於編譯器前端，從 start 到 writebarrier 屬於編譯器中端，從 lower 到 genssa 屬於編譯器後端。

這其中的 start/writebarrier/genssa 三道工序的輸出，請讀者認真看一下。

start 工序是編譯器前端的最後一步，輸出原始 IR 序列，請讀者對照源碼仔細體會。v10 對應變量 c，v11 對應第一個乘法運算的乘數 4，v12 是第一個乘法的積，v13 是第二個乘法的積，v14 是加法的和。

start
b1:
v1 (?) = InitMem <mem>
v2 (?) = SP <uintptr>
v3 (?) = SB <uintptr>
v4 (?) = LocalAddr <*int> {a} v2 v1
v5 (?) = LocalAddr <*int> {b} v2 v1
v6 (?) = LocalAddr <*int> {~r2} v2 v1
v7 (4) = Arg <int> {a} (a[int])
v8 (4) = Arg <int> {b} (b[int])
v9 (?) = Const64 <int> [0]
v10 (?) = Const64 <int> [8] (c[int])
v11 (?) = Const64 <int> [4]
v12 (6) = Mul64 <int> v7 v11
v13 (6) = Mul64 <int> v8 v10
v14 (6) = Add64 <int> v12 v13
v15 (6) = VarDef <mem> {~r2} v1
v16 (6) = Store <mem> {int} v6 v14 v15
Ret v16 (+6)

writebarrier 是編譯器中端的最後一步，輸出經通用優化後的 IR 序列。讀者可以看到，最初的乘法運算（Mul64）被優化成了移位運算（Lsh64x64）。

writebarrier [549 ns]
b1:
v1 (?) = InitMem <mem>
v2 (?) = SP <uintptr>
v6 (?) = LocalAddr <*int> {~r2} v2 v1
v7 (4) = Arg <int> {a} (a[int])
v8 (4) = Arg <int> {b} (b[int])
v15 (6) = VarDef <mem> {~r2} v1
v9 (+6) = Const64 <uint64> [2]
v5 (6) = Const64 <uint64> [3]
v12 (+6) = Lsh64x64 <int> [false] v7 v9
v13 (6) = Lsh64x64 <int> [false] v8 v5
v14 (6) = Add64 <int> v12 v13
v16 (6) = Store <mem> {int} v6 v14 v15
Ret v16 (+6)

而 genssa 是後端的最後一步，輸出真正的最優的 x86_64 彙編序列。

小結和展望

本文介紹了理解 Go 編譯器的所需背景知識，以及 Go 編譯器的整體工作流程。後續的文章會逐步針對上面的各道工序展開講解。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/0q0k8gGX56SBKJvfMquQkQ