如果你写过编译器里的静态分析或者用代码扫描工具抓过空指针那你大概率遇到过这种场景代码里一个指针明明指向了某个对象分析器却把另一条不相干的路径也并了进来报出一堆“可能为空”的告警。这里面的关键就是“指针分析”Points-to Analysis做得够不够细。上一篇我把指针分析的基础概念过了一遍什么是定向关系、为什么要用集合而不是单个对象、May-Alias和Must-Alias怎么区分。这篇接着往下写重点放在算法选型、实现细节和工程取舍上。你可以把它当成一份“从能跑通到跑得准”的实操笔记。1. 指针分析到底在分析什么指针分析的核心任务是给程序里的每个指针变量算出一个“可能指向的抽象对象集合”。这个集合在英文里叫 points-to set在中文语境里叫“点在集合”或者“可能指向集”。只要两个指针变量的集合有交集就说它们 May-Alias可能指向同一块内存如果集合完全相同且都是单元素才有可能谈 Must-Alias。这个集合看起来简单却是很多分析的地基。空指针检查要判断指针会不会为空数据竞争检测要判断两个线程访问的是不是同一个对象死代码消除要判断一块内存还有没有可能被读到逃逸分析要判断对象会不会逃出函数作用域。没有一份合理的 points-to 结果这些分析都只能靠猜。1.1 一个例子看懂可能指向集合拿一段最简单的 C 风格代码举例void demo() { int x, y; int *p; p x; p y; *p 42; }如果做流不敏感的指针分析不会区分“先赋值后赋值”只看语句之间的数据流关系。最终结果就是p 指向 xp 指向 y*p 可能修改 x也可能修改 y这个结果是一个保守的近似。真实程序里*p 42只会修改 x 或 y 当中的一个但分析器无法确定是哪一个所以把两种情况都保留下来。这就是“可能指向分析”的本质宁可多报不能漏报。1.2 能做和不能做指针分析能解决一类很实际的问题判定两个指针是否指向同一个抽象对象。两个集合没有交集就可以大胆地说不可能别名有交集就只能说“可能别名”。对编译优化来说可能别名会阻碍某种变换必须保守对缺陷检测来说可能别名又会导致误报需要后续过滤。它不能做的事也很清楚它不关心指针指向对象的运行时真实地址不模拟内存的具体内容也不追踪每个路径的布尔条件。它更像是在抽象内存模型上做一个“静态传播”把所有可能执行到的数据流都算进集合里。1.3 May-Alias 与 Must-Alias 的差别May-Alias 是“可能”Must-Alias 是“一定”。大部分指针分析算出来的是 May-Alias因为程序分支、函数调用、循环都会导致同一个变量指向多个对象。Must-Alias 的判定条件非常苛刻两个指针必须在所有执行路径上都指向同一个对象且没有其他可能。在流不敏感分析里很少谈 Must-Alias因为集合已经把所有路径合并在一起了只能证明“一定不别名”很难证明“一定别名”。2. 从入门到进阶必须做的三个取舍很多人写完一个最朴素的指针分析后发现结果“粗得没法用”。这时候不是算法写错了而是没有做精度上的取舍。指针分析的世界里有一个基本铁律精度和速度不可兼得。想做多精细就要付出多大代价。2.1 流敏感看顺序还是不看顺序流敏感的意思是分析过程是否区分语句的先后顺序。p x; p y;流不敏感分析会把两句话合并得到 p {x, y}。流敏感分析会沿着控制流走在第一条语句之后 p {x}在第二条语句之后 p {y}。显然流敏感更精确但它要为每个程序点保存一份集合状态内存和时间开销都成倍增长。工程里什么时候该用流敏感我的经验是做空指针检查、释放后使用这类“跟程序点强相关”的分析时流敏感的价值很大如果只是做逃逸分析、方法调用关系推断流不敏感通常就够用了。很多投入实用的静态分析框架默认用的还是流不敏感的指针分析因为它在全程序级别上跑得动。2.2 上下文敏感把调用点区分开上下文敏感要解决的是“同一个函数被不同地方调用却混在一起分析”的问题。void set_id(int **pp, int *v) { *pp v; } int *p, *q, *x, *y; set_id(p, x); set_id(q, y);上下文不敏感的分析会把*pp v当成一条公共约束pp 可能指向 p 和 qv 可能指向 x 和 y最后 p 和 q 都指向 x 和 y。这显然是过度近似。上下文敏感的做法是把调用点区分开。为第一次调用生成一组单独的约束pp 只指向 pv 只指向 x于是 p 精确指向 x为第二次调用也生成一组单独的约束q 精确指向 y。代价是函数体会被克隆多份或者用调用字符串来标记状态分析规模会指数级膨胀。实际工程里常用的折中是“只对部分函数做上下文敏感”比如递归函数不做小型函数做或者限制克隆深度。盲目全量上下文敏感程序稍微大一点就直接跑不完。2.3 字段敏感对象内部也要区分字段敏感解决的是对象内部字段混在一起的问题。struct Node { int *data; Node *next; }; Node n; n.data x; n.next y;字段不敏感的分析会把 n 这个对象的所有字段合并成一个集合于是以后读n.data的时候可能读出 y。如果把字段区分开n.data只指向 xn.next只指向 y别名关系就清晰得多。实现字段敏感并不难常见的做法是给每个抽象对象加上一个字段偏移比如A0.data和A0.next是两个独立节点。真正难的是字段敏感和上下文敏感同时使用时节点数量会爆炸。所以很多分析器默认只开字段敏感上下文敏感还要额外配置。3. 两种主流算法合并式与包含式指针分析算法有两大流派。一种叫“合并式”算法也叫 unification-based另一种叫“包含式”算法也叫 inclusion-based。两者的名字听起来差不多但解题思路完全不同。3.1 合并式看见赋值就等价合并式算法的核心思想非常粗暴只要出现p q这条赋值语句就把 p 和 q 合并成一个等价类它们以后共享同一个 points-to 集合。举个例子p x; q p; r q;合并式算法会先把 p 和 q 合并再把 q 和 r 合并最终 p、q、r 在同一个等价类里都指向 x。合并操作还会反向传播如果后来发现 p 又指向了 y那 q 和 r 也会跟着指向 y。这种算法的好处是快接近线性时间复杂度因为合并一次之后就不需要反复迭代。坏处也很明显精度差。因为 p 和 q 一旦合并就再也分不开哪怕程序里明明还有别的赋值关系会让 p 指向一个完全不同的对象。3.2 包含式子集约束慢慢收敛包含式算法不用“等价类”而是用“子集关系”。对p q它会生成约束pts(q) 是 pts(p) 的子集。意思是 q 指向的东西p 也必须指向但 p 可以多指向一些别的东西两者不必完全相等。一开始先处理直接赋值语句比如p x把 x 放进 pts(p)。然后反复检查所有约束只要 pts(q) 里新增了一个对象就把这个对象拷贝到 pts(p) 里只要有新增就要重新扫描所有约束直到没有任何集合发生变化。这种算法的精度远高于合并式但复杂度也高。最坏情况下是 O(n^3)程序稍微大一点就需要优化。实际工程里包含式算法是主流因为精度收益太明显了。3.3 怎么选型维度合并式包含式精度低适合快速估值高适合做精确别名分析时间复杂度近似线性最坏三次方实现难度简单一个并查集搞定中等需要约束迭代典型场景快速逃逸判断、大规模程序普查编译器优化、缺陷检测我在项目里一般这样选择如果只是想知道“对象有没有可能逃逸出函数”合并式足够如果要做死代码消除、空指针检查、数据竞争检测还是老老实实用包含式。很多分析框架跑出来的误报严重要么是选错了算法要么是没开上下文敏感而不是分析本身有问题。4. 从零实现一个可用版包含式分析器光讲理论容易飘我直接带大家写一个极简但能跑的包含式指针分析器。这里不做上下文敏感也不做字段敏感只做最基础的流不敏感全程序分析。理解这个版本之后往上加上下文、加字段都会容易很多。4.1 表示层节点、集合与约束先用节点 ID 表示每个变量和每个抽象对象。变量直接用自己的名字抽象对象用分配点的名字比如A0表示代码里第一个malloc或x对应的对象。每个节点对应一个 points-to 集合初始为空。from collections import defaultdict class PointerAnalyzer: def __init__(self): self.var2id {} self.id2name {} self.next_id 0 self.pts defaultdict(set) self.constraints [] def _node(self, name): if name not in self.var2id: self.var2id[name] self.next_id self.id2name[self.next_id] name self.next_id 1 return self.var2id[name]所有变量、抽象对象都是节点。变量名和抽象对象名都放在同一张表里方便后面处理*p q这种间接访问。4.2 约束生成对四种语句分别生成约束p x生成 alloc 约束pts(p) 中加入对象 xp q生成 copy 约束pts(q) 是 pts(p) 的子集p *q生成 load 约束q 指向的对象它的 points-to 集合要并入 p*p q生成 store 约束p 指向的对象要继承 q 的 points-to 集合代码实现def alloc(self, var, site): self.constraints.append( (alloc, self._node(var), self._node(site)) ) def copy(self, dst, src): self.constraints.append( (copy, self._node(dst), self._node(src)) ) def load(self, dst, src): self.constraints.append( (load, self._node(dst), self._node(src)) ) def store(self, dst, src): self.constraints.append( (store, self._node(dst), self._node(src)) )这里需要注意alloc里的site既是一个“对象节点”也可以作为 store 的左值出现。比如*p q中如果 p 指向对象 A0那么实际上修改的是 A0 指向的内容。把分配点也当作节点来存 points-to 集合正好能表达这件事。4.3 求解不动点求解过程就是一个循环反复扫描所有约束直到任何集合都不再变化。def solve(self): changed True while changed: changed False for kind, lhs, rhs in self.constraints: if kind alloc: if rhs not in self.pts[lhs]: self.pts[lhs].add(rhs) changed True elif kind copy: before len(self.pts[lhs]) self.pts[lhs] | self.pts[rhs] if len(self.pts[lhs]) ! before: changed True elif kind load: # dst *srcsrc 指向的所有对象的内容要流入 dst for obj in list(self.pts[rhs]): before len(self.pts[lhs]) self.pts[lhs] | self.pts[obj] if len(self.pts[lhs]) ! before: changed True elif kind store: # *dst srcdst 指向的所有对象要继承 src 的指向 for obj in list(self.pts[lhs]): before len(self.pts[obj]) self.pts[obj] | self.pts[rhs] if len(self.pts[obj]) ! before: changed True这个版本为了直观牺牲了性能。每条约束都要反复从头扫描程序规模大了肯定不行。生产环境会用带依赖关系的 worklist 算法每次某个节点的 points-to 集合有新增就把依赖它的 load、store、copy 约束重新激活一遍而不是从头扫全局。4.4 一个小例子跑通来测一个完整场景a PointerAnalyzer() # a box a.alloc(a, A_box) # d obj a.alloc(d, A_obj) # *box d a.store(A_box, d) # e a a.copy(e, a) # f *e a.load(f, e) a.solve() for name in [a, d, e, f, A_box, A_obj]: ids a.pts[a.var2id[name]] print(name, [a.id2name[i] for i in sorted(ids)])输出结果应该是a [A_box] d [A_obj] e [A_box] f [A_obj] A_box [A_obj] A_obj []手工推演一遍a 指向 box 对象d 指向 obj 对象store 让 box 对象指向 obje 拷贝 a 所以也指向 box最后f *e取 e 指向对象box的内容box 指向 obj所以 f 指向 obj。结果完全正确。这里有一个容易踩的坑在f *e这一步如果先执行 load 再执行 store第一轮可能看不到 obj因为 store 的结果还没传播过来。这也是需要反复迭代到不动点的原因。如果你把迭代次数写死成一次结果大概率是缺的。5. 常见问题与排查技巧实录写指针分析写通是第一关写准是第二关写快是第三关。下面这些问题基本是每个实现者都会遇到的。5.1 结果粗得离谱怎么办如果你的分析结果里到处都是同一个集合先别急着怀疑算法实现大概率是精度选项没开。常见原因有上下文不敏感导致同一个函数的调用全部混合字段不敏感导致结构体的不同字段互相污染堆对象用类型抽象而不是分配点抽象导致同一类型的对象全部合并。解决办法是逐步加精度不要一次全开。先开字段敏感再看结果是否变好还不够再开上下文敏感。一次全开的问题是你根本分不清到底是哪一个选项带来了收益后续调优非常痛苦。5.2 为什么报了假空指针假空指针往往是流不敏感造成的。看这段p x; ... p NULL; if (p NULL) { // 这里读 p 不会为空 }流不敏感分析会把p的所有赋值合并p 的集合里既包含 x 也包含 NULL于是在 NULL 分支里读 p 依然会被判定为“可能空”。真实路径里 p 已经被赋成 NULL这确实可能空报警不算错但如果代码在赋值 NULL 之前就检查过那就会误报。遇到这种情况别急着骂分析器先确认自己用的是流敏感还是流不敏感。只做空指针检查的话流敏感几乎是必须的。可以用被杀掉的误报样本来反推如果不看语句顺序就给出告警那就是缺少流敏感导致的。5.3 性能卡在瓶颈包含式算法太慢是另一个高频问题。最直接的手段是换成 worklist 驱动而不是每次全表扫描。每个节点维护“依赖它的约束列表”当pts[node]有新元素加入时只处理跟这个节点相关的约束。再进一步可以用“差异传播”不要把整个集合拷到下游只把新增的那部分元素拷出去。这个优化叫 delta propagation实现复杂一点但收益非常大。很多公开实现都会用位集来表示 points-to 集合用位运算来做集合拷贝和判断新增能再快一个数量级。还有一种思路是先把程序简化去掉不相关的库函数、内联小函数、去掉不参与指针运算的局部变量。分析规模降下来之后很多性能问题自然就消失了。5.4 调试小技巧从约束路径反推指针分析真正难的不是写算法而是结果出错时不知道错在哪一层。我常用的调试方法是给每个节点起一个“能看懂的名字”比如allocdemo5表示在demo函数第 5 行的分配点param:foo:pp表示foo函数的形参pp。这样一旦出现离谱的指向关系我能在输出里直接看到是哪一层的合并把它带进来的。再配一个最小复现程序。不要拿整个项目去调试而是把有问题的代码片段抽出来手工推演一遍约束再对比分析器的输出。通常很快就能定位到是约束生成错了还是不动点迭代不完整。最后再分享一个经验指针分析这种静态分析精度问题几乎永远比性能问题难调。先跑通再跑准最后才考虑跑快。这个顺序不要反过来否则你会在一个还有漏报的分析器上浪费时间优化性能。我手头所有静态分析项目里指针分析始终是性价比最高的部分。它本身不直接报 bug但几乎所有有价值的告警都建立在它之上。你把这份地基打好了后面的空指针、数据竞争、逃逸分析都会轻松很多。