原文地址：blog.yossarian.net/2021/08/10/…

原文作者：blog.yossarian.net

發布時間：2021年8月10日

前言

之前的內容。LLVM內部，第一部分。

在上一篇文章中，我對LLVM的比特碼格式（以及底層的比特流容器錶示法）進行了高層次的概述。那篇文章的最終結果是發布了llvm-bitcursor，它為一個純Rust的比特碼分析器提供了關鍵的第一個抽象。

這篇文章將是一個更具體的解析實際LLVM比特流的過程，是由另一個發布公告：llvm-bitstream激發的。

將llvm-bitcursor和llvm-bitstream放在一起，使我們在實現LLVM IR的純Rust解析器方面有三分之二的進展。剩下的主要組件是一個 "映射器"，從比特流中的塊和記錄錶示到實際的IR級錶示（對應於官方C++ API中的llvm::Module, llvm::Function, &c）。

回顧：比特流格式

快速回顧一下。LLVM的比特流格式有兩種實體：塊和記錄。塊提供了解析其組成記錄（和子塊）所需的基本狀態量；記錄是自成一體的字段序列。在比特流層面，記錄的字段只是無符號整數1。

每個塊都由一個全局唯一的 "塊ID "來識別（即為正在解析的那種比特流全局定義），而每個記錄都由一個 "記錄代碼 "來識別，該代碼只對記錄所在的塊的種類唯一2。

塊和記錄都不是字節對齊的（因此比特流中的 "比特"），也不保證在一個給定的比特流中具有一致的大小：發射器被允許出於壓縮目的改變其對可變比特整數的使用，而消費者被期望處理這個問題。

比特流中的每個實體（記錄和塊！）都有一個縮寫ID，它告訴解析器應該如何去解析緊隨ID的實體。縮寫ID屬於兩組中的一組（保留或定義），可以用以下漂亮的Rust枚舉來進行建模。

/// Abbreviation IDs that are reserved by LLVM.
#[repr(u64)]
pub enum ReservedAbbrevId {
/// Identifies an `END_BLOCK` record.
EndBlock = 0,
/// Identifies an `ENTER_SUBBLOCK` record.
EnterSubBlock,
/// Identifies a `DEFINE_ABBREV` record.
DefineAbbrev,
/// Identifies an `UNABBREV_RECORD` record.
UnabbrevRecord,
}
/// An abbreviation ID, whether reserved or defined by the stream itself.
pub enum AbbrevId {
/// A reserved abbreviation ID.
Reserved(ReservedAbbrevId),
/// An abbreviation ID that's been defined within the stream.
Defined(u64),
}
複制代碼

保留的縮寫ID可以被認為是 "引導 "標記--它們為範圍界定（ENTER_SUBBLOCK和END_BLOCK）和記錄定義（DEFINE_ABBREV和UNABBREV_RECORD）提供所需的最小結構量。特別是DEFINE_ABBREV是 "引導 "類比的閃光點：它發出一個 "縮寫定義 "記錄的信號，導致一個特定範圍的定義縮寫ID。稍後會有更多關於記錄格式化和範圍規則的內容。

解析比特流

為了成功和正確地解析LLVM比特流，我們需要處理容器格式的三個離散方面。

1. 單個記錄可以出現的格式。
2. 用於確定如何解析單個記錄的範圍規則。
3. 解析器的狀態機和推進機制。

讓我們逐一來做。

記錄格式

如上所述：所有的記錄都以一個縮寫ID開始。更具體地說，所有記錄都以UNABBREV_RECORD（即ID 3）或一個定義好的縮寫ID開始，該縮寫ID指向適用於該記錄所處範圍的DEFINE_ABBREV記錄。

UNABBREV_RECORD被稱為非縮寫記錄，而所有其他記錄都是縮寫記錄（因為如上所述，它們的格式是由流中其他地方的縮寫定義所定義的）。非縮寫記錄比較簡單，所以我們就從它們開始。

非縮寫記錄

UNABBREV_RECORD格式是一種低效的通用格式，適用於自定義記錄定義過於複雜或不能產生有意義的大小改進的情况（如在BLOCKINFO塊內）。UNABBREV_RECORD格式的記錄看起來像這樣。

