10|IDE 求解器如何扩展到大程序?
第 08 篇的跳转函数 〈源事实,目标点,目标事实,函数〉 在大程序中数量庞大,存储与访问成本可能成为瓶颈。
ECOOP 2024 论文 Scaling Interprocedural Static Data-Flow Analysis to Large C/C++ Applications: An Experience Report(Schiebel、Sattler、Schubert、Apel、Bodden)优化了跳转函数表的布局与条目回收。以下用自建条目说明布局、批处理和回收,性能数据引用论文实验。论文与出版信息
1. 跳转函数的访问成本
假设节点 n 处有三条跳转函数:
| 源事实 d₁ | 目标事实 d₂ | 函数 |
|---|---|---|
| p | a | t↦t+2 |
| p | b | t↦5(t+2) |
| q | b | 恒等 |
更新一条记录需要查找旧函数、合并新贡献,再判断是否入队。即使条目数相同,容器中的重复键、内层表、散列、扩容与额外索引也会带来不同的时间和空间成本。
2. 按访问方式选择映射布局
论文第 4.1 节比较的候选布局包括(下标表示外层映射用的键:N 是节点,D 是源事实,E 是出口摘要 EndSummary):
| 名称 | 结构 | 外层固定后还要查什么 |
|---|---|---|
| JF_old | n → d₁ → d₂ → f | 源事实、目标事实 |
| JF_ND | (n,d₁) → (d₂ → f) | 目标事实 |
| JF_N | n → ((d₁,d₂) → f) | 源目标事实对 |
| JF_NE | JF_N 加独立的出口摘要表 | 同 JF_N;出口摘要另查独立表 |
JF_old 在新求解器中保留了原来的嵌套形状,但移除了旧实现维护的多索引,比较实验时需要计入这项差异。论文第 4.1 节
在我们的三条记录中:
- JF_ND 为
(n,p)和(n,q)各建立一个内层表。 - JF_N 只为 n 建立一个内层表,里面有
(p,a)、(p,b)、(q,b)三个键。
若经常一次处理固定 n 下的很多事实,JF_N 能共用一次外层查找;若经常固定 n、p 查询,JF_ND 的内层表更直接,但可能需要更多小表。
3. 批处理:复用外层查找
原本每次更新都从总表查起(下面以 JF_N 的形状为例):
for 每个目标事实 d2:
old = table[n][d1,d2]
new = old ⊔ candidate
有变化则保存并调度若这一批的 n 固定,可把查找移到循环外:
row = table[n]
for 每个目标事实 d2:
old = row[d1,d2]
new = old ⊔ candidate
有变化则保存并调度本例用 Join 表示函数合并,论文按自己的顺序写 Meet;存储优化不改变合并语义。一次批处理包含 k 次更新时,外层定位由 k 次降为一次,内层更新和变化检测仍然都要做。
论文算法 1 将这样的局部视图传给 Propagate(论文中“把一条跳转函数合并进表并按需入队”的过程),在保留全部更新的同时复用查找结果。论文算法 1 与表 2
4. 有了摘要,能把方法内部条目全删掉吗?
条目回收(garbage collection,GC)释放后续不再需要的记录。判定条件来自 Arzt 的 IFDS 多线程 GC(ICSE 2021,Sustainable Solving: Reducing the Memory Footprint of IFDS-Based Data Flow Analyses Using Intelligent Garbage Collection);本篇论文将它改为单线程定点调用,并扩展到 IDE。
calc 内部保存 p→a、p→b,出口保存 p→ret。部分内部条目可以回收,但摘要应用可能触发新传播,IDE 第二阶段也可能还要用它们求值,因此不能在摘要生成后立即全删。
论文第 4.2 节将生命周期与两类工作列表结合:
- PathWorkList:待处理的向前传播。
- RetWorklist:待应用到调用者的摘要。
回收某过程的中间条目,需要确认两个列表中都没有该过程或其传递被调用者的待办;还要保留后续需要的结果与值传播信息。论文第 4.2.2 节明确列出的保留项有两类:感兴趣节点(interesting nodes,客户端要查询值的位置,例如类型状态分析的状态转移语句、常量分析的分支条件)和所有调用点(阶段二算过程入口值要用)。出口摘要不可回收则是从 Arzt 的原设计和论文第 6.2 节对 JF_NE 的讨论推出的,论文正文没有单独列出。
假设 p 调用 q,此时:
- q 的摘要刚产生,仍在返回列表里等待应用给 p。
- 若此时只看到 PathWorkList 里没有 p 的条目就回收 p,后续摘要应用又会要求继续处理 p。
- 按回收条件,q 是 p 的被调者、q 又在 RetWorklist 里,所以 p 不满足条件;等 q 的摘要应用完并处理完由此产生的新任务,才能回收 p 的中间条目。
论文先处理完 PathWorkList,再处理完 RetWorklist,随后调用回收(算法 3 第 9 行)。此时返回应用可能已向 PathWorkList 加入新任务,回收仍须检查两个列表;外层循环继续,直到二者都为空。论文算法 2、3 与第 4.2.2 节
若业务必须查询所有节点的值,内部节点也都需要保留,回收空间就会缩小,甚至完全消失。
5. 实验结果与比较基线
论文评估了 31 个 C/C++ 程序,使用类型状态分析(Typestate)、线性常量分析(LCA)和指令交互分析(IIA);三者的事实域从稀疏到稠密依次增大,IIA 的事实数接近程序点数,是最重的负载。实验节点为 AMD EPYC 72F3,内存限制 250 GiB,超时限制四小时。下表来自表 3,列出平均比值及标准差;比值大于 1 表示改善,小于 1 表示该项变差:
| 分析 | 内存:旧/新 | 时间:旧/新 |
|---|---|---|
| IIA | 4.811 ± 1.192 | 7.227 ± 2.042 |
| LCA | 1.729 ± 0.365 | 4.683 ± 2.150 |
| Typestate | 0.968 ± 0.050 | 1.162 ± 0.143 |
比较双方是原 IDESolver 与论文的新求解器 IDESolver++(使用 JF_old 布局)。 7.227 倍反映了索引、批处理等实现的整体变化。Typestate 的内存比小于 1,论文给出的原因是新求解器预分配了较大的缓冲区,而 Typestate 事实太稀疏、填不满。论文第 6 节,尤其表 3
换布局与开回收的增量收益由另外两组实验测量(论文第 6.2 节,表 4、图 6)。论文自己的结论是:没有对所有分析都最优的布局——JF_N、JF_NE 在 LCA 上内存最省,IIA 上反而是 JF_old 运行最快;单线程 GC 让 LCA 的内存平均降低约 12%(标准差约 10%),对 Typestate 几乎没有作用(不到 1%),并带来百分之几的运行时开销。把两项优化合起来(第 6.5 节),IIA 的内存与时间各改善约 6.9 倍,LCA 约 2.7 倍与 4.9 倍,Typestate 没有明显改善。不同分析的事实数量和稀疏程度不同,收益不能直接移植到 Java 污点分析。
还需将“完成的任务”“超时”“内存不足”一起看:从内存不足变为超时,不等于已经完成,也不必然意味着算法变慢。仅统计成功案例的平均耗时会遗漏这些差异。
6. 同一问题的其他路线
论文基于 PhASAR 优化存储与访问。还可以减少传播工作量,或改变工作的执行方式:
| 路线 | 做法 | 减少的成本 | 代表 |
|---|---|---|---|
| 稀疏化 | 事实只在定义与使用它的语句之间传播,跳过与该事实无关的程序点 | 恒等边的传播次数与路径边数量 | He 等,Performance-Boosting Sparsification of the IFDS Algorithm(ASE 2020);SVF 是另一类基于稀疏值流图的框架 |
| 按需求解 | 只从查询点出发,向前或向后探索到足以回答的范围 | 与查询无关的整程序传播 | Boomerang 的按需别名查询;同步下推系统同时处理调用与字段两种括号(两类括号精确匹配一般不可判定,见第 07 篇选读第 6.3 节) |
| 摘要复用 | 跨方法复用摘要,库方法预先算好摘要 | 重复分析的工作量 | FlowDroid 与 StubDroid 的方法摘要 |
| 并行与增量 | 多线程或 GPU 并行求解;代码改动后只重算受影响部分 | 挂钟时间;增量还减少重算的工作量 | Reviser(Arzt 与 Bodden,ICSE 2014)的增量 IFDS/IDE;Arzt 2021、He 等 2023 的多线程求解与回收;Yu 等 2020 的 GPU 并行 |
稀疏化需要定义使用关系,按需求解需要具体查询,回收依赖调度不变式。摘要复用减少重复工作,回收减少保留的条目,并行主要缩短挂钟时间;应按实际瓶颈选择或组合。
7. 怎样迁移到自己的求解器?
- 记录跳转函数条目数、各索引规模、容器分配,以及最频繁的查询键组合。
- 对固定节点的一批更新,测试复用内层表能节省多少查找,同时测量小表增多的代价。
- 固定输入、模型、种子与预算,分别测量布局、批处理和回收的收益。
- 比较优化前后各查询点的值与报告,确认结果一致。
- 同时记录内存峰值、耗时、超时与 OOM,让未完成的任务也进入对照。
本篇要点
- 布局与批处理应贴合查询方式,减少容器和重复查找的成本。
- 回收须检查两个工作列表中的本过程及传递被调者,并保留查询点、所需调用点与出口摘要。
- 性能倍数依赖比较基线与分析负载,不能直接移植到 Java 污点分析。
- 优化前先测瓶颈,优化后核对结果,并将超时与 OOM 纳入评估。
对象别名在下一篇展开;库建模与反射等后续专题见系列总览。
