摘要

本文中介紹了 Go 編譯器的整體編譯流程脈絡(luò)和一個(gè)編譯優(yōu)化錯(cuò)誤導(dǎo)致數(shù)據(jù)越界訪問(wèn)的 bug，并分析了對(duì)這個(gè) bug 的排查和修復(fù)過(guò)程，希望能夠借此讓大家對(duì) Go 編譯器有更多的了解，在遇到類(lèi)似問(wèn)題時(shí)有排查思路。

緣起

某日，一位友人在群里招呼我，“看到有人給 Go 提了個(gè)編譯器的 bug，挺有意思，感覺(jué)還挺嚴(yán)重的，要不要來(lái)看看?”于是我打開(kāi)了 issue 40367[1] 。彼時(shí)，最新一條評(píng)論是 這條[2] ：

提到將循環(huán)體中的一個(gè)常數(shù)從 1 改成 2 就無(wú)法復(fù)現(xiàn)問(wèn)題，這頓時(shí)勾起了我的興趣，于是我準(zhǔn)備研究一番。

bug 代碼跟現(xiàn)象如下圖，正常來(lái)看，代碼應(yīng)該在輸出 "5 6" 后停止，然而實(shí)際上卻無(wú)限執(zhí)行了下去，只能強(qiáng)行終止或等待程序觸碰到無(wú)權(quán)限內(nèi)存地址之后崩潰。

首先，我們要定位到這個(gè)問(wèn)題具體的直接原因。簡(jiǎn)單來(lái)說(shuō)，這個(gè) bug 是 for-range loop 越界，原本循環(huán)應(yīng)該在循環(huán)次數(shù)到達(dá)數(shù)組長(zhǎng)度后終止，但是這個(gè)復(fù)現(xiàn)程序中的循環(huán)無(wú)限執(zhí)行了下去。乍一看，問(wèn)題像是有 bound check 被優(yōu)化掉了，那么我們來(lái)實(shí)錘一下。有一個(gè)方便的網(wǎng)站，可以在線觀察給定程序編譯產(chǎn)出的匯編結(jié)果，我用 這個(gè)網(wǎng)站[3] 分別生成了原復(fù)現(xiàn)程序和將第六行的 +1 改為 +2 后不復(fù)現(xiàn)程序的匯編，供大家對(duì)比。拋開(kāi)無(wú)關(guān)細(xì)節(jié)不提，可以很容易地看到前者的匯編相較于后者的確少了一次判斷，導(dǎo)致循環(huán)無(wú)法終止，具體的位置是第二段代碼的 105 行：

既然直接原因已經(jīng)定位到了，那接下來(lái)我們就要想辦法追進(jìn)編譯器來(lái)查看為什么匯編結(jié)果有問(wèn)題了。對(duì)很多同學(xué)來(lái)說(shuō)，追進(jìn)編譯器查問(wèn)題的過(guò)程可能比較陌生，聽(tīng)起來(lái)就令人望而卻步，那么我們?nèi)绾蝸?lái)排查這個(gè)問(wèn)題呢?

背景知識(shí)

在追蹤這個(gè)具體問(wèn)題之前，我們需要先了解一些相關(guān)知識(shí)背景。

Go 編譯器的大體運(yùn)行流程

想要追查 Go 編譯器的問(wèn)題，首先就需要了解 Go 編譯器的大致運(yùn)行流程。其實(shí) Go 的編譯器的實(shí)現(xiàn)中規(guī)中矩，相比于 GCC/Clang 等老牌編譯器甚至有些簡(jiǎn)陋，許多優(yōu)化并未實(shí)現(xiàn)。一個(gè) Go 程序在生成匯編前的工作大概分為這幾步：

語(yǔ)法解析。由于 Go 語(yǔ)言語(yǔ)法相當(dāng)簡(jiǎn)單，所以 Go 編譯器使用的是一個(gè)手寫(xiě)的 LALR (1) 解析器，這部分跟今天的 bug 無(wú)關(guān)，細(xì)節(jié)略過(guò)不提。

