[Harmony Wiki] Update of "Jitrino OPT/osr" by George Timoshenko

[Apache Wiki <wi...@apache.org>]

Dear Wiki user,

You have subscribed to a wiki page or wiki category on "Harmony Wiki" for change notification.

The following page has been changed by George Timoshenko:
http://wiki.apache.org/harmony/Jitrino_OPT/osr

New page:
The 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.