INSTRUCTION SELECTION FOR THE MiniJava COMPILER

Pattern-matching of "tiles" is simple (if tedious) in Java, as shown in Program 9.3. But this figure does not show what to do with each pattern match. It is all very well to print the name of the instruction, but which registers should these instructions use? In a tree tiled by instruction patterns, the root of each tile will correspond to some intermediate result held in a register. Register allocation is the act of assigning register numbers to each such node. The instruction selection phase can simultaneously do register allocation. However, many aspects of register allocation are independent of the particular target-machine instruction set, and it is a shame to duplicate the registerallocation algorithm for each target machine. Thus, register allocation should come either before or after instruction selection. Before instruction selection, it is not even known which tree nodes will need registers to hold their results, since only the roots of tiles (and not other labeled nodes within tiles) require explicit registers. Thus, register allocation before instruction selection cannot be very accurate. But some compilers do it anyway, to avoid the need to describe machine instructions without the real registers filled in. We will do register allocation after instruction selection. The instruction selection phase will generate instructions without quite knowing which registers the instructions use.

ABSTRACT ASSEMBLY LANGUAGE INSTRUCTIONS

We will invent a data type for "assembly language instruction without register assignments", called Assem.Instr:

package Assem;
import Temp.TempList;
public abstract class Instr {
 public String assem;
 public abstract TempList use();
 public abstract TempList def();
 public abstract Targets jumps();
 public String format(Temp.TempMap m);
}
public Targets(Temp.LabelList labels);
public OPER(String assem, TempList dst, TempList src,
 Temp.LabelList jump);
public OPER(String assem, TempList dst, TempList src);
public MOVE(String assem, Temp dst, Temp src);
public LABEL(String assem, Temp.Label label);

An OPER holds an assembly language instruction assem, a list of operand registers src, and a list of result registers dst. Any of these lists may be empty. Operations that always fall through to the next instruction are constructed with OPER(assem,dst,src) and the jumps() method will return null; other operations have a list of "target" labels to which they may jump (this list must explicitly include the next instruction if it is possible to fall through to it). The use() method returns the src list, and the def() method returns the dst list, either of which may be null. A LABEL is a point in a program to which jumps may go. It has an assem component showing how the label will look in the assembly language program and a label component identifying which label symbol was used. A MOVE is like an OPER, but must perform only data transfer. Then, if the dst and src temporaries are assigned to the same register, the MOVE can later be deleted. The use() method returns a singleton list src, and the def() method returns a singleton list dst. Calling i.format(m) formats an assembly instruction as a string; m is an object implementing the TempMap interface, which contains a method to give the register assignment (or perhaps just the name) of every temp.

package Temp;
public interface TempMap {
 public String tempMap(Temp.Temp t);
}

Machine independence. The Assem.Instr class is independent of the chosen target-machine assembly language (though it is tuned for machines with only one class of register). If the target machine is a Sparc, then the assem strings will be Sparc assembly language. We will use Jouette assembly language for illustration. For example, the tree

could be translated into Jouette assembly language as

new OPER("LOAD 'd0 <- M['s0+8]",
 new TempList(new Temp(), null),
 new TempList(frame.FP(), null));

This instruction needs some explanation. The actual assembly language of Jouette, after register allocation, might be

LOAD r1 <- M[r27+8]

assuming that register r₂₇ is the frame pointer fp and that the register allocator decided to assign the new temp to register r₁.Butthe Assem instruction does not know about register assignments; instead, it just talks of the sources and destination of each instruction. This LOAD instruction has one source register, which is referred to as 's0, and one destination register, referred to as 'd0. Another example will be useful. The tree

could be translated as

where t908, t909, and t910 are temporaries newly chosen by the instruction selector. After register allocation the assembly language might look like:

ADDI r1 <- r12+3
LOAD r2 <- M[r13+0]
MUL r1 <- r1 * r2

