在 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 參數中是用字串來傳遞，其中兩個重要的例子：

Value Class ：拿來命名指令或著函數之類的
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");

Then you can run your pass like this:
所以你可以像這樣去跑你的 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
<no output>
$ 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() 。

為你的程式挑個正確的資料結構

LLVM 有一狗票的資料結構放在 llvm/ADT/ 這個資料夾，而我們大量的使用 STK 的資料結構，這個章節主要告訴你如何在不同資料夾結構中取捨及選擇。

當然在開始的第一步是要先選擇你要那一類的容器：循序存取的容器，存放集合的容器或著是 Map 型的容器_譯註1？其中主要的選擇依據是依演算法的特性，並且你要如何存取容器裡面的值而定，下面則是各種使用情境：

譯註1：Map 型的主要就是 Key-Value 對應的東東，例如 string array 的 Key 是 int，Value 是 string，而 Map 是更抽象一層的東西，Key可以是任意可比較型態的東西，例如 Key 跟 Value 都是 string 也沒問題，如果解釋還看不懂的話快拿起手邊 C++ 的書翻閱 STL Map 的章節。

Map 型容器（Map-like container）：如果你需要快速的利用一個值（Key）去查找另一個值（Value），Map 型的容器支援這種類型的快速查找，但 Map 型的容器通常沒辦法提供有效率的反查功能（利用 Value 反查 Key），如果你需要這類功能的話就必須使用兩個 Map ，另外某些Map 型容器提供有效率依照 Key 的順序走訪功能_譯註2，但 Map 型容器事實上是成本最高_譯註3的容器，當只有你真的需要 Key-Value 快速查找的情況時使用它。
集合型容器（Set-like container）：如果你想放入一堆東西，並且它會自己砍掉重複元素，那就使用集合型容器，某些集合型容器提供有效率的有序走訪，但集合型容器通常又會比循序型容器還要貴。
循序型容器（Sequential container）：可以快速的在容器加入新元素，並且允許重複的值，也提供快速的走訪功能，但不提供 Key 查找的功能。
字串容器（String container）：拿來專門存放字元陣列或 Byte 陣列的資料結構。
位元容器（Bit container）：可有效儲存以數字為 Key 的集合，並且會自動消除重複，位元容器可以保證最多每個元素以一個位元來儲存。

譯註2：例如 std::map，內部實作通常是 Binary Search Tree （也通常是 RB-Tree），所以走訪的時候很自然會是依照 Key 的大小順序走。
譯註3：這邊說的成本跟貴都是指執行時期的記憶體消耗較多或著是較慢的意思。

一旦你決定了你要使用那一類的容器，你就可以依據記憶體使用量，演算法複雜度的常數因子以及快取行為來選擇你要使用該類別的哪個容器。而演算法複雜度的常數因子以及快取行為通常會有相當大的影響，如果你有一個 vector 通常只儲存少數元素（當然要可能有時候要裝比較多也沒問題），那麼你應該優先選擇 SmallVector 而不是 vector，這樣可以有效避免昂貴 malloc/free 的呼叫。

循序型容器 (std::vector, std::list, 等等)

這邊列出了許多不同的循序型容器，根據你的需求可以選擇一個最適合的。
There are a variety of sequential containers available for you, based on your needs. Pick the first in this section that will do what you want.

llvm/ADT/ArrayRef.h

llvm::ArrayRef Class 主要拿來單純作為循序存取元素的一個界面，一個 ArrayRef 可以塞固定長度的陣列，std::vector， llvm::SmallVector 或著是其它使用連續記憶體的傢伙。

固定長度陣列

固定長度的陣列簡單且存取相當快速，它們通常適用於你確定有多少個元素或著是你有明確的（且較小的）使用上限時使用。

Heap 分配來的陣列

Heap 分配來的陣列（new[] + delete[]）也相當簡單易用，在事前長度不確定時相當好用，如果知道通常需要較大的容量的話（較小容量請優先使用 SmallVector），那麼使用 Heap 分配陣列的主要成本在於 new/delete，另外一個要注意的是，如果該型態有建構子的話，它會對陣列中的每個元素呼叫建構子與解構子（可長度變動的 vector 則只會在新增/實際使用元素時呼叫）。

"llvm/ADT/TinyPtrVector.h"

TinyPtrVector<Type> 是一個高度特殊化的容器，它被最佳化程只有零個或一個元素時來可避免額外分配空間，該容器有兩個主要限制

它只能放 Pointer
它不能放 Null Pointer

這個容器是高度特殊化的容器，在 LLVM 中相對也較少使用到。

"llvm/ADT/SmallVector.h"

SmallVector<Type, N> 是一個輕巧版的 vector<Type>：支援快速的走訪，並且是循序將元素放在記憶體中（所以你可以直接在元素間使用指標運算），支援快速的 push_back 及 pop_back ，並且支援快速的隨機存取能力。

SmallVector 的主要優點是它會先內建某些數量（Template Argument 中的 N）的元素，所以在你使用小於 N 個元素時 SmallVector 不需要呼叫 malloc，malloc/free 的成本遠大於直接把塞在元素當中。

SmallVector 對於通常長度很小的情況（例如 Basic Block 的 predecessors/successors 通常小於八個）相當好用，當然相對的 SmallVector 會因此相對體積較大，通常你不會想要分配一堆 SmallVector （這樣作會浪費一堆空間），但 SmallVector 放在 stack 時則相當好用。

SmallVector 也提供了比 alloca 更好的可攜性及效率。

<vector>

std::vector 被廣泛使用，它在大小通常很大的情況下比 SmallVector 好用或著是你需要分配一堆 vector 的時候（分配一堆 SmallVector 可能會浪費空間）並且 std::vector 也有著良好的界面。

一個關於 std::vector 的使用建議：避免寫出像下面的程式碼：

for ( ... ) {
   std::vector<foo> V;
   // 使用 V.
}

取而代之寫成下面這樣：

std::vector<foo> V;
for ( ... ) {
   // 使用 V.
   V.clear();
}

這樣可以節省每次迴圈都分配釋放 Heap 記憶體。

<deque>

std::deque 就某種角度而言是個更一般化版本的 std::vector ，如同 std::vector ，std::deque 提供常數時間的隨機存取以及其它類似性質，但它可以提供有效率的存取前面的元素，相對的它就沒有保證元素間一定是連續放置的。

由於它的彈性，std::deque 的複雜度常數因子比 std::vecotr 高上許多，如果可以的話盡量使用 std::vector 或其它較為便宜的資料結構。

<list>

std::list 是一個極為沒效率的類別，它通常很少被使用，每個元素插入都會跟 Heap 要記憶體一次，並且也有極高的複雜度常數因子，特別是在使用較小的資料型別的時候。std::list 只提供雙向走訪，不提供隨機存取。

由於它個高成本，std::list 提供快速存取列表中兩端的元素（類似 std::deque，但不像 std::vector 或 SmallVector），另外 std::list 的 Iterator 比其它 vector 的型別所提供的 Iterator 更為強健可靠，插入或刪除元素的時候 Iterator 不會失效。

llvm/ADT/ilist.h

ilist<T> 實作一個侵入式（intrusive）的雙向串列（doubly-linked list），為啥叫侵入式式因為它把指向上下一個元素的指標塞到儲存的型別去了。

ilist 有著跟 std::list 的缺點，另外有個額外的外的需求就是儲存的型態必須有實作 ilist_traits ，但相對的它提供了一些有用的新特性，在實務上它可以有效的儲存多型物件（Polymorphic object），而 Trait Class 在元素插入或移除的時候相當有用，並且 ilist 保證在串列切割的時後只需要常數時間。

這些特性事實上正是在實作 Instructions 以及 Basic Block 時所需要的特性，事實上由 LLVM 文件中你可以發現它們是實作於 ilist。

相關的實作分別在以下幾個小節解釋：

ilist_traits
iplist
llvm/ADT/ilist_node.h
Sentinels （哨兵）

llvm/ADT/PackedVector.h

這東西拿來儲存那種每個元入都只有幾個位元的時候相當有用，它的操作界面跟一般 vector 類別的容器相當類似，另外它也提供 OR 的集合操作：

一段簡短範例：

enum State {
    None = 0x0,
    FirstCondition = 0x1,
    SecondCondition = 0x2,
    Both = 0x3
};
 
State get() {
    /* 儲存型別為 State, 每個元素佔用兩個位元 */
    PackedVector<State, 2> Vec1;
    Vec1.push_back(FirstCondition);
 
    PackedVector<State, 2> Vec2;
    Vec2.push_back(SecondCondition);
 
    Vec1 |= Vec2;
    return Vec1[0]; // 回傳 'Both'.
}

ilist_traits

ilist_traits<T> 是拿來給 ilist<T> 客製化的方法，iplist<T> 跟 ilist<T> 都是公開繼承自這個 Traits Class。

iplist

iplist<T>是 ilist<T> 的稍微弱化版，主要差別在於缺少插入 T& 的界面。

ilist_traits<T> 則是一個可以公開繼承的老爸，可以拿來作各式各樣的客製化。

llvm/ADT/ilist_node.h

ilist_node<T> 實作向前或向後的鍊結串列，ilist<T> 需要這些東東。

ilist_node<T> 是給節點型態 T 用的，而且通常 T 會公開繼承 ilist_node<T>。

Sentinels（哨兵）

ilist 有其它一些特殊的要求，為了成為 C++ 這個生態系統的好公民，它必須支援標準的容器操作如 begin 還有 end 的 Iterator ，另外 Operator— 也必須能夠正確在非空串列上的 End Iterator 運作。

而最直覺的解法就是在侵入式串列使用所謂的 Sentinels（哨兵）來處理 End Iterator，以此提供回去上一個元素的功能，並且在 C++ 慣例中，Operator++ 在 End Iterator 是不合法的，並且也不應該被 Dereference。

這些約束（Constraint）允許一些實作上的自由，例如 Sentinels（哨兵）怎麼儲存跟分配。這些相對應的策略則被規範在 ilist_traits<T>，預設的行為是當 Sentinels（哨兵）第一次被呼叫的時候會從 Heap 那邊要。

