指向分析（Points-to Analysis）

指针可以指向局部变量、全局变量或动态分配的对象，还可以通过其他指针间接读写。编译器如果不知道一次间接访问可能涉及哪些内存，就只能保守地保留许多加载、存储和函数调用。

指针分析（Pointer Analysis）是研究这些访问关系的一类分析。本节重点介绍其中的指向分析：计算某个指针可能指向哪些抽象内存对象。上一节的别名分析则关注两个访问是否可能涉及相同或重叠的内存。指向分析可以为别名分析提供信息，但两者的问题并不完全相同。

本节从指向集合开始，介绍基于包含约束的 Andersen 分析、基于合一的 Steensgaard 分析，以及精度与代价之间的取舍，最后实现一个简化的约束求解器。

从具体地址到抽象对象

程序运行时，指针保存的是具体地址；静态分析通常不追踪每次执行的地址，而是用抽象内存对象表示一组可能的存储位置。

int x = 0, y = 0;
int *p = &x;
int *q = p;
q = &y;

我们用 o_x、o_y 表示变量 x、y 对应的对象，用 pt(p) 表示指针 p 的指向集合。分析结果取决于是否区分语句的执行顺序：

• 如果追踪每个程序点，最后一行之后可以得到 pt(p) = {o_x}，pt(q) = {o_y}。
• 如果把整个函数中的约束统一求解，不区分程序点，通常得到 pt(p) = {o_x}，pt(q) = {o_x, o_y}。

第二种结果不够精确，但仍然包含所有实际可能的目标。这样的“可能指向”分析通常称为 may-points-to 分析。

静态分析要求保守：可以多包含一些实际上不会出现的目标，不能遗漏可能发生的访问。对于无法建模的外部输入、未知函数或地址运算，需要使用未知对象等保守表示，不能直接把它们当作空集合。

对象怎样划分

内存来源	常见抽象方式	可能损失的信息
局部变量、全局变量	每个变量对应一个对象	跨调用合并局部对象时可能丢失调用区别
malloc 等动态分配	每个分配位置对应一个对象	同一位置在不同执行次数中分配的对象被合并
结构体	每个结构体一个对象，或每个字段一个子对象	不区分字段时，成员访问容易互相干扰
数组	整个数组一个对象，或按元素、区间划分	合并元素时无法区分不同下标

例如循环中的同一个 malloc 调用可以创建上千个对象，按分配位置抽象会把它们归入一个抽象对象。这使集合保持有限，也引入了额外的可能关系。

指向集合如何帮助判断别名

考虑只包含完整标量对象、没有字段偏移的简化模型：

pt(p) = {o_x}
pt(q) = {o_x, o_y}
pt(r) = {o_z}

p 与 q 的集合相交，因此可能别名；p 与 r 的集合不相交，因此在该模型下可以判定不别名。

集合相交并不能直接证明“一定别名”。例如 p 与 q 可能分别来自互斥分支，不同路径上的关系在合并时会丢失。即使两个集合都是同一个抽象堆对象，也可能只是指向同一分配位置产生的不同运行时对象。

真实编译器还需要考虑访问大小、字段偏移和对象重叠。两个指针指向同一个结构体，并不代表对不同字段的访问会冲突。因此，指向集合是别名查询的输入之一，而不是所有别名结论的完整替代。

基于包含约束的 Andersen 分析

Andersen 分析把指针操作转换为集合包含关系，再不断传播目标，直到所有约束都满足。经典形式通常是流不敏感、上下文不敏感的；这些是常见配置，不代表包含约束只能用于这一种精度。

为了先看清核心算法，我们只考虑四种规范化语句：取地址、复制、间接加载和间接存储。复杂表达式可以先拆成临时变量上的简单操作。

四种基本约束

语句	含义	约束
p = &x	取对象地址	o_x ∈ pt(p)
p = q	复制指针	pt(q) ⊆ pt(p)
p = *q	从 q 指向的对象中读取指针	对每个 o ∈ pt(q)，pt(o) ⊆ pt(p)
*p = q	向 p 指向的对象中写入指针	对每个 o ∈ pt(p)，pt(q) ⊆ pt(o)

这里需要区分两层含义：o_x 表示变量 x 的存储位置；如果 x 自身存放指针，pt(o_x) 就表示这个位置中可能保存的指针目标。非指针对象没有需要传播的指针内容。

直接指针变量可以视为其存储对象的简写：后面的求解器把 p 同时用作变量节点和该变量的存储对象标识，以便演示 &p 和间接访问之间的联系。实际实现也可以将变量值节点与内存对象节点分开，并显式连接读写关系。

一个包含二级指针的例子

int x = 0, y = 0;
int *p = &x;
int *q = &y;
int **r = &p;
*r = q;
int *s = *r;

在上述简写下，初始的取地址约束为：

