RyuJIT 后端 IR 去嵌入式语句改造从树序约束到纯线性 LIR 的设计与实现【免费下载链接】runtime.NET is a cross-platform runtime for cloud, mobile, desktop, and IoT apps.项目地址: https://gitcode.com/GitHub_Trending/runtime6/runtimeRyuJIT 是 .NET 运行时当前仓库 runtime中负责将中间语言IL编译为机器码的即时编译器JIT。本篇技术指南围绕设计文档 removing-embedded-statements.md 展开深入剖析 RyuJIT 后端 IRLIR中嵌入式语句embedded statements这一历史性构造的缺陷以及作者提出的去除树序约束、走向纯线性 LIR的完整六步改造方案。读完本文你将理解 HIR/LIR 的排序语义、逗号节点与嵌入式语句的等价关系、rationalizer/lowering/LSRA 各阶段的线性化改造要点并能对照当前仓库源码确认这一方案的实际落地形态。一、背景RyuJIT 的两种 IR 形态与排序构造RyuJIT 的中间表示IR以 rationalization理性化和 lowering降低为分界存在两种截然不同的形态前端 IRHIR由导入器importer等前端阶段产生并操作后端 IRLIR由 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 树边既是排序边也是数据流边因此树中的边同时表达了两种语义排序以及数据流图中每个定义只有一个使用SDSUsingle-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 的缺点在吞吐量与代码质量上最具吸引力。从当前源码看这一选择已经落地rationalizerrationalize.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 Decomposition64 位分解文档指出该 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.cppLSRA线性扫描寄存器分配器此前依赖树序不变量来构建一个栈用于跟踪运算符所消费 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::dumpLIRFlagslir.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），仅供参考