而預設的策略（Policy）可以應付大部分的情況，但可能會在 T 沒有提供預設建構子的時候爛掉，另外在當有很多 ilist 的情況下 Sentinels（哨兵）會浪費許多記憶體，而有一種小技巧被用於處理這種多餘的 Sentinels（哨兵），稱為 Ghostly Sentinels（幽靈哨兵）。

Ghostly Sentinels（幽靈哨兵）在 ilist_traits<T> 是使用一種特殊的技巧來實作在 ilist 上，我們利用指標運算來得到 Sentinels（哨兵），並且 ilist 使用額外的指標來去儲存 Sentinels（哨兵）的向前連結，使得 Ghostly Sentinels（幽靈哨兵）可以被正確的存取。

其它循序存取容器的選擇

其它的 STL 也可以用，例如 std::string。

另外許多的 STL Adapter Class （轉接器類別）例如 std::queue、std::priority_queue 以及 std::stack 等等，他們都提供簡單易懂的存取介面，並且不增加額外成本。

字串類型的容器

這邊提供了許多在 C、C++ 與 LLVM 中傳遞與使用字串的方法，一般而言直接挑選以下列表的第一個即可，另外下面的列表示按照使用成本來排序。

一般而言不建議你直接使用 const char* 來傳遞字串，它有許多缺點例如不能表示內嵌 nul 字元 ("\0")，以及沒辦法有效率的取得長度，在 LLVM 中通常是使用 StringRef 來取代 const char* 。

關於如何選擇字串容器的更詳細資訊請參照前面章節傳遞字串的部份

llvm/ADT/StringRef.h

StringRef 是拿來提供放置字元指標及其長度的類別，它有一點類似 ArrayRef （主要差別在於它是字元陣列的特製化版本），因為 StringRef 有儲存長度，因此它能夠處理內嵌 nul 字元 ("\0")的字串，並且取得字串長度不用透過 strlen，它有非常方便的切割與分割界面可以使用。

StringRef 是最適合拿來傳遞簡單字串的傢伙，其它例如 C String Literal、std::string、C Array 或 SmallVector 都可以隱式轉換為 StringRef，並且不需要動態的呼叫 strlen。

StringRef 有一些小限制，但因為這些限制而使得它成為更好的字串容器：

不能直接轉換 StringRef 到 const char * 因為它需要加入額外的 nul 字元（不能像其它類別中的 .c_str() 一樣直接轉換）。
StringRef 沒有底層儲存字串位元的擁有權，所以它可能會引發 Dangling Pointers，因此也不適合拿來嵌入在你的資料結構中使用（在這種情況就使用 std::string 或其它類似的傢伙比較適合）。
StringRef 也沒辦法拿來作為函數計算過後的回傳值，這種用途請使用 std::string
StringRef 不允許你拿來儲存會變動的字串，並且也不允許你插入或移除這段記憶體，如果你需要這類的操作的話請優先考慮 Twine 。

由於以上的限制，StringRef 經常用來傳遞參數，或著是回傳一些它內部自己擁有的字串_譯註1。

譯註1：例如回傳自己私有成員的常數字串

llvm/ADT/Twine.h

Twine 是拿來串接許多字串用的傢伙，並且 Twine 可以遞迴的建構於 Twine 之上，並且它只會在真的使用的時候才把內部要串接的字串一次串起來， Twine 通常只應該拿來當作函數的參數傳遞，並且只能透過 const reference 傳遞，例如：

  void foo(const Twine &T);
  ...
  StringRef X = ...
  unsigned i = ...
  foo(X + "." + Twine(i));

例如裡面串接完的字串是 "blarg.42"，那麼它內部並不儲存 "blarg" 或 "blarg."。
This example forms a string like "blarg.42" by concatenating the values together, and does not form intermediate strings containing "blarg" or "blarg.".

原因在於 Twine 會在 Stack 創造一個暫存物件，並且它會自動在這個 statement 後銷毀掉，因此它本質上是個有點危險的 API，例如在以下這種情況可能會產生 Undefined Behavior，並且可能爛掉：

  void foo(const Twine &T);
  ...
  StringRef X = ...
  unsigned i = ...
  const Twine &Tmp = X + "." + Twine(i);
  foo(Tmp);

主要是因為暫存物件會在函數呼叫前解構掉，但它比暫存的 std::string 有效率許多，並且 Twine 與 StringRef 可以一起運作的很好，請把它的一些使用限制謹記在心。

llvm/ADT/SmallString.h

SmallString 是一個 SmallVector 的特製化子類別，它加入了一些方便的 API 例如可以與 StringRef 直接 +=，SmallString 在字串長度小於預配置空間的時候可以不用額外分配記憶體，但在如果字串長度大於預配置空間時，則會使用 Heap 空間，它與 StringRef 及 Twine 相比，它擁有資料所有權，因此可以放心的對它進行字串的操作。

就像 SmallVector 一樣，SmallString 的大小會隨著它預分配的空間成長，它是設計來存放小型字串，但實際上它的大小並不小，因此它適合於存放於 Stack，不適合拿來存放於 Heap 空間。

std::string

標準的 C++ std::string 是相當一般化的類別，並且 sizeof(std::string) 也在可令人接受的範圍，因此適合放在 Heap 或著是嵌入其它資料結構當中，甚至是當回傳值也很適合，但在某些用途 std::string 是相當沒有效率的，例如在串接一沱字串的時候，另外由於它是標準函式庫的傢伙，所以效能基本上會隨著你使用的標準函式庫而定（利如 libc++ 跟 MSVC 提供高度最佳化的字串實作，GCC 則有一些非常龜速的實作）

主要的缺點是 std::string 幾乎每個操作都會分配 Heap 空間，因此一般而言使用 SmallVector 或 Twine 來當作暫存使用，但若當作回傳值則還是以 std::string 為主較佳。

集合類容器 (std::set, SmallSet, SetVector, 等等)

集合類型的容器在你需要剔除重複元素的時候相當有用，這邊提供了幾個不同的選擇，並且其實作上各有所取捨：

排序過的 'vector'

如果你需要插入很多元素以及大量查找，那麼有個好方法是用 vector (或著是其它的循序型容器)，加上 std::sort 及 std::unique 來去除重複的元素，如果在使用上有很明顯的將插入與查詢分為兩個階段的話，那麼循序型容器會是個很好的選擇。

這樣的組合提供許多良好的性質：

資料放在連續的記憶體區段（對於 Cache 有相當不錯的效果）
較少的記憶體配置次數
快速的 deference （vector 的 Iterator 通常只是指標而已）
可透過 binary search 或 radix search 快速查找

"llvm/ADT/SmallSet.h"

如果你的集合通常小於某個不會太大的數量的話，那麼 SmallSet<Type, N> 是你最佳的選擇，這個類別會把 N 個元素放在裡面（就像其它 Small* 家族一樣，只有在超過 N 個元素才會去 Heap 要空間），並且採用簡單的線性搜索，當元素多於 N 的時候，它會使用成本比較高的資料結構來保證其存取效率（大部分情況就是退化為 std::set ，但在儲存指標方面 SmallPtrSet 則提供更好的實作）。

這個神奇的類別在處理小集合的時候相當有效率，且在大集合的時候也有不錯的效率，他的界面則較為迷你一點：僅支援插入查詢刪除，不提供走訪功能。

"llvm/ADT/SmallPtrSet.h"

SmallPtrSet 有 SmallSet 的所有優點（SmallSet 是 transparently implement 於 SmallPtrSet），並且支援走訪功能，如果大於 N 次插入的話，則其 Hash Table 會一次成長二次方的大小，來保證其存取的效率（常數時間的插入刪除查詢，並且低常數因子），並且非常少呼叫 malloc。

另外要注意的是 SmallPtrSet 的 Iterator 會在插入後失效，不像 std::set 的 Iterator 插入後一樣可正常運作，另外走訪順序並不會依照順序走訪。

"llvm/ADT/DenseSet.h"

DenseSet 是一個簡易呈二次方成長的 Hash Table，它在支援小的資料型態的時候相當優異：在 Hash Table 不成長的情況下，只需要一次性的分配記憶體即可，DenseSet 是儲存非 Pointer 外小值的最佳選擇（存 Pointer 請往上看 SmallPtrSet），另外 DenseSet 對於儲存元素的要求與 DenseMap 一樣。

"llvm/ADT/SparseSet.h"

SparseSet 是拿來儲存中量的 unsigned 值，它會耗用許多記憶體來保證操作上與使用 vector 一樣快，一般而言是拿來儲存例如 Physical Register、Virtual Register 或著是 Basic Block 編號。

SparseSet 使用相當快的演算法來處理 clear/find/insert/erase 以及走訪，它不適合用於複雜的資料結構。

"llvm/ADT/FoldingSet.h"

FoldingSet 是設計來給那些創造成本很貴或著是多型物件的集合類別，它結合了侵入式連結（intrusive links）及 Hash Table （因此其元素必須繼承 FoldingSetNode），並且使用 SmallVector 來作為 ID _譯註1。

譯註1：大致上就是用 SmallVector 來紀錄串 unsigned value 來當 Hash Table 的 Key。

當你想要為某個很複雜的物件實作一個 getOrCreateFoo 這類方法的時候（例如在 Code Generator 的時候的 Node），使用端程式必須詳細描述要產生啥（承上面例子，例如 Opcode 及所有的 Operand），但我們實際上可能不需要創建一個新的 Node，你可以先查找集合中是否已經有一樣的 Node 存在，如果有的話那就把我們新創建的 Node 刪掉，並且重複使用已經存在的節點。

為了支援這一類的需求，FoldingSet 通常都是藉由 FoldingSetNodeID （底層是使用 SmallVector）來查詢，因此你需要把該元素的描述填上 FoldingSetNodeID ，如果集合裡面有找到該元素則會回傳他的 ID ，否則會回傳一個 opaque ID 供你插入新的元素進去，創建一個 ID 通常不須要跟 Heap 要空間。

由於 FoldingSet 使用侵入式連結，因此它能儲存多型物件（例如你可以插入 LoadSDNodes 到一個裝 SDNode 的 FoldingSet 中），因為各個元素是分別配置的，所以集合中的元素指標是穩定可靠的，插入或刪除都不會使得指向任何元素的指標失效。

<set>

