Introduction

Introduction

Writing a high quality native code generator for a single architecture is a considerable effort, which only gets more difficult when multiple architectures are involved. Micro-processor instruction sets have become simplier, but their basic architecture have become much more complicated, that the algorithms required to effectively utilize the various forms of parallelism and limited resources is usually the product of a Phd dissertation. Engineering efficient implementations of these algorithms is another major investment.

Adapting a native code generator from an existing compiler is not a viable option because of insurmountable assumptions. On some target architectures one may wish to rely more heavily on the native assembler pseudo-op directives to insert procedure entry and exit stubs, or lay out data in memory. A native code compiler targetted to a different architecture may not provide the appropriate support, or one targetted to multiple architectures will typically adopt the least common denomimator. An even bigger problem is the insertion and reuse of optimization modules. Adding new optimizations modules is difficult as the invariants that must hold between phases are often poorly described. Optimization modules are usually engineered to rely on properties of the source language and target architecture, making them impossible to reuse for a similar, but different, source language and architecture. It is hoped that experimental results from an optimization can be repeated based on a (sometimes poor and incomplete) flowchart or pseudocode description of the algorithms implemented.

This situation has forced researchers to generate C code instead. Even though C is regarded as a high-level assembly language, there may be properties of the source language that cannot be effectively expressed in C. For example, it may be desirable to always keep a variable in a register, such as the allocation pointer in a garbage collected language; or one may know that certain reads from memory are from immutable addresses -- giving the register spiller or scheduler more flexibility. In general the quality of C compilers vary, that the results of optimizations based on a C backend are difficult to replicate and misleading at best.

Lastly, one could bite the bullet and write a native code generator. However, in a language design or compiler researcher environment, these languages and compilers are not used extensively. Consequently, the bugs are never fully shaken out; the system is bloated and fragile, but just robust enough to support the experiments being conducted. Unfortunately, the bulk of this repeats the efforts of others. Even worse, after five years the target architecture is obsolete and of no interest.

The MLRISC framework addresses all of these issues.

The MLRISC Framework

MLRISC uses a strongly typed, tree-based, intermediate language called MLRisc, that is very similar to a register transfer language. The strong typing ensures that meaningless intermediate programs are never constructed by the frontend. Being tree-based, makes it convenient to use tree pattern-matching tools like BURG, that optimially match patterns describing the target architecture instruction set. Compilation to native machine code starts by translating the compiler intermediate language or abstract machine into operations and registers in MLRisc.

The MLRisc intermediate language is specialized to the needs of the front end which requires that all the code generators and optimization phases be appropriately specialized. For example, one may wish to customize the back end to manipulate an encoding of a list of registers that will be passed to a garbage collector as the roots of live variables. Unfortunately, this encoding can only be determined after register allocation has been performed. This implies that the intermediate language must be able to express computations over these values, and the code generators must be able to accept these values where constants are permitted as operands of instructions.

Pseudo-op directives, represents a further dimension to which the MLRisc intermediate language may be specialized. These directives may include constructors to generate jump tables, or layout memory in specific ways. Once again these pseudo-op directives must be seemlessly incorporated into the flowgraph, and correctly processed when generating assembly or machine code. Within the framework, it is possible to make full use of all the pseudo-op directives provided by a host assembler.

The generated MLRisc is fed into a code generator that has been pieced together from high quality, reusable components. These components include modules that perform pattern matching on the MLRisc tree, generating a representation of target machine instructions embedded in a flowgraph. Optimizations performed on the flowgraph are completely under the control of the user. Each optimization takes a flowgraph as input and returns a new (hopefully improved) flowgraph as output.

The optimization modules are typically implemented as a curried higher-order module. The first level of currying is over machine specific properties and perhaps internal data represenations --- details that are fixed for a specific target architecture. The second level of currying is over user specific properties that vary with the application. For example, a register allocator may include definition/use information of an instruction in the machine specific properties, and the number of available registers for coloring in the user specific properties. Native code generators will export a partial application of such higher order modules to machine specific properties, leaving an interface that is small and easy to understand. Such a partial application represents a specialization of the code generator to the target architecture.