類(lèi)型檢查。Go 是強(qiáng)類(lèi)型靜態(tài)類(lèi)型語(yǔ)言，在編譯期會(huì)對(duì)賦值、函數(shù)調(diào)用等過(guò)程做類(lèi)型檢查，判斷程序是否合法。另外，這個(gè)步驟會(huì)將一些 Go 自帶的泛型函數(shù)變換成具體類(lèi)型的函數(shù)調(diào)用，比方說(shuō) make 函數(shù)，在類(lèi)型檢查階段會(huì)根據(jù)類(lèi)型檢查的結(jié)果變換成具體的 makeslice/makemap 等。這部分也跟今天的 bug 無(wú)關(guān)。

中間代碼 (IR)生成。為方便做跨平臺(tái)代碼生成，也為方便做編譯優(yōu)化，現(xiàn)代編譯器通常會(huì)將語(yǔ)法樹(shù)變成一個(gè)中間代碼表示形式，這個(gè)表示形式的抽象程度通常是介于語(yǔ)法樹(shù)和平臺(tái)匯編之間。Go 選擇的是一種靜態(tài)單賦值 (SSA)形式的中間代碼。這部分較為重要，接下來(lái)一個(gè)小節(jié)會(huì)展開(kāi)詳述一下。

編譯優(yōu)化。在生成了 SSA IR 之后，編譯器會(huì)基于這個(gè) IR 跑很多趟(pass)代碼分析和改寫(xiě)，每個(gè) pass 會(huì)完成一個(gè)優(yōu)化策略。另外值得一提的是，Go 中很多強(qiáng)度削減類(lèi)的策略是使用一種 DSL 描述，然后代碼生成出實(shí)際的 pass 代碼來(lái)的，不過(guò)這塊跟今天內(nèi)容沒(méi)什么關(guān)系，感興趣的同學(xué)可以下來(lái)看看。在文章的后續(xù)內(nèi)容中，我們就會(huì)定位到導(dǎo)致本文中這個(gè) bug 的具體的 pass，并看到那個(gè) pass 中有問(wèn)題的邏輯。

這幾步之后，編譯器就已經(jīng)準(zhǔn)備好生成最終的平臺(tái)匯編代碼了。

靜態(tài)單賦值形式

靜態(tài)單賦值的含義是，在這種類(lèi)型的 IR 中，每一個(gè)變量只會(huì)被賦值一次。這種形式的好處我們不再贅述，僅以一段簡(jiǎn)單的 Go 代碼作為實(shí)例幫助大家理解 SSA IR 的含義。

這里是一個(gè)簡(jiǎn)單的例子，右側(cè)是 Go 代碼所對(duì)應(yīng)的 SSA IR?？梢钥吹?，整個(gè)代碼被切分成了多塊，每個(gè)代碼塊 (block)的代碼以 bXX 作為開(kāi)頭，另外在縮進(jìn)所對(duì)應(yīng)的結(jié)尾能夠看到這個(gè) block 會(huì)跳轉(zhuǎn)到哪個(gè) block。在 block 內(nèi)部，可以看到包括常量在內(nèi)的每個(gè)值都會(huì)有一個(gè)單獨(dú)的名字，比如變量 a 在 Go 代碼的 4、5 行的兩次賦值，在 SSA IR 中對(duì)應(yīng)了 v7 和 v11 兩個(gè)值。

但是，如果是代碼中包含了 if 等語(yǔ)句，在編譯時(shí)不能確定需要使用哪個(gè)值，在 SSA IR 中如何表示呢?例子中正好有這樣的代碼，可以看到 Go 代碼中第六行的 if。實(shí)際上，SSA IR 中有一個(gè)專(zhuān)門(mén)的 phi 操作符，就是為了這種情況設(shè)計(jì)，phi 操作符的含義是，返回值可能是參數(shù)的多個(gè)值中的任意一個(gè)，但是具體究竟是哪個(gè)值，需要取決于這個(gè) block 此次運(yùn)行是從哪個(gè) block 跳轉(zhuǎn)而來(lái)。在上圖中，可以看到 b2 就有一個(gè) phi 運(yùn)算符，v22 可能等于 v11 或 v21，具體等于哪個(gè)值需要看 b2 的上一個(gè)塊究竟是 b1 還是 b3，實(shí)際上就對(duì)應(yīng)了 if 條件的成立或不成立。當(dāng)然，這個(gè)例子中 if 顯然成立，只不過(guò)我們這里看到的 SSA IR 是未經(jīng)過(guò)優(yōu)化的 IR，在實(shí)際的編譯過(guò)程中，這里會(huì)被優(yōu)化掉。