std::set 是一個全能型的集合類別，它能夠在各方便都處理的不錯但也沒有特別優異的地方，std::set 在每次元素插入時都會分配一次記憶體（因此常會跟 malloc/new 打交道），內部實作中通常每個元素都會有儲存三個指標（需要相對大的單位附加成本），它的規格保證 log(n) 的效能，但在實務上這並不是很快（尤其在元素間比較成本很貴的時候，例如字串），並且查詢插入刪除的複雜度常數因子相當高。

std::set 的優點則是它的 Iterator 相當穩定（刪除插入都不會影響到 Iterator 或指向其中元素的指標），並且走訪時保證一定是照順序。如果元素很肥的話，那麼相對的 Heap 呼叫成本不是那麼大，但如果元素沒很肥的話，std::set 絕不會是最佳選擇。

"llvm/ADT/SetVector.h"

LLVM 提供 SetVector<Type> 來這個使用循序容器實作而成的集合容器，主要的重要功能是會自動砍掉重複元素，並且支援走訪功能，內部實作是會將插入的元素同時插入集合容器及循序容器，並且使用集合容器來去除重複元素，走訪時則使用循序容器。

SetVector 與其它容器最大的不同在於它走訪的時候保證會跟插入順序一樣，這個性質在集合都是存放 Pointer 時相當有用，因為 Pointer 的值是 non-deterministic 的，走訪集合中不同 Pointer 將不會有個 well-defined 的順序_譯註1。

譯註1：這段我真的不知道他在表達啥XD
原文：

The difference between SetVector and other sets is that the order of iteration is guaranteed to match the order of insertion into the SetVector. This property is really important for things like sets of pointers. Because pointer values are non-deterministic (e.g. vary across runs of the program on different machines), iterating over the pointers in the set will not be in a well-defined order.

SetVector 最大的缺點就是與其它集合容器相比需要兩倍的空間，並且其複雜度常數因子等於所使用的集合類別加上循序類別。請記得因為它很貴所以只有在存取順序很重要時使用 SetVector，並且它刪除元素需要線性時間，不然就是用 pop_back 踢掉最後一個元素則可以快些。

SetVector 預設是使用 std::vector 以及大小為 16 的 SmallSet ，所以它真的有一點貴，不過它也有提供 SmallSetVector 來讓你預設使用 SmallVector 及 SmallSet ，如果你動態大小都小於 N 的話，那麼用 SmallSetVector 會省下不少跟 Heap 溝通的時間。

"llvm/ADT/UniqueVector.h"

UniqueVector 有一點類似 SetVector ，但它會保留每個元素唯一 ID 到到集合中，它內部有一個 map 跟一個 vector ，並且會把唯一 ID 放到集合中。

UniqueVector 是個有點貴的傢伙，成本等於維護一個 map 跟 vecotr ，並且具有較高的複雜度與複雜度常數因子，並且需要很多的 Heap 溝通，盡量避免使用這傢伙。

"llvm/ADT/ImmutableSet.h"

ImmutableSet 是個不變的 (immutable) 集合，它實作於 AVL Tree 上，不論新增或刪除元素都會透過一個工廠物件(Factory object_譯註1)產生一個新的 ImmutableSet 物件，如果 ImmutableSet 已經存在的話，那它會傳回之前相同的那份，它是使用 FoldingSetNodeID 來作比較的動作，這傢伙不論新增或刪除元素的時間複雜度或空間複雜度都是原本那個集合大小的 log 時間。

譯註1：詳細可以參考 Design Pattern 的 Factory Pattern。

另外你沒有辦法叫它吐出集合中的東西，只能檢查一個元素是否存在該集合中。

其它集合容器選項

事實上 STL 提供了許多不同的選項例如 std::multiset 以及一些 hash_set （C++ TR1），在 LLVM 中我們不使用 hash_set 或著 unordered_set，主要原因在於它們很貴而且不具可攜性。

std::multiset 只有在你不想砍掉重複元素時有用，但它有所有 std::set 的缺點，一個排序好的 vector 或其它的方式都比這東西好。

Map 類型容器 (std::map, DenseMap, 等等)

在你需要有個 Key 對應到某個 Data 時， Map 類型的容器是你的好朋友，這裡有提供許多的方式供你選擇:)

排序過的 'vector'

如果你的使用模式是插入-查詢的話，那你可以使用排序過的 vector 來作為 Map 容器就像排序過的 vector 當作集合容器那樣，差別在於你的查詢函數(使用 std::lower_bound 可以在 log(n) 時間內查詢)只能比對 Key 值，他的優點跟排序過的 vector 作為集合容器一樣。

"llvm/ADT/StringMap.h"

字串是經常會拿來當作 Map 的 Key 的型態，但是又通常不容易有效率的實作，主要是因為字串是變動長度，不容易有效的 Hash ，比對時間呈線性，並且複製成本較高，因此 StringMap 是一個設計來克服這些問題的高度特製化容器，它支援任意範圍的位元到任意的物件去。

StringMap 使用的是 Quadratically-probed 的 Hash Table，Hash Table 中的格子則儲存指向 Heap 空間的指標，主要原因是字串是變動長度的，在實作細節上，字串(Key)是直接儲存在其對應的資料(Value)後方，意思是容器會跟你保證 (char*)(&Value+1) 就是放 Key 的字串。

StringMap 實作上相當有效率，原因在於 Quadratic Probing 在查找時相當 Cache Efficient，並且字串的 Hash Value 在查找的時候不會一直重新計算，StringMap 查找時會盡量避免去存取不相關物件的記憶體(即使在碰撞發生時也是)，在 Hash Table 長大的時候， Hash Value 也不需要重新計算，每個 Key-Value Pair 也保證只會分配一次記憶體。

StringMap 也提供使用特定位元範圍來查找，所以它只需要在插入新的值得時候才會複製到 Hash Table 中。

StringMap 在走訪順序則沒有保證任何的順序性，所以如果你有任何需求的話，還是使用 std::map 唄。

"llvm/ADT/IndexedMap.h"

IndexedMap 是為了對應一段很密集整數(或著是 Value 可以對應到又小又密集的整數的話也可以)的特製化容器，它內部是使用 Vector 來去儲存及對應它的 Key-Value。

這種容器在儲存例如 Virtual Register 的時候相當有用，它們密度相當高，並且有固定起始範圍(第一個 Virtual Register ID)。

"llvm/ADT/DenseMap.h"

DenseMap is a simple quadratically probed hash table. It excels at supporting small keys and values: it uses a single allocation to hold all of the pairs that are currently inserted in the map. DenseMap is a great way to map pointers to pointers, or map other small types to each other.

There are several aspects of DenseMap that you should be aware of, however. The iterators in a DenseMap are invalidated whenever an insertion occurs, unlike map. Also, because DenseMap allocates space for a large number of key/value pairs (it starts with 64 by default), it will waste a lot of space if your keys or values are large. Finally, you must implement a partial specialization of DenseMapInfo for the key that you want, if it isn't already supported. This is required to tell DenseMap about two special marker values (which can never be inserted into the map) that it needs internally.

DenseMap's find_as() method supports lookup operations using an alternate key type. This is useful in cases where the normal key type is expensive to construct, but cheap to compare against. The DenseMapInfo is responsible for defining the appropriate comparison and hashing methods for each alternate key type used.

"llvm/ADT/ValueMap.h"

ValueMap is a wrapper around a DenseMap mapping Value*s (or subclasses) to another type. When a Value is deleted or RAUW'ed, ValueMap will update itself so the new version of the key is mapped to the same value, just as if the key were a WeakVH. You can configure exactly how this happens, and what else happens on these two events, by passing a Config parameter to the ValueMap template.

"llvm/ADT/IntervalMap.h"

IntervalMap is a compact map for small keys and values. It maps key intervals instead of single keys, and it will automatically coalesce adjacent intervals. When then map only contains a few intervals, they are stored in the map object itself to avoid allocations.

The IntervalMap iterators are quite big, so they should not be passed around as STL iterators. The heavyweight iterators allow a smaller data structure.

<map>

std::map has similar characteristics to std::set: it uses a single allocation per pair inserted into the map, it offers log(n) lookup with an extremely large constant factor, imposes a space penalty of 3 pointers per pair in the map, etc.

std::map is most useful when your keys or values are very large, if you need to iterate over the collection in sorted order, or if you need stable iterators into the map (i.e. they don't get invalidated if an insertion or deletion of another element takes place).

"llvm/ADT/MapVector.h"

MapVector<KeyT,ValueT> provides a subset of the DenseMap interface. The main difference is that the iteration order is guaranteed to be the insertion order, making it an easy (but somewhat expensive) solution for non-deterministic iteration over maps of pointers.

It is implemented by mapping from key to an index in a vector of key,value pairs. This provides fast lookup and iteration, but has two main drawbacks: The key is stored twice and it doesn't support removing elements.

"llvm/ADT/IntEqClasses.h"

IntEqClasses provides a compact representation of equivalence classes of small integers. Initially, each integer in the range 0..n-1 has its own equivalence class. Classes can be joined by passing two class representatives to the join(a, b) method. Two integers are in the same class when findLeader() returns the same representative.

Once all equivalence classes are formed, the map can be compressed so each integer 0..n-1 maps to an equivalence class number in the range 0..m-1, where m is the total number of equivalence classes. The map must be uncompressed before it can be edited again.

"llvm/ADT/ImmutableMap.h"

ImmutableMap is an immutable (functional) map implementation based on an AVL tree. Adding or removing elements is done through a Factory object and results in the creation of a new ImmutableMap object. If an ImmutableMap already exists with the given key set, then the existing one is returned; equality is compared with a FoldingSetNodeID. The time and space complexity of add or remove operations is logarithmic in the size of the original map.

Other Map-Like Container Options

The STL provides several other options, such as std::multimap and the various "hash_map" like containers (whether from C++ TR1 or from the SGI library). We never use hash_set and unordered_set because they are generally very expensive (each insertion requires a malloc) and very non-portable.

std::multimap is useful if you want to map a key to multiple values, but has all the drawbacks of std::map. A sorted vector or some other approach is almost always better.

Bit 儲存容器 (BitVector, SparseBitVector)

不象其它容器, 這邊只有三種選擇, 而選擇要用哪一種則會依照跟儲存及存取方式來選擇.

當然這邊還有一個另外的選擇就是 std::vector<bool>: 不過我們並不鼓勵開法者使用它, 原因有二 1) 它的實作在大部分的 Compiler 都很鳥 (例如大部分 gcc) 2) C++ 標準委員會也傾向於 deprecate 它, 所以在任何情況下請不要考慮使用 std::vector<bool>.

