An Introduction to Machine SUIFand Its Portable Libraries for Analysis and OptimizationRelease version 2.02.07.15Michael D. Smith and Glenn Holloway{smith,holloway}@eecs.harvard.eduDivision of Engineering and Applied SciencesHarvard UniversityJuly 16, 2002AbstractMachine SUIF is a flexible and extensible infrastructure for constructing compiler back ends. Withit you can readily construct and manipulate machine-level intermediate forms and emit assemblylanguage, binary object, or C code. The system comes with backs ends for the Alpha and x86architectures. You can easily add new machine targets and develop profile-driven optimizations.Though Machine SUIF is built on top of the Stanford SUIF system (version 2.1), the analysesand optimizations within Machine SUIF are not SUIF specific. By rewriting the implementation ofan extensible interface layer, you can easily port the Machine-SUIF code base to another compilationenvironment. We refer to this interface as the Optimization Programming Interface (OPI). The OPIallows us to write optimizations and analyses that are parameterized with respect to both a targetand an underlying environment. We use this capability to share optimization passes between MachineSUIF and Deco, a system for dynamic code optimization.This document introduces Machine SUIF, presents the overall rationale behind its design, illus-trates how one writes a parameterized pass, and describes how to get started using the system. Itconcludes with a road map for the rest of the documentation that comes with Machine SUIF.1July 16, 2002 overview.nw 2Contents1 Introduction 32 Goals 33 Setting Up Your Environment 53.1 Compiling Machine SUIF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53.2 Compiling with Machine SUIF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 Back-End Organization and Flow 64.1 IR organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64.2 Dialects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64.3 General flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74.4 Compilation specifics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74.5 Constraints on pass orderings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 Developing a New Optimization Pass 106 Extending the OPI 127 Adding Support for New Targets 138 More Radical Changes 149 Where To Look Next 1410 Acknowledgments 15July 16, 2002 overview.nw 31 IntroductionMachine SUIF is a flexible, extensible, and easily-understood infrastructure for constructing compiler backends. We built Machine SUIF with the philosophy that the “textbook” portions, i.e. the optimization andanalysis passes, should be coded in a way that makes them as independent of the compiler environmentand compilation targets as possible. By adhering to this philosophy, we are able to distribute both aworking compiler and a collection of analyses/optimizations that can be quickly and easily inserted intoa new compilation environment.In particular, the Machine-SUIF distribution contains a working compiler based on the Stanford SUIFcompiler infrastructure (version 2.1). This compiler is capable of producing optimized code for machinesbased on the Alpha or x86 architectures. However, the analyses and optimizations distributed in MachineSUIF do not directly reference any SUIF constructs or embed constants from any target machine. Instead,each is written using a standardized view of the underlying compiler environment, an interface layer thatwe refer to as the Optimization Programming Interface (OPI).This document is an introduction to Machine SUIF. It briefly presents our overall design rationale, getsyou started using the system, and directs you to the rest of the infrastructure documentation. Weassume that you are familiar with the basic concepts of SUIF 2.1; if not, we encourage you to see thedocumentation on the SUIF 2 home page1.The next section enumerates our goals for Machine SUIF and outlines how we achieved them. Section 3then describes how to install Machine SUIF and start using it to compile programs. Section 4 providesan overview of the general flow of our back-end compilation system and presents several example back-end scripts. Section 5 describes what’s involved in developing optimization passes using our OPI, whileSection 6 shows you how to extend the OPI for new optimizations. Section 7 describes the steps thatyou need to take in order to provide support for a new target architecture. Section 8 discusses how youcan change the structure of the Machine-SUIF intermediate representation (IR) and how to port theoptimizations to a new environment. Section 9 briefly outlines where to go next for more details.2 GoalsWe designed Machine SUIF for a wide range of users. In particular, we support those interested in:• building new optimizations that are parameterizable with respect to the target machine and portableacross compiler environments;• adding support for a new or augmented target architecture;• developing a new IR, without having to rewrite all of our optimizations.To adequately address the needs of these users, we developed Machine SUIF with three primary goals inmind. First and foremost, Machine SUIF had to be easy to use, especially if you wanted to do somethingsimple, and straightforward to retarget so that we could use it in architectural investigations. Second, ithad to support the modular development of sophisticated optimizations. We wanted to provide our stu-dents and colleagues with the ability to contribute passes and benefit from the efforts of others. Finally, ithad to built in a manner that permitted reuse of existing optimizations directly in an optimization envi-ronment with significantly different constraints. Specifically, we wanted to be able to reuse optimizationsbuilt for Machine SUIF in Deco, a project at Harvard University in dynamic or on-line optimization. Therest of this section explores each of these goals in greater detail.1See URL http://suif.stanford.edu/suif/suif2/.July 16, 2002 overview.nw 4Ease of use. For those using Machine SUIF simply as a compiler, Sections 3 and 4 of this overviewshould be a sufficient introduction to the system.Since we designed Machine SUIF as a research compiler, we expect that most of our users will want to addor change the system