如何理解LLVM的PassManager系統的實現?
RT...感覺PassManager這塊的實現不好懂...
問題不太清楚，是指PassManager的add是如何管理的，還是指整體的原理？我覺得整體原理不難，主要是依賴bool run(Module M);方法，只是這裡面使用了C++的PIMPL的實現方式，讀起來不那麼自然而已，所以你在PassManager類裡面似乎什麼都看不到，只有一個PassManagerImpl *PM;實際實現都在這裡面。不過說到PIMPL，LLVM代碼到處都是這種實現方式，遠遠不止PassManager.
我對匿名答主說的Concept-based Implementation不了解。就僅僅說下我對之前的Pass Manager的實現原理吧。
在LLVM 4.0之前，LLVM的PassManager是分兩種類型的，一個是PassManager，這種pm用於module Pass。另外一種是FunctionPassManager，這個用於函數級別的Pass，也就是說這個這個pm裡面的pass都只是執行過程內(intra-procedural)的分析或變換，通常FunctionPassManager用於JIT編譯方式。在BackendUtil.cpp文件中，調用用於生成IR和彙編，可執行代碼都是一個CodeGenPasses，這個變數的類型即PassManager。
LLVM 中PassManager都會使用PassManagerImpl類去實現相關的功能，所以你直接在PassManager類裡面是看不到相關的代碼的。PassManager只是提供了兩個介面函數，分別是add和run。這兩個函數都會調用PassManagerImpl類中的add和run去完成相應的功能。
PassManagerImpl中都有一個void add(Pass *p)和bool run(Module m)函數，前者用於將對應的pass添加到PMDataManager（所有的pm都應該繼承的基類）中的passVector 隊列中，後者用於對Module m循環的運行pm中的pass，當然這個pass也有可能任然是pass manager，所以會一直調用下去。比如：FPPassManager是一個ModulePass，同時也是一個pm，當run在調用這個pass的時候，會調用FPPassManager中每個pass。
上述的void add()在往passVector中添加新的pass的時候，會預先調用pass的getAnalysisUsage()函數將該pass required的pass添加到passVector中，這樣每個pass預先需要的分析pass都會被提前執行。比如：RegAllocLinearScan類需要LiveIntervals類的分析信息，所以在RegAllocLinearScan的getAnalysisUsage函數中寫AU.addRequired&
當所有的pass都被add完了之後，pm調用run函數去執行該pm中每個pass，具體函數在
// Execute all the passes managed by this top level manager.
// Return true if any function is modified by a pass.
bool FunctionPassManagerImpl::run(Function F) {
bool Changed = false;
TimingInfo::createTheTimeInfo();
createDebugInfoProbe();
initializeAllAnalysisInfo();
for (unsigned Index = 0; Index &< getNumContainedManagers(); ++Index)
Changed |= getContainedManager(Index)-&>runOnFunction(F);
for (unsigned Index = 0; Index &< getNumContainedManagers(); ++Index) getContainedManager(Index)-&>cleanup();
wasRun = true;
return Changed;
}
在每個pm運行完了pass之後，會將passVector中dead的pass刪除，降低內存消耗。如果某個pass還需要被之後的pass使用，那麼在這個pass的getAnalysisUsage()中會調用AU.addPreserved()函數，告訴pm，之後這個pass還需要用到，不要從AvailableAnalysis中刪除它。
bool FPPassManager::runOnFunction(Function F) {
if (F.isDeclaration())
return false;
bool Changed = false;
// Collect inherited analysis from Module level pass manager.
populateInheritedAnalysis(TPM-&>activeStack);
for (unsigned Index = 0; Index &< getNumContainedPasses(); ++Index) {
FunctionPass *FP = getContainedPass(Index);
bool LocalChanged = false;
dumpPassInfo(FP, EXECUTION_MSG, ON_FUNCTION_MSG, F.getName());
dumpRequiredSet(FP);
initializeAnalysisImpl(FP);
if (TheDebugProbe)
TheDebugProbe-&>initialize(FP, F);
{
PassManagerPrettyStackEntry X(FP, F);
TimeRegion PassTimer(getPassTimer(FP));
LocalChanged |= FP-&>runOnFunction(F);
}
if (TheDebugProbe)
TheDebugProbe-&>finalize(FP, F);
Changed |= LocalChanged;
if (LocalChanged)
dumpPassInfo(FP, MODIFICATION_MSG, ON_FUNCTION_MSG, F.getName());
dumpPreservedSet(FP);
verifyPreservedAnalysis(FP);
removeNotPreservedAnalysis(FP);
recordAvailableAnalysis(FP);
removeDeadPasses(FP, F.getName(), ON_FUNCTION_MSG);
}
return Changed;
}
在每個pass的runOnFunction()函數中就會針對每個Function做分析或者變換了。當然如果這個pass需要其他的分析信息，比如RegAllocLinearScan需要LiveInterval，它就會在runOnFunction裡面調用getAnalysis&
LLVM里有兩套PassManager系統, legacy和由Chandler Carruth最近一兩年實現的一套新的系統(具體5.0還是6.0期間我懶得去查了)．老(legacy)PassManager系統的特點一言以蔽之: Pass是一套定義好的Pass和PassManager類的子類;新PassManager系統的特點一言以蔽之: 凡是提供了在IR上run()一把的method的類都是Pass(或者PassManager，沒必要區分Pass和PassManager了，因為都是在IR上run()一把).新的PassManager系統是所謂的concept based programming, 你可以看include/llvm/IR/PassManager.h開頭的那段注釋:
/// Note that the implementations of the pass managers use concept-based
/// polymorphism as outlined in the "Value Semantics and Concept-based
/// Polymorphism" talk (or its abbreviated sibling "Inheritance Is The Base
/// Class of Evil") by Sean Parent:
/// * sean-parent/sean-parent.github.io
/// * http://www.youtube.com/watch?v=_BpMYeUFXv8
/// * Inheritance Is The Base Class of Evil
不過這幾個鏈接我都沒看過．我的理解是, 我上面沒有提到關於新PassManager的一個細節: 如何將不同的Pass類放入同質容器（例如std::vector),例如當你的PassManager需要儲存他要run的Pass時？答：搞一個叫PassConcept的pure virtual class，以及一個template &
#include "llvm/InitializePasses.h"
#include "llvm/PassAnalysisSupport.h"
#include "llvm/PassSupport.h"
其他還有include/llvm/PassInfo.h, include/llvm/PassRegistry.h, 其中PassInfo是一個每一個Pass的子類都有一個實例的類，包含諸如是一個Analysis還是一個Transform, 是否只需CFG以及一個產生相應Pass的一個實例的method, 通常按ID(void*表示), 名字(字元串表示)查找Pass的函數會返回一個PassInfo實例, PassRegistry負責Pass registration和initialization相關的工作, 在lib/IR/PassRegistry.cpp中，有一個"全局PassRegistry"PassRegistryObj, 和PassRegistry的static方法getPassRegistry()的實現 https://github.com/llvm-mirror/llvm/blob/master/lib/IR/PassRegistry.cpp#L31
區分Legacy Pass和new Pass有多種辦法:
1 CRTP了PassInfoMixin的是new Pass, 繼承了BasicBlockPass, LoopPass, RegionPass, FunctionPass, ModulePass的這種是legacy Pass.
2 如果你看到INITIALIZE_PASS_BEGIN, INITIALIZE_PASS_END這種，則為legacy Pass（我覺得似乎void initializeAddressSanitizerModulePass(PassRegistry);這種也是legacy Pass的標誌，但是我不是特別確認）
3 通常看到SomethingWrapperPass, SomethingLegacyPass這種一般是legacy Pass(但是名字不是這樣的也可能是legacy Pass)
通常Analysis/Transform實現的.h文件和.cpp文件分別在include/llvm/Analysis或Transform和lib/Analysis或Transform下，不過像IR和Support目錄下也會有一些和optimization關係比較大的東西．
Chandler Carruth講過幾次LLVM Pass Manager的實現，ppt在這裡
https://llvm.org/devmtg/2014-10/Slides/Carruth-TheLLVMPassManagerPart2.pdf
https://llvm.org/devmtg/2014-04/PDFs/Talks/Passes.pdf
你也可以在youtube或llvm的網站上上找一下視頻(我記得是有一個的視頻還是ppt來著找不到了)，或者在mailing list里dig一下.
未帶待續, 計劃內容: 各種Legacy Pass Manager, Pass 依賴管理。
===================一更的分割線＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
關於legacy PassManager如何schedule Pass:
首先，我會描述一下PassManager去schedule Pass並滿足Pass間依賴的問題是什麼，然後我會描述一下llvm去schedule Pass的演算法(方法)是怎麼樣的，最後再補充一下在解釋前兩個問題的時候沒有提到的具體的實現方法(主要是設置了哪些類，作用分別是什麼)．
1 What"s the problem of scheduling passes ?
首先，IR是層次化的: module, function, basicblock, instruction; 相應的每個Pass P也有它所run的層次L: FunctionPass對module中的各個function逐一獨立運行, 不應該增刪函數,不應增刪全局變數, 在runOnFunction()方法對不同函數的調用間不應保持狀態.相應的BasicBlockPass也有對應的要求，你可以從這裡獲得關於各種Pass及其約束的詳細介紹 Writing an LLVM Pass 接下來的內容里我會假定你已經讀過這個tutorial並直接使用裡面介紹的內容. 這個doxygen頁面的類繼承關係圖也非常有用 http://llvm.org/doxygen/classllvm_1_1Pass__inherit__graph.png ,上面的Pass和他們的子類的.h文件都是include/llvm/Pass.h, .cpp文件都是lib/IR/Pass.h.
有下列三點需要說明:
1 Pass本身沒有runOnFunction/runOnModule之類的虛方法, 所有concrete Pass類不直接繼承Pass;
2 CallGraphSCC意思是函數間調用關係有向圖的強連通分量, 這種Pass是在function之上, module之下; Loop是natural loop: 一個back edge(u到v, v dominates u), v是loop header, u是latch, loop由v和所有可以不經過v而達到u的節點組成; natural loop(除loop header節點以外)具有包含嵌套關係, 同一個loop header可能是多個back edge的尾節點從而有多個loop（至於LoopPass是一次run一個loop還是同一個loop header的多個loop我沒仔細看, 如果你需要寫LoopPass的話應該自己確認一下）; region的定義是包括一下兩種region: definition1(simple region), single entry single exit region, 有兩條邊(a, b), a dominates b, b post dominates a, 且a, b loop equivalent(注意這裡的dominate和loop equivalent都是對邊定義的). definition2: 如果可以通過添加一個pre-header和post-exit構成definiton1中的simple region, 那麼稱為extended region(llvm里的region應該默認是指兩種region).llvm里找region的演算法不是文獻里各種O(n)的演算法, 而是利用dominator tree, post-dominator tree, 枚舉可能的region再檢查是否滿足條件. 構造dominator tree最起碼就已經是O(n)的了，llvm里的那個演算法最起碼是三次方的(我記得大概是，沒仔細check)，但是因為就算不要region info, 基本上dominator tree是肯定要構造的，所以這個算是"白給"，實際上出現的圖也不會達到演算法最差運行時間，經驗上這個演算法要快一些. 這個演算法具體實現在include/Analysis/RegionInfo.h, 是Grosser Tobias（似乎10年左右）寫的, 郵件列表裡也有部分Tobias解釋這個這個演算法的實現.
3 llvm::legacy::FunctionPassManagerImpl和llvm::legacy::PassManagerImpl就是llvm里兩個"top level manager"的pimpl實現.
回到schdule pass這個問題上, 每個Pass P除了具有屬性L(P)表示這個Pass應該在那個層次上run()，還具有兩個Analysis的集合Require(P)和Preserve(P), Require(P)表示P這個Pass運行之前哪些Analysis需要已經存在(Analysis也是Pass, 不過他們不修改IR所以他們的Preserve(P)是全集),Preserve(P)表示, P這個Pass運行過以後哪些Analysis的結果仍然有效: 比如你的Pass修改CFG了，那麼dominator tree就可能無效了，後面的Pass需要dominator tree的時候就要重新計算; 你的Pass沒有修改CFG，那麼dominator tree就仍有效，運行後續的需要dominator tree的Pass之前就不需要重新計算DT.一個Pass告訴llvm他的Require和Preserve集合是什麼是通過實現Pass::getAnalysisUsage()這個虛方法實現的，告訴了llvm需要哪些analysis後，可以通過Pass::getAnalysis()這個模板方法（這不是個虛方法）來獲取相應的analysis. 我省略了一些細節，具體可看上面的tutorial的這一部分: Writing an LLVM Pass .
然後schedule pass這個問題可以這樣定義: 你的PassManager有一個add(Pass*)方法，運行時會順序對一些Pass調用add(P), 這樣就定義了Pass之間的一個全序關係"&<"，此外每個Pass P有一個L(P)，你要對L這個層級的所有IR run()一遍P（例如對所有的BasicBlock B1, B2, ...,BN都run()一遍某BasicBlockPass BP1: (B1, BP1), (B2, BP1), ..., (BN, BP1)）, 運行P的時候需要已經運行產生Required(P)的analysis的Pass(注意到analysis也是有層級L的),運行P會使所有Preserve(P)以外的analysis invalidate掉; 對具有包含關係的IR運行的P需滿足全序關係"&<"，也即:
設IR單元L1屬於L2或者L2屬於L1, L(P1) == L(L1), L(P2) == L(L2)，那麼你給出的schedule中(L1, P1)與(L2, P2)的序關係應同P1, P2在全序關係"&<"中的關係一致.
例子1: FP1 &< FP2, 對於兩個function F1, F2: (F1, FP1) &< (F1, FP2), (F2, FP1) &< (F2, FP2), 此外無約束關係.
例子2: FP1 &< BP2, 對於一個function F1和一個basicblock B2, 若B2屬於F1，則(F1, FP1) &< (B2, BP2), 若果B2不屬於F1, 則兩者間無約束.
顯然，滿足上述＂正確性＂要求的schedule不止一個, llvm里為了考慮對緩存友好(llvm在代碼注釋中宣稱這樣對cache友好, 我只是轉述一下，我不知道到底哪樣對cache更好)，採用的schedule策略是:集中運行完某一部分IR的所有Pass(包括所有所包含的下級IR的Pass), 再去運行其他IR的Pass. 這樣顯然給出一個（隨意指定）IR間的順序，schedule就確定了.
What"s the algorithm of scheduling passes?
(未完待續)PMDataManager, PMStack, PMTopLevelManager.
===================二更的分割線＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
上面說過IR是有層次的，定義Module的層次為1, 往BasicBlock的方向遞增（或者直接就是參照這個枚舉定義層次對應的數值 include/llvm/Pass.h Source File ） ，然後對於層次L，我們定義這樣的一個類:1這個類繼承了層次為L的Pass子類 2可以向這個類add()層次為L + 1的Pass, 當這個類在層次為L的IR上run()的時候，會對IR中的子IR(層次L + 1)逐個運行這些Pass. 這些類就是上面那個枚舉中注釋的那些類，這些類還都繼承了PMDataManager llvm::PMDataManager Class Reference ,PMDataManager的作用是維護一個Pass的隊列(這些Pass都是同一個Level的，前面說過Pass類是沒有定義任何run()虛方法的，PMDataManager的子類需要把PMDataManager中的Pass* static_cast成自己知道的Pass子類再去run(), 如果同一個PMDataManager存儲的Pass不是預知其level的，你怎麼知道如何合適地static_cast&(Pass*)呢？), 除了上面些PassManager, FunctionPassManagerImpl和PassManagerImpl這兩個top level pass manager也繼承了PMDataManager(後面不再區分*PassManager和*PassManagerImpl了).注意這裡忽略了一下細節，例如LPPassManager, RGPassManager和BasicBlockPassManager都是實現FunctionPass類的，並不是上面說的L - 1(實際上Loop和Region無包含關係，所以L + 1和L是不對的，不過下面講演算法的時候還是假設L + 1和L是對的關係.)
然後定義PMStack: 這是一個PMDataManager的子類的stack, 棧底是一個FuntionPassManagerImpl或者PassManagerImpl；從棧底到棧頂，PMDataManager滿足嚴格的遞增關係. 然後棧當然可以入棧和出棧，這兩個操作也必須滿足LeveL遞增這個關係.初始化時，棧中只有FunctionPassManagerImpl或者PassManagerImpl(實際上PMStack是這兩個類的成員，棧上的東西其實是指針)
schedule(P)函數有下列幾步構成:
step 1: 遞歸對Require(P)中的元素Req執行schedule(Req)
step 2: 假設P的Level是L, 相應PM是把L層的Pass聚合成L - 1層的Pass的一個PMDataManager, 將棧上所有比PM層級高的PM1彈出, 注意到棧頂到棧底層級是遞減的，以及PM的層級不會低於棧底的FunctionPassManagerImpl或者PassManagerImpl的層級(這倆都是ModulePassManager層級).
step 3: 如果棧頂PMDataManager的層級和PM相同，那麼調用棧頂PM1的add(P)，返回．
如果棧頂PM1的層級小於PM的層級，new 一個PM，然後schedule(PM).注意到PM是一個層級L - 1的Pass. 這一步實際上就是把從PM到PM1這麼多等級的Pass逐個入棧. 然後PM1.add(P).
step 4. 刪除不在Preserve(P)中的Analysis．（實際上可以相見schedule()的入口會判斷P是一個analysis前當前存在這個analysis的情況直接返回，不過前面我沒寫這步）
然後在FunctionPassManagerImpl.run()或PassManagerImpl.run()中，只需逐個調用被add()的ModulePass. 這些ModulePass可能是"真的"ModulePass，也可能是聚合Pass---FunctionPassManager. FunctionPassManager的run()會調用所有add()了的FunctionPass(包括BasicBlockPassManagerPass), 以此類推.
What else implementation details are there?
簡單說一下legacy Pass Manager中的幾個比較重要的類:
Pass和只繼承了Pass的BasicBlockPass, RegionPass, LoopPass, FunctionPass, CGSSCCPass, ModulePass.
PMDataManager是用來分解出PassManager保存他所包含的Pass的這部分代碼的類．
同事集成Pass和PMDataManager的類:所有的聚合PassManager: MPPassManager, CGPassManager, FPPassManager, LPPassManager, RGPassManager, BBPassManager.
PMTopLevelManager: "真正的"的PassManager類借口, PMTopLevelManager可以作為PMStack的棧底；包含一個PMStack成員（用於schdule pass）;
FunctionPassManagerImpl和PassManagerImpl繼承了Pass, PMDataManager, 和 PMTopLevelManager; 有分別被FunctionPassManager和PassManager pimpl了.
AnalysisUsage是Pass用於表達preserve, require哪些Analysis的類.(新的Pass系統中是通過PreservedAnalysis類來返回一個Pass preserve哪些analysis)
AnalysisResolver: 每個Pass存了一個AnalysisResolver成員, AR存儲了一個指向PMDataManager的指針,指向Pass加入的那個PMDM，Pass的getAnalysis方法是通過AR, 通過PMDM實現的(順便說一下, PMDM中有指向棧頂的PMTopLevelManager的TPM指針).
PassRegistry:這個類有一個global singleton, 所有的Pass都應該向這個實例註冊一下. 這個類提供了根據字元串或者AnalysisID(AnalysisID是void*, 每個Pass都有一個static member AnalysisID，用來標記這個Pass)返回PassInfo的方法.
每個類都有一個對應的PassInfo類的實例, PassInfo有關於這個類是不是analysis, 和產生一個Pass*的creator方法等.
Writing an LLVM Pass這裡有一些Pass的介紹
結合我之前實現的pass，其實passmanager是一個隊列。對於單個pass，核心部分在於實現其runOnModule函數。
如有錯誤，還請各位大大指正。你好，我想問下，在增加一個pass時，$(LEVEL)下，Makefile.common，Makefile.rules, Makefile.config這些文件是怎麼得到的？我裝完後沒有這些文件，是不是需要創建個project?
推薦閱讀：
※為什麼很多語言的JIT實現最後會失敗，主要的技術原因和難點有哪些？
※llvm的reg2mem pass做了哪些事情？
※LLVM 相比與其他 Compiler Infrastructure 有什麼優勢?
※LLVM 怎樣入門和上手？
※編譯時能否關閉clang的所有優化？我試過-O0，但是編譯成彙編之後還是自動進行了一些優化？
TAG:LLVM |