[code:VBR6, numops:VBR6, op0:VBR6, op1:VBR6, ...]
複制代碼

(這裏和下面：:VBR<N>和:<N>的後綴分別錶示可變寬度和固定寬度的整數。關於VBR的更多細節，請參見LLVM文檔和上一篇文章）。)

為了把它聯系起來。

• 我們通過讀取一個6比特的VBR來讀取記錄的代碼。
• 我們以另一個6比特的VBR來讀取這個記錄中的 "操作數"（即字段）的數量。
• 對於numops中的每個操作數，我們讀取另一個6比特VBR；這是該特定操作數的實際字段值。

舉例來說，考慮以下UNABBREV_RECORD的字符串錶示。

[0b000100, 0b000011, 0b010000, 0b011111, 0b000001, 0b100000]
複制代碼

這定義了一條代碼為4（0b000100）的新記錄，有三個字段。

• 字段0：16 (0b010000)
• 字段1：31 (0b011111)
• 字段2：32（[0b000001, 0b100000]）。

注意，字段2是12比特，而不是6比特，因為32的值在一個VBR6塊中是無法錶示的!

DEFINE_ABBREV和簡略的記錄

現在我們知道了如何解析未縮寫的記錄，讓我們進入比特流的核心部分：縮寫定義和使用縮寫的記錄。

正如在上一篇文章中提到的，LLVM的比特流容器從根本上說是一種自我描述的格式：强烈鼓勵發射者使用DEFINE_ABBREV來產生緊凑的比特流，而不是依賴更通用、更不緊凑的UNABBREV_RECORD編碼。

要解析一個縮寫記錄，我們需要獲得其相應的縮寫定義，即適當範圍的DEFINE_ABBREV，它定義了我們將要解析的結構。獲得這個DEFINE_ABBREV的實際範圍規則緊接著在下面描述，所以我們在本節中只假設它們。

一旦我們真正擁有了DEFINE_ABBREV，它看起來就像這樣。

[numabbrevops:VBR5, abbrevop0, abbrevop1, ...]
複制代碼

看起來很像上面的UNABBREV_RECORD結構! 一些突出的區別。

• DEFINE_ABBREV並沒有為記錄代碼指定一個獨立的字段。相反，第一個縮寫操作數指定了記錄代碼。

• 縮寫操作數不是具體的字段：它們是符號操作數，告訴比特流解析器如何解析使用DEFINE_ABBREV結構的具體記錄的實際字段。

這裏有一個適當的類比，就是結構定義與聲明結構的任何特定實例：在UNABBREV_RECORD是一個自我描述的格式，任何縮寫記錄都需要引用其DEFINE_ABBREV來進行正確解析。

解析縮寫操作數是在numabbrevops的循環中進行的，就像UNABBREV_RECORD一樣。每個操作數都有以下的比特形式。

[encoded:1, ...]
複制代碼

...其中encoded是一個1比特的字段，錶示操作數是否被 "編碼"。當encoded為1時，操作數是一個 "字面 "操作數，其形式如下。

[litvalue:VBR8]
複制代碼

"字面 "操作數是前面3的 "具體與符號 "概念規則的例外：當DEFINE_ABBREV有一個字面操作數時，該操作數的記錄域在所有使用同一縮寫的記錄中具有相同的值。這一點的明顯應用是記錄代碼，因為我們希望大多數共用一個縮寫的記錄都有相同的代碼。然而，LLVM實際上並沒有强制規定只有第一個操作數可以是字面的（或者必須是字面的），所以沒有什麼可以阻止比特流發射器對其他記錄字段使用字面的。

相比之下，當編碼為0時，解析器會闡述為以下形式之一。

[encoding:3]
[encoding:3, value:VBR5]
複制代碼

闡述的形式是由編碼的值决定的，主要是。

• 固定（1）和VBR（2）。[encoding:3, value:VBR5]。
  • 對於這些編碼，value錶示解析所需的 "額外數據"：對於Fixed，value錶示讀取一個固定寬度的值所需的比特數，而對於VBR，它錶示讀取每個VBR塊的比特數。
