Home
Syllabus
Lecture Notes

Resources

 CS4410/6410: Compilers
Spring 2013

Problem Set 0: An introduction to ML and MIPS

Due Wednesday, 23 Jan 2013, 11:59pm

The goal of this problem set is to expose you to programming in ML and to learn a few details of the MIPS instruction set architecture.

Instructions: We have provided skeleton code which you can find here. Your job is to fill in the parts of the skeleton code marked TODO. To submit your work, create a zip archive containing all of the files provided in the original skeleton code distribution. Please name the zip archive ps0-lastname1-lastname2, where lastname is replaced with your own. We encourage you to work with a partner (there is a lot of code here). If the zip archive does not compile with make, then they will not be accepted. If you run out of time, it's better to comment out the parts that aren't working than to submit something that won't compile. Submit your assignment by emailing the zip archive to 4410staff at ccs.neu.edu. (Pay attention to the piazza forum for any announcements on a change in submission process.)

There are two parts to this assignment. The first part consists of writing a MIPS assembler. In the second part, you will implement an interpreter for a subset of the MIPS instruction set.

Part 1: MIPS Assembler

In this part, you will build an assembler for a subset of MIPS assembly. The assembler translates assembly code into machine code, the code that runs on hardware. This exercise will demonstrate how we get from assembly code, something that is still somewhat human-readable, to machine code. To do this part of the assignment, you will need to understand how MIPS assembly is encoded at the level of bits. To this end, the MIPS documentation is your friend. You can find information about how to encode instructions (and their semantics) in chapter A.10.2 (starting with page A-49) of the SPIM Simulator chapter. Your job is to write the assem function in mips_sim.ml. 
let rec assem (prog : program) : state
At a high level, you will transform a list of assembly instructions, a program, into an intial starting state. A state consists of a register file, memory and program counter. Refer to the skeleton code for more information.

Part 2: MIPS Interpreter

In this part, you will build an interpreter for MIPS code, similar to the SPIM simulator. The goal of this exercise is to become more familiar with the MIPS instruction set architecture and to gain more experience writing ML code. The interpreter is structured as a function: 
let rec interp (init_state : state) : state
Your job is to write the interp function which simulates one step of execution at a time until program termination (for the purposes of this assignment, treat the 0x00000000 as the program termination "instruction"). During a step, you should fetch a word's worth (4 bytes) of values from memory, starting at the address given by the program counter. (It doesn't matter which Endian-ness you pick, but be consistent.)

You should then decode the instruction and perform the associated operation. For example, if the instruction bytes decode to an "add $1,$2,$3", then you should update register one, with the sum of the values in registers two and three, and update the program counter so that it points to the next instruction. Look closely at the Int32 module Ocaml standard library as it provides most of the functions that you will need for doing bit manipulation.

Important!! Note that the load immediate (li) instruction is a pseudoinstruction. This means that its ok to use it in a Mips assembly program, with the caveat that Mips hardware does not actually support this instruction. Instead, the hardware supports a li instruction by encoding it as two instructions, a lui and ori. Thus, your assembler should accept any Mips assembly program that contains a li instruction, but your interp function should only accept lui and ori instructions to model the Mips hardware.