編譯器中端

中間代碼

LLVM 中間表示的三種格式：在內(nèi)存中的編譯中間語言；硬盤上存儲的二進制中間語言，以.bc結(jié)尾；以及可讀的中間代碼格式，以.ll結(jié)尾。

LLVM 中間代碼結(jié)構(gòu)包括四個部分：

1. 模塊（Module）是LLVM IR的頂層容器，對應于編譯前端的每個翻譯單元。每個模塊由目標機器信息、全局符號（全局變量和函數(shù)）及元信息組成。

2. 函數(shù)（Function）就是編程語言中的函數(shù)，包括函數(shù)簽名和若干個基本塊，函數(shù)內(nèi)的第一個基本塊叫做入口基本塊。

3. 基本塊（BasicBlock）是一組順序執(zhí)行的指令集合，只有一個入口和一個出口，非頭尾指令執(zhí)行時不會違背順序跳轉(zhuǎn)到其他指令上去。每個基本塊最后一條指令一般是跳轉(zhuǎn)指令（跳轉(zhuǎn)到其它基本塊上去），函數(shù)內(nèi)最后一個基本塊的最后一條指令是函數(shù)返回指令。

4. 指令（Instruction）是LLVM IR中的最小可執(zhí)行單位。

生成LLVM中間代碼的編譯命令為：

file.c代碼為:

轉(zhuǎn)換后的file.ll代碼為:

LLVM中間代碼為采用靜態(tài)單賦值形式的中間表示，使用的指令集為LLVM虛擬指令集。 LLVM虛擬指令集由操作指令和內(nèi)建指令兩部分組成。內(nèi)建指令是指以llvm.開頭的指令，比如預取內(nèi)建指令llvm.prefetch，在使用時被轉(zhuǎn)換成一條或多條操作指令。常見的操作指令有四則運算指令、邏輯運算指令等，如LLVM中間代碼的加法操作：

中間代碼優(yōu)化

編譯優(yōu)化選項

代碼優(yōu)化階段的任務是對中間代碼進行變換或改造，目的是使生成的目標代碼更為高效（省時間和省空間）。

-O優(yōu)化選項用以控制編譯器在對程序編譯時的優(yōu)化級別，常用的有-O0、-O1、-O2、-O3、-Ofast。其中-O0選項表示不開啟任何優(yōu)化，該編譯過程用的時間消耗最小，此時生成的匯編最接近程序源代碼的語句；-O1選項只開啟少量優(yōu)化，主要對代碼中的分支、常量以及表達式等進行優(yōu)化；-O2選項表示開啟適度優(yōu)化，在-O1選項的基礎(chǔ)上，增加自動向量化優(yōu)化，編譯過程會有一定的時間和空間消耗；-O3類似-O2，使用更多的優(yōu)化手段和更長的優(yōu)化時間；-Ofast啟用所有-O3優(yōu)化以及可能違反語義的其它優(yōu)化，以追求最大可能的代碼執(zhí)行效率。

死代碼刪除

死代碼是指在程序操作過程中不可能被執(zhí)行到的代碼，或是代碼可以被執(zhí)行，但是對計算結(jié)果不起任何作用，比如代碼段。

示例：

C語言代碼：

執(zhí)行命令：

關(guān)閉死代碼刪除優(yōu)化：

執(zhí)行命令：

開啟死代碼刪除優(yōu)化：

對于上述所示代碼，S1和S2兩個語句在程序執(zhí)行時會被執(zhí)行，但是只有S1的結(jié)果有意義，語句S2的執(zhí)行對結(jié)果沒有任何影響，語句S2就叫死代碼，編譯器可自動將其識別出來并刪除。

過程間優(yōu)化