Go 編譯器提供了非常方便的功能，可以查看各個(gè)優(yōu)化 pass 前后的 SSA IR，只需要在編譯時(shí)，增加一個(gè) GOSSAFUNC=xxx 環(huán)境變量即可，xxx 即為想要分析的函數(shù)的名字，因?yàn)?Go 編譯器內(nèi)部的優(yōu)化都是函數(shù)級(jí)別的。比如上圖的例子，只需要運(yùn)行 GOSSAFUNC=main go build ssaexample.go，編譯器就會(huì)將 SSA IR 結(jié)果輸出到當(dāng)前目錄的 ssa.html 中，用瀏覽器打開(kāi)即可。

排查過(guò)程

追查出問(wèn)題的優(yōu)化策略

了解了這么多前置知識(shí)，我們終于可以來(lái)追查這個(gè)具體的 bug 成因了。第一步，我們要首先通過(guò) Go 編譯器 dump 出來(lái)的 SSA IR，查看究竟是哪一個(gè) pass 出了問(wèn)題。用上一節(jié)中講到的方式，我們可以觀察 issue 中的復(fù)現(xiàn)程序的所有 SSA IR。由于 Go 編譯器的優(yōu)化 pass 不少，所以在 ssa.html 中記錄了大量的 SSA IR，我們?nèi)绾握业接袉?wèn)題的 pass 呢。對(duì)于我個(gè)人來(lái)說(shuō)，由于我之前有所了解，能夠大致猜到這種問(wèn)題是 prove pass 的 bug。但是即使大家沒(méi)有相關(guān)背景，由于我們已經(jīng)知道這個(gè) bug 的直接原因是少了一條比較判斷，所以也可以通過(guò)二分法查看哪個(gè) pass 少了一條比較指令來(lái)進(jìn)行定位。需要注意的是，大家可能會(huì)定位到 generic deadcode pass，因?yàn)檫@個(gè) pass 中少了一條 Less64 指令，如圖(我這里使用的是 Go 1.15rc1，具體輸出與編譯器版本相關(guān)，可能有所不同)，右側(cè)是 generic deadcode pass：

可以看到相比于左側(cè)，右側(cè)中 b4 里的 Less64 消失了，再觀察這條 Less64 的參數(shù)，v11 就是常量 6，也即代碼中數(shù)組的長(zhǎng)度，可以確定這條指令就是那個(gè)消失的邊界判斷。那么我們是否可以確定 bug 出在 generic deadcode pass 呢?并不能。因?yàn)檫@個(gè) pass 只是把前面 pass 中已經(jīng)變成死代碼的部分刪除掉，實(shí)際上這行 Less64 在前面已經(jīng)變成死代碼了，從左側(cè)這條指令的淺灰色可以看出來(lái)，也就是說(shuō) generic deadcode pass 其實(shí)是背鍋的。不過(guò)從這里開(kāi)始，往前查具體是哪個(gè) pass 變成的死代碼，就容易很多了，只需要在瀏覽器中點(diǎn)擊這行指令，就能將這條指令的變遷高亮出來(lái)，往前追幾個(gè) pass 很容易看到是 prove pass 出了問(wèn)題：

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

prove pass 簡(jiǎn)介

定位了出問(wèn)題的策略是 prove pass，那么接下來(lái)我們就需要看看 prove pass 究竟是干什么用的。實(shí)際上，prove pass 的功能是對(duì)全局中 SSA 值的取值范圍做一個(gè)推斷，這樣就可以消除掉許多不必要的分支判斷，是不是聽(tīng)起來(lái)就跟今天的 bug 脫不了干系?實(shí)際上，這是在 Go 編譯器中非常重要的一個(gè) pass，很多優(yōu)化都依賴(lài)于這個(gè) pass 之后得到的結(jié)果。比如，由于 Go 是內(nèi)存安全的語(yǔ)言，所以所有的 slice 取元素操作都需要做一個(gè)檢查，來(lái)判斷取元素用的下標(biāo)是否超出了 slice 的范圍，這個(gè)操作叫做 bound check。但是實(shí)際上，很多代碼中在編譯期就能確定這個(gè)下標(biāo)是否越界，那么我們就可以將原本需要在運(yùn)行期做 bound check 的檢查給消除掉，這步優(yōu)化叫做 bound check elimination，具體代碼示例比如下面這段，是從 Go 標(biāo)準(zhǔn)庫(kù)[4] 拿來(lái)的代碼:

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

