harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Apache Wiki <wikidi...@apache.org>
Subject [Harmony Wiki] Update of "Jitrino OPT/osr" by George Timoshenko
Date Tue, 06 May 2008 09:55:11 GMT
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.

Mime
View raw message