CSE5317/4305 Project #6 (Instruction Selection -- optional)

Due Friday May 8 before midnight

Worth 15% of your project grade


This project is optional. If you don't do this project you will get 100 (6.0 points in your final score), but if you complete this project successfully you will get up to 150 (6.0+3.0=9.0 points in your final score).

This is the final stage of your project in which you are asked to translate IRs into MIPS code. For this project, the goal is to generate correct MIPS code that runs and computes the correct results of a PCAT program.

You should modify the emit method in the file pcat/src/edu/uta/pcat/MIPS.scala that generates MIPS code from the IR and returns the register that will hold the result. Note that, at the Main program before this stage, the IR code generated in Project #5 is normalized by the normalize method in Normalize.scala (ie, Seq and ESeq have been removed), into a list of IRStmt. Your task is to generate MIPS code for each one of these IRstmt.

A simple register allocation algorithm is provided in MIPS.scala. It uses a pool of temporary registers, which is reinitialized at the beginning of each IR statement. Even though there is a danger of running out of registers for complex expressions, it is not expected to be so for the given test programs. It's very important to recycle registers (ie, to put registers back to pool after they are used). The rule is, if you don't return a register from a emit method, it should be recycled. The MIPS code for the Call IR is also provided because it requires to store the used registers in the run-time stack before the call and to restore them after the call. If you don't do so, there will be interference between the temporary registers of caller and callee. This means that all temporary registers are caller-save.

You need to run your parser against all tests/*.pcat files. For example:

run 6 tests/hello.pcat
It will generate MIPS code from tests/hello.pcat into the file tests/hello.s and will load and execute the code using the SPIM emulator. You also need to compare your output with that of the solution:
solution 6 tests/hello.pcat
Don't expect to get exactly the same output because the solution uses very few optimizations.

The SPIM emulator can be downloaded from http://spimsimulator.sourceforge.net/. You can run a MIPS assembly program, say tests/hanoi.s, using qtspim -file tests/hanoi.s.

One clever way to start this project is to temporarily remove the MIPS.scala file and run, eg.

run 6 tests/hello.pcat
that will convert your IR code into MIPS using the solution and will run it using SPIM.

When you make sure that your IR code generates the correct MIPS using the solution, then you can start writting your own MIPS.scala code to generate similar MIPS code.

After ensuring that your program compiles and executes correctly, cleanup your pcat directory using clean Then, if you are using Linux/MacOS, archive your pcat directory using tar cfz pcat.tgz pcat. If you are using Windows, zip the pcat directory into the file pcat.zip. Then submit your file (pcat.tgz or pcat.zip) here:

Submit Project #6:

Last modified: 04/21/2015 by Leonidas Fegaras