1、29 | 目標(biāo)代碼的生成和優(yōu)化（一）：如何適應(yīng)各種硬件架構(gòu)？2019-10-30 宮文學(xué)編譯原理之美進(jìn)入課程講述：宮文學(xué)時(shí)長(zhǎng) 16:11 大小 14.82M在編譯器的后端，我們要能夠針對(duì)不同的計(jì)算機(jī)硬件，生成優(yōu)化的代碼。在23 講，我曾帶你試著生成過匯編代碼，但當(dāng)時(shí)生成匯編代碼的邏輯是比較幼稚的，一個(gè)正式的編譯器后端，代碼生成部分需要考慮得更加嚴(yán)密才可以。那么具體要考慮哪些問題呢？其實(shí)主要有三點(diǎn)：指令的選擇。同樣一個(gè)功能，可以用不同的指令或指令序列來完成，而我們需要選擇比較優(yōu)化的方案。寄存器分配。每款 CPU 的寄存器都是有限的，我們要有效地利用它。指令重排序。計(jì)算執(zhí)行的次序會(huì)影響所生成的代碼

2、的效率。在不影響運(yùn)行結(jié)果的情況下，我們要通過代碼重排序獲得更高的效率。下載APP我會(huì)用兩節(jié)課的時(shí)間，帶你對(duì)這三點(diǎn)問題建立直觀認(rèn)識(shí)，然后，我還會(huì)介紹 LLVM 的實(shí)現(xiàn)策略。這樣一來，你會(huì)對(duì)目標(biāo)代碼的生成，建立比較清晰的頂層認(rèn)知，甚至可以嘗試去實(shí)現(xiàn)自己的算法。接下來，我們針對(duì)第一個(gè)問題，聊一聊為什么需要選擇指令，以及如何選擇指令。選擇正確的指令你可能會(huì)問：我們?yōu)槭裁捶且P(guān)注指令的選擇呢？我來做個(gè)假設(shè)。如果我們不考慮目標(biāo)代碼的性能，可以按照非常機(jī)械的方式翻譯代碼。比如，我們可以制定一個(gè)代碼翻譯的模板，把形如“a := b + c”的代碼都翻譯成下面的匯編代碼：那么，下面兩句代碼：將被機(jī)械地翻譯成：你

3、可以從上面這段代碼中看到，第 4 行其實(shí)是多余的，因?yàn)?r0 的值就是 a，不用再裝載一遍了。另外，如果后面的代碼不會(huì)用到 a（也就是說 a 只是個(gè)臨時(shí)變量），那么第 3 行也復(fù)制代碼1 mov b, r02 add c, r03 mov r0, a4 mov a, r05 add e, r06 mov r0, d復(fù)制代碼1 a := b + c2 d := a + e復(fù)制代碼1 mov b, r0/ 把 b 裝入寄存器 r02 add c, r0/ 把 c 加 到 r0 上3 mov r0, a/ 把 r0 存 入 a是多余的。這種算法很幼稚，正確性沒有問題，但代碼量太大，代價(jià)太高。所以我們

4、最好用聰明一點(diǎn)兒的算法來生成更加優(yōu)化的代碼。這是我們要做指令選擇的原因之一。做指令選擇的第二個(gè)原因是，實(shí)現(xiàn)同一種功能可以使用多種指令，特別是 CISC 指令集（可替代的選擇很多，但各自有適用的場(chǎng)景）。對(duì)于某個(gè) CPU 來說，完成同樣的任務(wù)可以采用不同的指令。比如，實(shí)現(xiàn)“a := a + 1”，可以生成三條代碼：也可以直接用一行代碼，采用 inc 指令，而我們要看看用哪種方法總體代價(jià)最低：第二個(gè)例子，把 r0 寄存器置為 0，也可以有多個(gè)方法：再比如，a * 7 可以用 a3 - a 實(shí)現(xiàn)：首先移位 3 位，相當(dāng)于乘 8，然后再減去一次 a，就相當(dāng)于乘以 7。雖然用了兩條指令，但是，可能消耗的總

