MLRisc Generation

MLRisc Generation

The focus of this section is to describe the pieces required to support MLRisc generation, and to provide a brief introduction to the main MLRisc data structure.

Abstract Machines

The stepping stone to generating machine code in any compiler is an abstract machine whose dedicated registers and instructions are mapped onto those of the target machine. In some cases, abstract machine instructions are generated as an intermediate representation, and several optimization passes may be performed. These instructions are finally macro expanded into target machine instructions. In other cases, the abstract machine may act as a conceptual model for the final generation of machine code and no intermediate representation is created. In either case a low level interface is an essential intermediary to target machine code. Various abstract machines that have found favor include:


Language Abstract machine
C Stack of activations
Prolog Warren Abstract Machine (WAM)
Haskell G machine
Algol/Pascal Stack of activations + display vector
Standard ML SECD machine
Functional abstract machine (FAM)
Continuation passing style (CPS)
ZINC abstract machine (ZAM)

Our approach to target machine code generation is to start with an abstract machine and translate their operations and registers onto those in MLRisc.

Registers

A small fragment of MLRisc specified by the signature MLTREE, is shown below:

signature MLTREE = sig
  datatype rexp =  
      REG of int 
    | LI of int
    | LOAD32 of rexp 
    | ADD of rexp * rexp
    | ...

  and fexp =  FREG of int | ...

  and ccexp = CC of int   | ...

  and stm = STORE32 (rexp, rexp) | ...
end

stm is used to describe instructions executed for their effect and do not return a value. The datatypes rexp, fexp, and ccexp represent computations that return a general, floating point, or condition code value. Each of these datatypes have registers namely, REG, FREG, and CC. MLRisc registers map directly onto target machine registers, except pseudo-registers whose assignment is deferred to register allocation time. Some machines represent condition code registers using general registers. In this case, the MLRisc condition code register CC(21) (for example) is mapped onto the general register 21 on the target machine. Machines like the IBM RS6000, have multiple condition code registers, and it is useful to assume an infinite supply of them.

All intermediate programs are expressed using these three types of registers. It is not possible to talk about special registers like vector floating point registers in the intermediate program. This is a limiting aspect of the current MLRisc framework. Theoretically, it is possible to translate a general purpose register into two distinct types of registers such as address and data registers on the Motorola 68000, although there is no direct experience with this.

The abstract machine in the SML/NJ compiler has several dedicated and general purpose registers used for parameter passing. These include an allocation pointer allocptr, a heap limit pointer limitptr, a variable indicating whether garbage collection must be invoked exhausted, and others. The signature CPSREGS describes these registers.

  signature CPSREGS = sig
     structure T : MLTREE
     val allocptr  : T.rexp
     val limitptr  : T.rexp
     val exhausted : T.ccexp
     ...
  end

T is used as an alias for the MLRisc language. On the DEC alpha the CPSREGS interface is matched by something similar to:

  structure Alpha32CpsRegs = struct
    val allocptr  = REG (13)
    val limitptr  = REG (9)
    val exhausted = CC (11)
    ...
  end
The exhausted register is mapped onto general register 11 on the Alpha. On the Intel x86 architecture, this interface is matched by:
  structure X86CpsRegs = struct
    val allocptr  = REG(7)
    val limitptr  = LOAD32(ADD(REG 5, LI 12))
    val exhausted = CC(0)
    ...
  end

REG(5) and REG(7) are the ebp and edi registers on the x86. LI is used to return values derived from integer constants. Since there are very few registers on the machine, most of the abstract machine registers are implemented in a small reserved portion of memory. The exhausted register is the condition code status register on the Intel.

Cells

During the generation of MLRisc it may be necessary to allocate fresh temporary pseudo-registers that will be assigned during register allocation time. The various phases of the back end also need to allocate temporary pseudo-registers for things like spilling, or holding intermediate values generated by reducing MLRisc subtrees. The CELLS interface, provides the various functions required to maintain a consistent view of pseudo-registers during the process of code generation:

  signature CELLS = sig
    val stackptrR : int              (* stack pointer *)
    val resetRegs : unit -> int Array.array ref list
    val newReg : unit -> int         (* allocate new general register *)
    val maxReg : unit -> int         (* largest number allocated *)
    val firstPseudoReg : unit -> int (* number of machine registers *)
    ...	
    type cellset                     (* collection of registers *)
    val empty : cellset              (* empty collection *)
    val addReg : cellset -> unit     (* add register to collection *)
    ...
  end
Every architecture is assumed to have a stack pointer, resetRegs resets the counters used to generate pseudo-registers and returns a list of references that will eventually contain register alias information. It is sometimes useful to get a handle on these early in code generation. Allocation of a new register always starts at the lowest numbered pseudo-register, i.e., firstPseudoReg. The cellset type provides an efficient representation for a heterogenous collection of registers. This is rarely required by a user of the MLRisc technology, but is useful for anyone writing optimization modules.

Constants

In the backend there are varied flavors of constants that need to be back-patched after certain phases of code generation have been performed. Labels are the most common example. The value of a label cannot be computed until span dependent expansion and scheduling has been performed. In some cases it may be desirable to manipulate an encoding of a list of registers. Such an encoding may be passed to a garbage collector, however, the actual value is only known after register allocation. A final example is the computation of frame sizes and accessing temporaries in activation frames. The frame size and offset of temporaries cannot be determined until register spilling has been performed. In each of these cases it is necessary to:

  1. Be able to express and use these constants in the generated MLRisc program.
  2. Each of the code generators need to be able to accept these values as valid arguments to instructions that manipulate immediate operands.
  3. There must be some mechanism to compute the value of these constants when needed.

