突破 RISC-V 模拟的极限

# 突破 RISC-V 模拟的极限 来源：https://shuklaayu.sh/blog/riscv-recompiler TL;DR本文探讨了在非 RISC-V 机器上，RISC-V 程序能有多接近裸机性能。关键在于一种提前（ahead-of-time）重编译器，它用尾调用连接生成的基本块，并利用 Clang 的 `preserve_none` 调用约定将热点 guest 状态保留在宿主寄存器中。最近，我在 Axiom (https://axiom.xyz/) 开发 OpenVM (https://github.com/openvm-org/openvm)，这是一个 RISC-V 虚拟机。它运行程序，并连同输出一起生成一个简洁的密码学证明 (https://ethereum.org/zero-knowledge-proofs/)1 (https://shuklaayu.sh/blog/riscv-recompiler#user-content-fn-proof)，证明执行是正确的。在 Axiom 工作期间，证明生成已从单 CPU 扩展到 GPU 集群 (https://ethproofs.org/provers)，方法是将工作负载分布到多个节点。然而，第一步始终不变：我们仍然需要运行程序并记录其执行过程。证明阶段是令人尴尬的并行，并且能很好地随硬件扩展，而执行本质上是串行的。随着证明不断扩展，执行速度日益成为瓶颈，本文介绍的就是如何加快这一步。当我开始研究执行时，我总是回到一个简单的问题：*程序应该运行多快？*OpenVM 运行由 Rust 等常规语言编译而成的 RISC-V 程序，因此我可以将同一程序本地编译到我的机器上，并将其作为基准。在 M3 MacBook 上，原生 arm64 程序大约 100 毫秒完成，而同一个程序通过我们的解释器则需三到四秒。我预料到虚拟机会更慢，毕竟运行时必然有额外开销，但没想到会慢几个数量级。运行程序最快的方式是让开道路，让硬件直接执行。虚拟机不能简单地把程序交给硬件，因为它必须维持对执行的控制，并弥合 guest2 (https://shuklaayu.sh/blog/riscv-recompiler#user-content-fn-guest-host) 与宿主之间的鸿沟。相反，它要么解释程序，要么将程序翻译成宿主能理解的指令。本文的其余部分探讨我们能把这一思路推进多远，从基本解释器开始，逐步移除 guest 与宿主之间的开销层。 ## 解释器基线 运行 RISC-V3 (https://shuklaayu.sh/blog/riscv-recompiler#user-content-fn-rv64i) 代码的一种直接方式是使用解释器，循环执行经典的取指-译码-执行周期。问题在于 guest 指令通常很小。一次加法或移位可能只执行单个算术操作，而解释器必须取指、译码字段、在 `switch` 中选择正确的分支，并沿途维护自己的执行状态。解释器最终花费在管理指令上的时间可能比执行指令本身还多。 switch-case 取指 译码 分发 + 执行 取指 译码 分发 + 执行 示例：一条已译码的 RISC-V 指令R 型指令（如 `add rd, rs1, rs2`）的字段布局是固定的：`opcode` 标识指令的编码类别。`funct3` 和 `funct7` 字段进一步将该类别缩小到具体操作，而 `rd`、`rs1`、`rs2` 则标识所涉及的寄存器。例如，`add x5, x6, x7` 计算 `x5 = x6 + x7`，其字段填充如下： 这里 `rd`、`rs1`、`rs2` 分别指寄存器 `x5`、`x6`、`x7`。`opcode`、`funct3` 和 `funct7` 字段共同选择 `add` 操作。`sub` 指令使用相同的 `opcode` 和 `funct3`，但将 `funct7` 从 `0000000` 改为 `0100000`。 ### 提前预译码 每次执行时都对相同的指令进行译码是不必要的。程序代码通常是静态的4 (https://shuklaayu.sh/blog/riscv-recompiler#user-content-fn-fencei)，因此我们可以预先对每条指令译码一次并复用结果。这就是*预译码*。对每条指令，我们存储其行为、操作数，以及指向执行它的一个小函数（*处理器*）的指针。译码不再是热循环的一部分。剩下的工作是通过间接调用处理器指针进行分发，然后对每条指令返回解释器循环。 预译码 取指 分发 执行 取指 分发 执行 > **注意：**switch 解释器直接跳转到指令实现，而预译码解释器对每条指令都需要一次函数调用和返回。 ### 通过计算 goto 进行分发 预译码消除了译码开销。剩下的瓶颈是间接分发。每条指令仍然必须返回到共享循环，以便解释器选择接下来运行什么。经典的解决方案是*计算 goto*5 (https://shuklaayu.sh/blog/riscv-recompiler#user-content-fn-computed-goto)。每个处理器不再返回到共享循环，而是在表中查找下一个操作码的标签，并用 `goto *` 直接跳转到它。 这里的预译码表示比之前更简单。没有处理器指针，只有第一节中相同的 `Instruction`，预先译码成按 `pc / 4` 索引的数组。每个操作码都有自己的标签作为分发目标。每条指令仍然需要取指和分发，但解释器不再对每个处理器执行函数调用和返回。相反，每个处理器将控制权转移给分发序列，后者选择下一个处理器并直接跳转到它。因此，执行通过间接跳转从一个处理器移动到下一个处理器，而不是反复跨越调用-返回边界。 计算 goto 执行 取指 + 分发 执行 取指 + 分发 ### 尾调用线程化 尾调用6 (https://shuklaayu.sh/blog/riscv-recompiler#user-content-fn-tail-call) 提供了另一种将处理器连接在一起的方法，同时保持每个处理器为普通函数。处理器可以尾调用下一个处理器，而不是返回共享分发循环： 每个处理器执行其指令，将 `pc` 前移，并调用内联的 `dispatch` 辅助函数，后者找到下一个处理器并尾调用它。由于调用者此后不再运行任何代码，编译器可以将调用降级为普通跳转，而无需保留调用者的栈帧。这就是尾调用消除，它允许处理器链以恒定的栈深度无限运行。Clang 的 `musttail` (https://clang.llvm.org/docs/AttributeReference.html#musttail) 属性使这种降级成为强制性的，要么发出尾调用，要么拒绝程序。 计算 goto 和尾调用线程化是表达相同处理器到处理器控制流的两种方式。前者使用函数内部的标签，后者使用独立的函数并依赖强制尾调用。 #### 将状态保存在寄存器中 每个处理器仍然通过 `State *` 访问 `pc`，每条指令都读写它。由于这些值已经通过尾调用链传递，因此可以将它们作为函数参数传递。宿主调用约定通常将这些参数分配给寄存器7 (https://shuklaayu.sh/blog/riscv-recompiler#user-content-fn-register-access)，从而允许编译器将频繁使用的值保存在宿主寄存器中，而不是通过 `State` 反复加载和存储： 现在 `pc` 可以始终留在寄存器中，而不是每条指令都从 `State` 加载并存储回去。同样的想法也适用于其他频繁访问的解释器状态，如 `mem`。 ## 走向原生 预译码消除了重复译码，线程化分发消除了共享循环。剩下的仍然是一个解释器，每条 guest 指令在执行前都必须经过处理器。这种开销仍然使与原生执行之间存在巨大差距。由于程序在运行前已经已知，下一步是将其直接翻译成宿主能执行的东西。 ### 手写汇编后端 一个简单的提前（AOT）8 (https://shuklaayu.sh/blog/riscv-recompiler#user-content-fn-aot) 翻译器逐条指令工作。每条 RISC-V 指令被翻译成一小段宿主指令序列，生成的部分按所需的控制流拼接在一起。翻译几乎是机械式的：`add` 变成宿主加法，加载变成宿主加载，依此类推。顺序指令可以自然地贯通，跳转到固定目标变成普通的宿主跳转。运行时计算目标的跳转需要通过分发表查找。翻译器以单次线性遍历为宿主架构生成汇编，之后生成的代码只需汇编成共享对象并加载。代价是可移植性——由于指令编码是架构特定的，每个目标都需要自己的后端。实际上，翻译器是一个 switch 语句，每个 RISC-V 操作码对应一个 case，每个 case 写入相应的宿主汇编。 这从热路径中移除了剩余的解释器开销。执行不再产生处理器分发，生成的宿主指令直接运行，顺序执行自然贯通，固定跳转变成普通宿主分支。 汇编后端 执行 执行 执行 执行 执行 执行 #### 寄存器映射 剩余的解释器开销是将 guest 状态在内存和寄存器之间移动。简单的翻译器仍然像解释器一样通过 `State` 读写每个 guest 寄存器。这里适用前面用过的相同思路。执行过程中携带的值不需要存在于内存中。翻译器不必将 guest 寄存器文件保存在 `State` 内部，而是可以将频繁使用的 guest 寄存器映射到宿主寄存器，在入口处加载一次，在执行退出时写回。加载和存储移到了翻译执行的边界。在热路径内部，guest 的 `add` 变成单条宿主指令。 ### 让 Clang 作为后端 此时，翻译器实际上是在手工重新实现编译器后端。它选择宿主指令、分配寄存器，并为每个目标架构维护单独的后端。更自然的方法是用现成编译器已经理解的语言生成代码。然后翻译器可以将指令选择、寄存器分配以及其他目标特定细节留给 Clang。 #### 一个巨型函数 使用编译器最直接的方式是将整个程序做成一个函数。译码程序，将每条指令翻译成 C，将频繁使用的 guest 寄存器保留为局部变量，并用标签和 `goto` 在函数内部表示控制流。这给了编译器整个程序作为上下文。它可以跨翻译指令跟踪值，决定寄存器应放在哪里，并在生成的代码上进行优化。控制流直接在函数内部表示。直线执行贯通，固定目标变成标签，只有运行时才知道的目标才需要间接跳转表。 为什么生成 C？生成的代码最终要经过 Clang 才能变成原生指令，因此翻译器可以直接发出 LLVM IR (https://llvm.org/docs/LangRef.html)。然而，对于这个项目，C 是更有用的接口。生成的 C 仍然是普通源代码，可以使用熟悉的工具阅读、审查、diff 和调试。随着 OpenVM 在执行周围添加插桩和运行时钩子，修改起来也更容易。直接在 LLVM IR 中表达相同的更改会繁琐得多。针对 LLVM IR 可以避免额外的 C 解析步骤，但它会让生成器面对更低级、更不稳定的编译器接口。C 提供了更清晰的边界，并将后端细节留给 Clang。 对于小型程序，这使编译器对 guest 程序有广泛的可见性。寄存器分配和优化可以从入口到出口跟踪每个值，而无需在翻译区域之间设置边界。但随着程序增长，这种方法会失效。编译器能很好地处理小型函数，但包含数千或数百万行的函数会给 Clang 一个巨大的函数体去分析和优化。编译时间可能变得不切实际，而且由于所有工作都在单个函数中，无法有效地跨核心分发。 #### 一次重编译一个基本块 一次性翻译整个程序给 Clang 太多东西要分析，而一次只翻译一条指令给它的上下文又太少。基本块提供了一个有用的中间地带。基本块是单入口的直线指令最大序列。控制只能从第一条指令进入，只能从末尾离开。重编译器将每个基本块作为独立的 C 函数发出。这给了 Clang 足够的上下文来跨多条 guest 指令进行优化，同时保持每个生成的函数足够小以高效编译。例如，块 `` # pc 0x1000slli a0, t0, 13xor t0, t0, a0add a1, t0, a2 `` 变成： 重要的区别在于，编译器将整个序列视为一个整体，而不是三条独立指令。它可以将中间值保留在寄存器中，并将多个 guest 操作合并成一条宿主指令。这里，移位和异或折叠成一条 arm64 指令，带有内置的移位操作数。 ##### 识别块 给定包含指令序列的 ELF 可执行文件9 (https://shuklaayu.sh/blog/riscv-recompiler#user-content-fn-elf)，重编译器必须确定每个生成函数的起始和结束位置。它通过识别基本块并将它们连接成控制流图（CFG）来实现，其中每个节点代表一个块，每条边代表可能的控制转移。可能开始一个基本块的指令称为*块领导者*。程序入口点是领导者，任何直接分支或跳转的目标也是领导者。控制流指令之后的指令，如果执行可能贯通到它，也是领导者。分析可能通过恢复未直接编码在指令中的目标来识别额外的领导者，例如通过常量传播确定的 `jalr` 目标。 从每个领导者开始，重编译器向前译码，直到到达另一个领导者或可能重定向控制的指令（如分支、跳转、调用、返回或陷阱）。这确保每个已识别的跳转目标都位于生成函数的开头。 这个过程可能会留下可执行文本的某些部分未被发现，因为没有已知的控制流边到达它们。为确保这些区域仍能被编译，重编译器还会线性扫描剩余的文本并将其划分为块，在节边界、控制流指令之后以及遇到的任何直接目标处开始新块。 一旦指令范围已知，重编译器根据后继关系连接它们。条件分支有一个跳转后继和一个贯通后继，而直接跳转只有其目标。这些后继成为 CFG 中的边。下面的示例将这些规则应用于一个对数组求和的函数。`B_1008` 中的条件分支结束一个块并产生两个后继，而 `B_100c` 中的直接跳转形成循环回边。这些转移直接编码了它们的目标。最后的 `jalr` 从 `ra` 读取其目标，因此其目标仅在运行时已知。 01按分支切分 02连接边 03每个块发出一个函数 guest 指令按块切分