首頁 > 軟體

為什麼人人都該懂點LLVM

2020-06-16 17:54:39

只要你和程式打交道，了解編譯器架構就會令你受益無窮——無論是分析程式效率，還是模擬新的處理器和作業系統。通過本文介紹，即使你對編譯器原本一知半解，也能開始用LLVM，來完成有意思的工作。

LLVM是什麼？

LLVM是一個好用、好玩，而且超前的系統語言（比如C和C++語言）編譯器。

當然，因為LLVM實在太強大，你會聽到許多其他特性（它可以是個JIT；支援了一大批非類C語言；還是App Store上的一種新的發布方式等等）。這些都是真的，不過就這篇文章而言，還是上面的定義更重要。

下面是一些讓LLVM與眾不同的原因：

  • LLVM的“中間表示”（IR）是一項大創新。LLVM的程式表示方法真的“可讀”（如果你會讀組合）。雖然看上去這沒什麼要緊，但要知道，其他編譯器的中間表示大多是種記憶體中的複雜資料結構，以至於很難寫出來，這讓其他編譯器既難懂又難以實現。
  • 然而LLVM並非如此。其架構遠比其他編譯器要模組化得多。這種優點可能部分來自於它的最初實現者。
  • 儘管LLVM給我們這些狂熱的學術駭客提供了一種研究工具的選擇，它還是一款有大公司做後台的工業級編譯器。這意味著你不需要去在“強大的編譯器”和“可玩的編譯器”之間做妥協——不像你在Java世界中必須在HotSpot和Jikes之間權衡那樣。

為什麼人人需要懂點兒LLVM？

是，LLVM是一款酷炫的編譯器，但是如果不做編譯器研究，還有什麼理由要管它？

答：只要你和程式打交道，了解編譯器架構就會令你受益，而且從我個人經驗來看，非常有用。利用它，可以分析程式要多久一次來完成某項工作；改造程式，使其更適用於你的系統，或者模擬一個新的處理器架構或作業系統——只需稍加改動，而不需要自己燒個晶片，或者寫個核心。對於電腦科學研究者來說，編譯器遠比他們想象中重要。建議你先試試LLVM，而不用hack下面這些工具（除非你真有重要的理由）：

  • 架構模擬器；
  • 動態二進位制分析工具，比如Pin；
  • 原始碼變換（簡單的比如sed，複雜一些的比如抽象語法樹的分析和序列化）；
  • 修改核心來干預系統呼叫；
  • 任何和虛擬機器管理程式相似的東西。

就算一個編譯器不能完美地適合你的任務，相比於從原始碼到原始碼的翻譯工作，它可以節省你九成精力。

下面是一些巧妙利用了LLVM，而又不是在做編譯器的研究專案：

  • UIUC的Virtual Ghost，展示了你可以用編譯器來保護掛掉的系統核心中的進程。
  • UW的CoreDet利用LLVM實現了多執行緒程式的確定性。
  • 在我們的近似計算工作中，我們使用LLVM流程來給程式注入錯誤資訊，以模仿一些易出錯的硬體。

重要的話說三遍：LLVM不是只用來實現編譯優化的！LLVM不是只用來實現編譯優化的！LLVM不是只用來實現編譯優化的！

組成部分

LLVM架構的主要組成部分如下（事實上也是所有現代編譯器架構）：

前端，流程（Pass），後端

下面分別來解釋：

  • 前端獲取你的原始碼然後將它轉變為某種中間表示。這種翻譯簡化了編譯器其他部分的工作，這樣它們就不需要面對比如C++原始碼的所有複雜性了。作為一個豪邁人，你很可能不想再做這部分工作；可以不加改動地使用Clang來完成。
  • “流程”將程式在中間表示之間互相變換。一般情況下，流程也用來優化程式碼：流程輸出的（中間表示）程式和它輸入的（中間表示）程式相比在功能上完全相同，只是在效能上得到改進。這部分通常是給你發揮的地方。你的研究工具可以通過觀察和修改編譯過程流中的IR來完成任務。
  • 後端部分可以生成實際執行的機器碼。你幾乎肯定不想動這部分了。

雖然當今大多數編譯器都使用了這種架構，但是LLVM有一點值得注意而與眾不同：整個過程中，程式都使用了同一種中間表示。在其他編譯器中，可能每一個流程產出的程式碼都有一種獨特的格式。LLVM在這一點上對hackers大為有利。我們不需要擔心我們的改動該插在哪個位置，只要放在前後端之間某個地方就足夠了。

