LLVM 目標獨立程式碼產生器

警告

這是一個正在進行中的工作。

簡介

LLVM 目標獨立程式碼產生器是一個框架，它提供了一套可重複使用的組件，用於將 LLVM 內部表示轉換為指定目標的機器碼——以組譯形式（適用於靜態編譯器）或二進制機器碼格式（適用於 JIT 編譯器）。LLVM 目標獨立程式碼產生器包含六個主要組件

  1. 抽象目標描述介面，用於捕獲有關機器各個方面的重要屬性，而與它們的使用方式無關。這些介面定義在 include/llvm/Target/ 中。

  2. 用於表示為目標產生的程式碼的類別。這些類別旨在具有足夠的抽象性，以表示任何目標機器的機器碼。這些類別定義在 include/llvm/CodeGen/ 中。在這個層級，像「常數池條目」和「跳躍表」這樣的概念被明確地公開。

  3. 用於表示物件檔案層級程式碼的類別和演算法，即 MC 層。這些類別表示組譯層級的結構，如標籤、區段和指令。在這個層級，「常數池條目」和「跳躍表」等概念不存在。

  4. 用於實作原生程式碼產生各個階段的目標獨立演算法（暫存器分配、排程、堆疊框架表示等）。此程式碼位於 lib/CodeGen/ 中。

  5. 特定目標的抽象目標描述介面的實作。這些機器描述利用 LLVM 提供的組件，並且可以選擇性地提供自訂的目標特定傳遞，以建構特定目標的完整程式碼產生器。目標描述位於 lib/Target/ 中。

  6. 目標獨立 JIT 組件。LLVM JIT 完全是目標獨立的（它使用 TargetJITInfo 結構來介面目標特定問題。目標獨立 JIT 的程式碼位於 lib/ExecutionEngine/JIT 中。

根據您感興趣處理的程式碼產生器的部分，這其中的不同部分對您會很有用。在任何情況下，您都應該熟悉目標描述和機器碼表示類別。如果您想為新目標新增後端，您將需要為您的新目標實作目標描述類別，並理解LLVM 程式碼表示。如果您有興趣實作新的程式碼產生演算法，它應該只依賴於目標描述和機器碼表示類別，以確保它是可移植的。

程式碼產生器中所需的組件

LLVM 程式碼產生器的兩個部分是程式碼產生器的高階介面，以及可用於建構目標特定後端的可重複使用組件集。兩個最重要的介面（ TargetMachine 和 DataLayout ）是後端要適應 LLVM 系統唯一需要定義的介面，但如果要使用可重複使用的程式碼產生器組件，則必須定義其他介面。

這種設計有兩個重要的含義。第一個是 LLVM 可以支援完全非傳統的程式碼產生目標。例如，C 後端不需要暫存器分配、指令選擇或系統提供的任何其他標準組件。因此，它只實作了這兩個介面，並做它自己的事情。請注意，C 後端已從 LLVM 3.1 版本的主幹中移除。另一個類似的程式碼產生器範例是（純粹假設的）後端，它將 LLVM 轉換為 GCC RTL 形式，並使用 GCC 為目標發射機器碼。

這種設計也意味著，在 LLVM 系統中設計和實作完全不同的程式碼產生器是可能的，這些程式碼產生器不使用任何內建組件。完全不建議這樣做，但對於與 LLVM 機器描述模型不符的完全不同的目標（例如 FPGA）可能需要這樣做。

程式碼產生器的高階設計

LLVM 目標獨立程式碼產生器旨在支援標準基於暫存器的微處理器的效率和高品質程式碼產生。此模型中的程式碼產生分為以下階段

  1. 指令選擇 — 此階段確定一種有效的方式，用目標指令集表示輸入的 LLVM 程式碼。此階段產生目標指令集中程式的初始程式碼，然後利用 SSA 形式的虛擬暫存器和實體暫存器，這些暫存器表示由於目標約束或呼叫慣例而需要的任何暫存器分配。此步驟將 LLVM 程式碼轉換為目標指令的 DAG。

  2. 排程和形成 — 此階段採用指令選擇階段產生的目標指令 DAG，確定指令的順序，然後以該順序發射指令作為 MachineInstrs 。請注意，我們在指令選擇章節中描述了這一點，因為它在 SelectionDAG 上運作。

  3. 基於 SSA 的機器碼最佳化 — 這個可選階段由一系列機器碼最佳化組成，這些最佳化在指令選擇器產生的 SSA 形式上運作。模數排程或窺孔最佳化等最佳化在這裡起作用。

  4. 暫存器分配 — 目標程式碼從 SSA 形式的無限虛擬暫存器檔案轉換為目標使用的具體暫存器檔案。此階段引入溢出程式碼並消除程式中所有虛擬暫存器參考。

  5. 序言/終結程式碼插入 — 一旦為函數產生了機器碼，並且已知所需的堆疊空間量（用於 LLVM alloca 和溢出槽），就可以插入函數的序言和終結程式碼，並消除「抽象堆疊位置參考」。此階段負責實作諸如框架指標消除和堆疊封裝之類的最佳化。

  6. 後期機器碼最佳化 — 在「最終」機器碼上運作的最佳化可以在這裡進行，例如溢出程式碼排程和窺孔最佳化。

  7. 程式碼發射 — 最後階段實際上輸出現前函數的程式碼，以目標組譯器格式或機器碼形式。

程式碼產生器基於這樣的假設：指令選擇器將使用最佳模式匹配選擇器來建立高品質的原生指令序列。基於模式擴展和積極迭代窺孔最佳化的替代程式碼產生器設計速度要慢得多。這種設計允許高效編譯（對於 JIT 環境很重要）和積極最佳化（在離線產生程式碼時使用），方法是允許使用不同複雜程度的組件來執行編譯的任何步驟。

除了這些階段之外，目標實作還可以將任意目標特定的傳遞插入到流程中。例如，X86 目標使用特殊的傳遞來處理 80x87 浮點堆疊架構。具有不尋常要求的其他目標可以使用自訂傳遞來支援，視需要而定。

使用 TableGen 進行目標描述

目標描述類別需要對目標架構進行詳細描述。這些目標描述通常具有大量共同資訊（例如，add 指令幾乎與 sub 指令相同）。為了允許最大程度地分解共同性，LLVM 程式碼產生器使用 TableGen 概觀 工具來描述目標機器的龐大區塊，這允許使用特定領域和目標特定的抽象來減少重複量。

隨著 LLVM 的持續開發和完善，我們計劃將越來越多的目標描述移到 .td 形式。這樣做給我們帶來了許多優勢。最重要的是，它使移植 LLVM 變得更容易，因為它減少了必須編寫的 C++ 程式碼量，以及在有人可以開始工作之前需要理解的程式碼產生器的表面區域。其次，它使更改事物變得更容易。特別是，如果表格和其他內容都由 tblgen 發射，我們只需要在一個地方進行更改（tblgen）即可將所有目標更新到新的介面。

目標描述類別

LLVM 目標描述類別（位於 include/llvm/Target 目錄中）提供了目標機器的抽象描述，獨立於任何特定客戶端。這些類別旨在捕獲目標的抽象屬性（例如，它具有的指令和暫存器），並且不包含任何特定的程式碼產生演算法片段。

所有目標描述類別（除了 DataLayout 類別）都設計為由具體的目標實作進行子類別化，並具有實作的虛擬方法。為了獲得這些實作， TargetMachine 類別提供了應該由目標實作的存取器。

TargetMachine 類別

TargetMachine 類別提供了虛擬方法，這些方法用於透過 get*Info 方法（getInstrInfo、getRegisterInfo、getFrameInfo 等）存取各種目標描述類別的目標特定實作。此類別設計為由具體的目標實作（例如，X86TargetMachine）進行專門化，後者實作各種虛擬方法。唯一需要的目標描述類別是 DataLayout 類別，但如果要使用程式碼產生器組件，則也應實作其他介面。

DataLayout 類別

DataLayout 類別是唯一需要的目標描述類別，並且是唯一不可擴展的類別（您不能從它派生新類別）。DataLayout 指定有關目標如何佈局結構記憶體、各種資料類型的對齊要求、目標中指標的大小以及目標是小端還是大端的信息。

TargetLowering 類別

TargetLowering 類別主要由基於 SelectionDAG 的指令選擇器使用，以描述應如何將 LLVM 程式碼降級為 SelectionDAG 操作。除其他外，此類別指示

  • 用於各種 ValueType 的初始暫存器類別，

  • 目標機器原生支援哪些操作，

  • setcc 操作的返回類型，

  • 用於移位量的類型，以及

  • 各種高階特性，例如將常數除法轉換為乘法序列是否有利可圖。

TargetRegisterInfo 類別

TargetRegisterInfo 類別用於描述目標的暫存器檔案以及暫存器之間的任何交互。

暫存器在程式碼產生器中以無符號整數表示。實體暫存器（目標描述中實際存在的暫存器）是唯一的小數字，而虛擬暫存器通常很大。請注意，暫存器 #0 保留為標誌值。

處理器描述中的每個暫存器都有一個關聯的 TargetRegisterDesc 條目，該條目提供暫存器的文字名稱（用於組譯輸出和偵錯轉儲）和一組別名（用於指示一個暫存器是否與另一個暫存器重疊）。

除了每個暫存器的描述外，TargetRegisterInfo 類別還公開了一組處理器特定的暫存器類別（TargetRegisterClass 類別的實例）。每個暫存器類別都包含具有相同屬性的暫存器集（例如，它們都是 32 位元整數暫存器）。指令選擇器建立的每個 SSA 虛擬暫存器都有一個關聯的暫存器類別。當暫存器分配器運行時，它會用集合中的實體暫存器替換虛擬暫存器。

這些類別的目標特定實作是從暫存器檔案的 TableGen 概觀 描述自動產生的。

TargetInstrInfo 類別

TargetInstrInfo 類別用於描述目標支援的機器指令。描述定義了諸如操作碼的助記符、運算元數量、隱含暫存器使用和定義的列表、指令是否具有某些目標獨立屬性（存取記憶體、是否可交換等），並保留任何目標特定的標誌。

TargetFrameLowering 類別

TargetFrameLowering 類別用於提供有關目標的堆疊框架佈局的信息。它保存堆疊增長的方向、每個函數入口處的已知堆疊對齊方式以及本地區域的偏移量。本地區域的偏移量是從函數入口處的堆疊指標到可以儲存函數資料（本機變數、溢出位置）的第一個位置的偏移量。

TargetSubtarget 類別

TargetSubtarget 類別用於提供有關所針對的特定晶片組的信息。子目標通知程式碼產生支援哪些指令、指令延遲和指令執行行程；即，使用哪些處理單元，以什麼順序使用，以及使用多長時間。

TargetJITInfo 類別

TargetJITInfo 類別公開了即時程式碼產生器使用的抽象介面，以執行目標特定的活動，例如發射存根。如果 TargetMachine 支援 JIT 程式碼產生，它應該透過 getJITInfo 方法提供其中一個物件。

機器碼描述類別

在高層級，LLVM 程式碼被轉換為由 組成的機器特定表示 MachineFunction , MachineBasicBlock 和 MachineInstr 實例（定義在 include/llvm/CodeGen 中）。這種表示完全是目標不可知的，以最抽象的形式表示指令：操作碼和一系列運算元。這種表示旨在支援機器碼的 SSA 表示以及暫存器分配的非 SSA 形式。

MachineInstr 類別

目標機器指令表示為 MachineInstr 類別的實例。此類別是一種非常抽象的機器指令表示方式。特別是，它僅追蹤操作碼編號和一組運算元。

操作碼編號是一個簡單的無符號整數，僅對特定後端有意義。目標的所有指令都應在目標的 *InstrInfo.td 檔案中定義。操作碼枚舉值是從此描述自動產生的。MachineInstr 類別沒有關於如何解釋指令（即，指令的語義是什麼）的任何信息；為此，您必須參考 TargetInstrInfo 類別。

