Accession Number:

ADA458495

Title:

Pegasus: An Efficient Intermediate Representation

Descriptive Note:

Research paper

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

2002-04-01

Pagination or Media Count:

21.0

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.

Subject Categories:

  • Electrical and Electronic Equipment
  • Computer Programming and Software
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE