Register Allocation Milestone, csc431, Fall 2019

1 Goal

Extend Milestone 1 to include register allocation.

2 Plan

Here’s how I’d go about it:

Design your representation for an interference graph; figure out which packages you’re going to use for graph coloring.

Next, I think I would write some test cases that actually exercise your graph coloring library; this will be useful to make sure that your chosen graph representation actually includes everything you need. Think about the "colors" that you’re going to use; they need to include both registers and stack locations. I advise not using the rax register in your coloring pass.

Following this, I would write the pass that walks backward through your pre-allocated code and generates the interference graph.

Finally, you can write code to take your colored graph and rewrite your assembly to use registers rather than stack locations.

Now you’re done!

3 Test cases

TBA...

4 Testing Plan

For the purposes of evaluation, we’re breaking down the functionality into six separate "tiers". Each one is worth a fraction of the overall points for correctness, as follows:

1. (10 pts) Milestone 1 code

2. (5 pts) Generating interference graphs

3. (5 pts) Completed register assocation