開始

讓我們開幹吧。

獲取LLVM

首先需要安裝LLVM。Linux的諸發行版中一般已經裝好了LLVM和Clang的包，你直接用便是。但你還是需要確認一下機子裡的版本，是不是有所有你要用到的標頭檔案。在OS X系統中，和XCode一起安裝的LLVM就不是那麼完整。還好，用CMake從原始碼構建LLVM也沒有多難。通常你只需要構建LLVM本身，因為你的系統提供的Clang已經夠用（只要版本是匹配的，如果不是，你也可以自己構建Clang）。

具體在OS X上，Brandon Holt有一個不錯的指導文章。用Homebrew也可以安裝LLVM。

去讀手冊

你需要對文件有所了解。我找到了一些值得一看的連結：

  • 自動生成的Doxygen文件頁非常重要。要想搞定LLVM，你必須要以這些API的文件維生。這些頁面可能不太好找，所以我推薦你直接用Google搜尋。只要你在搜尋的函數或者類名後面加上“LLVM”，你一般就可以用Google找到正確的文件頁面了。（如果你夠勤奮，你甚至可以“訓練”你的Google，使得在不輸入LLVM的情況下它也可以把LLVM的相關結果推到最前面）雖然聽上去有點逗，不過你真的需要這樣找LLVM的API文件——反正我沒找到其他的好方法。
  • 《語言參考手冊》也非常有用，如果你曾被LLVM IR dump裡面的語法搞糊塗的話。
  • 《開發者手冊》描述了一些LLVM特有的資料結構的工具，比如高效字串，vector和map的替代品等等。它還描述了一些快速型別檢查工具 isa、cast和dyn_cast），這些你不管在哪都要跑。 
    ?如果你不知道你的流程可以做什麼，讀《編寫LLVM流程》 。不過因為你只是個研究人員而不是浸淫於編譯器的大牛，本文的觀點可能和這篇教學在一些細節上有所不同。（最緊急的是，別再用基於Makefile的構建系統了。直接開始用CMake構建你的程式吧，讀讀《“原始碼外”指令》）儘管上面這些是解決流程問題的官方材料，
  • 不過在線上瀏覽LLVM程式碼時，這個GitHub映象有時會更方便。

寫一個流程

使用LLVM來完成高產研究通常意味著你要寫一些自定義流程。這一節會指導你構建和執行一個簡單的流程來變換你的程式。

框架

我已經準備好了模板倉庫，裡面有些沒用的LLVM流程。我推薦先用這個模板。因為如果完全從頭開始，配好構建的組態檔可是相當痛苦的事。

首先從GitHub上下載llvm-pass-skeleton倉庫：

  1. $ git clone git@github.com:sampsyo/llvm-pass-skeleton.git

主要的工作都是在skeleton/Skeleton.cpp中完成的。把它開啟。這裡是我們的業務邏輯：

  1. virtualbool runOnFunction(Function&F){
  2. errs()<<"I saw a function called "<< F.getName()<<"!n";
  3. returnfalse;
  4. }

LLVM流程有很多種，我們現在用的這一種叫函數流程（function pass）（這是一個不錯的入手點）。正如你所期望的，LLVM會在編譯每個函數的時候先喚起這個方法。現在它所做的只是列印了一下函數名。

細節：

  • errs()是一個LLVM提供的C++輸出流，我們可以用它來輸出到控制台。
  • 函數返回false說明它沒有改動函數F。之後，如果我們真的變換了程式，我們需要返回一個true。

構建

通過CMake來構建這個流程：

  1. $ cd llvm-pass-skeleton
  2. $ mkdir build
  3. $ cd build
  4. $ cmake ..# Generate the Makefile.
  5. $ make # Actually build the pass.

如果LLVM沒有全域性安裝,你需要告訴CMake LLVM的位置.你可以把環境變數LLVM_DIR的值修改為通往share/llvm/cmake/的路徑。比如這是一個使用Homebrew安裝LLVM的例??：

  1. $ LLVM_DIR=/usr/local/opt/llvm/share/llvm/cmake cmake ..