BitVector

BitVector 容器提供動態大小的 bit 集合操作. 它提供單一 bit 的設定/測試的界面, 並且提供所有的集合運算. 集合運算的時間複雜度大多是 O(size of bitvector), 一次執行的單位是一個 Word, 而不是一個 bit, 跟其它容器相比, BitVector 相對的迅速許多. 當你需要比較多的 bit 集合時(例如 Dense Set), BitVector 是你的最佳選擇.

SmallBitVector

SmallBitVector 容器提供跟 BitVector 一樣的界面, 差別在於 SmallBitVector 有針對少量 bit 特別最佳化過, 少於 25 個 bit 時則超會超快. 它一樣可以儲存大量的 bit, 但表現相對於 BitVector 會略遜色一些, 所以請記得只有在幾乎是小量的時候採用 SmallBitVector.

另外目前 SmallBitVector 不提供集合運算 (and, or, xor) 以及 Operator[] 僅提供唯讀的 lvalue.

SparseBitVector

SparseBitVector 有點類似 BitVector, 但有個決定性的不同點在於：只有在該 bit 在集合的時後會儲存, 這會使得 SparseBitVector 比 BitVector 在集合比較鬆散的時候有較好的空間效率, 並且它的集合操作的時間複雜度是 O(size of universe) 而不是 O(number of set bits). 而 SparseBitVector 的缺點則是在測試及設定單一 bit 時的時間複雜度是 O(N), 尤其在資料數量大的時候 SparseBitVectors 會明顯比 BitVector 慢. 在目前的實作當中若測試或著是設定在固定方向(固定往前或往後)的話時間複雜度則會降到 O(1). 另外在 128 bit 內的操作也都會是 O(1). 一般而言, 測試或設定的時間複雜度是與上次存取的距離呈現線性關係.

常用操作的小提示集

這部份描述如何間單的操作 LLVM 的程式，主要會有個小範例來告訴你如何使用 LLVM 的 Transformation。

當然這部份只是描述如何操作的章節，你還是需要去讀那些主要類別的文件，LLVM 核心類別的參考文件有更多你必須知道的細節跟描述。

基礎的走訪與檢查函數

在 LLVM 裡面有許多不同的資料結構可以走訪，並且界面大致上是與 C++ STL 的走訪界面相仿，例如對於大部分可走訪的值都會提供 xxxbegin() 及 xxxend() 函數，來回傳指向頭尾的 Iterator，並且也都會提供相對應的 xxxiterator 型態。

而這種形式的走訪在整個程式不同層面的內部表示中都相當適用，並且 STL 中的演算法部份也可以直接套用上去，這樣也可以使人較容易記住要怎麼走訪，接著就來看看一些 LLVM 中常見的資料結構要如何被走訪，其它沒被提及到的資料結構的走訪事實上也都相當類似。

走訪一個函數中的所有 BasicBlock

這是一個相當常見的例子，例如說你有一個 Function ，並且要對它最某些轉換，那通常需要操作該 Function 的 BasicBlcok ，例如走訪該函數的所有 BasicBlock ，下面這個例子則說明如何印出 BasicBlock 的名字與其中有幾道指令：

// func 是一個指向 Function 的指標
for (Function::iterator i = func->begin(), e = func->end(); i != e; ++i)
  // 印出 Basic Block 的名字以及指令的數目
  errs() << "Basic block (name=" << i->getName() << ") has "
             << i->size() << " instructions.\n";

走訪一個 Basic Block 中的所有 Instructions

就像走訪整個函數的 BasicBlock 一樣，走訪 BasicBlock 中所有指令也相當的容易，下面則是印出 BasicBlock 中每道指令的範例：

// blk 是一個指向 BasicBlock 的指標
for (BasicBlock::iterator i = blk->begin(), e = blk->end(); i != e; ++i)
   // 印出指令內容
   errs() << *i << "\n";

不過要注意的是使用 ostream _譯註來觀察 BasicBlock 中的資訊，最好的方式還是採用 errs() ，他會呼叫 BasicBlock 的 print 函數，印出的資訊會較為好讀。

譯註：指 c++ std::cout 或 std::cerr 之類的 output stream

走訪一個函數中的所有 Instructions

If you're finding that you commonly iterate over a Function's BasicBlocks and then that BasicBlock's Instructions, InstIterator should be used instead. You'll need to include and then instantiate InstIterators explicitly in your code. Here's a small example that shows how to dump all instructions in a function to the standard error stream:

如果你想要走訪一個函數所有 BasicBlock 中的所有 Instruction 的話，使用 InstIterator 會是較好的選擇，只要 include llvm/Support/InstIterator.h 即可使用，以下是簡短的使用範例：

#include "llvm/Support/InstIterator.h"

// F 是一個指到 Function 的 pointer
for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
  errs() << *I << "\n";

簡單好用吧，在一些 Work-List-based 演算法中你可以利用這種方式，例如你要初始化 Work-List 為該函數所有指令，那麼可以這樣寫：

std::set<Instruction*> worklist;
// 或著是 SmallPtrSet<Instruction*, 64> worklist;

for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
   worklist.insert(&*I);

執行完後 std::set worklist 就裝了滿滿的 Instruction！

把 Iterator 轉換程該類別的 Pointer

有時候你會想把拿取到的 Iterator 轉換成 Reference 或 Pointer ，直接來看以下的範例程式，其中 i 是 BasicBlock::iterator 而 j 是 BasicBlock::const_iterator：
Sometimes, it'll be useful to grab a reference (or pointer) to a class instance when all you've got at hand is an iterator. Well, extracting a reference or a pointer from an iterator is very straight-forward. Assuming that i is a BasicBlock::iterator and j is a BasicBlock::const_iterator:

Instruction& inst = *i;   // Grab reference to instruction reference
Instruction* pinst = &*i; // Grab pointer to instruction reference
const Instruction& inst = *j;

However, the iterators you'll be working with in the LLVM framework are special: they will automatically convert to a ptr-to-instance type whenever they need to. Instead of dereferencing the iterator and then taking the address of the result, you can simply assign the iterator to the proper pointer type and you get the dereference and address-of operation as a result of the assignment (behind the scenes, this is a result of overloading casting mechanisms). Thus the last line of the last example,

Instruction *pinst = &*i;

is semantically equivalent to

Instruction *pinst = i;

It's also possible to turn a class pointer into the corresponding iterator, and this is a constant time operation (very efficient). The following code snippet illustrates use of the conversion constructors provided by LLVM iterators. By using these, you can explicitly grab the iterator of something without actually obtaining it via iteration over some structure:

void printNextInstruction(Instruction* inst) {
  BasicBlock::iterator it(inst);
  ++it; // After this line, it refers to the instruction after *inst
  if (it != inst->getParent()->end()) errs() << *it << "\n";
}

Unfortunately, these implicit conversions come at a cost; they prevent these iterators from conforming to standard iterator conventions, and thus from being usable with standard algorithms and containers. For example, they prevent the following code, where B is a BasicBlock, from compiling:

  llvm::SmallVector<llvm::Instruction *, 16>(B->begin(), B->end());

Because of this, these implicit conversions may be removed some day, and operator* changed to return a pointer instead of a reference.

找出所有呼叫函數的地方：一個稍微複雜的例子

Say that you're writing a FunctionPass and would like to count all the locations in the entire module (that is, across every Function) where a certain function (i.e., some Function*) is already in scope. As you'll learn later, you may want to use an InstVisitor to accomplish this in a much more straight-forward manner, but this example will allow us to explore how you'd do it if you didn't have InstVisitor around. In pseudo-code, this is what we want to do:

initialize callCounter to zero
for each Function f in the Module
  for each BasicBlock b in f
    for each Instruction i in b
      if (i is a CallInst and calls the given function)
        increment callCounter

And the actual code is (remember, because we're writing a FunctionPass, our FunctionPass-derived class simply has to override the runOnFunction method):

Function* targetFunc = ...;

class OurFunctionPass : public FunctionPass {
  public:
    OurFunctionPass(): callCounter(0) { }

    virtual runOnFunction(Function& F) {
      for (Function::iterator b = F.begin(), be = F.end(); b != be; ++b) {
        for (BasicBlock::iterator i = b->begin(), ie = b->end(); i != ie; ++i) {
          if (CallInst* callInst = dyn_cast<CallInst>(&*i)) {
            // We know we've encountered a call instruction, so we
            // need to determine if it's a call to the
            // function pointed to by m_func or not.
            if (callInst->getCalledFunction() == targetFunc)
              ++callCounter;
          }
        }
      }
    }

  private:
    unsigned callCounter;
};

Treating calls and invokes the same way

You may have noticed that the previous example was a bit oversimplified in that it did not deal with call sites generated by 'invoke' instructions. In this, and in other situations, you may find that you want to treat CallInsts and InvokeInsts the same way, even though their most-specific common base class is Instruction, which includes lots of less closely-related things. For these cases, LLVM provides a handy wrapper class called CallSite. It is essentially a wrapper around an Instruction pointer, with some methods that provide functionality common to CallInsts and InvokeInsts.

This class has "value semantics": it should be passed by value, not by reference and it should not be dynamically allocated or deallocated using operator new or operator delete. It is efficiently copyable, assignable and constructable, with costs equivalents to that of a bare pointer. If you look at its definition, it has only a single pointer member.

Iterating over def-use & use-def chains

Frequently, we might have an instance of the Value Class and we want to determine which Users use the Value. The list of all Users of a particular Value is called a def-use chain. For example, let's say we have a Function* named F to a particular function foo. Finding all of the instructions that use foo is as simple as iterating over the def-use chain of F:

Function *F = ...;

for (Value::use_iterator i = F->use_begin(), e = F->use_end(); i != e; ++i)
  if (Instruction *Inst = dyn_cast<Instruction>(*i)) {
    errs() << "F is used in instruction:\n";
    errs() << *Inst << "\n";
  }

Note that dereferencing a Value::use_iterator is not a very cheap operation. Instead of performing *i above several times, consider doing it only once in the loop body and reusing its result.

Alternatively, it's common to have an instance of the User Class and need to know what Values are used by it. The list of all Values used by a User is known as a use-def chain. Instances of class Instruction are common Users, so we might want to iterate over all of the values that a particular instruction uses (that is, the operands of the particular Instruction):

Instruction *pi = ...;

for (User::op_iterator i = pi->op_begin(), e = pi->op_end(); i != e; ++i) {
  Value *v = *i;
  // ...
}

Declaring objects as const is an important tool of enforcing mutation free algorithms (such as analyses, etc.). For this purpose above iterators come in constant flavors as Value::const_use_iterator and Value::const_op_iterator. They automatically arise when calling use/op_begin() on const Value*s or const User*s respectively. Upon dereferencing, they return const Use*s. Otherwise the above patterns remain unchanged.

Iterating over predecessors & successors of blocks

Iterating over the predecessors and successors of a block is quite easy with the routines defined in "llvm/Support/CFG.h". Just use code like this to iterate over all predecessors of BB:

#include "llvm/Support/CFG.h"
BasicBlock *BB = ...;

for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
  BasicBlock *Pred = *PI;
  // ...
}

