Download now Free registration required
A dataflow query asks for the set of reachable (abstract) states, given a starting set of states. In this paper, the authors 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, they obtain an asymptotic improvement in answering dataflow queries. They use weighted pushdown systems as the abstract model of a program. The techniques are interprocedural. They are general, yet provide an impressive speedup. They applied the 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.
- Format: PDF
- Size: 392.9 KB