構建流程之後會產生一個庫檔案，你可以在build/skeleton/libSkeletonPass.so或者類似的地方找到它，具體取決於你的平台。下一步我們載入這個庫來在真實的程式碼中執行這個流程。

執行

想要執行你的新流程，用clang編譯你的C程式碼，同時加上一些奇怪的flag來指明你剛剛編譯好的庫檔案：

  1. $ clang -Xclang-load -Xclang build/skeleton/libSkeletonPass.* something.c
  2. I saw a function called main!

-Xclang -load -Xclang path/to/lib.so這是你在Clang中載入並啟用你的流程所用的所有程式碼。所以當你處理較大的專案的時候，你可以直接把這些引數加到Makefile的CFLAGS裡或者你構建系統的對應的地方。

（通過單獨呼叫clang，你也可以每次只跑一個流程。這樣需要用LLVM的opt命令。這是官方文件裡的合法方式，但在這裡我就不贅述了。）

恭喜你，你成功hack了一個編譯器！接下來，我們要擴充套件這個hello world水平的流程，來做一些好玩的事情。

理解LLVM的中間表示

想要使用LLVM裡的程式，你需要知道一點中間表示的組織方法。

模組（Module），函數（Function），程式碼塊（BasicBlock），指令（Instruction） 
模組包含了函數，函數又包含了程式碼塊，後者又是由指令組成。除了模組以外，所有結構都是從值產生而來的。

容器

首先了解一下LLVM程式中最重要的元件： 

  • 粗略地說，模組表示了一個原始檔，或者學術一點講叫翻譯單元。其他所有東西都被包含在模組之中。 
  • 最值得注意的是，模組容納了函數，顧名思義，後者就是一段段被命名的可執行程式碼。（在C++中，函數function和方法method都相應於LLVM中的函數。） 
  • 除了宣告名字和引數之外，函數主要會做為程式碼塊的容器。程式碼塊和它在編譯器中的概念差不多，不過目前我們把它看做是一段連續的指令。 
  • 而說到指令，就是一條單獨的程式碼命令。這一種抽象基本上和RISC機器碼是類似的：比如一個指令可能是一次整數加法，可能是一次浮點數除法，也可能是向記憶體寫入。

大部分LLVM中的內容——包括函數，程式碼塊，指令——都是繼承了一個名為值的基礎類別的C++類別。值是可以用於計算的任何型別的資料，比如數或者記憶體地址。全域性變數和常數（或者說字面值，立即數，比如5）都是值。

指令

這是一個寫成人類可讀文字的LLVM中間表示的指令的例子。

  1. %5= add i32 %4,2

這個指令將兩個32位元整數相加（可以通過型別i32推斷出來）。它將4號暫存器（寫作%4）中的數和字面值2（寫作2）求和，然後放到5號暫存器中。這就是為什麼我說LLVM IR讀起來像是RISC機器碼：我們甚至連術語都是一樣的，比如暫存器，不過我們在LLVM裡有無限多個暫存器。

在編譯器內，這條指令被表示為指令C++類別的一個範例。這個物件有一個操作碼表示這是一次加法，一個型別，以及一個運算元的列表，其中每個元素都指向另外一個值（Value）物件。在我們的例子中，它指向了一個代表整數2的常數物件和一個代表5號暫存器的指令物件。（因為LLVM IR使用了靜態單次分配格式，暫存器和指令事實上是一個而且是相同的，暫存器號是人為的字面表示。）

另外，如果你想看你自己程式的LLVM IR，你可以直接使用Clang：

  1. $ clang -emit-llvm -S -o - something.c

檢視流程中的IR

讓我們回到我們正在做的LLVM流程。我們可以檢視所有重要的IR物件，只需要用一個普適而方便的方法：dump()。它會列印出人可讀的IR物件的表示。因為我們的流程是處理常式的，所以我們用它來迭代函數裡所有的程式碼塊，然後是每個程式碼塊的指令集。

下面是程式碼。你可以通過在llvm-pass-skeleton程式碼庫中切換到containers分支來獲得程式碼。

  1. errs()<<"Function body:n";
  2. F.dump();
  3. for(auto& B : F){
  4. errs()<<"Basic block:n";
  5. B.dump();
  6. for(auto& I : B){
  7. errs()<<"Instruction: ";
  8. I.dump();
  9. }
  10. }

使用C++ 11裡的auto型別和foreach語法可以方便地在LLVM IR的繼承結構裡探索。

