University of Arizona, Department of Computer Science

CSc 553 : Programming Assignment 3 (Register Allocation)

Mon Oct 29, 2018

Due: 11:59 PM, Mon Nov 12, 2018

General

This assignment involves the improvement of the final code generated by your compiler via register allocation. This optimization is to be carried out if your program is invoked with the –O2 option. You are to test the effectiveness of your optimizations by testing programs compiled with and without the –O2 option, both by itself and in conjunction with previously implemented optimizations. You should report the results of these experiments in a README file.

Note: The actions taken for the –O2 option should be independent of those for the –O1 option used for the previous assignment. In other words, it should be possible to carry out register allocation with or without also performing machine-independent optimization: if both are desired, the compiler will be invoked with both –O1 and –O2 (the order of these arguments should not matter).

Intra-Procedural Register Allocation

You are to use the information obtained from your liveness analysis and/or reaching definitions to carry out register allocation within procedures.

I would like you to implement, if possible, global register allocation based on graph coloring. This requires the identification of live ranges, but for the purposes of this assignment it is acceptable to consider all of the occurrences of each variable to constitute a single live range.

If, for some reason, it is not feasible for you to implement global register allocation, you may implement local register allocation (i.e., intra-basic-block). However, this will not get full credit for this assignment.

Grading

In order to get credit, your optimizations must satisfy the following criteria:

It must be correct, i.e., it must not change the behavior of any program.
It must be effective, i.e., for programs that contain code instances to which the optimization is applicable, it should in fact optimize those code instances.

The effectiveness of register allocation will be evaluated using instruction execution counts. Penalties/partial credit will be assigned as follows:

50% Partial credit will be given if register allocation is done within basic block boundaries but not across the whole function.
I will assess a penalty of 30% if register allocation does not work correctly both (i) by itself, i.e., using only –O2; and (ii) using both –O1 and –O2.

Partial credit: You may be eligible for partial credit if your program works for some inputs but not others: see the Greding Procedure described in the class grading policies document for details of how to go about this. Note that you have to initiate the partial credit process by submitting the necessary information (described in this document).

Output

As before, your program will take its input from stdin and generate all output on stdout. Error messages, if any, will be sent to stderr.

Invoking Your Program

Your program will be called compile, and will take an optional switch –O2 that will specify whether or not register allocation is to be carried out.

Turnin

You should turn in the following:

All of the source files to your compiler, together with a Makefile that supports at least the following:

make compile

Creates an executable file called compile in the current directory that implements your compiler. Note that this should build your compiler from scratch, i.e. starting from the lex and yacc specifications.

make clean

Deletes the following files from the current directory: lex.yy.c, y.tab.*, y.output, all object files (*.o) and the executable file compile.
A README file that describes the different optimizations your compiler implements, as well as the cost/benefit of using these optimizations, based on testing at least five different nontrivial programs.

To turn in your program, execute the command "turnin cs553f18_assg3 files"