一例 Go 編譯器代碼優化 bug 定位和修復解析

摘要

本文中介紹了 Go 編譯器的整體編譯流程脈絡和一個編譯優化錯誤導致數據越界訪問的 bug，並分析了對這個 bug 的排查和修復過程，希望能夠藉此讓大家對 Go 編譯器有更多的瞭解，在遇到類似問題時有排查思路。

緣起

某日，一位友人在群裡招呼我，“看到有人給 Go 提了個編譯器的 bug，挺有意思，感覺還挺嚴重的，要不要來看看？”於是我打開了 issue 40367[1] 。彼時，最新一條評論是 這條[2] ：

提到將循環體中的一個常數從 1 改成 2 就無法復現問題，這頓時勾起了我的興趣，於是我準備研究一番。

bug 代碼跟現象如下圖，正常來看，代碼應該在輸出 "5 6" 後停止，然而實際上卻無限執行了下去，只能強行終止或等待程序觸碰到無權限內存地址之後崩潰。

首先，我們要定位到這個問題具體的直接原因。簡單來說，這個 bug 是 for-range loop 越界，原本循環應該在循環次數到達數組長度後終止，但是這個復現程序中的循環無限執行了下去。乍一看，問題像是有 bound check 被優化掉了，那麼我們來實錘一下。有一個方便的網站，可以在線觀察給定程序編譯產出的彙編結果，我用 這個網站[3] 分別生成了原復現程序和將第六行的 +1 改為 +2 後不復現程序的彙編，供大家對比。拋開無關細節不提，可以很容易地看到前者的彙編相較於後者的確少了一次判斷，導致循環無法終止，具體的位置是第二段代碼的 105 行：

既然直接原因已經定位到了，那接下來我們就要想辦法追進編譯器來查看為什麼彙編結果有問題了。對很多同學來說，追進編譯器查問題的過程可能比較陌生，聽起來就令人望而卻步，那麼我們如何來排查這個問題呢？

背景知識

在追蹤這個具體問題之前，我們需要先了解一些相關知識背景。

Go 編譯器的大體運行流程

想要追查 Go 編譯器的問題，首先就需要了解 Go 編譯器的大致運行流程。其實 Go 的編譯器的實現中規中矩，相比於 GCC/Clang 等老牌編譯器甚至有些簡陋，許多優化並未實現。一個 Go 程序在生成彙編前的工作大概分為這幾步：

1. 語法解析。由於 Go 語言語法相當簡單，所以 Go 編譯器使用的是一個手寫的 LALR (1) 解析器，這部分跟今天的 bug 無關，細節略過不提。
2. 類型檢查。Go 是強類型靜態類型語言，在編譯期會對賦值、函數調用等過程做類型檢查，判斷程序是否合法。另外，這個步驟會將一些 Go 自帶的泛型函數變換成具體類型的函數調用，比方說 make 函數，在類型檢查階段會根據類型檢查的結果變換成具體的 makeslice/makemap 等。這部分也跟今天的 bug 無關。
3. 中間代碼 （IR）生成。為方便做跨平臺代碼生成，也為方便做編譯優化，現代編譯器通常會將語法樹變成一箇中間代碼表示形式，這個表示形式的抽象程度通常是介於語法樹和平臺彙編之間。Go 選擇的是一種靜態單賦值 （SSA）形式的中間代碼。這部分較為重要，接下來一個小節會展開詳述一下。
4. 編譯優化。在生成了 SSA IR 之後，編譯器會基於這個 IR 跑很多趟（pass）代碼分析和改寫，每個 pass 會完成一個優化策略。另外值得一提的是，Go 中很多強度削減類的策略是使用一種 DSL 描述，然後代碼生成出實際的 pass 代碼來的，不過這塊跟今天內容沒什麼關係，感興趣的同學可以下來看看。在文章的後續內容中，我們就會定位到導致本文中這個 bug 的具體的 pass，並看到那個 pass 中有問題的邏輯。

這幾步之後，編譯器就已經準備好生成最終的平臺彙編代碼了。

靜態單賦值形式

靜態單賦值的含義是，在這種類型的 IR 中，每一個變量只會被賦值一次。這種形式的好處我們不再贅述，僅以一段簡單的 Go 代碼作為實例幫助大家理解 SSA IR 的含義。

