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:

  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 front-end.
  2. Implement the optimizor by analyzing and transforming the AST of the program.
  3. 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:

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

        should be transformed in the shape like

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

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: 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: 3)  Optimization Phases

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

For all the optimization projects, you MUST include a text-only file called README, in which you will cover AT LEAST the following:

  1. Your name and the project number
  2. A list of all files in the directory and a short description of each.
  3. HOW TO COMPILE your program.
  4. HOW TO USE (execute) your program.
  5. A short description of the structure of your program.
  6. A short description of the design of the optimizer you build;
  7. 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.
  8. 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.
  9. 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:

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.