Efficient algorithms for dynamic bidirected Dyck-reachability
Abstract
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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jan 12, 2022
- Source ID
- 10.1145/3498724
Entities
People
- Kris Satya
- Qirun Zhang
- Yuanbo Li
Organizations
- Defense Advanced Research Projects Agency
- Georgia Tech
- National Science Foundation