  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 \cdot \alpha(n))$, where $\alpha(n)$ is
the inverse Ackermann function, improving the previously known $O(n^2)$ 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 \cdot \log n)$ 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. We also show that the same hardness holds for
graphs of constant treewidth.
