一句话：提出首个双向图上动态 Dyck 可达性算法，每次边更新 O(n·α(n))、全对查询 O(1)。
双向 Dyck 可达性是程序分析的基础形式化，用于刻画括号配对的程序属性，并被别名分析等客户端分析采用。静态双向 Dyck 可达性已有 O(m) 时间最优算法，但在代码变更下动态维护全对信息尚无最坏情况保证的算法。本文研究双向图上边插入与删除序列下动态维护全对 Dyck 可达性的问题，提出首个动态双向 Dyck 可达性算法，每次更新耗时 O(n·α(n))，任意全对可达性查询耗时 O(1)，其中 α(n) 为反 Ackermann 函数。作者在 Java 别名分析与上下文敏感数据依赖分析上实现并评估该算法，与基于 O(m) 静态最优算法的直接方法及近期增量 Datalog 求解器比较，实验结果显示数量级加速。
Dyck-reachability is a fundamental formulation for program analysis, which has been widely used to capture properly-matched-parenthesis program properties such as function calls/returns and field writes/reads. Bidirected Dyck-reachability is a relaxation of Dyck-reachability on bidirected graphs where each edge u → ( i v labeled by an open parenthesis “( i ” is accompanied with an inverse edge v → ) i u labeled by the corresponding close parenthesis “) i ”, and vice versa. In practice, many client analyses such as alias analysis adopt the bidirected Dyck-reachability formulation. Bidirected Dyck-reachability admits an optimal reachability algorithm. Specifically, given a graph with n nodes and m edges, the optimal bidirected Dyck-reachability algorithm computes all-pairs reachability information in O ( m ) time. This paper focuses on the dynamic version of bidirected Dyck-reachability. In particular, we consider the problem of maintaining all-pairs Dyck-reachability information in bidirected graphs under a sequence of edge insertions and deletions. Dynamic bidirected Dyck-reachability can formulate many program analysis problems in the presence of code changes. Unfortunately, solving dynamic graph reachability problems is challenging. For example, even for maintaining transitive closure, the fastest deterministic dynamic algorithm requires O ( n 2 ) update time to achieve O (1) query time. All-pairs Dyck-reachability is a generalization of transitive closure. Despite extensive research on incremental computation, there is no algorithmic development on dynamic graph algorithms for program analysis with worst-case guarantees. Our work fills the gap and proposes the first dynamic algorithm for Dyck reachability on bidirected graphs. Our dynamic algorithms can handle each graph update ( i.e. , edge insertion and deletion) in O ( n ·α( n )) time and support any all-pairs reachability query in O (1) time, where α( n ) is the inverse Ackermann function. We have implemented and evaluated our dynamic algorithm on an alias analysis and a context-sensitive data-dependence analysis for Java. We compare our dynamic algorithms against a straightforward approach based on the O ( m )-time optimal bidirected Dyck-reachability algorithm and a recent incremental Datalog solver. Experimental results show that our algorithm achieves orders of magnitude speedup over both approaches.
@article{paperbot1597,
title = {Efficient algorithms for dynamic bidirected Dyck-reachability},
author = {Yuanbo Li and Kris Satya and Qirun Zhang},
journal = {Proceedings of the ACM on Programming Languages},
volume = {6},
number = {POPL},
year = {2022},
doi = {10.1145/3498724}
}