2012年10月30日 星期二

LLVM 程式員手冊 - 重要及有用的 LLVM API

目錄

  1. 簡介
  2. 背景知識
  3. 重要跟有用的 LLVM API
  4. 為你的程式挑個正確的資料結構
  5. 常用操作的小提示集
  6. 執行緒與 LLVM
  7. 進階議題
  8. LLVM 核心類別的族譜
本文翻譯自 LLVM Programmer's Manual
Written by Chris Lattner, Dinakar Dhurjati, Gabor Greif, Joel Stanley, Reid Spencer and Owen Anderson

Translated by Kito Cheng (kito at 0xlab.org)
WIKI 版本

重要跟有用的 LLVM API

這邊會列出一些有用且玩弄 LLVM 前最好知道的一些 LLVM API。


有關 isa<>, cast<> and dyn_cast<> templates

在 LLVM 大量的使用自製的 RTTI,這些 templates 的功能主要類似於 dynamic_cast<> operator,但是 LLVM 自製版本的沒有 C++ 內建版本的一些缺點 (主要是 dynamic_cast<> 只對於有 v-table 譯註1 的 class 有用,沒有就不能動)。在 LLVM 這類東西經常會用到,所以你最好知道它是怎麼運作的。所有相關的 template 都定義在 llvm/Support/Casting.h 這個檔案 (通常不用自己去 include 這檔案 譯註2)

譯註1: 一個 Class 只有在有 Virtual Function 的時候才會有 v-table ,所以換句話說,沒 Virtual Function 的 Class 家族就完全不能用 dynamic_cast<>

譯註2:幾乎每個 LLVM Header 都會 include 到它,所以基本上你也不用自己去 include

isa<>

isa<> operator 的功能就跟 Java 中的 instanceof operator一樣,它會根據你丟進去的 pointer 或 reference 並且檢查是不是你所預期的類別來回傳 true 或 false ,在許多情況下這傢伙很好用(下面有例子)

cast<>

cast<> operator 主要是拿來轉型用的,並且會作檢查,當你從父類別 (base class) 轉型到子類別 (derived class) 失敗的時候會直接 assertion failure 炸掉,所以只能在你非常確定它真的可以正確的向下轉型的時候使用,下面則是一個使用 isa<> 跟 cast<> template 的例子:

/* 檢查一個 Value 是不是 Loop Invariant */
static bool isLoopInvariant(const Value *V, const Loop *L) {
  if (isa<Constant>(V) || isa<Argument>(V) || isa<GlobalValue>(V))
    return true;

  /* 不是 Constant 、 Argument 或 GlobalValue 則一定是一個 Instruction
      如果不是存在該迴圈中則代表是 Loop Invariant */
  return !L->contains(cast<Instruction>(V)->getParent());
}

註:不要使用 isa<> 然後接著 cast<>,這種情況請直接使用 dyn_cast<> operator

dyn_cast<>

dyn_cast<> operator 主要是拿來轉型用的,並且會作檢查,當你從父類別 (base class) 轉型到子類別 (derived class) 失敗的時候會回傳 NULL pointer,所以上你不能餵 Reference 進去,而它整個功能就跟 C++ 的 dynamic_cast<> operator 非常類似,而且使用情境一樣,通常 dyn_cast<> operator 可以直接拿來塞在 if 判斷式或著是其它塞條件判斷式的地方,下面舉個例子:
/* 如果 Val 可以轉型成 AllocationInst */
if (AllocationInst *AI = dyn_cast<AllocationInst>(Val)) {
  /* ㄎㄎ,可以玩弄 AllocationInst 了 */
}

這樣子就可以有效的結合 isa<> 及 cast<> 變成一個 statement,方便吧~

註:dyn_cast<> operator 就像 C++ 的 dynamic_cast<> 或著是 Java 的 instanceof operator,常被濫用。千萬不要用一串的 dyn_cast<> + if/then/else 去檢查一堆類別。這種情況通常你可以直接用 InstVisitor 這個傢伙會比較方便又好看。

cast_or_null<>

cast_or_null<> operator 功能就跟 cast<> operator 一樣,唯一差別在於它可以塞 NULL pointer 進去,在某些情況下它還滿有用的。

dyn_cast_or_null<>

dyn_cast_or_null<> operator 功能就跟 dyn_cast<> operator 一樣,唯一差別在於它可以塞 NULL pointer 進去,在某些情況下它還滿有用的。

有關 isa<>, cast<> and dyn_cast<> templates 的結語

