使用遗传算法在 RyuJIT 中进行寄存器优化

使用遗传算法优化 RyuJIT 中的寄存器分配

遗传算法擅长在搜索空间巨大的问题中找到反直觉的解决方案——例如，优化 RyuJIT 编译器中寄存器分配的启发式顺序。与其采用固定的空闲和占用寄存器选择序列，.NET 团队的研究人员通过实验发现了一种更高效的顺序，能够减少“热点”循环中的溢出并提升 PerfScore。

固定启发式顺序的问题

RyuJIT 中的线性扫描寄存器分配（LSRA）算法在方法编译期间使用 17 个启发式规则来选择寄存器。其中前 13 个适用于空闲寄存器，后 4 个适用于占用寄存器。默认情况下，顺序是严格固定的：ABCDEFGHIJKLMNOPQ。这种方法可能并非最优：如果空闲寄存器被循环外的变量耗尽，那么在循环内部就会反复从占用寄存器中溢出值，导致代码体积膨胀并损害性能。

真实世界示例：在某个基准测试中，循环内的所有变量都使用了同一个寄存器，导致持续的溢出/重载操作。这并非寄存器不足所致，而是因为启发式总是优先选择空闲寄存器，即使它们并非长期的最佳选择。

重构 LSRA 以支持动态顺序

为了测试备选序列，开发者进行了以下改动：

• 将每个启发式移入独立的带有 __forceinline 属性的方法中，以避免开销。
• 创建哈希表，将符号（A–Q）映射到对应方法的指针。
• 引入环境变量 COMPlus_JitLsraOrdering，它接受一个由 17 个唯一符号组成的字符串来定义启发式顺序。

现在，你可以使用任意组合运行 JIT，例如：

set COMPlus_JitLsraOrdering=PEHDCGAIJNLKOBFMQ

这允许你先应用占用寄存器的启发式（例如 P 表示 PREV_REG_OPT），然后是空闲寄存器的，从而可能为关键代码段保留空闲寄存器。

使用 PerfScore 衡量效果

PerfScore 用于评估寄存器分配质量——它是生成代码执行成本的加权分数，考虑了指令延迟和吞吐量。它对溢出/填充操作（mov [rsp], reg / mov reg, [rsp]）特别敏感，尤其是在循环中。

superpmi 工具会比较两个版本的 clrjit.dll 在以下指标上的表现：

• CodeSize — 总机器码大小
• InstructionCount — 指令数量
• PerfScore — 主要目标指标

优化目标是最小化 PerfScore。但搜索空间巨大：17! ≈ 3.56 × 10¹⁴ 种可能排列。穷举搜索不可能，即使在集群上也行不通。

应用遗传算法

遗传算法（GA）非常适合此类问题：

• 染色体：由 17 个唯一符号（A–Q）组成的字符串，定义启发式顺序。
• 适应度函数：一组测试构建的平均 PerfScore 负值（PerfScore 越低，适应度越高）。
• 交叉算子：基于顺序的交叉（例如 PMX），保持符号唯一性。
• 变异：随机交换两个位置。

算法迭代流程如下：

• 初始化随机种群（例如 100 个染色体）。
• 使用 superpmi 为每个个体计算适应度。
• 选择顶级亲本（锦标赛或轮盘赌选择）。
• 通过交叉和变异生成后代。
• 更新种群；重复直至收敛。

结果与局限性

实验显示某些排列可将整体 PerfScore 比默认值降低 0.5–1.2%。最大收益出现在具有嵌套循环和大量临时变量的方法中。

不过，请注意：

• 改进并非通用的：某种顺序可能有助于某些方法，却损害其他方法。
• GA 自身开销很高：需要数千次 superpmi 运行。
• 最优顺序取决于架构（x64 与 Arm64）和工作负载特征。

关键要点

• 固定 LSRA 启发式顺序在真实场景中可能并非最优。
• COMPlus_JitLsraOrdering 允许无需修改源代码即可调整顺序。
• 遗传算法在阶乘复杂度搜索空间中大放异彩。
• PerfScore 是评估寄存器分配质量的可靠指标。
• 即使不到 1% 的 PerfScore 降低，在高吞吐系统中也意义重大。

— Editorial Team