CS352

View the Project on GitHub TiarkRompf/cs352

Project 6: Liveness Analysis & Register Allocation

Due 11:59pm Saturday December 12

Useful Links

Description

Your task is to implement liveness analysis and register allocation.

Liveness Analysis

You have available to you the working implementation of intra-procedural control flow analysis, which turns a list of instructions into a control flow graph, by implementing the class FlowGraph.AssemFlowGraph. You should first implement the class RegAlloc.Liveness which takes a FlowGraph and performs data-flow analysis to obtain liveness information. Use either the set-equation algorithm as described in class with a java.util.LinkedHashSet or sorted-list-of-temporaries representation of sets, or the one-variable at a time method. You may want to refine your implementation to use a worklist approach: The basic idea is that you maintain a list of CFG nodes that need to be processed because the live-in set of one of the node's successors was changed in a given iteration; the set can be initialized with all the nodes of the CFG (since we assume they all need to be processed from initial values to start out with). You will receive extra credit for any improvement on the basic iterative liveness algorithm, but you must document your work in a README file (see below).

Register Allocation

You are to implement the register allocation phase of the compiler. This will complete code generation and allow you to run programs. You should implement at least coloring without spilling or coalescing, such that you can compile and run simple programs. You will receive extra credit for implementation of spilling and/or coalescing. I strongly suggest that you implement allocation without spilling or coalescing to begin with, then implement spilling (optional for extra credit), followed by coalescing (optional for extra credit).

Here are some notes about the initial (non-spilling, non coalescing) implementation of coloring:

  1. The changes are all to RegAlloc.Color.
  2. Assume the incoming interference graph does not contain outgoing interference edges for precolored nodes.
  3. Use frame.registers() as the set of colors to be used to color the graph and to record the precolored nodes.
  4. Use 2 worklists in the initial implementation: simplifyWorkList & spillWorkList, implementing each as a java.util.LinkedList<Node>.
  5. Keep track of spilled nodes with another java.util.LinkedList.
  6. Use a java.util.LinkedHashMap to map nodes to their degree.
  7. The rest of the algorithm is a simplified version of the pseudo-code from the paper, with the code for spilling and coalescing omitted.
  8. Professor Hosking's initial version of RegAlloc.Color came out at around 100 lines of code.

Extra Credit Rules

The project is, as usual, out of 100 points. These 100 points will be awarded for full implementation of the graph coloring and register allocation portions. You can earn 5 extra points for correct implementation of spilling, and another 5 points for correct implementation of coalescing.

Executing Compiled Programs

As with project 5, when compiling for execution make sure to use the option -main so as to generate the linkage code (equivalent to a C-style main function). Compile the assembly code using gcc (to make sure you link to the C library).

Getting Started

Source code is available in a tarball in the /homes/cs352 directory, which can be copied into your working directory and expanded by doing the following:

cp /homes/cs352/Fall15/project6.tar.gz ./
tar -xvf 

If you wish to integrate the project into an Eclipse project, follow the directions on this blogpost to create an Eclipse project using the included Makefile.

To make the project, type "make" as per usual. To run your project, go into the bin directory. 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 file p6.sh will run itself as a command that invokes mojo.Main from java if you wish. All arguments will be copied.

Readme

Make sure to include a file called README in your project submission, explaining the approach you took to implement the project and what, if any, extra credit items you implemented. Ensure that the TA has enough information to grade your submission and knows what files to look in.

Turnin

For this project, please turn in your src directory, which should include all source files that you have added or modified, along with your README file. Do not turn in *.class files.

From the project6 directory submit your solution using the command:

turnin -c cs352 -p project6 ./src

To verify your turned-in work, do:

turnin -c cs352 -p project6 -v

Grading

We will create a set of test cases, and then compare the output of your solution to our reference implementation as we have with the previous projects. A less automated approach will be used to grade your coalescing and spill code, should you chose to do it.