問題背景:題主正在做的編譯器習作的源語言的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)
不過實際寫程式碼時這裏有許多東西要選擇:
別著急,上面這些問題都不是「致命選擇」。條條道路通羅馬,雖然有些路走起來會有點崎嶇…題主不要害怕,一開始每個地方都隨便選一種做法就好了。後面寫得多了就會慢慢體會到某些選擇或許選別的路更好,重要的是最初要邁出第一步做出第一個選擇。
采用最最最傳統的方式來做的話,可能會寫成:
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 FlowIR的形式顯式的資訊越多(例如有顯式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=8809C1 / C1X的一些設計選擇是:
值得提醒的是,雖然上面的文件把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裏摸爬滾打足夠時間後再讀這篇論文可能會有更多體會 >_<