Register AllocationAll 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:
The architecture specific parameters supplied to the higher-order
functor include:
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:
|