5、的時(shí)鐘周期更少。在這里我想再次強(qiáng)調(diào)一下，無論是為了生成更簡(jiǎn)短的代碼，還是從多種可能的指令中選擇最優(yōu)的，我們確實(shí)需要關(guān)注指令的選擇。那么，我們做指令選擇的思路是什么呢？目前最成熟復(fù)制代碼1 mov $0, r0/ 賦值為立即數(shù) 02 xor r0, r0/ 異或操作3 sub r0, r0/ 用自身的值去減4 .復(fù)制代碼1 inc a復(fù)制代碼1 mov a, r02 add $1, r03 mov r0, a的算法都是基于樹覆蓋的方法，我通過一個(gè)例子帶你了解一下，什么是樹覆蓋算法。ai = b 這個(gè)表達(dá)式的意思是，給數(shù)組 a 的第 i 個(gè)元素賦值為 b。假設(shè) a 和 b 都是棧里的本地變量，i

6、是放在寄存器 ri 中。這個(gè)表達(dá)式可以用一個(gè) AST 表示。你可能覺得這棵樹看著像 AST，但又不大像，那是因?yàn)槔锩嬗?mem 節(jié)點(diǎn)（意思是存入內(nèi)存）、mov 節(jié)點(diǎn)、棧指針 (fp)。它可以算作低級(jí)（low-level）AST，是一種 IR 的表達(dá)方式，有時(shí)被稱為結(jié)構(gòu)化 IR。這個(gè) AST 里面包含了豐富的運(yùn)行時(shí)的細(xì)節(jié)信息，相當(dāng)于把LLVM 的 IR 用樹結(jié)構(gòu)來表示了。你可以把一個(gè)基本塊的指令都畫成這樣的樹狀結(jié)構(gòu)。基于這棵樹，我們可以翻譯成匯編代碼：復(fù)制代碼取出數(shù)組開頭的地址，放入 r1，fp 是棧楨的指針，a 是地址的偏移量123456load Mfp+a,r1/把把把把把4 加載到 r2r

7、i 的值乘到 r2 上，即 i*4，即數(shù)組元素的偏移量，每個(gè)元素 4 字節(jié)r2 加到 r1 上，也就是算出 ai 的地址b 的值加載到 r2 寄存器r2 寫入地址為 r1 的內(nèi)存addi 4, mul ri,add r2,r2 r2r1load Mfp+b,r2store r2, Mr1在這里，我用了一種假想的匯編代碼，跟 LLVMIR 有點(diǎn)兒像，但更簡(jiǎn)化、易讀：注意，我們生成的匯編代碼還是比較精簡(jiǎn)的。如果采用比較幼稚的方法，逐個(gè)樹節(jié)點(diǎn)進(jìn)行翻譯，代碼會(huì)很多，你可以手工翻譯試試看。用樹覆蓋的方法可以大大減少代碼量，其中用橙色的線包圍的部分被形象地叫做一個(gè)瓦片(tiling)，那些包含了操作符的瓦

8、片，就可以轉(zhuǎn)化成一條指令。每個(gè)瓦片可以覆蓋多個(gè)節(jié)點(diǎn)，所以生成的指令比較少。那我們是用什么來做瓦片的呢？原來，每條機(jī)器指令，都會(huì)對(duì)應(yīng) IR 的一些模式（Pattern），可以表示成一些小的樹，而這些小樹就可以當(dāng)作瓦片：我們的算法可以遍歷 AST，遇到上面的模式，就可以生成對(duì)應(yīng)的指令。以 load 指令為例， 它有幾個(gè)模式：任意一個(gè)節(jié)點(diǎn)加上一個(gè)常量就行，這相當(dāng)于匯編語言中的間接地址訪問；或者 mem 下直接就是一個(gè)常量就行，這相當(dāng)于是直接地址訪問。最后，地址值還可以由下級(jí)子節(jié)點(diǎn)計(jì)算出來。所以，從一棵 AST 生成代碼的過程，就是用上面這些小樹去匹配一棵大樹，并把整個(gè)大樹覆蓋的過程，所以叫做樹覆蓋算