• 陣列(3), Char6 (4), Blob (5): [編碼:3]
  • Char6錶示一個6比特值，將[a-zA-Z0-9-_]空間映射到數字0...63。LLVM大概是把它作為標識符的簡明編碼，當標識符可以安全地規範化為拉丁字母數字字符串時。
  • Blob錶示一個8字節的blob值，它的具體形式是[count:VBR6, <align32bits>, b0:8, b1:8, ..., <align32bits>]。每個DEFINE_ABBREV只能有一個Blob操作數，而且必須是操作數列錶中的最後一個操作數。
  • Array是一種複雜的情况。和Blob一樣，Array在每個DEFINE_ABBREV中只能出現一次。與Blob不同，Array必須是操作數列錶中的倒數第二比特。為了完成解析，Array竊取了列錶中最後一個操作數，並將其作為自己的元素類型。不是所有的操作數都是Array的有效元素類型；特別是只有Fixed、VBR和Char6是有效的。這（很幸運）意味著嵌套數組和blobs數組不能被天真地用比特流格式錶示4。

注意，編碼形式0、6和7沒有被定義。LLVM可能會在未來的版本中增加新的編碼形式，但目前的解析器在遇到這些編碼形式時可能會出錯5。

當完全解析後，每個DEFINE_ABBREV都准確地告訴我們如何解析使用它的任何縮寫記錄。例如，考慮下面這個符號化的DEFINE_ABBREV。

[DEFINE_ABBREV, 0b00010, 0b1, 0b00001000, 0b0, 0b010, 0b01110]
複制代碼

破解了。

• 我們有兩個縮寫操作數（0b00010）。
  • 我們的第一個操作數是一個字面操作數（0b1），值為8（0b00001000）。
    • 因為它是第一個操作數，我們把它當作記錄代碼。任何使用這個縮寫定義的記錄都會有一個86的代碼。
  • 我們的第二個操作數是一個編碼的操作數（0b0），形式為VBR（2，0b010
    • VBR形式總是需要一個額外的值，在這個例子中是14（0b01110），所以我們的VBR是一個VBR14。我們為這個這個操作數解析的任何具體字段都會被解析為VBR14。

為了理解這個DEFINE_ABBREV與一個實際的縮寫記錄的關系，我們假設它的縮寫ID是16，當前的縮寫ID寬度是6，那麼，下面的比特串。

[0b010000, 0b00000011111111]
複制代碼

解析為。

• 讀取縮寫ID：0b010000映射到我們的DEFINE_ABBREV。
  • 開始進行縮寫解析。
• 第一個操作數是Literal(8)。
  • 第二個操作數是VBR(14)；解析為0b000000111111(0xff)。

結束解析的結果是Record(code: 8, fields: [0x8, 0xff])。 ...在瑣碎的情况下，相當於每條記錄只有20比特，而在UNABBREV_RECORD錶格中超過24比特7。

DEFINE_ABBREV和縮寫記錄很複雜! 但是大部分的複雜性是在概念上，而不是在實現上：在引擎蓋下，它們使用與比特流其他部分完全相同的基元（VBRs和固定寬度的字段）。唯一的複雜性是在轉接方面。

範圍規則和BLOCKINFO

在談及縮寫定義時，我忽略了一個重要的細節：將定義的縮寫ID實際映射到其相應的縮寫定義。這就是比特流的範圍規則發揮作用的地方。

簡而言之，决定一個縮寫記錄被映射到哪個DEFINE_ABBREV的縮寫ID的計算方式如下。

• 在一個新塊的開始，我們從縮寫ID 4（即第一個應用定義的縮寫ID）開始。
• 如果新區塊有任何通過BLOCKINFO注册的DEFINE_ABBREV，我們從這些開始。例如，如果一個ID為17的新塊在BLOCKINFO中有三個DEFINE_ABBREV，這些DEFINE_ABBREV分別成為縮寫ID為4、5和6。
• 最後，我們添加任何出現在塊本身的DEFINE_ABBREV。這些只在任何BLOCKINFO定義之後注册。

唯一的其他範圍規則是範圍封閉：為一個塊定義的縮寫（和縮寫ID）只適用於該塊--它的父塊和子塊都不能使用同一個縮寫定義列錶。換句話說：每個區塊必須計算它自己的有效縮寫定義集（以及它們的ID）。

