Team 4 (Team Foo) Page

New results after optimization

Benchmarks Starting Point P1:Adding Print Consolidation P2: Adding Copy Propagation P3: Adding loop unrolling Final optimization
automaton 114 112 (-2) 97 (-15) 97 90
binrep 77 76 (-1) 72 (-4) 72 72
fibonacci 1098 1098 862 (-236) 730 (-132) 730
jacobi 10201117 10201117 10201117 8171485 (-2029632) 8171485
mandel 6477411 6477411 6477411 6477411 6474447
movingedge 1355 1355 1244 (-111) 902 (-342) 901
multiply 156 156 152 (-4) 24 (-128) 11
sort 10971 10971 8372 (-1699) 8100 (-272) 7569
sort_insertion 2943 2943 2318 (-625) 2256 (-62) 2002
tax 172 153 (-19) 117 (-36) 117 104
trivia 47 47 41 (-6) 40 (-1) 40

  • 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 and serves only to increase useless statements. By merging these these empty blocks, we are improving our result.

Progress Report (2008-04-08)

  • Loop unrolling

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)

  • Copy propagation

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)

  • Print consolidation.

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

Edit | Attach | Watch | Print version | History: r17 < r16 < r15 < r14 < r13 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r15 - 2008-04-11 - YiChu
 
  • Edit
  • Attach
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding URCS? Send feedback