Similarly, to iterate over successors use succ_iterator/succ_begin/succ_end.

Making simple changes

There are some primitive transformation operations present in the LLVM infrastructure that are worth knowing about. When performing transformations, it's fairly common to manipulate the contents of basic blocks. This section describes some of the common methods for doing so and gives example code.

產生及插入新的指令

產生一道指令

產生一道指令是相當簡單的：只要呼叫該指令的建構子 (Constructor)，以及提供所需要的參數即可，例如要產生一個 AllocaInst 指令, 他的第一個參數是一個 Type 的 const pointer. 以下是範例程式：

AllocaInst* ai = new AllocaInst(Type::Int32Ty);

上面那段程式會產生一道 AllocaInst 指令，在執行時期在 Stack Frame 上分配一個型別為 32 bit 整數的區域變數的指令。每一道指令都會許多不同的參數組合，並且要注意參數不同所代表的語意也可能大不同，所以在開發的時候記得一定要參考 doxygen 所產生出來的文件。

為值命名

為一個指令的值命名對 Debug 的時候相當的有用。當你去查看最佳化或任何轉換後的 LLVM IR，如果沒有名字的話將會非常難以去驗證及除錯。
It is very useful to name the values of instructions when you're able to, as this facilitates the debugging of your transformations. If you end up looking at generated LLVM machine code, you definitely want to have logical names associated with the results of instructions!

要讓一個值有名字的話通常在建構子中會有一個參數名稱叫 Name 的參數，接著你把名字塞到該參數位置即可
舉例來說，你正在寫一個 Transformation 會需要動態的去分配空間，然後會把它當作索引使用，所以把它放在一開始的某個地方
長的會類似下面這樣：

AllocaInst* pa = new AllocaInst(Type::Int32Ty, 0, "indexLoc");

indexLoc 就是這個值的名稱。

插入指令

在插入指令到一個 Basic Block 主要有兩個方式可以使用：

Insertion into an explicit instruction list 插入到一個明確的位置

給定一個 Basic Block 的指標 BasicBlock *pb, 及一道指令 Instruction *pi，接著我們要插入一道新的指令到 *pi 的前面，可以這樣寫：

BasicBlock *pb = ...;
Instruction *pi = ...;
Instruction *newInst = new Instruction(...);

pb->getInstList().insert(pi, newInst); // 把 newInst 插入 pb 裡面，位置是 pi 的前面

Appending to the end of a BasicBlock is so common that the Instruction class and Instruction-derived
classes provide constructors which take a pointer to a BasicBlock to be appended to. For example code
that looked like:

BasicBlock *pb = ...;
Instruction *newInst = new Instruction(...);

pb->getInstList().push_back(newInst); // Appends newInst to pb

becomes:

BasicBlock *pb = ...;
Instruction *newInst = new Instruction(..., pb);

which is much cleaner, especially if you are creating long instruction streams.

Insertion into an implicit instruction list

Instruction instances that are already in BasicBlocks are implicitly associated with an existing instruction list: the instruction list of the enclosing basic block. Thus, we could have accomplished the same thing as the above code without being given a BasicBlock by doing:

Instruction *pi = ...;
Instruction *newInst = new Instruction(...);

pi->getParent()->getInstList().insert(pi, newInst);

In fact, this sequence of steps occurs so frequently that the Instruction class and Instruction-derived classes provide constructors which take (as a default parameter) a pointer to an Instruction which the newly-created Instruction should precede. That is, Instruction constructors are capable of inserting the newly-created instance into the BasicBlock of a provided instruction, immediately before that instruction. Using an Instruction constructor with a insertBefore (default) parameter, the above code becomes:

Deleting Instructions

Deleting an instruction from an existing sequence of instructions that form a BasicBlock is very straight-forward: just call the instruction's eraseFromParent() method. For example:

Instruction *I = .. ;
I->eraseFromParent();

This unlinks the instruction from its containing basic block and deletes it. If you'd just like to unlink the instruction from its containing basic block but not delete it, you can use the removeFromParent() method.

Replacing an Instruction with another Value

Replacing individual instructions

Including "llvm/Transforms/Utils/BasicBlockUtils.h" permits use of two very useful replace functions: ReplaceInstWithValue and ReplaceInstWithInst.

Deleting Instructions

ReplaceInstWithValue

This function replaces all uses of a given instruction with a value, and then removes the original instruction. The following example illustrates the replacement of the result of a particular AllocaInst that allocates memory for a single integer with a null pointer to an integer.

AllocaInst* instToReplace = ...;
BasicBlock::iterator ii(instToReplace);

ReplaceInstWithValue(instToReplace->getParent()->getInstList(), ii,
                     Constant::getNullValue(PointerType::getUnqual(Type::Int32Ty)));

ReplaceInstWithInst

This function replaces a particular instruction with another instruction, inserting the new instruction into the basic block at the location where the old instruction was, and replacing any uses of the old instruction with the new instruction. The following example illustrates the replacement of one AllocaInst with another.

AllocaInst* instToReplace = ...;
BasicBlock::iterator ii(instToReplace);

ReplaceInstWithInst(instToReplace->getParent()->getInstList(), ii,
                    new AllocaInst(Type::Int32Ty, 0, "ptrToReplacedInt"));

Replacing multiple uses of Users and Values

You can use Value::replaceAllUsesWith and User::replaceUsesOfWith to change more than one use at a time. See the doxygen documentation for the Value Class and User Class, respectively, for more information.

Deleting GlobalVariables

Deleting a global variable from a module is just as easy as deleting an Instruction. First, you must have a pointer to the global variable that you wish to delete. You use this pointer to erase it from its parent, the module. For example:

GlobalVariable *GV = .. ;

GV->eraseFromParent();

How to Create Types

In generating IR, you may need some complex types. If you know these types statically, you can use TypeBuilder<…>::get(), defined in llvm/Support/TypeBuilder.h, to retrieve them. TypeBuilder has two forms depending on whether you're building types for cross-compilation or native library use. TypeBuilder<T, true> requires that T be independent of the host environment, meaning that it's built out of types from the llvm::types namespace and pointers, functions, arrays, etc. built of those. TypeBuilder<T, false> additionally allows native C types whose size may depend on the host compiler. For example,

FunctionType *ft = TypeBuilder<types::i<8>(types::i<32>*), true>::get();

is easier to read and write than the equivalent

std::vector<const Type*> params;
params.push_back(PointerType::getUnqual(Type::Int32Ty));
FunctionType *ft = FunctionType::get(Type::Int8Ty, params, false);

See the class comment for more details.

執行緒與 LLVM

This section describes the interaction of the LLVM APIs with multithreading, both on the part of client applications, and in the JIT, in the hosted application.

Note that LLVM's support for multithreading is still relatively young. Up through version 2.5, the execution of threaded hosted applications was supported, but not threaded client access to the APIs. While this use case is now supported, clients must adhere to the guidelines specified below to ensure proper operation in multithreaded mode.

Note that, on Unix-like platforms, LLVM requires the presence of GCC's atomic intrinsics in order to support threaded operation. If you need a multhreading-capable LLVM on a platform without a suitably modern system compiler, consider compiling LLVM and LLVM-GCC in single-threaded mode, and using the resultant compiler to build a copy of LLVM with multithreading support.

Entering and Exiting Multithreaded Mode

In order to properly protect its internal data structures while avoiding excessive locking overhead in the single-threaded case, the LLVM must intialize certain data structures necessary to provide guards around its internals. To do so, the client program must invoke llvm_start_multithreaded() before making any concurrent LLVM API calls. To subsequently tear down these structures, use the llvm_stop_multithreaded() call. You can also use the llvm_is_multithreaded() call to check the status of multithreaded mode.

Note that both of these calls must be made in isolation. That is to say that no other LLVM API calls may be executing at any time during the execution of llvm_start_multithreaded() or llvm_stop_multithreaded . It's is the client's responsibility to enforce this isolation.

The return value of llvm_start_multithreaded() indicates the success or failure of the initialization. Failure typically indicates that your copy of LLVM was built without multithreading support, typically because GCC atomic intrinsics were not found in your system compiler. In this case, the LLVM API will not be safe for concurrent calls. However, it will be safe for hosting threaded applications in the JIT, though care must be taken to ensure that side exits and the like do not accidentally result in concurrent LLVM API calls.

Ending Execution with llvm_shutdown()

When you are done using the LLVM APIs, you should call llvm_shutdown() to deallocate memory used for internal structures. This will also invoke llvm_stop_multithreaded() if LLVM is operating in multithreaded mode. As such, llvm_shutdown() requires the same isolation guarantees as llvm_stop_multithreaded().

Note that, if you use scope-based shutdown, you can use the llvm_shutdown_obj class, which calls llvm_shutdown() in its destructor.

Lazy Initialization with ManagedStatic

ManagedStatic is a utility class in LLVM used to implement static initialization of static resources, such as the global type tables. Before the invocation of llvm_shutdown(), it implements a simple lazy initialization scheme. Once llvm_start_multithreaded() returns, however, it uses double-checked locking to implement thread-safe lazy initialization.

