论文标题
有条件的下限用于基于包含的点对点分析
Conditional Lower Bound for Inclusion-Based Points-to Analysis
论文作者
论文摘要
基于包容性的（即安徒生风格）点对点分析是一个基本的静态分析问题。安徒生的开创性工作给出了C的最差立方体$ O（n^3）$时间点分析算法，其中$ n $与程序变量的数量成正比。如果算法在$ o（n^{3-δ}）$Δ> 0 $中以$ o（n^{3-δ}）$时间运行，则确实是亚地。尽管数十年来大量的努力改善了点对点分析，但立方界限仍保持不败。最佳的组合分析算法具有“略微亚基” $ O（n^3 / \ text {log} n）$复杂性。是否可以在真正的亚采用时间内解决点对点分析是一个有趣的开放问题。 在本文中，我们证明了一个真正的亚地带$ O（N^{3-δ}）$时间组合算法用于基于包含的点对点分析：不太可能：一个真正的亚地下组合点到分析算法分析算法意味着真正的亚双比子亚ubibic subibic Compinatorial algorithial algorithm for Boolean Matrix Matrix倍增（BMM）。 BMM是一个充分研究的问题，并且尚无真正的亚地铁组合BMM算法。最快的组合BMM算法在时间$ o（n^3/ \ text {log}^4 n）$中运行。 我们的结果包括简化的Dyck可触觉BMM硬度的证明。减少本身就是有趣的。首先，它比现有的bmm- hard度结果稍强，因为我们的还原性仅需要一种类型的戴克（Dyck）可容纳性括号（$ d_1 $ reach的性能）。其次，我们正式将“立方瓶颈”归因于解决$ d_1 $ - reach的需求，该性能捕获指针参考/剥离的语义。这种新的观点使得更一般的减少适用于具有任意指针语句类型的程序。最后，我们基于$ d_1 $ reach的减少性表明，需求驱动的积分分析与详尽的对应物一样困难。
Inclusion-based (i.e., Andersen-style) points-to analysis is a fundamental static analysis problem. The seminal work of Andersen gave a worst-case cubic $O(n^3)$ time points-to analysis algorithm for C, where $n$ is proportional to the number of program variables. An algorithm is truly subcubic if it runs in $O(n^{3-δ})$ time for some $δ> 0$. Despite decades of extensive effort on improving points-to analysis, the cubic bound remains unbeaten. The best combinatorial analysis algorithms have a "slightly subcubic" $O(n^3 / \text{log } n)$ complexity. It is an interesting open problem whether points-to analysis can be solved in truly subcubic time. In this paper, we prove that a truly subcubic $O(n^{3-δ})$ time combinatorial algorithm for inclusion-based points-to analysis is unlikely: a truly subcubic combinatorial points-to analysis algorithm implies a truly subcubic combinatorial algorithm for Boolean Matrix Multiplication (BMM). BMM is a well-studied problem, and no truly subcubic combinatorial BMM algorithm has been known. The fastest combinatorial BMM algorithms run in time $O(n^3/ \text{log}^4 n)$. Our result includes a simplified proof of the BMM-hardness of Dyck-reachability. The reduction is interesting in its own right. First, it is slightly stronger than the existing BMM-hardness results because our reduction only requires one type of parenthesis in Dyck-reachability ($D_1$-reachability). Second, we formally attribute the "cubic bottleneck" to the need to solve $D_1$-reachability, which captures the semantics of pointer references/dereferences. This new perspective enables a more general reduction that applies to programs with arbitrary pointer statements types. Last, our reduction based on $D_1$-reachability shows that demand-driven points-to analysis is as hard as the exhaustive counterpart.
