k-CFA 高阶控制流分析

运行时每次进入函数都会建立新绑定，递归可以建立无穷多个。k-CFA用有限调用后缀给这些绑定贴标签；后缀相同的绑定共用一个抽象槽。槽里保存多种值，读槽时便可能产生多个后继。

0-CFA像只按变量名字设邮箱：identity的形参x收到过哪些函数，全放进同一箱。1-CFA再按“从哪个调用点送来的”分箱。它与调用串上下文敏感性公理库上下文敏感的过程间分析Context-sensitive interprocedural analysis · Interprocedurally valid paths把函数出口连回所有调用者会产生什么假执行，调用串和摘要怎样约束返回。共享截断思想，但还必须处理高阶闭包的词法捕获。

两次 identity 的函数结果 ​

表面程序为

id = λx.x
f = id(λu.u)          // c1，闭包标签A
g = id(λv.0)         // c2，闭包标签B
pair(f, g)

两次调用在不同的源位置。CPS转换显式带上各自的返回续延，而c1、c2仍标识进入id的两次调用。

0-CFA只为形参x保留地址 $(x,\epsilon )$。两次调用令它含A、B；id体读x时两者都可能返回，于是f与g的近似结果都含 $\{A,B\}$。真实结果却是f=A、g=B。

1-CFA分别分配 $(x,[c_1])$ 与 $(x,[c_2])$，并将相应续延参数也按调用上下文区分。在这个例子中，前者只含A，后者只含B，因此两次结果不再串线。

这里比较的是同一套闭包/调用语义，只改变历史截断；不能同时换掉返回建模后把全部改进归给k。

捕获环境不能在调用时重建 ​

考虑 make = λa. λb. a。分别在c1、c2调用make传入A和B，得到两个函数。它们的函数体同为 $\lambda b.a$，但捕获的a地址分别来自c1与c2。若只存函数体标签而丢掉环境，两值会被合并，后续调用仍可能返回A或B。

经典正k-CFA保留这种环境组合；只给每个函数体配一个创建上下文、再复制自由变量值的某些多项式变体，是另一种近似。二者都可以可靠，但不能在定义与复杂度之间悄悄切换。

增加k并不等于保留完整历史 ​

调用链的末尾若分别为 $c_1,d$ 与 $c_2,d$，k=1都只剩 $[d]$。若一个参数正是在d进入的函数中绑定，两路值仍会合并。递归重复同一个调用点更会不断复用相同后缀。

只增加k也不修复所有数值分支不精确、堆对象合并或不可达闭包的残留。抽象垃圾回收公理库抽象垃圾回收Abstract garbage collection · Abstract GC在静态分析中删除已不可能被访问的抽象存储内容，为什么会让后续结果更精确。可删除已经无法再访问的旧槽内容，处理的是另一种精度损失。

固定k与有限程序后，抽象调用历史有限，地址、环境、闭包和存储都只从有限集合组合，因此穷尽工作队列能终止。可靠性按具体步与抽象步对应证明：真实函数值在候选集合里，真实绑定地址映到选定抽象地址，取并保留原有别名所需值，闭包环境保证自由变量指向正确绑定的近似。

这项有限性不等于统一的低次多项式时间。若调用点数为c、变量数为v，地址数至多 $v\sum _{i=0}^k{c}^i$；但一个含r个自由变量的闭包还可有许多地址环境组合。经典正k-CFA的成本可能很高，不能只数调用串就宣布整体 $O(n^{k+1})$。0-CFA的标准约束化版本则可以用三次时间算法求解；采用不同环境抽象的工程变体应另外命名和报告界。

分析得到的函数流集合可用于间接调用图、内联候选、逃逸检查与类型恢复。若某调用点只有一个可能闭包体，优化仍要检查效果、捕获值和语言语义；“目标唯一”不自动保证随意移动或删除该调用。

练习与解答 ​

对make例子，写出1-CFA中两个 $\lambda b.a$ 的抽象闭包。答案为 $(\lambda b.a,\{a\mapsto (a,[c_1])\})$ 与 $(\lambda b.a,\{a\mapsto (a,[c_2])\})$，忽略不相关绑定。调用它们时，形参b获得新地址，a仍使用原捕获地址。

验收重点是两个层次：进入函数的当前上下文决定新形参，创建闭包时的环境决定旧自由变量。若把所有变量一律解释为当前调用上下文，词法作用域已经被错误改成动态作用域。