Team 4 (Team Foo) Page

New results after optimization

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

  • The number in the bracket indicates the number of reduced statements compared to the previous phase.

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

   val.1 = val;
   D.1538 = array[val.1];

After copy propagation, the code becomes:

  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: r14 - 2008-04-09 - 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