Difference: StandardOil (13 vs. 14)

Revision 142009-04-13 - DennisHuo

Line: 1 to 1
META TOPICPARENT name="IanChristopher"

Standard Oil Group Page

Line: 123 to 123
  • Allowing dead code elimination to eliminate arrays proved difficult, since any array access may potentially use any array definition, if the indices are not known statically. However, it was out of the question to mark all array usages as "absolutely useful", since this would prevent the dead loops in multiply.c from being removed.
  • In the majority of cases, limiting array def-use chains to the "last" array-write was able to pass the test cases. However, once aggressive inlining and loop unrolling techniques were used, array initializations often had the form of several consecutive array assignments, with the actual def-use chains difficult to determine.
  • The solution was to apply a third "use-propagation" phase, after I/O and function propagation, but before conditional-goto propagation. An initial pass is made to propagate usefullness only from I/O and function calls. Then, a pass-through is made to determine which arrays are used in those statements. As a heuristic, any array access in an absolutely useful statement renders ALL writes into that array absolutely useful.
  • The array propagation phase must be added into a loop until convergence; the def-use algorithm finds only the last write into an array as the exported definition, so propagation from useful statements can potentially unveil only a single array variable at a time. Once all instances of array accesses for a given "useful array" have been found and propagated, it will find the last definition into another unmarked "useful" array, if any exists.

Secondary Loop Unrolling

  • To aid in the cases of simple loops, a second loop unrolling technique has been implemented, where loops are unrolled linearly from the beginning of the induction variable. The loop body remains intact, but the induction variable is initialized just beyond a fixed unrolling point, and the loop body is copied and inserted before the induction variable initialization.
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