 |
CSC 255/455 Project
Engineering an Optimizing Compiler |
|
Schedule |
|
Phase |
Due Date |
Weight |
| Phase 1: Trivial
|
11:59 p.m., Sep. 19, 2006
|
10 |
| Phase 2: Code Generation
|
11:59 p.m., Sep.
26, 2006 |
10 |
| Phase 3: Control
Flow |
11:59 p.m., Oct. 3,
2006 |
15 |
| Phase 4: Value
Numbering |
11:59 p.m., Oct.
10, 2006 |
25 |
| Phase 5:
Data Flow |
11:59 p.m., Oct.
29, 2006 |
40 |
| Final Competition |
11:59 p.m., Nov. 21, 2006 |
25 |
|
|
Downloads & References |
|
|
Introduction |
|
Typically a compiler
is made up of a front end that converts source programs to a intermediate
representation, a middle end that carries out phases of optimizations
and a back end that generates target object codes. Here in your 255/455
class project, you are expected to implement the middle part of a toy
compiler that accepts a subset of C. Though much simpler than a product
compiler, making it perfect is not trivial. You need to organize the
compiler structure, implement all the required optimization phases and tune
the performance by yourselves. Of course your compiler should guarantee correctness,
otherwise you won't get full credits. At the competition stage, you are encouraged
to employ any optimization method that you know or you invent to boost the
output programs' performance. It'll be great fun to enjoy your work then.
The evaluation of your compiler is very simple. Instead of running time,
we count the number
of instructions executed by the output programs so that you don't bother
with those advanced issues such as cache effect.
Five phases are required:
- Trivial: to count the number of dynamic instructions in the program.
- Code Generation: to convert the program into an assembly-like format.
- Control Flow Graph: to build control flow graphs of the program.
- Value Numbering: to implement value numbering.
- Data Flow Analysis: to implement a few optimizations involving data flow analysis.
- Final competition: There would be a competition among all the CS255/455 students
to build the best compiler which minimizes dynamic instruction count (number of
instructions executed by the program) of the programs. Your compiler may be tested on some secret programs also.
With the development process going on,
difficulty level would probably increase too. Regarding this, you'd
better well-design your framework at the early stage to avoid rebuild the whole system to fit further optimizations.
The accepted language is a
subset of C. The test programs that will be used to evaluate the
following properties:
- There are no pointers
in the program.
- There are no
structure types in the program.
- The only data types
are integer and floating point scalars and one-dimensional
integer arrays.
A set of test programs can
be downloaded from
here.
The compiler is written in
Java. If you are not familiar with Java, please resort to the
resource page.
|
 |
|
|
Setup |
|
Step I: test_prog.c --> {test_prog.adap,
test_prog.adap.h} We use lcc as our
compiler's front end that converts the test programs into an
intermediate form, ADAP. ADAP is actually an abstract syntax tree
(AST) whose readable form is dumped into an output file with extension
.adap. You can reach lcc at /u/compiler/lcc/solaris/lcc.
But you have to logon to a solaris machine, such as heart, to
execute it. For your convenience, we have already converted the test
programs and from
here
you may download them.
Step II: {test_prog.adap,
test_prog.adap.h} --> AST
Now it comes to Java. The
AST_lib offers
classes to transform the .adap files into internal AST representations.
You'll create an instance of ProgAst using your test program's
adap file name as the constructor's input parameter. Then you'll be
working on the AST all the way until code generation.
Step III: AST -->
test_prog.out.c
The third step is code generation which is
simply done by calling the AST's method GenCode(). An output C
file will be dumped with extension .out.c. Now compile the
output .out.c file into an executable object file then run it on your
PC, you'll see and check the outputs.
Of course you have to make every step working to
see the final correct results.
An example ConstFolding.java shows the use of
the parser and code generator as well as traversal and modification of
an AST program tree. You can download it from
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.
Thanks for Virendra, we
have a template for the project. We'll reuse the Makefile and
the directory organization. Just add your own files if possible and
make small changes to the Makefile. Type
make, you'll
complete build, compile and run in a batch way. Check it out
here and use it as a start point of your whole project.
|
 |