9、法。2、4、5、6、8、9 這幾個(gè)節(jié)點(diǎn)依次生成匯編代碼。要注意的是，覆蓋方式可能會(huì)有多個(gè)，比如下面這個(gè)覆蓋方式，相比之前的結(jié)果，它在 8和 9 兩個(gè)瓦片上是有區(qū)別的：生成的匯編代碼最后兩句也不同：復(fù)制代碼/ 取出數(shù)組開頭的地址，放入 r1，fp 是棧楨的指針，a 是地址的偏移量123456load Mfp+a,r1/ 把/ 把/ 把/ 把4 加載到 r2ri 的值乘到 r2 上，即 i*4，即數(shù)組元素的偏移量，每個(gè)元素 4 字節(jié)r2 加到 r1 上，也就是算出 ai 的地址fp+b 的值加載到 r2 寄存器addi 4, mul ri,add r2,r2 r2r1addi fp+b,r2/ 把

10、地址為 r2 到值拷貝到地址為 r1 內(nèi)存里movm Mr2, Mr1你可以體會(huì)一下，這兩個(gè)覆蓋方式的差別：對(duì)于瓦片 8 中的加法運(yùn)算，一個(gè)當(dāng)做了間接地址的計(jì)算，一個(gè)就是當(dāng)成加法；對(duì)于根節(jié)點(diǎn)的操作，一個(gè)翻譯成從 store，把寄存器中的 b 的值寫入到內(nèi)存。一個(gè)翻譯成movm 指令，直接在內(nèi)存之間拷貝值。至于這兩種翻譯方法哪種更好，比較總體的性能哪個(gè)更高就行了。到目前為止，你已經(jīng)直觀地了解了為什么要進(jìn)行指令選擇，以及最常用的樹覆蓋方法了。當(dāng)然了，樹覆蓋算法有很多，比如 Maximal Munch 算法、動(dòng)態(tài)規(guī)劃算法、樹文法等，LLVM也有自己的算法。簡(jiǎn)單地說一下 Maximal Munch 算

11、法。Maximal Munch 直譯成中文，是每次盡量咬一大口的意思。具體來說，就是從樹根開始，每次挑一個(gè)能覆蓋最多節(jié)點(diǎn)的瓦片，這樣就形成幾棵子樹。對(duì)每棵子樹也都用相同的策略，這樣會(huì)使得生成的指令是最少的。注意，指令的順序要反過來，按照深度優(yōu)先的策略，先是葉子，再是樹根。這個(gè)算法是 Optimal 的算法。Optimal 被翻譯成最佳，我不太贊正這種翻譯方法，翻譯成“較優(yōu)”會(huì)比較合適，它指的是在局部，相鄰的兩個(gè)瓦片不可能連接成代價(jià)更低的瓦片。覆蓋算法除了 Optimal 的還有Optimum 的，Optimum 是全局最優(yōu)化的狀態(tài)，就是代碼總體的代價(jià)是最低的。關(guān)于其他算法的細(xì)節(jié)在本節(jié)課就不展開

12、了，因?yàn)楦鶕?jù)我的經(jīng)驗(yàn)，在學(xué)指令選擇時(shí)，最重要的還是建立圖形化的、直觀的理解，理解什么是瓦片，如何覆蓋會(huì)得到最優(yōu)的結(jié)果。接下來，我們繼續(xù)探討開篇提到的第二個(gè)問題：寄存器分配。分配寄存器寄存器優(yōu)化的任務(wù)是：最大程度地利用寄存器，但不要超過寄存器總數(shù)量的限制。因?yàn)槲覀兩?IR 時(shí)，是不知道目標(biāo)機(jī)器的信息的，也就不知道目標(biāo)機(jī)器到底有幾個(gè)寄存器可以用，所以我們?cè)?IR 中可以使用無限個(gè)臨時(shí)變量，每個(gè)臨時(shí)變量都代表一個(gè)寄存器?，F(xiàn)在既然要生成針對(duì)目標(biāo)機(jī)器的代碼，也就知道這些信息了，那么就要把原來的 IR 改寫一下，以便使用寄存器時(shí)不。那么寄存器優(yōu)化的原理是什么呢？我用一個(gè)例子帶你了解一下。下圖左邊的 IR