以上五個 template 能夠能來運作在任何 Class 上,不論它有沒有 v-table。如果你寫的 Class 也想要支援這些 template 的話參考這份文件: How to set up LLVM-style RTTI for your class hierarchy


字串傳遞 (StringRef 及 Twine Class)

雖然在 LLVM 中一般而言不用太多字串的操作,但在 LLVM 中一些重要的 API 參數中是用字串來傳遞,其中兩個重要的例子:
  1. Value Class :拿來命名指令或著函數之類的
  2. StringMap Class :在 LLVM 跟 Clang 經常被用到
這兩個 Class 基本上可以接受任何可能塞有 Null 字元的字串,不過它們不能直接轉換成 const char * 或著是 const string &,而許多 LLVM API 的參數通常是吃 StringRef 或著是 const Twine&。

The StringRef class


StringRef 是拿來表示常數字串(字元陣列加上一個長度)用的,支援許多 std::string 的操作,並且大部分不需要額外的 heap 空間。

它可以透過 Implicitly Constructor 來直接吃 C style null-terminated 字串或著是 std::string,或著是一個字元陣列加上一個長度。
例如 StringRef 的 find 函數宣告如下:
  iterator find(StringRef Key);
然後呼叫方可以用下面任意一個方式呼叫
  Map.find("foo");                 // Lookup "foo"
  Map.find(std::string("bar"));    // Lookup "bar"
  Map.find(StringRef("\0baz", 4)); // Lookup "\0baz"
而通常 API 也是回傳 StringRef ,如果你需要轉換成 std::string 的話要使用 str 函數詳細的資訊自己去爬一下llvm/ADT/StringRef.h。

大部分情況下請直接使用 StringRef ,主要是它字串跟物件本身是分離的,也因此在 LLVM 程式碼或 API 中可以發現它幾乎都是直接 pass by value 傳遞。

Twine Class


Twine Class 是一個高效能的字串串接 API。例如在 LLVM 慣例中指令名稱的結尾通常是令一個指令的名稱,範例如下:
    New = CmpInst::Create(..., SO->getName() + ".cmp");

而 Twine Class 則是一個高效率且輕量級建立於 stack 上的 rope 譯註1,Twine 可以由兩個字串的 operator+ 來隱式建構 (例如 C-style strings, std::string 或著是 StringRef)。Twine 主要把實際的字串串接動作延遲到實際要需要的時候才進行,這樣可以有效避免不必要中間暫存結果的 Heap 分配譯註2。詳細可以去挖 llvm/ADT/Twine.h 檔案來啃。

如果是跟 StringRef 互動的話 Twine只會紀錄指標並且幾乎不需要額外的記憶體,他們兩譯註3主要就是設計來快速有效的傳遞串接字串。

譯註1:一種拿來實作大量字串儲存的資料結構,詳見 wiki 說明 Rope
譯註2:直接看下面範例可以了解 Twine 省了啥:
/* 僅紀錄 abc 及 def 的 pointer, 不實際進行串接動作 */
Twine t1 = "abc" + "def";

/* Twine t1 跟 const char * "xyz" 串接, 但也不進行實際串接動作 */
Twine t2 = t1 + "xyz";

/* 實際到需要的時候內部才會進行串接動作!, 可避免到中間 abcdef 這個暫存字串出現 */
std::cout << t2.str();
譯註3:指 StringRef 跟 Twine 這對好兄弟


DEBUG() macro 跟 -debug 選項


通常在撰寫你的 pass 的時候你會放一堆拿來 debug 用的輸出程式碼,當它正式運作的時候又會想砍掉那串,但等到某天你發現它有 bug 或著是又要開始寫新功能的時候又要加進去那串 debug 用的輸出程式碼。。。

所以很自然的你會不希望砍掉那堆程式碼,但你又不想要它隨時的輸出一堆訊息,一些常見的作法就是把它註解掉,然後要的時候又把那個註解拿掉譯註1

譯註1:直接看下面 code
/* 例如把輸出的部份用個 ifdef 包裝 */
#ifdef DEBUG
 fprintf(stderr, "Debug Debug Debug");
#endif

/* 或著好看一點用 marco 包起來 */
#ifdef DEBUG
#define D(arg...) fprintf(stderr, __VA_ARGS__)
#else
#define D(arg...)
#endif

D("Debug Debug Debug");

在 "llvm/Support/Debug.h" 這個檔案中提供了一個 DEBUG() 來漂亮的解決這一類的問題,基本上你可以塞任何程式碼到 DEBUG 當參數,而包在裡面的程式碼只會在執行 opt 加上 -debug 參數的時候會吐出東西:

  DEBUG(errs() << "媽!我在這裡!\n");