pt(p) 包含 x
pt(q) 包含 y
pt(r) 包含 p

接着处理间接存储 *r = q：因为 r 可能指向 p，所以添加 pt(q) ⊆ pt(p)，于是 pt(p) 增加 y。

处理间接加载 s = *r 时，同样沿着 r -> p 找到保存指针的位置，再把 pt(p) 传播给 pt(s)。最终得到：

pt(p) = {x, y}
pt(q) = {y}
pt(r) = {p}
pt(s) = {x, y}

按顺序执行这段程序，最后的 p 和 s 实际只指向 y。流不敏感分析保留 x，因为它同时考虑了对 p 的初始赋值和后续写入。这个额外目标来自分析抽象，而不是程序真的在最后保留了两个地址。

为什么要反复传播

间接访问产生的关系取决于其他集合。例如处理 s = *r 时，如果尚不知道 r 指向 p，就无法立即发现从 p 到 s 的传播关系。

所以不能只扫描语句一次。一个简单实现是反复扫描全部约束，每次只向集合中增加元素，直到没有集合发生变化。由于节点和对象数量有限，集合只增不减，这个过程最终终止。由空集合出发，得到的是满足这些包含约束的最小不动点。

图与约束在这里不是互斥路线：取地址关系可以表示为指向边，pt(q) ⊆ pt(p) 可以表示为从 q 到 p 的复制边。加载和存储在发现新指向目标后，会产生新的传播关系。图是组织和求解约束的一种方式。

实验：实现一个简化求解器

下面的 Python 程序实现上述四类约束。它忽略控制流、字段、堆分配、空指针和函数调用，输入是假定已通过类型检查的规范化操作。

from collections import defaultdict


def solve(constraints):
    points_to = defaultdict(set)
    changed = True

    def include(dst, values):
        before = len(points_to[dst])
        points_to[dst].update(values)
        return len(points_to[dst]) != before

    while changed:
        changed = False
        for kind, dst, src in constraints:
            if kind == "addr":          # dst = &src
                grew = include(dst, {src})
            elif kind == "copy":        # dst = src
                grew = include(dst, points_to[src])
            elif kind == "load":        # dst = *src
                grew = False
                for obj in tuple(points_to[src]):
                    grew = include(dst, points_to[obj]) or grew
            elif kind == "store":       # *dst = src
                grew = False
                for obj in tuple(points_to[dst]):
                    grew = include(obj, points_to[src]) or grew
            else:
                raise ValueError(f"unknown constraint: {kind}")
            changed = grew or changed

    return {name: set(targets) for name, targets in points_to.items()}


constraints = [
    ("addr", "p", "x"),
    ("addr", "q", "y"),
    ("addr", "r", "p"),
    ("store", "r", "q"),
    ("load", "s", "r"),
]
result = solve(constraints)
for name in ("p", "q", "r", "s"):
    print(name, sorted(result[name]))

输出为：

p ['x', 'y']
q ['y']
r ['p']
s ['x', 'y']

tuple(...) 为本轮枚举建立快照，避免传播时集合增大导致迭代器失效；新增关系会在后续扫描中继续处理。每条约束都必须执行，不能因为本轮已经发现变化，就用短路求值跳过后面的传播。

这个实现便于理解，但会重复扫描没有变化的约束。实际实现常使用工作列表：集合增长时，只重新处理依赖该节点的约束，并尽量传播新增目标。需要特别注意，加载、存储的基址集合增长时，也必须重新建立或触发对应的传播关系。

读者可以尝试把 load 放到约束列表最前面，或增加 p = s 形成环。正确求解器仍应收敛到满足所有约束的结果，不能依赖语句在列表中的特定顺序。

基于合一的 Steensgaard 分析

Andersen 分析在复制 p = q 时保留有方向的包含关系，允许 p 比 q 拥有更多目标。

Steensgaard 分析采用另一种思路：用等价类表示抽象位置及其指向关系，通过合一（Unification）合并需要统一的节点。这类算法通常使用并查集，经典算法可以达到近线性的时间复杂度，但合并之后难以再区分原来的目标。

例如下面的代码：

int x = 0, y = 0;
int *p = &x;
int *q = &y;
p = q;

流不敏感的包含分析允许：

pt(p) = {x, y}
pt(q) = {y}

在典型合一模型中，复制约束会促使相关指向关系合一，原本不同的目标可能被合并为同一抽象类。后续查询 q 时，也可能无法再排除 x。这里描述的是合一造成精度损失的直观效果，完整算法还需要处理地址、解引用和类型结构，不能只把所有赋值两端的变量无条件并在一起。

方法	核心关系	典型特点
Andersen	集合包含	保留传播方向，通常更精确，求解代价可能较高
Steensgaard	等价与合一	借助并查集高效求解，合并容易引入额外目标

