Assigned: Oct. 3, 2002
First Phase Due: 11:59:59 pm, Oct. 10
Second Phase Due: 11:59:59 pm, Nov. 27
Last Change: Nov. 26
Updated:
Oct.
24: Rules of memory accesses counting for
array accesses are changed.
See the modified examples here
and below.
Nov.
21:The set of test programs has been updated.
A new program jacobi.c
was added. Two programs, multiply.c and tax.c, have been
changed.
Be sure to get the latest version to test!
Nov.
21:In order to compare the effect of
optimization, we specify a set of inputs
here.
You need to report the number of memory accesses of each
programs with the specified input.
Nov.
21: An additional requirement for the report:
the report should evaluate
different techniques by measuring their individual and combined effect
on the number of memory accesses with and without register allocation.
Nov.
26: Late policy
for this project.
In this project, you need to design and implement the optimization phase for the provided compiler (written in Java), which makes a source-to-source conversion of C programs in three steps:
The project is divided into two phases. The first phase will be due on Oct. 10 and the second phase will be due on Nov. 27. The purpose of the first phase is to help you get familiar of the provided compiler. 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
In the first phase, you need to instrument the IR and insert the following
function calls into the program:
should be transformed in the shape like
...
AccessMem(4);
a = a + b[1];
AccessMem(1);
foo(a);
...
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 "lcc" is not available on the machine
you are using, 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/cs255/public/proj/src/" for undergraduate students and "/u/ytzhong/255/public/proj/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.
You only need to work on a subset of C language. The test programs that will be used to evaluate have the following properties:
Turnin Instructions
Copy all the files you want to submit into a single directory. Double
check the submission checklist before submitting. Undergraduate students
should use the following command to turnin your files:
/u/cs255/bin/TURNIN <dir>
Graduate students should use the following command to turnin your files:
/u/ytzhong/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 what you have finished and what makes you stuck in the documentation. You can also include your own test programs which show the working part of your compiler.