The string of an instr may refer to source registers 's0, 's1, … 's(k − 1), and destination registers 'd0, 'd1, etc. Jumps are OPER instructions that refer to labels 'j0, 'j1, etc. Conditional jumps, which may branch away or fall through, typically have two labels in the jump list but refer to only one of them in the assem string. Two-address instructions Some machines have arithmetic instructions with two operands, where one of the operands is both a source and a destination. The instruction add t1,t2, which has the effect of t₁ ← t₁ + t₂, can be described as

assem dst src
 add 'd0,'s1 t1 t1, t2

where 's0 is implicitly, but not explicitly, mentioned in the assem string.

PRODUCING ASSEMBLY INSTRUCTIONS

Now it is a simple matter to write the right-hand sides of the pattern-matching clauses that "munch" Tree expressions into Assem instructions. We will show some examples from the Jouette code generator, but the same ideas apply to code generators for real machines. The functions munchStm and munchExp will produce Assem instructions, bottom-up, as side effects. MunchExp returns the temporary in which the result is held.

Temp.Temp munchExp(Tree.Exp e);
void munchStm(Tree.Stm s);

The "actions" of the munchExp clauses of Program 9.3 can be written as shown in Programs 9.5 and 9.6.Assem-instructions for munchStm.

TempList L(Temp h, TempList t) {return new TempList(h,t);}
munchStm(SEQ(a,b))
 {munchStm(a); munchStm(b);}
munchStm(MOVE(MEM(BINOP(PLUS,e1,CONST(i))),e2))
 emit(new OPER("STORE M['s0+" + i + "] <- 's1\n",
 null, L(munchExp(e1), L(munchExp(e2), null))));
munchStm(MOVE(MEM(BINOP(PLUS,CONST(i),e1)),e2))
 emit(new OPER("STORE M['s0+" + i + "] <- 's1\n",
 null, L(munchExp(e1), L(munchExp(e2), null))));
munchStm(MOVE(MEM(e1),MEM(e2)))
 emit(new OPER("MOVE M['s0] <- M['s1]\n",
 null, L(munchExp(e1), L(munchExp(e2), null))));
munchStm(MOVE(MEM(CONST(i)),e2))
 emit(new OPER("STORE M[r0+" + i + "] <- 's0\n",
 null, L(munchExp(e2), null)));
munchStm(MOVE(MEM(e1),e2))
 emit(new OPER("STORE M['s0] <- 's1\n",
 null, L(munchExp(e1), L(munchExp(e2), null))));
munchStm(MOVE(TEMP(i), e2))
 emit(new OPER("ADD 'd0 <- 's0 + r0\n",
 L(i,null), L(munchExp(e2), null)));
munchStm(LABEL(lab))
 emit(new Assem.LABEL(lab.toString() + ":\n", lab));

munchExp(MEM(BINOP(PLUS,e1,CONST(i))))
 Temp r = new Temp();
 emit(new OPER("LOAD 'd0 <- M['s0+" + i + "]\n",
 L(r,null), L(munchExp(e1),null)));
 return r;
munchExp(MEM(BINOP(PLUS,CONST(i),e1)))
 Temp r = new Temp();
 emit(new OPER("LOAD 'd0 <- M['s0+" + i + "]\n",
 L(r,null), L(munchExp(e1),null)));
 return r;
munchExp(MEM(CONST(i)))
 Temp r = new Temp();
 emit(new OPER("LOAD 'd0 <- M[r0+" + i + "]\n",
 L(r,null), null));
 return r;
munchExp(MEM(e1))
 Temp r = new Temp();
 emit(new OPER("LOAD 'd0 <- M['s0+0]\n",
 L(r,null), L(munchExp(e1),null)));
 return r;
munchExp(BINOP(PLUS,e1,CONST(i)))
 Temp r = new Temp();
 emit(new OPER("ADDI 'd0 <- 's0+" + i + "\n",
 L(r,null), L(munchExp(e1),null)));
 return r;
munchExp(BINOP(PLUS,CONST(i),e1))
 Temp r = new Temp();
 emit(new OPER("ADDI 'd0 <- 's0+" + i + "\n",
 L(r,null), L(munchExp(e1),null)));
 return r;
munchExp(CONST(i))
 Temp r = new Temp();
 emit(new OPER("ADDI 'd0 <- r0+" + i + "\n",
 null, L(munchExp(e1),null)));
 return r;
