Parallelism for free: Efficient and optimal bitvector analyses for parallel programs

Jens Knoop
Bernhard Steffen
Jürgen Vollmer

In TACAS, pages 319--333

Abstract:

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 cost.

Comments
University of Passau, Germany.

Available as PostScript.

BRICS WWW home page