Lab 8 - MIPS Assembly Code
(Designed by Jean-Christophe Filliâtre)
The goal of this lab is to manipulate MIPS assembly - first directly by writing manually some small MIPS programs and
then by implementing a compiler for a mini-language of arithmetic expressions generating automatically MIPS code.
Documentation and MIPS simulators
MIPS Documentation
MIPS Simulators:
-
SPIM
- on a command line : spim -file fichier.s
- interactively : xspim or xspim -file fichier.s
-
MARS
- on a command line : java -jar Mars4_4.jar fichier.s
- interactively : java -jar Mars4_4.jar
1. Writing small MIPS assembly programs
Recall that a MIPS program is written in a file bearing the suffix .s and having the following form:
.text
main:
...
li $v0, 10 # exit
syscall
.data
...
a. Arithmetic Expressions
Write assembly programs to evaluate and display results of the following arithmetic expressions:
- 4 + 6
- 21 * 2
- 4 + 7 / 2
- 3 - 6 * (10 / 5)
b. Boolean Expressions
Taking the convention that the integer 0 represents the value Boolean false and any other integer represents the value true ,
write assembly programs that evaluate and displays the results of the following expressions (you must display true or false
in the case of a Boolean result):
- true && false
- if 3 <> 4 then 10 * 2 else 14
- 2 = 3 || 4 <= 2*3
c. Global Variables
Write an assembly program that evaluates the three instructions following:
let x = 2
let y = x * x
print (y+x)
We will allocate the variables x and y in the data segment.
d. Local Variables
Write an assembly program that evaluates the following program:
print (let x = 3 in x * x)
print (let x = 3 in (let y = x + x in x * y) + (let z = x + 3 in z / z))
We will allocate the variables x, y, and z on the stack.
2. Compilation of a mini-langage
The goal of this exercise is to implement a compiler for a mini-language of arithmetic expressions, called Arith below, to the MIPS assembly code.
An Arith program is composed of a sequence of instructions, which are either the introduction of a global variable with the syntax
set <ident> = <expr>
or printing the avalue of an expression with a syntax
print <expr>
Here, <ident> denotes a variable name and
<expr> an arithmetic expression.
Arithmetic expressions can be constructed from integer constants, variables, addition, subtraction, of multiplication, of division, negation, parentheses and a
construction let inintroducing a local variable. More formally, the syntax of arithmetic expressions is therefore as follows:
<expr> ::= <integer constant>
| <ident>
| ( <expr> )
| <expr> + <expr>
| <expr> - <expr>
| <expr> * <expr>
| <expr> / <expr>
| - <expr>
| let <ident> = <expr> in <expr>
Here is an example of an Arith program:
set x = 1 + 2 + 3*4
print (let y = 10 in x + y)
Variable names are made up of letters and numbers and do not can start with a number.
The words set, print , let and in are reserved, i.e. they cannot be used as variable names.
The priority of the operators is usual and the construction let in has the lowest priority.
In order to help you build this compiler, we let's provide its basic structure (in the form of a set of Caml files and a Makefile/dune files)
which you can download here: arithc.tar.gz . Once this archive decompressed with tar zxvf arithc.tar.gz,
you obtain a directory arithc/ containing the following files:
ast.mli | abstract syntax of Arith (implemented)
|
lexer.mll | lexer (implemented)
|
parser.mly | parser (implemented)
|
mips.mli, mips.ml | (implemented,
but you shoud take a close look on those files)
|
compile.ml | la compilation phase (NOT implemented, TODO)
|
main.ml | main program (implemented)
|
Makefile/dune | to automatize the compilation process (implemented)
|
The provided code compiles; to compile it, e.g. do make in a terminal.
However, the compile.ml code is incomplete: and the generated MIPS code is empty before you complete it.
So you must complete the compile.ml file.
The executable is called main.exe and can be applied to an Arith file with the suffix .exp:
./main.exe file.exp
which has the effect of producing a file.s containing the MIPS code.
Compilation scheme
We will carry out a simple compilation using the stack to store intermediate values (i.e. the values of sub-expressions).
Recall that an integer value occupies 4 bytes in memory and that we can allocate 4 bytes on the stack by subtracting 4 to the value of $sp.
Global variables will be allocated in the data segment (directive .data of the MIPS assembler; here it corresponds to field data of type Mips.program).
Local variables will be allocated at the bottom of the stack. The necessary space for all local variables will be allocated at the start of the
program (by appropriate subtraction of $sp ).
register The $fp will be positioned so as to point at the bottom of the pile;
thus all reference to a local variable will be made with respect to $fp.
Work to do
You must carefully read the code that is located in compile.ml.
The parts to be completed, marked (* TODO *), are as follows:
- The function compile_expr which compiles an arithmetic expression e into a sequence of MIPS instructions
whose effect is to place the value of the expression e at the top of the stack.
This function is defined using a local recursive function comprec which takes the following arguments:
- an env parameter of type int StrMap.t : this is a dictionary indicating for each local variable its position on the stack (relative to $fp);
- a parameter next of type int that indicates the first free location for a local variable (w.r.t. to $fp);
- the expression to compile, on which pattern-matching is carried out.
- The function compile_instr which compiles an instruction Arith in a sequence of MIPS instructions.
In both cases (set x = e or print e), we must start by compiling e,
then we find the value of e at the top of the stack (don't forget to pop).
- The function compile_program which applies compile_instr to all program instructions and add code:
- before, in particular to allocate space for local variables and set $fp;
- afterwards, to restore the stack and terminate the program with system call 10 (exit).
Indications: we can proceed build by build, testing each time, in the following order:
- constant expression Cst, instruction Print and
exit with system call 10;
- arithmetic operations (Binop constructor);
- global variables (Var and Set constructors);
- local variables (Letin and Var constructors).
We will test with the test.exp file (also provided), the result of which should be the following:
60
50
0
10
55
60
20
43
return to the course homepage