在朴素表示下，经典 Andersen 求解的最坏复杂度可达立方量级；实际耗时仍取决于约束规模、集合表示和传播策略。不能仅凭算法名称判断某个工程实现的速度。

如何提高分析精度

流敏感：区分程序点

流不敏感分析把约束合在一起，通常只做弱更新：新增目标，不删除旧目标。流敏感分析则沿控制流传播状态，并在分支汇合处合并。

int *p = &x;
p = &y;
// 此处 p 只指向 y

如果能确认赋值覆盖了唯一的具体存储位置，可以进行强更新，用 {y} 替换旧集合。

对于 *r = q，只有证明被更新的是唯一具体对象，且写入覆盖相关指针位置时，才能安全删除该位置的旧目标。pt(r) 只有一个抽象对象还不一定足够：这个对象可能概括了多次分配产生的许多具体对象。此时通常仍需弱更新。

上下文敏感：区分调用

int *identity(int *p) {
    return p;
}

void example(void) {
    int x = 0, y = 0;
    int *a = identity(&x);
    int *b = identity(&y);
    // a、b 在各自调用中分别指向 x、y
}

上下文不敏感分析如果共用一份形参和返回值摘要，容易把两次调用的目标合并，导致 a、b 都被认为可能指向 x 或 y。上下文敏感分析可以按调用位置、有限长度的调用链等方式区分这两次调用，从而恢复精度。

上下文划分越细，需要维护的状态通常越多；递归也要求对上下文进行有限抽象，不能无限展开调用链。

字段敏感：区分结构体成员

struct Pair {
    int *left;
    int *right;
};

void fields(void) {
    int x = 0, y = 0;
    struct Pair pair;
    pair.left = &x;
    pair.right = &y;
}

字段敏感分析为 pair.left 和 pair.right 建立不同位置，可以分别记录 {x} 和 {y}。字段不敏感分析把它们合并到整个结构体的抽象中，容易让两个成员都得到 {x, y}。

流敏感、上下文敏感和字段敏感是不同维度，可以组合使用。路径敏感分析还可以利用分支条件区分互斥路径，但通常需要更多计算资源。

工程中还要处理什么

前面的求解器只展示了核心传播机制。面对 C/C++ 等语言，还需要扩展模型：

• 指针算术与数组：为偏移、下标和对象边界建立抽象；无法精确处理的偏移需要保守合并。
• 函数指针与间接调用：由指向结果发现可能的被调函数，再传播实参、形参和返回值。新调用边又可能产生新目标，调用图和指向结果常需一起迭代。
• 外部函数：为已知库函数提供摘要；未知函数可能读写可达内存、保存传入指针或返回未知地址，需要保守处理。
• 堆与对象生命周期：按分配位置或上下文区分对象。发现可能指向某对象并不等于证明该对象仍然有效，还需要生命周期分析。
• 整数与指针转换、联合体等操作：处理语言与目标平台允许的表示变化，避免因忽略访问方式而遗漏关系。

空指针也不能与“求解尚未发现目标”混为一谈。如果需要诊断空指针解引用，模型通常要显式记录空值及其传播；未知指针则可能指向许多有效对象。两者不能统一用一个空集合代替。

指向分析的应用与边界

指向结果可以帮助自动矢量化判断不同迭代的读写是否可能冲突，也能支持冗余加载消除、死存储消除、间接调用优化和逃逸分析。但每项优化还需要额外条件，例如控制流、访问大小、操作顺序和可观察副作用。

安全检查同样可以利用这些信息：可能的访问目标帮助定位空指针、释放后使用或内存泄漏风险。不过，仅靠指向集合不能证明没有越界、没有泄漏；还需要范围分析、生命周期分析或路径条件等信息。

例如，知道 p 指向数组 a，并不能回答 p[i] 是否越界；还必须知道数组长度、指针偏移和 i 的范围。分析结果提供证据，不应被解释为超出模型能力的安全保证。

练习

1. 对 p = &x; q = p; p = &y; 分别写出流不敏感结果和最后一个程序点的流敏感结果，解释两者的差异。
2. 在求解器中加入 t = s，并打乱约束顺序，验证结果不变；再加入一个没有取地址来源的复制环，观察其集合是否保持为空。
3. 解释为什么 pt(p) = pt(q) = {heap_site} 不能直接证明 p 和 q 在运行时相等。
4. 为简化求解器增加字段节点，例如 pair.left 和 pair.right，比较字段合并前后的目标集合。

小结

指向分析用有限的抽象对象描述指针可能访问的内存。Andersen 分析通过包含约束传播集合，Steensgaard 分析通过合一降低求解成本；两者都需要在分析精度和计算代价之间取舍。

理解取地址、复制、加载和存储四种约束，就能把多级指针关系变成可求解的问题。继续引入控制流、调用上下文、字段和堆抽象，才能逐步接近真实编译器所需的指针模型。