Project for CSC 255/455, Spring 2009

Introduction

In the project, you will add your own optimization passes in the Gnu C Compiler, GCC 4.2.2. It is not the most recent GCC, but should be sufficient for our project. You have to know the basic framework of GCC and how to manipulate the intermediate form, the gimple tree, for program analysis and transformation. This page includes many suggestions that will help you in the process. Please read the entire page and the pages about source browsing and debugging before you start.

Compilation, Installation and Run

  • Check out the code by using subversion, and install.
        mkdir gcc
        cd gcc
        svn co file:///p/compiler/repos/gcc-4.2.2/trunk gcc-4.2.2
           // if outside the firewall, use
           // svn co svn+ssh://usr_id@server_name.cs.rochester.edu/p/compiler/repos/gcc-4.2.2/trunk gcc-4.2.2
        mkdir obj
        cd obj
        ../gcc-4.2.2/configure --prefix=$INSTALL_DIR
          // $INSTALL_DIR is the directory you want to install your compiler
        make
        make install
  • For those who have no access to department research network, please download gcc-4.2.2.tar.bz2 and unzip it with the command tar -jxvf gcc-4.2.2.tar.bz2. There is also a copy on undergrad network at /home/hoover/u1/cs255/.
  • Use either our desktop or personal machine or one of the public use machines in the CS department. When using department machines, due to the shortage of space for the /home directory, it is better to put your code under /localdisk .
  • Invoke your pass: use -O2 -fcs255
  • Put your own code into gcc-4.2.2/gcc/cs255.c
  • Use make for your testing: see An Example for Makefile
  • About turn in: You need to turn in the file containing source code (normally only cs255.c), along with the README document describing the design, implementation and testing results when applicable. README is a very important part of your project, so lease take it seriously. To submit your work, make a new folder, put cs255.c and README into it, and then call /u/cs255/TURN_IN . (undergrad network) or /u/cs455/TURN_IN . (grad network) in the folder (Don't forget the "."). If you have problem with the submit script, feel free to send the two files to me by email.

Browsing GCC code

  • Gnu's wiki page on GCC getting started.
    • You can open in a web browser the following file /p/compiler/built/gcc-4.2.2/doxygen/ and start with index.html for a local copy of Gcc 4.2.2 documentation by doxygen. If you copy, the directory needs about 600MB disk space.
    • Installing and using Doxygen to generate your own documentation
    • Good Assorted Topics Page from developer site also has a decent overview.
  • Using Emacs (especially useful when you work remotely)
  • Using Eclipse (w/ CDT). You can download Eclipse IDE for C/C++ Developers (68 MB) from here.

Debugging

GCC Data Structures and Internal Representations

Part 1: Trivial (5%)(Individual Project) (Due: Feb. 4 11:59pm)

In this part, you will add a pass that will insert code into a program to count and output the number of executed statements when the program executes. You need to first add a call at the beginning of the main function, which has a global counter initialized to 0; then add a call before each gimple statement, which increments the counter; and finally add a call at the exit, which reports the run-time instruction counts. The three functions are provided in cs255-lib.c and cs255-lib.h:
  • Initialization: you'll need to add it at the entry of the main function
  • Increment: to be added before each real gimple statements (all except for labels)
  • Report: to be added at all possible exits of the program
  • Remember to add #include "cs255-lib.h" in your own testing programs.

This part should take at most tens of lines of code and no more than a day (including half an hour compiling the compiler for the first time). The purpose is to get you familiar with GCC and the basic GCC functions that you'll need for adding your optimization passes. Reading the relevant, existing code (in gcc-4.2.2/gcc/cs255.c) is the best way to help you writing your new code in an existing system. For instance, the code for counting the number of basic blocks and statements statically is already in the file. The code for getting the dynamic count of the basic blocks is also given.
For testing, there are some open test cases. You may use the results from them to check your code with your classmates. And they are very useful in following parts and final competition.

Part 2: Weird Control Flow (10%)(Individual Project)(Due: Feb. 16 11:59 pm)

  • Reverse all printf, scanf, and __builtin_puts statements in a basic block. If there are k such statements in a basic block, the first statement will be switched with the last statement, the second statement will be switched with the (k-1)th statement, and so on. At a call to printf, Gcc copies the arguments to a temporary variable. For the project, you need to move these copy statements with the call. A previous question in 2008 Q&A page discusses some ambiguity and its recommended resolution. If you have any other question, feel free to discuss with us, or solve it based on your own argument and document it.
  • If the statement is a conditional branch in the form of if cond goto L1; else goto L2, change it to if (not cond) goto L1; else goto L2. You only need to deal with >, >=, <, <=, '==', !=.
  • If the statement is a self increment (or decrement) by 1, change it to the opposite, that is, to decrement (or increment) by 1. For example, change i=i+1 to i=i-1 and vice versa.
  • Try all our test cases to make sure that your compiler generates code with no error, even though the generated code may not run correctly.

When you are working on this transformation, use the following two tests to check your compiler. The counting instructions should be inserted after the control flow changes.
As part of the documentation, submit two programs that would look bizarre but when compiled by your compiler, will produce the same output as the following two normal looking programs (ab.c, loop.c) when they are compiled by regular Gcc. (You may break for loop statement into a combination of several goto.)

Bonus point: We offer additional 5% of the project grade as bonus to students who use their compiler, using both of the bizarre examples or their equivalents, to baffle someone outside the class and document his or her reactions in the submitted report. The deadline for the bonus is the same as the project deadline.

Part 3: Value Numbering (10%)(Individual Project)(Due: Feb. 23 11:59pm)

In this part you need to implement value numbering in your compiler. As you know, value numbering can be carried out in different scopes: basic block, extended basic block, or dominator block. In this assignment, you are required to implement basic-block value numbering. However, optimizing at a larger scope may help you in your final competition. It is up to you to decide which algorithm you implement. In this and later projects, instrumentation should always be the last pass. Do not optimize on the instrumented program.

The public test programs use only basic arithmetic and logical operations. Your compiler is required only to correctly optimize these programs. It does not need to support pointer operations except to allow the taking-address operation in scanf. The absence of dynamic data allocation and pointer dereference removes most of the aliasing concerns and gives you more room for optimization. In addition, if you are taking CS255 instead of CS455, your compiler does not need to support or optimize array operations.

Your compiler may fail if a program contains operations it does not support. It should fail gracefully: it should check for cases it does not support, and when it finds such cases, output a descriptive error and exit. Documenting what your compiler checks in the README file is a good idea. Under no circumstances it may generate incorrect code (except in Part 2). Your compiler will be evaluated in hidden test cases, and an incorrectly optimized program would count against you more so than a failure in compilation.

In this and later projects, do not use any GCC optimization passes. You can use GCC routines for inspecting and changing gimple statements and their control flow, as you did in the first two projects. You need to write your own algorithm iterating through program statements, maintaining value tables, and removing redundant operations, as well as checking for unsupported operations. You may use vector, hash table, search tree, and other generic data structures in GCC. You may also use the analysis in GCC including the dominator information. For this project you may not use the SSA information or the GCC code for value numbering.

You do not have to use GCC code. If you do, you should document precisely the functions you use and the purpose of using them. Talk to the TA or the instructor if you are not sure.

If you find useful GCC routines, please post them to the class discussion page. 2008 Q&A page already contains some useful discussions, e.g. the temporary variables generated by GCC do not have names, so you need to figure out how to handle this. The project is a collaborative contest. You collaborate to understand and make the best use of existing code. You compete in the design and implementation of the optimization algorithms you add to the compiler.

Part 4: Data Flow (15%)(Individual Project)(Due: Mar.18 11:59pm)

You are asked to implement and use data flow analysis in the last part before the competition, in particular, implement the following parts in your cs255 pass.

  • Def-use graphs
  • Dead code elimination
  • Constant propagation (required for 455, Bonus for 255)
These data flow analysis have already been covered in class, although maybe detailed algorithms are not given. You can find some algorithm descriptions from Optimizing Compilers for Modern Architectures (UR access through books24x7). Working out your own algorithm before the implementation is a good strategy. This part will play an important role in your final compiler performance, so try to design it carefully and test it with our open benchmarks.

* Set ALLOWTOPICCHANGE = ChenDing, BinBao

Topic attachments
I Attachment History Action Size Date Who Comment
PDFpdf Project_Introduction.pdf r1 manage 120.9 K 2009-01-28 - 22:07 BinBao a general introduction to course project, given on Jan. 28
Edit | Attach | Watch | Print version | History: r30 | r26 < r25 < r24 < r23 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r24 - 2009-02-24 - BinBao
 
  • Edit
  • Attach
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding URCS? Send feedback