精简后端 (Bare Bones Backend) / 汇编中间表示

B3 编译器包含两种中间表示:一种是基于SSA 的高级别表示,称为 B3 IR;另一种是专注于机器细节(如寄存器)的低级别表示。这种低级别形式被称为 Air(汇编中间表示)。

Air 程序使用 Air::Code 对象表示。Code 包含一个 基本块 数组。每个基本块包含一个 Inst 数组。Air 有一个显式的控制流图:每个基本块都有前驱和后继块。执行总是从第一个基本块 (code[0]) 开始。每个块中的 Inst 按顺序执行。每个 Inst 都有一个操作码(opcode)、一些标志(flags)、一个参数数组(Args)和一个来源(origin)。操作码和标志被封装在 Kind 中,以便于一起携带。来源仅仅是一个 B3 IR Value。有些操作码将来源用于额外的元数据。这之所以可行,是因为 Air 代码总是与其生成的 B3 过程共存。

本文首先描述 Air 的设计理念。Args 的行为是 Air 执行模型的核心,这将在下一节中描述。最后一节将描述 Air 操作码的定义方式。

Air 的设计理念

B3 旨在可移植到多种 CPU。目前,它支持 x86-64 和 ARM64,这两种 CPU 彼此之间差异很大。在 B3 IR 中,我们只暴露了极少的指令集细节。B3 IR 的目标是确保 B3 值行为一致,除非替代方案会适得其反(例如指针大小、除法的边缘情况行为或调用约定自定义)。但要有效地将代码编译到不同的 CPU,编译器最终必须明确指令集细节。这就是 Air 发挥作用的地方。B3 在转换为 Air 的那一刻锁定了大多数 CPU 特定细节,并且 Air 代码不可逆地绑定到某个特定 CPU。

Air 是一种指令超集:它识别 Air 可能面向的所有 CPU 的所有指令。在其最低级别形式中,Air 仅仅是一种描述汇编指令序列的方式,这包括寄存器和直接访问堆栈等 CPU 概念。Air 也有一个更高级别的形式,其中汇编尚未经过寄存器或堆栈分配。因此,Air 也支持抽象寄存器(称为 Tmps)和抽象堆栈槽。一个 Tmp 对象可以表示未分配的临时值或一个寄存器。

作为指令超集的 Air

Air 具有可以描述我们所知道的所有 CPU 指令的语法。例如,在为 ARM64 编译时,也可以描述 x86-64 指令。Air 的客户端,例如 B3 到 Air 的降低阶段,可以选取任何 Air 操作码并询问该操作码在当前 CPU 上是否有效。它们还可以检查任何给定操作码的特定形式是否有效。这允许客户端通过遍历它们所知道的可能操作码(从它们认为最有效的操作码开始)来优化多个指令集。其中一些操作码可能只在一个 CPU 上可用,而另一些则在所有地方都可用。指令选择不需要知道哪些指令在哪些 CPU 上有效;Air 会告诉你某个指令目前是否因某种原因而无效。

Air 操作码支持重载。例如,Add32 操作码有两操作数和三操作数重载,并且这些重载有多种形式:第一个操作数可能允许或不允许是立即数,并且根据 CPU 和其他一些操作数,可能允许或不允许是内存地址。我们使用操作码重载来指代共享相同参数数量的操作码的所有形式,而操作码形式则指参数数量及其类型。一个基本的 Air 操作是 Inst::isValidForm(),它告诉客户端指令的当前形式在当前 CPU 上是否有效。这可能返回 false,原因可能是 Inst 对于任何 CPU 而言都格式不正确,或者即使它在其他某些 CPU 上可能有效,但对于当前 CPU 而言却无效。还有一个 Air::isValidForm(),即使您尚未创建 Inst,它也能回答您打算使用的形式是否有效。这允许客户端在确定当前 CPU 支持的形式之前,通过尝试不同的形式来生成 Air。

作为高级汇编的 Air