munchExp(BINOP(PLUS,e1,e2))
 Temp r = new Temp();
 emit(new OPER("ADD 'd0 <- 's0+'s1\n",
 L(r,null), L(munchExp(e1),L(munchExp(e2),null))));
 return r;
munchExp(TEMP(t))
 return t;

The emit function just accumulates a list of instructions to be returned later, as shown in Program 9.7.The Codegen class.

package Jouette;
public class Codegen {
 Frame frame;
 public Codegen(Frame f) {frame=f;}
 private Assem.InstrList ilist=null, last=null;
 private void emit(Assem.Instr inst) {
 if (last!=null)
 last = last.tail = new Assem.InstrList(inst,null);
 else last = ilist = new Assem.InstrList(inst,null);
 }
 void munchStm(Tree.Stm s) { ... }
 Temp.Temp munchExp(Tree.Exp s) { ... }
 Assem.InstrList codegen(Tree.Stm s) {
 Assem.InstrList l;
 munchStm(s);
 l=ilist;
 ilist=last=null;
 return l;
 }
}
package Frame;
public class Frame {
 ...
 public Assem.InstrList codegen(Tree.Stm stm); {
 return (new Codegen(this)).codegen(stm);
 }
}

PROCEDURE CALLS

Procedure calls are represented by EXP(CALL(f, args)), and function calls by MOVE(TEMP t, CALL(f, args)). These trees can be matched by tiles such as

munchStm(EXP(CALL(e,args)))
 {Temp r = munchExp(e); TempList l = munchArgs(0,args);
 emit(new OPER("CALL 's0\n",calldefs,L(r,l)));}

In this example, munchArgs generates code to move all the arguments to their correct positions, in outgoing parameter registers and/or in memory. The integer parameter to munchArgs is i for the ith argument; munchArgs will recur with i + 1 for the next argument, and so on. What munchArgs returns is a list of all the temporaries that are to be passed to the machine's CALL instruction. Even though these temps are never written explicitly in assembly language, they should be listed as "sources" of the instruction, so that liveness analysis () can see that their values need to be kept up to the point of call. A CALL is expected to "trash" certain registers - the caller-save registers, the return-address register, and the return-value register. This list of calldefs should be listed as "destinations" of the CALL, so that the later phases of the compiler know that something happens to them here.

In general, any instruction that has the side effect of writing to another register requires this treatment. For example, the Pentium's multiply instruction writes to register edx with useless high-order result bits, so edx and eax are both listed as destinations of this instruction. (The high-order bits can be very useful for programs written in assembly language to do multiprecision arithmetic, but most coding languages do not support any way to access them.)

IF THERE'S NO FRAME POINTER

In a stack frame layout such as the one shown in Image 6.2, the frame pointer points at one end of the frame and the stack pointer points at the other. At each procedure call, the stack pointer register is copied to the frame pointer register, and then the stack pointer is incremented by the size of the new frame. Many machines' calling conventions do not use a frame pointer. Instead, the "virtual frame pointer" is always equal to stack pointer plus frame size. This saves time (no copy instruction) and space (one more register usable for other purposes). But our Translate phase has generated trees that refer to this fictitious frame pointer. The codegen function must replace any reference to FP+k with SP + k + fs, where fs is the frame size. It can recognize these patterns as it munches the trees. However, to replace them it must know the value of fs, which cannot yet be known because register allocation is not known. Assuming the function f is to be emitted at label L14 (for example), codegen can just put sp+L14_framesize in its assembly instructions and hope that the prologue for f (generated by Frame.procEntryExit3) will include a definition of the assembly language constant L14_framesize. Codegen is passed the frame argument (Program 9.7) so that it can learn the name L14.

Implementations that have a "real" frame pointer won't need this hack and can ignore the frame argument to codegen. But why would an implementation use a real frame pointer when it wastes time and space to do so? The answer is that this permits the frame size to grow and shrink even after it is first created; some languages have permitted dynamic allocation of arrays within the stack frame (e.g., using alloca in C). Calling-convention designers now tend to avoid dynamically adjustable frame sizes, however.