Note that, because no other threads are allowed to issue LLVM API calls before llvm_start_multithreaded() returns, it is possible to have ManagedStatics of llvm::sys::Mutexs.

The llvm_acquire_global_lock() and llvm_release_global_lock APIs provide access to the global lock used to implement the double-checked locking for lazy initialization. These should only be used internally to LLVM, and only if you know what you're doing!

使用 LLVMContext 來達到隔離效果

LLVMContext is an opaque class in the LLVM API which clients can use to operate multiple, isolated instances of LLVM concurrently within the same address space. For instance, in a hypothetical compile-server, the compilation of an individual translation unit is conceptually independent from all the others, and it would be desirable to be able to compile incoming translation units concurrently on independent server threads. Fortunately, LLVMContext exists to enable just this kind of scenario!

Conceptually, LLVMContext provides isolation. Every LLVM entity (Modules, Values, Types, Constants, etc.) in LLVM's in-memory IR belongs to an LLVMContext. Entities in different contexts cannot interact with each other: Modules in different contexts cannot be linked together, Functions cannot be added to Modules in different contexts, etc. What this means is that is is safe to compile on multiple threads simultaneously, as long as no two threads operate on entities within the same context.

In practice, very few places in the API require the explicit specification of a LLVMContext, other than the Type creation/lookup APIs. Because every Type carries a reference to its owning context, most other entities can determine what context they belong to by looking at their own Type. If you are adding new entities to LLVM IR, please try to maintain this interface design.

For clients that do not require the benefits of isolation, LLVM provides a convenience API getGlobalContext(). This returns a global, lazily initialized LLVMContext that may be used in situations where isolation is not a concern.

執行緒與 JIT

LLVM's "eager" JIT compiler is safe to use in threaded programs. Multiple threads can call ExecutionEngine::getPointerToFunction() or ExecutionEngine::runFunction() concurrently, and multiple threads can run code output by the JIT concurrently. The user must still ensure that only one thread accesses IR in a given LLVMContext while another thread might be modifying it. One way to do that is to always hold the JIT lock while accessing IR outside the JIT (the JIT modifies the IR by adding CallbackVHs). Another way is to only call getPointerToFunction() from the LLVMContext's thread.

When the JIT is configured to compile lazily (using ExecutionEngine::DisableLazyCompilation(false)), there is currently a race condition in updating call sites after a function is lazily-jitted. It's still possible to use the lazy JIT in a threaded program if you ensure that only one thread at a time can call any particular lazy stub and that the JIT lock guards any IR access, but we suggest using only the eager JIT in threaded programs.

進階議題

This section describes some of the advanced or obscure API's that most clients do not need to be aware of. These API's tend manage the inner workings of the LLVM system, and only need to be accessed in unusual circumstances.

The ValueSymbolTable class

The ValueSymbolTable class provides a symbol table that the Function and Module classes use for naming value definitions. The symbol table can provide a name for any Value.

Note that the SymbolTable class should not be directly accessed by most clients. It should only be used when iteration over the symbol table names themselves are required, which is very special purpose. Note that not all LLVM Values have names, and those without names (i.e. they have an empty name) do not exist in the symbol table.

Symbol tables support iteration over the values in the symbol table with begin/end/iterator and supports querying to see if a specific name is in the symbol table (with lookup). The ValueSymbolTable class exposes no public mutator methods, instead, simply call setName on a value, which will autoinsert it into the appropriate symbol table.

The User and owned Use classes' memory layout

The User class provides a basis for expressing the ownership of User towards other Values. The Use helper class is employed to do the bookkeeping and to facilitate O(1) addition and removal.

Interaction and relationship between User and Use objects

A subclass of User can choose between incorporating its Use objects or refer to them out-of-line by means of a pointer. A mixed variant (some Uses inline others hung off) is impractical and breaks the invariant that the Use objects belonging to the same User form a contiguous array.

We have 2 different layouts in the User (sub)classes:

Layout a) The Use object(s) are inside (resp. at fixed offset) of the User object and there are a fixed number of them.
Layout b) The Use object(s) are referenced by a pointer to an array from the User object and there may be a variable number of them.

As of v2.4 each layout still possesses a direct pointer to the start of the array of Uses. Though not mandatory for layout a), we stick to this redundancy for the sake of simplicity. The User object also stores the number of Use objects it has. (Theoretically this information can also be calculated given the scheme presented below.)

Special forms of allocation operators (operator new) enforce the following memory layouts:

Layout a) is modelled by prepending the User object by the Use[] array.

...---.---.---.---.-------...
  | P | P | P | P | User
'''---'---'---'---'-------'''

Layout b) is modelled by pointing at the Use[] array.

