Due 11:59pm Saturday December 12
Your task is to implement liveness analysis and register allocation.
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).
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:
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.
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).
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.mjwhere
file.mjis 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.
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
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.