13、 中，a、d、f 這三個(gè)臨時(shí)變量不會(huì)同時(shí)出現(xiàn)。假設(shè) a 和 d 在這個(gè)代碼塊之后成了死變量，那么這三個(gè)變量可以共用同一個(gè)寄存器，就像右邊顯示的那樣：實(shí)際上，這三行代碼是對(duì)“b + c + e + 10”這個(gè)表達(dá)式的翻譯，所以 a 和 d 都是在轉(zhuǎn)換為 IR 時(shí)引入的中間變量，用完就不用了。這和在 23 講，我們把 8 個(gè)參數(shù)以及一個(gè)本地變量相加時(shí)，只用了一個(gè)寄存器來一直保存累加結(jié)果，是一樣的。所以，通過這個(gè)例子，你可以直觀地理解寄存器共享的原則：如果存在兩個(gè)臨時(shí)變量 a 和b，它們?cè)谡麄€(gè)程序執(zhí)行過程中，最多只有一個(gè)變量是活躍的，那么這兩個(gè)變量可以共享同一個(gè)寄存器。在27和28 講中，你已經(jīng)學(xué)過

14、了如何做變量的活躍性分析，所以你可以很容易分析出，在任何一個(gè)程序點(diǎn)，活躍變量的集合。然后，你再看一下，哪些變量從來沒有出現(xiàn)在同一個(gè)集合中就行。看看下面的這個(gè)圖：上圖中，凡是出現(xiàn)在同一個(gè)花括號(hào)里的變量，都不能共享寄存器，因?yàn)樗鼈冊(cè)谀硞€(gè)時(shí)刻是同時(shí)活躍的。那 a 到 f，哪些變量從來沒碰到過呢？我們?cè)佼嬕粋€(gè)圖來尋找一下。下圖中，每個(gè)臨時(shí)變量作為一個(gè)節(jié)點(diǎn)，如果兩個(gè)變量同時(shí)存在過，就畫一條邊。這樣形成的圖，叫做寄存器干擾圖 (Register Interference Graph, RIG)。在這張圖里，凡是沒有連線的兩個(gè)變量，就可以分配到同一個(gè)寄存器，例如，a 和 b，b 和 d，a 和 d，b 和

15、e，a 和e。那么問題來了：針對(duì)這個(gè)程序，我們一共需要幾個(gè)寄存器？怎么分配呢？一個(gè)比較常用的算法是圖染色算法：只要兩個(gè)節(jié)點(diǎn)之間有連線，節(jié)點(diǎn)就染成不同的顏色。最后所需要的最少顏色，就是所需要的寄存器的數(shù)量。我畫了兩個(gè)染色方案，都是需要 4 種顏色：不過我們是手工染色的，那么如何用算法來染色呢？假如一共有 4 個(gè)寄存器，我們想用算法知道寄存器是否夠用？應(yīng)該如何染色？染色算法很簡(jiǎn)單。如果想知道 k 個(gè)寄存器夠不夠用，你只需要找到一個(gè)少于 k 條邊的節(jié)點(diǎn)，把它從圖中去掉。接著再找下一個(gè)少于 k 條邊的節(jié)點(diǎn)，再去掉。如果最后整個(gè)圖都被刪掉了，那么這個(gè)圖一定可以用 k 種顏色來染色。為什么呢？因?yàn)槿绻粋€(gè)

16、圖（藍(lán)色邊的）是能用 k 種顏色染色的，那么再加上一個(gè)節(jié)點(diǎn)， 它的邊的數(shù)量少于 k 個(gè)，比如是 n，那么這個(gè)大一點(diǎn)兒的圖（橙色邊的）還是可以用 k 種顏色染色的。道理很簡(jiǎn)單，因?yàn)榧舆M(jìn)來的節(jié)點(diǎn)的邊數(shù)少于 k 個(gè)，所以一定能找到一個(gè)顏色，與這個(gè)點(diǎn)的 n 個(gè)鄰居都不相同。所以，我們把剛才一個(gè)個(gè)去掉節(jié)點(diǎn)的順序反過來，把一個(gè)個(gè)節(jié)點(diǎn)依次加到圖上，每加上一個(gè)，就找一個(gè)它的鄰居沒有用的顏色來染色就行了。整個(gè)方法簡(jiǎn)單易行。但是，如果所需要寄存器比實(shí)際寄存器的數(shù)量少，該怎么辦呢？當(dāng)然是用棧了。這個(gè)問題就是寄存器溢出（Register Spilling），溢出到棧里去，我在21 講關(guān)于運(yùn)行時(shí)機(jī)制時(shí)提到過，像本地變量

