深入 .NET 运行时 JIT 价值编号中的堆访问优化从VNF_MapStore展平到查询预算控制【免费下载链接】runtime.NET is a cross-platform runtime for cloud, mobile, desktop, and IoT apps.项目地址: https://gitcode.com/GitHub_Trending/runtime6/runtime导读本文基于 .NET 运行时dotnet/runtime核心库CoreCLRJIT 团队于 2013 年撰写的一篇内部设计文档系统剖析 JIT 价值编号Value Numbering简称 VN在对托管堆heap建模时面临的性能病理performance pathology并给出三类对策扁平化堆状态表示、phi 查询结果记忆化memoization以及查询预算上限。读者在读完本文后将理解VNF_MapStore/VNF_MapSelect这两类 VN 函数的形式语义与规约规则、堆 phi 定义的处理策略以及这些设计在当前仓库 valuenum.cpp 与 valuenum.h 中的实际落地情况例如VNForMapSelectWork的预算递减、m_fixedPointMapSels递归防护、JitVNMapSelLimit配置项从而具备定位与规避编译器极端编译耗时问题的能力。说明原文是多年前的规划性文档作者明确声明不保证所描述内容已按原样实现。本文在还原其设计思想的同时会结合当前仓库源码指出哪些部分已经落地、哪些仍是构想做到事实与推断严格区分。一、背景价值编号如何为堆建模1.1 函数式更新与两类 VN 函数在 CoreCLR JIT 的价值编号框架中一个赋值语句o.f vf是类C的某个字段被建模为对堆的函数式更新H’ H0[ C$f : H0[C$f][o : v] ]其中H0是赋值前的堆值heap valueH’是赋值后的堆值记号m[ind : val]表示对映射mapm的函数式更新生成一个新映射除索引ind处为val外其余与m相同记号m[ind]表示在m中取索引ind处的值。在 VN 框架中这两者分别对应两个 VN 函数VNF_MapStore(m, ind, val)—— 函数式更新是当前仓库中仅有的两个四元 VN 函数之一另一个是VNF_PtrToArrElem见 valuenum.cpp 的注释与断言VNF_MapSelect(m, ind)—— 映射查询且有专门入口VNForMapSelectvaluenum.h 明确指出它不能走通用VNForFunc必须使用专用函数。C$f是字段的唯一标识符在实现中CORINFO_FIELD_HANDLE即可充当该角色源码中通过VNForFieldSelector(CORINFO_FIELD_HANDLE fieldHnd, ...)生成字段选择子见 valuenum.h。1.2 两条select-of-store规约规则当 JIT 构造一个VNF_MapSelect值时会尝试用以下两条规则进行化简M[ind : v][ind] v // 规则 1同索引直接命中 ind1 ! ind2 M[ind1 : v][ind2] M[ind2] // 规则 2异索引则继续回溯第二条规则正是性能问题的根源如果M本身是一个由大量VNF_MapStore层层嵌套构成的大复合项那么为了确定ind2处的值我们可能沿着存储历史一路回溯试图找到针对该字段的最近一次存储。在当前仓库的VNForMapSelectWork中这两条规则的实现清晰可查valuenum.cppselect(store(m, i, v), i) v当funcApp.GetArg(1) index时直接返回存储的值funcApp.GetArg(2)i ! j select(store(m, i, v), j) select(m, j)当index与 store 的索引都是 VN 常量IsVNConstant时代码注释明确写着Currently the only source of distinctions is when both indices are constants目前唯一能判定索引相异的来源是两者均为常量随后通过goto TailCall实现等价于递归尾调用的select(m, j)回溯。注意TYP_HEAP/TYP_MEM这两个占位类型注释指出我们把占位类型TYP_UNDEF和TYP_UNKNOWN命名为TYP_MEM和TYP_HEAP用于表示不代表标量值的映射valuenum.h而MapIsPrecise判断即基于这两个类型valuenum.h。1.3 病理示例构造函数初始化n个字段考虑一个拥有大量设为n个字段的类其构造函数依次初始化每个字段。当处理到第k个字段f_k时方法内已累积了k层嵌套的VNF_MapStore代表自方法开始以来的全部存储为了构造T$f_k字段映射的先前值需要创建一个VNF_MapSelect该构造会反复应用规则 2在之前全部k次存储中向后搜索f_k由于从未存储过f_k每次搜索都会一路回溯到初始堆值H0。于是一个含n个字段的构造函数会引发O(n²) 的搜索成本——这就是文档描述的二次方病理quadratic process。一个重要的例外对于静态字段情况并不那么糟。文档特别指出类构造函数依次存储k个不同静态字段时后续对未被存储过的另一个静态字段的查询虽然可能消耗O(k)但存储本身每次都是线性的——因为静态字段的存储不需要先读取旧值。二次方病理的关键在于实例字段的每次存储隐式地包含一次对旧字段映射的查询H0[C$f][o]从而叠加出二次成本。二、为什么不能拆分为多个独立的状态变量一个自然的疑问是既然单个堆变量引发回溯为什么不干脆为每个字段映射维护一个独立的 SSA 状态变量文档给出了两条否决理由这两条理由在今天依然成立SSA 复杂度每个字段映射的每个状态都需要独立的 SSA 变量会显著复杂化 SSA / 被跟踪变量的体系调用与堆失效场景调用call在模型中会完全摧毁堆。使用单一堆变量时只要给堆赋一个新的、对其一无所知的唯一值编号即可丢弃全部堆信息同理适用于通过未知指针的存储、volatile 变量访问等需要丢弃全部堆信息的场景。若采用逐字段映射则必须在每个此类点给方法内出现的所有字段映射逐一赋予新值——代价反而更高。当前仓库的实现依然遵循单一堆 按索引取字段映射的模型堆/内存使用TYP_HEAP/TYP_MEM占位类型表示字段映射通过VNF_MapSelect从堆值中取出循环相关的堆依赖还引入了loopIndex见VNForFunc(TypeOfVN(map), VNF_MapStore, map, index, value, loopIndex)valuenum.cpp。三、解决方案一扁平化的堆状态表示3.1 核心观察堆只按常量索引文档指出堆有一个特殊性质堆仅以常量作为索引而我们总能判定两个常量索引是否相等。这既是问题的根源索引相异时规则 2 会一直回溯也是解决方案的钥匙。对比字段映射T$f_k它是以对象引用值为索引的而我们通常无法判定两个引用值是否相等因此针对字段映射的VNF_MapSelect回溯通常会很快停止——这正是常量索引与引用索引的根本差异。3.2 扁平化表示的设计基于仅按常量索引这一性质可以引入哈希表表示在块内做价值编号时我们关心的只是堆的当前值若同一块内在某个T$f_k处更新了多次只有最近一次存储的值有意义。因此设计提出一种扁平化的堆状态表示与标准的项term表示并存扁平化形式 一个基状态base state本身可以是扁平化或 term 形式 一张更新哈希表将堆索引一般情况下包括静态/实例字段的字段句柄、数组类型的表示映射到对应值静态字段为直接值、实例字段为字段映射、数组为数组映射块内维护双形态对块做价值编号时始终同时持有当前堆状态的 term 形式与扁平化形式处理修改堆的操作时既构造新的 term 表示与现状一致也强更新哈希表——同一块内对字段f多次更新时哈希表只保留f最近一次的值常数时间查询有了扁平化形式对当前堆状态的VNF_MapSelect求值可以在期望常数时间内完成——要么在哈希表中找到当前值若该索引被更新过要么确认未更新、继续对基状态求值。3.3 块间基状态让搜索与块数成正比上述方案仍保留了一次搜索对基状态。文档提出只需让基状态也是扁平化的即可加速处理每个基本块时分配一个新的扁平化表示块处理完毕后把最终堆状态保存下来若B1是B2的唯一前驱则B1的最终堆状态直接作为B2当前堆状态的基状态若B2有多个前驱且某些前驱修改了堆则会有一个堆状态的 phi 定义此时B1的最终堆状态作为 phi 函数中对应B1的参数值。这样对当前堆状态的VNF_MapSelect回溯搜索其深度至多与路径上的基本块数量成正比而不是与执行的堆更新次数成正比。3.4 更进一步复制后状态以折叠搜索链文档还提出一个激进选项当B1是B2的唯一前驱时不再把B1的后状态作为基状态而是直接复制B1的最终状态作为B2的初始堆状态。由于两者的基状态相同都是H0当B2处理完保存自己的后状态时搜索链就被折叠了——B2后状态上的VNF_MapSelect查询若在哈希表中未命中不会再去查B1的哈希表因为已复制进B2的初始状态。这是一个时间/空间权衡优点若方法中涉及的字段总量相对较小B1与B2修改的字段常有重叠则各块哈希表最终总大小大致相当坏情况若B1与B2修改的字段集合互不相交B1修改的字段会在两个块的后状态中重复表示空间翻倍。若将折叠作为默认策略则在一个以B0为根、基状态为H0的扩展基本块EBB内所有块在VNF_MapSelect未命中时都会直接跳回H0跳过 EBB 中的任何中间块。仓库现状截至当前仓库代码扁平化堆状态flattened heap state这一方案并未以同名数据结构落地——在 src/coreclr/jit 中搜索不到对应实现。从源码结构看可以推断当前 VN 仍采用 term 形式加预算控制的方式处理堆访问扁平化构想属于文档中尚未实现的部分。四、解决方案二堆 phi 定义的查询记忆化4.1 问题phi 上的查询不能简单放弃文档指出第二个可能更糟的性能问题。如果对堆状态H做VNF_MapSelect(H, ind)而H是块B开头的 phi 定义且B的所有前驱都已编号完成我们不能直接放弃。正确做法是若 H phi(H0, …, Hk)则分别求 VNF_MapSelect(H0, ind), …, VNF_MapSelect(Hk, ind) 若这些结果全部化简为同一个值 v则该值就是 VNF_MapSelect(H, ind) 的值4.2 动机示例让 CSE 跨分支工作考虑如下源码片段… o1.f … if (P) { o2.g 17; } else { o3.h 102; } … o1.f …为了让公共子表达式消除CSE良好运作我们希望首尾两处o1.f获得相同的值编号。设H0为代码片段之前的堆值该 VN 应表示H0[T1$f][o1]。条件分支的两个分支都更新了堆——但更新的索引分别是T2$g与T3$h都不同于T1$f。然而要确定这一点并得到正确的值编号必须在条件汇合点merge point的堆 phi 定义处同时检查两个 phi 参数并用T1$f查询它们。4.3 指数爆炸的恐惧与线性解法直觉上这可能引发灾难性指数过程若有一串N个条件分支是否存在2^N条路径需要全部探索文档的结论是路径确实呈指数级但只需做线性工作量。关键在于ValueNumberStore维护了多张从函数应用到 VN 结果的哈希表记忆化/备忘录。求值一个函数应用时总是先查表看是否有已求值的结果没有才求值并记录最终结果。当前实现对中间结果通常不记录例如外层查询为VNF_MapSelect(VNF_MapStore(VNF_MapStore(H0, T3$h, v3), T2$g, v2), T1$f)会先判定T1$f与T2$g相异从而递归求值VNF_MapSelect(VNF_MapStore(H0, T3$h, v3), T1$f)它再次化简得到VNF_MapSelect(H0, T1$f)。最终只会把最外层查询的 VN 记录为结果中间层不记录。但phi 函数是一个例外——因为存在指数爆炸风险它是最值得记忆化的候选在上述示例中对条件序列中第一个分支汇合后的 phi 函数的所有参数做完VNF_MapSelect若得到一致结果H0[T1$f][o1]就把它记录到记忆化 VN 函数应用的全局哈希表中到达第一个条件分支时我们确实探索了所有后续汇合块的第一个 phi 参数路径很多但由于记忆化没有路径会进一步探索它同理第二个条件的堆 phi 定义也会被记录依次向上最终整条链只做线性工作。4.4 仓库中的落地预算、递归防护与记忆化当前 valuenum.cpp 的VNForMapSelectWork完整实现了 phi 查询逻辑并附带三重保护结果缓存MapSelectWorkCache以VNDefFuncApp2(VNF_MapSelect, map, index)为键做查找命中则直接返回valuenum.cpp递归防护SelectIsBeingEvaluatedRecursively(map, index)检测外层调用是否正在计算同一选择若是则返回RecursiveVNvaluenum.cpp避免无限递归phi 场景中还通过m_fixedPointMapSels.Push(...)/Pop()记录当前正在求值的外层 selectvaluenum.cpp预算检查if (*pBudget 0)时放弃精确求值改用VNForExpr(nullptr, type)生成一个新的唯一值编号——这与文档预算耗尽就给堆一个唯一新值的思想完全一致valuenum.cpp。phi 分支的核心代码valuenum.cpp逻辑为对select(phi(m1, m2), x)逐个对 phi 参数求select(mi, x)若全部一致且未使用RecursiveVN则将该结果写入缓存MapSelectWorkCache::Overwrite并注释明确写道To avoid exponential searches, we make sure that this result is memo-ized为避免指数级搜索确保该结果被记忆化若使用了RecursiveVN说明处于多入口循环场景则不做记忆化防止缓存到不可靠的中间结果。堆 phi 的 SSA 参数通过GetMemoryPhiDef与GetMemoryPerSsaData获取valuenum.cpp。五、解决方案三终极病理与查询预算5.1 下一个坏案例不同对象引用上的大量存储扁平化解决了大量不同字段的病理。但如果字段数量少、而对象引用值的种类多呢一般这不是问题二次方搜索源于常量索引性质能持续判定 store 字段与 select 字段相异并继续回溯对对象引用值我们通常没有机制判定它们相异虽然能判定两个变量值相同却难以证明它们不同。文档设想如果将来引入一种推理机制能判断新分配对象的引用与先前任何对象的引用都相异fresh就会出现新病理class T { public int f; } void M(T t0) { … t0.f … T t1 new T(); t1.f 1; … t0.f … T t2 new T(); t2.f 2; … t0.f … … T tk new T(); tk.f k; … t0.f … }若能判定t1, t2, …, tk均与t0相异事实上它们两两相异那么每处t0.f查询都会遍历此前所有存储总工作量对k呈二次方。5.2 扁平化在此失效文档明确指出扁平化在这里不是选项至少不容易因为我们通常不知道对象引用相异——哈希表无法在可能别名的索引间安全折叠。5.3 预算上限终极退路文档给出的应对是文档开头就埋下的逃生门out为每次堆查询设置最大预算预算耗尽即放弃精确求值返回一个新的唯一值编号——这永远是正确只是不够精确的。例如预算可定义为最外层VNF_MapSelect求值过程中递归求值的VNF_MapSelect项数的上限。仓库落地这一思想已经完全实现VNForMapSelectWork通过pBudget指针逐层递减预算(*pBudget)--见 valuenum.cpp预算耗尽时返回VNForExpr(nullptr, type)并缓存valuenum.cpp调试构建下还有JitVNMapSelLimit配置项非零时若考虑的VNF_MapSelect应用数达到该值则断言jitconfigvalues.h配套计数m_numMapSels与断言assert(selLim 0 || m_numMapSels selLim)valuenum.cpp。在DEBUG构建中可通过设置DOTNET_JitVNMapSelLimit环境变量来验证某个方法是否触发了异常规模的 select 求值详见 valuenum.h 的说明。六、Struct 值另一种映射及其取舍文档在最后还讨论了结构体struct值的建模struct 值同样被表示为映射——从结构体字段句柄到字段值的映射与堆的处理非常相似。甚至可以把堆的静态变量部分视为一个包含所有静态字段的大 struct。病理场景对一个 struct 变量vs的字段做一长串存储除字段f外随后查询vs.f——该查询必须沿着所有VNF_MapStore项回溯到原始值。为何比堆的二次方病理轻实例字段的每次存储隐式包含一次旧字段映射的查询H0[C$f][o]这是堆二次方成本的主要来源struct 字段存储则直接覆盖旧值、不查询因此一长串对 struct 不同字段的存储本身是线性的同理类构造函数依次存储k个不同静态字段也不会触发二次方病理。为何扁平化在此不适用堆场景通常不保存中间堆状态虽然某些情况下会——如 handler 块中可能作为堆 phi 的输入文档提示可以考虑在那种情况下复制当前扁平化堆状态但 struct 场景必须保存每次修改 struct 变量的某字段都会产生外层变量的新 SSA 名字其值是VNF_MapStore进先前值并随 SSA 定义一起存储——若采用扁平化会出现大量哈希表副本不可取。一个开放构想若知道 store 嵌套的高度height可以在创建新 store 时当其高度超过某个最大值例如 10时改用扁平化表示——以基值加哈希表汇总自该基值以来的存储甚至可以做成分层结构保证任意 store 嵌套上的查询只付出对数成本。文档将此列为模糊的想法尚未形成完整方案。七、总结与后续方向7.1 已明确的三大对策病理对策仓库落地状态大量不同字段导致的二次方回溯扁平化堆状态基状态 更新哈希表块间折叠搜索链未落地源码中无同名实现条件级联中 phi 查询的指数爆炸phi 查询结果记忆化已落地MapSelectWorkCache、m_fixedPointMapSels递归防护valuenum.cpp所有未知病理的兜底每查询设预算上限耗尽返回唯一新值已落地pBudget递减 JitVNMapSelLimitvaluenum.cpp、jitconfigvalues.h文档作者认为为避免编译器在某个机械生成的 100MB 方法上卡死的 bug 追踪噩梦至少扁平化、phi 查询记忆化、预算上限这三点都需要落实——从仓库现状看后两者已成为现实扁平化仍停留在设计层面。7.2 尚未成形的方向合并点堆状态合并文档最后还思考了在汇合点合并堆状态的可能性若有一个控制流菱形汇合前堆状态均为H0两个分支都对o.f赋值那么在扁平化形式下可以判断进入堆 phi 定义的两个输入堆状态都以H0为公共祖先状态进而比较各分支修改了哪些字段修改相同字段且相同对象引用若值一致可用对H0在该索引处存储该值来概括若值不一致则存入一个唯一新值丢失二者之一的信息仅一个分支存储同样丢失信息两个分支对同一字段、不同对象引用存储则不仅要分析堆的字段句柄索引集合还要分析字段映射中的对象引用句柄——复杂度陡增。文档作者坦言这些复杂性使其回避了完整提案但认为或许其他人能让它落地。这也是读者可以继续在 valuenum.cpp 与 valuenum.h 中追踪演进的方向之一。7.3 阅读建议想从源码验证select-of-store规约看VNForMapSelectWork中case VNF_MapStorevaluenum.cpp注意常量判异IsVNConstant与goto TailCall的回溯实现想验证 phi 记忆化与递归防护看 valuenum.cpp 的GetPhiDef/GetMemoryPhiDef分支以及m_fixedPointMapSels的压栈/出栈配对想了解预算与调试配置看 valuenum.hVNForMapSelectWork签名、pBudget与 jitconfigvalues.hJitVNMapSelLimit想理解堆/内存占位类型与映射分类看 valuenum.h 与MapIsPrecisevaluenum.h。【免费下载链接】runtime.NET is a cross-platform runtime for cloud, mobile, desktop, and IoT apps.项目地址: https://gitcode.com/GitHub_Trending/runtime6/runtime创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考