摘要

本文中介紹了 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 程序在生成匯編前的工作大概分為這幾步：

語法解析。由于 Go 語言語法相當簡單，所以 Go 編譯器使用的是一個手寫的 LALR (1) 解析器，這部分跟今天的 bug 無關，細節略過不提。

類型檢查。Go 是強類型靜態類型語言，在編譯期會對賦值、函數調用等過程做類型檢查，判斷程序是否合法。另外，這個步驟會將一些 Go 自帶的泛型函數變換成具體類型的函數調用，比方說 make 函數，在類型檢查階段會根據類型檢查的結果變換成具體的 makeslice/makemap 等。這部分也跟今天的 bug 無關。

中間代碼 (IR)生成。為方便做跨平臺代碼生成，也為方便做編譯優化，現代編譯器通常會將語法樹變成一個中間代碼表示形式，這個表示形式的抽象程度通常是介于語法樹和平臺匯編之間。Go 選擇的是一種靜態單賦值 (SSA)形式的中間代碼。這部分較為重要，接下來一個小節會展開詳述一下。

編譯優化。在生成了 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] 拿來的代碼:

func (bigEndian) PutUint64(b []byte, v uint64) { 
 _ = b[7] // early bounds check to guarantee safety of writes below 
 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 中什么地方出了問題呢?

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 ;-)