哦，但是等等：有一個稍微難看的例外。BLOCKINFO本身。當在BLOCKINFO中，DEFINE_ABBREV並不適用於BLOCKINFO塊本身；相反，它適用於最後由特殊的SETBID記錄設置的哪個塊的ID。這意味著我們必須使用一個小的狀態機來收集BLOCKINFO塊所提供的縮寫定義。

(BLOCKINFO塊中還有其他記錄，但SETBID和DEFINE_ABBREV是目前正確的比特流解析中唯一需要的記錄)。

比特流狀態機

現在我們知道了如何解釋單個記錄並將縮寫定義與縮寫記錄形式適當地聯系起來，我們可以考慮實際解析整個比特流的總體任務。

在研究我自己的比特流解析器時，我發現把比特流看成一個有3個頂級內部狀態的狀態機是很有用的。

• 一個進入底層比特流的遊標C。
• 一個範圍棧S，它包含與當前塊/塊外範圍有關的所有信息。
  • 當前的縮寫ID寬度（S.top.abbrev_width）。
  • 當前的塊ID（S.top.block_id）（如果我們剛剛開始解析，則為無）。
  • BLOCKINFO塊當前所指的塊ID（S.top.blockinfo_block_id）（如果我們不在BLOCKINFO塊中，則為無）。
  • 任何對當前範圍有效的縮寫定義（S.top.abbrevs）。
• 一個block_id -> [abbrev_definition]的blockinfo映射B，它包含了到目前為止遇到的所有BLOCKINFO定義的縮寫定義。

鑒於這種狀態，我們可以定義比特流解析器的初始化機制。

1. 在我們第一次解析之前，把一個初始範圍推到S上。

 { abbrev_width: 2, block_id: None, blockinfo_block_id: None, abbrevs: [] }
複制代碼

2. 用S.top.abbrev_width比特來推進C。產生的值是第一個縮寫ID，而且必須是Enter_SUBBBLOCK；任何其他的ID都代錶無效的狀態。

使用ENTER_SUBBBLOCK格式來填充一個新的範圍，並把它推到S上。

 [blockid:VBR8, newabbrevlen:VBR4, <align32bits>, blocklen:32]
複制代碼

特別是，新的作用域包含。

 { abbrev_width: newabbrevlen, block_id: Some(blockid), blockinfo_block_id: None, abbrevs: [] }
複制代碼

然後，主要的推進機制。

1. 用B中與S.top.block_id相匹配的任何縮寫定義填充當前範圍的S.top.abbrevs。

2. 如果我們在一個 BLOCKINFO 塊中，使用 BLOCKINFO 特定的狀態機來（進一步）填充 B8。

3. 通過S.top.abbrev_width前進。

• 如果我們的下一個條目是一條記錄，用適當的策略（縮寫或不縮寫）來解析它。轉到3。

• 如果我們的下一個條目是一個新的塊（Enter_SUBBLOCK），就像我們在初始化階段所做的那樣，填充一個新的範圍並將其推送到S上。轉到1。

• 如果我們的下一個條目是一個塊的結束（END_BLOCK），彈出當前作用域的頂部。轉到3。

大致上是可視化的（忽略了作用域狀態管理和BLOCKINFO）。

把它放在一起

在這裏，我談一下實際的實現。據我所知，這只是第三個公開的LLVM比特流解析器，也是第二個完全獨立於LLVM代碼庫的實現（另一個是Galois的llvm-pretty-bc-parser）9。

我已經在一個新的Rust庫中完成了上述所有工作：llvm-bitstream。

今天你可以通過構建它所附帶的dump-bitstream示例程序來嘗試一下。

$ git clone https://github.com/woodruffw/mollusc && cd mollusc
$ cargo build --examples
$ cargo run --example dump-bitstream some-input.bc
複制代碼

得到的結果是這樣的（摘錄）。

