CSc 553 : Programming Assignment 2 (Machine-independent Code Optimization)
Mon Oct 8, 2018
Due: 11:59 PM, Mon Oct 22 Tue Oct 23, 2018
1. General
This assignment involves the implementation of dataflow analysis and
machine-independent optimizations. These optimizations
are to be carried out if your program is invoked with the
command-line option –O1.
You are to test the effectiveness of your
optimizations by testing programs compiled with and without the
–O1 option and report the results in a README file.
1.1. Optimizations Independent of Flow Information
You should implement the following optimizations:
-
Collapsing jump chains: chains of jump instructions should be
collapsed so that each jump branches directly to its final destination.
-
Simple machine-independent peephole optimizations. E.g., transform the
sequence (where R is a relational operator)
if x R y goto L1
goto L2
label L1
to the following (where, S is the complement operator of R):
if x S y goto L2
label L1
Examine the code generated by your compiler on several programs of
reasonable size, of your choosing, to determine what patterns to use
for your peephole optimizations.
-
Intra-block copy propagation: given a copy instruction d: x := y
and a subsequent use u of x within a basic block, if
it can be guaranteed that x is not redefined between d and u, then
the reference to x at u can be replaced by a reference to y,
as illustrated by the following:
Before |
|
After |
t1 := z |
|
t1 := z |
u := t1+1 |
|
u := z+1 |
1.2. Intra-Procedural Liveness Analysis and Dead Code Elimination
You should carry out liveness analysis at the intra-procedural level.
For this, you may assume that global variables are always live. To
simplify the problem, you may also assume that all elements of an array
are live if any of its elements is (i.e., treat the array as a single
variable).
Copy propagation can cause some instructions to become dead.
You are to use the information obtained from your liveness analysis to
eliminate dead code, i.e., code whose results are never used.
Note that the elimination of some dead code can cause additional
instructions to become dead. A naive approach would be to repeat the
liveness analysis all over again, eliminate some more dead code, and so
on. Such an approach would be hopelessly inefficient, and should
not be used. Instead, during liveness analysis, you should propagate
information about what instructions are dead, and use this to improve
the liveness analysis. The idea is as follows:
-
An instruction is marked "dead" if it defines a variable
that is dead.
-
Uses of variables in an instruction that is marked "dead"
can be ignored.
At the end of the analysis all instructions that are marked "dead"
represent dead code and can be eliminated.
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.
Effectiveness will be evaluated using instruction execution counts.
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 -O1 that will specify whether or not code
optimization is to be carried out.
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_assg2
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