CSE5317/4305 Project #7 (Instruction Selection)

Due Thursday May 2 before midnight

Worth 14% of your project grade


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 mips method in the file Mips.gen that generates MIPS code from the IR and returns the register that will hold the result. A simple register allocation algorithm is provided. It uses a pool of temporary registers, which is reset 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 mips 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 7 hello
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 7 hello
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.

On Linux/MacOS, you can use this solution script to compile and execute the solution using SPIM. You can run your program using the run script. On Windows, you must edit your solution.bat and run.bat scripts similarly.

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

run 7 hello
that will convert your IR code into MIPS using the solution and will run it using SPIM. (If it gives you a compilation error in PCAT.java, remove the line "Mips.rpool = new RegisterPool();".)

When you make sure that your IR code generates the correct MIPS using the solution, then you can start writting your own Mips.gen 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 #7:

Last modified: 04/16/13 by Leonidas Fegaras