Assignment 8: Register Allocation

Due: Midnight pm, Monday December 7th by git commit.
(That is, end of Monday / beginning of Tuesday.)

Home stretch: Project 8 is to read chapter eleven of the text and write code to register-allocate the assembler you produced in project 6 using graph-coloring global (intra-procedural) register allocation.

As always, stick to the module structure given by the text. See below for specific requirements (which are different for undergraduates and graduate students).

To hand in your work, mark your submission commit with git tag "8-reg-alloc". Your repo should contain a directory named 8-reg-alloc, that contains:

• Your source code
• Your sources.cm file
• A text file describing
  • the members of your team; and
  • anything you think is of interest about your code.
• An assembler listing for a program or procedure to compute factorial.

If some phase of your compiler is so broken that you cannot generate assembly code to test your register allocator on, you can try these example assembly files with your register allocator.

The register allocator comes in multiple levels of difficulty.

1. A basic allocator that does not coalesce or spill. If the assembly code cannot be register-allocated, the allocator simply raises an error exception and fails. Callee-saves/caller-saves interprocedural register-management protocols are obtained by adding pre-colored nodes to the interference graph to represent the hardware registers.
2. An allocator that does not coalesce, but does spill. That is, if a given assembly program cannot be register-allocated, your allocator picks spill candidates, edits the assembly to add spill code, and then re-attempts to register-allocate the resulting program, iterating until the colorer manages to successfully assign hardware registers to all temps.
3. An allocator that coalesces as well as spills.
4. Above and beyond: once you have allocated registers to all the temps, you can consider writing a second allocator, that colors stack-allocated variables with actual stack slots. Compacting a stack frame in this way can give benefits in cache behavior; if your allocator coalesces, you can even eliminate memory/memory move operations.

Undergraduates get full credit for a level-1 no-spill allocator, and extra credit for levels 2–4.

Graduate students get 85% credit for a level-1 no-spill allocator; 92% credit for a level-2 spilling allocator; full credit for a level-3 coalescing allocator; and extra credit for level 4.

Words to the wise: this is, in my opinion, by far the most difficult single piece of the compiler.

"You lose it out here, you're in a world of hurt."

CS4410