Deadline#

Your work should be committed and pushed to your forked gitlab repo by 11:59pm on Friday 26 May 2023.

This project is worth 10% of total course mark.

Description#

Implement register allocation to complete your compiler, which now can generate fully functional assembly files that you can assemble and run.

Getting Started#

Before starting this project, familiarize yourself with Chapters 9, 10, and 11 of the textbook and review the lecture notes on liveness analysis and register allocation.

To get started fork the Project 6 repository on gitlab.

The project structure is as it was in Preject 5.

Provided Solution#

The Project repo also includes binaries that implement all the stages of the compiler necessary prior to register allocation.

You may choose to base your Register Allocation work on the provided binaries for earlier phases of the compiler, or continue using your own solution. It is expected that you do not try to reverse engineer the class files of the provided solution to improve your score on prior projects, although you may run them to understand why your solution might be broken.

You can use your own solution by copying your files from Projects 2–5 into src/mojo and src/x64. The grading script will work with either solution as long as you put its source in the proper place.

Control flow and data flow analyses#

I have already implemented intra-procedural control flow analysis to construct a control flow graph (src/FlowGraph/AssemFlowGraph.java), and data flow analysis to compute liveness (src/RegAlloc/Liveness.java).

Register Allocation#

See also: Iterated Register Coalescing

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 (the same ones as compiled with the register allocator I provided you with in the last project).

You will receive additional 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, followed by coalescing.

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

  1. The changes are all to src/RegAlloc/Color.java.
  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.
  5. Keep track of spilled nodes with spilledNodes.
  6. Use the map degree 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. My initial version of RegAlloc.Color came out at around 100 lines of code.

Where to Add Your Code#

All the action in this project is in src/RegAlloc/Color.java. The driver for running the full compilation is in src/mj/Main.java. You can run the driver with:

% java -cp bin mojo.Main -main <prog>.mj

Running the driver outputs a dump of several phases of translation, as well as a <prog>.s assembly file. The assembly file can be assembled and linked using gcc (on an x86-64 machine such as those in the School of Computing’s Linux labs). If you don’t have an x86-64 machine of your own then you can copy the .s file to a lab machine and use gcc to assemble it into an executable with the command:

gcc -no-pie -o <prog> <prog>.s

where <prog.s> is the assembly file generated by the MoJo compiler and <prog> is the name of the executable that you can then run with the command ./<prog>. If you need more help on how to do this please ask on https://edstem.org in the COMP3710 discussion.

Running on a Mac (including Apple Silicon ARM64)#

First make sure you have the Apple command line developer tools installed by typing the command xcode-select --install into a terminal prompt.

To compile your programs for assembly on a Mac you can specify the target using the flag -target=x64osx as follows:

% java -cp bin mojo.Main -main -target=x64osx <prog>.mj

This will ensure that global symbols are prepended with _ which is what is expected by Apple’s development tools. The command to assemble your .s file on Mac is:

gcc --target=x86_64-apple-macos -o <prog> <prog>.s

This will generate an x64-apple-macos binary that you can run with the command ./<prog>.

You might ask: how does this x86-64 binary run on Apple Silicon ARM64? The answer is that Apple provides an x86-64 dynamic binary translator called Rosetta.

Expected Output#

The class mojo.Main contains a main method that loads files, invokes the parser, runs the semantic analysis phase, invokes translation, and then runs instruction selection, followed by register allocation. Like Project 5, the grading script will compare the output from your compiler with the expected output from mine. This will be useful to you in understanding the project and what you need to implement. However, your solution will be graded on correctness, not code quality. As long as your compiled programs compute the expected result then you are good.

Turn In and Grading#

  • Like previous projects, you should fork the project repo to get started.
  • Like before, you don’t need to turn anything in.
  • We will pull from your repo’s master branch at the deadline.
  • We will rebuild your submission from source with your Makefile.
  • We will run the grading script on your code with additional test inputs that are not included in the repo.
  • We will provide the additional test inputs along with your score after the deadline.
bars search times arrow-up