這裡是一個簡單的例子，右側是 Go 代碼所對應的 SSA IR。可以看到，整個代碼被切分成了多塊，每個代碼塊 （block）的代碼以 bXX 作為開頭，另外在縮進所對應的結尾能夠看到這個 block 會跳轉到哪個 block。在 block 內部，可以看到包括常量在內的每個值都會有一個單獨的名字，比如變量 a 在 Go 代碼的 4、5 行的兩次賦值，在 SSA IR 中對應了 v7 和 v11 兩個值。

但是，如果是代碼中包含了 if 等語句，在編譯時不能確定需要使用哪個值，在 SSA IR 中如何表示呢？例子中正好有這樣的代碼，可以看到 Go 代碼中第六行的 if。實際上，SSA IR 中有一個專門的 phi 操作符，就是為了這種情況設計，phi 操作符的含義是，返回值可能是參數的多個值中的任意一個，但是具體究竟是哪個值，需要取決於這個 block 此次運行是從哪個 block 跳轉而來。在上圖中，可以看到 b2 就有一個 phi 運算符，v22 可能等於 v11 或 v21，具體等於哪個值需要看 b2 的上一個塊究竟是 b1 還是 b3，實際上就對應了 if 條件的成立或不成立。當然，這個例子中 if 顯然成立，只不過我們這裡看到的 SSA IR 是未經過優化的 IR，在實際的編譯過程中，這裡會被優化掉。

Go 編譯器提供了非常方便的功能，可以查看各個優化 pass 前後的 SSA IR，只需要在編譯時，增加一個 GOSSAFUNC=xxx 環境變量即可，xxx 即為想要分析的函數的名字，因為 Go 編譯器內部的優化都是函數級別的。比如上圖的例子，只需要運行 GOSSAFUNC=main go build ssaexample.go，編譯器就會將 SSA IR 結果輸出到當前目錄的 ssa.html 中，用瀏覽器打開即可。

排查過程

追查出問題的優化策略

瞭解了這麼多前置知識，我們終於可以來追查這個具體的 bug 成因了。第一步，我們要首先通過 Go 編譯器 dump 出來的 SSA IR，查看究竟是哪一個 pass 出了問題。用上一節中講到的方式，我們可以觀察 issue 中的復現程序的所有 SSA IR。由於 Go 編譯器的優化 pass 不少，所以在 ssa.html 中記錄了大量的 SSA IR，我們如何找到有問題的 pass 呢。對於我個人來說，由於我之前有所瞭解，能夠大致猜到這種問題是 prove pass 的 bug。但是即使大家沒有相關背景，由於我們已經知道這個 bug 的直接原因是少了一條比較判斷，所以也可以通過二分法查看哪個 pass 少了一條比較指令來進行定位。需要注意的是，大家可能會定位到 generic deadcode pass，因為這個 pass 中少了一條 Less64 指令，如圖（我這裡使用的是 Go 1.15rc1，具體輸出與編譯器版本相關，可能有所不同），右側是 generic deadcode pass：

可以看到相比於左側，右側中 b4 裡的 Less64 消失了，再觀察這條 Less64 的參數，v11 就是常量 6，也即代碼中數組的長度，可以確定這條指令就是那個消失的邊界判斷。那麼我們是否可以確定 bug 出在 generic deadcode pass 呢？並不能。因為這個 pass 只是把前面 pass 中已經變成死代碼的部分刪除掉，實際上這行 Less64 在前面已經變成死代碼了，從左側這條指令的淺灰色可以看出來，也就是說 generic deadcode pass 其實是背鍋的。不過從這裡開始，往前查具體是哪個 pass 變成的死代碼，就容易很多了，只需要在瀏覽器中點擊這行指令，就能將這條指令的變遷高亮出來，往前追幾個 pass 很容易看到是 prove pass 出了問題：

右側是 prove pass，可以看到這行在 prove pass 變成了灰色。

prove pass 簡介