可以看到，這個(gè)函數(shù)中首先進(jìn)行了 b[7] 的操作，這樣一來(lái)，編譯器在 prove pass 就可以了解到，當(dāng)程序運(yùn)行到第三行及之后時(shí)，slice b 的長(zhǎng)度是必然大于等于 7 的，因此后續(xù)操作的 bound check 都可以被 eliminate 掉。 但是，prove pass 不止會(huì)做 bound check elimination 這一個(gè)特定 pattern 的優(yōu)化，還有許多其他 pattern 也會(huì)在 prove pass 被優(yōu)化掉。那么今天的這個(gè) bug 究竟是 prove pass 中什么地方出了問(wèn)題呢?

prove pass 問(wèn)題排查

說(shuō)起代碼問(wèn)題的定位方法，可能大體上能夠分成三個(gè)流派。第一是打日志，通過(guò)在日志中加信息來(lái)定位問(wèn)題;第二是通過(guò) gdb 等 debugger 下斷點(diǎn)、單步運(yùn)行來(lái)排查問(wèn)題;第三是動(dòng)態(tài)追蹤，通過(guò) perf/systemtap/ebpf 之類(lèi)的手段來(lái)動(dòng)態(tài)觀測(cè)程序運(yùn)行時(shí)的行為。具體到 Go 編譯器這里，其實(shí)開(kāi)發(fā) Go 編譯器的 Go team 大牛們也需要日常排查問(wèn)題，也不外乎這幾種手段，但是在編譯優(yōu)化的問(wèn)題上他們更青睞第一種打日志的方式，所以他們已經(jīng)在各個(gè) pass 中預(yù)埋了許多 debug 日志，只是這些日志平常不會(huì)開(kāi)啟，需要特殊的編譯開(kāi)關(guān)。既然 prove pass 相當(dāng)復(fù)雜，我們不妨通過(guò)查日志的方式來(lái)進(jìn)一步縮小問(wèn)題排查范圍。prove pass 的 debug 日志開(kāi)關(guān)是 -d=ssa/prove/debug=1，其中 debug 后面跟的數(shù)字越大日志越詳細(xì)，我們只需要在編譯時(shí)執(zhí)行 go tool compile -d=ssa/prove/debug=1 bug.go 就能看到對(duì)應(yīng)的日志。具體到這個(gè) bug，用 debug=1 的級(jí)別能夠看到對(duì)比。如下圖，左側(cè)為復(fù)現(xiàn)程序的日志，右側(cè)為修改常量后不復(fù)現(xiàn)的程序的日志：

可以很清楚地看到，bug 程序明顯多證出了一個(gè)關(guān)系。進(jìn)一步地，通過(guò) grep 編譯器代碼中這段日志關(guān)鍵詞，就能找到只有 findIndVar 和 addLocalInductiveFacts 這兩個(gè)函數(shù)中會(huì)打這條日志，結(jié)合上下文和相關(guān)注釋不難看出實(shí)際上問(wèn)題是出在 addLocalInductiveFacts 這個(gè)函數(shù)上。addLocalInductiveFacts 具體是什么功能呢?從注釋中不難看出，這里的功能是匹配到一種特殊的代碼 pattern，即類(lèi)似 repeat until 的邏輯，在循環(huán)末尾判斷某個(gè)條件是否成立。具體這個(gè)函數(shù)中的 bug 出在何處，我們還需要進(jìn)一步用更高級(jí)別的 debug=3 來(lái)看其運(yùn)行細(xì)節(jié)：

我這里只截到了相關(guān)日志部分。能看到，在出問(wèn)題的 induction 之前，首先證得了 v10 >= v16 不成立。結(jié)合 addLocalInductiveFacts 可以發(fā)現(xiàn)，實(shí)際上編譯器是將 v10 和 v16 分別當(dāng)作了循環(huán)變量的上下界，也就是代碼中的 min 和 max 變量。但是，結(jié)合 SSA IR 不難看出，其實(shí) v16 根本不是循環(huán)變量的上界，那么問(wèn)題究竟出在哪呢?

