Lunacy - 具备惰性基本块版本化与JIT的Lua 5.1解释器

# Lunacy | Red Vice 来源: https://redvice.org/2026/lunacy/ ## 懒惰的美德 Lunacy (https://github.com/chc4/lunacy) 是一个我作为 Rust 业余项目一直在开发的 Lua 5.1 解释器。与普通的 Lua 解释器业余项目不同，Lunacy 通过**惰性基本块版本化** (https://arxiv.org/abs/1411.0352) (LBBV) 对字节码操作进行类型特化，并且还包含一个即时编译器。LBBV 是一种相当酷的编译技术，源于 Maxime Chevalier-Boisvert 在蒙特利尔大学的研究，最终在她关于开发 JavaScript JIT 编译器 Higgs 的[博士论文] (https://pointersgonewild.com/2022/05/23/minimalism-in-programming-language-design/phdthesis.pdf) 中达到顶峰。对我而言至关重要的一点是，她的方法非常注重简单性：LBBV 的目标是成为一种有效的编译策略，只需一个博士生在合理的时间内即可实现，或者一个工程师作为业余项目来实现。原始的 LBBV 论文非常易于理解，我强烈推荐阅读。简而言之，它能够优化字节码操作，例如 `ADD`（朴素实现下需要根据操作数类型进行分支判断，以确定是两个数字相加还是两个字符串相加等）。每当操作要检查操作数的类型并判断是否匹配某类型时，可以根据基本块的**特化上下文**静态地判定通过或不通过。如果上下文**不知道**操作数的类型，那么无需保守地回退到能够处理任何值的动态操作，而是可以将编译挂起到一个 thunk（挂起执行体）：该 thunk 最终会在运行时被执行命中时触发，此时你可以继续编译，此时上下文已填充了值在运行时的类型——该类型被提升为静态类型，并由一个运行时检查来保证后续执行同一代码路径时使用相同的类型。在检查失败的情况下，你可以挂起另一个 thunk，该 thunk 将为下一个观察到的运行时类型特化该操作。这非常强大！最终结果是，你拥有一些基本块，它们似乎神奇地只包含实际运行时观察到的值类型的类型保护；对于循环来说，会“免费”展开一次迭代（包含所有类型保护），然后在热循环内部完全具有已知类型（因为该块达到了循环头特化上下文的固定点，因此重复使用该块形成循环）。因为你拥有针对基于观察到的运行时信息的静态上下文进行特化的基本块这个强大原语，你可以将任何你想要的信息塞入静态上下文，并且总能对投机信息的值有一个正确的“猜测”。而且，如果由于任何原因最终生成了太多块，你可以回退到运行通用代码，而不是发生指数级的块爆炸。 Lunacy IR for sum（求和） LBBV 论文 IR for sum（求和） > Lunacy 和 Higgs 针对 `sum` 的特化块对比。注意内部循环体（块 `7`）最终对累加器和循环归纳变量使用了完全特化的 `ADD` 操作。Lunacy 没有做小整数优化，因此没有溢出检查。 Lunacy 与 Higgs 有一些不同之处。首先，Higgs 是**纯粹的** JIT：它没有解释器，立即将所有字节码操作直接编译为汇编。而 Lunacy 则是先实现解释器，再实现 JIT：字节码操作被实现为 Rust 协程，这些协程会产生效应。这些效应可能是诸如“对栈槽 X 的类型为 Y 进行保护”之类，这些效应会以“槽匹配/不匹配保护”等结果恢复——并且与 LBBV 类似，如果类型当前未知，我们则通过闭包将协程挂起到一个 thunk 内部。它也可能产生诸如“将操作数 A 和 B 相加”的效应，这种效应可以这样实现：它只关心如何相加数字，因为协程只有在所需的保护匹配时才会到达该产出点。运行时行为被发射为独立的残差操作，与实际的 Lua 字节码操作分开；后者被实现为在编译时驱动的协程。为了避免为每种操作数类型的组合等定义和实现运行时行为，Lunacy 还使用了[闭包生成] (https://www.iro.umontreal.ca/~feeley/papers/FeeleyLapalmeCL87.pdf) 解释器：复杂的运行时行为（例如两个数字相加）改为由闭包实现，该闭包捕获字节码操作数（例如它使用的栈槽索引），在运行时我们执行该闭包以执行操作。解释器重复执行编译块后得到的残差操作——通过运行所有用于 Lua 字节码的协程。这种方法使得 Lunacy 中的字节码协程非常容易实现。一个操作的所有行为（包括不同的 `Residual::Exec` 变体）都位于单个协程中，该协程通过产生的效应混合了静态编译部分，并通过可以捕获任意静态信息的闭包混合了运行时执行部分。因为 Rust 协程甚至实现了 `Clone`，当我们将协程挂起到一个 thunk 中以便从运行时行为中发现额外信息时，我们甚至可以将同一个协程在相同产出点挂起的克隆推入失败情形——本质上是对其进行分支，每个分支独立地恢复执行，以使用不同的观察类型编译操作和块的剩余部分。解释器本身非常小且简单，因为它只需要处理一小部分简单的残差操作。这种残差方案也使得实现解释器的 JIT 端变得非常容易，这也是我选择使用闭包生成的重要原因之一：因为我们的残差操作集非常小，仅限于类型保护、执行闭包或执行 thunk（本身也是一个闭包）等，对于 JIT 我们只需处理如何编译同样那少量残差操作。无需为所有字节码操作维护第二套汇编实现，我们可以在 JIT 中发射对闭包函数指针地址的静态调用，这关键地消除了动态分发和其他使现代乱序处理器性能下降的因素。与此同时，剩余的残差操作（如运行时类型保护）我们可以用大约 4 条指令的汇编实现为原生分支，这些分支也可以获得其自己的分支预测器条目。实际的 JIT 很小，主要由一个 `match` 中的一些 DynASM-rs (https://github.com/CensoredUsername/dynasm-rs) 汇编组成。因为 Lunacy 是一个模板 JIT，其中大多数操作都是函数调用，它不做任何寄存器分配。它只是将解释器状态固定到一个寄存器中，以便重复移入闭包调用的函数参数 ABI 中。然而，由于闭包调用 ABI 保留了一些寄存器，这为将来使用这些保留寄存器进行类似于[复制并修补] (https://arxiv.org/abs/2011.13127) 风格的寄存器窗口操作或使用多个不同闭包副本（这些闭包期望参数位于我们可以在 JIT 发射期间选择的寄存器中）留下了机会。 与立即对所有代码进行 JIT 编译的 Higgs 不同，我们只在块达到热阈值（由于执行次数足够多）后才触发 JIT。这意味着我们将强制所有执行路径上的 thunk；而 Higgs 则不同：Lunacy 目前根本不使 JIT 代码失效或修改它，这对我来说更容易推理，原因就在于此。因为解释器和 JIT 都在为块运行相同的残差操作，所以从 JIT 回退到解释器非常容易：JIT 回退处的 PC 与解释器应继续执行的 PC 相同。在触发 JIT 编译时尚未被强制的 thunk 通过回退到解释器来处理，解释器将正常执行该 thunk，并将其重写为跳转到新块的跳转残差：如果新块被运行足够多次，跳转到它可能再次触发 JIT 编译。将来，如果 thunk 的 JIT->解释器->JIT 转换成为瓶颈，我们可以修正回退点以使其跳转到新 JIT 编译的块。 Lunacy JIT code for sum（求和） > 针对 `sum` 的 JIT 代码。每个残差执行操作都转为了对静态地址的原生 `CALL`，并带有一个静态闭包对象指针。尽管这对 JIT 来说看起来性能很差，但它仍然比解释器快几倍！ ## 更多背景 Lunacy 不仅在特化上下文中特化栈槽的类型，还会：1) 跟踪函数值的具体函数值；2) 将表键特化为静态类型和常量偏移。第一点相当基础：就像我们可以挂起执行以发现值的运行时类型一样，我们也可以挂起执行以发现我们知道是函数的东西的函数指针，再次发射一个关于指针值符合预期的保护。我们可以对原生函数（如 `print`）和 Lua 函数都这样做：这不仅让我们在 JIT 中可以直接发射对 C 函数的原生调用，还避免了需要动态检查值并根据是原生调用还是其他情况切换行为，并且如果 Lua 调用目标也已经 JIT 编译了，则允许我们使用原生处理器栈（而不是解释器调用栈）发射对更多 JIT 代码的嵌套调用。因为我们可以使用所有现有的 LBBV 基础设施来将动态值提升为静态上下文，这实现起来出乎意料地简单。对于第二点，稍微困难一些。V8 以隐藏类的形式实现了表特化，包括形状和转换映射：表被分配一个指向形状的指针，该形状描述了表的布局和类型；然后在运行时，您可以发射一个形状保护（`if table.shape != expected: fail; success`），以便从表中以形状描述的偏移处加载值（这些值是类型化的），从而避免在 JIT 中进行哈希表查找。表根据构建顺序增量地分配形状。诸如 `local t = {} t.a = 1 t.b = 2` 之类的代码会反复地根据一系列映射转换表的形状，每个映射说明添加的每个键的下一个形状，例如 `{} -> {a: int} -> {a: int, b: int}`。但是，我不想在 Lunacy 中实现这一点。因为形状描述的是整个表的布局，这意味着任何类似继承的行为都必须编译为多态块：`Dog` 和 `Cat` 具有不同的形状指针，你只能通过实现更多逻辑（找到共同的祖先并在运行时遍历形状指针）来插入它们都是 `Animal` 的保护，并且要弄清楚何时将其作为 LBBV 的一部分（所有编译都必须增量进行，这与方法 JIT 或跟踪 JIT 不同——后者会事前同时查看多个块）似乎有风险。形状还需要在有动态键时在运行时跟踪转换映射，并且 V8 还实现了形状失效等功能，这需要能够将 JIT 栈帧迁移回解释器（本身需要发射栈映射）以处理某些情况。因为 Lua 函数环境（包含非局部变量）本身就是表，我还会遇到形状指针甚至因为不相关的键而发生转换的问题，这可能使每个函数的环境形状保护失效——仅仅因为后期添加了一个新的全局变量，就需要添加一个单独的方案来处理环境。相反，Lunacy 实现了一种更接近 LuaJIT [哈希槽特化] (http://lua-users.org/lists/lua-l/2009-11/msg00089.html) 的方案，其中静态上下文仅包含块中访问的各个键。一个仅访问 `Animal` 属性的函数将针对这些属性的哈希槽进行特化（使用首次发现的类型和偏移）；对于按照相同顺序构造、具有共享前缀键的 `Dog` 和 `Cat`，可以使用相同的特化块。同样，向环境中添加新变量不会导致现有保护失败，因为所有先前键的类型和偏移保持不变。 Lunacy IR 显示 gettable（获取表） > 针对 `local t = {} t.a = 1 print(t.a)` 的 LBBV IR。`gettable_href` 使用由 `href_init` 初始化的哈希见证索引进行 O(1) 访问，并且包含 `print` 的栈槽被特化为具体的函数指针。 我对 LuaJIT 的方案稍作修改，添加了一个运行时“哈希见证”表，该表填充了键的动态索引，而不是包含基于首次观察到的键索引的常量索引；其思想是：`animal.age` 可能即使在子类中也位于不同的索引（因为哈希表存储会根据不同数量的键而调整大小），因此在每个函数中首次看到该键时初始化偏移将保持期望的行为。哈希见证表还包含一个“表纪元”：类似于形状转换，当 Lunacy 在表上设置键并且无法通过静态信息证明值保持相同类型时，它会增加一个单调递增的纪元计数器，并且当我们初始化哈希见证条目时会保存该纪元计数器的初始值。纪元用于捕获表键失效的情况，例如 `t.a = 1; t[dynamic] = "string"; t.a + 1` 不能假设 `t.a` 仍然是字符串，我们必须发射一个保护 `if t.epoch != witness[0].epoch: bail; success` 来验证表保持不变。如果纪元增加（因为表添加了新键），我们可以执行“纪元修复”操作，该操作会全面检查值是否仍然是期望的类型，并要么在确认仍然安全后将见证纪元值更新为新的表纪元，要么使用新观察到的类型编译新块。但是，Lunacy 现在改为使用 `IndexMap` 来实现 Lua 表的哈希部分，`IndexMap` 具有基于插入顺序的稳定索引，消除了索引可能因调整大小而不稳定的问题；我可能会从见证中移除索引，并在 JIT 中直接发射常量索引，这将从表属性访问中移除一次数据相关加载，同时仅引入少量冗余块。当我转移到更好的值表示（[NaN 装箱] (https://github.com/WebKit/WebKit/blob/4335716855bb893798267c14053068e6c8ad010e/Source/JavaScriptCore/runtime/JSCJSValue.h#L390)）时，纪元方案也可能不再需要，因为那样可以在单条指令中检查值的类型，从而像纪元保护一样简单。 Lunacy IR for say（说） > 针对 `local function say(animal) print(animal.name .. " is ", animal.age, "years old") if animal.barks ~= nil then print("bowwow") end end` 的 JIT IR。尽管使用 `local dog = {name = "Fido", age = 5, barks = "a lot"}` 和 `local cat = {name = "Mittens", age = 3, meows = "sometimes"}` 调用它，但第一个 `print` 是单态的，而不是需要按形状特化。 进行表形状优化的另一个难题与别名有关。如果你有 `x.a = 1; y.a = "string"; x.a + 1`，即使你从未看到存储使 `x.a` 失效，但如果 `x == y`，那么它现在可能具有错误的类型。Lunacy 最初的做法是在每次表访问时都发射纪元保护来捕获此类别名风险；我后来发现 PyPy 做了一种“基于类型的别名优化”，你可以推断 `y.b = "string"` 无法使 `x.a` 失效。