Air 不要求客户端执行寄存器或堆栈分配。Air 接受寄存器的任何地方,它也会接受 Tmp。Air 接受地址的任何地方,它也会接受堆栈槽引用。Air 代码生成包括一个寄存器分配器和一个堆栈分配器,它们将 Tmps 转换为 Regs,并将堆栈槽转换为以帧指针(或堆栈指针)为基址和某个整数偏移量的地址。即使在同时使用 Tmps 时,Air 也允许客户端直接引用寄存器,并且寄存器分配器将确保它避免破坏客户端代码已经依赖的寄存器。这之所以可能,是因为 Air 精确地建模了指令如何使用寄存器,因此总能确定 Air 代码中任何点的哪些寄存器是活跃的。

Air 的设计理念允许 B3 使用它将高级的、大部分与 CPU 无关的 SSA 过程转换为当前 CPU 的代码。Air 是一种指令超集,允许客户端考虑所有可能 CPU 上的所有可用指令,并查询这些指令的哪些形式在当前 CPU 上可用。Air 还支持 Tmps 和堆栈槽等高级概念,这使得 B3 到 Air 的降低过程能够专注于使用哪些指令,而无需担心寄存器分配或堆栈布局。

Args 和 Air 执行模型

Air 可以被认为是正交指令集。可以构造一个具有任何操作码和参数组合的 Inst。操作码决定了 Air 将对参数做什么——例如,它可能从参数中读取或写入参数。正交性意味着任何被读取的参数可以是寄存器(或 Tmp)、地址或立即数;而任何被写入的参数可以是寄存器或地址。Air 会在目标 CPU 所在的位置限制正交性。例如,Air 的目标 CPU 都不支持从内存加载源并同时将结果存储到内存的 Add32 指令。即使 x86 也不会走那么远。在创建 Inst 之前或之后,客户端都可以查询特定参数组合(例如,三个内存地址)对于给定操作码(例如,Add32)是否有效。

Air 参数使用 Arg 对象表示。Arg 可以表示以下任何汇编操作数:

Tmp
Tmp 表示寄存器或临时值。
Imm, BigImm, BitImm, 和 BitImm64
这些是各种类型的立即数。我们区分大立即数和小立即数,因为某些指令只允许在特定范围内的立即数。我们区分用于位操作的立即数和用于所有其他操作的立即数,因为 ARM 对立即数的值有不同的限制,具体取决于它们是否用于位运算。
Addr, Stack, CallArg, 和 Index
这些都是内存地址。Addr 是基址-偏移量地址,使用 Tmp 作为基址,立即数作为偏移量。StackCallArg 是抽象的堆栈偏移量。Index 是基址-索引地址,它有一对 Tmps(基址和索引)以及一个偏移量立即数和一个用于索引的缩放立即数。
RelCond, ResCond, 和 DoubleCond
这些是各种类型分支的条件码。
Special
Air 允许某些 Insts 指向额外的元数据。Special 参数类型用于此类元数据。它包含一个 Arg::Special*
WidthArg
某些特殊的 Air 操作码接受描述操作宽度的操作数。可能的值是 Width8Width16Width32Width64

Inst 的操作码与重载(即参数数量)结合,决定了 Inst 将对每个参数做什么。参数的行为归结为由操作码和重载确定的三个维度:

角色 (Role)
参数的角色是一个枚举,描述了参数访问的时间、访问方式(使用,即读取;或定义,即写入)、该访问对性能的重要性(),以及写入如何影响高位(忽略或零填充)。参数角色的时序将在下面进一步讨论。参数的性能要求用于寄存器分配优先级。热参数计入寄存器分配优先级启发式算法,而冷参数则不计。
类型 (Type)
Air 识别两种类型:GP(通用目的)和 FP(浮点)。参数也有类型。重要的是要记住,既有由操作码和重载确定的参数类型,也有参数本身的类型。有些参数是无类型的,这意味着它们可以被使用,而不管操作码/重载所需的类型如何。例如,地址是无类型的。其他参数有特定类型,如寄存器和 Tmps。除了 BigImm,立即数都是 GP 类型。
宽度 (Width)
指令影响的位数,从最低位开始。可能的值是 Width8Width16Width32Width64

