如何設計三地址中間程式碼的數據結構，以便於基本塊分析和程式碼最佳化？

2015-07-27數位

問題背景：題主正在做的編譯器習作的源語言的C的子集（某種C-Minus？），而實作語言是Java。

並且IR的設計是想用龍書系的三地址指令（TAC，three-address code）來做。

龍書

講前端的部份感覺還比較直觀，而且有第二章以及附錄A的實際程式碼例子，就算是初學者也應該比較好著手學習；但是講後端的部份由於沒多少配合演示的程式碼，確實容易感到怎麽讀都似懂非懂，然後又不知道應該如何組織實際程式碼去實作書上講的知識點。

對此我自己深有體會，頭幾次讀龍書都覺得後端的部份似乎讀懂了但還是不知道該怎麽下手寫程式碼。所以很樂意來回答題主的問題，好讓後人少走彎路。

而

【Crafting a Compiler】

（編譯器構造）我覺得寫得詳細是挺詳細，就是有點淺所以讀得很不過癮；而且在前端花了太多篇幅，有很嚴重的虎頭蛇尾感。

不過這個配置或許正好符合原本作者的目標讀者群的需求吧。它前面講得詳細的部份真的很詳細，可操作性很強，倒是挺適合初學用。

=======================================================

記憶體還是檔？

現代編譯器的（主要）都是在記憶體裏一口氣完成整個編譯流程，而不向外寫中間檔的。所以題主可以主要考慮in-memory形式的IR。

例外之一是微軟的Visual C++編譯器。它繼承了以前記憶體極其緊張時的分階段式設計，將編譯器前端（c1.dll/c1xx.dll）與編譯器後端（c2.dll）分開在兩個不同的行程裏，兩者由一個驅動行程（cl.exe）協調；前端用中間臨時檔來傳遞AST/IR給後端。這個設計一直延續了下來…

像

PCC

這種老爺編譯器也是前後端分離，中間用臨時檔傳遞IR。

如果想易於開發/偵錯的話，配套設計一種文本形式的IR也是極好的。LLVM IR就是這方面一個非常好的例子。這樣會很利於單獨測試編譯器裏的某些IR變換。

受LLVM IR啟發的MicroVM的

Mu IR

也設計為有in-memory形式和配套文本形式。其中一些IR指令的in-memory版的Scala實作可以看這裏：

https:// github.com/microvm/micr ovm-refimpl2/blob/master/src/main/scala/uvm/ssavariables/ssavariables.scala
就是不知道下面的三地址形式的中間程式碼不知道如何存放，是直接放到一個檔還是放在記憶體中的數據結構

所以回答這個問題：請先考慮以in-memory形式為主，這個是主幹；然後可選的，作為利於偵錯的手段配套設計一種文本形式；兩種形式之間最好能做到無失真的相互轉換。

=======================================================

IR設計

然後具體要怎麽設計IR便於最佳化…這個水就深了，而且雖然有些選擇非常重要，更多的buzzword選擇其實並不真的很影響功能，而更多的是個人程式碼風格的問題。就像大括弧寫行末還是換行寫還是換行+縮排寫一樣…

我不想在「個人偏好」方面亂放炮，總之題主自己摸索一下選擇自己喜歡的就好 >_<

下面針對龍書系的三地址IR來展開。以虎書為代表的樹形IR就按下不表了。

TAC的典型實作方式是Quad（四元組），一個operator加上3個operand。其典型形式是：

op src1 , src2 , dest

或者有些記法把它記為：

dest = op src1 , src2

兩種記法指的是同一種東西。

四元組，顧名思義，其實就是一個數據結構把四個欄位打包起來：

(op, src1, src2, dest)

不過實際寫程式碼時這裏有許多東西要選擇：

是否需要顯式的「變量」結構？就是說，讓IR分為兩種結構，一種專門表示變量，一種專門表示「運算」，每個運算結果一定要賦予一個（或多個）變量；還是用一種統一的結構，既表示運算又表示該運算的值。在做高層最佳化時，使用統一結構比較易於操作；而在後端做寄存器分配的時候，有顯式的「變量」概念利於記錄寄存器分配資訊。有些編譯器會采用多層IR，在上層IR不帶顯式「變量」結構，而在底層IR帶有顯式「變量」結構。「變量」結構在實際程式碼裏可能叫作Var、Operand、Opnd之類的名字。

如果不使用顯式的「變量」，那麽operands是直接參照其它Quad IR的指令？還是用某種壓縮的形式？例如說把所有IR指令都放在一個大陣列裏，那麽operand就可以用陣列下標來表示。通常鏈式結構更易於操縱，但壓縮形式更省記憶體。習作的話我還是推薦用鏈式結構。采用下標來表示operand最麻煩的就是假如IR陣列代表了執行順序，而我們要在某個IR指令前面插入幾條新的IR指令的話，後面的IR的下標就全都要重新計算一遍並且更新，特別麻煩——當然也有應對的解決辦法…

