RyuJIT 后端 IR 去嵌入式语句改造：从树序约束到纯线性 LIR 的设计与实现
【免费下载链接】runtime.NET is a cross-platform runtime for cloud, mobile, desktop, and IoT apps.项目地址: https://gitcode.com/GitHub_Trending/runtime6/runtime
RyuJIT 是 .NET 运行时（当前仓库 runtime）中负责将中间语言（IL）编译为机器码的即时编译器（JIT）。本篇技术指南围绕设计文档 removing-embedded-statements.md 展开，深入剖析 RyuJIT 后端 IR（LIR）中"嵌入式语句（embedded statements）"这一历史性构造的缺陷，以及作者提出的"去除树序约束、走向纯线性 LIR"的完整六步改造方案。读完本文，你将理解 HIR/LIR 的排序语义、逗号节点与嵌入式语句的等价关系、rationalizer/lowering/LSRA 各阶段的线性化改造要点，并能对照当前仓库源码确认这一方案的实际落地形态。
一、背景：RyuJIT 的两种 IR 形态与排序构造
RyuJIT 的中间表示（IR）以 rationalization（理性化）和 lowering（降低）为分界，存在两种截然不同的形态：
- 前端 IR（HIR）：由导入器（importer）等前端阶段产生并操作；
- 后端 IR（LIR）：由 rationalization 与 lowering 从前端 IR 变换而来，供后端（寄存器分配、codegen）使用。
根据设计文档，两种 IR 在"基本块（basic block）内的排序构造"上存在关键差异。块内排序涉及四类构造：顶层语句（top-level statements）、树（trees）、逗号节点（comma nodes）与嵌入式语句（embedded statements）。其中后两者用于表达"在树的某个特定执行点运行、但不参与该树数据流"的任意代码（通常带有副作用）。正是这些代表形式的挑战，使得嵌入式语句难以理解且极易在变换中出错——这正是本文要解决的问题。
二、HIR 的排序语义：语句、树与逗号节点
2.1 语句与树的执行顺序
在基本块内，HIR 首先按语句（statement）排序。每条语句由一棵完成该语句计算任务的单一树（tree）组成。树的节点按照"节点树的从左到右后序访问"顺序执行，唯一的例外是带有GTF_REVERSE_OPS标志的二元运算符节点——该标志会反转其操作数子树的执行顺序。
2.2 树边既是排序边也是数据流边
因此，树中的边同时表达了两种语义：排序以及数据流图中"每个定义只有一个使用（SDSU，single-def-single-use）"的边。但存在两类例外：
- 指向存储位置定义节点的边（例如赋值运算符左侧的节点）：既不表达排序，也不表达 use-to-def 关系——位置的定义发生在父节点执行过程中，且该边不构成对某个 SDSU 临时变量的使用；
- 指向未使用值的边：仅用于排序，不构成 use-to-def 关系。
2.3 逗号节点：向树中"塞入"任意代码
未使用值边的主要来源是逗号节点（comma nodes）。HIR 使用逗号节点，专门在树的执行序列中插入"不参与其 SDSU 数据流"的任意代码。换句话说，逗号节点允许编译器把一段副作用代码挂到树的某个执行点上，而这段代码本身不贡献树的结果值。
三、LIR 的排序语义：线性穿线与嵌入式语句
与 HIR 类似，LIR 同样首先按语句排序，但每条语句由两部分组成：
- 一棵树：表达与该语句关联的计算；
- 节点的线性穿线（linear threading）：表达与该语句关联的 SDSU 数据流与计算。
线性穿线必须满足两个约束：
- 树中出现的每个节点都必须包含在线性穿线中；
- 树的所有节点在线性穿线中的相对顺序必须与 HIR 树排序的执行顺序一致。
在此之上，线性穿线中还可以出现额外的节点，即嵌入式语句（embedded statements）。嵌入式语句是"子语句"：其节点构成所属语句执行顺序中的一个连续子序列，但不参与所属语句的 SDSU 数据流（即这些节点不出现在所属语句的树中）。嵌入式语句在排序语义上与顶层语句一致，其用途与 HIR 中的逗号节点完全相同：允许编译器在语句执行过程中插入不参与其数据流的任意代码。
四、问题所在：为什么嵌入式语句难以处理
设计文档明确指出，尽管逗号节点（HIR）与嵌入式语句（LIR）用途相同，但嵌入式语句明显更难处理，原因在于：
- 不在所属语句的树中：开发者在处理 LIR 时，必须格外小心，避免在诸如代码移动（code motion）所需的分析（例如使寻址模式"contained"所需的分析）中遗漏构成嵌入式语句的节点；
- 容易违反树序约束：处理线性穿线时，稍有不慎就会破坏 LIR 线性穿线必须保持的树序约束。
这两点使得任何触碰 LIR 的变换都处于"容易出错"的状态。
五、两条候选路线与最终选择
针对嵌入式语句的操作难题，设计文档给出了两条相对清晰的解决路线：
| 方案 | 思路 | 评价 |
|---|---|---|
| A | 用"在父语句树中表示的构造"替代嵌入式语句 | 将更多概念绑进树边 |
| B | 移除树序约束，将 LIR 迁移为"仅受数据流与副作用一致性约束"的线性排序 | 与 LIR 既有发展方向一致 |
作者最终选择方案 B：让树边此后只表达节点的 SDSU 数据流，从而澄清 IR 的语义，也简化后端所需的分析。这既符合 LIR 已有的演进方向，又减少了绑定在树边上的概念数量。
六、六步实施方案及其在仓库中的落地
设计文档给出了六步改造方案。对照当前仓库源码，可以看到这些步骤已基本完整落地——当前 src/coreclr/jit 中的 LIR 已是不含嵌入式语句的纯线性结构。
第 1 步：为线性 LIR 构建操作工具链（lir.h / lir.cpp）
新 IR 形态需要配套的操作、分析、校验与显示工具，集中实现在 lir.h 与 lir.cpp 中：
LIR::Use：封装"use ↔ def"边，提供Def()（返回产生该 def 的节点）、User()（返回使用该 def 的节点）、ReplaceWith()、ReplaceWithLclVar()等接口，并支持MakeDummyUse/IsDummyUse构造与分析哑使用；LIR::ReadOnlyRange/LIR::Range：对一段连续线性节点的只读/可编辑视图，支持begin()/end()正向迭代与rbegin()/rend()反向迭代，以及InsertBefore、InsertAfter、InsertAtBeginning、InsertAtEnd、Remove、Delete、GetTreeRange等操作；LIR::AsRange(BasicBlock*)：把基本块整体视作一个可编辑的Range，是所有后端阶段访问线性 LIR 的统一入口；LIR::SeqTree/LIR::EmptyRange/LIR::InsertBeforeTerminator：把树序化成线性范围、构造空范围、在块终止符前插入范围等常用工具。
文档还明确了 LIR **校验（validation）**至少应检查的性质：
- 线性穿线无环（loop-free）；
- 所有 SDSU 临时变量（即由边表示的临时变量）确实只被使用一次；
- 所有 SDSU 临时变量的定义先于对应使用出现；
- 所有被使用的 SDSU 定义都存在于线性 IR 中。
当前 lir.h 中CheckDoublyLinkedList这样的工具正是对线性穿线链表结构的校验辅助。
第 2 步：停止在 rationalizer 中生成嵌入式语句（rationalize.cpp）
文档给出三种停止生成的途径：
- 在 rationalize 之前移除逗号节点：当时已有在建的基础设施，开发成本低，但会引入额外一趟 pass 和额外局部变量，带来吞吐量与代码质量风险；
- 改造 rationalizer，使其不产生嵌入式语句：要求 rationalizer 能同时处理 HIR 与 LIR，或在过程中直接线性化逗号节点；
- 在 rationalizer 与 lowering 之间增加一趟线性化 pass。
作者选择方案 2：不增加额外 pass（方案 3 的缺点），也不引入额外局部变量（方案 1 的缺点），在吞吐量与代码质量上最具吸引力。
从当前源码看，这一选择已经落地：rationalizer（rationalize.cpp）在执行重写（如RewriteNodeAsCall、各类硬件内建函数重写）时，直接通过BlockRange().InsertAfter(insertionPoint, LIR::Range(m_compiler->fgSetTreeSeq(...), ...))把新节点以线性范围的形式插入，彻底取代了"插入嵌入式语句"的做法；文件末尾还保留ValidateStatement/SanityCheck用于一致性校验。
这里的关键辅助函数是 fgSetTreeSeq：它以执行顺序（UseExecutionOrder = true的后序遍历）为树设置gtPrev/gtNext链接，并在isLIR = true时清除所有节点的GTF_REVERSE_OPS标志——这正是"树序约束"在线性化时刻被显式剥离的体现。
第 3 步：重构 decomposition 与 lowering 以适配线性 LIR
本步的核心工作是把这两个 pass 从"语句/树序遍历"迁移到"线性遍历"，并重构所有依赖父栈（parent stack）的代码，改用能计算节点 def-to-use 边的辅助函数；嵌入式语句插入则替换为简单的线性 IR 插入。
3.i Decomposition（64 位分解）
文档指出该 pass 的迁移相当简单：它按执行顺序遍历每条语句的节点，把 64 位操作分解为等价的 32 位操作序列。关键在于，其重写普遍是"单个运算符展开为连续运算符序列"的扩张，天然适合线性 IR——只需把新节点插入到被替换节点之前即可；由于线性遍历中节点的相对顺序与执行顺序一致，重写的发生顺序也与原来一致。
当前实现 decomposelongs.cpp 印证了这一点：DecomposeBlock直接以m_range = &LIR::AsRange(block)取得块的线性范围并调用DecomposeRangeHelper；还提供DecomposeRange(Compiler*, Lowering*, LIR::Range&)以便对"已分解块中插入的未分解 IR 范围"进行再分解。
3.ii Lowering（降低）
lowering 的图景与 decomposition 类似：所有重写按执行顺序进行，多数重写是"单节点展开为多节点"。但有一个显著例外：x86 架构下 add 节点的降低会检查树遍历提供的父栈，以推迟降低直到可能形成寻址模式（address mode）时。在此场景下，父栈的使用可替换为"查找使用 add 节点所产生 def 的那个节点"的辅助函数——即通过 def-to-use 边来定位推迟时机。
当前 lower.cpp 全程以LIR::AsRange(block)与InsertAfter等线性接口操作（如开关语句的bitTest序列插入、除法/被除数节点从线性序中移除等），印证了 linear walk 的全面落地。
3.iii 通用问题：调用节点旁路表
decomposition 与 lowering 都会用到"修复每个调用节点旁路表（记录调用参数额外信息的 per-call-node side table）"的工具。该工具可替换为：在两个 pass 各自访问调用节点时直接修复旁路表条目，从而省去额外的全表修复遍历。
第 4 步：从 LSRA 中移除语句与树序不变量（lsra.cpp）
LSRA（线性扫描寄存器分配器）此前依赖树序不变量来构建一个栈，用于跟踪运算符所消费 def 的相关数据。移除树序不变量后，线性遍历产生的栈内容可能因"新插入的节点产生的值跨越运算符及其部分操作数存活"而不再正确。文档分析认为，一个从 def 到所需信息的简单映射（map）就足够。
当前实现 lsra.cpp 中，LSRA 直接以LIR::AsRange(block)获得线性范围，并明确注释"Just use the linear order."（lsra.cpp），寄存器分配结果 dump 也标注为 "Trees after linear scan register allocator (LSRA)"——树序依赖已从 LSRA 中清除。
第 5 步：从后端其余部分移除语句（codegen 与调试信息）
后端其余部分即codegen：它没有已知的树序依赖，因此排序语义的变化没有顾虑。但语句节点被用来推导调试信息的 IL 偏移（IL offset）。文档给出三种替代方案：
| 方案 | 做法 | 优缺点 |
|---|---|---|
| 1 | 在线性 LIR 中插入 "IL offset" 节点，codegen 据此发出 IP-mapping 条目 | 若在 LIR 上做代码移动则需额外维护 IL 偏移；但当时后端不做此类代码移动，且优化调试（optimized debugging）尚非场景，损失部分调试保真度可接受——推荐方案，尺寸与实现成本最低 |
| 2 | 用旁路表映射"节点 → IL 偏移" | 增大后端工作集，但便于在代码移动下保持偏移正确 |
| 3 | 直接把 IL 偏移信息加到每个节点上 | 增大整个编译器的工作集 |
文档结论是：除非未来预期需要在代码移动下保持调试信息正确，否则推荐方案 1。当前仓库中 debuginfo.cpp 与 debuginfo.h 已作为独立的调试信息跟踪模块存在，承载语句移除后 IL 偏移/调试序列的推导职责。
第 6 步：从 LIR 执行序中移除 contained 节点
语句移除后仍有一个大问题：contained 节点（如寻址模式中被吸收进父操作数的节点）在 LIR 执行序中的存在。这些节点的执行逻辑上属于其包含节点（containing node）的一部分，但物理上仍留在 IR 的原始位置，导致后端在处理需要考虑执行序的变换时必须特意跳过它们。文档建议：将这些节点从执行序中移除，改为仅由包含节点引用的（通常无序的）表达式树来表示。
值得说明的是：对照当前仓库，contained 节点这一概念仍然保留在 LIR 中（例如 lsra.cpp 中仍有 "Repeatedly check until there is no contained node" 的处理逻辑，lower 也会把节点标记为 contained），即本步更多属于设计文档中的前瞻性方向，与前三步的完全落地程度略有不同。
七、改造后的 LIR 形态与观察方式
改造完成后，RyuJIT 的 LIR 从"树序节点的线性视图 + 仅存在于执行序中的部分节点"演进为纯粹线性排序的节点序列。树边此后只表达两类关系：
- 对 SDSU 临时变量的使用（该使用在执行序中有位置，边从 use 指向 def）；
- 对"作为父节点一部分执行的无序表达式树"的使用。
这种形态由于消除了树序约束与嵌入式语句，且与其他线性 IR 设计高度相似，显著降低了后端变换的编写与推理难度。
如需观察当前仓库中 LIR 的实际形态，可以：
- 阅读 LIR 核心数据结构定义 lir.h 与实现 lir.cpp；
- 查看线性化入口 fgSetTreeSeq；
- 通过 JIT 的标准 dump 机制（
fgDumpTrees等，见 compiler.cpp 中cTrees/dTrees的说明）输出树的线性 dump，其中GenTree::dumpLIRFlags（lir.cpp）负责打印节点标志。
八、结论与后续方向
设计文档 removing-embedded-statements.md 提出的改造，将 RyuJIT 的 LIR 从"带嵌入式语句、受树序约束的线性视图"推进为"纯线性排序的节点序列"。六步方案中，LIR 工具链（LIR::Use/Range）、rationalizer 直接线性化、decomposition/lowering 的线性化重构、LSRA 移除树序不变量均已在前述源码中完整落地；IL 偏移的独立跟踪（debuginfo模块）也已成形；而 contained 节点从执行序中剥离则保留为后续演进方向。整个改造既降低了后端各 pass 的出错概率，也为 RyuJIT 后续的线性化优化与调试信息设计奠定了更清晰的 IR 基础。
【免费下载链接】runtime.NET is a cross-platform runtime for cloud, mobile, desktop, and IoT apps.项目地址: https://gitcode.com/GitHub_Trending/runtime6/runtime
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