機器指令的運算元可以是幾種不同的類型：暫存器參考、常數整數、基本區塊參考等。此外，機器運算元應標記為值的定義或使用（儘管只有暫存器允許作為定義）。

按照慣例，LLVM 程式碼產生器對指令運算元進行排序，以便所有暫存器定義都位於暫存器使用之前，即使在通常以其他順序列印的架構上也是如此。例如，SPARC add 指令：「add %i1, %i2, %i3」將「%i1」和「%i2」暫存器相加，並將結果儲存到「%i3」暫存器中。在 LLVM 程式碼產生器中，運算元應儲存為「%i3, %i1, %i2」：目的地在前。

將目的地（定義）運算元放在運算元列表的開頭有幾個優點。特別是，偵錯列印機會像這樣列印指令

%r3 = add %i1, %i2

此外，如果第一個運算元是定義，則更容易建立指令，其唯一定義是第一個運算元。

使用 MachineInstrBuilder.h 函數

機器指令是透過使用 BuildMI 函數建立的，該函數位於 include/llvm/CodeGen/MachineInstrBuilder.h 檔案中。BuildMI 函數使建立任意機器指令變得容易。BuildMI 函數的使用方式如下所示

// Create a 'DestReg = mov 42' (rendered in X86 assembly as 'mov DestReg, 42')
// instruction and insert it at the end of the given MachineBasicBlock.
const TargetInstrInfo &TII = ...
MachineBasicBlock &MBB = ...
DebugLoc DL;
MachineInstr *MI = BuildMI(MBB, DL, TII.get(X86::MOV32ri), DestReg).addImm(42);

// Create the same instr, but insert it before a specified iterator point.
MachineBasicBlock::iterator MBBI = ...
BuildMI(MBB, MBBI, DL, TII.get(X86::MOV32ri), DestReg).addImm(42);

// Create a 'cmp Reg, 0' instruction, no destination reg.
MI = BuildMI(MBB, DL, TII.get(X86::CMP32ri8)).addReg(Reg).addImm(42);

// Create an 'sahf' instruction which takes no operands and stores nothing.
MI = BuildMI(MBB, DL, TII.get(X86::SAHF));

// Create a self looping branch instruction.
BuildMI(MBB, DL, TII.get(X86::JNE)).addMBB(&MBB);

如果您需要新增定義運算元（除了可選的目的地暫存器之外），您必須明確地將其標記為這樣

MI.addReg(Reg, RegState::Define);

固定（預先分配）暫存器

程式碼產生器需要注意的一個重要問題是固定暫存器的存在。特別是，在指令流中通常存在一些位置，暫存器分配器必須安排將特定值放置在特定暫存器中。這可能是由於指令集的限制（例如，X86 只能使用 EAX/EDX 暫存器執行 32 位元除法），或呼叫慣例等外部因素。在任何情況下，指令選擇器都應發射程式碼，以便在需要時將虛擬暫存器複製到實體暫存器或從實體暫存器複製出來。

例如，考慮這個簡單的 LLVM 範例

define i32 @test(i32 %X, i32 %Y) {
  %Z = sdiv i32 %X, %Y
  ret i32 %Z
}

X86 指令選擇器可能會為 div 和 ret 產生此機器碼

;; Start of div
%EAX = mov %reg1024           ;; Copy X (in reg1024) into EAX
%reg1027 = sar %reg1024, 31
%EDX = mov %reg1027           ;; Sign extend X into EDX
idiv %reg1025                 ;; Divide by Y (in reg1025)
%reg1026 = mov %EAX           ;; Read the result (Z) out of EAX

;; Start of ret
%EAX = mov %reg1026           ;; 32-bit return value goes in EAX
ret

在程式碼產生結束時，暫存器分配器將合併暫存器並刪除產生的恆等移動，從而產生以下程式碼

;; X is in EAX, Y is in ECX
mov %EAX, %EDX
sar %EDX, 31
idiv %ECX
ret

這種方法非常通用（如果它可以處理 X86 架構，它可以處理任何架構！），並且允許將有關指令流的所有目標特定知識隔離在指令選擇器中。請注意，對於良好的程式碼產生，實體暫存器應具有較短的生命週期，並且假定所有實體暫存器在進入和退出基本區塊時都已失效（在暫存器分配之前）。因此，如果您需要一個值在基本區塊邊界之間保持有效，則它必須存在於虛擬暫存器中。

呼叫覆蓋暫存器

某些機器指令（如呼叫）會覆蓋大量實體暫存器。與為所有這些暫存器新增 <def,dead> 運算元不同，可以使用 MO_RegisterMask 運算元來代替。暫存器遮罩運算元保存保留暫存器的位元遮罩，而其他所有內容都被視為被指令覆蓋。

SSA 形式的機器碼

MachineInstr 最初以 SSA 形式選擇，並以 SSA 形式維護，直到發生暫存器分配。在大多數情況下，這非常簡單，因為 LLVM 已經是 SSA 形式；LLVM PHI 節點變為機器碼 PHI 節點，並且虛擬暫存器僅允許具有單個定義。

在暫存器分配之後，機器碼不再是 SSA 形式，因為程式碼中沒有剩餘虛擬暫存器。

MachineBasicBlock 類別

MachineBasicBlock 類別包含機器指令列表（ MachineInstr 實例）。它大致對應於輸入到指令選擇器的 LLVM 程式碼，但可能存在一對多的映射（即，一個 LLVM 基本區塊可以映射到多個機器基本區塊）。MachineBasicBlock 類別具有「getBasicBlock」方法，該方法返回它來自的 LLVM 基本區塊。

MachineFunction 類別

MachineFunction 類別包含機器基本區塊列表（ MachineBasicBlock 實例）。它與輸入到指令選擇器的 LLVM 函數一一對應。除了基本區塊列表之外，MachineFunction 還包含 MachineConstantPool、MachineFrameInfo、MachineFunctionInfo 和 MachineRegisterInfo。有關更多信息，請參閱 include/llvm/CodeGen/MachineFunction.h。

MachineInstr 捆綁包

LLVM 程式碼產生器可以將指令序列建模為 MachineInstr 捆綁包。MI 捆綁包可以建模 VLIW 組/包，其中包含任意數量的並行指令。它也可以用於建模一系列不能合法分離的順序指令列表（可能具有資料依賴性）（例如 ARM Thumb2 IT 區塊）。

從概念上講，MI 捆綁包是一個 MI，其中嵌套了許多其他 MI

--------------
|   Bundle   | ---------
--------------          \
       |           ----------------
       |           |      MI      |
       |           ----------------
       |                   |
       |           ----------------
       |           |      MI      |
       |           ----------------
       |                   |
       |           ----------------
       |           |      MI      |
       |           ----------------
       |
--------------
|   Bundle   | --------
--------------         \
       |           ----------------
       |           |      MI      |
       |           ----------------
       |                   |
       |           ----------------
       |           |      MI      |
       |           ----------------
       |                   |
       |                  ...
       |
--------------
|   Bundle   | --------
--------------         \
       |
      ...

MI 捆綁 (bundle) 支援不會改變 MachineBasicBlock 和 MachineInstr 的實體表示法。所有的 MI（包含頂層和巢狀的 MI）都儲存為 MI 的循序列表。「捆綁」的 MI 會標記 ‘InsideBundle’ 旗標。一個具有特殊 BUNDLE 運算碼的頂層 MI 被用來表示一個捆綁的開始。混合 BUNDLE MI 與非捆綁且不代表捆綁的個別 MI 是合法的。

MachineInstr 的 pass 應該將 MI 捆綁視為單一單元來操作。成員方法 (Member methods) 已經被教導正確地處理捆綁和捆綁內的 MI。MachineBasicBlock 的迭代器 (iterator) 已經被修改為跳過捆綁的 MI，以強制執行捆綁作為單一單元的概念。另一個迭代器 instr_iterator 已經被添加到 MachineBasicBlock，以允許 pass 迭代 MachineBasicBlock 中所有的 MI，包含那些巢狀在捆綁內的 MI。頂層 BUNDLE 指令必須具有正確的暫存器 MachineOperand 集合，以表示捆綁 MI 的累積輸入和輸出。

對於 VLIW 架構的 MachineInstr 的封裝 (Packing) / 捆綁 (bundling)，通常應該在暫存器分配 (register allocation) 的 super-pass 中完成。更具體地說，決定哪些 MI 應該捆綁在一起的 pass 應該在程式碼產生器 (code generator) 退出 SSA 形式 (form) 之後完成（亦即在 two-address pass、PHI elimination 和 copy coalescing 之後）。這類捆綁應該在虛擬暫存器 (virtual registers) 被重寫為實體暫存器 (physical registers) 之後最終完成（亦即，添加 BUNDLE MI 以及輸入和輸出暫存器 MachineOperands）。這消除了將虛擬暫存器運算元 (operands) 添加到 BUNDLE 指令的需求，否則會有效地使虛擬暫存器 def 和 use 列表加倍。捆綁可以使用虛擬暫存器並以 SSA 形式形成，但可能不適用於所有使用案例。

“MC” 層

MC 層用於在原始機器碼層級表示和處理程式碼，不包含「高階」資訊，例如「常數池 (constant pools)」、「跳躍表 (jump tables)」、「全域變數 (global variables)」或任何類似的東西。在這個層級，LLVM 處理諸如標籤名稱、機器指令和物件檔案 (object file) 中的區段 (sections) 等事物。此層中的程式碼用於許多重要的目的：程式碼產生器的尾端使用它來寫入 .s 或 .o 檔案，llvm-mc 工具也使用它來實作獨立的機器碼組譯器 (assemblers) 和反組譯器 (disassemblers)。

本節描述一些重要的類別 (classes)。在這個層級還有許多重要的子系統 (subsystems) 相互作用，這些子系統將在本手冊的後續章節中描述。

MCStreamer API

MCStreamer 最好被認為是一個組譯器 API。它是一個抽象的 API，以不同的方式實作（例如，輸出 .s 檔案、輸出 ELF .o 檔案等），但其 API 直接對應於您在 .s 檔案中看到的內容。MCStreamer 每個指令 (directive) 都有一個方法，例如 EmitLabel、EmitSymbolAttribute、switchSection、emitValue（用於 .byte、.word）等，這些方法直接對應於組合語言層級的指令。它也有一個 EmitInstruction 方法，用於將 MCInst 輸出到 streamer。

這個 API 對於兩個客戶端 (clients) 最重要：llvm-mc 獨立組譯器實際上是一個剖析器 (parser)，它剖析一行，然後調用 MCStreamer 上的一個方法。在程式碼產生器中，程式碼產生器的程式碼發射 (Code Emission)階段將更高階的 LLVM IR 和 Machine* 建構 (constructs) 降低到 MC 層級，並透過 MCStreamer 發射指令。

在 MCStreamer 的實作端，有兩個主要的實作：一個用於寫出 .s 檔案 (MCAsmStreamer)，另一個用於寫出 .o 檔案 (MCObjectStreamer)。MCAsmStreamer 是一個直接的實作，它為每個方法印出一個指令（例如 EmitValue -> .byte），但 MCObjectStreamer 實作了一個完整的組譯器。

對於目標特定的指令，MCStreamer 有一個 MCTargetStreamer 實例 (instance)。每個需要它的目標都定義了一個繼承自它的類別，並且很像 MCStreamer 本身：它每個指令都有一個方法，以及兩個繼承自它的類別，一個目標物件 streamer 和一個目標 asm streamer。目標 asm streamer 只是印出它（emitFnStart -> .fnstart），物件 streamer 實作了它的組譯器邏輯。

為了讓 llvm 使用這些類別，目標初始化 (initialization) 必須呼叫 TargetRegistry::RegisterAsmStreamer 和 TargetRegistry::RegisterMCObjectStreamer，傳遞回呼 (callbacks) 來分配相應的目標 streamer，並將其傳遞給 createAsmStreamer 或適當的物件 streamer 建構子 (constructor)。