讀 addLocalInductiveFacts 的 抽取 max 的相關(guān)代碼[5](如上圖片段)可以看出，這里的意圖其實(shí)就是從條件判斷結(jié)束后循環(huán)頭部的 phi 操作所在 block 出發(fā)，一路向前追溯，找到條件判斷的 block(if block)，然后如代碼中 1104 行，判斷 phi 操作究竟是 if 的條件成立分支邏輯，還是 else 邏輯，根據(jù)分支來(lái)判斷是否應(yīng)當(dāng)對(duì)條件進(jìn)行取反，因?yàn)槿绻?else 分支邏輯，那么意味著條件判斷結(jié)果是 false，我們需要對(duì)條件取反才能得到真正成立的邏輯條件。看到這里的代碼，相信大家已經(jīng)知道了這個(gè) bug 的根因所在。1104-1113 行代碼寫(xiě)的很清楚，如果是條件成立分支，那么 br 為 positive，如果是 else 分支，那么 br 為 negative。但是，這里并沒(méi)有判斷 phi 操作跟 if block 的間接關(guān)聯(lián)，如果 phi 操作跟 if block 沒(méi)有直接聯(lián)系，那么即使我們追溯到了 if block，也沒(méi)法知道 br 變量究竟是 positive 還是 negative，取值就是 unknown。但是在后續(xù)邏輯中，并沒(méi)有判斷 unknown，而是直接默認(rèn)按照 positive 的流程走;恰好在這個(gè) bug 復(fù)現(xiàn)程序中，phi 操作所在 block 跟 if block 的 else 分支有間接關(guān)聯(lián)，走 positive 流程自然就出了問(wèn)題。

上圖為問(wèn)題復(fù)現(xiàn)代碼的 ssa cfg 圖，能夠清楚地看出，b6 沒(méi)有與對(duì)應(yīng)的 b5 有直接關(guān)聯(lián)，而是間接關(guān)聯(lián)，命中了代碼的錯(cuò)誤路徑。

結(jié)尾

定位到了問(wèn)題，那么如何修復(fù)呢?一個(gè)很簡(jiǎn)單的方式，就是直接在 br 求值的邏輯后面，增加一個(gè) unknown 判斷邏輯，當(dāng) br == unknown 就直接退出判斷。這樣一來(lái)，prove pass 顯然會(huì)變得保守，但是可以保證正確性。加了這個(gè)檢查之后 bug 復(fù)現(xiàn)程序就運(yùn)行正常了，但是作為更加 general 的修復(fù)，我們?cè)诤瘮?shù)的入口處增加對(duì)入口 block 的判斷，確保入口 block 的確是一個(gè)循環(huán)開(kāi)頭塊，而不是什么別的恰好也能匹配上當(dāng)前 pattern 的東西。我將這個(gè)修復(fù)提交給了上游。這個(gè) bug 由于非常嚴(yán)重，而且這個(gè)修復(fù)對(duì)性能實(shí)測(cè)基本沒(méi)有太大影響，所以很快合入了 master，即 commit 7f8608047644ca34bad1728d5e2dbef041a1b3f2[6] ，并且將要 cherry pick 到仍然承諾維護(hù)的前兩個(gè)大版本 1.13 和 1.14 中。前面提到，這個(gè) patch 會(huì)讓優(yōu)化器更加保守，所以后續(xù)會(huì)通過(guò)其他修改讓優(yōu)化器恢復(fù)到之前的水平，我也已經(jīng)提交了對(duì)應(yīng)的 patch，不過(guò)由于 1.15 開(kāi)發(fā)周期已經(jīng)凍結(jié)，所以預(yù)計(jì)會(huì)在 1.16 cycle 合入 master。

相信大家通過(guò)本文已經(jīng)對(duì) Go 編譯器的運(yùn)行過(guò)程、定位 bug 的一些方式有了基本的了解?？赡艽蠹乙呀?jīng)注意到，開(kāi)頭我提到這個(gè) bug 的復(fù)現(xiàn)程序在修改一個(gè)常數(shù)為 2 之后就不再?gòu)?fù)現(xiàn)，那到底是什么原因?qū)е滦薷某?shù)之后就不復(fù)現(xiàn)了呢?相信細(xì)心的你經(jīng)過(guò)研究之后知道了答案。Happy hacking ;-)