IR指令是否需要串起來？要的話，用陣列（或例如ArrayList）還是連結串列？連結串列的話用單向連結串列還是用雙向鏈？這裏也是，通常鏈式結構更容易操縱，我會推薦先用鏈式結構來實作。

控制流，是在IR裏設計一種LabelNode來表達跳轉目標，還是使用顯式的CFG（基本塊構成的控制流圖）+Quad，還是把控制依賴跟數據依賴融合到同一種表現形式（PDG）？傳統做法是CFG+Quad，龍書預設大家都是這麽做的。

Quad是用傳統的非SSA形式，還是用SSA形式？

如果用SSA形式的話，是只對local variable（也叫scalar variable）做SSA，還是對記憶體也做SSA（memory-SSA或者heap-SSA）？

如果用傳統形式的話，是否或者如何維護use-def關系？是在輔助數據結構裏維護ud鏈（use-def chain），還是fud鏈（factored use-def chain），等等？

我的習慣是直接進SSA形式，然後在IR裏一直保持SSA形式一直到寄存器分配做完才退到傳統形式，但也有很多人正好相反，幾乎全程都用傳統形式，只在中間的特定最佳化階段轉入SSA形式。

…還有很多

別著急，上面這些問題都不是「致命選擇」。條條道路通羅馬，雖然有些路走起來會有點崎嶇…題主不要害怕，一開始每個地方都隨便選一種做法就好了。後面寫得多了就會慢慢體會到某些選擇或許選別的路更好，重要的是最初要邁出第一步做出第一個選擇。

采用最最最傳統的方式來做的話，可能會寫成：