過程間優(yōu)化是涉及程序中多個過程的程序變換與優(yōu)化，過程間分析階段為過程間優(yōu)化提供足夠的信息，用于支持過程間優(yōu)化階段的各類程序變換。內(nèi)聯(lián)優(yōu)化是過程間優(yōu)化中最常用的一種方法，它是指如果在循環(huán)中調(diào)用了另一個過程，則過程間優(yōu)化會將該過程內(nèi)聯(lián)到函數(shù)體內(nèi)，并且會重新對過程排序以獲得更好的內(nèi)存布局。

示例：

執(zhí)行命令：

內(nèi)聯(lián)優(yōu)化前中間代碼為：

執(zhí)行命令：

內(nèi)聯(lián)優(yōu)化后中間代碼為：

通過對比可以看出，過程間優(yōu)化中的內(nèi)聯(lián)操作將add函數(shù)內(nèi)聯(lián)到了循環(huán)體中，減少了函數(shù)調(diào)用的入棧出棧開銷，并且可以執(zhí)行一些內(nèi)聯(lián)優(yōu)化之前不會進行的優(yōu)化，比如在本例中內(nèi)聯(lián)優(yōu)化后的循環(huán)可以被向量化，LLVM在優(yōu)化級別-O3選項下即開啟過程間優(yōu)化。

自動向量優(yōu)化

自動向量化是指編譯器自動的將串行代碼轉(zhuǎn)化為向量代碼的一種優(yōu)化變換。向量計算是一種特殊的并行計算方式，相比于標量執(zhí)行時每次僅操作一個數(shù)據(jù)，它可以在同一時間對多個數(shù)據(jù)執(zhí)行相同的操作，從而獲得數(shù)據(jù)級并行。LLVM目前支持兩種自動向量化方法，分別是循環(huán)級向量化和基本塊級向量化。

循環(huán)級向量化

通過擴大循環(huán)中的指令以獲得多個連續(xù)迭代中操作的向量執(zhí)行，在LLVM中通過選項-fvectorize開啟循環(huán)向量化，并且當打開-O2選項及高于-O2優(yōu)化級別的選項即自動開啟循環(huán)向量化優(yōu)化。

示例：

執(zhí)行命令：

循環(huán)級向量化的中間代碼為：

可以看出，經(jīng)向量化后生成的中間代碼中，對于數(shù)組a每次取了四個數(shù)據(jù)進行運算，如果后端支持向量指令，則在一個循環(huán)內(nèi)對四個數(shù)據(jù)進行同時操作，實現(xiàn)了數(shù)據(jù)級并行。

基本塊級向量化

基本塊級向量化算法的思想來源于指令級并行，通過將基本塊內(nèi)可以同時執(zhí)行的多個標量操作打包成向量操作來實現(xiàn)并行，與循環(huán)級向量并行發(fā)掘方法不同，基本塊級向量化發(fā)掘方法主要是在基本塊內(nèi)尋找同構(gòu)語句，發(fā)掘基本塊內(nèi)指令的并行機會。在LLVM中加入選項-fslp-vectorize以開啟基本塊級向量化。

示例：

執(zhí)行命令：

基本塊級向量化的中間代碼為：

優(yōu)化后的中間代碼代碼示意如下：

基本塊級向量化算法主要用于發(fā)掘基本塊內(nèi)的并行性，它要遍歷所有的向量方案得到最優(yōu)解，所以復雜度高于循環(huán)級向量化，具有更強的向量挖掘能力，經(jīng)轉(zhuǎn)化后的向量代碼程序性能會有很大的提升。

循環(huán)優(yōu)化

循環(huán)優(yōu)化是編譯器中重要的優(yōu)化手段之一，本節(jié)選取LLVM編譯器支持的幾種典型的循環(huán)優(yōu)化，包括循環(huán)展開、循環(huán)分布和循環(huán)剝離進行介紹。

循環(huán)展開

循環(huán)展開是指將循環(huán)體代碼復制多次的實現(xiàn)，通過增大指令調(diào)度的空間來減少循環(huán)分支指令的開銷、增加數(shù)據(jù)引用的局部性，從而提高循環(huán)執(zhí)行性能的一種循環(huán)變換技術(shù)。在LLVM中通過選項-funroll-loops打開循環(huán)展開優(yōu)化。