如果你重新構建流程並通過它再跑程式，你可以看到很多IR被切分開輸出，正如我們遍歷它那樣。

做些更有趣的事

當你在找尋程式中的一些模式，並有選擇地修改它們時，LLVM的魔力真正展現了出來。這裡是一個簡單的例子：把函數裡第一個二元操作符（比如+，-）改成乘號。聽上去很有用對吧？

下面是程式碼。這個版本的程式碼，和一個可以試著跑的範例程式一起，放在了llvm-pass-skeleton倉庫的 mutate分支。

  1. for(auto& B : F){
  2. for(auto& I : B){
  3. if(auto* op = dyn_cast<BinaryOperator>(&I)){
  4. // Insert at the point where the instruction `op` appears.
  5. IRBuilder<> builder(op);
  6. // Make a multiply with the same operands as `op`.
  7. Value* lhs = op->getOperand(0);
  8. Value* rhs = op->getOperand(1);
  9. Value* mul = builder.CreateMul(lhs, rhs);
  10. // Everywhere the old instruction was used as an operand, use our
  11. // new multiply instruction instead.
  12. for(auto& U : op->uses()){
  13. User* user = U.getUser();// A User is anything with operands.
  14. user->setOperand(U.getOperandNo(), mul);
  15. }
  16. // We modified the code.
  17. returntrue;
  18. }
  19. }
  20. }

細節如下：

  • dyn_cast<T>(p)建構函式是LLVM型別檢查工具的應用。使用了LLVM程式碼的一些慣例,使得動態型別檢查更高效，因為編譯器總要用它們。具體來說，如果I不是“二元操作符”，這個建構函式返回一個空指標，就可以完美應付很多特殊情況（比如這個）。
  • IRBuilder用於構造程式碼。它有一百萬種方法來建立任何你可能想要的指令。
  • 為把新指令縫進程式碼裡，我們需要找到所有它被使用的地方，然後當做一個引數換進我們的指令裡。回憶一下，每個指令都是一個值：在這裡，乘法指令被當做另一條指令裡的運算元，意味著乘積會成為被傳進來的引數。
  • 我們其實應該移除舊的指令，不過簡明起見我把它略去了。

現在我們編譯一個這樣的程式（程式碼庫中的example.c）：

  1. #include<stdio.h>
  2. int main(int argc,constchar** argv){
  3. int num;
  4. scanf("%i",&num);
  5. printf("%in", num +2);
  6. return0;
  7. }

如果用普通的編譯器，這個程式的行為和程式碼並沒有什麼差別；但我們的外掛會讓它將輸入翻倍而不是加2。

  1. $ cc example.c
  2. $ ./a.out
  3. 10
  4. 12
  5. $ clang -Xclang-load -Xclang build/skeleton/libSkeletonPass.so example.c
  6. $ ./a.out
  7. 10
  8. 20

很神奇吧！

連結動態庫

如果你想調整程式碼做一些大動作，用IRBuilder來生成LLVM指令可能就比較痛苦了。你可能需要寫一個C語言的執行時行為，然後把它連結到你正在編譯的程式上。這一節將會給你展示如何寫一個執行時庫，它可以將所有二元操作的結果記錄下來，而不僅僅是悶聲修改值。

這裡是LLVM流程的程式碼，也可以在llvm-pass-skeleton程式碼庫的rtlib分支找到它。

  1. // Get the function to call from our runtime library.
  2. LLVMContext&Ctx= F.getContext();
  3. Constant* logFunc = F.getParent()->getOrInsertFunction(
  4. "logop",Type::getVoidTy(Ctx),Type::getInt32Ty(Ctx), NULL
  5. );
  6. for(auto& B : F){
  7. for(auto& I : B){
  8. if(auto* op = dyn_cast<BinaryOperator>(&I)){
  9. // Insert *after* `op`.
  10. IRBuilder<> builder(op);
  11. builder.SetInsertPoint(&B,++builder.GetInsertPoint());
  12. // Insert a call to our function.
  13. Value* args[]={op};
  14. builder.CreateCall(logFunc, args);
  15. returntrue;
  16. }
  17. }
  18. }

