CSE5317/4305 Project #6 (Instruction Selection)

Due Friday May 6 before midnight

Worth 15% of your project grade

This project is required for Graduate student but it is optional for Undergraduate students. If you are an undergraduate student and you do not 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/main/scala/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 an 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:

scala lib/pcat.jar 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:
scala pcat-solution.jar 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.

After ensuring that your program compiles and executes correctly, cleanup your pcat directory using mvn clean Then, zip the pcat directory into the file pcat.zip. Then submit your zip file here:

Submit Project #6:

Last modified: 04/11/2016 by Leonidas Fegaras