'osr' pass reduces the complexity of arithmetic instructions.

It is based on loop_unroll processOpnd function. However it gathers some additional OSR-specific information which is obsolele for loop_unroll.

The implementation is based on ideas from the paper "Operator Strength Reduction" by Keith D. Cooper, L.Taylor Simpson, Christopher Vick. However there are some differences between original alogorithm and the implementation:

  1. We do not traverse SSA graph, but rely on "lazy" detection of induction variables.
  2. The first step is not an SCC-detection, but CFG traversal that finds instruction of the following type: mul(iv, rc) or mul(rc, iv), (where iv -induction variable, rc - region constant, which is understood as loop invariant) and stores them uint32o cands vector.
  3. Useful step that prevents degradation: check if the induction variable is used as array subscript in the loop. If such a check returns true, we do not perform an optimization. The reasoning behind is the following: we will not be able to remove an old inductio variable in a case when it is used as an array subcsript. Even though our tranformation will reduce mul, it will increase register pres * sure and lengthen codepath. It's better to avoid such effects.
  4. Then we perform apply/reduce process to the instruction stored in cands vector.

Complexity OSR performs depth first search on each step - generally the complexity of this algorithm is exponential. However the SSA graphs are usually sparse, thus the results are no harder than quadratic complexity so, this otimization does not slow down the compilation in any noticable rate.

header file: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/osr.h
implementation file: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/osr.cpp

Jitrino_OPT/osr (last edited 2009-09-20 21:55:32 by localhost)