你需要的工具包括Module::getOrInsertFunction和IRBuilder::CreateCall。前者給你的執行時函數logop增加了一個宣告（類似於在C程式中宣告void logop(int i);而不提供實現）。相應的函數體可以在定義了logop函數的執行時庫（程式碼庫中的rtlib.c）找到。

  1. #include<stdio.h>
  2. void logop(int i){
  3. printf("computed: %in", i);
  4. }

要執行這個程式，你需要連結你的執行時庫：

  1. $ cc -c rtlib.c
  2. $ clang -Xclang-load -Xclang build/skeleton/libSkeletonPass.so -c example.c
  3. $ cc example.o rtlib.o
  4. $ ./a.out
  5. 12
  6. computed:14
  7. 14

如果你希望的話，你也可以在編譯成機器碼之前就縫合程式和執行時庫。llvm-link工具——你可以把它簡單看做IR層面的ld的等價工具，可以幫助你完成這項工作。

註記（Annotation）

大部分工程最終是要和開發者進行互動的。你會希望有一套註記（annotations），來幫助你從程式裡傳遞資訊給LLVM流程。這裡有一些構造註記系統的方法：

  • 一個實用而取巧的方法是使用魔法函數。先在一個標頭檔案裡宣告一些空函數，用一些奇怪的、基本是獨特的名字命名。在原始碼中引入這個標頭檔案，然後呼叫這些什麼都沒有做的函數。然後，在你的流程裡，查詢喚起了函數的CallInst指令，然後利用它們去觸發你真正要做的“魔法”。比如說，你可能想呼叫__enable_instrumentation()和__disable_instrumentation()，讓程式將程式碼改寫限制在某些具體的區域。
  • 如果想讓程式設計師給函數或者變數宣告加記號，Clang的__attribute__((annotate("foo")))語法會發射一個後設資料和任意字串，可以在流程中處理它。Brandon Holt（又是他）有篇文章講解了這個技術的背景。如果你想標記一些表示式，而非宣告，一個沒有文件，同時很不幸受限了的__builtin_annotation(e, "foo")內建方法可能會有用。
  • 可以自由修改Clang使它可以翻譯你的新語法。不過我不推薦這個。
  • 如果你需要標記型別——我相信大家經常沒意識到就這麼做了——我開發了一個名為Quala的系統。它給Clang打了修補程式，以支援自定義的型別檢查和可插拔的型別系統，到Java的JSR-308。如果你對這個專案感興趣，並且想合作，請聯絡我。

我希望能在以後的文章裡展開討論這些技術。

其他

LLVM非常龐大。下面是一些我沒講到的話題：

  • 使用LLVM中的一大批古典編譯器分析；
  • 通過hack後端來生成任意的特殊機器指令（架構師們經常想這麼乾）；
  • 利用debug info連線原始碼中的行和列到IR中的每一處；
  • 開發[Clang前端外掛]。(http://clang.llvm.org/docs/ClangPlugins.html)

我希望我給你講了足夠的背景來支援你完成一個好專案了。探索構建去吧！如果這篇文章對你幫助，也請讓我知道。

感謝UW的架構與系統組，圍觀了我的這篇文章並且提了很多很讚的問題。

以及感謝以下的讀者：

  • Emery Berger指出了動態二進位制分析工具，比如Pin，仍然是你在觀察系統結構中具體內容（比如暫存器，記憶體繼承和指令編碼等）的好幫手；
  • Brandon Holt發了一篇《LLVM debug 技巧》，包括如何用GraphViz繪製控制流圖；
  • John Regehr在評論中提到把軟體搭在LLVM上的缺點：API不穩定性。LLVM內部幾乎每版都要大換，所以你需要不斷維護你的專案。Alex Bradbury的LLVM週報是個跟進LLVM生態圈的好資源。

更多LLVM的資訊：

LLVM 和 GCC 編譯器開發者將開始展開合作 http://www.linuxidc.com/Linux/2014-02/96366.htm

LLVM 基金會成立 http://www.linuxidc.com/Linux/2014-04/99454.htm

LLVM 編譯器架構獲得 ACM 軟體系統獎 http://www.linuxidc.com/Linux/2013-04/82660.htm

如何建立原生的LLVM SVN映象庫 http://www.linuxidc.com/Linux/2013-03/80162.htm

RMS 談 GCC、LLVM 和 Copyleft http://www.linuxidc.com/Linux/2014-01/95828.htm


相關文章

IT145.com E-mail:sddin#qq.com