Pegasus: An Efficient Intermediate Representation
Abstract
This paper presents Pegasus, a compact and expressive intermediate representation for imperative languages. The representation is suitable for target architectures supporting predicated execution and aggressive speculation. In this paper, the authors present Pegasus (Predicated Explicit GAted Simple Uniform SSA), a new intermediate representation (IR) that makes explicit -- in a single representation -- the control flow, the data flow, and the synchronization of operations that interfere through side-effects. More importantly, Pegasus has a clean semantics, independent of the target architecture. This enables its use to bridge the gap between C programs and hardware implementations, enabling the conversion from an imperative, single-threaded model of computation to a highly parallel, asynchronous, explicitly synchronized target. Pegasus combines predicated static single assignment (SSA) representation and gated SSA, making explicit the switching of data values, enabling the compiler to use predication and aggressive speculation for exposing instruction-level parallelism (ILP). In the second section, the authors describe the basic components of Pegasus and how the IR can be constructed starting from an imperative language. The operational semantics of Pegasus is described informally in Section 3, and formally in Appendix A. Section 4 shows that the compactness of Pegasus enables the use of extremely simple and efficient algorithms for many major compiler optimizations; in particular, they exhibit linear-time algorithms for almost all of the scalar optimizations from Muchnick. The versatility of Pegasus is demonstrated in Section 5, where they describe its use in a compiler that translates ANSI C programs into hardware.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 2002
- Accession Number
- ADA458495
Entities
People
- Mihai Budiu
- Seth C. Goldstein
Organizations
- Carnegie Mellon University