Eliminating partially dead code has proved to be a powerful technique for the runtime optimization of sequential programs. In this article, we show how this technique can be adapted to explicitly parallel programs with shared memory and interleaving semantics on the basis of a recently presented framework underlying our bitvector analyses for this program setting. Whereas the framework underlying our approach allows a straightforward adaption of the required data flow analyses to the parallel case, the transformation part of the optimization requires special care in order to preserve parallelism. This preservation is an absolute must in order to guarantee that the optimization does never impair efficiency. The introduction of an appropriate natural side condition suffices to lift even the optimality result known from the sequential setting to the parallel setting.
Ulrike Peiker, Martin Griebl