Project 5: Instruction Selection

Due 11:59pm Friday, November 30

Useful Links

Description

You have already implemented a substantial sequence of the major steps in compiling a high-level language into low-level code. At the beginning of this project, we already have intermediate tree code for the input program, which you will now convert into x86-64 assembly-code instructions. You will implement code generation for the x86-64, and run your compiled programs on the lab machines.

Resources

Before starting this project, familiarize yourself with Chapters 8 and 9 of the textbook. In addition to the lectures, this will give you a solid foundation for starting your code generator.

Getting Started

Source code to get started with is available via svn on any of the lab machines using the command:

 svn co file:///homes/cs352/svn/p5

or remotely using the command:

 svn co svn+ssh://sslab01.cs.purdue.edu/homes/cs352/svn/p5

You can replace the machine name sslab01 in the above command with any of the machine names in the lab (e.g., sslab02).

You will now have a working copy of the project files in the directory p5. The p5 directory contains src and lib subdirectories. The src subdirectory contains source files for this project. The lib subdirectory contains contains any precompiled class files you will need to compile this project. (The files are actually configured as an Eclipse project, so you can also import the p5 directory as a new project in Eclipse, or directly import the project via svn, at your convenience.)

As in previous projects, you must run the setup script to configure your environment.

All commands below will assume that you have first set your current directory to the p5/src subdirectory using the command:

 cd p5/src

to enter the src subdirectory.

All changes for this project will be done to the x64 code generator file x64/Codegen.java in the p5/src subdirectory. You can compile the project using the commands:

 javac */*.java

in the p5/src subdirectory.

You can run the full compiler with the command:

 java mojo.Main file.mj

where file.mj is a mojo source code file.

You can also run the compiler with the command:

 java mojo.Main -main file.mj

The flag -main indicates that the compiled file is to be treated as the "main" module, and will generate a standard "main" function as entry point for running the program.

For input file foo.mj the compiler will also produce output for the various intermediate forms of the translated program:

tree intermediate code before canonicalization
after canonicalization
after locating basic blocks
after scheduling those blocks
after injection of procedure prologue and epilogue
the instructions (you) generate for those trees
further output regarding register allocation (the interference graph, register allocation, and final assembly code)

The compiler will also produce a final assembly code file foo.s which you can run by first compiling:

 gcc -o foo foo.s

and then running:

 ./foo

You may find gdb useful in debugging the code produced by your compiler as it executes.

The command

 gdb foo

will open the executable in the debugger.

The command

 b main

will set a breakpoint at the main function.

The command

run

will start the program running, stopping at the next breakpoint.

The command

si

steps to the next instruction.

The command

 display/i $pc

tells gdb to display the assembly code instruction at each program point.

You can find information on these commands and others (such as to examine the contents of registers and memory) using the help command.

Turnin

You should only need to turn in your x64/Codegen.java file, since that is the only file you need to change. From the src directory submit your solution using the command:

  turnin -ccs352 x64/Codegen.java

Grading

We will create a set of test cases, and then compare the output of your solution to our reference implementation. Grading test cases are intended to test separable functionality of your type checker.

There will be a reconciliation period after initial grading when you will be able to compare outputs of your parser with those of the reference implementation, and you may then offer simple fixes for the TAs to apply to your implementation to improve your grade. These fixes will be accepted only at the discretion of the TAs and the instructor — we will judge what "simple" means!

The reconciliation period is only intended for you to be able to fix simple problems that you may have mistakenly overlooked. Thus, you must make sure to test your implementation thoroughly.