CSC 255/455 Project: Optimizing Compiler*
Last Change: Sep. 24
Update:
Nov. 06: See Optimizor Competition.
Oct. 07: See "Optimization
Phases".
Oct. 02: See "Optimization Phases".
Sept. 24: See "Code Generation Phase".
Introduction
In this project,
you need to design and implement the optimizor in
Java. The system makes a source-to-source conversion of C programs in
three steps:
- Use a C front-end to convert a C program into
an abstract syntax tree (AST). The conversion uses a C parser, lcc, and
the front-end of the provided front-end.
- Implement the optimizor by analyzing and
transforming the AST of the program.
- Use the provided back-end to translate the
transformed AST back into C code.
Your task is to
design and implement the second step of the
compilation.
The project is
divided into five phases. The schedule is:
(the
default due time is mid-night)
trivial due on
Sept. 16; code generation due on Sept. 27;
value numbering due on Oct. 7; AVAIL,
DEAD, and CONST optimization due on Oct. 28;
space reduction due on
Nov. 11.
You need to program in Java to use the provided compiler. If
you want to use other languages and your own front-end or back-end,
talk with the instructor.
Detailed Description
1) Trivial
Phase (due on Sept. 16)
In this phase,
you need to instrument the IR (i.e. AST) and insert
the
following function calls into the program:
- Insert "Init();"
at the beginning of the program;
- Insert "RecordInst();" for each statement in
the program. For
example,
the following code fragmentation
...
a = a + b[1];
foo(a);
...
should be transformed in
the shape like
...
RecordInst();
a = a + b[1];
RecordInst();
foo(a);
...
- Insert "Report();" at each exit of the
program.
You also need
to implement function Init(), RecordInst()
and Report() and make them part
of the program. They maintain a
global
counter that records the number of instructions in the program. Init()
sets the counter to zero. Each time RecordInst() is called, the
counter is incremented by 1. Finally, Report() prints the total number
of instructions to screen. An example of instrumented programs (without
the implementation of the functions) can be downloaded here.
Except for recording and reporting instructions, the instrumented
program should behave exactly the same as the original program. You
need to learn how to use the provided front-end and back-end tools, how
to traverse and manipulate the AST tree before working on the
instrumentation. This will
also prepare you for the optimization in the later phases. What you
need
to submit for this phase include:
- An instrumentor that can work with the
front-end and back-end tool to generate the instrumented version for
given C programs;
- A Readme specifying how to use your program,
include Makefile if necessary;
- For the given test
programs, report the number of instructions
you measured in the Readme.
2) Code
Generation Phase (due
on Sept. 27)
Given a C
program, you need to do some transformations on its AST and
generate
a C program whose expressions satisfy the following requirements:
They occur in the right-hand-side of an
assignment, conditions of
an if-goto statement, index of an array access, and actual parameters
of
a function call. In the first two cases, one expression
contains at most
two scalar operands (scalar
variables or constants) or one array access. In the last two
cases, it must
be
a scalar variable or constant. The left-hand-side of an assignment
must be a scalar variable or array access. For example:
a = b + c[e] + d;
if (a+d<b) goto L1;
foo (m[a+d]);
m[e+f] = m[a] + m[d];
L1:
needs to be
converted to something like the following:
t0 = c[e];
t1 = b + t0;
a = t1 + d;
t2 = a + d;
if (t2 <b) goto L1;
t3 = a + d;
t4 = m[t3];
foo(t4);
t5 = m[a];
t6 = m[d];
t7 = e + f;
m[t7] = t5 + t6;
L1:
What you need
to submit for this phase include:
- An generator that can work with the front-end
and
back-end tool to generate the converted version for given C programs;
- A Readme specifying how to use your program,
include
Makefile if necessary;
3)
Optimization Phases
You need to
design and implement the optimization part of the
compilation. For 255 students, the minimum requirement is to implement
- Local value numbering in basic blocks
- Global redundancy
removal
- Dead code elimination
- Constant Propagation
For 455
students, in addition to the above four, you also need to
implement
some other optimizations, which will be posted later.
You can choose
any other optimization techniques such as loop
transformation to implement as well. The generated programs should
still satisfy the requirements of the first two projects, i.e. the
instrumentation of the three functions and code generation
requirements. (NOTE, we don't have any requirements on registers
any more!)
Requirements
of CS455:
(1) Value numbering phase: to
implement the Local value numbering optimization of the compilation. (due
on Oct. 7)
(2) Implement
the AVAIL, DEAD, and CONST optimization of the compilation. (due
on Oct. 28)
(3) Optimize for space: to reduce the static count of local
variables in a program. "Static count" means the number of
variables defined in each function at the compile time,
not
the number of run-time instances in an execution. You can use
local or global register allocation techniques. Basic requirement
is the local allocation in single basic blocks.
Global allocation can get up to 10 points extra credit. You cannot add
in global variables (scalars or arrays). Local variables cannot
be arrays either. What they need to do is
to reduce the uses of local scalar variables by
reusing them when there is no conflict (the problem of register
allocation). (due
on Nov. 11)
Requirements of CS255:
(1) Value numbering phase: to
implement the Local value numbering optimization of the compilation. (due
on Oct. 7)
(2) Implement
the AVAIL, DEAD, and CONST optimization of the compilation. (due
on Oct. 28)
What you need
to submit for the each phase includes:
- An optimizer that can work with the front-end
and back-end tool to generated the optimized version for given C
programs;
- A README specifying how to use your program,
include Makefile if necessary;
- For the given test
programs, report
the
number of calculations you measured for both the original program and
the optimized program in the README.
For all the
optimization projects,
you MUST include a text-only file called README, in which you will
cover AT LEAST the following:
- Your name and the
project number
- A list of all
files in the directory and a short description of each.
- HOW TO COMPILE
your program.
- HOW TO USE
(execute) your program.
- A short
description of the structure of your program.
- A short
description of the design of the
optimizer you build;
- In case you
have not completed the project, you should mention in significant
detail:
- what you have and have not done,
- why you did not manage to complete your project (e.g.,
greatest difficulties)
This will allow us to give you partial credit for the things you have
completed.
- Document any
bugs of your program that you know of. Run-time errors will cost you
fewer points if you document them and you show that you know their
cause. Also describe what you would have done to correct them, if you
had more time to work on your project.
- A clear
description of any extensions or special features of your project. This
will be used for assigning extra credit.
Note: It is possible that
we will schedule a presentation
session. The details will be posted on Web when the schedule is ready.
Please keep checking this web page for the latest changes!
Optimizor Competition:
Objective:
to do whatever correct to minimize the number of dynamic instructions
for the test programs.
Deadline:
Nov. 18, 2003.
Current Status:
see here for the best results till Nov.
6,
2003.
Front-end and Back-end
Tools
The complete
process of compilation is as the following:
To use the front-end tool, the command is "lcc
prog_name.c". The C front-end will keep source-level data
definitions but will convert high-level control flow into "goto"s and
"if-goto"s. It generates two files: prog_name.adap and prog_name.adap.h.
The files include a textual representation of the abstract syntax
tree.
The structure of the tree directly corresponds to the abstract syntax
tree
(AST) used in the Java compiler. Currently "lcc" is only
available for solaris machines. Graduate students can use
"/u/compiler/lcc/solaris/lcc" on solaris machines such as heart. If
undergraduate students' systems, "lcc" is not
availabe. You can ask TA for pre-converted code of test programs.
Once the .adap
files are available, you can construct an AST tree
from by using the provided AST classes. For example,
ProgAst("prog_name.adap") will construct an AST tree for the program
described in prog_name.adap.
All the optimization and instrumentation are done on AST directly. The
final step is to call "ProgAst.GenCode()" to generate the new C program
for the modified AST tree. The default output file name will be prog_name.out.c.
Notice your optimizer need to convert a .adap file into AST and AST
back to a C program. You will need to use gcc to compile the
generated C file to check the correctness of your transformation.
An example
(ConstFolding.java)
shows the use of the parser and code generator as well
as the traversal and modification of an AST program tree can be
downloaded here.
A test input is also included: initial program is const1.c; first
converted to const1.adap and const1.adap.h by lcc; then applied
constant folding
by ConstFolding procedure; finally the output is in const1.out.c.
See AST
Overview and AST
Javadoc for the detailed interfaces. The src files are available at
"/u/xshen/src/" for undergraduate students
and
"/u/xshen/255/public/src/" for graduate
students. It contains three sub-directories: ast, drivers and tools.
Make sure that this directory is in your CLASSPATH
environment variable before you compile and run the example Java
program and your own program.
A note on javac:
the code was written
using Java 1.3. Since Java 1.3 did not have built-in Assertion
and AssertionError, these classes were defined as part of the
program. Java 1.4 has defined an assertion utility, but it
conflicts with our own definition. So we cannot use Java 1.4 or
higher to compile AST classes. However, Java 1.3 is available on
CS machines and can compile these classes fine. Both graduate
students and undergraduate students can use the following command to
invoke JDK1.3:
/usr/staff/lib/java/jdk1.3/bin/javac
Once you have the
byte code, you can link it with Java classes
compiled with Java 1.4 and debug it with any Java debugger, including
the one come with Java 1.4.
Language
& Test Programs
You only need to
work on a subset of C language. The test programs
that will be used to evaluate have the following properties:
- There are no pointers in the program.
- There are no structure types in the program.
- The only data types are integer scalars and
one-dimensional integer arrays.
A
set of test programs can be downloaded from here.
Turnin Instructions
Copy all the files you want to submit into a single directory. Double
check the submission checklist before submitting. Both graduate and
undergraduate students should use the following command to turnin your
files:
/u/xshen/bin/TURNIN <dir>
where <dir>
is the directory in which your files reside. Use
"." for current directory. You can submit any number of times before
the due time, but only the latest version will be kept and
graded. Upon each successful submission, a confirming email will
be sent to your mailbox, listing all files
submitted. Note: You CANNOT run the turnin command in a
Solaris machine.
If that is a problem, please report to TA.
Late Policy:
Late submissions receive 5% reduction per half day (12 hours sharply).
Partial work will count, as long as you explain clearly in the
documentation what you have finished. You can also include your
own test programs which show the working part of your compiler.
* This page is based
on the project
description from Yutao Zhong.