How to Obtain MLRISC
Problem Statement
MLRISC Based Compiler
MLRISC Intermediate Representation
MLRisc Generation
Back End Optimizations
Register Allocation
Machine Description
Garbage Collection Safety
System Integration
Graphical Interface
Line Counts
Systems Using MLRISC
Future Work
Architecture of MLRISC
The MLTREE Language
MLTree Extensions
MLTree Utilities
Instruction Selection
Machine Code Emitters
Delay Slot Filling
Span Dependency Resolution
The Graph Library
The Graph Visualization Library
Basic Compiler Graphs
SSA Optimizations
ILP Optimizations
Optimizations for VLIW/EPIC Architectur...
Register Allocator
Back Ends
The Alpha Back End
The PA RISC Back End
The Sparc Back End
The Intel x86 Back End
The PowerPC Back End
The MIPS Back End
The TI C6x Back End
Basic Types
Client Defined Constants
Client Defined Pseudo Ops
Instruction Streams
Label Expressions

Register Allocation

All the optimization modules are written in a generic fashion but parameterized over architecture and client information. The Standard ML module system is a central mechanism to the design and organization of MLRISC. Parameterized modules in Standard ML are provided by functors, that takes the specification of input modules and produces a module that matches some output specification. In particular, SML/NJ modules are higher order, which means that a functor can yield functors as a result. I will use register allocation as an example.

Back end optimizations

The register allocator is written has a higher order functor which when applied to suitable arguments produces an integer or floating point register allocator. The figure is simplifed because the output functor is not restricted to integer and floating point allocators but could also be other types of allocators, for example, condition code. The integer and floating point register allocators are functors that only take client specific parameters as input, whereas the higher-order takes architectural parameters as input. The client specific parameters include:

   nFreeRegs : int
   dedicated : int list
   spill : ..
   reload : ..
is the number of free registers or essentially the number of colors available for coloring the interference graph.

is the list of dedicated registers. It is useful to exclude these from the graph-color process to reduce the size of the data structures created.

are functions that describe how to spill and reload registers that need to be spilled or reloaded in an instruction. These two functions are perhaps the most complicated pieces of information that need to be supplied by a client of MLRISC.

The architecture specific parameters supplied to the higher-order functor include:

   firstPseudoReg : int
   maxPseudoR : unit -> int
   defUse : instruction -> (int list * int list)
is an integer representing the first pseudo register. Any register below this value is a physical register.

is a function that returns an integer indicating the number of the highest pseudo-register that has been used in the program. This number is useful in estimating the intial size of various tables.

is a function that returns the registers defined and used by an instruction.

These parameters are largely self explanatory, however, there are addition architectural parameters that relate to the internal representation of instructions that would be ugly to explain. For example there is the need for a module that does liveness analysis over the register class that is being allocated. This type of complexity can be shielded from a user. For the DEC Alpha the situation is as shown in the figure:

Back end optimizations

The client only sees the functors on the right, to which only client specific information need be provided. There is the illusion of a dedicated DEC Alpha integer and floating point register allocator. There are several advantages to this:

  • The architectural parameters that are implementation specific do not need to be explained to a user, and are supplied by someone that intimately understands the port to the target architecture.

  • The number of parameters that a client supplies is reduced.

  • The parameters that the client supplies is restricted to things that concern the front end.

Lal George
Allen Leung
SML/NJ Validate this page
Generated by mltex2html
Last modified: Thu Jan 9 19:38:15 EST 2003 by leunga@slinky