Tapir: Embedding Recursive Fork-join Parallelism into LLVM’s Intermediate Representation

Reviewer: William M. Waite

A typical compiler has a front end that analyzes the source text and converts it to a language-independent intermediate representation (IR) whose structure and operations support general-purpose optimization in the compiler's middle end. The quality of the optimization depends on the IR's ability to express the intent of source language constructs in a way that the middle end understands and can improve. Although some compilers now support task parallel linguistic constructs, their front ends convert those constructs into more primitive IR sequences. Often, those sequences involve opaque procedure calls that block further optimization. The authors took a different approach with Tapir. They chose to extend the existing LLVM IR to encode logical parallelism and expose opportunities for standard compiler optimizations to work on parallel code. Integration of these extensions was relatively simple, and they turned out to be easy to maintain in response to LLVM changes. The extensions opened parallel code to a wide variety of standard optimizations by avoiding the problems with opaque procedure calls. According to the authors, the Tapir approach is premised on the notion that parallel programs can usually be executed serially and that there is a normative serial execution order for tasks. This allows them to define serial projection: A serial projection transforms a given program to replace parallel constructs with serial constructs. If the serial projection produces one of the valid behaviors of the original program, then the compiler and runtime system can execute parallel tasks serially. The authors argue that the serial projection property is supported by most task parallel programming models, but not necessarily by arbitrary concurrency mechanisms. They therefore strongly advocate that task parallelism and concurrency be treated as separate concepts. The paper describes how Tapir represents logically parallel tasks, how LLVM's analysis is adapted to Tapir programs, and how the authors evaluated Tapir in practice. Each of these topics is covered in detail, with examples and discussion. The authors discuss related work and present a comprehensive retrospective on where they have been and where they are going. I found the paper easy to read and engrossing; it should be accessible to anyone with a basic understanding of code optimization