Project 4: Code lowering

Due: Wednesday, November 16, 2016


In this project we will implement a translator that lowers "linearizes" the program representation to something that looks more like assembly code. The goal is to produce something that is easy to analyze for register allocation and instruction selection -- low level, but not too low level.

Project Description

Start by downloading the code framework for the MIR structure ("Medium-level Intermediate Representation"). It includes three main parts: (1) the definition of the MIR code representation, (2) the outline of the lowering functions, which you will fill in, and (3) a pretty-printer for the MIR code.

Link: mir.sml

MIR representation

The MIR structure has two different kinds of structures: instructions and trees. Instructions primarily represent the different kinds of control flow, including labels and jumps, and call and return. The MOVE instruction encapsulates most kinds of computations. Within these instructions, trees are used to compute various operands. Trees are expressions with no control flow and no side-effects (all side effects occur at the level of the MOVE instruction). This property will be nice later when we are doing program analysis and instruction selection.

The meaning of each instruction is as follows:

The meaning of each tree construct is:

Function interfaces

I am providing you with an entry-point function called lowerProgram, which you can call from your driver code. It calls lowerFun, which translates a single function declaration (which I am also providing). The main work is done in lowerExp, which handles all the different kinds of AST expressions. The primary work in this assignment is completing all of the cases marked raise NotImplemented in this function.

The interface to lowerExp is as follows:

val lowerExp : AST.exp -> MIR.tree * MIR.inst list * MIR.funrep list

It takes an AST expression and produces three things: (1) an expression tree representing the value of the whole AST expression, (2) a sequence of instructions that are needed to compute this value, and (3) a list of any functions that were lowered during the process of lowering this one. The third case is needed because any Tiger expression can use let to introduce new functions.

A typical case in lowerExp calls itself recursively to lower any subexpressions, then assembles a new tree and a list of instructions from those parts in order to represent the whole construct. The ASSIGN case in the started code is a good example.

Tips and pitfalls

Start by implementing let and expression sequences, so that you can test some very simple programs. Then dig into the more interesting cases. Update your driver program to call MIR.printProgram (MIR.lowerProgram absyn).

The most interesting case, IMHO, is handling conditionals with short-circuiting logical operators, AND and OR. Start by defining the IF construct without logical operators. Then think about how to make it more general. Remember that Tiger conditionals are a lot more restrictive than C: the conditions must consist of one or more comparisons, joined by logical operators. We cannot write things like if x | y then ... .

HINT: think about writing a helper function for conditionals that takes labels are arguments.

Submitting your work

Submit your mir implementation in mir.sml. Please include a plain-text file describing (a) anyone you worked with, and (b) any other interesting details about your implementation.

provide comp181 lower mir.sml description.txt

Back to Comp181