论文标题
安徒生指针分析的细粒度和平行复杂性
The Fine-Grained and Parallel Complexity of Andersen's Pointer Analysis
论文作者
论文摘要
指针分析是静态程序分析中的基本问题之一。给定一组指针，任务是对每个指针可能在运行时指向的内存位置产生有用的过度评估。最常见的配方是Andersen的指针分析（APA），定义为一组$ n $指针的基于包含的$ m $指针约束。现有的算法将APA求解为$ O（N^2 \ cdot m）$时间，虽然已经猜想该问题没有真正的亚基算法，但到目前为止，证明仍然难以捉摸。 在这项工作中，我们绘制了APA的丰富细粒度和平行的复杂性景观，并呈现上限和下边界。首先，我们为General APA建立了一个$ O（n^3）$上限，将$ O（N^2 \ cdot m）$改善为$ n = o（m）$。其次，我们表明，即使是按需APA（“可以指向特定位置的特定指针$ a $ a $？”）也有$ω（n^3）$（组合）$（组合）下限，在标准复杂性理论假设下。这正式建立了APA的长关注的“立方瓶颈”，并表明我们的$ O（n^3）$ - 时间算法是最佳的。第三，我们表明，在$ \ tilde {o}（n^ω）$时间中，apa在限制下，apa可以解决，其中$ω<2.373 $是矩阵 - 杂质的指数。据信$ω= 2+o（1）$，在这种情况下，此界限变成二次。第四，我们表明，即使在此类限制下，即使按需问题也具有$ω（n^2）$下限在标准复杂性理论假设下，因此当$ω= 2+o（1）$时，我们的算法也是最佳的。第五，我们研究了APA的并行性并建立下限和上限：（i）通常，问题是p完整的，因此不可行，而（ii）在轻度限制下，问题是可行的。我们的理论待遇正式化了几种见解，这些见解可能会导致未来的实际改进。
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. Existing algorithms solve APA in $O(n^2\cdot m)$ time, while it has been conjectured that the problem has no truly sub-cubic algorithm, with a proof so far having remained elusive. 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\cdot 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 $\tilde{O}(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.
