  A compiler's intermediate representation (IR) defines a program's execution
plan by encoding its instructions and their relative order. Compiler
optimizations aim to replace a given execution plan with a
semantically-equivalent one that increases the program's performance for the
target architecture. Alternative representations of an IR, like the Program
Dependence Graph (PDG), aid this process by capturing the minimum set of
constraints that semantically-equivalent execution plans must satisfy. Parallel
programming like OpenMP extends a sequential execution plan by adding the
possibility of running instructions in parallel, creating a parallel execution
plan. Recently introduced parallel IRs, like TAPIR, explicitly encode a
parallel execution plan. These new IRs finally make it possible for compilers
to change the parallel execution plan expressed by programmers to better fit
the target parallel architecture. Unfortunately, parallel IRs do not help
compilers in identifying the set of parallel execution plans that preserve the
original semantics. In other words, we are still lacking an alternative
representation of parallel IRs to capture the minimum set of constraints that
parallel execution plans must satisfy to be semantically-equivalent.
Unfortunately, the PDG is not an ideal candidate for this task as it was
designed for sequential code. We propose the Parallel Semantics Program
Dependence Graph (PS-PDG) to precisely capture the salient program constraints
that all semantically-equivalent parallel execution plans must satisfy. This
paper defines the PS-PDG, justifies the necessity of each extension to the PDG,
and demonstrates the increased optimization power of the PS-PDG over an
existing PDG-based automatic-parallelizing compiler. Compilers can now rely on
the PS-PDG to select different parallel execution plans while maintaining the
same original semantics.
