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.
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.
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:
LABELmarks the position of the next real instruction (i.e., multiple labels in a row denote the same position). Labels must be unique within a function, and you can generate unique names using the gensym function.
MOVEis essentially assignment. The contents of the second operand are loaded and then stored in the location denoted by the first operand.
CALLcalls a function. The first symbol is the name of the function to call; the second symbol is the name of a variable to hold the result of the call; the remaining expressions are the actual arguments.
RETreturns from a function. The expression gives the value to return.
JUMPis an unconditional jump. The symbol must denote a label in the given function.
CJUMPis a conditional jump. The two trees are compared according to the comparison operator, and control jumps to the label denoted by the last symbol if the condition is true.
The meaning of each tree construct is:
STRINGdenote compile-time constants.
OFFSETis used to represent a field offset within a record. For now, it is just a symbolic value, but eventually it will be an actual integer offset. It should always be used in combination with PLUS and MEM (see DOT example in the code).
VARis just a variable.
BINOPis a binary operation between two expressions.
MEMtreats the given expression tree as computing an address, which it accesses indirectly. It's semantics are like the "*" star operator in C: when it appears on the left-hand side, it is a "store"; when it appears on the right-hand side, it is a "load".
I am providing you with an entry-point function
lowerProgram, which you can call from your driver code. It
lowerFun, which translates a single function declaration
(which I am also providing). The main work is done in
which handles all the different kinds of AST expressions. The primary work in
this assignment is completing all of the cases marked
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
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.
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
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.
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