SPIRE: A Methodology for Sequential to Parallel Intermediate Representation Extension

International audienceSPIRE is a new methodology for the design of parallel extensions of the intermediate repre- sentations used in compilation frameworks of sequential languages. It can be used to leverage existing infrastructures for sequential languages to address both control and data parallel constructs while pre- serving as much as possible existing analyses for sequential and parallel code. We suggest to view this upgrade process as an "intermediate representation transformer" at the syntactic and semantic levels; we show this can be done via the introduction of only ten new concepts, collected in three groups, namely execution, synchronization and data distribution, and precisely defined via a formal semantics and rewriting rules. We use the sequential intermediate representation of PIPS, a comprehensive source-to-source compila- tion platform, as a use case for our approach. We introduce our SPIRE parallel primitives, extend PIPS intermediate representation and show how example code snippets from the OpenCL, Cilk, OpenMP, X10, Habanero-Java, MPI and Chapel parallel programming languages can be represented this way. A formal definition of SPIRE operational semantics is provided, built on top of the one used for the sequential intermediate representation. We assess the generality of our proposal by (1) showing how a different sequential IR, namely LLVM, can be extended to handle parallelism using the SPIRE method- ology and (2) providing implementation and run-time performance data of a SPIRE-derived paralleliza- tion process. Our primary goal with the development of SPIRE is to provide, at a low cost, powerful parallel program representations that will ease the design of efficient automatic parallelization algorithms. More gener- ally, our work provides a possible roadmap for the compiler designers who need to introduce parallel features into their own infrastructures