返回学习路线

D02：分清返回错误、地址合并与活引用 ​

两种分析都报告第二次调用可能执行F。它们的错误来源却可能不同：一张图接错了返回边，另一张图的返回完全正确，只是把两次形参绑定装进了同一个槽。本题用给定程序、存储和根集合把这两种情况拆开。

题目：同一个函数，两种调用者 ​

采用词法作用域、从左到右的按值调用。F、G和M都是无自由变量的全局函数：

F() = 0
G() = 1
M(x) = { x(); return (λ(). x); }

M先调用实参函数，再返回一个捕获本次x的闭包。记第一次返回的闭包为H。下面let的作用域由缩进给出；discard先求值、再丢弃结果，不保留其引用。c₁、c₂是两处调用M的程序标签，r₁、r₂是对应返回点。

P_drop:
  discard (let h = M(F) @c₁ in 0);
  discard M(G) @c₂;
  return 0

P_keep:
  let h = M(F) @c₁ in
    discard M(G) @c₂;
    return (h())()

P_keep末尾先调用H得到第一次保存的F，再调用F。P_drop中h在内层let结束后不可访问。

本题用环境、存储和返回栈组成的抽象机器。存储随状态保存，绑定向已有槽加入候选值；收集只限制当前状态的存储。下面的“0-CFA式”和“1-CFA式”专指地址分配，不把它们等同于一张全局共享存储上的完整分析实现。

全局槽固定保存相应闭包，闭包本身不引用其他地址。本题始终把三个全局槽作为根，记 $B=\{bF,bG,bM\}$。H只捕获x：0-CFA式分配中 $H=(\lambda ().x,\{x\mapsto a\})$；1-CFA式分配中把a换成a₁。当前环境可以包含额外历史条目，但根只包括当前表达式、待执行续延及全局接口仍可读取的地址。

检查点位于第一次调用已经返回、P_drop的内层let已经退出、第二次调用尚未进入时。此时当前表达式均为M(G) @c₂。给定0-CFA式分配的GC前存储：

P_drop的h条目是此前绑定留下的历史内容，已经没有活引用。两种程序的续延及根如下：

1-CFA式检查点的表完全相同，只把地址a及H捕获的a换成a₁；a₂尚未分配。

请完成以下任务：

1. 列出两个具体程序依次调用F、G所得的整数，确认第二次M调用的x()只能调用哪个函数
2. 对两种地址分配、两种程序，逐轮计算 $R_{i+1}=R_i\cup \mathrm{Refs}(\hat{\sigma }(R_i))$，列出GC后存储的定义域
3. 在检查点“不收集”或“收集一次”后进入c₂，把G加入分配给x的槽。列出第二次x()读取的候选函数，并说明P_keep最终的H读取什么
4. 给出一条错配返回的图路径，以及一条返回匹配正确但x取到F的伪函数流；判断调用上下文、下推栈和抽象GC分别能消除哪一种

答案一：先确定真实执行 ​

P_drop在第一次M中调用F得到0，在第二次M中调用G得到1，所以被调用函数的返回值依次为0、1；主程序最后返回0。P_keep先得到0、1，最后调用H取出F，再调用F得到0，所以这些整数依次为0、1、0，主程序也返回0。

两种程序的第二次M都只收到G。真实执行为两次M创建不同的局部x绑定；H保存的是第一次绑定，不会被第二次调用改写。分析中把它们映射到同一个a，是近似造成的重合。

答案二：逐轮求根闭包 ​

对0-CFA式P_drop，$R_0=B$。B中的三个闭包没有自由变量，因此 $R_1=B=R_0$，闭包已稳定。回收后存储的定义域为B，a和h一起删除。虽然存储中有一条h到a的引用边，但没有根能到达h，这条孤立边不会让二者存活。

对0-CFA式P_keep，$R_0=B\cup \{h\}$。读取h中的H发现捕获地址a，故

