Andersen 包含式指针分析

每条包含边都保留信息流方向：x=y让y的可能目标流到x，却不要求x原有的目标也反向流到y。解引用则先问指针可能指到哪些单元，再为这些单元建立新的传播关系。

所以约束图不一定一次建完。刚发现a属于pt(y)时，x=*y才暴露出新的边 $a\to x$；若后来pt(a)继续增长，这条边还要继续传新事实。

写穿一层指针，再读回来 ​

考虑

p = &a
q = &b
r = p
*r = q
s = *p

这里a、b也是有地址的存储单元。起初各pt集合为空，取地址先产生pt(p)=$\{a\}$、pt(q)=$\{b\}$。复制r=p让a进入pt(r)。

因为a在pt(r)中，存储 *r=q 激活包含边 $q\to a$，于是b进入pt(a)。又因为a在pt(p)中，加载 s=*p 激活边 $a\to s$，使b最终进入pt(s)。稳定结果为

pt(b)仍为空；程序没有向单元b写入其他地址。不要把“q指向b”误读成“b指向q”，也不要把pt(a)与地址a自身混为一层。

新边必须携带旧事实 ​

若先求得pt(q)=$\{b\}$，之后才因r发现a而加入边 $q\to a$，只订阅q未来的变化会漏掉已经存在的b。可靠工作队列需要两个对称入口：新增事实时沿已有边传播；新增边时立即传播源端已有的全部事实。加载/存储的条件约束同样既处理旧目标，也登记未来目标。

流不敏感会保留已经覆盖的目标 ​

x = &a
x = &b
y = x

本分析给pt(x)=pt(y)=$\{a,b\}$。真实执行到最后时x和y只指b，但分析有意丢掉语句顺序，不能进行“第二次赋值杀掉a”的强更新。这个伪别名来自流不敏感，而非包含方向做错。

相反，若程序为 p=&a; q=&b; r=p; r=q，包含分析保留pt(p)=$\{a\}$、pt(q)=$\{b\}$，只有pt(r)=$\{a,b\}$。Steensgaard合一分析公理库Steensgaard 合一式指针分析Steensgaard pointer analysis · Unification-based points-to analysis把可能别名合成等价类为什么更快，又会在哪个小程序上丢掉精度。会用更粗的目标等价类换取更低成本；这组例子可以精确比较差别。

一套有界工作队列 ​

维护每个x的目标集合及包含后继列表。发现新事实 $(a,x)$ 后，将它加入队列一次。弹出时，一方面沿x已有的包含边传播a，另一方面检查以x为指针的load/store约束，为a生成新的包含边。每条新边在安装时推送源端现有目标。

若程序大小为n，抽象单元及规范化语句数量均为 $O(n)$，最多有 $O(n^2)$ 个“单元、目标”事实和 $O(n^2)$ 条包含边。适当去重后，每个事实沿每条相关边传播、每条新边接收旧事实的总工作可按三元组合计为 $O(n^3)$，空间为 $O(n^2)$。反复重扫全部约束的教学实现虽然也终止，不应未经计数就冒充这个工作队列界。

可靠性来自抽象解释公理库抽象解释Abstract interpretation · Theory of sound static approximation以具体与抽象语义、可靠转移和不动点逼近统一组织静态程序分析的数学框架。式的不变量：每次具体存储中出现的有效指针边，在对应抽象单元的pt集合中都有代表。取地址直接加入代表；复制用包含传播；load/store按所有可能目标覆盖实际被访问的那个单元。将这些局部步骤归纳到执行，就得到全局may-points-to覆盖。

最小约束解不等于最精确的全部流不敏感语义。路径相关性、不同指针事实能否同时成立、语句规范化引入的临时值，仍可能造成额外近似。可靠的共同目标是不能漏真实地址，不是保证每条静态边都能在某次执行实现。

字段敏感扩展可用 $(h,f)$ 表示抽象对象h的字段f；把全部字段合成一个槽更省空间，却可能让不同字段的目标串在一起。和调用图联合求解时，新函数地址也会激活新的参数/返回约束，因此不能预先假定调用图永远不变。

对象敏感分析公理库对象敏感指针分析Object-sensitive pointer analysis · Object sensitivity为什么用接收者的分配身份区分方法实例，比仅记调用位置更适合某些面向对象程序。进一步按接收者身份区分方法中的变量与参数传播。字段敏感区分“同一对象的哪个字段”，接收者上下文区分“同一方法正在处理哪个抽象对象”；两者可以组合，却不是同一项精度选择。

练习与解答 ​

在主例最后增加 t=*r，能否断定pt(t)只有b？答案可以：pt(r)只有a，故新增边 $a\to t$；pt(a)只有b，传播后pt(t)=$\{b\}$。若再加入 r=&c 和 c=&d，则pt(r)扩大为 $\{a,c\}$，加载多出 $c\to t$，pt(t)变成 $\{b,d\}$。验收要指出是哪条新地址事实激活了哪条新包含边，而不是直接猜最终集合。