Difference: StandardOil (12 vs. 13)

Revision 132009-04-12 - DennisHuo

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

Standard Oil Group Page

Line: 119 to 119
  • The only reason SSA is needed is due to phi functions for value numbers killed in predecessors between the current block and its immediate dominator
  • We can simply ignore killed value numbers, but still import all "untouched" value numbers from the block's immediate dominator



Array Bug in Dead Code Elimination

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

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.
  • The loop is unrolled incrementally in each pass, to allow DCE and constant propagation between passes. For each copied out section, range checks are eliminated and any references to the induction variable are turned into NumConsts. In particular, in cases such as:

for(i = 0; i < 10; i++)

a[i] = i*512;

The loop body would normally require a temporary variable, since the RHS is an OpExpr involving a VarAcc and a NumConst. When unrolled, after further constant propagation, the RHS expression is collapsed into a NumConst, allowing the temporary variable to be eliminated, and the code to transform into

a[0] = 512;

a[1] = 1024;


  • Unsatisfiable loop ranges are eliminated in subsequent passes.


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