CSC 255/455 Project: Optimizing Compiler

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.

Introduction

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:

  1. 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 compiler.
  2. Optimize the program by analyzing and transforming the intermediate representation (IR) of the program.
  3. Use the back-end of the provided compiler to translate the intermediate representation back into C code.
Your task is to design and implement the second step of the compilation.

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:

                ...
                a = a + b[1];
                foo(a);
                ...

        should be transformed in the shape like

                ...
             AccessMem(4);
                 a = a + b[1];
                AccessMem(1);
                 foo(a);
                 ...

You also need to implement function Init(), AccessMem() and Report() and make them part of the program. They maintain a global counter that records the number of run-time data accesses in the program. Init() sets the counter to zero. Each time AccessMem(int num) is called, the counter is incremented by the value of num. Finally, Report() prints the total number of data accesses to screen. An example of instrumented programs (without the implementation of the functions) can be downloaded here. Except for recording and reporting memory accesses, 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 second phase. What you need to submit for the first phase include: In the second phase, you need to design and implement the optimization part of the compilation. For 255 students, the minimum requirement is to implement For 455 students, in addition to the above four, you also need to implement You can choose any other optimization techniques such as loop transformation to implement as well. The generated programs should still have the three functions mentioned above and the required function calls. But this time you are allowed to use a global integer array as registers. The accesses to the elements of this array are not counted as memory accesses. Design you compiler so that it can target machines with a different number of registers. The compilation should take as its parameter the number of registers it can use, which can be any number between 3 and 32. Compare the number of memory accesses reported by the transformed program and the original program to measure the effect of optimization. What you need to submit for the second phase include: Note: It is very possible we will schedule a presentation session for phase II. The details will be posted on Web when the schedule is ready. Please keep checking this web page for the latest changes!

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 "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.

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:

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. 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.