article
Optimal Dyck reachability for data-dependence and Alias analysis
published
yes
Krishnendu
Chatterjee
author 2E5DCA20-F248-11E8-B48F-1D18A9856A870000-0002-4561-241X
Bhavya
Choudhary
author
Andreas
Pavlogiannis
author 49704004-F248-11E8-B48F-1D18A9856A870000-0002-8943-0722
KrCh
department
POPL: Programming Languages
Quantitative Graph Games: Theory and Applications
project
Modern Graph Algorithmic Techniques in Formal Verification
project
Rigorous Systems Engineering
project
A fundamental algorithmic problem at the heart of static analysis is Dyck reachability. The input is a graph where the edges are labeled with different types of opening and closing parentheses, and the reachability information is computed via paths whose parentheses are properly matched. We present new results for Dyck reachability problems with applications to alias analysis and data-dependence analysis. Our main contributions, that include improved upper bounds as well as lower bounds that establish optimality guarantees, are as follows: First, we consider Dyck reachability on bidirected graphs, which is the standard way of performing field-sensitive points-to analysis. Given a bidirected graph with n nodes and m edges, we present: (i) an algorithm with worst-case running time O(m + n · α(n)), where α(n) is the inverse Ackermann function, improving the previously known O(n2) time bound; (ii) a matching lower bound that shows that our algorithm is optimal wrt to worst-case complexity; and (iii) an optimal average-case upper bound of O(m) time, improving the previously known O(m · logn) bound. Second, we consider the problem of context-sensitive data-dependence analysis, where the task is to obtain analysis summaries of library code in the presence of callbacks. Our algorithm preprocesses libraries in almost linear time, after which the contribution of the library in the complexity of the client analysis is only linear, and only wrt the number of call sites. Third, we prove that combinatorial algorithms for Dyck reachability on general graphs with truly sub-cubic bounds cannot be obtained without obtaining sub-cubic combinatorial algorithms for Boolean Matrix Multiplication, which is a long-standing open problem. Thus we establish that the existing combinatorial algorithms for Dyck reachability are (conditionally) optimal for general graphs. We also show that the same hardness holds for graphs of constant treewidth. Finally, we provide a prototype implementation of our algorithms for both alias analysis and data-dependence analysis. Our experimental evaluation demonstrates that the new algorithms significantly outperform all existing methods on the two problems, over real-world benchmarks.
https://research-explorer.ista.ac.at/download/10416/10421/2017_ACMProgLang_Chatterjee.pdf
application/pdfno
Association for Computing Machinery2017Los Angeles, CA, United States
eng
Proceedings of the ACM on Programming Languages
2475-1421
1910.0024110.1145/3158118
2POPL
https://research-explorer.ista.ac.at/record/5455
K. Chatterjee, B. Choudhary, and A. Pavlogiannis, “Optimal Dyck reachability for data-dependence and Alias analysis,” <i>Proceedings of the ACM on Programming Languages</i>, vol. 2, no. POPL. Association for Computing Machinery, 2017.
Chatterjee, Krishnendu, et al. “Optimal Dyck Reachability for Data-Dependence and Alias Analysis.” <i>Proceedings of the ACM on Programming Languages</i>, vol. 2, no. POPL, 30, Association for Computing Machinery, 2017, doi:<a href="https://doi.org/10.1145/3158118">10.1145/3158118</a>.
Chatterjee K, Choudhary B, Pavlogiannis A. Optimal Dyck reachability for data-dependence and Alias analysis. <i>Proceedings of the ACM on Programming Languages</i>. 2017;2(POPL). doi:<a href="https://doi.org/10.1145/3158118">10.1145/3158118</a>
K. Chatterjee, B. Choudhary, A. Pavlogiannis, Proceedings of the ACM on Programming Languages 2 (2017).
Chatterjee K, Choudhary B, Pavlogiannis A. 2017. Optimal Dyck reachability for data-dependence and Alias analysis. Proceedings of the ACM on Programming Languages. 2(POPL), 30.
Chatterjee, K., Choudhary, B., & Pavlogiannis, A. (2017). Optimal Dyck reachability for data-dependence and Alias analysis. <i>Proceedings of the ACM on Programming Languages</i>. Los Angeles, CA, United States: Association for Computing Machinery. <a href="https://doi.org/10.1145/3158118">https://doi.org/10.1145/3158118</a>
Chatterjee, Krishnendu, Bhavya Choudhary, and Andreas Pavlogiannis. “Optimal Dyck Reachability for Data-Dependence and Alias Analysis.” <i>Proceedings of the ACM on Programming Languages</i>. Association for Computing Machinery, 2017. <a href="https://doi.org/10.1145/3158118">https://doi.org/10.1145/3158118</a>.
104162021-12-05T23:01:48Z2023-02-23T12:27:13Z