Static Single Assignment for Explicitely Parallel Programs

Abstract

We describe and prove algorithms to convert programs which use the Parallel Computing Forum Parallel Sections construct into Static Single Assignment (SSA) form. This proces allows compilers to apply classical scalar optimization algorithms to explicitly parallel programs. To do so, we must define what the concept of dominator and dominance frontier mean in parallel programs. We also describe how we extend SSA form to handle parallel updates and still preserve the SSA properties.