Steensgaard 合一式指针分析

Andersen允许p只指a、q只指b，而r指a或b。Steensgaard要求r只有一个目标代表，所以把a和b装进同一个位置类；此后任何指向该类的指针都可能指其中任一成员。

这会把一条新别名传播到原本较精确的其他指针，但不需要反复维护任意大的目标集合。等价类只能合并、不能拆开，有限代表数量给出很低的更新成本。

一个合并为何影响三个指针 ​

执行分析以下语句，顺序只用于展示求解过程，不作为流敏感杀死信息：

p = &a
q = &b
r = p
r = q

前两句令 $T_p$ 与 $L_a$ 同类，$T_q$ 与 $L_b$ 同类。因为变量位置本身都有ref形状，第三句的源目标 $T_p$ 已非底，故把 $T_r$ 与 $T_p$ 合并；第四句同样把 $T_r$ 与 $T_q$ 合并。

于是 $L_a,L_b,T_p,T_q,T_r$ 属于同一代表类，读出的结果为

相比之下，包含分析只让r得到两目标，p仍只有a、q仍只有b。额外目标来自等价类合并，不是程序真的把q的值写进了p。

变量p和q自己的位置代表 $L_p,L_q$ 不因此必须合并。若还写 u=&p、v=&q，不应仅凭p、q目标相同就断言u、v都指向同一变量位置。目标层与容器层必须区分。

条件合并保留了什么 ​

先遇到 x=y，此时 $T_y=\mathrm{\perp }$，算法只登记 $T_x$ 等待 $T_y$。随后处理 x=&a，x获得目标a，但y仍无指针事实；原版不会仅因这次单向赋值就把a反向灌给y。

若后来出现 y=&b，$T_y$由底变为有形状，待办才触发，与已有的 $T_x$ 合并，最终两者指向含a、b的同一类。这个例子说明条件合并保留部分方向信息，但一旦源端有了指针形状，合并仍会产生对称的粗化。

如果直接为每条赋值无条件join，第一种程序就会让y也指a。这依然可以是可靠的更粗分析，却不再是这里给出的原版条件合并结果。

自指针不是类型错误 ​

语句 x=&x 使 $T_x$ 与 $L_x$ 合并，从而出现形如 $L_x=\mathrm{ref}(L_x)$ 的循环形状。运行时自指针完全合法，分析应以有限循环图表示它，不能照搬有限类型树一阶统一公理库一阶统一First-order unification · Syntactic unification寻找使若干一阶项在替换后相等的最一般替换。里的occurs check并拒绝程序。

这里的“类型”是存储形状，不是源语言的Int、Bool等静态类型。只用ref一种形状构造器时，合并的职责是保守覆盖地址关系，不是发现通常意义上的类型不匹配。

一次赋值只产生常数个代表及合并约束，整个规范化程序产生 $O(n)$ 个代表。每次真正join都减少等价类数量，所以最多线性次；递归合并子形状的成本可归到这些实际合并。配合路径压缩与按秩合并，核心求解为 $O(n\alpha (n))$ 时间、$O(n)$ 紧凑形状空间，其中 $\alpha$ 是增长极慢的反Ackermann函数。待办集合也须采用可高效合并和消费的表示，不能在每次join时复制整张大列表。

线性空间描述的是共享等价类图。若对每个变量显式打印其可能目标列表，许多变量可以指向同一个大类，输出总长仍可能为 $\mathrm{\Theta }(n^2)$；不能把紧凑解的成本当成完整展开报告的成本。

可靠性建立在存储形状对具体地址边的覆盖上。join只扩大类而不删地址，解引用规则确保目标单元的内容形状与读写源相容；条件合并在源端没有信息时延迟，但一旦有信息就执行全部必要合并，因此不会永久漏掉约束。

用于大程序的初筛时，较粗结果可能仍足以证明很多地址互不相关。若关键告警恰由大等价类造成，可以只对相关区域改用包含分析或更细上下文，而不是假定一种分析在所有精度/成本维度都占优。