A CONSTANT PROPAGATION ALGORITHM FOR EXPLICITLY PARALLEL PROGRAMS

In this paper, we present a constant propagation algorithm for explici tly parallel programs, which we call the Concurrent Sparse Conditional Constant propagation algorithm. This algorithm is an extension of the Sparse Conditional Constant propagation algorithm. Without considerin g the interaction between threads, classical optimizations lead to an incorrect program transformation for parallel programs. To make analyz ing parallel programs possible, a new intermediate representation is n eeded. We introduce the Concurrent Static Single Assignment (CSSA) for m to represent explicitly parallel programs with interleaving semantic s and synchronization. The only parallel construct considered in this paper is cobegin/coend. A new confluence function, the pi-assignment, which summarizes the information of interleaving statements between th reads, is introduced. The Concurrent Control Flow Graph, which contain s information about conflicting statements, control flow, and synchron ization, is used as an underlying representation for the CSSA from.