MCContext 類別

MCContext 類別是 MC 層級中各種唯一化 (uniqued) 資料結構 (data structures) 的擁有者，包括符號 (symbols)、區段 (sections) 等。因此，這是您用來建立符號和區段的類別。這個類別不能被子類別化 (subclassed)。

MCSymbol 類別

MCSymbol 類別代表組譯檔案中的符號（又名標籤 (label)）。有兩種有趣的符號：組譯器暫時符號 (assembler temporary symbols) 和一般符號 (normal symbols)。組譯器暫時符號由組譯器使用和處理，但在產生物件檔案時會被丟棄。這種區別通常透過在標籤中添加前綴來表示，例如「L」標籤在 MachO 中是組譯器暫時標籤。

MCSymbols 由 MCContext 建立並在那裡唯一化。這表示可以比較 MCSymbols 的指標等效性 (pointer equivalence)，以找出它們是否是相同的符號。請注意，指標不等效性 (pointer inequality) 並不保證標籤最終會位於不同的位址。將如下內容輸出到 .s 檔案是完全合法的

foo:
bar:
  .byte 4

在這種情況下，foo 和 bar 符號都將具有相同的位址。

MCSection 類別

MCSection 類別代表一個物件檔案特定的區段。它被物件檔案特定的實作（例如 MCSectionMachO、MCSectionCOFF、MCSectionELF）子類別化，並且這些實作由 MCContext 建立和唯一化。MCStreamer 具有當前區段的概念，可以使用 SwitchToSection 方法更改當前區段（這對應於 .s 檔案中的「.section」指令）。

MCInst 類別

MCInst 類別是指令的目標獨立 (target-independent) 表示法。它是一個簡單的類別（比 MachineInstr 更簡單），它保存一個目標特定的運算碼 (opcode) 和一個 MCOperands 向量 (vector)。MCOperand 反過來是一個簡單的可辨識聯合 (discriminated union)，包含三種情況：1) 一個簡單的立即值 (immediate)，2) 一個目標暫存器 ID，3) 一個符號表示式 (symbolic expression)（例如「Lfoo-Lbar+42」）作為一個 MCExpr。

MCInst 是用於在 MC 層級表示機器指令的通用媒介 (common currency)。它是指令編碼器 (encoder)、指令印表機 (printer) 使用的類型，以及由組譯器剖析器和反組譯器產生的類型。

物件檔案格式

MC 層的物件寫入器 (writers) 支援各種物件格式。由於物件格式的目標特定方面，每個目標僅支援 MC 層支援的格式的子集。大多數目標都支援發射 (emitting) ELF 物件。其他供應商特定的物件通常僅在該供應商支援的目標上支援（亦即，MachO 僅在 Darwin 支援的目標上支援，而 XCOFF 僅在支援 AIX 的目標上支援）。此外，某些目標有自己的物件格式（亦即 DirectX、SPIR-V 和 WebAssembly）。

下表捕捉了 LLVM 中物件檔案支援的快照

表 104 物件檔案格式

格式

支援的目標

COFF

AArch64, ARM, X86

DXContainer

DirectX

ELF

AArch64, AMDGPU, ARM, AVR, BPF, CSKY, Hexagon, Lanai, LoongArch, M86k, MSP430, MIPS, PowerPC, RISCV, SPARC, SystemZ, VE, X86

GOFF

SystemZ

MachO

AArch64, ARM, X86

SPIR-V

SPIRV

WASM

WebAssembly

XCOFF

PowerPC

目標獨立的程式碼產生演算法

本節記錄了程式碼產生器的高階設計中描述的階段。它解釋了它們的工作原理以及其設計背後的一些基本原理 (rationale)。

指令選擇 (Instruction Selection)

指令選擇是將呈現給程式碼產生器的 LLVM 程式碼轉換為目標特定的機器指令的過程。文獻中有幾種眾所周知的方法可以做到這一點。LLVM 使用基於 SelectionDAG 的指令選擇器 (selector)。

DAG 指令選擇器的部分是從目標描述 (*.td) 檔案產生的。我們的目標是讓整個指令選擇器都從這些 .td 檔案產生，儘管目前仍然有一些東西需要自訂的 C++ 程式碼。

GlobalISel 是另一個指令選擇框架 (framework)。

SelectionDAG 簡介

SelectionDAG 為程式碼表示法提供了一個抽象層，使其適用於使用自動技術（例如，基於動態規劃的最佳模式匹配選擇器）進行指令選擇。它也非常適合程式碼產生的其他階段；特別是，指令排程 (instruction scheduling)（SelectionDAG 非常接近選擇後的排程 DAG）。此外，SelectionDAG 提供了一個主機表示法 (host representation)，可以在其中執行各種非常低階（但目標獨立）的最佳化；這些最佳化需要關於目標有效支援的指令的廣泛資訊。

SelectionDAG 是一個有向無環圖 (Directed-Acyclic-Graph)，其節點 (nodes) 是 SDNode 類別的實例 (instances)。SDNode 的主要酬載 (payload) 是其運算碼 (Opcode)，指示節點執行的運算以及運算的運算元 (operands)。各種運算節點類型在 include/llvm/CodeGen/ISDOpcodes.h 檔案的頂部描述。

儘管大多數運算定義單個值，但圖中的每個節點可以定義多個值。例如，組合的 div/rem 運算將定義被除數 (dividend) 和餘數 (remainder)。許多其他情況也需要多個值。每個節點也有一些數量的運算元，這些運算元是指向定義所用值的節點的邊 (edges)。由於節點可以定義多個值，因此邊由 SDValue 類別的實例表示，它是 <SDNode, unsigned> 對 (pair)，分別指示節點和正在使用的結果值。SDNode 產生的每個值都有一個相關聯的 MVT（機器值類型 (Machine Value Type)），指示值的類型。

SelectionDAG 包含兩種不同類型的值：表示資料流 (data flow) 的值和表示控制流 (control flow) 相依性 (dependencies) 的值。資料值是具有整數或浮點數值類型的簡單邊。控制邊表示為「鏈 (chain)」邊，其類型為 MVT::Other。這些邊在具有副作用 (side effects) 的節點（例如載入 (loads)、儲存 (stores)、呼叫 (calls)、返回 (returns) 等）之間提供排序 (ordering)。所有具有副作用的節點都應該將權杖鏈 (token chain) 作為輸入並產生一個新的權杖鏈作為輸出。按照慣例，權杖鏈輸入始終是運算元 #0，而鏈結果始終是運算產生的最後一個值。然而，在指令選擇之後，機器節點的鏈位於指令的運算元之後，並且後面可能跟著膠合 (glue) 節點。

SelectionDAG 具有指定的「Entry」和「Root」節點。Entry 節點始終是一個標記節點，其運算碼為 ISD::EntryToken。Root 節點是權杖鏈中最後一個具有副作用的節點。例如，在單個基本區塊 (basic block) 函數中，它將是返回節點。

SelectionDAG 的一個重要概念是「合法 (legal)」與「非法 (illegal)」DAG 的概念。目標的合法 DAG 是僅使用受支援的運算和受支援的類型的 DAG。例如，在 32 位元 PowerPC 上，具有 i1、i8、i16 或 i64 類型值的 DAG 將是非法的，使用 SREM 或 UREM 運算的 DAG 也將是非法的。合法化類型 (legalize types)和合法化運算 (legalize operations)階段負責將非法 DAG 轉換為合法 DAG。

SelectionDAG 指令選擇過程

基於 SelectionDAG 的指令選擇包含以下步驟

  1. 建立初始 DAG (Build initial DAG) — 此階段執行從輸入 LLVM 程式碼到非法 SelectionDAG 的簡單轉換。

  2. 最佳化 SelectionDAG (Optimize SelectionDAG) — 此階段對 SelectionDAG 執行簡單的最佳化以簡化它，並識別中繼指令 (meta instructions)（例如旋轉 (rotates) 和 div/rem 對）以用於支援這些中繼運算的目標。這使得產生的程式碼更有效率，並使從 DAG 選擇指令 (select instructions from DAG)階段（如下）更簡單。

  3. 合法化 SelectionDAG 類型 (Legalize SelectionDAG Types) — 此階段轉換 SelectionDAG 節點以消除目標上任何不受支援的類型。

  4. 最佳化 SelectionDAG (Optimize SelectionDAG) — 執行 SelectionDAG 最佳化器以清理類型合法化所暴露的冗餘 (redundancies)。

  5. 合法化 SelectionDAG 運算 (Legalize SelectionDAG Ops) — 此階段轉換 SelectionDAG 節點以消除目標上任何不受支援的運算。

  6. 最佳化 SelectionDAG (Optimize SelectionDAG) — 執行 SelectionDAG 最佳化器以消除運算合法化引入的低效率。

  7. 從 DAG 選擇指令 (Select instructions from DAG) — 最後，目標指令選擇器將 DAG 運算與目標指令匹配。此過程將目標獨立的輸入 DAG 轉換為另一個目標指令的 DAG。

  8. SelectionDAG 排程和形成 (SelectionDAG Scheduling and Formation) — 最後一個階段將目標指令 DAG 中的指令分配線性順序，並將它們發射到正在編譯的 MachineFunction 中。此步驟使用傳統的預先 pass 排程技術。

完成所有這些步驟後，SelectionDAG 將被銷毀，其餘的程式碼產生 pass 將被執行。

除錯這些步驟最常見的方法之一是使用 -debug-only=isel，它會在每個步驟之後印出 DAG 以及其他資訊，例如除錯資訊 (debug info)。或者，-debug-only=isel-dump 僅顯示 DAG 傾印 (dumps)，但可以使用 -filter-print-funcs=<function names> 按函數名稱過濾結果。

視覺化此處正在發生的事情的一個好方法是利用一些 LLC 命令列選項。以下選項會彈出一個視窗，在特定時間顯示 SelectionDAG（如果您在使用此選項時只在主控台 (console) 中印出錯誤，您可能需要配置您的系統以添加對它的支援）。

  • -view-dag-combine1-dags 顯示在建立 DAG 之後，在第一個最佳化 pass 之前的 DAG。

  • -view-legalize-dags 顯示合法化 (Legalization) 之前的 DAG。

  • -view-dag-combine2-dags 顯示在第二個最佳化 pass 之前的 DAG。

  • -view-isel-dags 顯示在選擇 (Select) 階段之前的 DAG。

  • -view-sched-dags 顯示在排程 (Scheduling) 之前的 DAG。

-view-sunit-dags 顯示排程器的相依性圖 (dependency graph)。此圖基於最終的 SelectionDAG，其中必須一起排程的節點被捆綁到單個排程單元節點中，並且省略了立即運算元和其他與排程無關的節點。

選項 -filter-view-dags 允許選擇您有興趣視覺化的基本區塊的名稱，並過濾所有先前的 view-*-dags 選項。

初始 SelectionDAG 建構 (Initial SelectionDAG Construction)

初始 SelectionDAG 由 SelectionDAGBuilder 類別從 LLVM 輸入天真地 (naïvely) 以窺孔最佳化 (peephole expanded) 的方式展開。此 pass 的目的是盡可能多地向 SelectionDAG 公開低階的、目標特定的細節。此 pass 主要是硬式編碼 (hard-coded) 的（例如，LLVM add 變成 SDNode add，而 getelementptr 則展開為顯而易見的算術）。此 pass 需要目標特定的掛鉤 (hooks) 來降低呼叫、返回、varargs 等。對於這些功能， TargetLowering 介面 (interface) 被使用。

SelectionDAG LegalizeTypes 階段

合法化 (Legalize) 階段負責將 DAG 轉換為僅使用目標原生支援的類型。

將不受支援的純量類型 (scalar types) 的值轉換為受支援的類型的值主要有兩種方式：將小類型轉換為較大類型（「提升 (promoting)」）以及將大型整數類型分解為較小類型（「擴展 (expanding)」）。例如，目標可能要求將所有 f32 值提升為 f64，並將所有 i1/i8/i16 值提升為 i32。相同的目標可能要求將所有 i64 值擴展為 i32 值對。這些更改可以根據需要插入符號和零擴展，以確保最終程式碼與輸入具有相同的行為。

