Go 底層探索 -一-: 編譯器
1. 介紹
@注: 以下內容來自本人學習《Go 語言底層原理剖析》書中的摘要信息。另外這本書中使用的
Go
是老版本,我使用的版本是Go1.18
有時候源碼路徑可能會不一樣
編譯器是一個大型且複雜的系統,一個好的編譯器會很好地結合形式語言理論、算法、人工智能、系統設計、計算機體系結構及編程語言理論。
Go
語言的編譯器遵循了主流編譯器採用的經典策略及相似的處理流程和優化規則(例如經典的遞歸下降的語法解析、抽象語法樹的構建)。另外,Go
語言編譯器有一些特殊的設計,例如內存的逃逸等;
1.1 爲什麼要了解 Go 語言編譯器?
通過了解Go
語言編譯器,不僅可以瞭解大部分高級語言編譯器的一般性流程與規則,也能指導我們寫出更加優秀的程序。
1.2 三階段編譯器
在經典的編譯原理中,一般將編譯器分爲編譯器前端、優化器和編譯器後端。這種編譯器被稱爲三階段編譯器(three-phase compiler
).
-
編譯器前端: 專注於理解源程序、掃描解析源程序並進行精準的語義表達;
-
優化器 (中間階段): 編譯器會使用多個
IR
階段、多種數據結構表示代碼,並在中間階段對代碼進行多次優化。例如: 識別冗餘代碼、識別內存逃逸等。編譯器的中間階段離不開編譯器前端記錄的細節. -
編譯器後端:專注於生成特定目標機器上的程序,這種程序可能是可執行文件,也可能是需要進一步處理的中間形態
obj
文件、彙編語言等.
編譯器優化並不是一個非常明確的概念。優化的主要目的一般是降低程序資源的消耗,比較常見的是降低內存與
CPU
的使用率。但在很多時候,這些目標可能是相互衝突的,對一個目標的優化可能降低另一個目標的效率。
1.3 Go 編譯器階段
Go
語言編譯器一般縮寫爲小寫的gc(go compiler)
,需要和大寫的GC
(垃圾回收)進行區分。Go
語言編譯器的執行流程可細化爲多個階段,包括詞法解析、語法解析、抽象語法樹構建、類型檢查、變量捕獲、函數內聯、逃逸分析、閉包重寫、遍歷函數、SSA 生成、機器碼生成。
和
Go
語言編譯器有關的代碼主要位於src/cmd/compile/internal
目錄下,在後面分析中給出的文件路徑均默認位於該目錄中。
2. 詞法解析
在詞法解析階段,Go
語言編譯器會掃描輸入的Go
源文件,並將其符號(token
)化。例如將表達式a :=b+c(12)
符號化之後的情形,如下圖所示:
從上圖可以看出:
-
+
操作符會被轉換爲_IncOp
; -
賦值符號
:=
會被轉換爲_Define
; -
變量名
a、b、c
會被轉換爲_Name
; -
...
實際上,這些token
就是用iota
聲明的整數常量,定義在syntax/tokens.go
文件中。如下圖:
2.1 總結歸納
-
符號化保留了
Go
語言中定義的符號,可以識別出錯誤的拼寫。 -
字符串被轉換爲整數後,在後續的階段中能夠被更加高效地處理。
3. 語法解析
詞法解析階段結束後,需要根據Go
語言中指定的語法對符號化後的Go
文件進行解析。
Go
語言採用了標準的自上而下的遞歸下降[Top-Down Recursive-Descent]
算法,以簡單高效的方式完成無須回溯的語法掃描。
如下圖示例:
源文件中的每一種聲明都有對應的語法,採用對應的語法進行解析, 能夠較快地解析並識別可能出現的語法錯誤。
3.1 總結歸納
- 語法解析階段的目的: 解析並識別可能出現的語法錯誤.
4. 抽象語法樹構建
編譯器前端必須構建程序的中間表示形式,以便在編譯器中間階段及後端使用。抽象語法樹[Abstract Syntax Tree,AST]
是一種常見的樹狀結構的中間態.
在
Go
語言源文件中的任何一種import、type、const、func
聲明都是一個根節點,在根節點下包含當前聲明的子節點。
通過使用decls
函數,將源文件中的所有聲明語句轉爲節點數組。每個節點都包含了當前節點屬性的Op
字段,以O
開頭。與詞法解析階段中的token
相同的是,Op
字段也是一個整數。不同的是,每個Op
字段都包含了語義信息, 如下圖:
《Go 語言底層原理剖析》這本書中使用的
Go
是老版本,我使用的版本是Go.18
,所以源碼路徑會有所出入.
還是以a :=b+c(12)
爲例,該賦值語句最終會變爲如圖 1-6 所示的抽象語法樹。節點之間具有從上到下的層次結構和依賴關係。
4.1 歸納總結
- 瞭解
Go
程序從源碼到抽象樹生成的邏輯步驟;
5. 類型檢查
完成抽象語法樹的初步構建後,就進入類型檢查階段,遍歷節點樹並決定節點的類型。節點的類型判斷有以下兩種情況:
-
明確指定的類型: 在語法中明確指定,例如
var a int
。 -
需要通過編譯器類型推斷得到的類型:例如,
a :=1
中的變量a
與常量1
都未直接聲明類型,編譯器會自動推斷出節點常量1
的類型爲TINT
,並自動推斷出a
的類型爲TINT
。
在類型檢查階段,會對一些類型做特別的語法或語義檢查, 例如:
-
引用的結構體字段是否是大寫可導出的?
-
數組的訪問是否超過了其長度?
-
數組的索引是不是正整數?
除此之外,在類型檢查階段還會進行其他工作。例如:計算編譯時常量、將標識符與聲明綁定等;
6. 變量捕獲
類型檢查階段完成後,Go
語言編譯器將對抽象語法樹進行分析及重構,從而完成一系列優化。
變量捕獲主要是針對閉包場景而言的,由於閉包函數中可能引用閉包外的變量,因此變量捕獲需要明確在閉包中通過值引用或地址引用的方式來捕獲變量。
6.1 舉個例子
func main() {
a := 1
b := 2
// 使用閉包
go func() {
fmt.Println(a, b)
}()
a = 99
}
上面例子中, 在 e 閉包內引入了閉包外的a、b
變量,由於變量a
在閉包之後又進行了其他賦值操作,因此在閉包中,a、b
變量的引用方式會有所不同。通過如下方式查看當前程序閉包變量捕獲的情況:
$ go tool compile -m=2 main.go | grep capturing
main.go:8:2: main capturing by ref: a (addr=false assign=true width=8)
main.go:9:2: main capturing by value: b (addr=false assign=false width=8)
上面輸出說明:
-
by ref: a
:a
採取ref
引用傳遞的方式, -
by value: b
:b
採取了值傳遞的方式。 -
assign=true
:代表變量a
在閉包完成後又進行了賦值操作。
7. 函數內聯
函數內聯指將較小的函數直接組合進調用者的函數。這是現代編譯器優化的一種核心技術。
7.1 優點
函數內聯的優勢在於,可以減少函數調用帶來的開銷。對於Go
語言來說,函數調用的成本在於: 參數與返回值棧複製、較小的棧寄存器開銷以及函數序言部分的檢查棧擴容(Go
語言中的棧是可以動態擴容的);
7.2 性能對比
下面通過寫一段程序,來對比函數內聯和不內聯的性能;
package tests
import "testing"
func max(a, b int) int {
if a > b {
return a
}
return b
}
// 使用了函數內聯
func BenchmarkUseOnline(b *testing.B) {
var a = 10
for i := 0; i < b.N; i++ {
// 進行大小計算
max(a, i)
}
}
//go:noinline
func maxNotOnline(a, b int) int {
if a > b {
return a
}
return b
}
// 使用了函數內聯
func BenchmarkNotUseOnline(b *testing.B) {
var a = 10
for i := 0; i < b.N; i++ {
// 進行大小計算
maxNotOnline(a, i)
}
}
運行測試:
$ go test -bench=. tests/func_test.go
BenchmarkUseOnline-12 1000000000 0.2577 ns/op
BenchmarkNotUseOnline-12 774045170 1.558 ns/op
從上面運行結果可以看出使用了函數內聯的方法,比不使用的快了近三倍;
go:noinline
: 代表當前函數是禁止進行函數內聯優化的.
7.3 不使用內聯
Go
語言編譯器會計算函數內聯花費的成本,只有執行相對簡單的函數時纔會內聯。函數內聯的核心邏輯位於gc/inl.go
中。以下情況都不會使用函數內聯:
-
當函數內部有 for、range、go、select 等語句時,該函數不會被內聯,
-
當函數執行過於複雜(例如太多的語句或者函數爲遞歸函數)時,也不會執行內聯。
-
如果函數前的註釋中有
go:noinline
標識,則該函數不會執行內聯
如果希望程序中所有的函數都不執行內聯操作,那麼可以添加編譯器選項
-l
, 如下:# go build $ go build -gcflags="-l" main.go # go tool命令 $ go tool compile -l main.go
7.4 不內聯原因
在調試時,可以使用go tool compile -m=2
來打印調試信息,並輸出不可以內聯的原因, 如下代碼:
package tests
import (
"testing"
)
// 使用遞歸
func fib(i int) int {
if i < 2 {
return i
}
return fib(i-1) + fib(i-2)
}
func TestRun(t *testing.T) {
i := 10
fib(i)
}
打印調試信息:
$ go tool compile -m=2 tests/funcLine_test.go
tests/funcLine_test.go:8:6: cannot inline fib: recursive
tests/funcLine_test.go:14:6: can inline TestRun with cost 65 as: func(*testing.T) { i := 10; fib(i) }
tests/funcLine_test.go:14:14: t does not escape
當在編譯時加入
-m=2
標誌時,可以打印出函數的內聯調試信息。可以看出fib
函數爲遞歸函數,所以不能被內聯.
8. 逃逸分析
逃逸分析是Go
語言中重要的優化階段,用於標識變量內存應該被分配在棧區還是堆區。
在傳統的
C
或C++
語言中,開發者經常會犯的錯誤是函數返回了一個棧上的對象指針,在函數執行完成,棧被銷燬後,繼續訪問被銷燬棧上的對象指針,導致出現問題。
Go
語言能夠通過編譯時的逃逸分析識別這種問題,自動將該變量放置到堆區,並藉助Go
運行時的垃圾回收機制自動釋放內存。編譯器會盡可能地將變量放置到棧中,因爲棧中的對象隨着函數調用結束會被自動銷燬,減輕運行時分配和垃圾回收的負擔。
8.1 分配原則
在Go
語言中,開發者模糊了棧區與堆區的差別,不管是字符串、數組字面量,還是通過new、make
標識符創建的對象,都既可能被分配到棧中,也可能被分配到堆中。分配時,遵循以下兩個原則:
-
原則 1:指向棧上對象的指針不能被存儲到堆中
-
原則 2:指向棧上對象的指針不能超過該棧對象的生命週期
舉個例子:
// 全局變量
var a *int
func TestVarEscape(t *testing.T) {
// 局部變量
b := 1
// 引用變量b地址
a = &b
}
運行測試:
$ go tool compile -m=2 tests/var_test.go
tests/var_test.go:10:6: can inline TestVarEscape with cost 9 as: func(*testing.T) { b := 1; a = &b }
tests/var_test.go:12:2: b escapes to heap:
tests/var_test.go:12:2: flow: {heap} = &b:
tests/var_test.go:12:2: from &b (address-of) at tests/var_test.go:14:6
tests/var_test.go:12:2: from a = &b (assign) at tests/var_test.go:14:4
tests/var_test.go:10:20: t does not escape
tests/var_test.go:12:2: moved to heap: b # 變量b最終被分配到堆內存
在上例中,變量
a
爲全局變量,是一個指針。在函數中,全局變量a
引用了局部變量b
的地址。如果變量
b
被分配到棧中,那麼最終程序將違背原則 2,因此變量 b 最終將被分配到堆中。
9. 閉包重寫
在前面的階段,編譯器完成了閉包變量的捕獲用於決定是通過指針引用還是值引用的方式傳遞外部變量。在完成逃逸分析後,下一個優化的階段爲閉包重寫,閉包重寫分爲以下兩種情況:
-
** 閉包定義後被立即調用: ** 這種情況下, 閉包只能被調用一次, 可以將閉包轉換爲普通函數的調用形式。
-
包定義後不被立即調用: 同一個閉包可能被調用多次,這時需要創建閉包對象。
9.1 重寫示例
下面示例展示的是閉包函數,重寫後的樣子。
// 閉包定義後被立即調用
func todo() {
a := 1
func() {
fmt.Println(a)
a = 2
}()
}
閉包重寫後:
func todo() {
a := 1
func1(&a)
fmt.Println("aa:", a)
}
func func1(a *int) {
fmt.Println(*a)
*a = 2
}
10. 遍歷函數
閉包重寫後,需要遍歷函數。在該階段會識別出聲明但是並未被使用的變量,遍歷函數中的聲明和表達式,將某些代表操作的節點轉換爲運行時的具體函數執行。
例如: 獲取map
中的值會被轉換爲運行時mapaccess2_fast64
函數:
v,ok := m["foo"]
// 轉化爲
tmp,ok := runtime.mapaccess2_fast64(typeOf(m),m,"foo")
v := *tmp
字符串變量的拼接會被轉換爲調用運行時
concatstrings
函數。對於new
操作,如果變量發生了逃逸,那麼最終會調用運行時newobject
函數將變量分配到堆區。for...range
語句會重寫爲更簡單的for
語句形式。
11. SSA 生成
遍歷函數後,編譯器會將抽象語法樹轉換爲下一個重要的中間表示形態,稱爲SSA(Static Single Assignment,靜態單賦值)
。SSA
被大多數現代的編譯器(包括GCC和LLVM
)使用, 在Go 1.7
中被正式引入並替換了之前的編譯器後端,用於最終生成更有效的機器碼。
在
SSA
生成階段,每個變量在聲明之前都需要被定義,並且,每個變量只會被賦值一次。
11.1 SSA 階段作用
SSA
生成階段是編譯器進行後續優化的保證,例如常量傳播(Constant Propagation)、無效代碼清除、消除冗餘、強度降低(Strength Reduction)等.
在SSA
階段,編譯器先執行與特定指令集無關的優化,再執行與特定指令集有關的優化,並最終生成與特定指令集有關的指令和寄存器分配方式。
-
SSA lower階段之後
: 開始執行與特定指令集有關的重寫與優化。 -
genssa階段
: 編譯器會生成與單個指令對應的Prog
結構。
11.2 怎麼生成 SSA
Go
語言提供了強有力的工具查看SSA
初始及其後續優化階段生成的代碼片段,可以通過在編譯時指定GOSSAFUNC=main
實現, 使用如下:
$ GOSSAFUNC=main go tool compile main.go
dumped SSA to /Users/liuqh/ProjectItem/K8sDemo/go-app/ssa.html
打開 ssa.html
上述圖片展示了
SSA的初始階段、優化階段、最終階段的代碼片段
12. 機器碼生成 (彙編器)
在SSA
後,編譯器將調用與特定指令集有關的彙編器(Assembler)
生成obj
文件,obj
文件作爲鏈接器(Linker)
的輸入,生成二進制可執行文件。
彙編和鏈接是編譯器後端與特定指令集有關的階段。由於歷史原因,
Go
語言的彙編器基於了不太常見的plan9
彙編器的輸入形式。需要注意的是,輸入彙編器中的彙編指令不是機器碼的表現形式,其仍然是人類可讀的底層抽象。
12.1 源程序轉匯編代碼
package main
import "fmt"
func main() {
fmt.Println("hello word")
}
轉成彙編代碼:
$ go tool compile -S main.go
"".main STEXT size=103 args=0x0 locals=0x40 funcid=0x0 align=0x0
0x0000 00000 (main.go:5) TEXT "".main(SB), ABIInternal, $64-0
0x0000 00000 (main.go:5) CMPQ SP, 16(R14)
0x0004 00004 (main.go:5) PCDATA $0, $-2
0x0004 00004 (main.go:5) JLS 92
0x0006 00006 (main.go:5) PCDATA $0, $-1
0x0006 00006 (main.go:5) SUBQ $64, SP
0x000a 00010 (main.go:5) MOVQ BP, 56(SP)
0x000f 00015 (main.go:5) LEAQ 56(SP), BP
....
本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源:https://mp.weixin.qq.com/s/Evotvj5bOZab87Yh7ArP9A