Fast algorithms for dyck-cfl-reachability with applications to alias analysis
Refereed conference paper presented and published in conference proceedings

Times Cited
Altmetrics Information

Other information
AbstractThe context-free language (CFL) reachability problem is a wellknown fundamental formulation in program analysis. In practice, many program analyses, especially pointer analyses, adopt a restricted version of CFL-reachability, Dyck-CFL-reachability, and compute on edge-labeled bidirected graphs. Solving the all-pairs Dyck-CFL-reachability on such bidirected graphs is expensive. For a bidirected graph with n nodes and m edges, the traditional dynamic programming style algorithm exhibits a subcubic time complexity for the Dyck language with k kinds of parentheses. When the underlying graphs are restricted to bidirected trees, an algorithm with O(n log n log k) time complexity was proposed recently. This paper studies the Dyck-CFL-reachability problems on bidirected trees and graphs. In particular, it presents two fast algorithms with O(n) and O(n+m log m) time complexities on trees and graphs respectively. We have implemented and evaluated our algorithms on a state-of-the-art alias analysis for Java. Results on standard benchmarks show that our algorithms achieve orders of magnitude speedup and consume less memory.
All Author(s) ListZhang Q., Lyu M.R., Yuan H., Su Z.
Volume Number48
Issue Number6
PublisherAssociation for Computing Machinary, Inc.
Place of PublicationUnited States
Pages435 - 446
LanguagesEnglish-United Kingdom
KeywordsAlias analysis, Dyck-CFL-reachability

Last updated on 2020-14-10 at 03:23