17、、參數(shù)、返回值等，都盡量用寄存器，如果寄存器不夠用，那就放到棧里。另外再說一下，無論放在寄存器里，還是棧里，都是活動(dòng)記錄的組成部分，所以活動(dòng)記錄這個(gè)概念比棧楨更廣義。還是拿上面的例子來說，如果只有 3 個(gè)寄存器，那么要計(jì)算一下 3 個(gè)寄存器夠不夠用。我們先把 a 和 b 從圖中去掉：這時(shí)你發(fā)現(xiàn)，剩下的 4 個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都有 3 個(gè)鄰居。所以，3 個(gè)寄存器肯定不夠用，必須要溢出一個(gè)去。我們可以選擇讓 f 保存在棧里，把 f 去掉以后，剩下的 c，d，e 可以用 3 種顏色成功染色。這就結(jié)束了嗎？當(dāng)然沒有。f 雖然被保存到了棧里，但每次使用它的時(shí)候，都要 load 到一個(gè)臨時(shí)變量，也就是寄存器

18、中。每次保存 f，也都要用一個(gè)臨時(shí)變量寫入到內(nèi)存。所以，我們要把原來的代碼修改一下，把每個(gè)使用 f 的地方，都加上一條 load 或 save 指令，以便在使用 f 的時(shí)候把 f 放到寄存器，用完后再寫回內(nèi)存。修改后的 CFG 如下：因?yàn)樵瓉碛?4 個(gè)地方用到了 f，所以我們引入了 f1 到 f4 四個(gè)臨時(shí)變量。這樣的話，總的臨時(shí)變量反而變多了，從 6 個(gè)到了 9 個(gè)。不過沒關(guān)系，雖然臨時(shí)變量更多了，但這幾個(gè)臨時(shí)變量的生存期都很短，圖里帶有 f 的活躍變量集合，比之前少多了。所以，即使有 9 個(gè)臨時(shí)變量，也能用三種顏色染色，如下圖所示：最后，在選擇把哪個(gè)變量溢出的時(shí)候，你實(shí)際上是要有所選擇的。

19、你最好選擇使用次數(shù)最少的變量。在程序內(nèi)循環(huán)中的變量，就最好不要溢出，因?yàn)槊看窝h(huán)都會(huì)用到它們，還是放在寄存器里性能更高。目前為止，代碼生成中的第二項(xiàng)重要工作，分配寄存器就概要地講完了。我留給你一段時(shí)間消化本節(jié)課的內(nèi)容，在下一講，我會(huì)接著講指令重排序和 LLVM 的實(shí)現(xiàn)。課程小結(jié)目標(biāo)代碼生成過程中有三個(gè)關(guān)鍵知識(shí)點(diǎn)：指令選擇、寄存器分配和指令重排序，本節(jié)課，我講了前兩個(gè)，期望能幫你理解這兩個(gè)問題的實(shí)質(zhì)，讓你對(duì)指令選擇和寄存器分配這兩個(gè)問題 建立直觀理解。這樣你再去研究不同的算法時(shí)，腦海里會(huì)有這兩個(gè)概念的頂層的、圖形化的 認(rèn)識(shí)，事半功倍。與此同時(shí)，本節(jié)課我希望你記住幾個(gè)要點(diǎn)如下：相同的 IR 可以由不同的機(jī)器指令序列來實(shí)現(xiàn)。你要理解瓦片為什么長(zhǎng)那個(gè)樣子，并且在大腦里建立用瓦片覆蓋一棵 AST 的直觀印象，最好具備多種覆蓋方式，從而把這個(gè)問題由抽象變得具象。寄存器分配是編譯器必須要做的一項(xiàng)工作，它把可以使用無限多寄存