PyPy 的汇编器后端¶

2016 年关于 PyPy JIT 中汇编器后端组织的草稿笔记¶

输入：指令的线性序列，称为“跟踪”。

跟踪是 SSA 形式的指令序列。大多数指令对应于一个或几个 CPU 级指令。有一些元指令，例如label 和调试内容。所有分支都使用保护来完成，保护是检查条件是否为真并在不为真的情况下退出跟踪的指令。失败的保护稍后可以添加一个新的跟踪，称为“桥”。修补的保护成为一个直接的Jcond 指令，跳转到桥，没有间接寻址，没有寄存器溢出等。

跟踪以return 或jump to label 结束。目标标签要么在同一个跟踪中，要么在某个旧的跟踪中。由于历史原因，我们将“循环”称为不是桥的跟踪。我们生成的机器代码被组织成一个树林；树的树干是“循环”，分支都是桥（从树干或另一个分支分支出来）。

每个以jump to label 结束的树干或分支也可以目标另一个树的标签。
汇编循环或分支的整个过程基本上是单线程的，因此没有同步问题（包括修补旧的生成指令）。
生成的汇编程序在 %rbp 中有一个“帧”，它实际上根本不在堆栈上，而是一个 GC 对象（称为“jitframe”）。溢出转到那里。
保护是Jcond 到一小段生成的代码，该代码基本上是在堆栈上推送几个常量，然后跳转到通用保护恢复代码。该代码会将寄存器保存到 jitframe 中，然后退出整个生成函数。该生成函数的调用者检查它是如何完成的：如果它通过命中保护完成，则调用者负责调用“黑洞解释器”。这是前端的一部分，它从失败的保护中恢复并完成运行框架（包括可能再次跳转到生成的汇编程序）。

关于 JIT 过程的详细信息

前端和优化过程
重写（包括与 gc 相关的转换以及简化）
汇编器生成

前端和优化过程¶

此处未详细讨论。这使用某种意义上“高级”的指令集生成循环和桥：它包含诸如“new”/“new_array”和“setfield”/“setarrayitem”/“setinteriorfield”之类的指令，这些指令描述了将值存储在结构或数组的精确字段中的操作。例如，“setfield”操作可能隐式地需要一个 GC 写屏障。这是我们发送到下一步的高级跟踪。

重写¶

一个主要但并非完全独立于 CPU 的阶段：降低一些指令。例如，“new”的变体被降低到“malloc”和几个“gc_store”：它增加 GC 的指针，然后显式地设置新分配的结构中的几个字段。如果需要，“setfield”将替换为“cond_gc_wb_call”（对写屏障的条件调用），然后是“gc_store”。

“gc_store”指令可以在单个 MOV 汇编指令中编码，但不像 MOV 那样灵活。地址始终指定为“某些 GC 指针 + 偏移量”。我们没有 GC 对象的内部指针的概念。

不同的指令“gc_store_indexed”提供了其他操作数，可以使用诸如[rax+8*rcx+24] 之类的形式映射到单个 MOV 指令。

其他一些复杂指令传递到后端，后端必须处理它们：例如，GC 中的“卡标记”。（在数组内部写入对象指针需要稍后遍历整个数组以查找“年轻”的引用。与其这样，我们为每 128 个条目的范围翻转一个位。这是一种常见的 GC 优化。）设置 GC 对象的卡位需要一系列汇编指令，这些指令过分依赖于目标 CPU 而无法在此处明确表示（此外，它包含一些分支，这些分支难以在此级别表达）。

汇编¶

没有花哨的代码生成技术，但贪婪的前向传递试图避免一些陷阱

处理指令¶

逐个（向前方向）。每个指令都要求寄存器分配器确保某些参数位于寄存器中（而不是在 jitframe 中）；要求一个寄存器将结果放入其中；并要求额外的暂存寄存器，这些寄存器将在指令结束时释放。布尔变量有一种特殊情况：它们存储在条件代码标志中，而不是作为 0/1 值具体化。（除了在它们仅由下一个guard_false 或guard_true 使用然后被遗忘的常见情况下，它们稍后会具体化。）
指令参数根据需要加载到寄存器中。这使得后端非常容易编写，但会导致一些糟糕的决策。

线性扫描寄存器分配¶

