Assignment 3: Optimizations
(15% of the Final Grade)

Objective

In this final assignment, you will write several different optimizations that will (ideally) improve the quality of the code generated by the compiler. The evaluation of your assignment will be based primarily upon the correctness (9%) and execution time (6%) of the programs it compiles. You must implement three optimizations: (1) loop invariant code motion, (2) constant propagation, and (3) common sub-expression elimination. In addition, you may also implement any other optimizations you choose, such as copy propagation, strength reduction, and loop induction variable elimination. The performance of the code generated by your compiler will be compared with that generated by the other submitted compilers. There are many different forms of constant propagation. You can use the lecture slides for Single Static Assignment Form and Constant Propagation as a guideline when creating an algorithm. Alternatively you can use a combination of copy propagation and constant folding.

Procedure

You are free to build from the code produced from the first and second assignments. There are no restrictions on how you write your optimizations for this assignment. You can choose how detailed your optimizations are (for instance, you can limit your optimizations to only alter certain types of instructions or data types) and how aggressive your optimizations are. Note that there are a large number of engineering decisions to be made in this assignment and you are free to decide them as you wish. We recommend you use the structure of the test programs to guide your decisions.

Passes must be disabled by setting environment variables

So that we can test correctness of each pass independently, each pass should be disabled by an environment variable. Setting the environment variable NO_CP should turn off constant propagation, NO_CSE should turn off common subexpression elimination, NO_LOOP should turn off loop invariant code motion and NO_OPTIONAL should turn off all the optional optimizations you have added. You can use the getenv C function to check if these variables have been set (and export or setenv to set them depending on the shell you use). When your code is ranked, none of these variables will be set, i.e. all of your passes will run.

Performance Ranking Details

The performance of your code will be compared against other submitted code by collecting the dynamic count and types of instructions executed when running the code generated by your compiler. Your ranking among submissions will determine the performance part of the grade (6 of the 15 marks).

Incorrect submissions cannot be ranked -- so make sure your compiler is correct before worrying about performance. If any of the (pre-released) benchmarks generate incorrect results, you will receive a zero for your performance mark. The details of the ranking system is here. Submit early and often to see where you rank.

Marking

Each of the three optimizations is assigned three marks for correctness. One of these three is for the report (i.e. the report is worth 3 marks).

Three marks are for absolute performance. You will receive 1 mark if you achieve a speedup of at least 1.1 (relative to the base case), 2 marks for a speedup of at least 1.2, and 3 marks for a speedup of at least 1.5.

The last three marks are assigned for performance relative to others. If there are n people who hand in the assignment then the person with the highest speedup will receive 3n/n marks, the person with the second highest will receive 3(n-1)/n, et cetera.

The late penalty is one mark per day that the assignment is late (the assignment is out of 15). Please email all late assignments to bradel@eecg.utoronto.ca or fort@eecg.utoronto.ca.

Deliverables

Your executable should be called "hw3" (without the quotes). Submit a brief report describing your implementation with your code. In addition to the report, submit the source of your implementation using the following commands:

% tar cvf - Makefile *.c *.cc *.h passkey report.ps | gzip -c > hw3.tar.gz
% submitece540s 3 hw3.tar.gz

Your hw3.tar.gz should include all of your source files, your report, a Makefile and the passkey. The passkey file is a plain text file with a one word password used to access the marking website. No spaces or special characters are allowed in the password. Do NOT use any password that you care about because the password will be sent on the interent as plain text. The source and report are due Thursday April 13, 2006 at 11:59:59 pm.