.NET CoreCLR JIT 分析框架深度解析从 2009 年架构计划看 SSA、值编号与约束传播的落地实现【免费下载链接】runtime.NET is a cross-platform runtime for cloud, mobile, desktop, and IoT apps.项目地址: https://gitcode.com/GitHub_Trending/runtime6/runtime本篇技术指南以仓库中 docs/design/coreclr/jit/Jit Architecture Plan 2009.md 为骨架逐段解析 CLR JIT 团队在 2009 年提出的优化分析框架——静态单赋值形式SSA、值编号Value Numbering与约束传播——并结合当前仓库中 src/coreclr/jit 的实际实现SsaBuilder、ValueNumStore、fgValueNumber等说明这份十余年前的架构蓝图如何在今天的 RyuJIT 中落地。读完本文你将理解 JIT 编译器如何以不可变值为推理单位做公共子表达式消除、循环不变量提升与冗余分支优化并能从源码层面定位每一处理论对应的实现。一、文档背景一份历史档案式的架构计划该文档由 CLR Jit Team 撰写于 2009 年 9 月仓库在收录时明确标注this is an excerpt from a document written a number of years ago outlining a plan for Jit development... There is no guarantee that what is described here has been implemented, or was implemented as described.即这是一份历史规划文档的节选描述的是计划而非必然的现状。这一点决定了本文的阅读姿势我们既要把文档中的理论讲透也要回到当前仓库源码src/coreclr/jit目录去核实其中哪些设想真正落地、以何种形态落地。从代码结构看文档第 3.3 节提出的核心设想——SSA 形式、值编号、基于值编号的约束传播——已在 RyuJIT 的优化流水线中基本实现但堆内存的字段图建模与 egraph 同余闭包等高级设想则以折中形态如ValueNumStore中的 map select 机制存在。二、分析框架的总纲把优化问题归结为值的问题文档开篇提出的方法论基石是是否适用某个优化本质上是在回答——能否证明性质 P 对表达式 E 的值恒成立can we prove that property P always holds of the value of expression E?因此分析框架应围绕表达式的值来回答问题而不是围绕语法结构做模式识别。这一论断直接决定了后续三件工具的选择顺序先做 SSA 形式再做值编号含流不敏感约束最后做约束传播。在今天的 src/coreclr/jit/compiler.cpp 中这一思路体现为优化流水线中严格有序的若干阶段DoPhase(this, PHASE_BUILD_SSA, Compiler::fgSsaBuild); // 构建 SSA DoPhase(this, PHASE_EARLY_PROP, Compiler::optEarlyProp); // 数组长度传播等 DoPhase(this, PHASE_VALUE_NUMBER, Compiler::fgValueNumber); // 值编号 DoPhase(this, PHASE_HOIST_LOOP_CODE, Compiler::optHoistLoopCode); // 循环不变量提升 DoPhase(this, PHASE_VN_COPY_PROP, Compiler::optVnCopyProp); // 基于 VN 的复制传播 DoPhase(this, PHASE_OPTIMIZE_BRANCHES,Compiler::optRedundantBranches); // 冗余分支优化SSA 与值编号被设计为后续所有基于值优化的公共基础设施这与文档先建框架、再谈具体优化的论述顺序完全一致。三、SSA 形式把可变变量的生命周期切分成不可变的值段3.1 SSA 的核心思想与 phi 函数SSAStatic Single-Assignment form静态单赋值形式把局部变量的生命周期切分为多个片段每个片段内变量持有不同的值并赋予不同的名字每个名字只对应唯一一处定义。因此在静态分析中每个 SSA 名字代表一个在其名字生命周期内不可变的值。这为 CSE、循环不变量代码移动等优化提供了直接答案两个相同表达式是否产生相同值取决于两次求值之间自由变量是否被修改。在非 SSA 形式下需要做路径上是否有修改的保守分析在 SSA 形式下若自由变量在路径上被修改它们会被赋予不同的 SSA 名字两次出现自然就不再是同一个表达式了。文档同时指出这种处理是保守的——它不区分被修改成新值但保持了所在表达式不变的情况而后续的值编号可以弥补这一不精确性。SSA 的成立条件每个使用的 SSA 变量都有唯一的支配性定义需要在合并点插入新定义。文档给出的经典示例基本块B3有前驱B1、B2二者各自定义了局部变量v而B3使用v。SSA 转换把B1、B2中的定义改名为v1、v2并同步改写被其支配的所有使用并在B3头部插入新定义v3其值由一个phi 函数从v1、v2中选出。文档对 phi 函数给出一个很精到的可执行视角把 phi 看成额外携带一个整数选择子参数指示控制流来自哪个前驱——每个前驱传入对应的整数常量phi 依据选择子返回剩余参数之一。从这个视角看phi 函数是良定义的数学函数完全保持执行语义而从静态分析的保守视角看phi 则是在输入之间非确定性选择。文档特意指出这种可执行视角对 phi 成立但对某些用于给 SSA 名字附加约束的所谓pi 函数却不一定非平凡地成立后文约束传播将涉及。3.2 剪枝 SSA 与需求驱动分析剪枝 SSApruned SSA在变量已死的位置避免插入无意义的 phi 定义代价是需要局部变量活性分析。需求驱动demand-driven是 SSA 的另一大优点传统前向数据流分析要传播所有抽象值直到不动点不知道哪些值最终对优化有用而 SSA 支持沿 use-def 链反向遍历——从某个使用出发立刻找到对应定义、定义里的表达式、表达式用到的 SSA 变量如此反向回溯得到影响该使用点值的程序切片program slice。数组边界检查移除正是典型场景只需关注数组引用表达式与下标表达式的性质用 use-def 链独立分析即可不必扫描整个方法。3.3 源码实现SsaBuilder当前仓库中SSA 构建由 src/coreclr/jit/ssabuilder.h 中的SsaBuilder类完成其设计几乎逐条对应文档描述Build()要求语句节点已按求值顺序排列分析流图以确定哪些块需要 phi 节点并将 phi 节点以GT_PHI树节点的形式插入到每个块的起始处每个GT_LCL_VAR通过节点的GetSsaNum()字段获得 SSA 编号每个GT_PHI节点位于一个STORE_LCL_VAR节点之下、作为该 store 的值操作数phi 的输入表示为GT_PHI_ARG节点的链表变量的所有定义def记录在局部变量描述符的 per SSA data 中供 use-def 链查询。构建过程分为两阶段见 ssabuilder.h 中注释先在按拓扑序排列的postOrder块上为需要 phi 的块插入GT_PHI节点再对方法内所有定义和使用执行重命名Rename系列函数。值得注意的细节是 EH 异常处理AddDefToEHSuccessorPhis系列函数专门处理定义所在块处于一个或多个 EH 后继块内的情形——若局部变量在对应后继块入口处存活则把该 SSA 编号加入相应处理器起始块 phi 的参数列表。这说明真实 JIT 的 SSA 必须应对异常流图这一文档未展开的复杂性。四、值编号追踪等价而不只是名字4.1 为什么 SSA 还不够复制与同余SSA 名字是值的不可变名字但它不表达值之间的等价关系。等价关系可能来自复制copyx y;之后x与y持有相同值但 SSA 给它们不同名字同余congruence(a7 b4)两次出现——既然a7、b4是 SSA 变量且两次出现同名说明中间语句S既没定义a也没定义b两次应用是作用于等价参数的同函数应用即公共子表达式。但检测表达式等价超出 SSA 的能力范围。值编号正是负责追踪复制与同余引发的等价关系的机制它还能编码函数语义带来的进一步等价例如加法交换律使b4 a7与a7 b4被发现等价。文档给出了值编号的精确定义值编号发现等价表达式类。由于找出程序中所有表达式等价关系不可判定具体系统只能发现全部等价的某个子集。每个等价类被赋予一个整数value number值编号每个表达式被标记为其所属等价类的编号必要时创建单元素类。于是具有相同值编号的两个不同表达式求值结果相同技术上要求在从一次求值到另一次求值的控制流路径上没有插入任何会影响表达式值的 phi 求值。反过来值编号不同并不保证值一定不同。4.2 值编号的基本赋值算法文档给出的赋值流程非常工程化为所有输入参数分配 primitive 值编号入参是方法开始执行前就存在的值维护字面量 → 值编号映射表常量映射按前向流分析遍历程序跟踪变量中保存的值编号把globMem视为隐式程序变量维护一张算子参数值编号元组→ 结果值编号的表格。遇到内建算子算术、逻辑等表达式时若关心其等价性就在表中查找该元组是否已有值编号命中则复用未命中则新建值编号、记录其定义并把元组映射存入表。若不关心则直接分配新编号、不存表。今天ValueNumStoresrc/coreclr/jit/valuenum.h的接口与此一一对应VNForIntCon/VNForLongCon/VNForDoubleCon等为各类常量分配编号VNForFunc有 0 到 4 元五个重载为算子应用分配编号——这正是文档中算子/参数元组表的具象化VNF_ARR_LENGTH、VNF_ADD、VNF_MUL、VNF_DIV、VNF_AND、VNF_LT_UN等枚举见 src/coreclr/jit/inductionvariableopts.cpp 与 src/coreclr/jit/gentree.cpp 的调用则是文档所说内建算子的现代形态。ValueNumStore还提供VNForNull()、VNForVoid()、VNForEmptyExcSet()等特殊编号用于表达空指针、空值与空异常集合这是文档未涉及、实现中必需的扩展。文档还定义了值编号的三分类可直接对应实现中对值的查询能力常量值编号表示字面常量原始primitive值编号表示方法开始执行前就存在的值入参、初始堆状态其余值编号带有定义定义是其他值编号的某个纯函数——其中一类就是后文要讲的值编号 phi 函数。4.3 堆内存建模字段图、globMem 与 havoc文档最前瞻的部分是对托管堆内存的统一建模其动机是托管语言大多使用类型化指针可以采用比 C 语言通用指针分析更受限的别名处理。建模方案若对象类型A有字段f则把a.f建模为对字段映射A$f以引用值a为索引的取值。字段写a.f v建模为函数式更新A$f ¬ A$f[a : v]——生成一张新映射内容与原映射相同仅在索引a处值为v。由此对不同字段的写不会影响A$f可以准确地对涉及堆引用的表达式做 CSE如o.f o.f文档直言据我所知我们今天不做这件事更进一步还能追踪A$f相邻两个值之间的关系使编译器得知通过已知与a不同的引用做 store 不影响a.f的值。调用点问题调用方法时通常必须对堆影响持高度保守态度需要havoc搅乱操作——为所有字段映射分配新值编号。为此把字段映射看作全局内存状态的函数全局内存状态是字段名 → 字段映射值编号的映射。于是a.f实际上是globMem[A$f][a]a.f v实际更新globMem使其A$f映射在引用值a处为v。一次调用只需把全局内存状态的值编号设为新值对它一无所知即可廉价地使所有堆知识失效。在此视图下globMem是所有方法的隐式输入在没有反证的情况下被假定被所有方法修改。这一模型在源码中的痕迹清晰可见ValueNumStore注释中提到VNForMapSelect[Work]方法代表了选择基础设施的核心见 src/coreclr/jit/valuenum.h 注释区专门处理在字段映射上按对象引用做选择这类取值编号问题与文档a.f是globMem[A$f][a]的表述对应编译器阶段fgValueNumberFieldLoad/fgValueNumberFieldStore/fgValueNumberByrefExposedLoad见 src/coreclr/jit/compiler.h分别处理字段读、字段写与 byref 暴露下的堆读。文档还设想了方法的纯度建模方法调用结果及 ref 参数被赋的值可视为参数含globMem与调用目标对象的方法特有函数若 CLR 支持可验证的[Pure]属性则纯方法既不观察也不修改全局内存可建模为不接收globMem参数的函数其调用也不修改globMem。需要说明这是一个 2009 年的展望性描述截至当前仓库源码并未提供该可验证[Pure]属性的通用实现。五、值编号 phi合并点与循环的处理5.1 合并点的 VN phi流分析到达控制流合并点时遇到难题若变量v沿不同入边持有不同值显然应新建一个值编号定义为入边值的VN phi 函数。但问题是如何知道何时需要——不能在每个合并点为每个变量都新建值编号很多情况下变量在菱形控制流前并未被修改所有路径上值相同。文档给出的工程策略尽量延迟分析块直到其所有前驱都被完整分析存在循环时这不可能做到但SSA 转换已经算出了哪里必须放 SSA phi 节点这可以非常近似地指示 VN phi 节点的必要性这是一个保守近似若某合并点没有v的 SSA phi则所有入边v值相同不需要 VN phi但可能存在需要 SSA phi 却不需要 VN phi的情况——例如变量在所有入边都被赋值但各边赋的是同一个值于是算法是先对应 SSA phi 引入 VN phi 定义再做流分析当能证明所有入参等价时消除 VN phi及其结果值编号。这个过程只会发现新等价绝不会使已声称的等价失效。消除方式可以沿用标准流分析范式若最初为v在合并点分配了n2 vnphi(n0, n1)后来发现两条分支流入的都是n0就把n0赋给v并继续流分析、把该块标记为已变化这种变化传播可能连带消除更多 VN phi。5.2 循环示例k k 1 – 1文档用如下循环展示了 VN phi 在不动点处消解等价的能力k … while (P) { k k 1; … use k …; k k – 1; }SSA 形式为k_0 … loop: k_1 phi(k_0, k_3); // n1 vnphi(n0, ^) if (!P) goto exit; k_2 k_1 1; … use k …; k_3 k_2 – 1; goto loop; exit:流分析给k_0分配值编号n0并流入循环循环头是汇合点、有k的 SSA 定义于是为k引入值编号n1定义为k_0与k_3值编号的 VN phi。初始时k_3的值未知记为 bottom 元素。分析循环体时假设k_1持有n1若值编号基础设施内建足够的算术知识能推出n1 1 – 1 n1则循环结束时确定k_3持有n1。此时n1的定义形如n1 vnphi(n0, n1)。由于 phi 的非确定性选择语义无论 VN phi 选哪个输入该方程都必须成立——唯一解是n1 n0。于是到达不动点时即可判定k在每次循环迭代开始时始终持有同一个值其值在循环内不变因为定义在循环外。这正是文档值编号超越 SSA 保守性的经典例证SSA 形式因循环内语法上的赋值而不得不创建 phi而值编号能够证明变量实际持有的值不变。该设想在今天的实现中以更工程化的形态存在Compiler::optVNIsLoopInvariant(ValueNum vn, FlowGraphNaturalLoop* loop, VNSet* recordedVNs)见 src/coreclr/jit/compiler.h用于判定某个值编号是否对给定循环不变其注释明确指出VNPhi 把 VN 连接到 SSA 定义因此我们可以知道该 SSA 定义是否出现在循环中——常量与初始值总是循环不变的而 VNPhi 提供了SSA 定义在循环内但值实际不变的判定通道。这正是文档中若 SSA 的循环不变测试失败则检查值编号图的落地若变量的值编号递归地由常量、primitive 值编号或位于循环外的 VN phi 定义则表达式值循环不变。该判定由循环不变量提升阶段optHoistLoopCode见 src/coreclr/jit/compiler.cpp消费。5.3 等价类合并union-find 与 egraph文档提出了两种处理发现新等价后收回旧值编号的机制流分析传播前述把块标记为已变化简单但可能低效等价类代表映射 union-find 并查集维护值编号 → 值编号映射把每个值编号映射到其等价类代表。使用任何值编号前先翻译成类代表。查询时沿指针链行进并做路径压缩使链上所有元素直接指向最终代表合并两个等价类只需让一方的代表指向另一方。若再配合对函数定义映射中不同表达式做统一如vn4 (vn1, vn3)、vn5 (vn2, vn3)统一vn1与vn2后希望发现vn4与vn5同余则可引入定理证明领域的数据结构egraphNelson, 1981高效表示等价类并自动发现同余即同余闭包congruence closure从而有可能在对 SSA 转换后程序的单次线性遍历中完成值编号。文档自评使用 egraph 会增加复杂度。从当前源码看RyuJIT 采用的前者路径——即流分析传播加 VN phi 消除——是主要机制egraph 属于文档层面的前瞻设想并未以 Nelson 原始形态出现于 src/coreclr/jit 中。六、约束传播值编号上的流敏感事实文档预告了约束传播constraint propagation即流敏感事实作为分析框架的第三块拼图其设计要点如下不变量事实invariant facts由定义表达式产生的值保证成立的事实在不可变值的整个生命周期内保持可直接记录为值编号的属性。例如new Foo()的结果非空、且精确类型为Foo。流敏感事实flow-sensitive facts由程序控制流谓词衍生的事实。例如循环测试可用以推断递增的循环迭代变量的上界但仅限循环内。需求驱动不必为所有表达式做完整数据流分析而是给定某位置某表达式的出现查询其值编号、以及在该位置适用于该值编号的约束仅在 SSA use-def 图的有关部分做局部化数据流分析。以值编号而非变量名表达约束若两个变量持有等价值对其中一个的约束自动是另一个的约束无需跟踪依赖变量、也无需在变量更新时杀死断言。这一节在文档中属于预告we will discuss a treatment of flow-sensitive facts in the next section但今天仓库中有对应实现optRedundantBranchesPHASE_OPTIMIZE_BRANCHESsrc/coreclr/jit/compiler.cpp即基于 VN 做冗余分支优化src/coreclr/jit/redundantbranchopts.cpp 中大量使用VNForFunc构造关系表达式如VNF_AND来推理分支条件src/coreclr/jit/assertionprop.cpp 中则用VNF_ARR_LENGTH构造数组长度值编号参与断言传播。这些都属于在值编号上附加流敏感事实的现代形态。七、为什么值编号优于裸 SSA文档的总结性评论文档在 3.3.3 节给出三点关键评论每一句都能在今天的优化器中找到对应物1. 从可变变量到不可变值的思维转变。JIT32x86 全框架 JIT即旧版 JIT做 CSE 时为每个候选表达式计算其依赖的变量集合两个同文表达式只有当路径间无依赖变量被修改时才公共在 SSA/值编号框架中发生此类修改时两个表达式根本不会被当作 CSE 候选——SSA 下二者使用的 SSA 变量集合不同值编号下二者获得不同值编号。类似地若断言传播系统以值编号而非变量表达就无需跟踪依赖变量、也无需在变量更新时杀死断言。今天 RyuJIT 的 CSE 阶段optPerformCSE见PHASE_CSE之前Remove common sub-expressions注释src/coreclr/jit/compiler.cpp与 VN 复制传播阶段PHASE_VN_COPY_PROP→optVnCopyProp正是沿此思路运作。2. 稀疏 use-def 图上的需求驱动分析。与传统为整个方法计算分析事实的全量流分析相比SSA 与值编号在文档所述的混合概念下都允许在稀疏 use-def 图上做需求驱动分析把分析精力集中到优化真正需要的地方——这对编译时间敏感的场景JIT 或 NGEN 编译尤其重要。RyuJIT 作为运行时 JIT 对编译开销高度敏感正是文档此点的现实背景。3. 推理单位从变量格子到不可变值。转向值编号视角完成了 SSA 开启的那一步从变量是可变的存储单元的视角转向推理变量在每个程序点所持有的不可变值的性质。值编号编码的信息严格多于 SSA 名字至少捕获了表达式间的一部分等价因此许多优化只需要关心变量或表达式持有的值的性质——查询值编号即可。八、总结从 2009 蓝图到今天的 RyuJIT将文档设想与当前仓库源码对照可以得出清晰的落地清单2009 年文档设想当前仓库实现落地状态SSA 形式构建phi 节点、重命名、剪枝SsaBuilderssabuilder.h、PHASE_BUILD_SSA已实现含 EH 后继 phi 等增强值编号赋值常量、primitive、算子元组表ValueNumStore::VNFor*Con、VNForFuncvaluenum.h已实现堆内存字段图建模A$f、globMem、havocVNForMapSelect[Work]、fgValueNumberFieldLoad/Storecompiler.h以 map select 机制实现VN phi 消除与循环值不变证明optVNIsLoopInvariantcompiler.h、fgValueNumberPhiDef已实现值编号上的约束传播需求驱动optRedundantBranches、断言传播中的VNF_ARR_LENGTH使用已实现分布形态egraph 同余闭包单遍值编号未见于 src/coreclr/jit未落地文档自评增加复杂度可验证[Pure]属性建模未见于当前仓库未落地文档明确为展望这份文档的价值在于它用一份 2009 年的规划清晰阐述了 .NET 托管编译器中以值为中心的分析哲学——SSA 提供不可变的名字值编号捕获名字之上的等价约束传播在等价之上叠加流敏感事实。而仓库中 src/coreclr/jit/compiler.cpp 的优化流水线正是这一哲学十余年后仍在使用的活证据。对于想深入 RyuJIT 优化器源码的读者建议按PHASE_BUILD_SSA → PHASE_VALUE_NUMBER → PHASE_HOIST_LOOP_CODE → PHASE_VN_COPY_PROP → PHASE_OPTIMIZE_BRANCHES的顺序跟踪 src/coreclr/jit 中的对应实现即可把本文的理论逐一映射到可调试的代码路径上。【免费下载链接】runtime.NET is a cross-platform runtime for cloud, mobile, desktop, and IoT apps.项目地址: https://gitcode.com/GitHub_Trending/runtime6/runtime创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 .NET CoreCLR JIT 分析框架深度解析：从 2009 年架构计划看 SSA、值编号与约束传播的落地实现
.NET CoreCLR JIT 分析框架深度解析从 2009 年架构计划看 SSA、值编号与约束传播的落地实现【免费下载链接】runtime.NET is a cross-platform runtime for cloud, mobile, desktop, and IoT apps.项目地址: https://gitcode.com/GitHub_Trending/runtime6/runtime本篇技术指南以仓库中 docs/design/coreclr/jit/Jit Architecture Plan 2009.md 为骨架逐段解析 CLR JIT 团队在 2009 年提出的优化分析框架——静态单赋值形式SSA、值编号Value Numbering与约束传播——并结合当前仓库中 src/coreclr/jit 的实际实现SsaBuilder、ValueNumStore、fgValueNumber等说明这份十余年前的架构蓝图如何在今天的 RyuJIT 中落地。读完本文你将理解 JIT 编译器如何以不可变值为推理单位做公共子表达式消除、循环不变量提升与冗余分支优化并能从源码层面定位每一处理论对应的实现。一、文档背景一份历史档案式的架构计划该文档由 CLR Jit Team 撰写于 2009 年 9 月仓库在收录时明确标注this is an excerpt from a document written a number of years ago outlining a plan for Jit development... There is no guarantee that what is described here has been implemented, or was implemented as described.即这是一份历史规划文档的节选描述的是计划而非必然的现状。这一点决定了本文的阅读姿势我们既要把文档中的理论讲透也要回到当前仓库源码src/coreclr/jit目录去核实其中哪些设想真正落地、以何种形态落地。从代码结构看文档第 3.3 节提出的核心设想——SSA 形式、值编号、基于值编号的约束传播——已在 RyuJIT 的优化流水线中基本实现但堆内存的字段图建模与 egraph 同余闭包等高级设想则以折中形态如ValueNumStore中的 map select 机制存在。二、分析框架的总纲把优化问题归结为值的问题文档开篇提出的方法论基石是是否适用某个优化本质上是在回答——能否证明性质 P 对表达式 E 的值恒成立can we prove that property P always holds of the value of expression E?因此分析框架应围绕表达式的值来回答问题而不是围绕语法结构做模式识别。这一论断直接决定了后续三件工具的选择顺序先做 SSA 形式再做值编号含流不敏感约束最后做约束传播。在今天的 src/coreclr/jit/compiler.cpp 中这一思路体现为优化流水线中严格有序的若干阶段DoPhase(this, PHASE_BUILD_SSA, Compiler::fgSsaBuild); // 构建 SSA DoPhase(this, PHASE_EARLY_PROP, Compiler::optEarlyProp); // 数组长度传播等 DoPhase(this, PHASE_VALUE_NUMBER, Compiler::fgValueNumber); // 值编号 DoPhase(this, PHASE_HOIST_LOOP_CODE, Compiler::optHoistLoopCode); // 循环不变量提升 DoPhase(this, PHASE_VN_COPY_PROP, Compiler::optVnCopyProp); // 基于 VN 的复制传播 DoPhase(this, PHASE_OPTIMIZE_BRANCHES,Compiler::optRedundantBranches); // 冗余分支优化SSA 与值编号被设计为后续所有基于值优化的公共基础设施这与文档先建框架、再谈具体优化的论述顺序完全一致。三、SSA 形式把可变变量的生命周期切分成不可变的值段3.1 SSA 的核心思想与 phi 函数SSAStatic Single-Assignment form静态单赋值形式把局部变量的生命周期切分为多个片段每个片段内变量持有不同的值并赋予不同的名字每个名字只对应唯一一处定义。因此在静态分析中每个 SSA 名字代表一个在其名字生命周期内不可变的值。这为 CSE、循环不变量代码移动等优化提供了直接答案两个相同表达式是否产生相同值取决于两次求值之间自由变量是否被修改。在非 SSA 形式下需要做路径上是否有修改的保守分析在 SSA 形式下若自由变量在路径上被修改它们会被赋予不同的 SSA 名字两次出现自然就不再是同一个表达式了。文档同时指出这种处理是保守的——它不区分被修改成新值但保持了所在表达式不变的情况而后续的值编号可以弥补这一不精确性。SSA 的成立条件每个使用的 SSA 变量都有唯一的支配性定义需要在合并点插入新定义。文档给出的经典示例基本块B3有前驱B1、B2二者各自定义了局部变量v而B3使用v。SSA 转换把B1、B2中的定义改名为v1、v2并同步改写被其支配的所有使用并在B3头部插入新定义v3其值由一个phi 函数从v1、v2中选出。文档对 phi 函数给出一个很精到的可执行视角把 phi 看成额外携带一个整数选择子参数指示控制流来自哪个前驱——每个前驱传入对应的整数常量phi 依据选择子返回剩余参数之一。从这个视角看phi 函数是良定义的数学函数完全保持执行语义而从静态分析的保守视角看phi 则是在输入之间非确定性选择。文档特意指出这种可执行视角对 phi 成立但对某些用于给 SSA 名字附加约束的所谓pi 函数却不一定非平凡地成立后文约束传播将涉及。3.2 剪枝 SSA 与需求驱动分析剪枝 SSApruned SSA在变量已死的位置避免插入无意义的 phi 定义代价是需要局部变量活性分析。需求驱动demand-driven是 SSA 的另一大优点传统前向数据流分析要传播所有抽象值直到不动点不知道哪些值最终对优化有用而 SSA 支持沿 use-def 链反向遍历——从某个使用出发立刻找到对应定义、定义里的表达式、表达式用到的 SSA 变量如此反向回溯得到影响该使用点值的程序切片program slice。数组边界检查移除正是典型场景只需关注数组引用表达式与下标表达式的性质用 use-def 链独立分析即可不必扫描整个方法。3.3 源码实现SsaBuilder当前仓库中SSA 构建由 src/coreclr/jit/ssabuilder.h 中的SsaBuilder类完成其设计几乎逐条对应文档描述Build()要求语句节点已按求值顺序排列分析流图以确定哪些块需要 phi 节点并将 phi 节点以GT_PHI树节点的形式插入到每个块的起始处每个GT_LCL_VAR通过节点的GetSsaNum()字段获得 SSA 编号每个GT_PHI节点位于一个STORE_LCL_VAR节点之下、作为该 store 的值操作数phi 的输入表示为GT_PHI_ARG节点的链表变量的所有定义def记录在局部变量描述符的 per SSA data 中供 use-def 链查询。构建过程分为两阶段见 ssabuilder.h 中注释先在按拓扑序排列的postOrder块上为需要 phi 的块插入GT_PHI节点再对方法内所有定义和使用执行重命名Rename系列函数。值得注意的细节是 EH 异常处理AddDefToEHSuccessorPhis系列函数专门处理定义所在块处于一个或多个 EH 后继块内的情形——若局部变量在对应后继块入口处存活则把该 SSA 编号加入相应处理器起始块 phi 的参数列表。这说明真实 JIT 的 SSA 必须应对异常流图这一文档未展开的复杂性。四、值编号追踪等价而不只是名字4.1 为什么 SSA 还不够复制与同余SSA 名字是值的不可变名字但它不表达值之间的等价关系。等价关系可能来自复制copyx y;之后x与y持有相同值但 SSA 给它们不同名字同余congruence(a7 b4)两次出现——既然a7、b4是 SSA 变量且两次出现同名说明中间语句S既没定义a也没定义b两次应用是作用于等价参数的同函数应用即公共子表达式。但检测表达式等价超出 SSA 的能力范围。值编号正是负责追踪复制与同余引发的等价关系的机制它还能编码函数语义带来的进一步等价例如加法交换律使b4 a7与a7 b4被发现等价。文档给出了值编号的精确定义值编号发现等价表达式类。由于找出程序中所有表达式等价关系不可判定具体系统只能发现全部等价的某个子集。每个等价类被赋予一个整数value number值编号每个表达式被标记为其所属等价类的编号必要时创建单元素类。于是具有相同值编号的两个不同表达式求值结果相同技术上要求在从一次求值到另一次求值的控制流路径上没有插入任何会影响表达式值的 phi 求值。反过来值编号不同并不保证值一定不同。4.2 值编号的基本赋值算法文档给出的赋值流程非常工程化为所有输入参数分配 primitive 值编号入参是方法开始执行前就存在的值维护字面量 → 值编号映射表常量映射按前向流分析遍历程序跟踪变量中保存的值编号把globMem视为隐式程序变量维护一张算子参数值编号元组→ 结果值编号的表格。遇到内建算子算术、逻辑等表达式时若关心其等价性就在表中查找该元组是否已有值编号命中则复用未命中则新建值编号、记录其定义并把元组映射存入表。若不关心则直接分配新编号、不存表。今天ValueNumStoresrc/coreclr/jit/valuenum.h的接口与此一一对应VNForIntCon/VNForLongCon/VNForDoubleCon等为各类常量分配编号VNForFunc有 0 到 4 元五个重载为算子应用分配编号——这正是文档中算子/参数元组表的具象化VNF_ARR_LENGTH、VNF_ADD、VNF_MUL、VNF_DIV、VNF_AND、VNF_LT_UN等枚举见 src/coreclr/jit/inductionvariableopts.cpp 与 src/coreclr/jit/gentree.cpp 的调用则是文档所说内建算子的现代形态。ValueNumStore还提供VNForNull()、VNForVoid()、VNForEmptyExcSet()等特殊编号用于表达空指针、空值与空异常集合这是文档未涉及、实现中必需的扩展。文档还定义了值编号的三分类可直接对应实现中对值的查询能力常量值编号表示字面常量原始primitive值编号表示方法开始执行前就存在的值入参、初始堆状态其余值编号带有定义定义是其他值编号的某个纯函数——其中一类就是后文要讲的值编号 phi 函数。4.3 堆内存建模字段图、globMem 与 havoc文档最前瞻的部分是对托管堆内存的统一建模其动机是托管语言大多使用类型化指针可以采用比 C 语言通用指针分析更受限的别名处理。建模方案若对象类型A有字段f则把a.f建模为对字段映射A$f以引用值a为索引的取值。字段写a.f v建模为函数式更新A$f ¬ A$f[a : v]——生成一张新映射内容与原映射相同仅在索引a处值为v。由此对不同字段的写不会影响A$f可以准确地对涉及堆引用的表达式做 CSE如o.f o.f文档直言据我所知我们今天不做这件事更进一步还能追踪A$f相邻两个值之间的关系使编译器得知通过已知与a不同的引用做 store 不影响a.f的值。调用点问题调用方法时通常必须对堆影响持高度保守态度需要havoc搅乱操作——为所有字段映射分配新值编号。为此把字段映射看作全局内存状态的函数全局内存状态是字段名 → 字段映射值编号的映射。于是a.f实际上是globMem[A$f][a]a.f v实际更新globMem使其A$f映射在引用值a处为v。一次调用只需把全局内存状态的值编号设为新值对它一无所知即可廉价地使所有堆知识失效。在此视图下globMem是所有方法的隐式输入在没有反证的情况下被假定被所有方法修改。这一模型在源码中的痕迹清晰可见ValueNumStore注释中提到VNForMapSelect[Work]方法代表了选择基础设施的核心见 src/coreclr/jit/valuenum.h 注释区专门处理在字段映射上按对象引用做选择这类取值编号问题与文档a.f是globMem[A$f][a]的表述对应编译器阶段fgValueNumberFieldLoad/fgValueNumberFieldStore/fgValueNumberByrefExposedLoad见 src/coreclr/jit/compiler.h分别处理字段读、字段写与 byref 暴露下的堆读。文档还设想了方法的纯度建模方法调用结果及 ref 参数被赋的值可视为参数含globMem与调用目标对象的方法特有函数若 CLR 支持可验证的[Pure]属性则纯方法既不观察也不修改全局内存可建模为不接收globMem参数的函数其调用也不修改globMem。需要说明这是一个 2009 年的展望性描述截至当前仓库源码并未提供该可验证[Pure]属性的通用实现。五、值编号 phi合并点与循环的处理5.1 合并点的 VN phi流分析到达控制流合并点时遇到难题若变量v沿不同入边持有不同值显然应新建一个值编号定义为入边值的VN phi 函数。但问题是如何知道何时需要——不能在每个合并点为每个变量都新建值编号很多情况下变量在菱形控制流前并未被修改所有路径上值相同。文档给出的工程策略尽量延迟分析块直到其所有前驱都被完整分析存在循环时这不可能做到但SSA 转换已经算出了哪里必须放 SSA phi 节点这可以非常近似地指示 VN phi 节点的必要性这是一个保守近似若某合并点没有v的 SSA phi则所有入边v值相同不需要 VN phi但可能存在需要 SSA phi 却不需要 VN phi的情况——例如变量在所有入边都被赋值但各边赋的是同一个值于是算法是先对应 SSA phi 引入 VN phi 定义再做流分析当能证明所有入参等价时消除 VN phi及其结果值编号。这个过程只会发现新等价绝不会使已声称的等价失效。消除方式可以沿用标准流分析范式若最初为v在合并点分配了n2 vnphi(n0, n1)后来发现两条分支流入的都是n0就把n0赋给v并继续流分析、把该块标记为已变化这种变化传播可能连带消除更多 VN phi。5.2 循环示例k k 1 – 1文档用如下循环展示了 VN phi 在不动点处消解等价的能力k … while (P) { k k 1; … use k …; k k – 1; }SSA 形式为k_0 … loop: k_1 phi(k_0, k_3); // n1 vnphi(n0, ^) if (!P) goto exit; k_2 k_1 1; … use k …; k_3 k_2 – 1; goto loop; exit:流分析给k_0分配值编号n0并流入循环循环头是汇合点、有k的 SSA 定义于是为k引入值编号n1定义为k_0与k_3值编号的 VN phi。初始时k_3的值未知记为 bottom 元素。分析循环体时假设k_1持有n1若值编号基础设施内建足够的算术知识能推出n1 1 – 1 n1则循环结束时确定k_3持有n1。此时n1的定义形如n1 vnphi(n0, n1)。由于 phi 的非确定性选择语义无论 VN phi 选哪个输入该方程都必须成立——唯一解是n1 n0。于是到达不动点时即可判定k在每次循环迭代开始时始终持有同一个值其值在循环内不变因为定义在循环外。这正是文档值编号超越 SSA 保守性的经典例证SSA 形式因循环内语法上的赋值而不得不创建 phi而值编号能够证明变量实际持有的值不变。该设想在今天的实现中以更工程化的形态存在Compiler::optVNIsLoopInvariant(ValueNum vn, FlowGraphNaturalLoop* loop, VNSet* recordedVNs)见 src/coreclr/jit/compiler.h用于判定某个值编号是否对给定循环不变其注释明确指出VNPhi 把 VN 连接到 SSA 定义因此我们可以知道该 SSA 定义是否出现在循环中——常量与初始值总是循环不变的而 VNPhi 提供了SSA 定义在循环内但值实际不变的判定通道。这正是文档中若 SSA 的循环不变测试失败则检查值编号图的落地若变量的值编号递归地由常量、primitive 值编号或位于循环外的 VN phi 定义则表达式值循环不变。该判定由循环不变量提升阶段optHoistLoopCode见 src/coreclr/jit/compiler.cpp消费。5.3 等价类合并union-find 与 egraph文档提出了两种处理发现新等价后收回旧值编号的机制流分析传播前述把块标记为已变化简单但可能低效等价类代表映射 union-find 并查集维护值编号 → 值编号映射把每个值编号映射到其等价类代表。使用任何值编号前先翻译成类代表。查询时沿指针链行进并做路径压缩使链上所有元素直接指向最终代表合并两个等价类只需让一方的代表指向另一方。若再配合对函数定义映射中不同表达式做统一如vn4 (vn1, vn3)、vn5 (vn2, vn3)统一vn1与vn2后希望发现vn4与vn5同余则可引入定理证明领域的数据结构egraphNelson, 1981高效表示等价类并自动发现同余即同余闭包congruence closure从而有可能在对 SSA 转换后程序的单次线性遍历中完成值编号。文档自评使用 egraph 会增加复杂度。从当前源码看RyuJIT 采用的前者路径——即流分析传播加 VN phi 消除——是主要机制egraph 属于文档层面的前瞻设想并未以 Nelson 原始形态出现于 src/coreclr/jit 中。六、约束传播值编号上的流敏感事实文档预告了约束传播constraint propagation即流敏感事实作为分析框架的第三块拼图其设计要点如下不变量事实invariant facts由定义表达式产生的值保证成立的事实在不可变值的整个生命周期内保持可直接记录为值编号的属性。例如new Foo()的结果非空、且精确类型为Foo。流敏感事实flow-sensitive facts由程序控制流谓词衍生的事实。例如循环测试可用以推断递增的循环迭代变量的上界但仅限循环内。需求驱动不必为所有表达式做完整数据流分析而是给定某位置某表达式的出现查询其值编号、以及在该位置适用于该值编号的约束仅在 SSA use-def 图的有关部分做局部化数据流分析。以值编号而非变量名表达约束若两个变量持有等价值对其中一个的约束自动是另一个的约束无需跟踪依赖变量、也无需在变量更新时杀死断言。这一节在文档中属于预告we will discuss a treatment of flow-sensitive facts in the next section但今天仓库中有对应实现optRedundantBranchesPHASE_OPTIMIZE_BRANCHESsrc/coreclr/jit/compiler.cpp即基于 VN 做冗余分支优化src/coreclr/jit/redundantbranchopts.cpp 中大量使用VNForFunc构造关系表达式如VNF_AND来推理分支条件src/coreclr/jit/assertionprop.cpp 中则用VNF_ARR_LENGTH构造数组长度值编号参与断言传播。这些都属于在值编号上附加流敏感事实的现代形态。七、为什么值编号优于裸 SSA文档的总结性评论文档在 3.3.3 节给出三点关键评论每一句都能在今天的优化器中找到对应物1. 从可变变量到不可变值的思维转变。JIT32x86 全框架 JIT即旧版 JIT做 CSE 时为每个候选表达式计算其依赖的变量集合两个同文表达式只有当路径间无依赖变量被修改时才公共在 SSA/值编号框架中发生此类修改时两个表达式根本不会被当作 CSE 候选——SSA 下二者使用的 SSA 变量集合不同值编号下二者获得不同值编号。类似地若断言传播系统以值编号而非变量表达就无需跟踪依赖变量、也无需在变量更新时杀死断言。今天 RyuJIT 的 CSE 阶段optPerformCSE见PHASE_CSE之前Remove common sub-expressions注释src/coreclr/jit/compiler.cpp与 VN 复制传播阶段PHASE_VN_COPY_PROP→optVnCopyProp正是沿此思路运作。2. 稀疏 use-def 图上的需求驱动分析。与传统为整个方法计算分析事实的全量流分析相比SSA 与值编号在文档所述的混合概念下都允许在稀疏 use-def 图上做需求驱动分析把分析精力集中到优化真正需要的地方——这对编译时间敏感的场景JIT 或 NGEN 编译尤其重要。RyuJIT 作为运行时 JIT 对编译开销高度敏感正是文档此点的现实背景。3. 推理单位从变量格子到不可变值。转向值编号视角完成了 SSA 开启的那一步从变量是可变的存储单元的视角转向推理变量在每个程序点所持有的不可变值的性质。值编号编码的信息严格多于 SSA 名字至少捕获了表达式间的一部分等价因此许多优化只需要关心变量或表达式持有的值的性质——查询值编号即可。八、总结从 2009 蓝图到今天的 RyuJIT将文档设想与当前仓库源码对照可以得出清晰的落地清单2009 年文档设想当前仓库实现落地状态SSA 形式构建phi 节点、重命名、剪枝SsaBuilderssabuilder.h、PHASE_BUILD_SSA已实现含 EH 后继 phi 等增强值编号赋值常量、primitive、算子元组表ValueNumStore::VNFor*Con、VNForFuncvaluenum.h已实现堆内存字段图建模A$f、globMem、havocVNForMapSelect[Work]、fgValueNumberFieldLoad/Storecompiler.h以 map select 机制实现VN phi 消除与循环值不变证明optVNIsLoopInvariantcompiler.h、fgValueNumberPhiDef已实现值编号上的约束传播需求驱动optRedundantBranches、断言传播中的VNF_ARR_LENGTH使用已实现分布形态egraph 同余闭包单遍值编号未见于 src/coreclr/jit未落地文档自评增加复杂度可验证[Pure]属性建模未见于当前仓库未落地文档明确为展望这份文档的价值在于它用一份 2009 年的规划清晰阐述了 .NET 托管编译器中以值为中心的分析哲学——SSA 提供不可变的名字值编号捕获名字之上的等价约束传播在等价之上叠加流敏感事实。而仓库中 src/coreclr/jit/compiler.cpp 的优化流水线正是这一哲学十余年后仍在使用的活证据。对于想深入 RyuJIT 优化器源码的读者建议按PHASE_BUILD_SSA → PHASE_VALUE_NUMBER → PHASE_HOIST_LOOP_CODE → PHASE_VN_COPY_PROP → PHASE_OPTIMIZE_BRANCHES的顺序跟踪 src/coreclr/jit 中的对应实现即可把本文的理论逐一映射到可调试的代码路径上。【免费下载链接】runtime.NET is a cross-platform runtime for cloud, mobile, desktop, and IoT apps.项目地址: https://gitcode.com/GitHub_Trending/runtime6/runtime创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考