.-------...
| User
'-------'''
    |
    v
    .---.---.---.---...
    | P | P | P | P |
    '---'---'---'---'''

(In the above figures 'P' stands for the Use** that is stored in each Use object in the member Use::Prev)

waymarking 演算法

Since the Use objects are deprived of the direct (back)pointer to their User objects, there must be a fast and exact method to recover it. This is accomplished by the following scheme:

A bit-encoding in the 2 LSBits (least significant bits) of the Use::Prev allows to find the start of the User object:

00 —> binary digit 0
01 —> binary digit 1
10 —> stop and calculate (s)
11 —> full stop (S)

Given a Use*, all we have to do is to walk till we get a stop and we either have a User immediately behind or we have to walk to the next stop picking up digits and calculating the offset:

.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.----------------
| 1 | s | 1 | 0 | 1 | 0 | s | 1 | 1 | 0 | s | 1 | 1 | s | 1 | S | User (or User*)
'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'----------------
    |+15                |+10            |+6         |+3     |+1
    |                   |               |           |       |__>
    |                   |               |           |__________>
    |                   |               |______________________>
    |                   |______________________________________>
    |__________________________________________________________>

Only the significant number of bits need to be stored between the stops, so that the worst case is 20 memory accesses when there are 1000 Use objects associated with a User.

Reference implementation

The following literate Haskell fragment demonstrates the concept:

> import Test.QuickCheck
> 
> digits :: Int -> [Char] -> [Char]
> digits 0 acc = '0' : acc
> digits 1 acc = '1' : acc
> digits n acc = digits (n `div` 2) $ digits (n `mod` 2) acc
> 
> dist :: Int -> [Char] -> [Char]
> dist 0 [] = ['S']
> dist 0 acc = acc
> dist 1 acc = let r = dist 0 acc in 's' : digits (length r) r
> dist n acc = dist (n - 1) $ dist 1 acc
> 
> takeLast n ss = reverse $ take n $ reverse ss
> 
> test = takeLast 40 $ dist 20 []
>

Printing <test> gives: "1s100000s11010s10100s1111s1010s110s11s1S"

The reverse algorithm computes the length of the string just by examining a certain prefix:

> pref :: [Char] -> Int
> pref "S" = 1
> pref ('s':'1':rest) = decode 2 1 rest
> pref (_:rest) = 1 + pref rest
> 
> decode walk acc ('0':rest) = decode (walk + 1) (acc * 2) rest
> decode walk acc ('1':rest) = decode (walk + 1) (acc * 2 + 1) rest
> decode walk acc _ = walk + acc
>

Now, as expected, printing <pref test> gives 40.

We can quickCheck this with following property:

> testcase = dist 2000 []
> testcaseLength = length testcase
> 
> identityProp n = n > 0 && n <= testcaseLength ==> length arr == pref arr
>     where arr = takeLast n testcase
>

As expected <quickCheck identityProp> gives:

*Main> quickCheck identityProp
OK, passed 100 tests.
Let's be a bit more exhaustive:

> 
> deepCheck p = check (defaultConfig { configMaxTest = 500 }) p
>

And here is the result of <deepCheck identityProp>:

*Main> deepCheck identityProp
OK, passed 500 tests.

Tagging considerations

To maintain the invariant that the 2 LSBits of each Use** in Use never change after being set up, setters of Use::Prev must re-tag the new Use** on every modification. Accordingly getters must strip the tag bits.

For layout b) instead of the User we find a pointer (User* with LSBit set). Following this pointer brings us to the User. A portable trick ensures that the first bytes of User (if interpreted as a pointer) never has the LSBit set. (Portability is relying on the fact that all known compilers place the vptr in the first word of the instances.)

The Core LLVM Class Hierarchy Reference

#include "llvm/Type.h"
doxygen info: Type Class

The Core LLVM classes are the primary means of representing the program being inspected or transformed. The core LLVM classes are defined in header files in the include/llvm/ directory, and implemented in the lib/VMCore directory.

The Type class and Derived Types

Type is a superclass of all type classes. Every Value has a Type. Type cannot be instantiated directly but only through its subclasses. Certain primitive types (VoidType, LabelType, FloatType and DoubleType) have hidden subclasses. They are hidden because they offer no useful functionality beyond what the Type class offers except to distinguish themselves from other subclasses of Type.

All other types are subclasses of DerivedType. Types can be named, but this is not a requirement. There exists exactly one instance of a given shape at any one time. This allows type equality to be performed with address equality of the Type Instance. That is, given two Type* values, the types are identical if the pointers are identical.

Important Public Methods

bool isIntegerTy() const: Returns true for any integer type.
bool isFloatingPointTy(): Return true if this is one of the five floating point types.
bool isSized(): Return true if the type has known size. Things that don't have a size are abstract types, labels and void.

Important Derived Types

IntegerType

Subclass of DerivedType that represents integer types of any bit width. Any bit width between IntegerType::MIN_INT_BITS (1) and IntegerType::MAX_INT_BITS (~8 million) can be represented.

static const IntegerType* get(unsigned NumBits): get an integer type of a specific bit width.
unsigned getBitWidth() const: Get the bit width of an integer type.

SequentialType

This is subclassed by ArrayType, PointerType and VectorType.

const Type * getElementType() const: Returns the type of each of the elements in the sequential type.

ArrayType

This is a subclass of SequentialType and defines the interface for array types.

unsigned getNumElements() const: Returns the number of elements in the array.

PointerType

Subclass of SequentialType for pointer types.

VectorType

Subclass of SequentialType for vector types. A vector type is similar to an ArrayType but is distinguished because it is a first class type whereas ArrayType is not. Vector types are used for vector operations and are usually small vectors of of an integer or floating point type.

StructType

Subclass of DerivedTypes for struct types.

FunctionType

Subclass of DerivedTypes for function types.

bool isVarArg() const: Returns true if it's a vararg function
const Type * getReturnType() const: Returns the return type of the function.
const Type * getParamType (unsigned i): Returns the type of the ith parameter.
const unsigned getNumParams() const: Returns the number of formal parameters.

The Module class

#include "llvm/Module.h"
doxygen info: Module Class

The Module class represents the top level structure present in LLVM programs. An LLVM module is effectively either a translation unit of the original program or a combination of several translation units merged by the linker. The Module class keeps track of a list of Functions, a list of GlobalVariables, and a SymbolTable. Additionally, it contains a few helpful member functions that try to make common operations easy.

Important Public Members of the Module class

Module::Module(std::string name = "")
Constructing a Module is easy. You can optionally provide a name for it (probably based on the name of the translation unit).
Module::iterator - Typedef for function list iterator
Module::const_iterator - Typedef for const_iterator.
begin(), end() size(), empty()
These are forwarding methods that make it easy to access the contents of a Module object's Function list.
Module::FunctionListType &getFunctionList()
Returns the list of Functions. This is necessary to use when you need to update the list or perform a complex action that doesn't have a forwarding method.
Module::global_iterator - Typedef for global variable list iterator
Module::const_global_iterator - Typedef for const_iterator.
global_begin(), global_end() global_size(), global_empty()
These are forwarding methods that make it easy to access the contents of a Module object's GlobalVariable list.
Module::GlobalListType &getGlobalList()
Returns the list of GlobalVariables. This is necessary to use when you need to update the list or perform a complex action that doesn't have a forwarding method.
SymbolTable *getSymbolTable()
Return a reference to the SymbolTable for this Module.
Function *getFunction(StringRef Name) const
Look up the specified function in the Module SymbolTable. If it does not exist, return null.
Function *getOrInsertFunction(const std::string &Name, const FunctionType *T)
Look up the specified function in the Module SymbolTable. If it does not exist, add an external declaration for the function and return it.
std::string getTypeName(const Type *Ty)
If there is at least one entry in the SymbolTable for the specified Type, return it. Otherwise return the empty string.
bool addTypeName(const std::string &Name, const Type *Ty)
Insert an entry in the SymbolTable mapping Name to Ty. If there is already an entry for this name, true is returned and the SymbolTable is not modified.

The Value class

#include "llvm/Value.h"
doxygen info: Value Class

The Value class is the most important class in the LLVM Source base. It represents a typed value that may be used (among other things) as an operand to an instruction. There are many different types of Values, such as Constants,Arguments. Even Instructions and Functions are Values.

A particular Value may be used many times in the LLVM representation for a program. For example, an incoming argument to a function (represented with an instance of the Argument class) is "used" by every instruction in the function that references the argument. To keep track of this relationship, the Value class keeps a list of all of the Users that is using it (the User class is a base class for all nodes in the LLVM graph that can refer to Values). This use list is how LLVM represents def-use information in the program, and is accessible through the use_* methods, shown below.

Because LLVM is a typed representation, every LLVM Value is typed, and this Type is available through the getType() method. In addition, all LLVM values can be named. The "name" of the Value is a symbolic string printed in the LLVM code:

%foo = add i32 1, 2

The name of this instruction is "foo". NOTE that the name of any value may be missing (an empty string), so names should ONLY be used for debugging (making the source code easier to read, debugging printouts), they should not be used to keep track of values or map between them. For this purpose, use a std::map of pointers to the Value itself instead.

One important aspect of LLVM is that there is no distinction between an SSA variable and the operation that produces it. Because of this, any reference to the value produced by an instruction (or the value available as an incoming argument, for example) is represented as a direct pointer to the instance of the class that represents this value. Although this may take some getting used to, it simplifies the representation and makes it easier to manipulate.

Important Public Members of the Value class

Value::use_iterator - Typedef for iterator over the use-list
Value::const_use_iterator - Typedef for const_iterator over the use-list
unsigned use_size() - Returns the number of users of the value.
bool use_empty() - Returns true if there are no users.
use_iterator use_begin() - Get an iterator to the start of the use-list.
use_iterator use_end() - Get an iterator to the end of the use-list.
User *use_back() - Returns the last element in the list.
These methods are the interface to access the def-use information in LLVM. As with all other iterators in LLVM, the naming conventions follow the conventions defined by the STL.

Type *getType() const
This method returns the Type of the Value.

bool hasName() const
std::string getName() const
void setName(const std::string &Name)
This family of methods is used to access and assign a name to a Value, be aware of the precaution above.

void replaceAllUsesWith(Value *V)
This method traverses the use list of a Value changing all Users of the current value to refer to "V" instead. For example, if you detect that an instruction always produces a constant value (for example through constant folding), you can replace all uses of the instruction with the constant like this:

Inst->replaceAllUsesWith(ConstVal);

The User class

#include "llvm/User.h"
doxygen info: User Class
Superclass: Value

The User class is the common base class of all LLVM nodes that may refer to Values. It exposes a list of "Operands" that are all of the Values that the User is referring to. The User class itself is a subclass of Value.

The operands of a User point directly to the LLVM Value that it refers to. Because LLVM uses Static Single Assignment (SSA) form, there can only be one definition referred to, allowing this direct connection. This connection provides the use-def information in LLVM.

Important Public Members of the User class

The User class exposes the operand list in two ways: through an index access interface and through an iterator based interface.

Value *getOperand(unsigned i)
unsigned getNumOperands()
These two methods expose the operands of the User in a convenient form for direct access.

User::op_iterator - Typedef for iterator over the operand list
op_iterator op_begin() - Get an iterator to the start of the operand list.
op_iterator op_end() - Get an iterator to the end of the operand list.
Together, these methods make up the iterator based interface to the operands of a User.

The Instruction class

#include "llvm/Instruction.h"
doxygen info: Instruction Class
Superclasses: User, Value

The Instruction class is the common base class for all LLVM instructions. It provides only a few methods, but is a very commonly used class. The primary data tracked by the Instruction class itself is the opcode (instruction type) and the parent BasicBlock the Instruction is embedded into. To represent a specific type of instruction, one of many subclasses of Instruction are used.

Because the Instruction class subclasses the User class, its operands can be accessed in the same way as for other Users (with the getOperand()/getNumOperands() and op_begin()/op_end() methods).

An important file for the Instruction class is the llvm/Instruction.def file. This file contains some meta-data about the various different types of instructions in LLVM. It describes the enum values that are used as opcodes (for example Instruction::Add and Instruction::ICmp), as well as the concrete sub-classes of Instruction that implement the instruction (for example BinaryOperator and CmpInst). Unfortunately, the use of macros in this file confuses doxygen, so these enum values don't show up correctly in the doxygen output.

Important Subclasses of the Instruction class

BinaryOperator
This subclasses represents all two operand instructions whose operands must be the same type, except for the comparison instructions.

CastInst
This subclass is the parent of the 12 casting instructions. It provides common operations on cast instructions.

CmpInst
This subclass respresents the two comparison instructions, ICmpInst (integer opreands), and FCmpInst (floating point operands).

TerminatorInst
This subclass is the parent of all terminator instructions (those which can terminate a block).

Important Public Members of the Instruction class

BasicBlock *getParent()
Returns the BasicBlock that this Instruction is embedded into.

bool mayWriteToMemory()
Returns true if the instruction writes to memory, i.e. it is a call,free,invoke, or store.

unsigned getOpcode()
Returns the opcode for the Instruction.

Instruction *clone() const
Returns another instance of the specified instruction, identical in all ways to the original except that the instruction has no parent (ie it's not embedded into a BasicBlock), and it has no name

The Constant class and subclasses

Constant represents a base class for different types of constants. It is subclassed by ConstantInt, ConstantArray, etc. for representing the various types of Constants. GlobalValue is also a subclass, which represents the address of a global variable or function.

Important Subclasses of Constant

ConstantInt : This subclass of Constant represents an integer constant of any width.
const APInt& getValue() const: Returns the underlying value of this constant, an APInt value.
int64_t getSExtValue() const: Converts the underlying APInt value to an int64_t via sign extension. If the value (not the bit width) of the APInt is too large to fit in an int64_t, an assertion will result. For this reason, use of this method is discouraged.
uint64_t getZExtValue() const: Converts the underlying APInt value to a uint64_t via zero extension. IF the value (not the bit width) of the APInt is too large to fit in a uint64_t, an assertion will result. For this reason, use of this method is discouraged.
static ConstantInt* get(const APInt& Val): Returns the ConstantInt object that represents the value provided by Val. The type is implied as the IntegerType that corresponds to the bit width of Val.
static ConstantInt* get(const Type *Ty, uint64_t Val): Returns the ConstantInt object that represents the value provided by Val for integer type Ty.
ConstantFP : This class represents a floating point constant.
double getValue() const: Returns the underlying value of this constant.
ConstantArray : This represents a constant array.
const std::vector<Use> &getValues() const: Returns a vector of component constants that makeup this array.
ConstantStruct : This represents a constant struct.
const std::vector<Use> &getValues() const: Returns a vector of component constants that makeup this array.
GlobalValue : This represents either a global variable or a function. In either case, the value is a constant fixed address (after linking).

The GlobalValue class

#include "llvm/GlobalValue.h"
doxygen info: GlobalValue Class
Superclasses: Constant, User, Value

Global values (GlobalVariables or Functions) are the only LLVM values that are visible in the bodies of all Functions. Because they are visible at global scope, they are also subject to linking with other globals defined in different translation units. To control the linking process, GlobalValues know their linkage rules. Specifically, GlobalValues know whether they have internal or external linkage, as defined by the LinkageTypes enumeration.

If a GlobalValue has internal linkage (equivalent to being static in C), it is not visible to code outside the current translation unit, and does not participate in linking. If it has external linkage, it is visible to external code, and does participate in linking. In addition to linkage information, GlobalValues keep track of which Module they are currently part of.

Because GlobalValues are memory objects, they are always referred to by their address. As such, the Type of a global is always a pointer to its contents. It is important to remember this when using the GetElementPtrInst instruction because this pointer must be dereferenced first. For example, if you have a GlobalVariable (a subclass of GlobalValue) that is an array of 24 ints, type [24 x i32], then the GlobalVariable is a pointer to that array. Although the address of the first element of this array and the value of the GlobalVariable are the same, they have different types. The GlobalVariable's type is [24 x i32]. The first element's type is i32. Because of this, accessing a global value requires you to dereference the pointer with GetElementPtrInst first, then its elements can be accessed. This is explained in the LLVM Language Reference Manual.

Important Public Members of the GlobalValue class

bool hasInternalLinkage() const
bool hasExternalLinkage() const
void setInternalLinkage(bool HasInternalLinkage)
These methods manipulate the linkage characteristics of the GlobalValue.

Module *getParent()
This returns the Module that the GlobalValue is currently embedded into.

The Function class

#include "llvm/Function.h"
doxygen info: Function Class
Superclasses: GlobalValue, Constant, User, Value

The Function class represents a single procedure in LLVM. It is actually one of the more complex classes in the LLVM hierarchy because it must keep track of a large amount of data. The Function class keeps track of a list of BasicBlocks, a list of formal Arguments, and a SymbolTable.

The list of BasicBlocks is the most commonly used part of Function objects. The list imposes an implicit ordering of the blocks in the function, which indicate how the code will be laid out by the backend. Additionally, the first BasicBlock is the implicit entry node for the Function. It is not legal in LLVM to explicitly branch to this initial block. There are no implicit exit nodes, and in fact there may be multiple exit nodes from a single Function. If the BasicBlock list is empty, this indicates that the Function is actually a function declaration: the actual body of the function hasn't been linked in yet.

In addition to a list of BasicBlocks, the Function class also keeps track of the list of formal Arguments that the function receives. This container manages the lifetime of the Argument nodes, just like the BasicBlock list does for the BasicBlocks.

The SymbolTable is a very rarely used LLVM feature that is only used when you have to look up a value by name. Aside from that, the SymbolTable is used internally to make sure that there are not conflicts between the names of Instructions, BasicBlocks, or Arguments in the function body.

Note that Function is a GlobalValue and therefore also a Constant. The value of the function is its address (after linking) which is guaranteed to be constant.

Important Public Members of the Function class

Function(const FunctionType *Ty, LinkageTypes Linkage, const std::string &N = "", Module* Parent = 0)
Constructor used when you need to create new Functions to add the program. The constructor must specify the type of the function to create and what type of linkage the function should have. The FunctionType argument specifies the formal arguments and return value for the function. The same FunctionType value can be used to create multiple functions. The Parent argument specifies the Module in which the function is defined. If this argument is provided, the function will automatically be inserted into that module's list of functions.

bool isDeclaration()
Return whether or not the Function has a body defined. If the function is "external", it does not have a body, and thus must be resolved by linking with a function defined in a different translation unit.

Function::iterator - Typedef for basic block list iterator
Function::const_iterator - Typedef for const_iterator.
begin(), end() size(), empty()
These are forwarding methods that make it easy to access the contents of a Function object's BasicBlock list.

Function::BasicBlockListType &getBasicBlockList()
Returns the list of BasicBlocks. This is necessary to use when you need to update the list or perform a complex action that doesn't have a forwarding method.

Function::arg_iterator - Typedef for the argument list iterator
Function::const_arg_iterator - Typedef for const_iterator.
arg_begin(), arg_end() arg_size(), arg_empty()
These are forwarding methods that make it easy to access the contents of a Function object's Argument list.

Function::ArgumentListType &getArgumentList()
Returns the list of Arguments. This is necessary to use when you need to update the list or perform a complex action that doesn't have a forwarding method.

BasicBlock &getEntryBlock()
Returns the entry BasicBlock for the function. Because the entry block for the function is always the first block, this returns the first block of the Function.

Type *getReturnType()
FunctionType *getFunctionType()
This traverses the Type of the Function and returns the return type of the function, or the FunctionType of the actual function.

SymbolTable *getSymbolTable()
Return a pointer to the SymbolTable for this Function.

The GlobalVariable class

#include "llvm/GlobalVariable.h"
doxygen info: GlobalVariable Class
Superclasses: GlobalValue, Constant, User, Value

Global variables are represented with the (surprise surprise) GlobalVariable class. Like functions, GlobalVariables are also subclasses of GlobalValue, and as such are always referenced by their address (global values must live in memory, so their "name" refers to their constant address). See GlobalValue for more on this. Global variables may have an initial value (which must be a Constant), and if they have an initializer, they may be marked as "constant" themselves (indicating that their contents never change at runtime).

Important Public Members of the GlobalVariable class

GlobalVariable(const Type *Ty, bool isConstant, LinkageTypes& Linkage, Constant *Initializer = 0, const std::string &Name = "", Module* Parent = 0)
Create a new global variable of the specified type. If isConstant is true then the global variable will be marked as unchanging for the program. The Linkage parameter specifies the type of linkage (internal, external, weak, linkonce, appending) for the variable. If the linkage is InternalLinkage, WeakAnyLinkage, WeakODRLinkage, LinkOnceAnyLinkage or LinkOnceODRLinkage, then the resultant global variable will have internal linkage. AppendingLinkage concatenates together all instances (in different translation units) of the variable into a single variable but is only applicable to arrays. See the LLVM Language Reference for further details on linkage types. Optionally an initializer, a name, and the module to put the variable into may be specified for the global variable as well.

bool isConstant() const
Returns true if this is a global variable that is known not to be modified at runtime.

bool hasInitializer()
Returns true if this GlobalVariable has an intializer.

Constant *getInitializer()
Returns the initial value for a GlobalVariable. It is not legal to call this method if there is no initializer.

The BasicBlock class

#include "llvm/BasicBlock.h"
doxygen info: BasicBlock Class
Superclass: Value

This class represents a single entry single exit section of the code, commonly known as a basic block by the compiler community. The BasicBlock class maintains a list of Instructions, which form the body of the block. Matching the language definition, the last element of this list of instructions is always a terminator instruction (a subclass of the TerminatorInst class).

In addition to tracking the list of instructions that make up the block, the BasicBlock class also keeps track of the Function that it is embedded into.

Note that BasicBlocks themselves are Values, because they are referenced by instructions like branches and can go in the switch tables. BasicBlocks have type label.

Important Public Members of the BasicBlock class

BasicBlock(const std::string &Name = "", Function *Parent = 0)
The BasicBlock constructor is used to create new basic blocks for insertion into a function. The constructor optionally takes a name for the new block, and a Function to insert it into. If the Parent parameter is specified, the new BasicBlock is automatically inserted at the end of the specified Function, if not specified, the BasicBlock must be manually inserted into the Function.

BasicBlock::iterator - Typedef for instruction list iterator
BasicBlock::const_iterator - Typedef for const_iterator.
begin(), end(), front(), back(), size(), empty() STL-style functions for accessing the instruction list.
These methods and typedefs are forwarding functions that have the same semantics as the standard library methods of the same names. These methods expose the underlying instruction list of a basic block in a way that is easy to manipulate. To get the full complement of container operations (including operations to update the list), you must use the getInstList() method.

BasicBlock::InstListType &getInstList()
This method is used to get access to the underlying container that actually holds the Instructions. This method must be used when there isn't a forwarding function in the BasicBlock class for the operation that you would like to perform. Because there are no forwarding functions for "updating" operations, you need to use this if you want to update the contents of a BasicBlock.

Function *getParent()
Returns a pointer to Function the block is embedded into, or a null pointer if it is homeless.

TerminatorInst *getTerminator()
Returns a pointer to the terminator instruction that appears at the end of the BasicBlock. If there is no terminator instruction, or if the last instruction in the block is not a terminator, then a null pointer is returned.

The Argument class

This subclass of Value defines the interface for incoming formal arguments to a function. A Function maintains a list of its formal arguments. An argument has a pointer to the parent Function.

Kito's LAB

前言

簡介

背景知識

The C++ Standard Template Library

其它有用的連結

重要跟有用的 LLVM API

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

isa<>

cast<>

dyn_cast<>

cast_or_null<>

dyn_cast_or_null<>

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

字串傳遞 (StringRef 及 Twine Class)

The StringRef class

Twine Class

DEBUG() macro 跟 -debug 選項

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

Statistic Class 及 -stats 選項

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

為你的程式挑個正確的資料結構

循序型容器 (std::vector, std::list, 等等)

llvm/ADT/ArrayRef.h

固定長度陣列

Heap 分配來的陣列

"llvm/ADT/TinyPtrVector.h"

"llvm/ADT/SmallVector.h"

<vector>

<deque>

<list>

llvm/ADT/ilist.h

llvm/ADT/PackedVector.h

ilist_traits

iplist

llvm/ADT/ilist_node.h

Sentinels（哨兵）

其它循序存取容器的選擇

字串類型的容器

llvm/ADT/StringRef.h

llvm/ADT/Twine.h

llvm/ADT/SmallString.h

std::string

集合類容器 (std::set, SmallSet, SetVector, 等等)

排序過的 'vector'

"llvm/ADT/SmallSet.h"

"llvm/ADT/SmallPtrSet.h"

"llvm/ADT/DenseSet.h"

"llvm/ADT/SparseSet.h"

"llvm/ADT/FoldingSet.h"

<set>

"llvm/ADT/SetVector.h"

"llvm/ADT/UniqueVector.h"

"llvm/ADT/ImmutableSet.h"

其它集合容器選項

Map 類型容器 (std::map, DenseMap, 等等)

排序過的 'vector'

"llvm/ADT/StringMap.h"

"llvm/ADT/IndexedMap.h"

"llvm/ADT/DenseMap.h"

"llvm/ADT/ValueMap.h"

"llvm/ADT/IntervalMap.h"

<map>

"llvm/ADT/MapVector.h"

"llvm/ADT/IntEqClasses.h"

"llvm/ADT/ImmutableMap.h"

Other Map-Like Container Options

Bit 儲存容器 (BitVector, SparseBitVector)

BitVector

SmallBitVector

SparseBitVector

常用操作的小提示集

基礎的走訪與檢查函數

走訪一個函數中的所有 BasicBlock

走訪一個 Basic Block 中的所有 Instructions

走訪一個函數中的所有 Instructions

把 Iterator 轉換程該類別的 Pointer

找出所有呼叫函數的地方：一個稍微複雜的例子

Treating calls and invokes the same way

Iterating over def-use & use-def chains