enum Opcode { // add, sub, mul, div, load, store, if, goto, call, return, label ... } // 變量 class Var { // ... } // 一條IR指令 class Quad { // 四元組 Opcode op ; // 單獨把opcode寫做一個欄位挺不Java的，許多C/C++寫的編譯器喜歡這樣，Java可以用繼承 Var src1 ; Var src2 ; Var dest ; Quad prev , next ; // 雙向鏈 } // 整體IR class IR { Quad head ; // 用一個線性連結串列來表示整個函式的邏輯；沒有顯式CFG，用label來指定跳轉目標 }

這樣用單一結構體（例中Quad類）作為IR的指令的做法常見於用C寫的編譯器。Java的話可以對IR型別建立一套類層次，透過不同的子類別來表達不同opcode的語意；這些子類別也不需要采用同樣的layout——有些子類別可以只要更少的欄位（例如實作單目運算子就只需要1個src operand），而有些可能需要更多欄位。

龍書的第二章和附錄A所演示的前端範例生成的中間程式碼是一種用label表達控制流的線性程式碼，沒有顯式構造CFG。這種程式碼可以很直觀的對映到上面的IR設計。

但是後續要做最佳化需要控制流資訊時，還是得遍歷一次這個線性IR去顯式構造CFG，我覺得反而麻煩…

如果是要做一個非常非常簡單的編譯器，其middle-end到back-end只有一種IR貫穿其中的話，那采用這種IR也有一定道理：它在從AST轉譯過來的時候不需要顯式建立CFG，而最終要生成目標機器碼時對應關系比較好——目標機器也多半不會有顯式的CFG概念，而是用label+有fallthrough語意的branch來實作條件控制流，正好跟這種IR一樣。這就可以讓中間需要CFG的最佳化變得完全是可選的，而不必一開始就非得實作CFG不可。

但是，一旦開始想認真做更多最佳化，這種IR就會讓人感到特別蛋疼…

然後假如不要變量、要CFG、要SSA的話，可能會寫成：

enum Opcode { // add, sub, mul, div, load, store, if, goto, call, return, phi ... } // 一條IR指令 class Quad { // 四元組 Opcode op ; Quad src1 ; // 直接使用別的指令作為operand Quad src2 ; // 不需要指定dest; 自身就代表了運算和值 Quad prev , next ; // 雙向鏈 } // 一個基本塊 class BasicBlock { Quad head ; // 用一個線性連結串列來表示整個基本塊的邏輯；末尾必須是控制流指令；中間不包括phi ArrayList < Quad > phis ; // 記錄該基本塊開頭所需的phi指令 // ArrayList<BasicBlock> successors; // 後繼基本塊；該資訊可以從該基本塊末尾的控制流指令提取，不需要顯式用欄位記錄 // ??? flags; // 可選的額外資訊，可以用來記錄諸如按reverse post-order（RPO）遍歷CFG的序號，是否是迴圈開頭（loop header），等等 } class IR { BasicBlock start ; // 起始基本塊 // List<BasicBlock> blocks; // 所有基本塊 // 雖然從start肯定能順著CFG遍歷到所有活著的基本塊，但也有些實作為方便而在一個列表裏記錄下所有基本塊的參照； // 有時候（例如要處理異常的話）有可能有活著的基本塊會無法直接從start到達，此時也最好顯式記錄所有block。 }

是不是有點區別？

許多編譯器都會選擇直接從AST直接生成帶CFG的IR。要參考例子的話，LLVM Tutorial的Kaleidoscope是個好去處。

我寫這段的時候LLVM官網正好掛了，所以放個映像網站的連結：

LLVM Tutorial: Control Flow

IR的形式顯式的資訊越多（例如有顯式CFG，采用SSA形式之類），在最初構造這種IR時所需的處理就越多，但是相應的後面做分析的時候就越方便，特別是如果要做稀疏分析（sparse analysis）的話。

這些記錄在IR裏的額外資訊很多都可以看作是一種「緩存」——即便不記錄在IR裏也可以在後續分析需要的時候從頭遍歷一次IR來計算出來。但是緩存起來就不用每次重新算，所以比較方便——然而缺點也很明顯：這些資訊存在IR裏是得維護的，有維護成本；每次IR發生變化，緩存的資訊可能都得跟著更新。

就看IR的設計者想如何取舍了…

=======================================================

實際計畫的例子

龍書系的Quad設計，一種實際實作是JoeQ裏的IR。

請參考Stanford CS243課程的資料：

http:// suif.stanford.edu/~cour ses/cs243/joeq/#quads

現在可用的一份JoeQ的程式碼可以從這裏下載：

http:// suif.stanford.edu/~cour ses/cs243/hw2/hw2.zip

，其中lib/joeq.jar裏既包含程式的 class檔也包含源碼。

JoeQ是一個用Java實作的「元迴圈JVM」，內含一個用Java寫的、能把Java字節碼編譯為機器碼的編譯器。

JoeQ IR就是這個編譯器裏的IR，實作形式為顯式CFG+Quad。Quad可以是傳統形式也可以是SSA形式。

@啥玩應啊

的回答提醒了我，

Soot

的Jimple IR也是TAC。有很多靜態代分碼析工具基於Soot框架實作，甚至也有直接把Soot用在編譯器裏作為前端的（例如

RoboVM

）。Jimple IR的設計也可以參考，源碼在Soot的Github站上可以找到。

我比較熟悉和習慣的一種IR是HotSpot Client Compiler（C1）的HIR。它原本用C++實作，不過有個Java移植版C1X，可供題主參考。C1X的HIR實作源碼在此：

https:// kenai.com/projects/maxi ne/sources/maxine/show/com.oracle.max.c1x/src/com/sun/c1x/ir?rev=8809

C1 / C1X的一些設計選擇是：

在HIR裏不使用顯式變量，每條IR指令既代表一個運算也代表該運算的值

每條HIR指令的operand直接參照其它HIR指令

HIR指令透過單向鏈串起來

有顯式的CFG，HIR指令都掛靠在其所屬的基本塊（用BlockBegin指令表示）中

HIR使用SSA形式，不過只對local variable做SSA而不對記憶體做SSA。結合前面提到的直接參照其它HIR指令作為operand，從數據依賴的角度看，每條IR指令帶有完整的數據依賴描述——每個use-site都可以直接找到其對應的def-site。這種設計的概述請參考Design of the Java HotSpot™ Client Compiler for Java 6論文。也有地方把C1/C1X的HIR形式叫做VDG（Value-Dependence Graph）：C1X | Oracle Community

C1X retains most of C1's original design, with some front-end improvements, simplifications, and cleanups while porting to Java. The C1X frontend parses bytecodes into an SSA- style value-dependency graph that retains the original basic block structure of bytecodes. Because of the value-dependence graph nature of this main IR, operations on local variables and the stack result in no IR nodes being generated (unlike a named-form SSA or three-address form of IR). This representation is remarkably convenient for forward-dataflow problems such as constant-folding, value-numbering, and null-check elimination.

值得提醒的是，雖然上面的文件把C1/C1X HIR叫做VDG，它這麽叫只是為了突出「一個值直接依賴於別的值，而沒有變量結構」的特點，而並不是指那種專門叫做VDG的IR形式：

https:// courses.cs.washington.edu /courses/cse501/06wi/reading/weise-popl94.pdf

我比較熟悉、習慣和喜歡的另一種IR是HotSpot Server Compiler（C2）的Sea-of-nodes IR。這是個PDG（Program Dependence Graph）的變種，在編譯器中很非主流。PDG更多見於非編譯器的靜態分析器中，所以就不在這帖多說…

但是為了安利一下Sea-of-nodes形式，還是放個Cliff Click大神讀PhD時寫的論文的傳送門好了：

From Quads to Graphs: An Intermediate Representation's Journey (1993)

。

等題主在Quad裏摸爬滾打足夠時間後再讀這篇論文可能會有更多體會 >_<