参数角色的时序很重要,这引出了 Inst 的执行顺序。每个 Inst 可以被认为是执行三个步骤:

  1. 执行早期操作。
  2. 执行主要操作。
  3. 执行后期操作。

一个指令的早期操作紧接着前一个指令的后期操作发生。然而,许多 Air 分析将它们视为同时发生。例如,一个指令早期操作中的任何寄存器使用都会干扰其之前指令后期操作中的寄存器使用。所有 Air 的活跃性(liveness)和干扰(interference)分析都围绕着指令之间的栅栏桩进行推理,其中前一个指令的后期操作和下一个指令的早期操作形成一个干扰团(interference clique)。

我们来看一个简单的例子,比如带有两个参数的 Add32。假设第一个参数是内存位置,第二个参数是寄存器。Air 在大多数指令中采用 AT&T 风格将目标参数放在最后。这个 Add32 从内存中加载并将其值添加到寄存器。Air 这样写:

Add32 42(%rax), %rcx

此指令将分三步执行:

  1. %rax 中的内存地址以偏移量 42 加载值。结果存储在内部的、隐藏的 CPU 位置,供后续执行使用。即使指令稍后存储到内存并覆盖此值,Add32 仍将使用它加载的原始值。我们称之为早期使用 (early use)。同时,CPU 将加载 %rcx 的值并将其存储在隐藏的 CPU 位置。这也是一个早期使用。
  2. 将这两个值相加。将结果存储在隐藏的 CPU 位置。
  3. 将结果值零扩展并存储到 %rcx 中。这是一个带零扩展的后期定义 (late def with zero extension)。

因此,Add32 的两参数重载为其参数赋予了以下属性:

Air 可以通过使用 Inst::forEachArg(func) 操作来告诉你每个参数被赋予的角色、类型和宽度。它接受一个类型为 void(Arg&, Arg::Role, Arg::Type, Arg::Width) 的回调函数。对于我们的 Add32 示例,此回调函数将被调用两次:

  1. func(42(%rax), Use, GP, Width32)
  2. func(%rcx, UseZDef, GP, Width32)

重要的是要记住,Air 对指令作用于参数的总结并非详尽无遗。例如,如果一条指令声称使用一个地址,这会告诉你该指令将执行加载,但没有告诉你加载将如何执行。这意味着除非你确切知道使用/定义一个参数意味着什么,否则你无法执行以下转换:

即使你知道 Foo32 只使用其参数,你也不能这样做,因为 Move32 可能不会使用与 Foo32 完全相同的加载方式从地址加载。内存访问有许多维度的选项:对齐语义(如果你幸运的话,未对齐的访问运行速度快,但有时它们会忽略低位、在未对齐时触发陷阱,或在未对齐时运行超级慢,并且这种行为可能取决于操作码)、时间性和内存顺序、陷阱的确定性等。仅仅看到一条指令使用一个地址并不能告诉你将发生哪种加载,而且目前 Air 还没有能力回答此类问题。幸运的是,Air 不需要将内存访问移出指令。对临时变量、寄存器、立即数和溢出槽的使用和定义没有这些限制,因此这些参数可以在指令之间自由移动。

得益于模板特化和 C++ lambda 的使用,Air 对 Insts 的内省(introspection)通常非常快。forEachArg() 模板方法使用高效的 switch 语句排列来确定操作码和重载。如果 func 是一个 C++ lambda,我们期望 forEachArg() 会针对该 lambda 进行特化。因此,这种惯用法避免了虚派发或内存分配。

Air 支持奇特的角色,例如后期使用(late uses)和早期定义(early defs)。甚至还有 Scratch 角色,这意味着早期定义和后期使用。在 Scratch 角色中提及 Tmp 意味着该 Tmp 将被分配一个寄存器,该寄存器保证不会干扰指令中提及的任何其他寄存器。后期使用和早期定义对于补丁点(patchpoints)至关重要,补丁点可能要求传入值之一被赋予一个不干扰结果所用寄存器的寄存器。这可以通过赋予输入后期使用角色或赋予输出早期定义角色来表达。可能的角色完整列表如下:

