Parallelism for free: Efficient and optimal bitvector analyses for
In TACAS, pages
In this paper we show how to construct optimal bitvector
analysis algorithms for parallel programs with shared memory that are as
efficient as their purely sequential counterparts, and which can easily be
implemented. Whereas the complexity result is rather obvious, our optimality
result is a consequence of a new Kam/Ullman-style Coincidence Theorem. Thus
using our method, the standard algorithms for sequential programs computing
liveness, availability, very business, reaching definitions, definition-use
chains, or performing partially redundant expression and assignment
elimination, partial dead code elimination or strength reduction, can
straightforward be transferred to the parallel setting at almost no
University of Passau, Germany.
Available as PostScript.
BRICS WWW home page