---
res:
bibo_abstract:
- '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.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Chatterjee, Krishnendu
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
- foaf_Person:
foaf_givenName: Bhavya
foaf_name: Choudhary, Bhavya
foaf_surname: Choudhary
- foaf_Person:
foaf_givenName: Andreas
foaf_name: Pavlogiannis, Andreas
foaf_surname: Pavlogiannis
foaf_workInfoHomepage: http://www.librecat.org/personId=49704004-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-8943-0722
bibo_doi: 10.1145/3158118
bibo_issue: POPL
bibo_volume: 2
dct_date: 2017^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/2475-1421
dct_language: eng
dct_publisher: Association for Computing Machinery@
dct_title: Optimal Dyck reachability for data-dependence and Alias analysis@
...