a中只有无自由变量的F，所以没有新的引用边。回收后五个槽全部保留。h不是当前表达式M(G)的自由变量，却是续延里(h())()要读取的变量；漏掉续延根会错误删除一个真实会用到的闭包。

对1-CFA式P_drop，仍有 $R_0=R_1=B$，定义域为B。对1-CFA式P_keep，

定义域为 $B\cup \{h,a_1\}$。两种分配都能识别H仍然存活；它们的差别发生在第二次绑定选择哪个槽。

答案三：进入第二次调用 ​

下表只观察c₂入口已绑定x、尚未执行其x()的时刻。没有收集的各行保留给定检查点中的全部历史内容；有收集的各行先执行上一节的限制映射，再加入G。

0-CFA式P_drop中，收集先把不可达的a删掉，所以弱更新从空槽得到{G}。0-CFA式P_keep不能删除a：H仍要访问它。第二次绑定因此把G加入{F}，得到{F,G}。这时H也捕获a，最终h()会被分析成可返回F或G，尽管具体执行只返回F。GC保住了真实引用，却无法拆开一个同时代表两次绑定的地址。

1-CFA式P_keep中，H捕获a₁，第二次绑定使用a₂。因而a₁:{F}和a₂:{G}可同时存活，H仍只读取F。这里精度来自本题两个不同的调用标签；若改成循环中同一标签反复调用M，长度一的上下文未必还能区分各次绑定。

答案四：两种伪路径的修复各有依据 ​

第一种是返回错配。在共享M入口和出口的普通过程间图中，可以连出

这条图路径从第一次调用进入，却越过r₁跳到第二次调用的返回点。沿途栈先压入c₁，退出时却要求弹出c₂，因此不是真实执行。下推分析按栈顶匹配返回，直接排除它；IFDS等有效路径算法也能排除它。仅把x分到a₁、a₂，或删除垃圾槽，都不自动修复一张仍允许任意返回边的图。按上下文复制过程时还须正确连接对应返回边，不能把“用了上下文”当作无需检查边的理由。

第二种是地址合并。在0-CFA式P_keep中，沿合法的c₂调用进入M，栈顶确为c₂，x也确实读取a。只是a存着{F,G}，分析便允许此次x()选择F，执行后仍正常返回r₂。调用和返回标签全部匹配，这条伪函数流不会被下推栈排除。收集也不能删掉a，因为H活着；本题的1-CFA式地址分配则以a₂把第二次绑定隔开，消除这条伪流。

在P_drop上，同样的地址伪流还可被检查点GC消除，因为旧a没有活引用。这正是两个程序必须一起检查的原因：只看P_drop，会误以为GC总能代替更细的地址分配。

验收标准 ​

• 根闭包应分别稳定在B和 $B\cup \{h,a\}$，1-CFA式把a换成a₁；必须写出续延贡献的h
• 八行候选表中，只有0-CFA式P_drop的收集开关改变第二次x()结果
• 保留H时，0-CFA式GC不能删a；1-CFA式可以同时保留a₁而让第二次调用只读取a₂
• 两条伪路径必须有不同的证据：第一条的调用/返回标签不匹配，第二条标签匹配但候选值过多
• 不能把本题的状态局部收集规则直接套到跨路径共享的一张全局存储上

相关概念：上下文敏感过程间分析公理库上下文敏感的过程间分析Context-sensitive interprocedural analysis · Interprocedurally valid paths把函数出口连回所有调用者会产生什么假执行，调用串和摘要怎样约束返回。、k-CFA公理库k-CFA 高阶控制流分析k-CFA · 0-CFA · Higher-order control-flow analysis函数也是值时，怎样有限地近似每个调用点可能遇到哪些闭包。、下推控制流分析公理库下推控制流分析Pushdown control-flow analysis · Pushdown CFA只让堆和环境有限抽象而保留真正的调用栈，能消除哪类高阶调用返回伪路径。、抽象垃圾回收公理库抽象垃圾回收Abstract garbage collection · Abstract GC在静态分析中删除已不可能被访问的抽象存储内容，为什么会让后续结果更精确。。