示例：

執(zhí)行命令：

中間代碼部分即為對sum規(guī)約加法操作進行的循環(huán)展開，即在一個基本塊內(nèi)，對該操作展開了四次操作。

循環(huán)分布

循環(huán)分布是指將循環(huán)內(nèi)的一條或多條語句移到單獨一個循環(huán)中，以滿足某些特定的需求。例如，當循環(huán)中某條語句存在依賴不可消除的情況，會導致整個循環(huán)無法向量化，通過循環(huán)分布優(yōu)化將循環(huán)中有依賴的語句和無依賴的語句分開，使得分離后的某個循環(huán)中不存在依賴在LLVM中通過選項-mllvm -enable-loop-distribute打開循環(huán)分布優(yōu)化。

示例：

執(zhí)行命令：

循環(huán)分布后的中間代碼為：

循環(huán)剝離

循環(huán)剝離常用于將循環(huán)中數(shù)據(jù)首地址不對齊的引用，以及循環(huán)末尾不夠裝載到一個向量寄存器的數(shù)據(jù)剝離出來，使剩余數(shù)據(jù)滿足向量化對齊性要求。在LLVM編譯器優(yōu)化分析中，循環(huán)展開優(yōu)化通常與循環(huán)剝離配合使用，優(yōu)化人員可通過選項-mllvm unroll-peel-count寫定剝離數(shù)值。

示例：

執(zhí)行命令：

循環(huán)剝離后的中間代碼為：

剝離前，不符合向量對齊要求

剝離后，符合向量對齊要求

浮點優(yōu)化

若優(yōu)化人員想提高浮點數(shù)據(jù)的運算性能，可以利用LLVM編譯器的-ffast-math選項開啟較為激進的浮點優(yōu)化，該選項中包含了多種浮點優(yōu)化方法，比如浮點數(shù)據(jù)歸約向量化、除法運算優(yōu)化和忽略浮點數(shù)0的正負號等。

示例：

進行浮點優(yōu)化前：

可以從代碼中看出，該程序代碼中變量均為浮點數(shù)類型，第二次循環(huán)中的sum變量由循環(huán)的連續(xù)迭代所使用，LLVM為了保證計算結(jié)果的精度，在未加-ffast-math選項之前不會對該浮點類型數(shù)據(jù)的歸約實施向量化優(yōu)化。

數(shù)據(jù)預取優(yōu)化

LLVM編譯器支持自動數(shù)據(jù)預取和手動添加預取內(nèi)建指令兩種預取方式，其中自動數(shù)據(jù)預取是編譯器對程序分析后在中間代碼中自動插入預取指令，當前LLVM編譯器僅支持AArch64平臺和PowerPC平臺的自動數(shù)據(jù)預取優(yōu)化。手動添加的預取函數(shù)為：

示例：

進行數(shù)據(jù)預取優(yōu)化后的中間代碼為：

如果平臺支持預取指令則可以生成，否則該函數(shù)會是一個空操作，不做任何處理。當為高局部性時則表示該數(shù)據(jù)會在首次被訪問不久之后極有可能再次被訪問。其中內(nèi)建函數(shù)__builtin_prefetch(arr+i,1,3)表示對數(shù)組arr實施預取寫操作，并且該數(shù)組具有很好的數(shù)據(jù)局部性。該內(nèi)建函數(shù)會在中間代碼和匯編代碼中生成預取指令以達到預取優(yōu)化功能。

相關(guān)選項

有關(guān)中端的常用選項如表所示，每一種優(yōu)化功能都通過優(yōu)化選項控制。

這些優(yōu)化可以通過使用優(yōu)化信息選項打印編譯優(yōu)化相關(guān)的信息，其中包括優(yōu)化成功的信息、優(yōu)化失敗的信息、優(yōu)化分析信息等。