如何理解Go編譯器代碼優(yōu)化bug定位和修復

這篇文章主要介紹“如何理解Go編譯器代碼優(yōu)化bug定位和修復”，在日常操作中，相信很多人在如何理解Go編譯器代碼優(yōu)化bug定位和修復問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”如何理解Go編譯器代碼優(yōu)化bug定位和修復”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

緣起

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

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

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

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

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

背景知識

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

Go 編譯器的大體運行流程

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

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

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

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

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

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

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

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

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

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

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

排查過程

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

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

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

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

prove pass 簡介

定位了出問題的策略是 prove pass，那么接下來我們就需要看看 prove pass 究竟是干什么用的。實際上，prove pass  的功能是對全局中 SSA 值的取值范圍做一個推斷，這樣就可以消除掉許多不必要的分支判斷，是不是聽起來就跟今天的 bug 脫不了干系?實際上，這是在 Go  編譯器中非常重要的一個 pass，很多優(yōu)化都依賴于這個 pass 之后得到的結(jié)果。比如，由于 Go 是內(nèi)存安全的語言，所以所有的 slice  取元素操作都需要做一個檢查，來判斷取元素用的下標是否超出了 slice 的范圍，這個操作叫做 bound  check。但是實際上，很多代碼中在編譯期就能確定這個下標是否越界，那么我們就可以將原本需要在運行期做 bound check 的檢查給消除掉，這步優(yōu)化叫做  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) }

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

prove pass 問題排查

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

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

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

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

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

結(jié)尾

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

到此，關(guān)于“如何理解Go編譯器代碼優(yōu)化bug定位和修復”的學習就結(jié)束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續(xù)學習更多相關(guān)知識，請繼續(xù)關(guān)注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>