Team 4 (Team Foo) Page
New results after optimization
- The number in the bracket indicates the number of reduced statements compared to the previous phase.
Somthing to say...
- we are kind of proud of our latest result. Thanks to everyone in our team, especially to our leader Bin ; ), and also thanks to our TA, Xiaoming who updates our ranking everyday, and last but definetely not least, many thanks to our professor Chen, who gave us such a nice opportunity to understand how much potentiality there lies to optimize our code and how much potentiality there lies in us to really do something about it. ^_^
Report on final optimization (2008-04-10)
- Further improve value numbering to extended basic blocks, which has nice effect on reducing the number of statements for sort.c and sort_insertion.c. This optimization is really basic and effective, but it didn't strike us at first. : )
- Copy propagation for returned values of function calls
We found that gcc uses a temporary variable to store the return value of a function call. For instance,
a.0 = foo();
a = a.0;
c = a + b;
By replacing a.0 with a, we can get rid of one copy statement and leave only a=foo(). This helps in cases when the program calls subroutine functions with returned values very often.
- Empty Basic Blocks Merging
After dead code elimination, we are actually left with some empty basic blocks and this discovery provides us another chance for further optimization. For instance, in the tax.c the gimple code generated after dead code elimination is like this:
if (a<b) goto L2 else goto L3;
L2: //empty BB
goto L4;
L3: //empty BB
L4:
a = a+c;
...
It seems clear that block L2 and L3 are actually dummy blocks. Although they don't increase our stmt counter, removing them can get rid of the cond stmt and provide a larger bb, which is good for our optimization.
Progress Report (2008-04-08)
The idea is if the total number of iteration is constant, we can unroll the loop and write the instructions inside the loop sequentially, thus reducing the number of statements needed for jumps and conditional testing. For instance, in the testcase sort.c we have some code fragment as follows:
while (idx < bound)
{
write(array_1[idx]);
idx = idx +1;
}
We know from constant propagation that variable bound is actually constant, thus the loop can be unwinded. Thus, we don't have test the condition idx<bound everytime we want to execute write. And the self-increament statement for idx is also saved. For loop with large number of iterations, loop unrolling is definitely an efficient optimization.
Progress Highlight (2008-04-05)
- Updating the statistics after optimization on loop unrolling.
Progress Highlight (2008-04-03)
- Group meeting and talk about ideas on how to do the new optimization on in-line function and loop unrolling.
- Updating the statistics after modifying the statement counting function.
Report on progress (2008-04-02)
The idea of copy propagation is to eliminate those statements that define some temporary variables which serve no other purpose than just a temporary copy of the value of other variables. Whenever we encounter a copy statement in the
form of "y=x", we replace all the occurrences of y after this statement with x given that both x and y have not been rewritten in between the copy statement and replaced statement. This optimization turns out to work very well on most test cases as we know copy statements are very common in a program. Following is some code fragment from test case "fibonacci.c":
fib(val)
{
...
val.1 = val;
D.1538 = array[val.1];
...
}
After copy propagation, the code becomes:
fib(val)
{
...
D.1538 = array[val];
...
}
We see that the variable "val.1" in the array reference has been replaced with "val" and the copy statement is deleted after optimization. And it should be noted that this optimization is not confined to basic block but in the global scope.
Progress Highlight (2008-04-01)
- Fixing a bug in constant propagation and further reduce the number of statement in open test case 'sort'. The bug is on handling the constant propagation for a not so apparent condition when the constant value is obtained after the binary operation of two constants.
- Start the work on the next phase of optimization which has something to do with in-line small functions.
Report on progress (2008-04-01)
By merging two or more printf statements, we can reduce the number of statements for output.
To merge two "printf", we just link the string list and the argument list of one "printf" statement at the end of those
of another "printf" statement respectively. One problem to be noted is about the built_in print statement, which
loses "\n" at the end of the output string after gimple code is generated. In order to link this statement with another
print statement, we have to recover "\n" at the output string for each built_in print statement. This optimization works
especially effecively for programs with astonishingly great number of output statements. For example, in the open test
case, the statements in tax program is reduced most among all test cases after applying print consolidation optimization.
Progress Highlight (up till 2008-03-30)
- Set up SVN for the single file cs255.c
- Implement optimizaiton on print consolidation (Detailed report will come soon)
- Implement optimization on copy propagation (Detailed report will come soon)
- Comment: we are happy with the result of copy propagation, which looks nice.
Meeting One (2008-03-25)
- Set up wiki page and access control
- Chose team name (after much disagreement, Team Foo)
- Decide to set up SVN to synchronize code (see VersionStuff)
- Agreed on team roles -- as assigned, though everyone will help a bit on everything
Team Role
- Leader: Bin Bao
- Developer: Bin Bao, Jonathan Gordon
- Reporting/testing: Yi Chu
Project Plan
- Analyze test cases and decide on optimization parts by Friday, March 28th
- Implementing optimization and testing on public test cases by April 4th
- Further testing and debugging
- Submitting project on April 7th