Many program-analysis problems can be formulated as
Interleaved Dyck language reachability (InterDyck-reachability)
is a fundamental framework to express a wide variety
of program-analysis problems over edge-labeled graphs.
The InterDyck language represents an
intersection of multiple matched-parenthesis
languages (i.e., Dyck languages).
In practice, program analyses typically leverage one Dyck language to achieve
context-sensitivity, and other Dyck languages to model data dependences, such as
field-sensitivity and pointer references/dereferences.
In the ideal case, an InterDyck-reachability framework should model multiple
Dyck languages simultaneously.
Unfortunately, precise InterDyck-reachability is
Any practical solution must over-approximate
the exact answer.
In the literature, a lot of work has been proposed to over-approximate the
We present a new perspective on improving both the precision and the
scalability of InterDyck-reachability:
we aim to simplify the underlying input graph G.
Our key insight is based on the observation that if an edge is not contributing
\InterDyck-path, we can safely eliminate it from G.
Our technique is orthogonal to the InterDyck-reachability formulation, and can
serve as a pre-processing
step with any over-approximating approaches for InterDyck-reachability.