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

原文作者：blog.yossarian.net

发布时间：2021年8月10日

前言

在上一篇文章中，我对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位流，我们需要处理容器格式的三个离散方面。

单个记录可以出现的格式。
用于确定如何解析单个记录的范围规则。
解析器的状态机和推进机制。

让我们逐一来做。

记录格式

如上所述：所有的记录都以一个缩写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定义的缩写定义。

鉴于这种状态，我们可以定义比特流解析器的初始化机制。

在我们第一次解析之前，把一个初始范围推到S上。

 { abbrev_width: 2, block_id: None, blockinfo_block_id: None, abbrevs: [] }
复制代码

用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: [] }

复制代码

然后，主要的推进机制。

用B中与S.top.block_id相匹配的任何缩写定义填充当前范围的S.top.abbrevs。
如果我们在一个 BLOCKINFO 块中，使用 BLOCKINFO 特定的状态机来（进一步）填充 B8。
通过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进行烟熏测试。

下一步：上述每一项。请关注本系列的另一篇文章，可能在下个月！”。

这并不完全正确，因为缩写记录指定了更高层次的语义和结构信息（比如当某个字段是Char6而不是6位固定宽度的整数）。但这对于编写一个正确的比特流解析器来说实际上是不必要的；它只是告诉我们关于最终预期的记录结构的一些情况。
换句话说：在一个特定的比特流中，块ID #8总是指同一个 “种类 “的块，但记录代码#4将指不同种类的记录，这取决于包围块的ID。
这是LLVM的比特流格式在概念上非常密集的几个地方之一，可以说收获不大。
另一个比特流格式非常复杂的地方。为什么数组操作数要 “偷 “其后面的操作数，而不是使用另一种编码形式来嵌入操作数本身？我想LLVM的开发者这样做是有原因的，但是当我写解析器的时候，它把我搞得晕头转向。
一个很好的例子：如果签名的VBR有自己的编码，那就太好了，因为这将使它们在记录中的使用实际上是自我描述的，而不是知道某个区块中的特定记录代码恰好使用它们而不是 “正常 “的VBR。就目前而言，最终负责映射到IR对象的代码将需要对这些进行特殊处理。但是，我相信有一个很好的历史或工程原因，为什么比特流格式不包括这个。
这也是针对具体环境的：8的代码在一个块ID中意味着什么，在另一个块ID中又意味着什么。
UNABBREV_RECORD形式将是6位代码，6位操作数，然后为每个具体操作数提供多个6位VBR块（因为我们不能使用最佳的14位VBR形式）。在天真的情况下，我们希望每条记录大约有24到30位，这取决于值的分布。
就我所知，没有规则反对一个比特流有多个BLOCKINFO块。我想不出你为什么要这样做，但它似乎并不被禁止，而且有很好的定义语义（缩写大概是按照访问顺序插入的）。
我很想用这个实现作为对照，但我的Haskell还远远不够好。