Eliminating partially dead code in explicitly parallel programs

AbstractEliminating 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. The basis of this adaption is a recently presented framework for efficient and precise bitvector analyses for this program setting. Whereas the framework underlying our approach allows a straightforward adaptation 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