Project for CSC 255/455, Spring 2008

Introduction

In the project, you will add your own optimization passes in the most recent Gnu C compiler, Gcc 4.2.2. Because Gcc is a real compiler, it is more difficult to use than the teaching compiler used in previous semesters. 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 page on source browsing and debugging before you start. Wish you a happy journey with Gcc. Below is a quote from Will Durant from his 1926 book The story of philosophy

"Happiness, says an old lesson, lies rather in achievement than in possession or satiation. The healthy man asks not so much for happiness as for an opportunity to exercise his capacities; and if he must pay the penalty of pain for this freedom and this power he makes the forfeit cheerfully; it is not too great a price. We need resistance to raise us, as it raises the airplane or the bird; we need obstacles against which to sharpen our strength and stimulate our growth. Life without tragedy would be unworthy of a man."

Installation, compilation, and turn-in

  • Check out code and install: See Gcc-4.0.1 notes on installation and change all 4.0.1 to 4.2.2.
  • 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.
  • Use qsub -I at node64 to get a node to accelerate the make and install: see ClusterJobs
  • To prevent the problem of hardware incompatibility, you'd better build your compiler and use it and run the compiled executables on the same kind of machines.
  • Output gimple tree in c-like form: use option -fdump-tree-gimple
  • Invoke your pass: use -O2 -fcs255
  • Output gimple tree in c-like form after the pass for cs255: use option -fdump-cs255-tree-gimple
  • Put your own code into gcc-4.2.2/gcc/cs255.c
  • Use make for your testing: see An Example for Makefile
  • How to turn in your code: see Turn in for cs255

Browsing Gcc code and debugging

Other Gcc resources

Part 1: Trivial (5%)

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

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. The next best way is to ask your instructor, TA, and your classmates to find out how to get Gcc to do something. You are encouraged to discuss the project and work out the algorithms on paper or a white or black board with others. The only limitation is that you should not copy other people's code---every line in your submitted code file must be yours.

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.

Deadline: 11:59pm Feb 11, 2008.

Part 2: Weird Control Flow (10%)

  • 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 recent question and answer discusses some ambiguity and its recommended resolution.
  • 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 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.

Program 1: ab.c

int main() 
{
   int a, b;
   printf("Input two integers for comparison\n");
   scanf("%d", &a);
   scanf("%d", &b);
   printf("a is %d\n", a);
   printf("b is %d\n", b);
   if (a > b)
     printf("a is greater than b\n");
   else
     printf("a is no greater than b\n");
}

Program 2: loop.c

int main() 
{
   int i, s, n;
   printf("Input an integer for sum\n");
   scanf("%d", &n);
   for (i=0, s=0; i<=n; i++)
     s += i;
   printf("The sum from 1 to %d is %d\n", n, s);
}

Deadline: 11:59pm Feb 18, 2008.

Edit | Attach | Watch | Print version | History: r43 | r31 < r30 < r29 < r28 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r29 - 2008-02-17 - ChenDing
 
  • Edit
  • Attach
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding URCS? Send feedback