Implement Instruction Selection

Instruction Selection for the MIPS

Build an instruction selector IR2ASM for programs in intermediate representation that produces MIPS code. This essentially consists of defining rules that cover all combinations of IR expressions and map them to MIPS instructions.

The instruction selection component should be implemented in IR2ASM.r in the TigerTrans package. In order to build the component you'll also need to install the ASM package, which implements the back-end and provides the signature and OverlayDefinitions for MIPS code.

Notes

• Use the OverlayDefinitions in MIPS.r (from the ASM package) as compact representations of abstract assembly code instructions.

• First define a basic instruction selection scheme that covers all IntermediateRepresentation constructs. Then try to find more complex patterns that produce more efficient code.

• Expressions produce results. In assembly code intermediate results should be stored in registers. If the IR expression does not explicitly move the result into a register, you'll have to invent a new temporary to put the result in and to retrieve it from in the next expression.

• In order to construct a correct control-flow graph, all branching instructions need to have all possible labels they can branch to in their labels argument. This includes the label of the next instruction in case the instruction can fall through. Also be aware of the fact that jal returns to the next instruction.

• Make small test programs to test your instruction selection scheme.

-- EelcoVisser - 13 Nov 2001