Use
早期热使用。
ColdUse
早期冷使用。
LateUse
后期热使用。
LateColdUse
后期冷使用。
Def
后期定义。请注意,所有定义都是热的。
ZDef
带零扩展的后期定义。
UseDef
早期热使用和后期定义。
UseZDef
带零扩展的早期热使用和后期定义。
EarlyDef
早期定义。
Scratch
早期定义和后期热使用。
UseAddr
地址组件的早期热使用。

UseAddr 对于 Lea(加载有效地址)指令很有趣,它评估地址并将结果放入临时变量或寄存器。参数必须是地址,但 UseAddr 意味着我们实际上不从地址读取。请注意,以任何其他角色使用地址总是意味着地址的组件被早期热使用(即 Use)。

Air 参数是 Air 执行模型的核心。指令的早期和后期操作与参数有关,并且每个参数在早期和后期操作期间会发生什么由操作码和参数数量(即重载)决定。Air 的客户端可以创建具有任何操作码和参数组合的 Inst,然后使用 isValidForm() 查询操作码、重载和特定参数对于当前 CPU 是否有效。

定义 Air

Air 有许多操作码,并且这些操作码有许多不同的重载和形式。Air 通过 isValidForm()forEachArg() 等辅助函数,使推理所有这些操作码变得容易。它还提供了一个 Inst::generate() 函数,可以为指令生成代码,前提是它不使用任何非寄存器 Tmp 或任何抽象堆栈槽。如果手动编写用于验证、迭代和生成每种形式的代码,那将会非常麻烦。因此,Air 带有一个操作码代码生成器,它以操作码定义文件作为输入。操作码定义文件使用简单简洁的语法,允许我们一次性定义许多操作码,并将它们限制在支持它们的 CPU 类型。此外,Air 支持自定义操作码,代码生成器会发出对手写 C++ 代码的调用。本节描述操作码定义语言。

通过一个例子来理解操作码定义最为简单。我们使用 Add32 的两参数重载。

Add32 U:G:32, UZD:G:32
    Tmp, Tmp
    x86: Imm, Addr
    x86: Imm, Index
    Imm, Tmp
    x86: Addr, Tmp
    x86: Tmp, Addr
    x86: Tmp, Index

第一行定义了重载。它有两个参数。第一个参数担任 Use 角色,简写为 U。它是通用目的(general-purpose),简写为 G。它具有 32 位宽度。因此字符串为 U:G:32。类似地,UZD:G:32 意味着 UseZDefGPWidth32

接下来的几行列出了重载的可用形式。形式是可能的参数类型列表。这些使用了与上一节中 Arg 类型相同的术语,但需要注意的是,Addr 意味着 AddrStackCallArg 都将被接受。

任何行前缀 x86: 都意味着此形式仅在 x86 CPU(如 x86 或 x86-64)上可用。

Air 操作码旨在与 JavaScriptCore 现有的 MacroAssembler 配合工作。默认情况下,操作码会自动获得一个代码生成器,该生成器调用 MacroAssembler::opcodeName,其中 opcodeName 是通过将 Air 操作码名称的首字母小写而得出的。例如,Add32 变为 MacroAssembler::add32

请参阅 AirOpcode.opcodes 文件的头部,以获取 Air 操作码定义语言所使用的完整简写列表。

总结

Air 的设计围绕着 JavaScriptCore 现有的 MacroAssembler。Air 具有 Inst 对象,每个对象描述对 MacroAssembler 的某个方法调用:Inst 的操作码指示要使用的方法名称,其参数指示要传递给该方法的参数。我们使用代码生成来创建一个巨大的 switch 语句,将“反射式”的 Insts 转换为对 MacroAssembler 的实际调用。因此,我们通常只需编辑 AirOpcode.opcodes 文件,即可“添加”新的指令到 Air 中。