One could provide each of these constants in the definition of MLRisc, however, this would be inflexible, and would add complexity in situations where some of the constants were not used. The SML/NJ compiler does not use a runtime stack or manipulate activation frames, for example. A more elegant solution is to define an abstract type called constant and have MLRisc and all the code generators parameterized over this abstract type. The appropriate module sharing constraints will ensure that the same abstract constant type is used in all cases. The abstract type is defined by the CONSTANT interface.

  signature CONSTANT = sig
    type const
    val toString : const -> string
    val valueOf : const -> int
  end
The type const should encapsulate all the relevant information needed to finally compute its value. This may include the register alias maps returned by resetRegs in the CELLS interface, or it may contain front end information such as a reference to frame sizes.

Since the module matching the CONSTANT interface is application dependent, the MLRisc datatype is parameterized over this module, using the MLTreeF functor.

  functor MLTreeF(structure Const : CONSTANT ...) : MLTREE = ...

  signature MLTREE = sig
     structure Constant : CONSTANT

     datatype rexp = 
         REG of int 
      | LABEL of LabelExp.labexp
      | CONST of Constant.const
      | ...
  end 
The constructor CONST is used to hold these constant types. Labels are so pervasive in code generation that MLRisc provides a constructor to express them directly, although they too could be provided using the CONSTANT interface.

Assembler Pseudo-op Directives

Binary machine code is the only language that the target machine will understand. However, generating machine code requires scheduling, span dependency analysis, linking, and a host of other issues that need to be addressed by the compiler. An alternative is to generate assembly code and let other tools deal with these issues.

To make assembly level programming and generation easier, assemblers will provide a large variety of pseudo-op directives that, for example:

The MLRisc framework must have a way to describe these pseudo-ops at the level of detail required by the front end. This is accomplished by a module matching the PSEUDO_OPS interface.

  signature PSEUDO_OPS = sig
    type pseudo_op
    val toString: pseudo_op -> string 
    val emitValue: {pOp:pseudo_op, loc:int, emit:(Word8.word -> unit)} -> unit 
    val sizeOf: (pseudo_op * int) -> int 
    val adjustLabels: (pseudo_op * int) -> unit 
  end

The type pseudo_op need not be the full set of primops that the native assembler provides, but they can be constructors that may expand to several primitive pseudo-ops such as jump tables. The PSEUDO_OPS interface describes various functions that are needed for the generation of both machine code and assembly code. If assembly code is the only output that is being generated then it is sufficient to raise a NotImplemented exception for all functions except the toString function. Otherwise, sizeOf is the size of the pseudo-op given the current location counter; adjustLabels adjust the value of labels embedded in the pseudo-op given the current location counter; and emitValue will output the value of the pseudo-op given an output stream. The output must respect the endianness of the target machine.

An example of a pseudo_op type used in the SML/NJ compiler is given by the signature SMLNJ_PSEUDO_OP_TYPE. This interface is matched by PseudoOpsLittle and PseudoOpsBig for little and big endian machines.

signature SMLNJ_PSEUDO_OP_TYPE = sig
   datatype pseudo_op
      = MARK
      | REALCONST of (Label.label * string) 
      | STRINGCONST of (Label.label * int * string) 
      | JUMPTABLE of {base : Label.label, targets : Label.label list} 
end
Each of these pseudo-ops involves several primitive assembler pseudo-ops. For example, REALCONST is used to embed real constants in strings. The pseudo-op will:
  1. deposits a back pointer, which is the offset to the start of the string in which this real constant is embedded in.
  2. deposit a tag or descriptor for real constants, and finally
  3. deposit the 64 bit real constant.

The MLRisc language is specialized to the front end pseudo-ops using the MLTreeF which is finally:

  functor MLTreeF(structure Const : CONSTANT
                  structure P : PSEUDO_OPS)

MLRisc Compilation

Once MLRisc trees have been constructed it is necessary to translate them into native machine code. The code generator that translates MLRisc to a flowgraph of target machine instructions and performs various optimizations over it, is constructed (by a user) by piecing together reusable components. A very simple interface MLTREECOMP is exported by the back end code generator:

  signature MLTREECOMP = sig
    structure T : MLTREE
    val mlriscComp : T.stm -> unit 
    val mltreeComp : T.mltree -> unit 
  end

The type mltree contains non-code fragments of the flowgraph such as pseudo-ops. To emit instructions into the flowgraph, it is sufficient to wrap an MLRisc code fragment with mlriscComp.

Assuming that the module that generates MLRisc is called MLRiscGen, then it must be parameterized over an interface matching CELLS and MLTREECOMP for the target machine and a mapping of abstract registers onto target registers (given by CPSREGS in the case of the SML/NJ compiler). The module dependency diagram for this very simple situation is show below:

We need to ensure that the MLRisc data structure used to describe the CPS abstract registers is exactly the same as that used to build the code generator, and hence the need for a sharing constraint. In practise the MLRiscGen functor may take a host of additional parameters like the C-calling conventions on the target machine, and even different pseudo-op directives for different target architectures, for example.

    functor MLRiscGen
       (structure R : CPSREGS
        structure C : CELLS
	structure Comp : MLTREECOMP
               sharing Comp.T = R.T)

  Submit a comment on this page  

[ INDEX | TOP | Parent | Root ]

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