將不受支援的向量類型 (vector types) 的值轉換為受支援的類型的值主要有兩種方式：拆分向量類型，必要時多次拆分，直到找到合法類型，以及透過在末尾添加元素來擴展向量類型，使其四捨五入到合法類型（「加寬 (widening)」）。如果向量一直拆分到單元素部分，但沒有找到受支援的向量類型，則元素將轉換為純量（「純量化 (scalarizing)」）。

目標實作 (implementation) 透過在其 TargetLowering 建構子中呼叫 addRegisterClass 方法來告知合法化器 (legalizer) 哪些類型受支援（以及要為它們使用哪個暫存器類別 (register class)）。

SelectionDAG 合法化階段

合法化 (Legalize) 階段負責將 DAG 轉換為僅使用目標原生支援的運算。

目標通常具有奇怪的約束 (constraints)，例如並非在每個受支援的資料類型 (datatype) 上都支援每個運算（例如，X86 不支援位元組條件移動 (byte conditional moves)，而 PowerPC 不支援從 16 位元記憶體位置進行符號擴展載入）。合法化透過開放編碼 (open-coding) 另一個運算序列來模擬運算（「擴展 (expansion)」），透過將一種類型提升為支援運算的較大類型（「提升 (promotion)」），或透過使用目標特定的掛鉤來實作合法化（「自訂 (custom)」）來處理這個問題。

目標實作透過在其 TargetLowering 建構子中呼叫 setOperationAction 方法來告知合法化器哪些運算不受支援（以及要採取上述三種操作中的哪一種）。

如果目標具有合法的向量類型，則預期它會為使用這些類型的 shufflevector IR 指令的常見形式產生有效的機器碼。這可能需要針對從 shufflevector IR 建立的 SelectionDAG 向量運算進行自訂合法化。應該處理的 shufflevector 形式包括

  • 向量選擇 (Vector select) — 向量的每個元素都是從 2 個輸入向量的對應元素中選擇的。此運算也可能在目標組合語言中稱為「混合 (blend)」或「位元選擇 (bitwise select)」。這種类型的 shuffle 直接映射到 shuffle_vector SelectionDAG 節點。

  • 插入子向量 (Insert subvector) — 向量被放置到從索引 0 開始的較長向量類型中。這種类型的 shuffle 直接映射到 insert_subvector SelectionDAG 節點，其中 index 運算元設定為 0。

  • 提取子向量 (Extract subvector) — 向量從索引 0 開始從較長的向量類型中拉出。這種类型的 shuffle 直接映射到 extract_subvector SelectionDAG 節點，其中 index 運算元設定為 0。

  • Splat — 向量的所有元素都具有相同的純量元素。此運算也可能在目標組合語言中稱為「廣播 (broadcast)」或「複製 (duplicate)」。shufflevector IR 指令可能會更改向量長度，因此此運算可能會映射到多個 SelectionDAG 節點，包括 shuffle_vector、concat_vectors、insert_subvector 和 extract_subvector。

在合法化 (Legalize) pass 存在之前，我們要求每個目標選擇器 (selector)都支援和處理每個運算子 (operator) 和類型，即使它們不是原生支援的。合法化階段的引入允許在目標之間共享所有的規範化 (canonicalization) 模式，並且由於規範化的程式碼仍然以 DAG 的形式存在，因此可以非常容易地最佳化規範化的程式碼。

SelectionDAG 最佳化階段：DAG Combiner

SelectionDAG 最佳化階段在程式碼產生過程中執行多次，在建立 DAG 後立即執行一次，在每次合法化後執行一次。pass 的第一次執行允許清理初始程式碼（例如，執行依賴於知道運算子具有受限類型輸入的最佳化）。pass 的後續執行清理由合法化 pass 產生的混亂程式碼，這使得合法化可以非常簡單（它可以專注於使程式碼合法，而不是專注於產生良好且合法的程式碼）。

執行的一個重要最佳化類別是最佳化插入的符號和零擴展指令。我們目前使用特設 (ad-hoc) 技術，但未來可能會轉向更嚴格的技術。以下是一些關於這個主題的好論文

“Widening integer arithmetic”
Kevin Redwine 和 Norman Ramsey
International Conference on Compiler Construction (CC) 2004

“Effective sign extension elimination”
Motohiro Kawahito, Hideaki Komatsu 和 Toshio Nakatani
Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation.

SelectionDAG 選擇階段

選擇階段是指令選擇的目標特定程式碼的主要部分。此階段以合法的 SelectionDAG 作為輸入，將目標支援的指令與此 DAG 進行模式匹配，並產生一個新的目標程式碼 DAG。例如，考慮以下 LLVM 片段

%t1 = fadd float %W, %X
%t2 = fmul float %t1, %Y
%t3 = fadd float %t2, %Z

此 LLVM 程式碼對應於一個 SelectionDAG，其基本外觀如下

(fadd:f32 (fmul:f32 (fadd:f32 W, X), Y), Z)

如果目標支援浮點乘法-加法 (multiply-and-add) (FMA) 運算，則其中一個加法可以與乘法合併。例如，在 PowerPC 上，指令選擇器的輸出可能看起來像這個 DAG

(FMADDS (FADDS W, X), Y, Z)

FMADDS 指令是一個三元指令 (ternary instruction)，它將其前兩個運算元相乘並加上第三個運算元（作為單精度浮點數）。FADDS 指令是一個簡單的二元單精度加法指令。為了執行這種模式匹配，PowerPC 後端 (backend) 包含以下指令定義

def FMADDS : AForm_1<59, 29,
                    (ops F4RC:$FRT, F4RC:$FRA, F4RC:$FRC, F4RC:$FRB),
                    "fmadds $FRT, $FRA, $FRC, $FRB",
                    [(set F4RC:$FRT, (fadd (fmul F4RC:$FRA, F4RC:$FRC),
                                           F4RC:$FRB))]>;
def FADDS : AForm_2<59, 21,
                    (ops F4RC:$FRT, F4RC:$FRA, F4RC:$FRB),
                    "fadds $FRT, $FRA, $FRB",
                    [(set F4RC:$FRT, (fadd F4RC:$FRA, F4RC:$FRB))]>;

指令定義的突出顯示部分指示用於匹配指令的模式。DAG 運算子（例如 fmul/fadd）在 include/llvm/Target/TargetSelectionDAG.td 檔案中定義。「F4RC」是輸入和結果值的暫存器類別。

TableGen DAG 指令選擇器產生器讀取 .td 檔案中的指令模式，並自動為您的目標建立模式匹配程式碼的部分。它具有以下優勢

  • 在編譯器編譯時 (compiler-compile time)，它會分析您的指令模式，並告訴您您的模式是否有意義。

  • 它可以處理模式匹配的運算元的任意約束。特別是，直接說出「匹配任何作為 13 位元符號擴展值的立即值」之類的話。有關範例，請參閱 PowerPC 後端中的 immSExt16 和相關的 tblgen 類別。

  • 它知道已定義模式的幾個重要恆等式 (identities)。例如，它知道加法是可交換的，因此它允許上面的 FMADDS 模式匹配「(fadd X, (fmul Y, Z))」以及「(fadd (fmul X, Y), Z)」，而無需目標作者 (author) 專門處理這種情況。

  • 它具有全功能的類型推斷 (type-inferencing) 系統。特別是，您應該很少需要明確地告訴系統您的模式的哪些部分是什麼類型。在上面的 FMADDS 案例中，我們不必告訴 tblgen 模式中的所有節點都是 ‘f32’ 類型。它能夠從 F4RC 具有 ‘f32’ 類型的事實中推斷和傳播這種知識。

  • 目標可以定義自己的（並依賴內建的）「模式片段 (pattern fragments)」。模式片段是在編譯器編譯期間內聯到您的模式中的可重複使用模式的區塊 (chunks)。例如，整數「(not x)」運算實際上被定義為一個模式片段，它展開為「(xor x, -1)」，因為 SelectionDAG 沒有原生的 ‘not’ 運算。目標可以根據自己的需要定義自己的簡寫片段。請參閱 ‘not’ 和 ‘ineg’ 的定義以獲取範例。

  • 除了指令之外，目標還可以指定任意模式，這些模式使用 ‘Pat’ 類別對應到一或多個指令。例如，PowerPC 沒有辦法用單一指令將任意整數立即值載入暫存器。為了告訴 tblgen 如何做到這一點，它定義了：

    // Arbitrary immediate support.  Implement in terms of LIS/ORI.
def : Pat<(i32 imm:$imm),
          (ORI (LIS (HI16 imm:$imm)), (LO16 imm:$imm))>;

    如果沒有任何單一指令模式符合將立即值載入暫存器的需求，則會使用此模式。此規則表示「匹配任意 i32 立即值，並將其轉換為 ORI（「或 16 位元立即值」）和 LIS（「載入 16 位元立即值，其中立即值向左位移 16 位元」）指令」。為了使此方法有效，LO16/HI16 節點轉換用於操作輸入的立即值（在本例中，取得立即值的高位或低位 16 位元）。

  • 當使用 ‘Pat’ 類別將模式對應到具有一或多個複雜運算元（例如 X86 定址模式）的指令時，該模式可以完整地使用 ComplexPattern 指定運算元，或者它可以分別指定複雜運算元的組件。後者是透過 PowerPC 後端針對前置遞增指令完成的

    def STWU  : DForm_1<37, (outs ptr_rc:$ea_res), (ins GPRC:$rS, memri:$dst),
                "stwu $rS, $dst", LdStStoreUpd, []>,
                RegConstraint<"$dst.reg = $ea_res">, NoEncode<"$ea_res">;

def : Pat<(pre_store GPRC:$rS, ptr_rc:$ptrreg, iaddroff:$ptroff),
          (STWU GPRC:$rS, iaddroff:$ptroff, ptr_rc:$ptrreg)>;

    在此，ptroff 和 ptrreg 運算元組配對到 STWU 指令中類別為 memri 的複雜運算元 dst 上。

  • 雖然系統自動化了很多流程，但如果有些難以表達的特殊情況，它仍然允許您編寫自訂 C++ 程式碼來匹配。

雖然此系統有很多優點，但目前仍有一些限制，主要是因為它仍在開發中，尚未完成

  • 總體而言，沒有辦法定義或匹配定義多個值的 SelectionDAG 節點（例如 SMUL_LOHI、LOAD、CALL 等）。這是目前您仍然必須為您的指令選擇器編寫自訂 C++ 程式碼的最大原因。

  • 目前還沒有很好的方法來支援匹配複雜的定址模式。在未來，我們將擴展模式片段，使其能夠定義多個值（例如 X86 定址模式的四個運算元，目前使用自訂 C++ 程式碼進行匹配）。此外，我們將擴展片段，以便一個片段可以匹配多個不同的模式。

  • 我們不會自動推斷諸如 isStore/isLoad 之類的標誌。

  • 我們還沒有自動產生 Legalizer 支援的暫存器和運算集合。

  • 我們還沒有方法將自訂合法化節點連結進來。

儘管存在這些限制，指令選擇器產生器對於典型指令集中的大多數二元和邏輯運算仍然非常有用。如果您遇到任何問題或無法弄清楚如何做某事，請告知 Chris！

SelectionDAG 排程和形成階段

排程階段會取得來自選擇階段的目標指令 DAG，並指派一個順序。排程器可以根據機器的各種約束條件選擇順序（即，最小化暫存器壓力的順序或嘗試涵蓋指令延遲）。一旦建立順序，DAG 就會轉換為 的列表 MachineInstrs 並銷毀 SelectionDAG。

請注意，此階段在邏輯上與指令選擇階段是分開的，但在程式碼中與之緊密相關，因為它在 SelectionDAG 上運作。

