Project 6: Instruction Selection

Due 11:59am Wednesday December 8th, 2004

Description

In this project you will be traversing the Intermediate Representation Tree that was created in project 5 and outputting the PowerPC assembly code.

Directions

Read chapter 8 and 9 of Appel.
Observe the reference implementation. It can be run with the command:
/homes/cs352/bin/p3 inputfile.java | /homes/cs352/bin/p4 | /homes/cs352/bin/p5 | /homes/cs352/bin/p6
This means that your translator should accept the Intermediate Representation Tree from standard input (System.in).
You will need to modify your existing parser to:
- Read in the output of P5.
- Rebuild the Intermediate Representation Tree.
- Output the PowerPC assembly code.
To create the Intermediate Representation Tree, you will need to create/add to the following packages:
- Canon
- Assem
- PowerPC
New Package Cannon (chap 8):
- Canon.java - Removes ESEQs and moves CALLs to top level
- BasicBlocks.java - Groups statements into sequences of straight-line code
- TraceSchedule.java - Orders the blocks so that every CJUMP is followed by its false label
New Package Assem (chap 8):
- Instr.java
- LABEL.java
- MOVE.java
- OPER.java
Package PowerPC will have a new file added (Chap 9):
- Codegen.java - Visits the Canonical Tree and generates the assembly code

Resources

A lot (if not all) of the code for the Cannon and Assem packages is available on the book's web site. The code is very similar to our sample but not exactly the same so you should only use it as a guide.

If you have questions please ask either Dr. Brylow or a TA, or post a message to the class news group at purdue.class.cs352.

Hints

The meat of this project is writing the Codegen class file in the PowerPC package. This class will be another visitor class. It will visit the nodes in the Tree package and produce list of instructions in the form of Assem.Instr objects. A typical Codegen visit method will take as a parameter a Tree.XXX object and return void or a Tree.TEMP. The body of the method will both 'accept' sub-trees and add instruction to the ever growing list. An example my look like:

public TEMP visit(Tree.XXX){ ... instructionList.add(new Assem.OPER("add `d0,`s0,`s1..."); ... return SomeTemp; }

Testing/Debugging

The only way to find the exact output you should produce is to create a small test case and run p6 on it. Observe the output from p6 and recreate it with your code.

% /homes/cs352/bin/p3 inputfile.java | /homes/cs352/bin/p4 | /homes/cs352/bin/p5 | java Main.Main >& out1

% /homes/cs352/bin/p3 inputfile.java | /homes/cs352/bin/p4 | /homes/cs352/bin/p5 | /homes/cs352/bin/p6 >& out2

% diff -w out1 out2

Running Natively on PowerPC

The Project 6 backend register allocator is now available. To run a MiniJava program on the PowerPC architecture:

p3 inputfile.java | p4 | p5 | p6 | p6-regalloc > output.s

Download the runtime helper functions HERE.

With your output assembly file and the runtime.c file in the same directory, run gcc output.s runtime.c. The resulting executable can be natively executed on the PowerPC.
Full credit for this project can be earned if your compiler produces correct, equivalent executables -- MiniJava programs that produce the intended answer. Naturally, precisely matching the output of the P6 reference implementation should also produce an identical executable.

Turnin

Note: Late submissions will not be graded. Please see the course website for more info.

Submit a directory named Project6 with the required programs and a Makefile. Do not submit any binaries or compiled class files.
Submit using
turnin -c cs352=0X01 -p project6 Project6
on a machine in the CS undergrad "Lore" domain, where "Project6" is the name of your project 6 directory, and "0X01" is your division number.

We must be able to run your program from within your Project6 directory with the command:

/homes/cs352/bin/p3 inputfile.java | /homes/cs352/bin/p4 | /homes/cs352/bin/p5 | java Main.Main | /homes/cs352/bin/p6-regalloc

Useful Links

Credits

This has been adapted from Dr. Hosking's and Dr. Brylow's previous description.

[Rev 1.01 2004 Dec 05 05:31 DWB]