There are two important properties underlying the design of the language.
signature MLTREE = sig
structure Constant : CONSTANT
structure PseudoOp : PSEUDO_OPS
datatype cond = LT | LTU | LE | ...
datatype order = LR | RL
datatype stm =
MV of int * rexp
| COPY of int list * int list
| CALL of rexp * mlrisc list * mlrisc list
| STORE32 of rexp * rexp
| BCC of cond * ccexp * Label.label
...
and rexp =
REG of int
| LI of int
| LABEL of int
| CONST of Constant.const
| LOAD32 of rexp
| ADD of rexp * rexp
| SUB of rexp * rexp * order
| ...
and fexp =
FREG of int
| LOADD of rexp
| FADDD of fexp * fexp
| ...
and ccexp =
CC of int
| LOADCC of rexp
| CMP of cond * rexp * rexp * order
...
datatype mlrisc = CCR of ccexp | GPR of rexp | FPR of fexp
datatype mltree = ...
end
The mlrisc datatype defines values that may be returned. The top-level stm datatype characterize operations that are performed for effect and do not return a value. The CALL instruction deposits the return address in a location that is natural for the target architecture. It takes as arguments registers that are defined and used by the call.
The main drawback with MLRisc is that it is not possible to match instructions that are naturally expressed as DAGs. Instructions that involve some form of auto-increment fall in this category. This is not a serious problem as the framework described here makes it possible to perform an optimization pass that can combine instructions into auto-increment instructions. This problem is also not directly solved in an RTL framework either, where du and ud-chains must be computed before an auto-increment instruction can be synthesized.
Besides generating MLRisc code, a compiler has the need for other things like defining labels, pseudo_ops, and anontating control flowgraphs. These operations are described by the mltree datatype:
datatype mltree =
DEFINELABEL of Label.label
| PSEUDO_OP of PseudoOp.pseudo_op
| BEGINCLUSTER
| CODE of stm
| ESCAPEBLOCK of mlrisc list
| ENDCLUSTER of int Array.array ref list
each of the constructors are defined in more detail, except CODE which passes MLRisc instructions to the backend, and DEFINELABEL that defines a label at the current point.
As MLRisc instructions are being emitted, they are translated into target machine instructions and a flowgraph is built simultaneously based on the target machine instruction semantics. When there is an indirect jump to an unknown location, such as an external function, it is necessary to annotate the flowgraph with registers that are live at the branch. Liveness analysis has no way of knowing what registers are live across the call. This annotation is conveyed to the flowgraph construction module using the ESCAPEBLOCK construct. ESCAPEBLOCK takes a list of type mlrisc, and is associated with the basic block currently being built.
When compiling a module in Standard ML or a file in C, it is beneficial to break up the code generation into clusters. A cluster is a collection of functions and procedures that are members of a call graph. A cluster or call graph is the unit upon which interprocedural optimizations may be performed. The construct BEGINCLUSTER marks the beginning of a cluster.
ENDCLUSTER marks the end of a cluster. The flowgraph that was being constructed is passed onto a code generator. The argument to ENDCLUSTER is a register map obtained from CELLS.resetRegs().
The MLRisc program below computes the sum of numbers from 1 to 100, and leaves the result in REG(1). Cells is assumed to match CELLS and T is an alias for a structure matching MLTREE.
let
val emit = MLTreeComp.mlriscComp
val comp = MLTreeComp.mltreeComp
val indx = Cells.newReg() ;; allocate fresh registers
val sum = Cells.newReg()
val labelDone = Label.newLabel"" ;; create labels
val loop = Label.newLabel""
in
emit(T.MV(indx, T.LI 100)); ;; initialize
emit(T.MV(sum, T.LI 0));
comp(T.DEFINELABEL loop);
emit(T.BCC(T.EQ, T.CMP(T.EQ,indx,T.LI 0), labelDone);
emit(T.MV(sum, T.ADD(sum, indx))); ;; sum := sum + indx
emit(T.MV(indx, T.SUB(indx, T.LI 1))); ;; indx := indx + 1
emit(T.BR loop) ;; loop
comp(T.DEFINELABEL labelDone);
emit(T.COPY(1, sum)) ;; REG(1) := sum
end
A new pseudo register is allocated for the counter and sum, and finally the sum is moved into REG(1) with the COPY instruction. With a good register allocator, sum will be assigned REG(1) and the COPY trivially eliminated.
Consider the simple C program:
extern int G();
int F(int x)
{
int w, y = x * x;
w = G(y, x);
return (w + x);
}
static int G(int u, v)
{
return (v * 100 / u + v);
}
Many architectures will specify a parameter passing convention for interoperability. In this example, let us assume that there are only three registers on the machine, and that REG(0) and REG(1) are to be used for parameter passing and REG(0) for return values. This means that the formal x will be in register REG(0), and the formals u and v in registers REG(0) and REG(1). In generating MLRisc for F, the register containing x, is overwritten by the call, yet x is needed after the call. It is therefore necessary to save x in memory before the call. Under these assumptions the code (written as three-address codes) to be generated in our example is:
F:
save x in memory
r1 := r0 ;; argument 1
r0 := r0 * r0 ;; argument 2
call(G) ;; G(y,x)
restore x from memory
r0 := r0 + r1 ;; return(w+x)
ret
G:
r2 := r1 * 100 ;; temp := v*100
r2 := r2 / r0 ;; temp := temp / u
r0 := r2 + r1 ;; return(temp/u)
ret
There have been a large number of fairly complicated decisions made in generating this code. First was the need to save and restore x. Another was the use of the temporary register REG(2) in the fuction G.
Being able to assume an infinite number of registers provides a significant simplification. Further, if all formal parameters are moved into fresh temporaries, then we need not be concerned about register conflicts, and the spill phase of a register allocator will save and restore values in memory as needed.
There is another problem with the code that has been generated. All the call sites for the fuction G are known since it is declared to be static. This means that we can adopt a more appropriate parameter passing convention. By moving all parameters into fresh temporaries, we limit the number of artifical dependencies, and give the register allocator a better chance at copy propagation. The code generated for the example program would then be.
F:
t1 := r0 ;; move x into fresh temporary
t2 := t1 * t1 ;; y
t100 := t2 ;; argument 1
t200 := t1 ;; argument 2
call(G) ;; G(y,x)
t3 := t300 + t1 ;; t3 := w + x
r0 := t3 ;; return(w+x)
ret
G:
t1000 := t100 ;; move u to fresh temporary
t2000 := t200 ;; move v to fresh temporary
t2001 := t2000 * 100 ;; v * 100
t2002 := t2001 / t1000 ;; temp/u
t300 := t2002 + t2000 ;; return(temp + v)
ret
We have assumed that the function G takes its arguments in registers t100 and t200 and returns its result in t300 --- all pseudo-registers. The argument to F has been copied into the temporary t1. This program was trivial to generate, but we now have a program that has a lot of moves. It is fairly easy for a good register allocator to coalesce these moves. For example the following register assignments,
| Temp | Assignment |
|---|---|
| t1 | r0 |
| t2 | r1 |
| t100 | r1 |
| t200 | r0 |
| t1000 | r1 |
| t2000 | r0 |
| t2001 | r2 |
| t2002 | r1 |
| t300 | r1 |
| t3 | r0 |
F:
r1 := r0 * r0 ;; y
call(G) ;; G(y,x)
r0 := r1 + r0 ;; return(w+x)
ret
G:
r2 := r0 * 100 ;; v * 100
r1 := r2 / r1 ;; (v * 100) / u
r0 := r1 + r0 ;; (v * 100) / u + v
ret
This interprocedural register allocation has resulted in an excellent register assignment. The arguments to function G are passed in registers REG(1) and REG(0) and the result in REG(0). It was not necessary to save and restore the value of x when making the call to G.
Moving registers into fresh temporaries has the effect of limiting the live extent of temporaries to the body of the function. Copy propagation may stretches these live extents where possible by coalescing the source and destination of move instructions. This technique need not be limited to formal parameters at function entry points, but can be used at:
Generating the moves described above can result in a large number of instructions being generated. This can have an impact an space and time used by the compiler. However, there is a more serious problem; consider the set of moves defined by:
r1 := t3
...
t4 := r1
Assume that it is desirable to coalesce t3 with r1. In the sequence of moves defined above, this is not permissible as r1 is used later. The sequential ordering of moves generated has imposed constraints on the copy propagation algorithm. It would have been permissible to coalesce r1 and t3, if the sequence generated had reversed.
To address this issue, MLRisc has a parallel copy construct COPY(dstList, srcList), and FCOPY(dstList, srcList) for floating point registers. These instructions copy, in parallel, the registers in srcList into the corresponding registers in dstList. Duplicate registers in dstList is an error which is not currently checked.
Submit a comment on this page
Author: Lal George
Last Modified: September 4, 1996
Copyright © 1996 Bell Laboratories