SelectionDAG 的未來方向

  1. 可選的 function-at-a-time 選擇。

  2. 從 .td 檔案自動產生整個選擇器。

基於 SSA 的機器碼最佳化

待撰寫

活躍區間

活躍區間是變數活躍的範圍（區間）。它們被一些 暫存器分配器 傳遞使用，以判斷兩個或多個需要相同實體暫存器的虛擬暫存器是否在程式中的同一點活躍（即，它們衝突）。當發生這種情況時，必須溢出一個虛擬暫存器。

活躍變數分析

確定變數活躍區間的第一步是計算指令後立即失效的暫存器集合（即，指令計算了值，但從未使用過），以及指令使用但之後從未使用過的暫存器集合（即，它們被殺死）。為函數中的每個虛擬暫存器和可分配暫存器的實體暫存器計算活躍變數資訊。這是以非常有效的方式完成的，因為它使用 SSA 來稀疏地計算虛擬暫存器（採用 SSA 形式）的生命週期資訊，並且僅需追蹤區塊內的實體暫存器。在暫存器分配之前，LLVM 可以假設實體暫存器僅在單一基本區塊內活躍。這使其能夠執行單一的局部分析，以解析每個基本區塊內的實體暫存器生命週期。如果實體暫存器不可分配暫存器（例如，堆疊指標或條件碼），則不會追蹤它。

實體暫存器可能在函數中或函數外活躍。活躍輸入值通常是暫存器中的引數。活躍輸出值通常是暫存器中的傳回值。活躍輸入值被標記為這樣，並在活躍區間分析期間被賦予一個虛擬的「定義」指令。如果函數的最後一個基本區塊是 return，則它會被標記為使用函數中的所有活躍輸出值。

PHI 節點需要特殊處理，因為從函數 CFG 的深度優先遍歷計算活躍變數資訊無法保證 PHI 節點使用的虛擬暫存器在其使用前已定義。當遇到 PHI 節點時，僅處理定義，因為使用將在其他基本區塊中處理。

對於當前基本區塊的每個 PHI 節點，我們在當前基本區塊的末尾模擬一個賦值，並遍歷後繼基本區塊。如果後繼基本區塊有一個 PHI 節點，並且 PHI 節點的其中一個運算元來自當前基本區塊，則該變數會被標記為在當前基本區塊及其所有前導基本區塊中活躍，直到遇到具有定義指令的基本區塊。

活躍區間分析

我們現在擁有可用的資訊來執行活躍區間分析並建立活躍區間本身。我們首先對基本區塊和機器指令進行編號。然後我們處理「活躍輸入」值。這些值在實體暫存器中，因此假設實體暫存器在基本區塊結束時被殺死。虛擬暫存器的活躍區間是針對機器指令的某些排序 [1, N] 計算的。活躍區間是一個區間 [i, j)，其中 1 >= i >= j > N，變數在此區間內活躍。

注意

更多內容待續…

暫存器分配

暫存器分配問題包括將可以使用無限數量虛擬暫存器的程式 Pv 映射到包含有限（可能很小）數量的實體暫存器的程式 Pp。每個目標架構都有不同數量的實體暫存器。如果實體暫存器的數量不足以容納所有虛擬暫存器，則其中一些必須映射到記憶體中。這些虛擬暫存器稱為溢出的虛擬暫存器。

暫存器在 LLVM 中的表示方式

在 LLVM 中，實體暫存器用整數數字表示，通常範圍從 1 到 1023。若要查看特定架構如何定義此編號，您可以閱讀該架構的 GenRegisterNames.inc 檔案。例如，透過檢查 lib/Target/X86/X86GenRegisterInfo.inc，我們看到 32 位元暫存器 EAX 由 43 表示，而 MMX 暫存器 MM0 映射到 65。

某些架構包含共用相同實體位置的暫存器。一個著名的例子是 X86 平台。例如，在 X86 架構中，暫存器 EAX、AX 和 AL 共用前八個位元。這些實體暫存器在 LLVM 中被標記為別名。給定一個特定的架構，您可以透過檢查其 RegisterInfo.td 檔案來檢查哪些暫存器是別名。此外，MCRegAliasIterator 類別會列舉別名到暫存器的所有實體暫存器。

實體暫存器在 LLVM 中被分組到暫存器類別中。相同暫存器類別中的元素在功能上是等效的，並且可以互換使用。每個虛擬暫存器只能映射到特定類別的實體暫存器。例如，在 X86 架構中，某些虛擬暫存器只能分配給 8 位元暫存器。暫存器類別由 TargetRegisterClass 物件描述。若要發現虛擬暫存器是否與給定的實體暫存器相容，可以使用以下程式碼：

bool RegMapping_Fer::compatible_class(MachineFunction &mf,
                                      unsigned v_reg,
                                      unsigned p_reg) {
  assert(TargetRegisterInfo::isPhysicalRegister(p_reg) &&
         "Target register must be physical");
  const TargetRegisterClass *trc = mf.getRegInfo().getRegClass(v_reg);
  return trc->contains(p_reg);
}

有時，主要為了偵錯目的，更改目標架構中可用的實體暫存器數量很有用。這必須靜態地在 TargetRegisterInfo.td 檔案中完成。只需 grep RegisterClass，其最後一個參數是暫存器列表。註解掉一些暫存器是避免使用它們的一種簡單方法。更禮貌的方法是從分配順序中明確排除某些暫存器。請參閱 lib/Target/X86/X86RegisterInfo.td 中 GR8 暫存器類別的定義，以取得範例。

虛擬暫存器也用整數數字表示。與實體暫存器相反，不同的虛擬暫存器永遠不會共用相同的數字。實體暫存器在 TargetRegisterInfo.td 檔案中靜態定義，並且不能由應用程式開發人員建立，但虛擬暫存器並非如此。為了建立新的虛擬暫存器，請使用 MachineRegisterInfo::createVirtualRegister() 方法。此方法將傳回一個新的虛擬暫存器。使用 IndexedMap<Foo, VirtReg2IndexFunctor> 來保存每個虛擬暫存器的資訊。如果您需要列舉所有虛擬暫存器，請使用 TargetRegisterInfo::index2VirtReg() 函數來尋找虛擬暫存器編號

for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
  unsigned VirtReg = TargetRegisterInfo::index2VirtReg(i);
  stuff(VirtReg);
}

在暫存器分配之前，指令的運算元主要為虛擬暫存器，儘管也可以使用實體暫存器。為了檢查給定的機器運算元是否為暫存器，請使用布林函數 MachineOperand::isRegister()。若要取得暫存器的整數代碼，請使用 MachineOperand::getReg()。指令可以定義或使用暫存器。例如，ADD reg:1026 := reg:1025 reg:1024 定義暫存器 1024，並使用暫存器 1025 和 1026。給定暫存器運算元，MachineOperand::isUse() 方法會告知該暫存器是否被指令使用。MachineOperand::isDef() 方法會告知該暫存器是否被定義。

我們將在暫存器分配之前存在於 LLVM 位元碼中的實體暫存器稱為預先著色的暫存器。預先著色的暫存器用於許多不同的情況，例如，傳遞函數呼叫的參數，以及儲存特定指令的結果。預先著色的暫存器有兩種型別：隱式定義的和顯式定義的。顯式定義的暫存器是正常運算元，可以使用 MachineInstr::getOperand(int)::getReg() 存取。為了檢查哪些暫存器被指令隱式定義，請使用 TargetInstrInfo::get(opcode)::ImplicitDefs，其中 opcode 是目標指令的運算碼。顯式和隱式實體暫存器之間的一個重要區別是，後者對於每個指令都是靜態定義的，而前者可能會根據正在編譯的程式而變化。例如，表示函數呼叫的指令將始終隱式定義或使用同一組實體暫存器。若要讀取指令隱式使用的暫存器，請使用 TargetInstrInfo::get(opcode)::ImplicitUses。預先著色的暫存器對任何暫存器分配演算法都施加了約束。暫存器分配器必須確保它們都不會被活躍的虛擬暫存器的值覆蓋。

將虛擬暫存器映射到實體暫存器

有兩種方法可以將虛擬暫存器映射到實體暫存器（或記憶體插槽）。第一種方法，我們稱之為直接映射，是基於使用 TargetRegisterInfo 和 MachineOperand 類別的方法。第二種方法，我們稱之為間接映射，依賴 VirtRegMap 類別來插入載入和儲存指令，以發送和接收記憶體的值。

直接映射為暫存器分配器的開發人員提供了更大的靈活性；但是，它更容易出錯，並且需要更多實作工作。基本上，程式設計師將必須指定應在正在編譯的目標函數中插入載入和儲存指令的位置，以便在記憶體中取得和儲存值。若要將實體暫存器指派給給定運算元中存在的虛擬暫存器，請使用 MachineOperand::setReg(p_reg)。若要插入儲存指令，請使用 TargetInstrInfo::storeRegToStackSlot(...)，若要插入載入指令，請使用 TargetInstrInfo::loadRegFromStackSlot。

間接映射使應用程式開發人員免於插入載入和儲存指令的複雜性。為了將虛擬暫存器映射到實體暫存器，請使用 VirtRegMap::assignVirt2Phys(vreg, preg)。為了將某個虛擬暫存器映射到記憶體，請使用 VirtRegMap::assignVirt2StackSlot(vreg)。此方法將傳回將放置 vreg 值的堆疊插槽。如果需要將另一個虛擬暫存器映射到相同的堆疊插槽，請使用 VirtRegMap::assignVirt2StackSlot(vreg, stack_location)。使用間接映射時要考慮的一個重點是，即使虛擬暫存器映射到記憶體，它仍然需要映射到實體暫存器。此實體暫存器是在儲存之前或重新載入之後應該找到虛擬暫存器的位置。

如果使用間接策略，在所有虛擬暫存器都已映射到實體暫存器或堆疊插槽之後，則需要使用溢出器物件在程式碼中放置載入和儲存指令。每個已映射到堆疊插槽的虛擬暫存器都將在定義後儲存到記憶體，並在使用前載入。溢出器的實作嘗試回收載入/儲存指令，避免不必要的指令。有關如何調用溢出器的範例，請參閱 lib/CodeGen/RegAllocLinearScan.cpp 中的 RegAllocLinearScan::runOnMachineFunction。

處理雙位址指令

除了極少數例外（例如，函數呼叫）之外，LLVM 機器碼指令都是三位址指令。也就是說，每個指令預計最多定義一個暫存器，並最多使用兩個暫存器。但是，某些架構使用雙位址指令。在這種情況下，定義的暫存器也是使用的暫存器之一。例如，X86 中的 ADD %EAX, %EBX 指令實際上等效於 %EAX = %EAX + %EBX。

為了產生正確的程式碼，LLVM 必須將表示雙位址指令的三位址指令轉換為真正的雙位址指令。LLVM 提供了 TwoAddressInstructionPass pass 來實現此特定目的。它必須在暫存器分配發生之前執行。在其執行之後，產生的程式碼可能不再是 SSA 形式。例如，在 %a = ADD %b %c 之類的指令轉換為以下兩個指令的情況下，就會發生這種情況：

%a = MOVE %b
%a = ADD %a %c

請注意，在內部，第二個指令表示為 ADD %a[def/use] %c。也就是說，暫存器運算元 %a 同時被指令使用和定義。

SSA 解構階段

暫存器分配期間發生的重要轉換稱為SSA 解構階段。SSA 形式簡化了對程式控制流程圖執行的許多分析。但是，傳統的指令集不實作 PHI 指令。因此，為了產生可執行程式碼，編譯器必須用其他指令替換 PHI 指令，以保留其語義。

有很多種方法可以安全地從目標程式碼中移除 PHI 指令。最傳統的 PHI 解構演算法用複製指令替換 PHI 指令。這是 LLVM 採用的策略。SSA 解構演算法在 lib/CodeGen/PHIElimination.cpp 中實作。為了調用此 pass，必須在暫存器分配器的程式碼中將識別碼 PHIEliminationID 標記為必要。

