CSc 553 : Programming Assignment 4 (Code Optimization 2)
Mon Nov 19, 2018
Due: 11:59 PM, Mon Dec 3, 2018
1. General
This assignment involves the implementation of a more complex
code optimization: namely, global common subexpression elimination.
This optimization is to be carried out if your program is invoked with the
command-line option –O3.
You are to test the effectiveness of your
optimizations by testing programs compiled with and without the
–O3 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 –O3 option should be
independent of those for the –O1 and –O2 options
used for previous assignments. In other words, it should be possible to
carry out global common subexpression elimination
with or without also performing machine-independent optimization and/or
register allocation: if those optimizations are also desired, the compiler
will be invoked with additional arguments –O1
and/or –O2 (the order of these arguments should not matter).
Algorithm
For algorithms on common subexpression elimination, you can refer to
either the class notes,
or Section 11.2 of the book
"Basics of
Compiler Design" by Torben Mogensen (available online for free).
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 global common subexpression elimination
will be evaluated using instruction execution counts. Penalties/partial
credit will be assigned as follows:
-
I will assess a penalty of 30% if global common subexpression elimination
does not work correctly both (i) by itself, i.e., using
only –O3; and
(ii) together with –O1 and/or –O2
(in any combination).
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).
2. 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. (Note that the input
programs used fo testing your code will not contain syntax or
semantic errors.)
3. Invoking Your Program
Your program will be called compile, and will take an optional
command-line switch –O3 that will specify whether or not common
subexpression elimination is to be carried out.
Additionally, your compiler should accept the command-line switches
–O1 and –O2 from previous assignments, along with the corresponding
functionality from those assignments, so as to make it
possible to examine interactions between common subexpression
elimination and previously implemented optimizations (dead code elimination and
register allocation).
4. 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_assg4
files".
5. Evaluating Your Optimizations
You can evaluate the cost of your optimizations by measuring the additional
runtime overhead of the optimizations themselves together with the program analyses
needed to support the optimizations.
The benefits of optimizations can be estimated by the percentage reduction in the
number of instructions executed. This can be obtained using a version of
SPIM that provides statistics on
different kinds of instructions executed by a program. The source code for this version of SPIM
is available here and
also in
/home/cs553/fall18/spim-7.2.1-keepstats;
the executable for this version of SPIM
is in
/home/cs553/fall18/bin/spim
To get execution count statistics for an assembly file foo.s, use the command
spim -keepstats -file foo.s