CS412/413
Introduction to Compilers and Translators
Spring 2000
Cornell University Computer Science Department

Programming Assignment 6: Register Allocation

Design report due Friday, May 5
Code and demo due Thursday, May 11 or Friday, May 12


In this programming assignment, you will complete your Iota+ compilers by implementing graph-coloring register allocation and constant folding.

Output and option requirements

The name of the compiler class and its syntax for invocation remain the same as in Programming Assignments 3 and 4. However, the compiler must support three additional options: -dump_live, -dump_reg_alloc, and -noopt. The -dump_live option causes the abstract assembly code to be dumped by the compiler, but with a list of variables live on input to and output from each assembly code statement printed with each statement. Abstract assembly statements are dumped in exactly the format shown in the following example:

    add t1, t2    ; live-in: t1, t2, t3   live-out: t1, t3

The -dump_reg_alloc option causes the compiler to print out for each method and function the register allocations that were performed. For a method f of class C in module M, the print-out will state which temporary variable was allocated to each of the allocatable registers in the register set:

M.C.f:
    ax: t1, t2, t4
    bx: t3, t8
    cx: t5, t6
    ...
    di: <nothing>

For a global function f in module M, the print-out of register allocations is introduced by the line M.f: instead.

By default, the compiler will perform the optimizations of graph-coloring register allocation and constant folding. To turn off these optimizations, the -noopt option must be supported. This option causes code to be generated in the same way as in the earlier programming assignments.

Constant Folding

The constant folding optimization replaces expressions that have constant arguments with either their result or a simplified expression. You are expected to implement at least the following kinds of simplifications:

  1. Replace IR nodes of the form BINOP(op, a, b) with the result of evaluating a op b when both a and b are constants. This replacement is performed recursively, so that large expressions containing only constants are evaluated at compile time.
  2. Expressions of the form 1*E and E*1, where E is an arbitrary expression, are replaced by E. Similarly, expressions of the form 0+E and E+0 are replaced by E.
  3. if and while statements are simplified when the test expression is determined to be a constant. For example, the statement if (4 == 5) a++; else a--; should be replaced by the statement a-- because it can have no effect: the test expression always is false.

These optimizations should be performed on IR trees, where it will be easy to express the rewriting necessary. Some optimizations can be performed at the AST level as well; for example, the simplification of if and while statements is more easily recognized in AST form. However, some opportunities for constant folding will become apparent only when the code is expanded into IR. When the test condition of a conditional jump in the IR code is always true or false, it can be replaced with an unconditional jump. In general, some code may then become unreachable and can be removed from the program. For this assignment it is acceptable to implement constant folding for only IR trees.

We recommend implementing these optimizations using a functional style: rather than modifying the IR (or possibly AST) tree in-place, construct a new tree. A nice trick that improves performance is to share unmodified nodes with the old tree. For example, when implementing constant folding on a binary operation node, recursively fold constants on both operand sub-trees. If the recursive calls return exactly the same sub-trees, and no constant folding is possible at the current node, then the node itself can be returned as a result. If one or both of the recursive calls do some constant folding, or some constant folding is possible on the sub-trees, then a new node must be constructed as the result of constant folding. This approach avoids allocation of new objects when it is unnecessary.

Register Allocation

Your compiler will implement the graph-coloring register allocation algorithm described in Appel, except that register coalescing and removal of redundant mov instructions are optional and can be done for extra credit. Rather than being allocated immediately to stack locations, local variables will be allocated to temporaries that will be spilled to stack locations only if necessary. It will be necessary to deal properly with callee-save and caller-save registers. If any callee-save registers are used during a function, they must be saved on the stack and restored at the end of th function. Similarly, the content of caller-save registers must be assumed to be destroyed by all function calls. The register allocation algorithm will cause this spilling automatically if the def and use for call instructions are set up properly.

It will be necessary to perform live variable analysis over the control flow graph of each method and function in the program. To aid you in constructing live variable analysis, we are providing a Dataflow package that implements the work-list algorithm described in class. You will need to fill in the implementations of the Dataflow.Node and Dataflow.Value classes to obtain a live variable analyzer, by defining the appropriate flow functions and meet operations for live variable analysis.

Demo

You will be demonstrating your compiler in person on May 11 or 12. Signups for demo time slots will be arranged later.  The demo will be a half hour long, consisting of two roughly 15-minute segments. In the first segment, you will give a short presentation about your compiler and impress the course staff with its design and functionality. We will be interested to hear about interesting challenges you addressed and lessons you learned. In the second segment, the course staff will run your program through several benchmarks. We will be looking at the quality of your compiler and the quality of your generated code.  For each benchmark, we will measure (at least), the time it takes to run the compiled benchmark, the size of your generated code, and the time it takes your compiler to compile the benchmark. The groups producing the best two compilers, based on these results and measures of quality, will receive a small prize and future bragging rights.

What to turn in

Turn in on paper:

We are requiring less complete documentation of your project for this programming assignment because you will be demoing your system in person. However, we are still interested in receiving a complete design document that shows you have thought through all of the implementation issues. You should turn in the following information in hardcopy in class on May 5:

Turn in electronically (at demo time):

Electronic submission instructions

Your electronic submission is expected at the same time as your demo To submit Programming Assignment 6, please drop your files in \\goose\courses\cs412-sp00\grpX\pa6, where grpX is your group identifier.  Please organize your top-level directory structure as follows :

Note: Failure to submit your assignment in the proper format may result in deductions from your grade.