指令摺疊

指令摺疊是在暫存器分配期間執行的最佳化，可移除不必要的複製指令。例如，諸如以下的指令序列：

%EBX = LOAD %mem_address
%EAX = COPY %EBX

可以安全地替換為單一指令：

%EAX = LOAD %mem_address

可以使用 TargetRegisterInfo::foldMemoryOperand(...) 方法摺疊指令。摺疊指令時必須小心；摺疊後的指令可能與原始指令有很大不同。請參閱 lib/CodeGen/LiveIntervalAnalysis.cpp 中的 LiveIntervals::addIntervalsForSpills，以取得其用法的範例。

內建暫存器分配器

LLVM 基礎架構為應用程式開發人員提供了三種不同的暫存器分配器：

  • Fast — 此暫存器分配器是偵錯版本的預設分配器。它在基本區塊層級分配暫存器，嘗試將值保留在暫存器中，並在適當的時候重複使用暫存器。

  • Basic — 這是暫存器分配的增量方法。活躍範圍一次一個地分配給暫存器，順序由啟發式方法驅動。由於程式碼可以在分配期間即時重寫，因此此框架允許將有趣的分配器開發為擴展。它本身不是生產級暫存器分配器，但可能是用於分類錯誤和作為效能基準的潛在有用獨立模式。

  • Greedy — 預設分配器。這是 Basic 分配器的高度調整實作，它結合了全域活躍範圍分割。此分配器努力將溢出程式碼的成本降至最低。

  • PBQP — 基於分割布林二次規劃 (PBQP) 的暫存器分配器。此分配器透過建構表示正在考慮的暫存器分配問題的 PBQP 問題來工作，使用 PBQP 求解器求解此問題，並將解決方案映射回暫存器分配。

在 llc 中使用的暫存器分配器類型可以使用命令列選項 -regalloc=... 選擇。

$ llc -regalloc=linearscan file.bc -o ln.s
$ llc -regalloc=fast file.bc -o fa.s
$ llc -regalloc=pbqp file.bc -o pbqp.s

序言/後記程式碼插入

注意

待撰寫

精簡展開

拋出例外需要從函數中展開。有關如何展開給定函數的資訊傳統上以 DWARF 展開（又名 frame）資訊表示。但是該格式最初是為偵錯器回溯而開發的，每個 Frame Description Entry (FDE) 每個函數需要約 20-30 個位元組。在執行階段將函數中的位址映射到對應的 FDE 也需要成本。另一種展開編碼稱為精簡展開，每個函數僅需 4 個位元組。

精簡展開編碼是一個 32 位元值，它以架構特定的方式編碼。它指定要還原哪些暫存器以及從何處還原，以及如何從函數中展開。當連結器建立最終連結映像時，它將建立一個 __TEXT,__unwind_info 區段。此區段是一種小型且快速的方式，供執行階段存取任何給定函數的展開資訊。如果我們為函數發出精簡展開資訊，則該精簡展開資訊將編碼在 __TEXT,__unwind_info 區段中。如果我們發出 DWARF 展開資訊，則 __TEXT,__unwind_info 區段將包含最終連結映像中 __TEXT,__eh_frame 區段中 FDE 的偏移量。

對於 X86，精簡展開編碼有三種模式：

具有框架指標的函數（``EBP`` 或 ``RBP``）

基於 EBP/RBP 的框架，其中 EBP/RBP 在傳回位址後立即推入堆疊，然後將 ESP/RSP 移動到 EBP/RBP。因此，若要展開，ESP/RSP 會使用當前的 EBP/RBP 值還原，然後透過彈出堆疊來還原 EBP/RBP，並透過再次彈出堆疊到 PC 來完成傳回。所有需要還原的非揮發性暫存器都必須儲存在堆疊上的小範圍內，該範圍從 EBP-4 到 EBP-1020（RBP-8 到 RBP-1020）開始。偏移量（在 32 位元模式下除以 4，在 64 位元模式下除以 8）編碼在位元 16-23 中（遮罩：0x00FF0000）。儲存的暫存器編碼在位元 0-14 中（遮罩：0x00007FFF），作為來自下表的五個 3 位元條目：

精簡編號

i386 暫存器

x86-64 暫存器

1

EBX

RBX

2

ECX

R12

3

EDX

R13

4

EDI

R14

5

ESI

R15

6

EBP

RBP
無框架且具有小型常數堆疊大小（``EBP`` 或 ``RBP`` 不用作框架指標）

若要傳回，常數（編碼在精簡展開編碼中）會新增至 ESP/RSP。然後透過將堆疊彈出到 PC 來完成傳回。所有需要還原的非揮發性暫存器都必須儲存在緊接在傳回位址之後的堆疊上。堆疊大小（在 32 位元模式下除以 4，在 64 位元模式下除以 8）編碼在位元 16-23 中（遮罩：0x00FF0000）。在 32 位元模式下，最大堆疊大小為 1024 位元組，在 64 位元模式下為 2048 位元組。儲存的暫存器數量編碼在位元 9-12 中（遮罩：0x00001C00）。位元 0-9（遮罩：0x000003FF）包含儲存了哪些暫存器及其順序。（請參閱 lib/Target/X86FrameLowering.cpp 中的 encodeCompactUnwindRegistersWithoutFrame() 函數，以取得編碼演算法。）

無框架且具有大型常數堆疊大小（``EBP`` 或 ``RBP`` 不用作框架指標）

這種情況類似於「無框架且具有小型常數堆疊大小」的情況，但堆疊大小太大而無法編碼在精簡展開編碼中。相反，它要求函數在其序言中包含「subl $nnnnnn, %esp」。精簡編碼在位元 9-12 中包含函數中 $nnnnnn 值的偏移量（遮罩：0x00001C00）。

後期機器碼最佳化

注意

待撰寫

程式碼發射

程式碼產生的程式碼發射步驟負責從程式碼產生器抽象概念（如 MachineFunction、MachineInstr 等）降低到 MC 層使用的抽象概念（MCInst、MCStreamer 等）。這是透過幾個不同類別的組合來完成的：目標獨立的 AsmPrinter 類別（名稱不當）、AsmPrinter 的目標特定子類別（例如 SparcAsmPrinter）和 TargetLoweringObjectFile 類別。

由於 MC 層在物件檔案的抽象層級上運作，因此它沒有函數、全域變數等的概念。相反，它考慮標籤、指令和指令。此時使用的關鍵類別是 MCStreamer 類別。這是一個抽象 API，它以不同的方式實作（例如，輸出 .s 檔案、輸出 ELF .o 檔案等），實際上是一個「組譯器 API」。MCStreamer 每個指令都有一個方法，例如 EmitLabel、EmitSymbolAttribute、switchSection 等，它們直接對應於組譯層級指令。

如果您有興趣為目標實作程式碼產生器，則需要為您的目標實作三個重要的東西：

  1. 首先，您需要目標的 AsmPrinter 子類別。此類別實作將 MachineFunction 轉換為 MC 標籤結構的一般降低流程。AsmPrinter 基底類別提供了許多有用的方法和常式，並且還允許您以一些重要的方式覆寫降低流程。如果您正在實作 ELF、COFF 或 MachO 目標，您應該可以免費獲得大部分降低，因為 TargetLoweringObjectFile 類別實作了許多通用邏輯。

  2. 其次，您需要為您的目標實作指令印表機。指令印表機取得 MCInst 並將其呈現為 raw_ostream 作為文字。大部分內容是從 .td 檔案自動產生的（當您在指令中指定類似「add $dst, $src1, $src2」的內容時），但您需要實作常式來列印運算元。

  3. 第三，您需要實作將 MachineInstr 降低為 MCInst 的程式碼，通常在「<target>MCInstLower.cpp」中實作。此降低流程通常是目標特定的，並且負責將跳躍表條目、常數池索引、全域變數位址等轉換為適當的 MCLabel。此轉換層也負責將程式碼產生器使用的虛擬運算擴展為它們對應的實際機器指令。由此產生的 MCInst 會饋送到指令印表機或編碼器。

最後，您可以選擇實作 MCCodeEmitter 的子類別，將 MCInst 降低為機器碼位元組和重定位。如果您想要支援直接發射 .o 檔案，或想要為您的目標實作組譯器，這點非常重要。

發射函式堆疊大小資訊

當 TargetLoweringObjectFile::StackSizesSection 不是 null，且 TargetOptions::EmitStackSizeSection 設定時 (-stack-size-section)，將會發射包含函式堆疊大小元資料的區段。該區段將包含函式符號值（指標大小）和堆疊大小 (unsigned LEB128) 的配對陣列。堆疊大小值僅包含在函式序言中配置的空間。具有動態堆疊配置的函式不包含在內。

VLIW 指令封包器

在超長指令字組 (VLIW) 架構中，編譯器負責將指令對應到架構上可用的功能單元。為此，編譯器會建立稱為封包或捆綁的指令群組。LLVM 中的 VLIW 指令封包器是一種目標獨立機制，可啟用機器指令的封包化。

從指令到功能單元的對應

VLIW 目標中的指令通常可以對應到多個功能單元。在封包化過程中，編譯器必須能夠推論指令是否可以新增到封包中。這個決定可能很複雜，因為編譯器必須檢查指令到功能單元的所有可能對應。因此，為了減輕編譯時的複雜性，VLIW 指令封包器會解析目標的指令類別，並在編譯器建置時產生表格。然後，提供的獨立於機器的 API 可以查詢這些表格，以確定指令是否可以容納在封包中。

封包化表格的產生和使用方式

指令封包器從目標的行程讀取指令類別，並建立確定性有限自動機 (DFA) 來表示封包的狀態。DFA 由三個主要元素組成：輸入、狀態和轉換。產生 DFA 的輸入集表示要新增到封包的指令。狀態表示封包中指令可能消耗的功能單元。在 DFA 中，從一個狀態到另一個狀態的轉換發生在將指令新增到現有封包時。如果功能單元到指令存在合法的對應，則 DFA 包含相應的轉換。缺少轉換表示不存在合法的對應，並且該指令無法新增到封包中。

要為 VLIW 目標產生表格，請將 TargetGenDFAPacketizer.inc 作為目標目錄中 Makefile 的目標新增。匯出的 API 提供三個函式：DFAPacketizer::clearResources()、DFAPacketizer::reserveResources(MachineInstr *MI) 和 DFAPacketizer::canReserveResources(MachineInstr *MI)。這些函式允許目標指令封包器將指令新增到現有封包，並檢查指令是否可以新增到封包。有關更多資訊，請參閱 llvm/CodeGen/DFAPacketizer.h。

實作原生組譯器

雖然您閱讀本文可能是因為您想要編寫或維護編譯器後端，但 LLVM 也完全支援建置原生組譯器。我們已努力自動化從 .td 檔案（特別是指令語法和編碼）產生組譯器的過程，這表示大部分手動和重複的資料輸入可以被分解並與編譯器共用。

指令剖析

注意

待撰寫

指令別名處理

指令剖析完成後，它會進入 MatchInstructionImpl 函式。MatchInstructionImpl 函式執行別名處理，然後執行實際的匹配。

別名處理階段將相同指令的不同詞彙形式規範化為一個表示形式。可以實作幾種不同的別名，它們在下面列出，順序是它們被處理的順序（從最簡單/最弱到最複雜/最強）。通常，您會想要使用滿足您指令需求的第一個別名機制，因為它將允許更簡潔的描述。

助記符別名

別名處理的第一階段是簡單的指令助記符重新對應，適用於允許使用兩個不同助記符的指令類別。此階段是從一個輸入助記符到一個輸出助記符的簡單且無條件的重新對應。此形式的別名不可能查看運算元，因此重新對應必須適用於給定助記符的所有形式。助記符別名定義很簡單，例如 X86 具有

def : MnemonicAlias<"cbw",     "cbtw">;
def : MnemonicAlias<"smovq",   "movsq">;
def : MnemonicAlias<"fldcww",  "fldcw">;
def : MnemonicAlias<"fucompi", "fucomip">;
def : MnemonicAlias<"ud2a",    "ud2">;

