PROGRAM INSTRUCTION SELECTION

Implement the translation to Assem-instructions for your favorite instruction set (let μ stand for Sparc, Mips, Alpha, Pentium, etc.) using maximal munch. If you would like to generate code for a RISC machine, but you have no RISC computer on which to test it, you may wish to use SPIM (a MIPS simulator implemented by James Larus), described on the Web page for this tutorial. First write the class μ.Codegen implementing the "maximal munch" translation algorithm from IR trees to the Assem data structure. Use the Canon module (described in ) to simplify the trees before applying your Codegen module to them. Use the format function to translate the resulting Assem trees to μ assembly language. Since you won't have done register assignment, just pass new Temp.DefaultMap() to format as the translation function from temporaries to strings.

package Temp;
public class DefaultMap implements TempMap {
 public String tempMap(Temp.Temp t) {
 return t.toString();
 }
}

This will produce "assembly" language that does not use register names at all: The instructions will use names such as t3, t283, and so on. But some of these temps are the "built-in" ones created by the Frame module to stand for particular machine registers (see page 143), such as Frame.FP. The assembly language will be easier to read if these registers appear with their natural names (e.g., fp instead of t1). The Frame module must provide a mapping from the special temps to their names, and nonspecial temps to null:

package Frame;
public class Frame implements Temp.TempMap {
 ⋮
 abstract public String tempMap(Temp temp);
}

Then, for the purposes of displaying your assembly language prior to register allocation, make a new TempMap function that first tries frame.tempMap, and if that returns null, resorts to Temp.toString().

REGISTER LISTS

Make the following lists of registers; for each register, you will need a string for its assembly language representation and a Temp.Temp for referring to it in Tree and Assem data structures.

• specialregs a list of μ registers used to implement "special" registers such as RV and FP and also the stack pointer SP, the return-address register RA, and (on some machines) the zero register ZERO. Some machines may have other special registers;
• argregs a list of μ registers in which to pass outgoing arguments (including the static link);
• calleesaves a list of μ registers that the called procedure (callee) must preserve unchanged (or save and restore);
• callersaves a list of μ registers that the callee may trash.

The four lists of registers must not overlap, and must include any register that might show up in Assem instructions. These lists are not public, but they are useful internally for both Frame and Codegen - for example, to implement munchArgs and to construct the calldefs list. Implement the procEntryExit2 function of the μ.Frame class.

package Frame;
class Frame implements Temp.TempMap {
 ⋮
 abstract public Assem.InstrList procEntryExit2(
 Assem.InstrList body);
}

This function appends a "sink" instruction to the function body to tell the register allocator that certain registers are live at procedure exit. In the case of the Jouette machine, this is simply:

package Jouette;
class Frame extends Frame.Frame {
 ⋮
 static TempList returnSink =
 L(ZERO, L(RA, L(SP, calleeSaves)));
 static Assem.InstrList append(Assem.InstrList a,
 Assem.InstrList b) {
 if (a==null) return b;
 else {Assem.InstrList p;
 for(p=a; p.tail!=null; p=p.tail) {}
 p.tail=b;
 return a;
 }
 }
public Assem.InstrList procEntryExit2(
 Assem.InstrList body) {
 return append(body,
 new Assem.InstrList(
 new Assem.OPER("", null, returnSink),null));
 }
}

meaning that the temporaries zero, return-address, stack pointer, and all the callee-saves registers are still live at the end of the function. Having zero live at the end means that it is live throughout, which will prevent the register allocator from trying to use it for some other purpose. The same trick works for any other special registers the machine might have. Files available in $MINIJAVA/chap9 include: Canon/* Canonicalization and trace generation. Assem/* The Assem module. Main/Main.java A Main module that you may wish to adapt. Your code generator will handle only the body of each procedure or function, but not the procedure entry/exit sequences. Use a "scaffold" version of Frame.procEntryExit3 function:

package μ;
class Frame extends Frame.Frame {
 ⋮
 public Frame.Proc procEntryExit3(Assem.InstrList body) {
 return new Frame.Proc(
 "PROCEDURE " + name.toString() + "\n",
 body,
 "END " + name.toString() + "\n");
 }
}