LLVM架構(gòu)介紹
本文主要介紹了LLVM的架構(gòu)設(shè)計(jì)惹想。LLVM命名源自于底層虛擬機(jī)(Low Level Virtual Machine)的縮寫。它并不是針對(duì)于某一種語(yǔ)言的編譯器工具逮光，它是一種提供支持與保護(hù)的一系列底層的工具鏈程序集合。讓LLVM與其它編譯器不同的是它的內(nèi)部架構(gòu)。下面就介紹LLVM的內(nèi)部架構(gòu)惜辑。
從2000年的11月開始，LLVM被設(shè)計(jì)為一系列擁有清晰接口并且可重用的庫(kù)疫赎，在那時(shí)候盛撑，開源的編程語(yǔ)言的實(shí)現(xiàn)被用作特別目的，而且經(jīng)常是進(jìn)行龐大的獨(dú)立執(zhí)行捧搞。這樣的話抵卫，復(fù)用靜態(tài)庫(kù)（例如GCC）做靜態(tài)分析或者代碼重構(gòu)時(shí)就會(huì)變得特別困難。而且腳本語(yǔ)言經(jīng)常是通過(guò)動(dòng)態(tài)解釋嵌入到即將運(yùn)行的大型應(yīng)用程序中胎撇。這種動(dòng)態(tài)運(yùn)行時(shí)使得代碼臃腫介粘。復(fù)用其中的某一模塊幾乎不可能，而且絲毫沒(méi)有共享精神晚树。
拋開編譯器本身實(shí)現(xiàn)不談姻采，各個(gè)流行語(yǔ)言之間實(shí)現(xiàn)方式的交流也是極端分化的：某一種語(yǔ)言實(shí)現(xiàn)通常要么采用傳統(tǒng)的編譯器（如GCC、Free Pascal...）爵憎，要么采用運(yùn)行時(shí)的編譯方式慨亲。同時(shí)提供兩種編譯方式的可不常見婚瓜。
LLVM從本質(zhì)上改變了這一切，LLVM被用來(lái)作為同時(shí)支持靜態(tài)和動(dòng)態(tài)運(yùn)行時(shí)編譯器的基礎(chǔ)框架刑棵。它同時(shí)也代替了各種實(shí)現(xiàn)特殊目的的編譯器巴刻，例如Apple OpenGL stack 的運(yùn)行時(shí)特殊引擎和Adobe After Effects 的圖片處理庫(kù)。目前蛉签，LLVM已經(jīng)被用于創(chuàng)造各種新的產(chǎn)品胡陪。
傳統(tǒng)的編譯器設(shè)計(jì)
傳統(tǒng)的靜態(tài)編譯器（例如大多數(shù)C編譯器）采用三段式設(shè)計(jì)：前端，優(yōu)化組件和后端正蛙。前端組件解析程序源代碼督弓，檢查語(yǔ)法錯(cuò)誤，生成一個(gè)基于語(yǔ)言特性的AST（Abstract Syntax Tree）來(lái)表示輸入代碼乒验。AST將代碼轉(zhuǎn)換為具有新的表達(dá)語(yǔ)法的代碼提供給優(yōu)化器愚隧，然后優(yōu)化器和后端程序執(zhí)行轉(zhuǎn)換后的代碼翻譯成機(jī)器能識(shí)別的語(yǔ)言。
優(yōu)化器作用是采用各種方式使得代碼運(yùn)行得更快锻全，例如刪除不必要的計(jì)算狂塘。后端（又叫代碼生成器）將代碼與任務(wù)指令一一對(duì)應(yīng)起來(lái)。除了生成正確的代碼以外鳄厌，也要與機(jī)器設(shè)備的特性結(jié)合以保證生成代碼的質(zhì)量荞胡。通常編譯器后端包括指令選擇，寄存器分配和指令安排表等功能了嚎。
JVM也是采用這種模式實(shí)現(xiàn)的泪漂，它是使用Java字節(jié)碼作為前端與優(yōu)化器的接口。
傳統(tǒng)編譯器模式的實(shí)現(xiàn)
這種模式的優(yōu)點(diǎn)在于當(dāng)編譯器決定支持多種語(yǔ)言或者多種目標(biāo)設(shè)備的時(shí)候歪泳，如果編譯器在優(yōu)化器這里采用普通的代碼表示時(shí)萝勤，前端可以使用任意的語(yǔ)言來(lái)進(jìn)行編譯，后端也可以使用任意的目標(biāo)設(shè)備來(lái)匯編呐伞。如下圖：
使用這種設(shè)計(jì)敌卓，使編譯器支持一種新的語(yǔ)言需要實(shí)現(xiàn)一個(gè)新的前端，但是優(yōu)化器以及后端都是可以復(fù)用伶氢，不用改變的趟径。那么實(shí)現(xiàn)支持新的語(yǔ)言需要從最初的前端設(shè)計(jì)開始，支持N種設(shè)備和M種源代碼語(yǔ)言一共需要N*M種編譯方式癣防。
這種三段式設(shè)計(jì)的另一優(yōu)點(diǎn)是編譯器提供了一個(gè)非常寬泛的語(yǔ)法集蜗巧，即對(duì)于開源編譯器項(xiàng)目來(lái)說(shuō)，這意味著會(huì)有更多的人參與進(jìn)來(lái)劣砍，自然而然地就提升了項(xiàng)目的質(zhì)量惧蛹。這也是為什么一些開源的編譯器通常更為流行。
最后一個(gè)優(yōu)點(diǎn)是實(shí)現(xiàn)一個(gè)編譯器前端相對(duì)于優(yōu)化器與后端來(lái)說(shuō)是完全不同的刑枝。將他們分離開來(lái)對(duì)于專注于設(shè)計(jì)前端來(lái)提升編譯器的多用性（支持多種語(yǔ)言）來(lái)說(shuō)相對(duì)容易點(diǎn)香嗓。它降低了開源編譯器項(xiàng)目的參與要求。
LLVM's Code Representation：LLVM IR
LLVM中最重要的設(shè)計(jì)模塊：LLVM IR（LLVM Intermediate Representation）装畅，它是在編譯器中用來(lái)表示代碼的一種形式靠娱。它被設(shè)計(jì)用來(lái)在編譯器的優(yōu)化模塊中，作為主導(dǎo)中間層的分析與轉(zhuǎn)換掠兄。它是經(jīng)過(guò)特殊設(shè)計(jì)的像云，包括支持輕量級(jí)的運(yùn)行時(shí)優(yōu)化、過(guò)程函數(shù)的優(yōu)化蚂夕，整個(gè)程序的分析和代碼完全重構(gòu)和翻譯等等迅诬。其中最重要的是，它定義了清晰的語(yǔ)義婿牍。參考如下的.ll文件：
define i32 @add1(i32 %a, i32 %b) {
entry:
%tmp1 = add i32 %a, %b
ret i32 %tmp1
}
define i32 @add2(i32 %a, i32 %b) {
entry:
%tmp1 = icmp eq i32 %a, 0
br i1 %tmp1, label %done, label %recurse
recurse:
%tmp2 = sub i32 %a, 1
%tmp3 = add i32 %b, 1
%tmp4 = call i32 @add2(i32 %tmp2, i32 %tmp3)
ret i32 %tmp4
done:
ret i32 %b
}
上述這段代碼對(duì)應(yīng)的是下面這段C代碼侈贷，它提供兩種方式返回一個(gè)整型變量：
unsigned add1(unsigned a, unsigned b) {
return a+b;
}
// Perhaps not the most efficient way to add two numbers.
unsigned add2(unsigned a, unsigned b) {
if (a == 0) return b;
return add2(a-1, b+1);
}
從這個(gè)例子中可以看出，LLVM IR 是一種底層的類RISC虛擬指令集等脂。正如真正的RISC指令集一樣俏蛮，它提供了一系列線性的簡(jiǎn)單指令：加、減上遥、比較以及分支結(jié)構(gòu)搏屑。這些指令在三種地址形式中：即通過(guò)對(duì)一些輸入的計(jì)算，得出的結(jié)果存在不同的寄存器中粉楚。LLVM IR提供了標(biāo)簽支持辣恋，它通常看起來(lái)像是一種奇怪的匯編語(yǔ)言一樣模软。
和大多數(shù)RISC指令集不同的是伟骨，LLVM使用一種簡(jiǎn)單的類型系統(tǒng)來(lái)標(biāo)記強(qiáng)類型（i32表示32位整型，i32**表示指向32位整型的指針）撵摆，而一些機(jī)器層面的細(xì)節(jié)都被抽象出去了底靠。例如函數(shù)調(diào)用使用call作標(biāo)記，而返回使用ret標(biāo)記特铝。此外還有個(gè)不同是LLVM IR不直接像匯編語(yǔ)言那樣直接使用寄存器暑中，它使用無(wú)限的臨時(shí)存儲(chǔ)單元，使用%符號(hào)來(lái)標(biāo)記這些臨時(shí)存儲(chǔ)單元鲫剿。
不僅僅是語(yǔ)言層面的實(shí)現(xiàn)那么簡(jiǎn)單鳄逾，LLVM IR實(shí)際上定義了定義了三種同型的形式：在代碼格式的檢查之上——內(nèi)存中數(shù)據(jù)結(jié)構(gòu)檢查、自身最優(yōu)化修正以及一種高效率密集型的二進(jìn)制代碼格式——bitcode灵莲。當(dāng)然LLVM也提供了將代碼文本轉(zhuǎn)為二進(jìn)制文件格式的工具：llvm-as雕凹，它將.ll文件轉(zhuǎn)為.bc格式文件，llvm-dis將.bc文件轉(zhuǎn)為.ll文件。
LLVM IR對(duì)于優(yōu)化器來(lái)說(shuō)非常友好枚抵，正是由于它的存在线欲，優(yōu)化器可以不受某一種特定語(yǔ)言或者特定設(shè)備的約束。因?yàn)槭褂肔LVM IR轉(zhuǎn)換一下就可以使得支持多種語(yǔ)言與多種設(shè)備了汽摹。
嘗試一種LLVM IR 優(yōu)化方式
大多數(shù)的優(yōu)化策略都遵守以下三條原則：
- 尋找一種轉(zhuǎn)換模式
- 驗(yàn)證這種轉(zhuǎn)換模式與匹配的實(shí)例是安全吻合的
- 開始轉(zhuǎn)換李丰，更新代碼
在模式匹配中有一些計(jì)算特性上的細(xì)節(jié)：對(duì)于任意的X，X-X是0逼泣，X-0是X趴泌，(X*2)-X是X，它們?cè)贚LVM IR中看起來(lái)像是這樣：
? ? ?
%example1 = sub i32 %a, %a
? ? ?
%example2 = sub i32 %b, 0
? ? ?
%tmp = mul i32 %c, 2
%example3 = sub i32 %tmp, %c
? ? ?
LLVM提供簡(jiǎn)化的指令接口被用來(lái)給其它高層轉(zhuǎn)換調(diào)用拉庶，這些特定的轉(zhuǎn)換在SimplifySubInst模塊中嗜憔，它看起來(lái)像是這樣：
// X - 0 -> X
if (match(Op1, m_Zero()))
return Op0;
// X - X -> 0
if (Op0 == Op1)
return Constant::getNullValue(Op0->getType());
// (X*2) - X -> X
if (match(Op0, m_Mul(m_Specific(Op1), m_ConstantInt<2>())))
return Op1;
…
return 0; // Nothing matched, return null to indicate no transformation.
在這個(gè)例子中Op0和Op1分別綁定到操作式的左右兩邊，
LLVM的三段式實(shí)現(xiàn)
在基于LLVM的編譯器中氏仗，前端的作用是解析吉捶、驗(yàn)證和診斷代碼錯(cuò)誤，將解析后的代碼翻譯為L(zhǎng)LVM IR（通常是這么做廓鞠，通過(guò)生成AST然后將AST轉(zhuǎn)為L(zhǎng)LVM IR）帚稠。翻譯后的IR代碼經(jīng)過(guò)一系列的優(yōu)化過(guò)程與分析后，代碼得到改善床佳，并將其送到代碼生成器去產(chǎn)生原生的機(jī)器碼滋早。過(guò)程如下圖所示。這是非常直觀的三段式設(shè)計(jì)的實(shí)現(xiàn)過(guò)程砌们，但是這簡(jiǎn)單的描述當(dāng)然是省去了一些細(xì)節(jié)的實(shí)現(xiàn)杆麸。
LLVM IR就是完全的代碼“代理”
LLVM IR可以說(shuō)是提供給優(yōu)化器的接口。這么說(shuō)的意思是你只需要了解為L(zhǎng)LVM編譯器寫前端就是搞清楚LLVM IR是什么浪感，它是怎么工作的昔头。既然LLVM IR擁有生成特定的代碼文本形式，那么我們?cè)O(shè)計(jì)的編譯器前端的功能就是產(chǎn)生LLVM IR文本代碼影兽，將其發(fā)送給優(yōu)化器和代碼生成器揭斧。那么和傳統(tǒng)的三段式不同的是后端生成機(jī)器代碼的時(shí)候不需要知道前端的AST的格式是什么，省去了一些工作峻堰。
LLVM是一些庫(kù)的集合
介紹完LLVM IR之后讹开，LLVM的另一個(gè)重要方面是它是由一系列庫(kù)所組件成的。相比于龐大的命令行編譯器GCC捐名、晦澀的虛擬機(jī)JVM旦万、.NET等，LLVM是一個(gè)基礎(chǔ)框架镶蹋，它是一些可用的編譯技術(shù)的集合并且可以忍受特殊的問(wèn)題成艘。
讓我們從優(yōu)化器的設(shè)計(jì)開始：優(yōu)化器從讀入LLVM IR代碼開始赏半，經(jīng)過(guò)優(yōu)化后產(chǎn)生的LLVM IR 可能會(huì)運(yùn)行的快一點(diǎn)，在LLVM中淆两，優(yōu)化器有很多種不同的優(yōu)化通道(optimization passes)断箫，根據(jù)輸入的不同，我們可以針對(duì)性地進(jìn)行一些改變(do sth here)琼腔，
每一個(gè)pass都被寫成了一個(gè)C++類瑰枫，它是由Pass類繼承來(lái)的踱葛。大多數(shù)的pass都是寫在一個(gè)單獨(dú)的類文件(.cpp)中的丹莲。Pass類的子類被定義在一個(gè)匿名空間中（保證完全私有），為了使得pass可用尸诽，文件外的代碼必須可以訪問(wèn)到此pass類文件甥材，因此單獨(dú)把創(chuàng)建pass的函數(shù)暴露出來(lái)就很有必要了。這里是一個(gè)小型的pass例子：
namespace {
class Hello : public FunctionPass {
public:
// Print out the names of functions in the LLVM IR being optimized.
virtual bool runOnFunction(Function &F) {
cerr << "Hello: " << F.getName() << "\n";
return false;
}
};
}
FunctionPass *createHelloPass() { return new Hello(); }
正如之前提到的那樣性含，LLVM的優(yōu)化器提供了非常多不同的pass洲赵，每種pass的寫法都是類似的。這些pass文件都被編譯成為.o文件商蕴，接著會(huì)被鏈接打包成為一系列庫(kù)文件(.a文件)叠萍，這些庫(kù)文件提供了很多的分析與翻譯的功能。pass之間都盡可能地寬松地結(jié)合：相互之間盡可能保持獨(dú)立绪商，或者時(shí)明確地定義pass之間的依賴關(guān)系苛谷。如果給了許多的pass文件，那么pass管理器就可以通過(guò)pass之間的文件依賴關(guān)系正確地執(zhí)行這些pass格郁。
LLVM優(yōu)化器允許挑選指定的pass文件并將它們鏈接到一起執(zhí)行腹殿，以此來(lái)完成指定的一些功能。當(dāng)然在優(yōu)化時(shí)例书，也只會(huì)由指定的pass完成優(yōu)化锣尉，而不是整個(gè)優(yōu)化器。如下圖所示：
這種基于庫(kù)的實(shí)現(xiàn)方式允許LLVM提供大量的功能决采，如果你只是需要LLVM中的一些簡(jiǎn)單的功能自沧，那么只需要指定運(yùn)行的pass文件而不需要管所有的優(yōu)化pass。
LLVM代碼生成器的設(shè)計(jì)
代碼生成器的任務(wù)是將LLVM IR翻譯為機(jī)器可識(shí)別的代碼树瞭。理論上說(shuō)拇厢，每個(gè)代碼生成器都要針對(duì)不同的任務(wù)定制不同的機(jī)器代碼，但是另一方面移迫，對(duì)于每個(gè)任務(wù)旺嬉，代碼生成器所做的工作又有很多類似的，例如將變量分配到寄存器厨埋。
和優(yōu)化器采用的方式類似邪媳，LLVM的代碼生成器將代碼生成的問(wèn)題分離成獨(dú)立的pass，例如指令選擇，寄存器分配雨效，建表迅涮，代碼布局優(yōu)化以及提供默認(rèn)的內(nèi)建pass等等。通過(guò)選用內(nèi)建的默認(rèn)pass徽龟，重寫這些默認(rèn)pass實(shí)現(xiàn)針對(duì)特定設(shè)備的自定制pass叮姑。例如x86后端使用寄存器調(diào)度是因?yàn)闄C(jī)器上的寄存器較少，而PowerPC后端使用潛在優(yōu)化寄存器調(diào)度是因?yàn)闄C(jī)器上有很多寄存器据悔。因此對(duì)于這兩種機(jī)器传透，必須有不同的pass代碼生成器去解決。這種靈活的方式允許根據(jù)機(jī)器的不同采用不同的解決辦法而不是完全重寫默認(rèn)的解決方式极颓。
LLVM 任務(wù)描述文件
這種方式帶來(lái)了新的問(wèn)題:每個(gè)共享的pass組件應(yīng)該有能力去識(shí)別對(duì)應(yīng)的任務(wù)所需要的文件以及相應(yīng)指令之間的約束關(guān)系朱盐。LLVM的做法是對(duì)于每一個(gè)任務(wù)，都有對(duì)應(yīng)的任務(wù)描述文件(.ed文件)菠隆，x86的生成過(guò)程如下：
不同的子系統(tǒng)提供了不同的.td文件兵琳，例如x86后端定義了一個(gè)寄存器類，它記錄了所有的32位寄存器骇径，名稱為GR32：
def GR32 : RegisterClass<[i32], 32,
[EAX, ECX, EDX, ESI, EDI, EBX, EBP, ESP,
R8D, R9D, R10D, R11D, R14D, R15D, R12D, R13D]> { … }
這個(gè)定義列出了此類中的寄存器可以保存32位的整型數(shù)躯肌。
未完待續(xù)...
