Solving Multiple Dataflow Queries Using WPDSs
Akash Lal and Thomas Reps
A dataflow query asks for the set of reachable (abstract)
states, given a starting set of states. In this paper, we show how to
optimize multiple queries on the same program (each with a different
starting set of states) for better overall running time. After a preprocessing
phase, we obtain an asymptotic improvement in answering dataflow
queries. We use weighted pushdown systems as the abstract model of
a program. Our techniques are interprocedural. They are general, yet
provide an impressive speedup. We applied our algorithm to three very
different applications, one based on finding affine relations using linear
algebra, and others for model checking Boolean programs, and obtained
1.5-fold to 7-fold speedups.
(Click here to access the paper:
PDF;
(c) Springer-Verlag.)
University of Wisconsin