一句话：提出 POCR，利用传递关系有序性与混合图表示，在 CFL 可达性求解中高效消除传递冗余并保持精度。
CFL-可达性通过推导新边计算边标记图中可达节点对，但同一节点对间多路径会造成重复推导，限制可扩展性。作者发现冗余主要来自传递关系相关推导，现有传递闭包去冗余技术难以用于动态求解。论文提出保持精度的 all-pairs CFL-可达性方法 POCR：利用传递关系内在有序性确定推导顺序，设计生成树与邻接表结合的混合图表示及动态构造算法，在图上动态变化时维护该顺序。在 C/C++ 上下文敏感值流分析与字段敏感别名分析中，POCR 平均消除 98.50% 和 97.26% 的冗余推导，相较标准算法加速 21.48× 和 19.57×，并比 Graspan 与 Soufflé 平均快 3.67× 以上。
Given an edge-labeled graph, context-free language reachability (CFL-reachability) computes reachable node pairs by deriving new edges and adding them to the graph. The redundancy that limits the scalability of CFL-reachability manifests as redundant derivations, i.e., identical edges can be derived multiple times due to the many paths between two reachable nodes. We observe that most redundancy arises from the derivations involving transitive relations of reachable node pairs. Unfortunately, existing techniques for reducing redundancy in transitive-closure-based problems are either ineffective or inapplicable to identifying and eliminating redundant derivations during on-the-fly CFL-reachability solving. This paper proposes a scalable yet precision-preserving approach to all-pairs CFL-reachability analysis by taming its transitive redundancy. Our key insight is that transitive relations are intrinsically ordered, and utilizing the order for edge derivation can avoid most redundancy. To address the challenges in determining the derivation order from the dynamically changed graph during CFL-reachability solving, we introduce a hybrid graph representation by combining spanning trees and adjacency lists, together with a dynamic construction algorithm. Based on this representation, we propose a fast and effective partially ordered algorithm POCR to boost the performance of CFL-reachability analysis by reducing its transitive redundancy during on-the-fly solving. Our experiments on context-sensitive value-flow analysis and field-sensitive alias analysis for C/C++ demonstrate the promising performance of POCR. On average, POCR eliminates 98.50% and 97.26% redundant derivations respectively for the value-flow and alias analysis, achieving speedups of 21.48× and 19.57× over the standard CFL-reachability algorithm. We also compare POCR with two recent open-source tools, Graspan (a CFL-reachability solver) and Soufflé (a Datalog engine). The results demonstrate that POCR is over 3.67× faster than Graspan and Soufflé on average for both value-flow analysis and alias analysis.
@article{paperbot1434,
title = {Taming transitive redundancy for context-free language reachability},
author = {Yuxiang Lei and Yulei Sui and Shuo Ding and Qirun Zhang},
journal = {Proceedings of the ACM on Programming Languages},
volume = {6},
number = {OOPSLA2},
year = {2022},
doi = {10.1145/3563343}
}