定位了出問題的策略是 prove pass，那麼接下來我們就需要看看 prove pass 究竟是幹什麼用的。實際上，prove pass 的功能是對全局中 SSA 值的取值範圍做一個推斷，這樣就可以消除掉許多不必要的分支判斷，是不是聽起來就跟今天的 bug 脫不了干係？實際上，這是在 Go 編譯器中非常重要的一個 pass，很多優化都依賴於這個 pass 之後得到的結果。比如，由於 Go 是內存安全的語言，所以所有的 slice 取元素操作都需要做一個檢查，來判斷取元素用的下標是否超出了 slice 的範圍，這個操作叫做 bound check。但是實際上，很多代碼中在編譯期就能確定這個下標是否越界，那麼我們就可以將原本需要在運行期做 bound check 的檢查給消除掉，這步優化叫做 bound check elimination，具體代碼示例比如下面這段，是從 Go 標準庫[4] 拿來的代碼:

<code>
func
 
(bigEndian)
  
PutUint64
(b []
byte
, v 
uint64
)
 {
 _ = b[
7
]  
 b[
0
] = 
byte
(v >> 
56
)
 b[
1
] = 
byte
(v >> 
48
)
 b[
2
] = 
byte
(v >> 
40
)
 b[
3
] = 
byte
(v >> 
32
)
 b[
4
] = 
byte
(v >> 
24
)
 b[
5
] = 
byte
(v >> 
16
)
 b[
6
] = 
byte 
(v >> 
8
)
 b[
7
] = 
byte
(v)
}

可以看到，這個函數中首先進行了 b[
7
] 的操作，這樣一來，編譯器在 prove pass 就可以瞭解到，當程序運行到第三行及之後時，slice b 的長度是必然大於等於 
7
 的，因此後續操作的 bound check 都可以被 eliminate 掉。 但是，prove pass 不止會做 bound check elimination 這一個特定 pattern 的優化，還有許多其他 pattern 也會在 prove pass 被優化掉。那麼今天的這個 bug 究竟是 prove pass 中什麼地方出了問題呢？
/<code>

prove pass 問題排查

說起代碼問題的定位方法，可能大體上能夠分成三個流派。第一是打日誌，通過在日誌中加信息來定位問題；第二是通過 gdb 等 debugger 下斷點、單步運行來排查問題；第三是動態追蹤，通過 perf/systemtap/ebpf 之類的手段來動態觀測程序運行時的行為。具體到 Go 編譯器這裡，其實開發 Go 編譯器的 Go team 大牛們也需要日常排查問題，也不外乎這幾種手段，但是在編譯優化的問題上他們更青睞第一種打日誌的方式，所以他們已經在各個 pass 中預埋了許多 debug 日誌，只是這些日誌平常不會開啟，需要特殊的編譯開關。既然 prove pass 相當複雜，我們不妨通過查日誌的方式來進一步縮小問題排查範圍。prove pass 的 debug 日誌開關是 -d=ssa/prove/debug=1，其中 debug 後面跟的數字越大日誌越詳細，我們只需要在編譯時執行 go tool compile -d=ssa/prove/debug=1 bug.go 就能看到對應的日誌。具體到這個 bug，用 debug=1 的級別能夠看到對比。如下圖，左側為復現程序的日誌，右側為修改常量後不復現的程序的日誌：

可以很清楚地看到，bug 程序明顯多證出了一個關係。進一步地，通過 grep 編譯器代碼中這段日誌關鍵詞，就能找到只有 findIndVar 和 addLocalInductiveFacts 這兩個函數中會打這條日誌，結合上下文和相關注釋不難看出實際上問題是出在 addLocalInductiveFacts 這個函數上。addLocalInductiveFacts 具體是什麼功能呢？從註釋中不難看出，這裡的功能是匹配到一種特殊的代碼 pattern，即類似 repeat until 的邏輯，在循環末尾判斷某個條件是否成立。具體這個函數中的 bug 出在何處，我們還需要進一步用更高級別的 debug=3 來看其運行細節：

我這裡只截到了相關日誌部分。能看到，在出問題的 induction 之前，首先證得了 v10 >= v16 不成立。結合 addLocalInductiveFacts 可以發現，實際上編譯器是將 v10 和 v16 分別當作了循環變量的上下界，也就是代碼中的 min 和 max 變量。但是，結合 SSA IR 不難看出，其實 v16 根本不是循環變量的上界，那麼問題究竟出在哪呢？