Entered bitstream; magic: 0xDEC04342
BLOCK 13 {
RECORD { code: 1, values: [Array([Char6(37), Char6(37), Char6(47), Char6(38), Char6(53), Char6(52), Char6(62), Char6(52), Char6(62), Char6(52)])] }
RECORD { code: 2, values: [Unsigned(0)] }
}
BLOCK 8 {
RECORD { code: 1, values: [Unsigned(2)] }
BLOCK 17 {
RECORD { code: 1, values: [Unsigned(6)] }
RECORD { code: 7, values: [Unsigned(32)] }
RECORD { code: 21, values: [Unsigned(0), Array([Unsigned(0), Unsigned(0), Unsigned(0)])] }
RECORD { code: 8, values: [Unsigned(1), Unsigned(0)] }
RECORD { code: 16, values: [] }
RECORD { code: 8, values: [Unsigned(0), Unsigned(0)] }
RECORD { code: 2, values: [] }
}
... snip ...
複制代碼

目前的輸出並不漂亮或有用，但它展示了流本身的完整消費，包括BLOCKINFO塊的內部解釋和縮寫的處理。這些解析細節並沒有出現在公共API中，這意味著用戶在消費比特流時不需要擔心這些細節--所有的塊和記錄都出現在其額外的比特錶示之上，防止任何意外的依賴比特流發射器的特定布局决定。所有這些只需要大約600行的Rust!

從這裏開始，有大量的工作要做。

• llvm-bitstream發出的記錄從根本上說是與內容和上下文無關的，這意味著它們本身並不了解它們是什麼（一個函數，一個基本塊，等等）。為了達到這個目的，還需要另一個更高層次的庫，這個庫將把各個比特流塊和記錄映射到LLVM的IR中各個特性的具體的、專門的結構上。

• 同樣地，比特流中的其他非IR特征也需要被映射。這些包括其他包含重要元數據、調試信息和字符串錶的頂級比特流塊。

• 測試。LLVM的IR很龐大，可能還有一些我沒有考慮到的邊緣情况。除了對單個分析器功能的單元測試外，有兩個全面的測試策略是合理的。

  • 針對llvm-canalyzer --dump的輸出進行等效測試，它發出的是一種偽XML格式，應該很容易複制。

  • 針對llvm-stress生成的、用llvm-as轉換為比特流的隨機LLVM IR進行烟熏測試。

下一步：上述每一項。請關注本系列的另一篇文章，可能在下個月！"。

---

1. 這並不完全正確，因為縮寫記錄指定了更高層次的語義和結構信息（比如當某個字段是Char6而不是6比特固定寬度的整數）。但這對於編寫一個正確的比特流解析器來說實際上是不必要的；它只是告訴我們關於最終預期的記錄結構的一些情况。

2. 換句話說：在一個特定的比特流中，塊ID #8總是指同一個 "種類 "的塊，但記錄代碼#4將指不同種類的記錄，這取决於包圍塊的ID。

3. 這是LLVM的比特流格式在概念上非常密集的幾個地方之一，可以說收獲不大。

4. 另一個比特流格式非常複雜的地方。為什麼數組操作數要 "偷 "其後面的操作數，而不是使用另一種編碼形式來嵌入操作數本身？我想LLVM的開發者這樣做是有原因的，但是當我寫解析器的時候，它把我搞得暈頭轉向。

5. 一個很好的例子：如果簽名的VBR有自己的編碼，那就太好了，因為這將使它們在記錄中的使用實際上是自我描述的，而不是知道某個區塊中的特定記錄代碼恰好使用它們而不是 "正常 "的VBR。就目前而言，最終負責映射到IR對象的代碼將需要對這些進行特殊處理。但是，我相信有一個很好的曆史或工程原因，為什麼比特流格式不包括這個。

6. 這也是針對具體環境的：8的代碼在一個塊ID中意味著什麼，在另一個塊ID中又意味著什麼。

7. UNABBREV_RECORD形式將是6比特代碼，6比特操作數，然後為每個具體操作數提供多個6比特VBR塊（因為我們不能使用最佳的14比特VBR形式）。在天真的情况下，我們希望每條記錄大約有24到30比特，這取决於值的分布。

8. 就我所知，沒有規則反對一個比特流有多個BLOCKINFO塊。我想不出你為什麼要這樣做，但它似乎並不被禁止，而且有很好的定義語義（縮寫大概是按照訪問順序插入的）。

9. 我很想用這個實現作為對照，但我的Haskell還遠遠不够好。

---

www.deepl.com 翻譯