所以你可以像這樣去跑你的 pass :

$ opt < a.bc > /dev/null -mypass
<沒有輸出>
$ opt < a.bc > /dev/null -mypass -debug
媽!我在這裡!

使用 DEBUG() Marco 取代自幹解法讓你不用弄一堆命令列參數譯註2,在你使用最佳化類型建置 LLVM 時,DEBUG() Marco 則會整個關閉,進而不會影響任何的效能(所以你也不要在 DEBUG 裡面有 side-effects譯註3!)。

譯註2:GCC 就是這樣幹。。。內部使用的 Debug 命令列參數無敵多。。。可以去 <gcc-source>/gcc/common.opt 參觀所有的命令列列表XD…

譯註3:大致上就是都不要更動到任何變數的值,不論區域或全域。

另一個 DEBUG() Marco 的方便東東就是當你在 gdb 中 debug LLVM 的時候只要輸入 "set DebugFlag=0" 或著是 "set DebugFlag=1" 就可以控制 DEBUG 的開關。

使用 DEBUG_TYPE 及 -debug-only 選項來細部控制 debug 資訊

有些時候你只想要 debug 自己的程式,而 -debug 又吐出全世界的錯誤訊息(例如在 Code Gen 的階段的時候),如果你想要細部控制 debug 資訊的話你就需要定義 DEBUG_TYPE 這個 marco 以及 -debug-only 選項,下面是使用範例:

#undef  DEBUG_TYPE
DEBUG(errs() << "No debug type\n");
#define DEBUG_TYPE "foo"
DEBUG(errs() << "'foo' debug type\n");
#undef  DEBUG_TYPE
#define DEBUG_TYPE "bar"
DEBUG(errs() << "'bar' debug type\n"));
#undef  DEBUG_TYPE
#define DEBUG_TYPE ""
DEBUG(errs() << "No debug type (2)\n");
然後接著你可以這樣跑你的 pass :
$ opt < a.bc > /dev/null -mypass
<沒有輸出>
$ opt < a.bc > /dev/null -mypass -debug
No debug type
'foo' debug type
'bar' debug type
No debug type (2)
$ opt < a.bc > /dev/null -mypass -debug-only=foo
'foo' debug type
$ opt < a.bc > /dev/null -mypass -debug-only=bar
'bar' debug type

當然在實務上你只需要再程式碼的最上方定義 DEBUG_TYPE 即可,這樣就可以為你的整個模組定義 debug type,(記得要放在#include "llvm/Support/Debug.h" 之前,通常你應該不會想用到醜不拉機的 #undef),然後最好把名稱取的有意義一點,不要用 foo 或 bar 這類沒營養的名字,主要是因為目前沒有任何機制去避免 DEBUG_TYPE 撞名的問題,如果兩個不同的模組使用同樣的 DEBUG_TYPE 名稱,則它們會被一起啟動,例如所有在 instruction scheduling 的 debug 資訊都會在 -debug-type=InstrSched 的時候一起噴出來,而那堆程式碼是散落在許多檔案當中。

DEBUG_WITH_TYPE 這個 Marco 則可以用在你想為某些 DEBUG 資訊設定特定 DEBUG_TYPE 時可以用,這個 Marco 比 DEBUG 多一個參數,第一個參數可以指定 DEBUG_TYPE,下面則是它的使用範例:
DEBUG_WITH_TYPE("", errs() << "No debug type\n");
DEBUG_WITH_TYPE("foo", errs() << "'foo' debug type\n");
DEBUG_WITH_TYPE("bar", errs() << "'bar' debug type\n"));
DEBUG_WITH_TYPE("", errs() << "No debug type (2)\n");


Statistic Class 及 -stats 選項


在 llvm/ADT/Statistic.h 這個檔案中提供一個叫做 Statistic 的 Class,他是專門拿來提供 LLVM 來紀錄各種最佳化對於程式有無實質上的改進。

你會在你的 pass 中處理一些東西,然後通常你會對於某些最佳畫到底執行幾次感興趣,雖然你可以直接在某些重要的函數中插入一些 code 去統計,但這樣的方式實在是有點鳥,而使用 Statistic Class 則可以讓你可以很簡單的去追蹤一些資訊,然後統一的在 pass 執行完後輸出。

下面是一些使用 Statistic class 的範例,他們基本上可以這樣用:

定義一個你的 statistic :
#define DEBUG_TYPE "mypassname"   // 這行 code 記得塞在所有 #include 前面
STATISTIC(NumXForms, "The # of times I did stuff");
STATISTIC Macro 定義了一個全域的靜態變數,其變數名稱如第一個參數,然後這個 Pass 的名稱它會直接從 DEBUG_TYPE 拿,它的描述則是放在第二個參數,這個變數實際上就像是個 unsigned integer 一 當你要執行一些最佳化或轉換的時候,遞增一下這個變數:
++NumXForms;   // 我做了某些事!
然後接著你只要在執行 opt 時加入 -stats 參數:
$ opt -stats -mypassname < program.bc > /dev/null
... statistics output ...

當你用 opt 跑某些測試時他會出現類似下面的統計報告:

   7646 bitcodewriter   - Number of normal instructions
    725 bitcodewriter   - Number of oversized instructions
 129996 bitcodewriter   - Number of bitcode bytes written
   2817 raise           - Number of insts DCEd or constprop'd
   3213 raise           - Number of cast-of-self removed
   5046 raise           - Number of expression trees converted
     75 raise           - Number of other getelementptr's formed
    138 raise           - Number of load/store peepholes
     42 deadtypeelim    - Number of unused typenames removed from symtab
    392 funcresolve     - Number of varargs functions resolved
     27 globaldce       - Number of global variables removed
      2 adce            - Number of basic blocks removed
    134 cee             - Number of branches revectored
     49 cee             - Number of setcc instruction eliminated
    532 gcse            - Number of loads removed
   2919 gcse            - Number of instructions removed
     86 indvars         - Number of canonical indvars added
     87 indvars         - Number of aux indvars removed
     25 instcombine     - Number of dead inst eliminate
    434 instcombine     - Number of insts combined
    248 licm            - Number of load insts hoisted
   1298 licm            - Number of insts hoisted to a loop pre-header
      3 licm            - Number of insts hoisted to multiple loop preds (bad, no loop pre-header)
     75 mem2reg         - Number of alloca's promoted
   1444 cfgsimplify     - Number of blocks simplified
由上面的統計輸出可以看出,程式執行了許多最佳化,而統一的界面讓這件事變得很容易,在你的 pass 中使用這個統一的界面將會使得你的程式碼更好維護!


在 Debug 程式的時候觀看某些 Graph

在 LLVM 當中許多重要的資料結構都是 Graph:例如 CFG 由一堆 Basic Block 組成,在 Instruction Selection 時使用的 DAG,在對 Compiler 除錯的情況下,如果能視覺化的看到內部的 Graph 則會使得除錯變得容易許多。

LLVM 提供許多的 Callback 提供 Debug 的時候用,例如你呼叫 Function::viewCFG() 這個函數,目前的 LLVM 會跳出一個視窗上面畫有該函數精美的 CFG,圖中的節點還會放置著 Basic Block 中的所有指令,而 Function::viewCFGOnly() 則可以讓你只看 Basic Block,不要顯示裡面的指令,類似的東西還有 MachineFunction::viewCFG() , MachineFunction::viewCFGOnly() 以及SelectionDAG::viewGraph() 這幾個函數,在 GDB 中你只要使用 DAG.viewGraph() 就會跳出視窗並且顯示出來,所以你也可以試著將那些函數呼叫塞到你正在 Debug 的部份。

要讓這個功能動起來事實上你可能需要一些額外的設定,例如在 Unix-linke 系統上需要安裝 graphviz 套件,並且確定 dot 跟 gv 這兩隻程是在你的 PATH 中,如果你在 Mac OS/X 的話,可以下載並安裝 Mac OS/X 的 graphviz 套件,然後加到 /Applications/Graphviz.app/Contents/MacOS/ (或任何你安裝的地方)到你的 PATH,一旦你系統的 PATH 設定好,在重新執行一次 LLVM configure script,並且重新建置 LLVM 就可以啟動這個好用的功能了!

SelectionDAG 部份則有一些方便你定位 Graph 中某些 Node 的功能,在 GDB 中如果你先呼叫 DAG.setGraphColor(node, "color"),再呼叫 DAG.viewGraph() 就會將你想看的 Node 標上指定的顏色(你可以在這個網頁找到color 的列表),事實上你還可以呼叫 DAG.setGraphAttrs(node, "attributes") 更詳細的去設定 Node 的屬性(可參考graphviz 的網頁),如果你想要回復預設 Graph 屬性的話可以呼叫DAG.clearGraphAttrs() 。