讀 addLocalInductiveFacts 的 抽取 max 的相關代碼[5]（如上圖片段）可以看出，這裡的意圖其實就是從條件判斷結束後循環頭部的 phi 操作所在 block 出發，一路向前追溯，找到條件判斷的 block（if block），然後如代碼中 1104 行，判斷 phi 操作究竟是 if 的條件成立分支邏輯，還是 else 邏輯，根據分支來判斷是否應當對條件進行取反，因為如果是 else 分支邏輯，那麼意味著條件判斷結果是 false，我們需要對條件取反才能得到真正成立的邏輯條件。看到這裡的代碼，相信大家已經知道了這個 bug 的根因所在。1104-1113 行代碼寫的很清楚，如果是條件成立分支，那麼 br 為 positive，如果是 else 分支，那麼 br 為 negative。但是，這裡並沒有判斷 phi 操作跟 if block 的間接關聯，如果 phi 操作跟 if block 沒有直接聯繫，那麼即使我們追溯到了 if block，也沒法知道 br 變量究竟是 positive 還是 negative，取值就是 unknown。但是在後續邏輯中，並沒有判斷 unknown，而是直接默認按照 positive 的流程走；恰好在這個 bug 復現程序中，phi 操作所在 block 跟 if block 的 else 分支有間接關聯，走 positive 流程自然就出了問題。

上圖為問題復現代碼的 ssa cfg 圖，能夠清楚地看出，b6 沒有與對應的 b5 有直接關聯，而是間接關聯，命中了代碼的錯誤路徑。

結尾

定位到了問題，那麼如何修復呢？一個很簡單的方式，就是直接在 br 求值的邏輯後面，增加一個 unknown 判斷邏輯，當 br == unknown 就直接退出判斷。這樣一來，prove pass 顯然會變得保守，但是可以保證正確性。加了這個檢查之後 bug 復現程序就運行正常了，但是作為更加 general 的修復，我們在函數的入口處增加對入口 block 的判斷，確保入口 block 的確是一個循環開頭塊，而不是什麼別的恰好也能匹配上當前 pattern 的東西。我將這個修復提交給了上游。這個 bug 由於非常嚴重，而且這個修復對性能實測基本沒有太大影響，所以很快合入了 master，即 commit
7f8608047644ca34bad1728d5e2dbef041a1b3f2[6] ，並且將要 cherry pick 到仍然承諾維護的前兩個大版本 1.13 和 1.14 中。前面提到，這個 patch 會讓優化器更加保守，所以後續會通過其他修改讓優化器恢復到之前的水平，我也已經提交了對應的 patch，不過由於 1.15 開發週期已經凍結，所以預計會在 1.16 cycle 合入 master。

相信大家通過本文已經對 Go 編譯器的運行過程、定位 bug 的一些方式有了基本的瞭解。可能大家已經注意到，開頭我提到這個 bug 的復現程序在修改一個常數為 2 之後就不再復現，那到底是什麼原因導致修改常數之後就不復現了呢？相信細心的你經過研究之後知道了答案。Happy hacking ;-)

加入我們

我們是字節跳動基礎架構的圖平臺團隊，專注於構建世界一流的分佈式圖數據庫和大規模圖計算平臺，支持抖音、今日頭條等社交、推薦、風控等關鍵業務，致力於解決海量併發下 social graph 架構、推薦架構、用戶畫像、知識圖譜等場景下的關鍵技術問題，把有趣的分佈式系統技術落地，服務 10 億級別用戶，在持續招聘中。內推聯繫郵箱： [email protected] ；郵件標題： 姓名 - 工作年限 - 基礎架構 - 圖平臺 。

參考資料

[1] issue 40367:

https://github.com/golang/go/issues/40367

[2] 這條:

https://github.com/golang/go/issues/40367#issuecomment-662911846

[3] 這個網站:

https://godbolt.org/z/s9sWc4

[4] Go 標準庫:

https://golang.org/src/encoding/binary/binary.go#L130

[5] 抽取 max 的相關代碼:

https://golang.org/src/cmd/compile/internal/ssa/prove.go#L1098

[6] commit 7f8608047644ca34bad1728d5e2dbef041a1b3f2:

https://github.com/golang/go/commit/7f8608047644ca34bad1728d5e2dbef041a1b3f2

歡迎關注「字節跳動技術團隊」