Analysis and Optimization of Explicitly Parallel Programs

Most current compiler analysis techniques are unable to cope with the semantics introduced by explicit parallel and synchronization constructs in parallel programs. In this paper we introduce new analysis and optimization techniques for compiling explicitly parallel programs that use mutual exclusion synchronization. We introduce the CSSAME form, an extension of Concurrent Static Single Assignment (CSSA) that incorporates mutual exclusion into a data flow framework for explicitly parallel programs. We show how this analysis can improve the effectiveness of constant propagation in a parallel program. We also present a modification to a sequential dead code elimination algorithm to work on explicitly parallel programs. Finally, we introduce new optimization techniques specifically targeted at explicitly parallel programs. These techniques apply optimizing transformations to a program by taking advantage of its parallel and synchronization structure. We prove the correctness of these tran..