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:

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:
solution TBD
solution with a stack TBD

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):
solution TBD

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.
solution TBD

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.
solution TBD

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:
  1. 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:

  2. 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).

  3. The function compile_program which applies compile_instr to all program instructions and add code:

Indications: we can proceed build by build, testing each time, in the following order:

  1. constant expression Cst, instruction Print and exit with system call 10;
  2. arithmetic operations (Binop constructor);
  3. global variables (Var and Set constructors);
  4. 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
solution TBD
return to the course homepage