抽象垃圾回收

有限地址分析公理库k-CFA 高阶控制流分析k-CFA · 0-CFA · Higher-order control-flow analysis函数也是值时，怎样有限地近似每个调用点可能遇到哪些闭包。经常让多次绑定复用同一槽。若槽从第一次绑定一直保存旧闭包，第二次绑定只会把新闭包加入，结果越来越混杂。运行时垃圾回收会在没有任何引用时释放对象；抽象GC则在没有任何可能引用时删除旧槽，让后续抽象分配不必与已死亡的旧值合流。

它改变的是分析状态，不是在生成程序中插入一次运行时GC。分析可以证明旧值已经不可再访问，即使实际语言的内存管理器选择晚一点才释放。

一个抽象槽怎样被旧函数污染 ​

假设两次短暂调用都为形参x分配抽象地址a。第一次把闭包F放到a，调用结束后，当前表达式和全部续延都不再引用x；a没有逃逸到其他闭包或外部对象。

不做收集时，第二次绑定G使用弱更新，得到

第二次调用体再读取x时会考虑两个函数，产生伪控制流。若在两次调用之间检查根可达性，发现a不可达，先删除它，那么第二次分配从空槽加入G，得到 $\{G\}$。

关键条件是第一次绑定真的已经不可达。若返回了一个捕获x的闭包H，而当前环境仍保存H，则根先到H所在槽，再沿其捕获环境到a；收集不能删a。只有“变量名字离开表面作用域”并不足以判断生命周期。

续延也是根 ​

考虑先保存x=F，再计算一个内部调用，返回后还要执行 x()。内部调用当前表达式可能完全不出现x，但它的返回续延包含随后调用x的代码及环境地址a。若只从当前表达式取根，就会错误删掉a，等返回时缺少F，甚至把真实调用路径分析成不可能。

正确根集合同时包括续延帧。类似地，一个闭包槽内可能有H1和H2，只有H2捕获a；只沿H1遍历也不可靠，因为H2仍是该状态允许的值。

不能跨路径清理一张全局事实表 ​

一处分支使a死亡，另一处分支仍把a保存在活闭包中。若分析先处理死亡分支，就从全局store删掉a，稍后处理另一分支可能丢失真实值。正确做法是保留每个抽象状态自己的存储，或为共享存储的优化设计并证明专门的GC规则。

因此抽象GC并非“在任何单调分析中定期删掉看起来不用的集合元素”。收集规则必须与状态表示、可访问关系和求解方式一起设计。

给定一个有限抽象存储图，使用深度优先搜索公理库深度优先搜索Depth-first search · DFS沿未访问边尽可能深入后回溯的图遍历算法。或工作队列即可求R。时间为可访问地址数加引用边数，记为 $O(A+E_r)$；建立或复制受限存储的成本还取决于持久映射表示。每个分析步骤都收集可能较贵，可以在指定时机收集；延后通常损失部分精度，但不能随意缩小根集合来加速。

可靠性的核心是：若具体状态被当前抽象状态覆盖，任何未来具体读取先沿环境、续延或已可达值的引用链找到地址，那么对应抽象地址也在R中。归纳一条引用链，收集删除的槽不会参与这些读取。重新分配到同一个抽象地址时，删除的是已经死亡的旧绑定，而不是抹去仍存活的别名。

抽象GC有时能减少后继分支，从而既更精确又更快，但不是所有程序都会改善。一个长寿命根捕获大量地址时，很多旧内容仍必须保留；GC自身也有遍历成本。报告效果应同时看状态数、时间和剩余伪路径。

下推CFA公理库下推控制流分析Pushdown control-flow analysis · Pushdown CFA只让堆和环境有限抽象而保留真正的调用栈，能消除哪类高阶调用返回伪路径。保留无界栈，普通下推转移只看栈顶，而GC需要整栈的根地址。二者结合需用可达根摘要或受限的栈检查机制。简单把有限栈扫描代码移到无界下推模型上，会越过其可判定算法所依赖的接口。

单元终局任务：一份精度诊断报告 ​

分清返回错误、地址合并与活引用给出两个完整程序、0/1-CFA式地址分配、GC前存储，以及当前表达式和续延各自贡献的根。题解逐轮计算可达闭包，再比较八种配置下第二次调用的候选函数。

做完应能分别识别“调用与返回不匹配”和“返回正确但旧值混入新绑定”这两类伪路径，并解释为什么保留捕获闭包H时，GC必须留下旧地址，而更细的地址分配仍可把两次绑定分开。