虽然我们始终考虑的是线性跟踪，但我们没有使用高级的寄存器分配技术：我们在后端生成汇编程序时进行前向、按需分配。当它请求一个寄存器来存储某个值时，我们给它任何空闲的寄存器，而无需考虑稍后将如何处理它。我们计算所有变量的寿命，但仅在选择要溢出的寄存器时使用它（我们溢出寿命最长的变量）。

这在某种程度上有效，因为它与早期的优化过程很好地集成在一起。循环由优化过程展开一次以允许更强大的优化——优化过程本身是获益最多的位置，但它在此处的汇编过程中也有好处。这些是

第一次剥离在第一次使用时初始化寄存器绑定。
这导致跟踪循环的寄存器已分配。
以及退出桥时分配的寄存器

[尝试更好地分配寄存器以匹配 ABI（在当前状态下好处很小或没有好处）]

更复杂的映射¶

一些指令生成更复杂的代码。这些要么是，要么是两者兼而有之

生成一些本地控制流的复杂指令，例如“cond_gc_wb_call”（用于写屏障），“call_assembler”（调用后跟一些检查）。
调用自定义汇编程序帮助程序的指令，例如写屏障的慢速路径或分配的慢速路径。这些慢速路径通常也会生成，因此我们不受常用调用约定的约束。

GC 指针¶

在大多数 CALL 指令周围，我们需要记录 GC 指针所在位置的描述（寄存器和堆栈帧）。如果 CALL 调用垃圾回收，则需要此信息。GC 指针可能会移动；寄存器和堆栈帧中的指针由 GC 更新。这就是我们没有显式内部指针的原因。

GC 指针可以作为跟踪中的常量出现。我们正在忙于将其更改为使用常量表和MOV REG, (%RIP+offset)。“表”中的“常量”实际上由 GC 更新，如果对象移动。

向量化¶

开发的优化以使用 SIMD 指令进行跟踪循环。主要思想是将其用作微 numpy 的优化。它在已优化的跟踪上执行多个过程。

简要解释：它为展开的跟踪循环构建依赖关系，收集可以并行执行的操作对/包，最后安排操作。

它为代码库添加了什么

可以构建依赖项
保护的代码移动以放松依赖项
调度程序重新排序跟踪
数组边界检查删除（特别是对于展开的跟踪）

它能做什么

转换向量循环（逐元素操作）
累加（reduce([…],operator,0)）。要求操作是关联的和可交换的
SSE 4.1 作为“向量后端”

我们不¶

保留跟踪数据以重新优化跟踪树。（一旦编译跟踪，就会保留最少的数据。）这是以下结果的原因之一（前端还有其他原因）：JIT 编译具有两个常见路径的小循环最终会汇编成一个“循环”和一个桥，并且桥后路径效率稍低。这主要是因为这个桥是在两个约束下汇编的：输入寄存器是固定的（来自保护），输出寄存器是固定的（来自跳转目标）；通常这两组固定寄存器是不同的，需要进行复制。
我们不连接跟踪尾部：我们只汇编树。
我们不做任何重新排序（无论是跟踪指令还是单个汇编指令）
我们不做任何仅对后端有意义且不容易在更高层次表达的跨指令优化。我确定有很多这样的例子，例如在将持续多个指令的寄存器中加载一个大常量；从循环中移出某些指令的一部分，例如地址计算；等等等等。
我想到的其他优化机会：查看函数序言/结语；查看桥开始时的开销（很小但非零）。还要检查保护的实现方式是否合理。此外，我们生成大量的汇编指令序列，其中包含大量几乎从不遵循的Jcond；那里有任何优化机会吗？（如果发生变化，它们都将向前发展。）理论上我们也可以用段错误上的信号处理程序替换其中的一些（例如guard_nonnull_class）。

GCC 或 LLVM 后端？¶

至少为了比较，我们想要一个使用 GCC 或 LLVM 发射代码的 JIT 后端（无论需要多长时间）。但是，将保护（guards）合理地映射到 C 语言或 LLVM IR 非常困难。问题在于：(1) 我们有很多保护，我们希望避免出现许多路径，每条路径都执行完整保存所有仍然存活的局部变量的操作；(2) 当从保护编译桥接时，很难修补保护；(3) 像 CALL 这样的指令需要公开作为 GC 指针的局部变量；CALL_MAY_FORCE 需要公开所有局部变量，以便可选地离线重建解释器状态。