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 well-known 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. Copyright © 2013 ACM.
All Author(s) ListZhang Q., Lyu M.R., Yuan H., Su Z.
Name of Conference34th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2013
Start Date of Conference16/06/2013
End Date of Conference19/06/2013
Place of ConferenceSeattle, WA
Country/Region of ConferenceUnited States of America
Pages435 - 446
LanguagesEnglish-United Kingdom
KeywordsAlias analysis, Dyck-CFL-reachability

Last updated on 2020-20-10 at 00:38