The bulk of porting the framework to a new architecture involves three things: 1) designing a representation for instructions that would support efficient queries, 2) writing a module to pattern match MLRisc trees into target machine instructions, and 3) writing machine specific modules that describe properties of the machine. The signature of the curried higher-order optimization module acts as the main documentation needed to use the module.

The system is written in Standard ML, and extensive use of the module system is used to guarantee that the various phases of the code generator are composed and built correctly. MLRISC is currently used as a backend in the SML/NJ compiler for the DEC Alpha and HPPA architectures, and work on an x86 code generator is in progress. Code generators for the MIPS, SPARC, and RS6000 (which used an older version of MLRISC) exist but are not actively maintained. All of these code generators generate binary machine code directly, without going to the intermediate assembly language.

It is difficult to compare the final quality of the code produced with vendor compilers, but the process of improved code quality can be incremental; adding phases that have a significant benefit. A useful data point will be a comparison of the new x86 code generator with the one currently used in the SML/NJ compiler. None of the optimizations performed in the new code generator are easy to do in the old framework.

Contributions

The MLRISC framework was motivated by the observation that:

The MLRISC framework addresses all these issues. Writing a code generator for a new front end or new target architecture is not a major investment. It is easy to adapt the system to the constraints of different front ends and target architectures, and finally, the Standard ML module system provides a rigorous framework that ensures the correct reuse of optimizations modules.

Related Work

None of the systems described here have the flexibility and robustness in integration that MLRisc demonstrates. A distinguishing feature across these systems is the representation used to peform low level optimizations. GCC, SUIF, and IMPACT use a low level RTL like representation to peform machine independent optimizations like constant propagation, branch chaining, and strength reduction. VPO uses an RTL representation but incorporates machine information into these optimizations. MLRisc is unique in throwing away the RTL intermediate form, and performing all of these optimizations on the flowgraph of target machine instructions. MLRisc is similar to the Toaster project at IBM but not nearly as ambitious.

VPO

The VPO system translates a high level intermediate representation of the program into an RTL based language. Instruction selection decisions are performed incrementally. Each RTL instruction is linked with du and ud-chains, and each basic block node contains a host of information to support traditional optimizations. MLRisc optimization passes are very similar to those in VPO, in which optimization modules are parameterized over target machine properties, but MLRisc takes advantage of the powerful type system and module language to ensure proper integration.

GCC

GCC is an extremely large and complicated system. The machine description files alone for an architecture like the RS6000 can run into over 10,000 lines! Code generation is performed on a per function basis, implying no interprocedural optimizations. Each function is converted directly into RTL, and a series of optimization passes peformed over this. The bulk of the machine descriptions is used to provide patterns during RTL generation, and final assembly output. The INSN language, used to define the overall structure of the compilation unit, is rigid and not nearly as flexible as the pseudo-op treatment in MLRisc.

SUIF

The SUIF system has two intermediate representations; a high level one to support parallelization algorithms, and a low level one to support code generation. The motivation and goals of MLRisc are common to those of the low level representation, although MLRisc is far more sophisticated in its retargetability.

Impact

The IMPACT compiler uses two main intermediate forms to support code generation . The Lcode representation is similar to a RISC instruction set. Like GCC, a large number of machine independent optimizations are performed on this representation. The Lcode is then translated to Mcode that is closer to the target machine. Register allocation and scheduling are performed on the Mcode, which is finally macro-expanded to the target assembly language. Target machine information is used to guide register allocation and scheduling of Mcode.


  Submit a comment on this page  

[ INDEX | TOP | Parent | Root ]

Author: Lal George
Last Modified: September 4, 1996
Copyright © 1996 Bell Laboratories