MLRISC

MLRISC Contributors Requirements How to Obtain MLRISC

Overview

Problem Statement Contributions MLRISC Based Compiler MLRISC Intermediate Representation MLRisc Generation Back End Optimizations Register Allocation Machine Description Garbage Collection Safety System Integration Optimizations Graphical Interface Line Counts Systems Using MLRISC Future Work

System

Architecture of MLRISC The MLTREE Language MLTree Extensions MLTree Utilities Instruction Selection Assemblers Machine Code Emitters Delay Slot Filling Span Dependency Resolution The Graph Library The Graph Visualization Library Basic Compiler Graphs The MLRISC IR 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

Annotations Cells Cluster Client Defined Constants Client Defined Pseudo Ops Instructions Instruction Streams Label Expressions Labels Regions Regmap

# 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.

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 : ..

where:

`nFreeRegs`
  is the number of free registers or essentially the number of colors available for coloring the interference graph.

`dedicated`
  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.

`spill/reload`
  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)

where:

`firstPseudoR`
  is an integer representing the first pseudo register. Any register below this value is a physical register.

`maxPseudoR`
  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.

`defUse`
  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:

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

Generated by mltex2html
Last modified: Mon Oct 3 20:52:35 UTC 2022 by buildd@x86-grnet-02