Assignment 8: Register Allocation
Due: 10:00 pm, Monday, December 6.
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).
You should submit the following files:
- 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.
- 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.
- 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.
- An allocator that coalesces as well as spills.
- 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."
Start early.
–Olin
CS4410