感謝 up 主 ZOMI 醬：https://space.bilibili.com/517221395
LLVM IR 與 GCC IR 對比#
| 特性 | LLVM IR | GCC IR (GIMPLE) |
|---|---|---|
| 獨立性和庫化架構 | 高度模組化，前端和後端分離，易於添加新語言和目標平台 | 傳統 GCC 架構，前端和後端耦合較緊密 |
| 表達形式 | 人類可讀的匯編形式、C++ 物件形式、序列化後的 bitcode 形式 | GIMPLE 表示形式，三地址碼，SSA 形式 |
| 設計和應用 | 更獨立，可在編譯器之外的工具中重用，有正式定義和良好的 C++ API，更接近硬體行為 | 降低控制流複雜度，優化相對容易 |
| 適用場景 | 適合學術界的應用，因為已經做了較大簡化，可以更快地得出結果 | 適合工業應用，可以自己生成統一的 AST 進行數據流分析，或生成類似 GIMPLE 的三地址碼進行分析 |
LLVM IR 的優點#
- 更獨立：LLVM IR 設計為可以在編譯器之外的任意工具中重用，使得可以輕鬆集成其他類型的工具，例如靜態分析器和插桿器。
- 更正式的定義和更好的 C++ API：這使得處理、轉換和分析變得更加容易。
- 更接近硬體行為：LLVM IR 提供了類似 RISCV 的模擬指令集和強類型系統，實現了其 “通用表示” 的目的。
GIMPLE 的優點#
- 降低控制流複雜度：GIMPLE 通過降低控制流複雜度、採用三地址表示和限制語法，使得優化變得相對容易。
LLVM 架構設計#
LLVM 架構圖：
LLVM 核心流程分析#
編譯器前端工作流程包括詞法、語法、語義分析；中間優化層大數據中的 Pass 優化；編譯器後端工作流程包括機器指令選擇、寄存器分配、指令調度。
實踐：Clang 編譯流程#
- 生成.i 文件
clang -E -c .\hello.c -o .\hello.i - 將預處理過後的.i 文件轉化為.bc 文件
clang -emit-llvm .\hello.i -c -o .\hello.bc clang -emit-llvm .\hello.c -S -o .\hello.ll - 使用 llc 和 lld 鏈接器
llc .\hello.ll -o .\hello.s llc .\hello.bc -o .\hello2.s - 轉變為可執行的二進制文件
clang .\hello.s -o hello - 查看編譯過程
clang -ccc-print-phases .\hello.c
總結#
LLVM 組件之間互動發生在高層次抽象，不同組件隔離為單獨程序庫，易於在整個編譯流水線中集成轉換和優化 Pass。現在被作為實現各種靜態和運行時編譯語言的通用基礎結構。
LLVM IR 詳解#
LLVM IR 設計理念#
LLVM IR 采用靜態單賦值形式（Static single assignment，SSA），具有兩個重要特徵：!
SSA 靜態單賦值#
LLVM IR 中，每個變量都在使用前都必須先定義，且每個變量只能被賦值一次。
以 1 * 2 + 3 為例：
LLVM IR 基本語法#
LLVM IR 是類似於精簡指令集（RISC）的底層虛擬指令集，支持簡單指令的線性序列。
- LLVM IR 是類似於精簡指令集（RISC）的底層虛擬指令集；
- 和真實精簡指令集一樣，支持簡單指令的線性序列，例如添加、相減、比較和分支；
- 指令都是三地址形式，它們接受一定數量的輸入然後在不同的寄存器中存儲計算結果；
- 與大多數精簡指令集不同，LLVM 使用強類型的簡單類型系統，並剝離了機器差異；
- LLVM IR 不使用固定的命名寄存器，它使用以 ％ 字符命名的臨時寄存器；
每個三地址碼指令，都可以被分解為一個四元組（4-tuple）的形式：（運算符，操作數 1，操作數 2，結果），由於每個陳述都包含了三個變量，即每條指令最多有三個操作數，所以它被稱為三地址碼。
| 指令類型 | 指令形式 | 四元組表示 |
|---|---|---|
| 賦值指令 | z = x op y (z = x + y) | (op, x, y, z) |
LLVM IR 內存模型#
LLVM IR 文件的基本單位稱為 module
一個 module 中可以擁有多個頂層實體，比如 function 和 global variavle
一個 function define 中至少有一個 basicblock
每個 basicblock 中有若干 instruction，並且都以 terminator instruction 結尾
| 類名 | 詳述 |
|---|---|
Module | **Module 類聚合了整個翻譯單元用到的所有數據，** 它是 LLVM 術語中的 “module” 的同義詞。它聲明了 Module::iterator typedef，作為遍歷這個模塊中的函數的簡便方法。你可以用 begin () 和 end () 方法獲取這些迭代器。 |
Function | Function 類包含有關函數定義和聲明的所有對象。對於聲明來說（用 isDeclaration () 檢查它是否為聲明），它僅包含函數原型。無論定義或者聲明，它都包含函數參數的列表，可通過 getArgumentList () 方法或者 arg_begin () 和 arg_end () 這對方法訪問它。你可以通過 Function::arg_iterator typedef 遍歷它們。如果 Function 對象代表函數定義，你可以通過這樣的語句遍歷它的內容：for (Function::iterator i = function.begin (), e = function.end (); i != e; ++i)，你將遍歷它的基本塊。 |
BasicBlock | BasicBlock 類封裝了 LLVM 指令序列，可通過 begin ()/end () 訪問它們。你可以利用 getTerminator () 方法直接訪問它的最後一條指令，你還可以用一些輔助函數遍歷 CFG，例如通過 getSinglePredecessor () 訪問前驅基本塊，當一個基本塊有單一前驅時。然而，如果它有多個前驅基本塊，就需要自己遍歷前驅列表，這也不難，你只要逐個遍歷基本塊，查看它們的終結指令的目標基本塊。 |
Instruction | Instruction 類表示 LLVM IR 的運算原子，一個單一的指令。利用一些方法可獲得高層級的斷言，例如 isAssociative ()，isCommutative ()，isIdempotent ()，和 isTerminator ()，但是它的精確的功能可通過 getOpcode () 獲知，它返回 llvm::Instruction 枚舉的一個成員，代表了 LLVM IR opcode。可通過 op_begin () 和 op_end () 這對方法訪問它的操作數，它從 User 超類繼承得到。 |
LLVM IR 內存模型最重要概念： Value, Use, User
LLVM IR 內存模型中，Value、Use 和 User 是三個核心概念，它們之間的關係定義了 LLVM 中的數據流和控制流。
| 概念 | 描述 |
|---|---|
Value | 在 LLVM 中，Value 是一個非常基礎的概念，它表示任何有值的實體，比如常數、變量、函數等。每個 Value 都有一個唯一的編號，用於在 LLVM 內部標識自己。Value 還可以有用戶（User），這意味著它可以是其他指令的操作數。 |
Use | Use 是 Value 的一個使用實例。在 LLVM 中，每個 Value 都有一個或多個 Use，表示這個 Value 被哪些指令所使用。Use 包含了指向使用該 Value 的 User 的指針，以及在該 User 中的操作數索引。 |
User | User 是指那些使用 Value 的指令或常量。例如，一條指令可能有多個操作數，每個操作數都是一個 Value，那麼這條指令就是一個 User。User 通過 Use 對象來引用它的操作數 Value。 |
這三個概念共同構成了 LLVM IR 的內存模型，它們之間的關係反映了指令之間的數據依賴關係。在 LLVM 的優化過程中，這些概念對於分析和管理指令之間的依賴非常重要。
LLVM 前端和優化層#
LLVM 前端#
編譯器前端將源代碼變換為編譯器的中間表示 LLVM IR。
- Lexical analysis 詞法分析
前端的第一個步驟處理源代碼的文本輸入，將語言結構分解為一組單詞和標記，去除註釋、空白、制表符等。每個單詞或者標記必須屬於語言子集，語言的保留字被變換為編譯器內部表示。
$ clang -cc1 -dump-tokens hello.c
- Syntactic analysis 語法分析
分組標記以形成表達式、語句、函數體等。檢查一組標記是否有意義，考慮代碼物理佈局，未分析代碼的意思，就像英語中的語法分析，不關心你說了什麼，只考慮句子是否正確，並輸出語法樹（AST）。
$ clang -fsyntax-only -Xclang -ast-dump hello.c
- Semantic analysis 語義分析
借助符號表檢驗代碼沒有違背語言類型系統。符號表存儲標識符和其各自的類型之間的映射，以及其它內容。類型檢查的一種直覺的方法是，在解析之後，遍歷 AST 的同時從符號表收集關於類型的信息。
$ clang -c hello.c
LLVM 優化層#
優化通常由分析 Pass 和轉換 Pass 組成。
優化通常由分析 Pass 和轉換 Pass 組成。
- 分析 Pass：負責發掘性質和優化機會；
- 轉換 Pass：生成必需的數據結構，後續為後者所用；
opt hello.bc -instcount -time-passes -domtree -o hello-tmp.bc -stats
LLVM 後端代碼生成#
後端架構#
後端由一套分析和轉換 Pass 組成，它們的任務是代碼生成。
Instruction Selection 指令選擇#
內存中 LLVM IR 變換為目標特定 SelectionDAG 節點。
Instruction Scheduling 指令調度#
第 1 次指令調度，也稱為前寄存器分配（RA）調度；
對指令排序，同時嘗試發現盡可能多的指令層次的並行；
然後指令被變換為 MachineInstr 三地址表示。
Register Allocation 寄存器分配#
寄存器分配將無限的虛擬寄存器引用轉換為有限的目標特定的寄存器集。
寄存器不夠時擠出（spill）到內存。
Instruction Scheduling 指令調度#
第 2 次指令調度，也稱為後寄存器分配（RA）調度；
此時可獲得真實的寄存器信息，某些類型寄存器存在延遲，它們可被用以改進指令順序。
Code Emission 代碼輸出#
代碼輸出階段將指令從 MachineInstr 表示變換為 MCInst 實例。