|
|
In
Detail |
Phase I: Trivial
In the first phase, you
need to instrument the IR and insert the following function calls
into the program:
- Insert Init();
at the beginning of the program;
- Insert RecordInst();
for each statement (except return statements) in the program.
For example, the following code fragment
...
a = a + 1;
foo(a);
...
should be transformed to
...
RecordInst();
a = a + 1;
RecordInst();
foo(a);
...
- Insert Report();
at each exit of the program.
You also need to implement
functions Init(), RecordInst(), and Report() and make
them part of the program. They maintain a global counter that
records the number of dynamic instructions (statements in case of
PHASE I) in the program. Init() sets the counter to zero.
Each time RecordInst() is called, the counter is incremented
by one. Finally, Report() prints the total number of
instructions (statements) executed to the standard output. An
example of instrumented programs (without the implementation of the
functions) can be downloaded from
here. Except for recording and reporting number of instructions
executed, the instrumented program should behave exactly the same as
the original program. Make sure that there is no possibility of name
conflicts among variables. However, I would not mind if you do not
ensure their uniqueness in the C code, since the names were given by
me. However, other than these three functions you need to make sure
that none of the entities that you add to the code conflicts with
any other variable or function name in the code.
Here are my test programs after code generation (PHASE II) and
instrumentation. At this stage, you may ignore the extra statements
and variables generated in them. You need to learn how to use
the provided front-end and back-end tools, how to traverse and
manipulate the AST tree before start working on the instrumentation.
This will also prepare you for the later phases.
Hint: You may want to
add function definitions not by modifying AST, but by adding them
directly to the output file. Do not forget #include lines.
Phase II: Code
Generation
In
this phase, you need to transform the program into an
assembly-like format. In doing so, you are still working on the
AST. What is changed is only its internal structure. After the
transformation, you may call method GenCode() to generate
the output C file.
Expressions
in the transformed program should satisfy the following
requirements:
- Left hand side of
an assignment statement should be a variable or an array
access.
- Right hand side
of an assignment statement should be either a variable, a
constant, an array access, a function call or an expression
with no more than two operands (or one operator).
- Any
operand of an expression can only be a variable or a
constant.
-
The predicate of a conditional
jump can be one comparison operation whose two operands are
either a variable or a constant.
- Parameters to a
function call can only be a variable or a constant.
- Index of an array
can only be a variable or a constant.
- Return parameter
can only be a variable or a constant.
After the program transformation, new temporary variables could be
introduced.
. An example program segment
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:
Some notices:
You should take
scanf and printf as special instructions that need
not conform to above specifications. You should not make any
temporary variable to take value of the pointer passed to
scanf. Remember that our language does not have pointers, so
we do not deal with them. For printf, you still need to
make all the arguments in variable or constant form except for
the format string.
Here are my test programs after code generation and
instrumentation. Your output should match with them. Remember
that you have to take care of types. Our language has integers
and floating points only. I will not penalize CS255
students if they do not take care of types. They will get
additional bonus points if they correctly handle types.
Phase III: Control
Flow
In this phase, you
need to construct a control flow graph (CFG) for each function
definition. You should identify all the basic blocks (BB) in
a function and figure out predecessors and successors
of each BB. You may assign each BB a unique ID with naming
scope either within a function or throughout the whole program.
As a debugging support, your compiler
should provide a means of dumping the CFG's into an output stream. In this
assignment, you are required to dump the CFG's of each program into
a text file with extension .cfg (for instance, automaton.cfg for
automaton.new.c)
in the output program directory.
A sample control flow graph is shown as following
int a, b;
//Block 1:
//
Predecessors: Entry
//
Successors: Block 2, Block 3
a = 1;
b = 2;
if ((a > b)) goto L6;
//Block 2:
//
Predecessors: Block 1
//
Successors: Block 3, Block 4
a = a - b;
b = b - a;
if ((a <= b)) goto L4;
//Block 3:
//
Predecessors: Block 1, Block 2
//
Successors: Exit
L6:
return 0;
//Block 4:
//
Predecessors: Block 2
//
Successors: Block 6
L4:
goto L3;
//Block 5:
//
Predecessors:
//
Successors: Exit
L7:
return 1;
//Block 6:
//
Predecessors: Block 4
//
Successors: Exit
L3:
Note: your dumped CFG's should not omit labels if they mark
the beginning of a basic block. Function calls are not necessarily
conditions of starting a new BB.
Phase IV: Value
Numbering
Value numbering is a classic technique that eliminates redundancies in
the linear IR. In this phase, you need to implement value numbering in your
compiler. Essentially, you should take care of your hash table. As you know,
value numbering can be carried out on different level of scopes: BB, EBB, or
even bigger regions. In this assignment, you are only required to implement
the algorithm within a basic block. However, value numbering on larger scope
may help you in your final competition. So it's up to you to decide what
scope to be worked on.
Note: From this phase on, actually already from phase two, by default,
instrumentation should always be the last pass. Do not optimize on
your instrumented programs.
Phase V: Data
Flow
The optimizations in this phase involve data flow analysis. You need to
implement
1. Constant propagation
2. Avail (455 only, Bonus for 255)
3. Dead code elimination
Final Competition
This is the most fun part of the project. Also the hardest part if you
want to beat others and get a big bonus on your final grade.
From now on until the deadline, you can try your best to improve your compiler
using whatever you learned in class, on textbooks or even by your own inventions.
For instance, many people use loop unroling to eliminate branch statements
has already become a public secret.
Also if you are not satisfied with the poor organization of your earlier phases,
you may even start all over. Last year we had a undergrad student who implemented
SSA in his compiler. So if you want to win out, start early and try methods you
deem to have positive impact on your final results. While we say you can do
whatever you want in your compiler, we do mean the following prohibits:
- no tampering
with the instruction counter
- no transforming
your code such that it does not comply with the rules of PHASE 2
- no hard
coding program output
- no
copying of other one's code
We will start putting up results, on the
2006 255/455 competition ranking page,
for this phase from November 9th and
the last date of submission would be November 21st (Again, the dates are
tentative and subject to change by the instructor). There will be multiple update
points between these dates. Your job is to add whatever optimization you see fit
and submit it. There are no restrictions on the number of times you can submit
your project (you could submit a new version every day if you please). Based on
the submissions I will update the competition ranking as early as possible once
I receive a submission that affects the ranking. For a sneak peak at how the
competition results will look like visit the
2005 255/455
competition webpage. The less the number of instructions your optimized programs
execute, more the points you get. Point distribution would be completely
relative and would depend on the rank of your optimizer when compared with
others. May the best optimizer win!
|
 |
|
|
Turn In |
You must include a Readme file in which you should
mention your name and the phase number first. Extra infos should be
presented are
- file and directory descriptions
- building and running guide
- program descriptions, on structure and
function
- descriptions of your optimizations
- bug reports
A clear readme file is necessary for others to
judge what you have done so that your effort be fairly evaluated. So
don't save too much time on that.
Turn in Instructions:
Copy all the files you
want to submit into a single directory. Double check the submission
checklist before submitting. Use the following command to turn in
your files:
/u/bai/TA/255/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 count. Upon each successful
submission, a confirming email will be sent to your mailbox, listing
all files submitted. Note that you cannot run the turnin
command from a Solaris machine.
Late Policy:
Late submissions suffer
10% reduction per day. If you have trouble finishing the assignments
on time, please let me know as early as possible. Probably you'll
need to explain your progress in documentation.
|
 |
|