… 以及許多其他別名。透過 MnemonicAlias 定義，助記符會被簡單且直接地重新對應。雖然 MnemonicAlias 無法查看指令的任何方面（例如運算元），但它們可以依賴全域模式（與匹配器支援的模式相同），透過 Requires 子句

def : MnemonicAlias<"pushf", "pushfq">, Requires<[In64BitMode]>;
def : MnemonicAlias<"pushf", "pushfl">, Requires<[In32BitMode]>;

在此範例中，助記符會根據目前的指令集對應到不同的助記符。

指令別名

別名處理最通用的階段發生在匹配正在進行時：它為匹配器提供新的形式來匹配，以及要產生的特定指令。指令別名有兩個部分：要匹配的字串和要產生的指令。例如

def : InstAlias<"movsx $src, $dst", (MOVSX16rr8W GR16:$dst, GR8  :$src)>;
def : InstAlias<"movsx $src, $dst", (MOVSX16rm8W GR16:$dst, i8mem:$src)>;
def : InstAlias<"movsx $src, $dst", (MOVSX32rr8  GR32:$dst, GR8  :$src)>;
def : InstAlias<"movsx $src, $dst", (MOVSX32rr16 GR32:$dst, GR16 :$src)>;
def : InstAlias<"movsx $src, $dst", (MOVSX64rr8  GR64:$dst, GR8  :$src)>;
def : InstAlias<"movsx $src, $dst", (MOVSX64rr16 GR64:$dst, GR16 :$src)>;
def : InstAlias<"movsx $src, $dst", (MOVSX64rr32 GR64:$dst, GR32 :$src)>;

這顯示了指令別名的強大範例，根據組譯中存在的運算元，以多種不同的方式匹配相同的助記符。指令別名的結果可以包含與目標指令順序不同的運算元，並且可以多次使用輸入，例如

def : InstAlias<"clrb $reg", (XOR8rr  GR8 :$reg, GR8 :$reg)>;
def : InstAlias<"clrw $reg", (XOR16rr GR16:$reg, GR16:$reg)>;
def : InstAlias<"clrl $reg", (XOR32rr GR32:$reg, GR32:$reg)>;
def : InstAlias<"clrq $reg", (XOR64rr GR64:$reg, GR64:$reg)>;

此範例也顯示了綁定運算元僅列出一次。在 X86 後端中，XOR8rr 有兩個輸入 GR8 和一個輸出 GR8（其中一個輸入綁定到輸出）。InstAliases 採用扁平化的運算元列表，沒有重複的綁定運算元。指令別名的結果也可以使用立即值和固定的實體暫存器，這些暫存器作為結果中的簡單立即運算元新增，例如

// Fixed Immediate operand.
def : InstAlias<"aad", (AAD8i8 10)>;

// Fixed register operand.
def : InstAlias<"fcomi", (COM_FIr ST1)>;

// Simple alias.
def : InstAlias<"fcomi $reg", (COM_FIr RST:$reg)>;

指令別名也可以具有 Requires 子句，使其成為子目標特定的別名。

如果後端支援，指令印表機可以自動發射別名，而不是正在別名的內容。這通常會產生更好、更易於閱讀的程式碼。如果最好印出正在別名的內容，則將 '0' 作為 InstAlias 定義的第三個參數傳遞。

指令匹配

注意

待撰寫

目標特定的實作注意事項

文件的本節說明特定於特定目標程式碼產生器的功能或設計決策。

尾端呼叫最佳化

尾端呼叫最佳化，被呼叫者重複使用呼叫者的堆疊，目前在 x86/x86-64、PowerPC、AArch64 和 WebAssembly 上受到支援。如果符合以下條件，則會在 x86/x86-64、PowerPC 和 AArch64 上執行：

  • 呼叫者和被呼叫者都具有呼叫慣例 fastcc、cc 10 (GHC 呼叫慣例)、cc 11 (HiPE 呼叫慣例)、tailcc 或 swifttailcc。

  • 呼叫是尾端呼叫 - 位於尾端位置（ret 緊接在 call 之後，且 ret 使用 call 的值或為 void）。

  • 選項 -tailcallopt 已啟用，或呼叫慣例為 tailcc。

  • 符合平台特定的限制。

x86/x86-64 限制

  • 未使用可變參數列表。

  • 在 x86-64 上產生 GOT/PIC 程式碼時，僅支援模組本機呼叫（可見性 = hidden 或 protected）。

PowerPC 限制

  • 未使用可變參數列表。

  • 未使用 byval 參數。

  • 在 ppc32/64 GOT/PIC 上，僅支援模組本機呼叫（可見性 = hidden 或 protected）。

WebAssembly 限制

  • 未使用可變參數列表

  • 已啟用 'tail-call' 目標屬性。

  • 呼叫者和被呼叫者的傳回型別必須匹配。除非被呼叫者也是 void，否則呼叫者不能是 void。

AArch64 限制

  • 未使用可變參數列表。

範例

呼叫方式為 llc -tailcallopt test.ll。

declare fastcc i32 @tailcallee(i32 inreg %a1, i32 inreg %a2, i32 %a3, i32 %a4)

define fastcc i32 @tailcaller(i32 %in1, i32 %in2) {
  %l1 = add i32 %in1, %in2
  %tmp = tail call fastcc i32 @tailcallee(i32 inreg %in1, i32 inreg %in2, i32 %in1, i32 %l1)
  ret i32 %tmp
}

-tailcallopt 的含義

為了在被呼叫者的引數多於呼叫者的情況下支援尾端呼叫最佳化，使用了「被呼叫者彈出引數」慣例。這目前會導致每個未進行尾端呼叫最佳化的 fastcc 呼叫（因為未滿足上述一個或多個限制）之後，都要進行堆疊的重新調整。因此，在這種情況下，效能可能會更差。

同級呼叫最佳化

同級呼叫最佳化是尾端呼叫最佳化的受限形式。與上一節中描述的尾端呼叫最佳化不同，當未指定 -tailcallopt 選項時，它可以自動在任何尾端呼叫上執行。

當滿足以下限制時，目前在 x86/x86-64 上執行同級呼叫最佳化

  • 呼叫者和被呼叫者具有相同的呼叫慣例。它可以是 c 或 fastcc。

  • 呼叫是尾端呼叫 - 位於尾端位置（ret 緊接在 call 之後，且 ret 使用 call 的值或為 void）。

  • 呼叫者和被呼叫者具有匹配的傳回型別，或未使用被呼叫者的結果。

  • 如果任何被呼叫者的引數透過堆疊傳遞，則它們必須在呼叫者自己的傳入引數堆疊中可用，並且框架偏移量必須相同。

範例

declare i32 @bar(i32, i32)

define i32 @foo(i32 %a, i32 %b, i32 %c) {
entry:
  %0 = tail call i32 @bar(i32 %a, i32 %b)
  ret i32 %0
}

X86 後端

X86 程式碼產生器位於 lib/Target/X86 目錄中。此程式碼產生器能夠以各種 x86-32 和 x86-64 處理器為目標，並包含對 ISA 擴充功能（例如 MMX 和 SSE）的支援。

支援的 X86 目標三元組

以下是 X86 後端支援的已知目標三元組。這不是詳盡的列表，新增人們測試過的目標三元組會很有用。

  • i686-pc-linux-gnu — Linux

  • i386-unknown-freebsd5.3 — FreeBSD 5.3

  • i686-pc-cygwin — Win32 上的 Cygwin

  • i686-pc-mingw32 — Win32 上的 MingW

  • i386-pc-mingw32msvc — Linux 上的 MingW 交叉編譯器

  • i686-apple-darwin* — X86 上的 Apple Darwin

  • x86_64-unknown-linux-gnu — Linux

支援的 X86 呼叫慣例

以下是後端已知的目標特定呼叫慣例

  • x86_StdCall — 在 Microsoft Windows 平台上看到的 stdcall 呼叫慣例 (CC ID = 64)。

  • x86_FastCall — 在 Microsoft Windows 平台上看到的 fastcall 呼叫慣例 (CC ID = 65)。

  • x86_ThisCall — 類似於 X86_StdCall。在 ECX 中傳遞第一個引數，其他引數透過堆疊傳遞。被呼叫者負責堆疊清理。MSVC 在其 ABI 中預設將此慣例用於方法 (CC ID = 70)。

在 MachineInstrs 中表示 X86 定址模式

x86 具有非常彈性的記憶體存取方式。它能夠直接在整數指令中形成以下表示式的記憶體位址（使用 ModR/M 定址）：

SegmentReg: Base + [1,2,4,8] * IndexReg + Disp32

為了表示這一點，LLVM 為這種形式的每個記憶體運算元追蹤不少於 5 個運算元。這表示 'mov' 的「載入」形式依序具有以下 MachineOperand：

Index:        0     |    1        2       3           4          5
Meaning:   DestReg, | BaseReg,  Scale, IndexReg, Displacement Segment
OperandTy: VirtReg, | VirtReg, UnsImm, VirtReg,   SignExtImm  PhysReg

儲存和所有其他指令都以相同的方式且以相同的順序處理四個記憶體運算元。如果未指定區段暫存器 (regno = 0)，則不會產生區段覆寫。「Lea」運算未指定區段暫存器，因此它們的記憶體參考只有 4 個運算元。

支援的 X86 位址空間

x86 具有一項功能，可透過 x86 區段暫存器執行對不同位址空間的載入和儲存。指令上的區段覆寫前置位元組會導致指令的記憶體存取進入指定的區段。LLVM 位址空間 0 是預設位址空間，其中包括堆疊以及程式中的任何未限定的記憶體存取。位址空間 1-255 目前保留供使用者定義程式碼使用。GS 區段由位址空間 256 表示，FS 區段由位址空間 257 表示，SS 區段由位址空間 258 表示。其他 x86 區段尚未分配位址空間編號。

雖然這些位址空間可能看起來與透過 thread_local 關鍵字的 TLS 相似，並且通常使用相同的底層硬體，但它們之間存在一些根本差異。

thread_local 關鍵字適用於全域變數，並指定它們要配置在執行緒本機記憶體中。不涉及型別限定詞，並且可以使用一般指標指向這些變數，並使用一般載入和儲存來存取。在 LLVM IR 層級，thread_local 關鍵字是獨立於目標的（儘管 LLVM 尚未針對某些配置實作它）

相反地，特殊位址空間適用於靜態型別。每個載入和儲存在其位址運算元型別中都有特定的位址空間，這決定了存取的位址空間。LLVM 忽略全域變數上的這些特殊位址空間限定詞，並且不提供直接在其中配置儲存空間的方法。在 LLVM IR 層級，這些特殊位址空間的行為部分取決於底層作業系統或執行階段環境，它們是 x86 特有的（並且 LLVM 在某些情況下尚未正確處理它們）。

某些作業系統和執行階段環境使用（或將來可能會使用）FS/GS 區段暫存器用於各種低階用途，因此在考慮它們時應謹慎。

指令命名

指令名稱由基本名稱、預設運算元大小以及每個運算元的字元和可選的特殊大小組成。例如

ADD8rr      -> add, 8-bit register, 8-bit register
IMUL16rmi   -> imul, 16-bit register, 16-bit memory, 16-bit immediate
IMUL16rmi8  -> imul, 16-bit register, 16-bit memory, 8-bit immediate
MOVSX32rm16 -> movsx, 32-bit register, 16-bit memory

PowerPC 後端

PowerPC 程式碼產生器位於 lib/Target/PowerPC 目錄中。程式碼產生可重新定向到 PowerPC ISA 的幾個變體或子目標；包括 ppc32、ppc64 和 altivec。

LLVM PowerPC ABI

