ELIMINATING PARTIALLY DEAD CODE IN EXPLICITLY PARALLEL PROGRAMS

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 progr ams with shared memory and interleaving semantics. The basis of this a daption is a recently presented framework for efficient and precise bi tvector analyses for this program setting. Whereas the framework under lying our approach allows a straightforward adaptation of the required data flow analyses to the parallel case, the transformation part of t he 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 appr opriate natural side condition suffices to lift even the optimality re sult known from the sequential setting to the parallel setting. (C) 19 98-Elsevier Science B.V. All rights reserved.