一句话：刻画 Andersen 指针分析（APA）的细粒度与并行复杂度，证明一般情形 Θ(n³) 最优，受限情形近矩阵乘法并可并行。
Andersen 指针分析（APA）是静态程序分析的基础问题，可表示为 n 个指针上的 m 条包含式约束；其可扩展性至关重要，但除 O(n^2·m) 与稀疏情形 O(n^2) 外，复杂度理解不足。本文系统刻画 APA 的细粒度与并行复杂度：一般情形给出 O(n^3) 上界，并在标准复杂性假设下证明按需查询也有 Ω(n^3) 组合下界，形式化长期猜测的立方瓶颈，说明该算法最优；在温和限制下给出 Õ(n^ω) 算法（ω 为矩阵乘法指数），并证明按需问题 Ω(n^2) 下界，当 ω=2+o(1) 时最优；并行性方面，一般问题 P-complete，而温和限制下可并行。这些理论结果给未来实际优化提供洞察。
Pointer analysis is one of the fundamental problems in static program analysis. Given a set of pointers, the task is to produce a useful over-approximation of the memory locations that each pointer may point-to at runtime. The most common formulation is Andersen’s Pointer Analysis (APA), defined as an inclusion-based set of m pointer constraints over a set of n pointers. Scalability is extremely important, as points-to information is a prerequisite to many other components in the static-analysis pipeline. Existing algorithms solve APA in O ( n 2 · m ) time, while it has been conjectured that the problem has no truly sub-cubic algorithm, with a proof so far having remained elusive. It is also well-known that APA can be solved in O ( n 2 ) time under certain sparsity conditions that hold naturally in some settings. Besides these simple bounds, the complexity of the problem has remained poorly understood. In this work we draw a rich fine-grained and parallel complexity landscape of APA, and present upper and lower bounds. First, we establish an O ( n 3 ) upper-bound for general APA, improving over O ( n 2 · m ) as n = O ( m ). Second, we show that even on-demand APA (“may a specific pointer a point to a specific location b ?”) has an Ω( n 3 ) (combinatorial) lower bound under standard complexity-theoretic hypotheses. This formally establishes the long-conjectured “cubic bottleneck” of APA, and shows that our O ( n 3 )-time algorithm is optimal. Third, we show that under mild restrictions, APA is solvable in Õ( n ω ) time, where ω<2.373 is the matrix-multiplication exponent. It is believed that ω=2+ o (1), in which case this bound becomes quadratic. Fourth, we show that even under such restrictions, even the on-demand problem has an Ω( n 2 ) lower bound under standard complexity-theoretic hypotheses, and hence our algorithm is optimal when ω=2+ o (1). Fifth, we study the parallelizability of APA and establish lower and upper bounds: (i) in general, the problem is P-complete and hence unlikely parallelizable, whereas (ii) under mild restrictions, the problem is parallelizable. Our theoretical treatment formalizes several insights that can lead to practical improvements in the future.
@article{paperbot1147,
title = {The fine-grained and parallel complexity of andersen’s pointer analysis},
author = {Anders Alnor Mathiasen and Andreas Pavlogiannis},
journal = {Proceedings of the ACM on Programming Languages},
volume = {5},
number = {POPL},
year = {2021},
doi = {10.1145/3434315}
}