LLVM 遵循 AIX PowerPC ABI，但有兩個偏差。LLVM 使用 PC 相對 (PIC) 或靜態定址來存取全域值，因此未使用 TOC (r2)。其次，r31 用作框架指標，以允許堆疊框架的動態成長。LLVM 利用沒有 TOC 的優勢，在呼叫者框架的 PowerPC 連結區域中提供空間來儲存框架指標。PowerPC ABI 的其他詳細資訊可以在 PowerPC ABI 中找到。注意：此連結描述了 32 位元 ABI。64 位元 ABI 類似，除了 GPR 的空間為 8 位元組寬（而不是 4 位元組），並且 r13 保留供系統使用。

框架佈局

PowerPC 框架的大小通常在函式調用期間是固定的。由於框架大小是固定的，因此可以透過來自堆疊指標的固定偏移量來存取框架中的所有參考。當存在動態 alloca 或可變大小陣列時，這是例外情況，然後使用基底指標 (r31) 作為堆疊指標的代理，並且堆疊指標可以自由成長或縮小。如果 llvm-gcc 未傳遞 -fomit-frame-pointer 旗標，也會使用基底指標。堆疊指標始終對齊到 16 個位元組，以便為 altivec 向量配置的空間能夠正確對齊。

調用框架佈局如下（低記憶體在頂部）

連結
參數區域
動態區域
本機變數區域
已儲存暫存器區域

先前的框架

連結區域由被呼叫者用於在配置自己的框架之前儲存特殊暫存器。只有三個條目與 LLVM 相關。第一個條目是先前的堆疊指標 (sp)，也稱為連結。這允許探測工具（如 gdb）或例外處理常式快速掃描堆疊中的框架。函式 epilog 也可以使用連結從堆疊中彈出框架。連結區域中的第三個條目用於儲存來自 lr 暫存器的傳回位址。最後，如上所述，最後一個條目用於儲存先前的框架指標 (r31)。連結區域中的條目是 GPR 的大小，因此在 32 位元模式下，連結區域長 24 個位元組，在 64 位元模式下長 48 個位元組。

32 位元連結區域

0 已儲存 SP (r1)
4 已儲存 CR
8 已儲存 LR
12 保留
16 保留
20 已儲存 FP (r31)

64 位元連結區域

0 已儲存 SP (r1)
8 已儲存 CR
16 已儲存 LR
24 保留
32 保留
40 已儲存 FP (r31)

參數區域用於儲存傳遞給被呼叫函式的引數。根據 PowerPC ABI，前幾個引數實際上是在暫存器中傳遞的，參數區域中的空間未使用。但是，如果暫存器不足，或者被呼叫者是 thunk 或 vararg 函式，則這些暫存器引數可以溢出到參數區域中。因此，參數區域必須足夠大，才能儲存呼叫者進行的最大呼叫序列的所有參數。大小也必須至少足夠大，才能溢出暫存器 r3-r10。這允許不知道呼叫簽章的被呼叫者（例如 thunk 和 vararg 函式）有足夠的空間來快取引數暫存器。因此，參數區域最小為 32 個位元組（在 64 位元模式下為 64 個位元組）。另請注意，由於參數區域是框架頂部的固定偏移量，因此被呼叫者可以使用來自堆疊指標（或基底指標）的固定偏移量來存取其分割的引數。

結合有關連結、參數區域和對齊方式的資訊。堆疊框架在 32 位元模式下最小為 64 個位元組，在 64 位元模式下最小為 128 個位元組。

動態區域的起始大小為零。如果函式使用動態 alloca，則會將空間新增到堆疊，連結和參數區域會移至堆疊頂部，並且新空間在連結和參數區域下方立即可用。移動連結和參數區域的成本很小，因為只需要複製連結值。透過將原始框架大小新增到基底指標，可以輕鬆擷取連結值。請注意，動態空間中的配置需要遵守 16 位元組對齊。

本機變數區域是 llvm 編譯器為本機變數保留空間的位置。

已儲存暫存器區域是 llvm 編譯器在進入被呼叫者時溢出被呼叫者儲存的暫存器的位置。

序言/結語

llvm 序言和結語與 PowerPC ABI 中描述的相同，但有以下例外情況。被呼叫者儲存的暫存器在建立框架後溢出。這允許 llvm epilog/prolog 支援與其他目標通用。基底指標被呼叫者儲存的暫存器 r31 儲存在連結區域的 TOC 插槽中。這簡化了基底指標空間的配置，並使其在程式設計和偵錯期間易於定位。

動態配置

注意

TODO - 更多內容即將推出。

NVPTX 後端

lib/Target/NVPTX 下的 NVPTX 程式碼產生器是 NVIDIA NVPTX 程式碼產生器的開放原始碼版本，適用於 LLVM。它由 NVIDIA 貢獻，是 CUDA 編譯器 (nvcc) 中使用的程式碼產生器的移植版本。它以 PTX 3.0/3.1 ISA 為目標，並且可以以任何運算能力大於或等於 2.0 (Fermi) 的目標。

此目標具有生產品質，並且應與官方 NVIDIA 工具鏈完全相容。

程式碼產生器選項

選項 描述
sm_20 將著色器模型/運算能力設定為 2.0
sm_21 將著色器模型/運算能力設定為 2.1
sm_30 將著色器模型/運算能力設定為 3.0
sm_35 將著色器模型/運算能力設定為 3.5
ptx30 目標 PTX 3.0
ptx31 目標 PTX 3.1

延伸 Berkeley 封包過濾器 (eBPF) 後端

延伸 BPF (或 eBPF) 類似於用於過濾網路封包的原始（「經典」）BPF (cBPF)。bpf() 系統呼叫 執行一系列與 eBPF 相關的操作。對於 cBPF 和 eBPF 程式，Linux 核心在載入程式之前會靜態分析程式，以確保它們不會損害執行中的系統。eBPF 是一個 64 位元 RISC 指令集，設計用於一對一對應到 64 位元 CPU。運算碼以 8 位元編碼，並定義了 87 個指令。有 10 個暫存器，按功能分組如下。

R0        return value from in-kernel functions; exit value for eBPF program
R1 - R5   function call arguments to in-kernel functions
R6 - R9   callee-saved registers preserved by in-kernel functions
R10       stack frame pointer (read only)

指令編碼（算術和跳躍）

eBPF 重新使用經典的大部分運算碼編碼，以簡化將經典 BPF 轉換為 eBPF。對於算術和跳躍指令，8 位元 'code' 欄位分為三個部分

+----------------+--------+--------------------+
|   4 bits       |  1 bit |   3 bits           |
| operation code | source | instruction class  |
+----------------+--------+--------------------+
(MSB)                                      (LSB)

三個 LSB 位元儲存指令類別，它是以下其中之一

BPF_LD     0x0
BPF_LDX    0x1
BPF_ST     0x2
BPF_STX    0x3
BPF_ALU    0x4
BPF_JMP    0x5
(unused)   0x6
BPF_ALU64  0x7

當 BPF_CLASS(code) == BPF_ALU 或 BPF_ALU64 或 BPF_JMP 時，第 4 個位元編碼來源運算元

BPF_X     0x1  use src_reg register as source operand
BPF_K     0x0  use 32 bit immediate as source operand

四個 MSB 位元儲存運算碼

BPF_ADD   0x0  add
BPF_SUB   0x1  subtract
BPF_MUL   0x2  multiply
BPF_DIV   0x3  divide
BPF_OR    0x4  bitwise logical OR
BPF_AND   0x5  bitwise logical AND
BPF_LSH   0x6  left shift
BPF_RSH   0x7  right shift (zero extended)
BPF_NEG   0x8  arithmetic negation
BPF_MOD   0x9  modulo
BPF_XOR   0xa  bitwise logical XOR
BPF_MOV   0xb  move register to register
BPF_ARSH  0xc  right shift (sign extended)
BPF_END   0xd  endianness conversion

如果 BPF_CLASS(code) == BPF_JMP，則 BPF_OP(code) 是以下其中之一

BPF_JA    0x0  unconditional jump
BPF_JEQ   0x1  jump ==
BPF_JGT   0x2  jump >
BPF_JGE   0x3  jump >=
BPF_JSET  0x4  jump if (DST & SRC)
BPF_JNE   0x5  jump !=
BPF_JSGT  0x6  jump signed >
BPF_JSGE  0x7  jump signed >=
BPF_CALL  0x8  function call
BPF_EXIT  0x9  function return

指令編碼（載入、儲存）

對於載入和儲存指令，8 位元 'code' 欄位劃分為

+--------+--------+-------------------+
| 3 bits | 2 bits |   3 bits          |
|  mode  |  size  | instruction class |
+--------+--------+-------------------+
(MSB)                             (LSB)

大小修飾符是以下其中之一

BPF_W       0x0  word
BPF_H       0x1  half word
BPF_B       0x2  byte
BPF_DW      0x3  double word

模式修飾符是以下其中之一

BPF_IMM     0x0  immediate
BPF_ABS     0x1  used to access packet data
BPF_IND     0x2  used to access packet data
BPF_MEM     0x3  memory
(reserved)  0x4
(reserved)  0x5
BPF_XADD    0x6  exclusive add

封包資料存取 (BPF_ABS, BPF_IND)

兩個非通用指令：(BPF_ABS | <size> | BPF_LD) 和 (BPF_IND | <size> | BPF_LD)，用於存取封包資料。暫存器 R6 是一個隱含輸入，必須包含指向 sk_buff 的指標。暫存器 R0 是一個隱含輸出，其中包含從封包擷取的資料。暫存器 R1-R5 是暫存暫存器，不得用於在 BPF_ABS | BPF_LD 或 BPF_IND | BPF_LD 指令之間儲存資料。這些指令也具有隱含的程式結束條件。當 eBPF 程式嘗試存取超出封包邊界的資料時，解譯器將中止程式的執行。

BPF_IND | BPF_W | BPF_LD 等效於

R0 = ntohl(*(u32 *) (((struct sk_buff *) R6)->data + src_reg + imm32))

eBPF 映射

提供 eBPF 映射以在核心和使用者空間之間共用資料。目前實作的型別是雜湊和陣列，可能會擴充以支援布隆過濾器、基數樹等。映射由其型別、元素的最大數量、金鑰大小和值大小（以位元組為單位）定義。eBPF 系統呼叫支援在映射上建立、更新、尋找和刪除函式。

函式呼叫

函式呼叫引數最多使用五個暫存器 (R1 - R5) 傳遞。傳回值在專用暫存器 (R0) 中傳遞。四個額外的暫存器 (R6 - R9) 是被呼叫者儲存的，並且這些暫存器中的值在核心函式中會被保留。R0 - R5 是核心函式中的暫存暫存器，因此，如果需要在函式呼叫之間使用這些暫存器中的值，則 eBPF 程式必須儲存/還原這些暫存器中的值。可以使用唯讀框架指標 R10 存取堆疊。eBPF 暫存器與 x86_64 和其他 64 位元架構上的硬體暫存器 1:1 對應。例如，x86_64 核心 JIT 將它們映射為

R0 - rax
R1 - rdi
R2 - rsi
R3 - rdx
R4 - rcx
R5 - r8
R6 - rbx
R7 - r13
R8 - r14
R9 - r15
R10 - rbp

因為 x86_64 ABI 規定 rdi、rsi、rdx、rcx、r8、r9 用於引數傳遞，而 rbx、r12 - r15 是被呼叫者儲存的。

程式啟動

eBPF 程式接收單個引數並包含單個 eBPF 主要常式；程式不包含 eBPF 函式。函式呼叫僅限於預定義的核心函式集。程式的大小限制為 4K 指令：這確保了快速終止和有限數量的核心函式呼叫。在執行 eBPF 程式之前，驗證器會執行靜態分析，以防止程式碼中的迴圈，並確保有效的暫存器使用和運算元型別。

AMDGPU 後端

AMDGPU 程式碼產生器位於 lib/Target/AMDGPU 目錄中。此程式碼產生器能夠以各種 AMD GPU 處理器為目標。有關更多資訊，請參閱 AMDGPU 後端使用者指南。