Go 程式到機器碼的編譯之旅
在 ofollow,noindex" target="_blank">Stream 裡,我們廣泛地使用 Go,它也的確巨大地提高了我們的生產效率。我們也發現 Go 語言效能的確出眾。自從使用了 Go 以後,我們也完成了類似於我們內部使用的基於 RPC/">gRPC, Raft 和 RocksDB 儲存引擎這類技術棧關鍵性部分的目標。
今天我們根據 Go 1.11 版本的編譯器,來看一下它是如何將我們的 Go 原始碼編譯成可執行程式的。以此我們能更加了解我們每天工作所用到的工具。我們也會看到為何 Go 語言如此之快並且編譯器在其中所起到的作用。我們會從編譯器的下述三個階段入手:
- Scanner(掃描器)將原始碼轉換為一系列的 token,以供 Parser 使用。
- Parser(語法分析器)將這些 token 轉換為 AST(Abstract Syntax Tree, 抽象語法樹),以供程式碼生成。
- 程式碼生成階段,將 AST 轉換為機器碼。
注意:我們即將使用的包(go/scanner, go/parser, go/token, go/ast 等等)實質上並沒有被 Go 編譯器使用,它們主要是提供給其他工具用來操作 Go 原始碼的。然而,實際的 Go 編譯器實現上也是類似的。這是因為 Go 編譯器最早是用 C 語言編寫的,後來才用 Go 實現了自舉。所以它仍然保持了原先的結構。
Scanner
任何編譯器所做的第一步都是將原始碼轉換成 token,這就是 Scanner (也被稱為 “詞法分析器”)所做的事。Token 可以是關鍵字,字串值,變數名以及函式名等等。任何合法的程式詞都可以用 token 來表示。具體到 Go 來說,我們就可能會得到一個 token 列表,包含 "package", "main", "func" 等等。
在 Go 中,每個 token 都以它所處的位置,型別和原始字面量來表示。Go 甚至允許我們在程式中通過 go/scanner 和 go/scanner 包來手動執行 scanner。這意味著我們可以觀察到當我們的程式經過詞法分析階段之後的樣子。為此,我們寫個程式來列印一下 Hello World 程式所生成的所有的 token。
程式如下:
package main import ( "fmt" "go/scanner" "go/token" ) func main() { src := []byte(`package main import "fmt" func main() { fmt.Println("Hello, world!") } `) var s scanner.Scanner fset := token.NewFileSet() file := fset.AddFile("", fset.Base(), len(src)) s.Init(file, src, nil, 0) for { pos, tok, lit := s.Scan() fmt.Printf("%-6s%-8s%q\n", fset.Position(pos), tok, lit) if tok == token.EOF { break } } }
我們先建立原始碼字串,然後初始化 scanner.Scanner 來掃描我們的原始碼。我們可以通過不停地呼叫 Scan() 方法來獲取 token 的位置,型別和字面量,直到遇到 EOF 標記。
當執行程式後,會得到如下輸出:
1:1package "package" 1:9IDENT"main" 1:13;"\n" 2:1import"import" 2:8STRING"\"fmt\"" 2:13;"\n" 3:1func"func" 3:6IDENT"main" 3:10("" 3:11)"" 3:13{"" 4:3IDENT"fmt" 4:6."" 4:7IDENT"Println" 4:14("" 4:15STRING"\"Hello, world!\"" 4:30)"" 4:31;"\n" 5:1}"" 5:2;"\n" 5:3EOF""
如此我們就看到了當編譯過程中 Parser 所用到的 token 了。我們也可以看到 scanner 打印出了分號,就像 C 語言等其他語言一樣。這就解釋了為什麼 Go 語言不需要寫分號,因為 scanner 給自動添加了。
Parser
當原始碼被掃描之後,結果就被傳遞給了 parser。Parser 用來在編譯過程中將 token 轉換為抽象語法樹(AST)。AST 是原始碼的一種結構化的表示方式。在 AST 中,我們能夠看出程式的結構,比如函式和常量的宣告。
Go 同樣提供了包 go/parser 和 go/ast 給我們用來解析程式和檢視 AST。我們可以這樣來列印完整的 AST:
package main import ( "go/ast" "go/parser" "go/token" "log" ) func main() { src := []byte(`package main import "fmt" func main() { fmt.Println("Hello, world!") } `) fset := token.NewFileSet() file, err := parser.ParseFile(fset, "", src, 0) if err != nil { log.Fatal(err) } ast.Print(fset, file) }
輸出:
0*ast.File { 1.Package: 1:1 2.Name: *ast.Ident { 3..NamePos: 1:9 4..Name: "main" 5.} 6.Decls: []ast.Decl (len = 2) { 7..0: *ast.GenDecl { 8...TokPos: 3:1 9...Tok: import 10...Lparen: - 11...Specs: []ast.Spec (len = 1) { 12....0: *ast.ImportSpec { 13.....Path: *ast.BasicLit { 14......ValuePos: 3:8 15......Kind: STRING 16......Value: "\"fmt\"" 17.....} 18.....EndPos: - 19....} 20...} 21...Rparen: - 22..} 23..1: *ast.FuncDecl { 24...Name: *ast.Ident { 25....NamePos: 5:6 26....Name: "main" 27....Obj: *ast.Object { 28.....Kind: func 29.....Name: "main" 30.....Decl: *(obj @ 23) 31....} 32...} 33...Type: *ast.FuncType { 34....Func: 5:1 35....Params: *ast.FieldList { 36.....Opening: 5:10 37.....Closing: 5:11 38....} 39...} 40...Body: *ast.BlockStmt { 41....Lbrace: 5:13 42....List: []ast.Stmt (len = 1) { 43.....0: *ast.ExprStmt { 44......X: *ast.CallExpr { 45.......Fun: *ast.SelectorExpr { 46........X: *ast.Ident { 47.........NamePos: 6:2 48.........Name: "fmt" 49........} 50........Sel: *ast.Ident { 51.........NamePos: 6:6 52.........Name: "Println" 53........} 54.......} 55.......Lparen: 6:13 56.......Args: []ast.Expr (len = 1) { 57........0: *ast.BasicLit { 58.........ValuePos: 6:14 59.........Kind: STRING 60.........Value: "\"Hello, world!\"" 61........} 62.......} 63.......Ellipsis: - 64.......Rparen: 6:29 65......} 66.....} 67....} 68....Rbrace: 7:1 69...} 70..} 71.} ..... // Left out for brevity 83}
在上述輸出中,你可以看到不少關於程式的資訊。在 Decls 欄位中,包含了檔案中所有宣告的列表,比如 imports, constants, variables 和 functions。在本例中只有兩個,我們 fmt 包的匯入(import)和 main 函式。
為了更加深入,我們看一下下述示意圖。它就代表了上述的資料,但只包含了型別資訊和紅色的程式碼用以標識各個節點。
main 函式由三個部分組成:函式名,定義和函式體。函式名就是取值為 main 的識別符號。Type 欄位對應的就是定義,根據情況會包含一系列的引數和返回值。函式體就是一系列的程式語句。這邊我們就一條語句。
在 AST 中我們唯一的一條 fmt.Println 語句也包含了不少東西。定義是 ExprStmt ,表示一個表示式。在這裡的話,就是一個函式呼叫。當然,有時候也可以是一個字面量,一個二元表示式(加減表示式),一個一元表示式(取負數操作)或者其他。任何函式呼叫中的引數也都是一個表示式。
我們的 ExprStmt 包含了一個 CallExpr ,也就是實際的函式呼叫。它同樣也包含了許多部分,最重要的就是 Fun 和 Args 。Fun 包含了對於函式呼叫的一個引用,在這邊就是一個 SelectorExpr 。因為我們從 fmt 包中選擇了 Println 識別符號。然而,在 AST 中編譯器並不知道 fmt 是一個包,它也有可能是一個變數。
Args 包含了一個表示函式呼叫引數的表示式列表。在本例中,我們給函式傳遞了一個字串字面量,它被表示為型別為 STRING 的一個 BasicLit 。
很顯然我們能從 AST 中推斷出很多東西。這表示我們可以更深入地觀察 AST 並從檔案中找出所有的函式呼叫。為此,我們需要使用 ast 包中的 Inspect 函式。這個函式會遍歷整棵語法樹以便於我們觀察所有節點的資訊。
為了提取出所有的函式呼叫,我們使用如下程式碼:
package main import ( "fmt" "go/ast" "go/parser" "go/printer" "go/token" "log" "os" ) func main() { src := []byte(`package main import "fmt" func main() { fmt.Println("Hello, world!") } `) fset := token.NewFileSet() file, err := parser.ParseFile(fset, "", src, 0) if err != nil { log.Fatal(err) } ast.Inspect(file, func(n ast.Node) bool { call, ok := n.(*ast.CallExpr) if !ok { return true } printer.Fprint(os.Stdout, fset, call.Fun) fmt.Println() return false }) }
這邊我們所做的就是從所有節點中找出所有型別為 *ast.CallExpr 的節點,這些節點就代表了函式呼叫。我們會通過使用 printer 包,傳入 Fun 成員變數,來列印函式的名稱。
這段程式碼的輸出如下:
fmt.Println
這也就是我們這個簡單的程式中所有並且唯一的函式呼叫。
當 AST 構建完成之後,所有的匯入都會依賴於 GOPATH,或者 Go 1.11 及以上版本中的 modules 。然後,就會執行型別檢查,並且做一些初步優化以使得程式執行的更快。
程式碼生成
當包匯入和型別檢查完成之後,我們就能確定 Go 程式程式碼是合法的並可以開始將 AST 轉換為(偽)機器程式碼了。
這個過程的第一步就是將 AST 轉換到更低一層的程式形式,具體來說就是 SSA (Static Single Assignment,靜態單賦值)。這個中間形式並非最終的機器碼但很大程式上已經差不多了。SSA 有一系列的屬性使得它更易於優化。最重要的是每個變數在使用前都必定會被預先定義,並且每個變數都會被明確地賦值過一次。
在最初版本的 SSA 生成之後,就會被進行一系列的優化。這些優化被應用於程式碼的特定階段使得處理器能夠更簡單和快速地執行。舉例來說,像 if (false) { fmt.Println(“test”) } 這類的死程式碼可以刪除,因為永遠不可能被執行到。另一個優化的例子是特定的 nil 檢查可以移除,因為編譯器可以保證它們永遠不會失敗。
現在讓我們看一下下面這個小程式的 SSA 和優化階段:
package main import "fmt" func main() { fmt.Println(2) }
你可以看到,這個程式只有一個函式和一個匯入。執行會打印出 2。然而,這個程式對於我們瞭解 SSA 來說已經足夠了。
注意:我們只展示 main 函式的 SSA,因為它才有實際意義
為了展示生成的 SSA,我們需要對要檢視 SSA 的方法設定環境變數 GOSSAFUNC,此處就是 main。我們還需要給編譯器傳遞 -S 標誌,這樣它才能列印程式碼並建立一個 HTML 檔案。我們也會針對 Linux 64-bit 環境進行編譯,從而保證生成的機器碼和你這邊看到的一樣。所以,我們執行:
$ GOSSAFUNC=main GOOS=linux GOARCH=amd64 go build -gcflags “-S” simple.go
這會列印整個 SSA,並生成一個相關聯的 ssa.html 檔案。
當你開啟 ssa.html,你會看到一系列的階段,大部分被摺疊了。最開始的階段是從 AST 生成 SSA。再然後就是將非特定機器的 SSA 轉換成特定機器的 SSA。最後生成最終的機器碼 genssa。
起始階段的程式碼看起來像這樣:
b1: v1= InitMem <mem> v2= SP <uintptr> v3= SB <uintptr> v4= ConstInterface <interface {}> v5= ArrayMake1 <[1]interface {}> v4 v6= VarDef <mem> {.autotmp_0} v1 v7= LocalAddr <*[1]interface {}> {.autotmp_0} v2 v6 v8= Store <mem> {[1]interface {}} v7 v5 v6 v9= LocalAddr <*[1]interface {}> {.autotmp_0} v2 v8 v10 = Addr <*uint8> {type.int} v3 v11 = Addr <*int> {"".statictmp_0} v3 v12 = IMake <interface {}> v10 v11 v13 = NilCheck <void> v9 v8 v14 = Const64 <int> [0] v15 = Const64 <int> [1] v16 = PtrIndex <*interface {}> v9 v14 v17 = Store <mem> {interface {}} v16 v12 v8 v18 = NilCheck <void> v9 v17 v19 = IsSliceInBounds <bool> v14 v15 v24 = OffPtr <*[]interface {}> [0] v2 v28 = OffPtr <*int> [24] v2 If v19 → b2 b3 (likely) (line 6) b2: ← b1 v22 = Sub64 <int> v15 v14 v23 = SliceMake <[]interface {}> v9 v22 v22 v25 = Copy <mem> v17 v26 = Store <mem> {[]interface {}} v24 v23 v25 v27 = StaticCall <mem> {fmt.Println} [48] v26 v29 = VarKill <mem> {.autotmp_0} v27 Ret v29 (line 7) b3: ← b1 v20 = Copy <mem> v17 v21 = StaticCall <mem> {runtime.panicslice} v20 Exit v21 (line 6)
就這個簡單的程式也生成了大量的 SSA(總共 35 行)。然而,有很多都是模版並可以被移除(最終的 SSA 版本包含 28 行並且最終的機器碼只有 18 行)。
每個 v 都是一個新變數,能夠通過點選檢視。 b's 表示語句塊。這裡我們有三個語句塊: b1 , b2 和 b3 。 b1 每次都會被執行。 b2 和 b3 是條件語句塊,可以從 b1 的末尾看到 If v19 → b2 b3 (likely) 。我們可以點選這行的 v19 來檢視它的定義。我們能夠看到它被定義為 IsSliceInBounds
編譯器也能保證這種情況。我們檢視 opt 階段(機器獨立優化),會發現 v19 被重寫成了 ConstBool
現在我們來看一下當 SSA 被轉換為特定機器的 SSA(此處為針對 amd64 架構的機器碼)之後 Go 編譯器所做的另一個簡單的優化。為此,我們要對比一下更低層的死程式碼。下面就是更低層的階段:
b1: BlockInvalid (6) b2: v2 (?) = SP <uintptr> v3 (?) = SB <uintptr> v10 (?) = LEAQ <*uint8> {type.int} v3 v11 (?) = LEAQ <*int> {"".statictmp_0} v3 v15 (?) = MOVQconst <int> [1] v20 (?) = MOVQconst <uintptr> [0] v25 (?) = MOVQconst <*uint8> [0] v1 (?) = InitMem <mem> v6 (6) = VarDef <mem> {.autotmp_0} v1 v7 (6) = LEAQ <*[1]interface {}> {.autotmp_0} v2 v9 (6) = LEAQ <*[1]interface {}> {.autotmp_0} v2 v16 (+6) = LEAQ <*interface {}> {.autotmp_0} v2 v18 (6) = LEAQ <**uint8> {.autotmp_0} [8] v2 v21 (6) = LEAQ <**uint8> {.autotmp_0} [8] v2 v30 (6) = LEAQ <*int> [16] v2 v19 (6) = LEAQ <*int> [8] v2 v23 (6) = MOVOconst <int128> [0] v8 (6) = MOVOstore <mem> {.autotmp_0} v2 v23 v6 v22 (6) = MOVQstore <mem> {.autotmp_0} v2 v10 v8 v17 (6) = MOVQstore <mem> {.autotmp_0} [8] v2 v11 v22 v14 (6) = MOVQstore <mem> v2 v9 v17 v28 (6) = MOVQstoreconst <mem> [val=1,off=8] v2 v14 v26 (6) = MOVQstoreconst <mem> [val=1,off=16] v2 v28 v27 (6) = CALLstatic <mem> {fmt.Println} [48] v26 v29 (5) = VarKill <mem> {.autotmp_0} v27 Ret v29 (+7)
在 HTML 檔案中,一些行是灰色的,這意味著它們會被移除或者在下個階段中改變。舉例來說, v15 (MOVQconst
Go 編譯器做了很多這類的優化。所以,雖然從 AST 轉換得到的最初版本的 SSA 並非最快的實現,但是編譯器會優化 SSA 得到更快速的版本。HTML 檔案中的每個階段都是一種潛在的提速。
總結
得益於編譯器和優化,Go 是一種非常高生產力和高效能的語言。如果想更加了解關於 Go 編譯器, 原始碼 中有非常不錯的 README。
如果你想了解更多關於為何 Stream 選擇了 Go 或者為何我們從 Python 遷移到 Go 的原因,可以檢視我們的 部落格 。