harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From e...@apache.org
Subject svn commit: r599804 - in /harmony/enhanced/drlvm/trunk/vm/jitrino: config/em64t/ config/ia32/ src/optimizer/
Date Fri, 30 Nov 2007 12:44:23 GMT
Author: egor
Date: Fri Nov 30 04:44:20 2007
New Revision: 599804

URL: http://svn.apache.org/viewvc?rev=599804&view=rev
Log:
applied HARMONY-5090, i.e. operator strength reduction optimization

(minor formatting fixes, build.sh test passed on Linux/ia32/Ubuntu_6.06)


Added:
    harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/osr.cpp   (with props)
    harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/osr.h   (with props)
Modified:
    harmony/enhanced/drlvm/trunk/vm/jitrino/config/em64t/opt.emconf
    harmony/enhanced/drlvm/trunk/vm/jitrino/config/em64t/server.emconf
    harmony/enhanced/drlvm/trunk/vm/jitrino/config/em64t/server_static.emconf
    harmony/enhanced/drlvm/trunk/vm/jitrino/config/ia32/opt.emconf
    harmony/enhanced/drlvm/trunk/vm/jitrino/config/ia32/server.emconf
    harmony/enhanced/drlvm/trunk/vm/jitrino/config/ia32/server_static.emconf

Modified: harmony/enhanced/drlvm/trunk/vm/jitrino/config/em64t/opt.emconf
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/config/em64t/opt.emconf?rev=599804&r1=599803&r2=599804&view=diff
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/config/em64t/opt.emconf (original)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/config/em64t/opt.emconf Fri Nov 30 04:44:20 2007
@@ -24,7 +24,9 @@
 
 -XX:jit.CS_OPT.path=opt_init,translator,optimizer,hir2lir,codegen
 
--XX:jit.CS_OPT.path.optimizer=ssa,devirt,hlo_api_magic,inline,purge,hvn,simplify,dce,uce,escape,dce,uce,memopt,simplify,dce,uce,lower,dessa,statprof
+-XX:jit.CS_OPT.path.optimizer=ssa,devirt,hlo_api_magic,inline,purge,osr_path,escape_path,dce,uce,memopt,simplify,dce,uce,lower,dessa,statprof
+-XX:jit.CS_OPT.path.osr_path=simplify,dce,uce,gcm,osr
+-XX:jit.CS_OPT.path.escape_path=hvn,simplify,dce,uce,escape
 -XX:jit.CS_OPT.path.codegen=lock_method,bbp,gcpoints,cafl,dce1,i8l-,api_magic,early_prop-,itrace-,native,constraints,dce2,regalloc,spillgen,layout,copy,rce-,stack,break-,iprof-,emitter!,si_insts,gcmap,info,unlock_method
 -XX:jit.CS_OPT.path.dce1=cg_dce
 -XX:jit.CS_OPT.path.dce2=cg_dce

Modified: harmony/enhanced/drlvm/trunk/vm/jitrino/config/em64t/server.emconf
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/config/em64t/server.emconf?rev=599804&r1=599803&r2=599804&view=diff
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/config/em64t/server.emconf (original)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/config/em64t/server.emconf Fri Nov 30 04:44:20 2007
@@ -69,7 +69,9 @@
 -XX:jit.SD1_OPT.arg.optimizer.vp_instrument.profile_abstract=true
 
 
--XX:jit.SD2_OPT.path.optimizer=ssa,simplify,dce,uce,devirt_virtual,edge_annotate,unguard,devirt_intf,hlo_api_magic,inline,purge,hvn,simplify,dce,uce,escape,dce,uce,hvn,dce,uce,inline_helpers,purge,simplify,uce,dce,uce,abce,lower,dce,uce,memopt,reassoc,dce,uce,hvn,dce,uce,gcm,dessa,statprof
+-XX:jit.SD2_OPT.path.optimizer=ssa,simplify,dce,uce,devirt_virtual,edge_annotate,unguard,devirt_intf,hlo_api_magic,inline,purge,osr_path,escape_path,dce,uce,hvn,dce,uce,inline_helpers,purge,simplify,uce,dce,uce,abce,lower,dce,uce,memopt,reassoc,dce,uce,hvn,dce,uce,gcm,dessa,statprof
+-XX:jit.SD2_OPT.path.osr_path=simplify,dce,uce,gcm,osr
+-XX:jit.SD2_OPT.path.escape_path=hvn,simplify,dce,uce,escape
 -XX:jit.SD2_OPT.path.abce=classic_abcd,dce,uce,dessa,statprof,peel,ssa,hvn,simplify,dce,uce,memopt,dce,uce,dessa,fastArrayFill,ssa,statprof,dabce,dce,uce
 -XX:jit.SD2_OPT.path.codegen=lock_method,bbp,gcpoints,cafl,dce1,i8l-,api_magic,early_prop-,itrace-,native,cg_fastArrayFill,constraints,dce2,regalloc,spillgen,layout,copy,rce-,stack,break-,iprof-,emitter!,si_insts,gcmap,info,unlock_method
 -XX:jit.SD2_OPT.path.dce1=cg_dce

Modified: harmony/enhanced/drlvm/trunk/vm/jitrino/config/em64t/server_static.emconf
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/config/em64t/server_static.emconf?rev=599804&r1=599803&r2=599804&view=diff
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/config/em64t/server_static.emconf (original)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/config/em64t/server_static.emconf Fri Nov 30 04:44:20 2007
@@ -24,7 +24,8 @@
 
 -XX:jit.SS_OPT.path=opt_init,translator,optimizer,hir2lir,codegen
 
--XX:jit.SS_OPT.path.optimizer=ssa,simplify,dce,uce,statprof,devirt,hlo_api_magic,inline,purge,simplify,dce,uce,hvn,dce,uce,dessa,statprof,peel,ssa,hvn,simplify,dce,uce,lower,dce,uce,memopt,reassoc,dce,uce,hvn,dce,uce,classic_abcd,dce,uce,gcm,dessa,statprof
+-XX:jit.SS_OPT.path.optimizer=ssa,simplify,dce,uce,statprof,devirt,hlo_api_magic,inline,purge,osr_path,simplify,dce,uce,hvn,dce,uce,dessa,statprof,peel,ssa,hvn,simplify,dce,uce,lower,dce,uce,memopt,reassoc,dce,uce,hvn,dce,uce,classic_abcd,dce,uce,gcm,dessa,statprof
+-XX:jit.SS_OPT.path.osr_path=simplify,dce,uce,gcm,osr
 -XX:jit.SS_OPT.path.codegen=lock_method,bbp,gcpoints,cafl,dce1,i8l-,api_magic,early_prop-,itrace-,native,constraints,dce2,regalloc,spillgen,layout,copy,rce-,stack,break-,iprof-,emitter!,si_insts,gcmap,info,unlock_method
 -XX:jit.SS_OPT.path.dce1=cg_dce
 -XX:jit.SS_OPT.path.dce2=cg_dce

Modified: harmony/enhanced/drlvm/trunk/vm/jitrino/config/ia32/opt.emconf
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/config/ia32/opt.emconf?rev=599804&r1=599803&r2=599804&view=diff
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/config/ia32/opt.emconf (original)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/config/ia32/opt.emconf Fri Nov 30 04:44:20 2007
@@ -24,7 +24,9 @@
 
 -XX:jit.CS_OPT.path=opt_init,lock_method,translator,optimizer,hir2lir,codegen,unlock_method
 
--XX:jit.CS_OPT.path.optimizer=ssa,devirt,hlo_api_magic,inline,purge,simplify,dce,uce,lazyexc,throwopt,hvn,simplify,dce,uce,escape,dce,uce,memopt,simplify,dce,uce,lower,statprof,unroll,ssa,simplify,dce,uce,dessa,statprof
+-XX:jit.CS_OPT.path.optimizer=ssa,devirt,hlo_api_magic,inline,purge,osr_path,simplify,dce,uce,lazyexc,throwopt,escape_path,dce,uce,memopt,simplify,dce,uce,lower,statprof,unroll,ssa,simplify,dce,uce,dessa,statprof
+-XX:jit.CS_OPT.path.osr_path=simplify,dce,uce,gcm,osr
+-XX:jit.CS_OPT.path.escape_path=hvn,simplify,dce,uce,escape
 -XX:jit.CS_OPT.path.codegen=bbp,btr,gcpoints,cafl,dce1,i8l,api_magic,early_prop,peephole,itrace-,native,constraints,dce2,regalloc,spillgen,copy,i586,layout,rce+,stack,break-,iprof-,peephole,emitter!,si_insts,gcmap,info
 -XX:jit.CS_OPT.path.dce1=cg_dce
 -XX:jit.CS_OPT.path.dce2=cg_dce

Modified: harmony/enhanced/drlvm/trunk/vm/jitrino/config/ia32/server.emconf
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/config/ia32/server.emconf?rev=599804&r1=599803&r2=599804&view=diff
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/config/ia32/server.emconf (original)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/config/ia32/server.emconf Fri Nov 30 04:44:20 2007
@@ -71,7 +71,9 @@
 
 -XX:jit.SD2_OPT.path=opt_init,translator,optimizer,hir2lir,codegen
 
--XX:jit.SD2_OPT.path.optimizer=ssa,simplify,dce,uce,devirt_virtual,edge_annotate,unguard,devirt_intf,hlo_api_magic,inline,purge,simplify,dce,uce,lazyexc,throwopt,hvn,simplify,dce,uce,escape,inline_helpers,purge,simplify,uce,dce,uce,abce,lower,dce,uce,statprof,unroll,ssa,simplify,dce,uce,memopt,reassoc,dce,uce,hvn,dce,uce,gcm,dessa,statprof
+-XX:jit.SD2_OPT.path.optimizer=ssa,simplify,dce,uce,devirt_virtual,edge_annotate,unguard,devirt_intf,hlo_api_magic,inline,purge,osr_path,simplify,dce,uce,lazyexc,throwopt,escape_path,inline_helpers,purge,simplify,uce,dce,uce,abce,lower,dce,uce,statprof,unroll,ssa,simplify,dce,uce,memopt,reassoc,dce,uce,hvn,dce,uce,gcm,dessa,statprof
+-XX:jit.SD2_OPT.path.osr_path=simplify,dce,uce,gcm,osr
+-XX:jit.SD2_OPT.escape_path=hvn,simplify,dce,uce,escape
 -XX:jit.SD2_OPT.path.abce=classic_abcd,dce,uce,dessa,statprof,peel,ssa,hvn,simplify,dce,uce,memopt,dce,uce,dessa,fastArrayFill,ssa,statprof,dabce,dce,uce
 -XX:jit.SD2_OPT.path.codegen=lock_method,bbp,btr,gcpoints,cafl,dce1,i8l,api_magic,early_prop,peephole,itrace-,native,cg_fastArrayFill,constraints,dce2,regalloc,spillgen,copy,i586,layout,rce+,stack,break-,iprof-,peephole,emitter!,si_insts,gcmap,info,unlock_method
 -XX:jit.SD2_OPT.path.dce1=cg_dce

Modified: harmony/enhanced/drlvm/trunk/vm/jitrino/config/ia32/server_static.emconf
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/config/ia32/server_static.emconf?rev=599804&r1=599803&r2=599804&view=diff
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/config/ia32/server_static.emconf (original)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/config/ia32/server_static.emconf Fri Nov 30 04:44:20 2007
@@ -24,7 +24,8 @@
 
 -XX:jit.SS_OPT.path=opt_init,lock_method,translator,optimizer,hir2lir,codegen,unlock_method
 
--XX:jit.SS_OPT.path.optimizer=ssa,simplify,dce,uce,statprof,devirt,hlo_api_magic,inline,purge,simplify,dce,uce,lazyexc,throwopt,statprof,hvn,dce,uce,dessa,statprof,peel,ssa,hvn,simplify,dce,uce,lower,dce,uce,unroll,ssa,simplify,dce,uce,memopt,reassoc,dce,uce,hvn,dce,uce,classic_abcd,dce,uce,gcm,dessa,statprof
+-XX:jit.SS_OPT.path.optimizer=ssa,simplify,dce,uce,statprof,devirt,hlo_api_magic,inline,purge,osr_path,simplify,dce,uce,lazyexc,throwopt,statprof,hvn,dce,uce,dessa,statprof,peel,ssa,hvn,simplify,dce,uce,lower,dce,uce,unroll,ssa,simplify,dce,uce,memopt,reassoc,dce,uce,hvn,dce,uce,classic_abcd,dce,uce,gcm,dessa,statprof
+-XX:jit.SS_OPT.path.osr_path=simplify,dce,uce,gcm,osr
 -XX:jit.SS_OPT.path.codegen=bbp,btr,gcpoints,cafl,dce1,i8l,api_magic,early_prop,peephole,itrace-,native,constraints,dce2,regalloc,spillgen,copy,i586,layout,rce+,stack,break-,iprof-,peephole,emitter!,si_insts,gcmap,info
 -XX:jit.SS_OPT.path.dce1=cg_dce
 -XX:jit.SS_OPT.path.dce2=cg_dce

Added: harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/osr.cpp
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/osr.cpp?rev=599804&view=auto
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/osr.cpp (added)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/osr.cpp Fri Nov 30 04:44:20 2007
@@ -0,0 +1,851 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one or more
+ *  contributor license agreements.  See the NOTICE file distributed with
+ *  this work for additional information regarding copyrighashTable ownership.
+ *  The ASF licenses this file to You under the Apache License, Version 2.0
+ *  (the "License"); you may not use this file except in compliance with
+ *  the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+
+
+/*
+ * NOTE: The code below 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.
+ *
+ * On 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.   
+ */
+
+#include "osr.h"
+#include "deadcodeeliminator.h"
+
+namespace Jitrino {
+
+DEFINE_SESSION_ACTION(OSRPass, osr, "Operator Strength Reduction")
+
+static uint32 signof(int v){ return (v == 0) ? 0 : (v < 0 ? -1 : 1);}
+
+
+/* The code below is based on loop_unroll processOpnd function. However it
+ * gathers some additional OSR-specific information which is obsolele for
+ * loop_unroll. 
+ *
+ * TODO: create flexible mechanism for gathering info on the operands which
+ * would help to avoid code duplication from the one hand, and be customizable
+ * from another hand 
+ */
+OSROpndInfo OSRInductionDetector::processOpnd(LoopTree* tree,
+                                      LoopNode* loopHead,
+                                      InstStack& defStack,
+                                      const Opnd* opnd,
+                                      iv_detection_flag flag){
+    if (Log::isEnabled()) {
+        Log::out() << "Processing opnd: ";
+        opnd->print(Log::out());
+        Log::out() << "\n";
+    }
+
+    OSROpndInfo result;
+    Inst* defInst = opnd->getInst();
+
+    if (std::find(defStack.begin(), defStack.end(), defInst) !=
+        defStack.end()) {
+        result.setType(OSROpndInfo::COUNTER);
+        result.setIncrement(0);
+        result.setOpnd((Opnd*) opnd);
+        return result;
+    }
+
+    Opcode opcode = defInst->getOpcode();
+
+    if (opcode == Op_LdConstant) {
+        result.setType(OSROpndInfo::LD_CONST);
+        result.setConst(defInst->asConstInst()->getValue().i4);
+        result.setOpnd((Opnd*) opnd);
+        result.setHeader((Opnd*) opnd);
+        result.setHeaderFound();
+        return result;
+    }
+
+    if (!inExactLoop(tree, (Opnd*) opnd, loopHead)) {
+        result.setOpnd((Opnd*) opnd);
+        result.setHeader((Opnd*) opnd);
+        result.setHeaderFound();
+        return result;
+    }
+
+    defStack.push_back(defInst);
+
+    if (opcode == Op_Phi) {
+        OSROpndInfo info1 =
+            processOpnd(tree, loopHead, defStack, defInst->getSrc(0));
+
+        if (defInst->getNumSrcOperands() > 1) {
+            OSROpndInfo info2 =
+                processOpnd(tree, loopHead, defStack, defInst->getSrc(1));
+            if ((info1.isCounter() && !info1.isPhiSplit())
+                && (info2.isDOL() || info2.isLDConst())
+                || (info2.isCounter()
+                    && !info2.isPhiSplit())
+                && (info1.isDOL() || info1.isLDConst())) {
+
+                result.setType(OSROpndInfo::COUNTER);
+                result.setIncrement(info1.isCounter()? info1.
+                                    getIncrement() : info2.getIncrement());
+                result.markPhiSplit();
+                result.setHeader((Opnd*) opnd);
+                result.setHeaderFound();
+            } else if ((flag == CHOOSE_MAX_IN_BRANCH) && info1.isCounter()
+                       && info2.isCounter()
+                       && signof(info1.getIncrement()) ==
+                       signof(info2.getIncrement())) {
+
+                result.setType(OSROpndInfo::COUNTER);
+                result.setIncrement(std::abs(info1.getIncrement()) >
+                                    std::abs(info2.getIncrement())? info1.
+                                    getIncrement() : info2.getIncrement());
+                result.markPhiSplit();
+                result.setHeader((Opnd*) opnd);
+                result.setHeaderFound();
+            } else {
+                result.setType(OSROpndInfo::UNDEF);
+            }
+        }
+    } else if (opcode == Op_Add || opcode == Op_Sub) {
+        Opnd* opnd1 = defInst->getSrc(0);
+        Opnd* opnd2 = defInst->getSrc(1);
+        OSROpndInfo info1 = processOpnd(tree, loopHead, defStack, opnd1);
+        OSROpndInfo info2 = processOpnd(tree, loopHead, defStack, opnd2);
+
+        if ((info1.isLDConst() || info1.isDOL())
+            && (info2.isLDConst() || info2.isDOL())) {
+            if (info1.isLDConst() && info2.isLDConst()
+                && info1.getConst() == info2.getConst()) {
+                result.setType(OSROpndInfo::LD_CONST);
+                result.setConst(info1.getConst());
+                writeHeaderToResult(result, tree, info1, info2);
+            }
+        } else if ((info1.isCounter() && info2.isLDConst())
+                   || (info2.isCounter() && info1.isLDConst())) {
+            uint32 increment = info1.isCounter() ?
+                info1.getIncrement() : info2.getIncrement();
+            uint32 diff = info1.isLDConst()? info1.getConst() : info2.getConst();
+            bool monotonousFlag = increment == 0 || diff == 0
+                || (opcode == Op_Add && signof(diff) == signof(increment))
+                || (opcode == Op_Sub && signof(diff) != signof(increment));
+            if (monotonousFlag) {
+                result.setType(OSROpndInfo::COUNTER);
+                if ((info1.isCounter() && info1.isPhiSplit()) ||
+                    (info2.isCounter() && info2.isPhiSplit())) {
+                    result.markPhiSplit();
+                    writeHeaderToResult(result, tree, info1, info2);
+                }
+                if (opcode == Op_Add) {
+                    result.setIncrement(increment + diff);
+                    writeHeaderToResult(result, tree, info1, info2);
+                } else {
+                    result.setIncrement(increment - diff);
+                    writeHeaderToResult(result, tree, info1, info2);
+                }
+            } else {
+                result.setType(OSROpndInfo::UNDEF);
+            }
+        } else {
+            result.setType(OSROpndInfo::UNDEF);
+        }
+    } else if (opcode == Op_StVar || opcode == Op_LdVar) {
+        Opnd* newOpnd = defInst->getSrc(0);
+        result = processOpnd(tree, loopHead, defStack, newOpnd);
+    } else if (opcode == Op_TauArrayLen) {
+        Opnd* arrayOpnd = defInst->getSrc(0);
+        result = processOpnd(tree, loopHead, defStack, arrayOpnd);
+    } else {
+        result.setType(OSROpndInfo::UNDEF);
+    }
+
+    defStack.pop_back();
+    result.setOpnd((Opnd*) opnd);
+    return result;
+}
+
+bool OSRInductionDetector::inExactLoop(LoopTree* tree, Opnd* opnd,
+                                       LoopNode* curnode){
+    LoopNode* lnode = tree->getLoopNode(opnd->getInst()->getNode(), false);
+    if (lnode == 0) {
+        return false;
+    } else if (lnode == curnode) {
+        return true;
+    }
+    return false;
+}
+
+bool OSRInductionDetector::inLoop(LoopTree* tree, Opnd* opnd){
+    LoopNode* lnode = tree->getLoopNode(opnd->getInst()->getNode(), false);
+    if (lnode == 0) {
+        return false;
+    }
+    return true;
+}
+
+void OSRInductionDetector::writeHeaderToResult(OSROpndInfo& result,
+                                               LoopTree* tree,
+                                               OSROpndInfo info1,
+                                               OSROpndInfo info2){
+    if (result.isCounter()) {
+        bool opnd1_in_loop = inLoop(tree, info1.getOpnd());
+        bool opnd2_in_loop = inLoop(tree, info2.getOpnd());
+        if (opnd1_in_loop) {
+            result.setHeader(info1.getHeader());
+        } else if (opnd2_in_loop) {
+            result.setHeader(info2.getHeader());
+        }
+        result.setHeaderFound();
+
+    } else {
+        if (info2.isHeaderFound()) {
+            result.setHeader(info2.getHeader());
+            result.setHeaderFound();
+        } else if (info1.isHeaderFound()) {
+            result.setHeader(info1.getHeader());
+            result.setHeaderFound();
+        }
+    }
+}
+
+OSR::OSR(IRManager & irManager0, 
+         MemoryManager & memManager, 
+         LoopTree* loop_Tree, 
+         DominatorTree* dtree): iv(0),
+                                 rc(0),
+                                 irManager(irManager0),
+                                 mm(memManager),
+                                 loopTree(loop_Tree),
+                                 hashTable(new CSEHashTable(memManager)),
+                                 dominators(dtree),
+                                 leading_operands(memManager),
+                                 addedOpnds(memManager), 
+                                 cands(memManager),
+                                 LFTRHashMap(memManager){}
+
+void OSRPass::_run(IRManager & irm){
+    splitCriticalEdges(irm);
+    computeDominatorsAndLoops(irm);
+    LoopTree* loopTree = irm.getLoopTree();
+    DominatorTree* dominatorTree = irm.getDominatorTree();
+    OSR osr(irm, irm.getMemoryManager(), loopTree, dominatorTree);
+    osr.runPass();
+}
+
+void OSR::recordIVRC(Inst* inst){
+
+    if (Log::isEnabled()) {
+        Log::out() << "Processing: ";
+        inst->print(Log::out());
+        Log::out() << "\n";
+    }
+
+    Opnd* opnd1 = inst->getSrc(0);
+    Opnd* opnd2 = inst->getSrc(1);
+
+    LoopNode* lnode = loopTree->getLoopNode(inst->getNode(), false);
+    if (lnode == 0)
+        return;
+
+    OSRInductionDetector::InstStack defstack(mm);
+    OSROpndInfo info1 = OSRInductionDetector::processOpnd(loopTree, lnode, defstack, opnd1);
+    OSROpndInfo info2 = OSRInductionDetector::processOpnd(loopTree, lnode, defstack,opnd2);
+
+    if (Log::isEnabled()) {
+        info1.print(Log::out());
+        info2.print(Log::out());
+
+    }
+    if (info1.isCounter() && (info2.isLDConst() || info2.isDOL())) {
+        iv = (SsaOpnd*) info1.getOpnd();
+        rc = (SsaOpnd*) info2.getOpnd();
+        bool no_array = isNoArrayInLoop(lnode, iv);
+        if (no_array) {
+            writeLeadingOperand((SsaOpnd*) opnd1,
+                                (SsaOpnd*) info1.getHeader());
+        } else {
+            iv = 0;
+            rc = 0;
+        }
+    } else if (info2.isCounter() && (info1.isLDConst() || info1.isDOL())) {
+        iv = (SsaOpnd*) info2.getOpnd();
+        rc = (SsaOpnd*) info1.getOpnd();
+
+        bool no_array = isNoArrayInLoop(lnode, iv);
+
+        if (no_array) {
+            writeLeadingOperand((SsaOpnd*) opnd2,
+                                (SsaOpnd*) info2.getHeader());
+        } else {
+            iv = 0;
+            rc = 0;
+        }
+    }
+}
+
+bool OSR::isNoArrayInLoop(LoopNode* lnode, SsaOpnd* iv){
+    Nodes nodes = lnode->getNodesInLoop();
+    StlVector < Node* >::iterator iter = nodes.begin(), end = nodes.end();
+
+    for (; iter != end; iter++) {
+        Node* node = *iter;
+        Inst* last_inst = (Inst*) node->getLastInst();
+
+        for (Inst* iter1 = (Inst*) node->getFirstInst();
+             iter1 != last_inst; iter1 = iter1->getNextInst()) {
+            Inst inst = *iter1;
+            if (inst.getOpcode() == Op_AddScaledIndex) {
+                Opnd* opnd = inst.getSrc(1);
+                findLeadingOpnd(&inst, (SsaOpnd*) opnd);
+                SsaOpnd* lop = getLeadingOperand((SsaOpnd*) opnd);
+                if (lop != 0) {
+                    SsaOpnd* ivlop = getLeadingOperand(iv);
+                    if (lop == ivlop) {
+                        return false;
+                    }
+
+                }
+
+            }
+        }
+    }
+    return true;
+}
+
+void OSR::writeInst(Inst* inst){
+    Opcode opcode = inst->getOpcode();
+    if (opcode == Op_Mul) {
+        recordIVRC(inst);
+        if (iv != 0 && rc != 0) {
+            reduceCand red_c((SsaOpnd*) inst->getDst(), iv, rc);
+            cands.push_back(red_c);
+        }
+        iv = 0;
+        rc = 0;
+    }
+}
+
+void OSR::runPass(){
+    StlVector < Node* >nodes(mm);
+    ControlFlowGraph& flowgraph = irManager.getFlowGraph();
+    flowgraph.getNodes(nodes);
+
+    StlVector < Node* >::iterator iter = nodes.begin(), end = nodes.end();
+
+    for (; iter != end; iter++) {
+        Node* node = *iter;
+        Inst* last_inst = (Inst*) node->getLastInst();
+
+        for (Inst* iter1 = (Inst*) node->getFirstInst();
+             iter1 != last_inst; iter1 = iter1->getNextInst()) {
+            writeInst(iter1);
+        }
+    }
+
+    StlVector < reduceCand >::iterator viter = cands.begin();
+    StlVector < reduceCand >::iterator vend = cands.end();
+
+    for (; viter != vend; viter++) {
+        reduceCand rcand = *viter;
+        replace(rcand.dst, rcand.iv, rcand.rc);
+    }
+
+    StlVector < Node* >nnodes(mm);
+    ControlFlowGraph& ffg = irManager.getFlowGraph();
+    ffg.getNodes(nnodes);
+    replaceLinearFuncTest(nnodes);
+
+}
+
+void OSR::writeLeadingOperand(SsaOpnd* opnd, SsaOpnd* header){
+    leading_operands[opnd] = header;
+    if (Log::isEnabled()) {
+        Log::out() << "Header of: " << std::endl;
+        opnd->print(Log::out());
+        Log::out() << "is" << std::endl;
+        if (header) {
+            header->print(Log::out());
+            Log::out() << std::endl;
+        } else {
+            Log::out() << "Null" << std::endl;
+        }
+    }
+}
+
+SsaOpnd* OSR::getLeadingOperand(SsaOpnd* opnd){
+    if (opnd == 0) {
+        return 0;
+    }
+    SsaOpnd* result = 0;
+    if (leading_operands.has(opnd)) {
+        result = leading_operands[opnd];
+    }
+    return result;
+}
+
+void OSR::replace(SsaOpnd* opnd, SsaOpnd* iv, SsaOpnd* rc){
+    Inst* inst = opnd->getInst();
+    SsaOpnd* dstInst = reduce(inst->getDst()->getType(), inst->getOpcode(),
+                              inst->getOperation(), iv, rc);
+    Inst* copyInst = irManager.getInstFactory().makeCopy(opnd, dstInst);
+    copyInst->insertBefore(inst);
+    inst->unlink();
+    writeLeadingOperand(opnd, getLeadingOperand(iv));
+
+}
+
+Inst* OSR::insertNewDef(Type* type, SsaOpnd* iv, SsaOpnd* rc){
+    Inst* inst = copyInst(type, iv->getInst(), rc,
+                          Operation(iv->getInst()->getOpcode()));
+    insertInst(inst, iv->getInst());
+    return inst;
+}
+
+void OSR::findLeadingOpnd(Inst* newDef, SsaOpnd* opnd){
+    Node* node = newDef->getNode();
+    LoopNode* lnode = this->loopTree->getLoopNode(node, false);
+    OSRInductionDetector::InstStack newstack(this->mm);
+    OSROpndInfo oinfo = OSRInductionDetector::processOpnd(loopTree, lnode, newstack, opnd);
+    if (oinfo.isHeaderFound()) {
+        writeLeadingOperand(opnd, (SsaOpnd*) oinfo.getHeader());
+    }
+}
+
+void OSR::replaceOperand(uint32 num, Inst* inst, SsaOpnd* opnd,
+                         Opnd* iv_lead, Node* iv_lead_node,
+                         Type* type, Opcode opcode, SsaOpnd* rc,
+                         Operation op){
+    findLeadingOpnd(inst, opnd);
+    SsaOpnd* opnd_header = getLeadingOperand(opnd);
+    Node* opnd_headerNode = 0;
+
+    if (opnd_header != 0) {
+        opnd_headerNode = opnd_header->getInst()->getNode();
+    }
+
+    if ((iv_lead != 0) && (opnd_headerNode == iv_lead_node)) {
+        inst->setSrc(num, reduce(type, opcode, op, opnd, rc));
+    } else if ((opcode == Op_Mul) || (inst->getOpcode() == Op_Phi)) {
+        SsaOpnd* newOpnd = apply(type, opcode, op, opnd, rc);
+        if (opnd->isSsaVarOpnd()) {
+            newOpnd = makeVar(newOpnd, inst->getDst()->asSsaVarOpnd(),
+                              opnd->getInst());
+        } else {
+            newOpnd = makeTmp(newOpnd->asSsaOpnd(), opnd->getInst());
+        }
+        inst->setSrc(num, newOpnd);
+    }
+}
+
+void OSR::replaceOperands(Type* type, Inst* inst, SsaOpnd* iv,
+                          SsaOpnd* rc, Opcode opcode, Operation op){
+
+    if (Log::isEnabled()) {
+        Log::out() << "Replacing operands" << std::endl;
+        Log::out() << "RC" << std::endl;
+        rc->print(Log::out());
+        Log::out() << "IV" << std::endl;
+        iv->print(Log::out());
+        Log::out() << std::endl;
+    }
+
+    uint32 numOpnds = inst->getNumSrcOperands();
+    SsaOpnd* iv_lead = getLeadingOperand(iv);
+    Node* iv_lead_node = iv_lead->getInst()->getNode();
+    for (uint32 num = 0; num < numOpnds; num++) {
+        SsaOpnd* opnd = inst->getSrc(num)->asSsaOpnd();
+        replaceOperand(num, inst, opnd, iv_lead, iv_lead_node, type,
+                       opcode, rc, op);
+    }
+
+}
+
+SsaOpnd* OSR::reduce(Type* type, Opcode opcode, Operation op,
+                     SsaOpnd* iv, SsaOpnd* rc){
+    if (Log::isEnabled()) {
+        Log::out() << "Reducing: ";
+        iv->print(Log::out());
+        Log::out() << std::endl;
+        rc->print(Log::out());
+        Log::out() << std::endl;
+    }
+    Inst* newinst = hashTable->lookup(op.encodeForHashing(), iv->getId(), rc->getId());
+    if (!newinst) {
+        Inst* newDef = insertNewDef(type, iv, rc);
+        if (Log::isEnabled()) {
+            Log::out() << "NewDef" << std::endl;
+            newDef->print(Log::out());
+            Log::out() << std::endl;
+        }
+
+        SsaOpnd* result = newDef->getDst()->asSsaOpnd();
+        writeLeadingOperand(result, getLeadingOperand(iv));
+        hashTable->insert(op.encodeForHashing(), iv->getId(),
+                          rc->getId(), newDef);
+        writeLFTR(iv, op, rc, newDef->getDst()->asSsaOpnd());
+        replaceOperands(type, newDef, iv, rc, opcode, op);
+        return result;
+
+    } else {
+        SsaOpnd* result = newinst->getDst()->asSsaOpnd();
+        return result;
+    }
+}
+
+Inst* OSR::copyInst(Type* type, Inst* oldDef, SsaOpnd* rc, Operation op){
+    Inst* newDef = 0;
+    SsaOpnd* old = oldDef->getDst()->asSsaOpnd();
+    if (old->isSsaVarOpnd()) {
+        newDef = createNewVarInst(old, type, oldDef, rc, op);
+    } else {
+        InstFactory& instFactory = irManager.getInstFactory();
+        OpndManager& opndManager = irManager.getOpndManager();
+        OpndRenameTable opndRenameTable(mm);
+        newDef = instFactory.clone(oldDef, opndManager, &opndRenameTable);
+        newDef->getDst()->setType(type);
+        newDef->setType(type->tag);
+    }
+    return newDef;
+}
+
+Inst* OSR::createNewVarInst(SsaOpnd* old, Type* type,
+                            Inst* old_inst, SsaOpnd* rc, Operation op){
+    InstFactory& instFactory = irManager.getInstFactory();
+    OpndManager& opndManager = irManager.getOpndManager();
+
+    VarOpnd* oldVar = old->asSsaVarOpnd()->getVar();
+    VarOpnd* newVar = createOperand(type, oldVar, rc, op);
+    SsaVarOpnd* newSsaVar = opndManager.createSsaVarOpnd(newVar);
+    if (old_inst->getOpcode() == Op_StVar) {
+        return instFactory.makeStVar(newSsaVar,
+                                     old_inst->getSrc(0)->asSsaOpnd());
+    } else {
+        uint32 num = old_inst->getNumSrcOperands();
+        Opnd** newOpnds = new(mm) Opnd* [num];
+        for (uint32 i = 0; i < num; i++) {
+            newOpnds[i] = old_inst->getSrc(i)->asSsaOpnd();
+        }
+        return (PhiInst*)instFactory.makePhi(newSsaVar, num, newOpnds);
+    }
+}
+
+void OSR::insertInst(Inst* inst, Inst* place){
+    if (inst->getOpcode() == Op_Phi || place->getOpcode() != Op_Phi) {
+        inst->insertAfter(place);
+    } else {
+        do {
+            place = (Inst*) place->next();
+        }
+        while ((place != 0) && (place->getOpcode() == Op_Phi));
+        if (place != 0) {
+            inst->insertBefore(place);
+        }
+    }
+}
+
+SsaOpnd* OSR::apply(Type* type, Opcode opcode, Operation op,
+                    SsaOpnd* opnd1, SsaOpnd* opnd2){
+    findLeadingOpnd(opnd2->getInst(), opnd2);
+    SsaOpnd* opnd2Leader = getLeadingOperand(opnd2);
+    if (opnd2 != 0) {
+        opnd2 = opnd2Leader;
+    }
+
+    opnd1 = (SsaOpnd*) DeadCodeEliminator::copyPropagate(opnd1);
+
+    if (Log::isEnabled()) {
+        Log::out() << "Applying: ";
+        opnd1->print(Log::out());
+        Log::out() << std::endl;
+        opnd2->print(Log::out());
+        Log::out() << std::endl;
+    }
+
+    Inst* newinst =
+        hashTable->lookup(op.encodeForHashing(), opnd1->getId(),
+                          opnd2->getId());
+    SsaOpnd* result = 0;
+    if (newinst) {
+        result = newinst->getDst()->asSsaOpnd();
+    } else {
+        if (getLeadingOperand(opnd1) && isLoopInvariant(opnd2)) {
+            result = reduce(type, opcode, op, opnd1, opnd2);
+        } else if (getLeadingOperand(opnd2) && isLoopInvariant(opnd1)) {
+            result = reduce(type, opcode, op, opnd2, opnd1);
+        } else {
+            OpndManager & opndManager = irManager.getOpndManager();
+            result = opndManager.createSsaTmpOpnd(type);
+            InstFactory & instFactory = irManager.getInstFactory();
+            opnd1 = makeTmp(opnd1, opnd1->getInst());
+            opnd2 = makeTmp(opnd2, opnd2->getInst());
+
+            Inst* newInst = instFactory.makeInst(opcode, op.getModifier(), type->tag,
+                                                 result, opnd1, opnd2);
+            Inst* instLoc = findInsertionPlace(opnd1, opnd2);
+            insertInst(newInst, instLoc);
+            writeLeadingOperand(result, 0);
+            hashTable->insert(op.encodeForHashing(), opnd1->getId(),
+                              opnd2->getId(), newInst);
+            writeLFTR(opnd1, op, opnd2, newInst->getDst()->asSsaOpnd());
+
+        }
+    }
+    return result;
+}
+
+Inst* OSR::findInsertionPlace(SsaOpnd* opnd2, SsaOpnd* opnd1){
+    Inst* opnd1inst = opnd1->getInst();
+    Inst* opnd2inst = opnd2->getInst();
+    Node* block1 = opnd1inst->getNode();
+    Node* block2 = opnd2inst->getNode();
+    Inst* place = 0;
+    if (block1 == block2) {
+        Inst* i = opnd1inst;
+        place = opnd2inst;
+        while (!i->isLabel()) {
+            if (i == opnd2inst) {
+                place = opnd1inst;
+                break;
+            }
+            i = i->getPrevInst();
+        }
+    } else if ((block1 != 0) && (dominators->dominates(block1, block2))) {
+        place = opnd2inst;
+    } else {
+        place = opnd1inst;
+    }
+    return place;
+}
+
+SsaTmpOpnd* OSR::makeTmp(SsaOpnd* inOpnd, Inst* place){
+    if (inOpnd->isSsaVarOpnd()) {
+        SsaVarOpnd* inSsaVarOpnd = inOpnd->asSsaVarOpnd();
+        Inst* inst = inSsaVarOpnd->getInst();
+        if (inst->getOpcode() == Op_StVar) {
+            SsaTmpOpnd* res = inst->getSrc(0)->asSsaTmpOpnd();
+            return res;
+        } else {
+            OpndManager& opndManager = irManager.getOpndManager();
+            InstFactory& instFactory = irManager.getInstFactory();
+
+            SsaTmpOpnd* res = opndManager.createSsaTmpOpnd(inOpnd->getType());
+            Inst* ldVarInst = instFactory.makeLdVar(res, inSsaVarOpnd);
+            Inst* where = chooseLocationForConvert(inst, place);
+            insertInst(ldVarInst, where);
+            writeLeadingOperand(res, getLeadingOperand(inOpnd));
+            return res;
+        }
+    } else {
+        return inOpnd->asSsaTmpOpnd();
+    }
+}
+
+SsaVarOpnd* OSR::makeVar(SsaOpnd* inOpnd, SsaVarOpnd* var, Inst* place){
+
+    if (inOpnd->isSsaTmpOpnd()) {
+        Inst* inst = inOpnd->getInst();
+        if (inst->getOpcode() == Op_LdVar) {
+            SsaVarOpnd* res = inst->getSrc(0)->asSsaVarOpnd();
+            return res;
+        } else {
+            OpndManager& opndManager = irManager.getOpndManager();
+            InstFactory& instFactory = irManager.getInstFactory();
+
+            SsaVarOpnd* res = opndManager.createSsaVarOpnd(var->getVar());
+            Inst* stVarInst = instFactory.makeStVar(res, inOpnd);
+
+            Inst* where = chooseLocationForConvert(inst, place);
+            insertInst(stVarInst, where);
+            writeLeadingOperand(res, getLeadingOperand(inOpnd));
+            return res;
+        }
+    } else {
+        return inOpnd->asSsaVarOpnd();
+    }
+}
+
+Inst* OSR::chooseLocationForConvert(Inst* inst, Inst* place){
+    Node* instNode = inst->getNode();
+    Node* placeNode = place->getNode();
+    Inst* where = 0;
+    if (instNode == placeNode) {
+        where = inst;
+    } else {
+        if (dominators->dominates(instNode, placeNode)) {
+            where = place;
+        } else {
+            where = inst;
+        }
+    }
+    return where;
+
+}
+
+VarOpnd* OSR::createOperand(Type* newType, VarOpnd * var, SsaOpnd * rc,
+                            Operation op){
+    OldInst g;
+    g.type = newType;
+    g.var = var;
+    g.ssa = rc;
+    Entry key(g, op);
+
+    VarOpnd* newVar = addedOpnds[key];
+
+    if (newVar == 0) {
+        OpndManager & opndManager = irManager.getOpndManager();
+        newVar = opndManager.createVarOpnd(newType, false);
+        addedOpnds[key] = newVar;
+    }
+    return newVar;
+}
+
+bool OSR::isLoopInvariant(SsaOpnd* name){
+
+    OSRInductionDetector::InstStack stack(this->mm);
+    LoopNode* mynode = this->loopTree->getLoopNode(name->getInst()->getNode(), false);
+    if (mynode == 0) {
+        return false;
+    }
+    OSROpndInfo nameinfo = OSRInductionDetector::processOpnd(loopTree, mynode, stack, name);
+    if (nameinfo.isHeaderFound()) {
+        writeLeadingOperand(name, (SsaOpnd*) nameinfo.getHeader());
+    }
+    if (nameinfo.isDOL() || nameinfo.isLDConst()) {
+        return true;
+    } else {
+        return false;
+    }
+
+}
+
+void OSR::writeLFTR(SsaOpnd* iv, Operation op, SsaOpnd* loop_inv,
+                    SsaOpnd* result){
+    OperationSsaOpnd tmp1(op, loop_inv);
+    LFTREntry tmp2(tmp1, result);
+    LFTRHashMap[iv] = tmp2;
+}
+
+void OSR::replaceLinearFuncTest(StlVector < Node* >&postOrderNodes){
+    StlVector < Node* >::reverse_iterator riter = postOrderNodes.rbegin(),
+        rend = postOrderNodes.rend();
+    for (; riter != rend; ++riter) {
+        Node* node = *riter;
+        Inst* labelInst = (Inst*) node->getLabelInst();
+
+        for (Inst* iter = (Inst*) labelInst->next();
+             (iter != 0 && iter != labelInst);
+             iter = (Inst*) iter->next()) {
+            if ((iter->getOpcode() == Op_Cmp)
+                || (iter->getOpcode() == Op_Branch))
+                performLFTR(iter);
+
+        }
+    }
+}
+
+void OSR::performLFTR(Inst* inst){
+    Opcode opcode = inst->getOpcode();
+    if (opcode == Op_Cmp || opcode == Op_Branch) {
+        uint32 num = inst->getNumSrcOperands();
+        if (2 == num) {
+            iv = 0;
+            rc = 0;
+            recordIVRC(inst);
+            if (iv && rc) {
+                SsaOpnd* reduced = 0;
+                SsaOpnd* newbound = 0;
+                SsaOpnd* src = getLeadingOperand(iv);
+                if (src == 0)
+                    return;
+                reduced = followEdges(iv);
+                newbound = applyEdges(iv, rc);
+                if ((reduced != src) && (newbound != rc)) {
+                    reduced = makeTmp(reduced, iv->getInst());
+                    newbound = makeTmp(newbound, rc->getInst());
+                    inst->setType(reduced->getType()->tag);
+
+                    if ((inst->getOpcode() == Op_Cmp
+                         || inst->getOpcode() == Op_Branch)
+                        && inst->getComparisonModifier() == Cmp_GT) {
+                        inst->setSrc(1, reduced);
+                        inst->setSrc(0, newbound);
+                    } else
+                        if ((inst->getOpcode() == Op_Cmp
+                             || inst->getOpcode() == Op_Branch)
+                            && inst->getComparisonModifier() == Cmp_GTE) {
+                        inst->setSrc(0, reduced);
+                        inst->setSrc(1, newbound);
+
+                    } else {
+                        inst->setSrc(1, reduced);
+                        inst->setSrc(0, newbound);
+                    }
+                }
+            }
+            iv = 0;
+            rc = 0;
+        }
+    }
+}
+
+SsaOpnd* OSR::followEdges(SsaOpnd* iv){
+    if (!LFTRHashMap.has(iv)) {
+        return iv;
+    } else {
+        LFTREntry & tmp2 = LFTRHashMap[iv];
+        SsaOpnd* reduced = tmp2.second;
+        return followEdges(reduced);
+    }
+}
+
+SsaOpnd* OSR::applyEdges(SsaOpnd* iv, SsaOpnd* bound){
+    SsaOpnd* res = 0;
+    if (!LFTRHashMap.has(iv)) {
+        res = bound;
+    } else {
+        LFTREntry & tmp2 = LFTRHashMap[iv];
+        Operation op = tmp2.first.first;
+        SsaOpnd* rc = tmp2.first.second;
+        SsaOpnd* reduced = tmp2.second;
+        Opcode opcode = op.getOpcode();
+        SsaOpnd* newRC = apply(reduced->getType(), opcode, op, bound, rc);
+        res = applyEdges(reduced, newRC);
+    }
+    return res;
+}
+}

Propchange: harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/osr.cpp
------------------------------------------------------------------------------
    svn:eol-style = native

Added: harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/osr.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/osr.h?rev=599804&view=auto
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/osr.h (added)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/osr.h Fri Nov 30 04:44:20 2007
@@ -0,0 +1,258 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one or more
+ *  contributor license agreements.  See the NOTICE file distributed with
+ *  this work for additional information regarding copyright ownership.
+ *  The ASF licenses this file to You under the Apache License, Version 2.0
+ *  (the "License"); you may not use this file except in compliance with
+ *  the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+
+#ifndef _OSR_H
+#define _OSR_H
+
+#include "LoopTree.h"
+#include <iostream>
+#include "Opcode.h"
+#include "ControlFlowGraph.h"
+#include "Stl.h"
+#include "Dominator.h"
+#include "CSEHash.h"
+#include "optpass.h"
+#include "Opnd.h"
+#include "irmanager.h"
+#include "constantfolder.h"
+#include <utility>
+
+namespace Jitrino {
+
+class IRManager;
+class MemoryManager;
+class InequalityGraph;
+class Node;
+class DominatorNode;
+class Dominator;
+class CFGNode;
+class Opnd;
+class CFGInst;
+class CSEHashTable;
+class Type;
+class LoopTree;
+class DominatorTree;
+
+enum iv_detection_flag {
+    CHOOSE_MAX_IN_BRANCH,
+    IGNORE_BRANCH
+};
+
+/* Class for holding info on operands.
+ * Similar to what loop_unroll uses internally.
+ * */
+
+class OSROpndInfo {
+public:
+    enum OpndType {
+        DEF_OUT_OF_LOOP,
+        LD_CONST,
+        COUNTER,
+        UNDEF
+    };
+
+    OSROpndInfo() {
+        type = DEF_OUT_OF_LOOP;
+        val = 0;
+        phiSplit = false;
+        header = 0;
+        header_found = false;
+        curOpnd = 0;
+    } 
+    OpndType getType() const {return type;} 
+
+    void setType(OpndType newType) {
+        assert(type != newType);
+        type = newType;
+        val = 0;
+    }
+
+    bool isCounter() const { return type == COUNTER;} 
+    bool isLDConst() const {return type == LD_CONST;} 
+    bool isDOL() const {return type == DEF_OUT_OF_LOOP;} 
+    bool isUndefined() const {return type == UNDEF;} 
+
+    uint32 getConst() const {
+        assert(getType() == LD_CONST);
+        return val;
+    }
+    void setConst(uint32 v) {
+        assert(getType() == LD_CONST);
+        val = v;
+    }
+
+    int getIncrement() const {
+        assert(getType() == COUNTER);
+        return val;
+    }
+    void setIncrement(int v) {
+        assert(getType() == COUNTER);
+        val = v;
+    }
+    bool isPhiSplit() const { return phiSplit;} 
+    void markPhiSplit() {
+        assert(isCounter());
+        phiSplit = true;
+    }
+    Opnd *getHeader() { return header;}
+    void setHeader(Opnd * h) {header = h;}
+    bool isHeaderFound() { return header_found;}
+    void setHeaderFound() {header_found = true;}
+    void setOpnd(Opnd * opnd) {curOpnd = opnd;}
+    Opnd *getOpnd() {return curOpnd;}
+
+    void print(std::ostream & out) {
+        out << "Pruint32ing status for: ";
+        curOpnd->print(Log::out());
+        out << "\n";
+        if (type == DEF_OUT_OF_LOOP)
+            out << "DOL";
+        else if (type == LD_CONST)
+            out << "LDC:" << getConst();
+        else if (type == COUNTER)
+            out << "CNT:" << getIncrement() << (phiSplit ? " splt" : "");
+        else
+            out << "UNDEF";
+        if (isHeaderFound()) {
+            out << "\n Header: ";
+            if (header != 0) {
+                header->print(Log::out());
+            } else {
+                Log::out() << "NULL";
+            }
+            out << "\n";
+        }
+    }
+
+private:
+    friend class OSRInductionDetector;
+    OpndType type;
+    int val;
+    bool phiSplit;
+    Opnd *header;
+    bool header_found;
+    Opnd *curOpnd;
+};
+
+class OSRInductionDetector {
+public:
+    typedef StlVector < Inst* >InstStack;
+    static OSROpndInfo processOpnd(LoopTree * tree,
+                   LoopNode* loopHead,
+                   InstStack& defStack,
+                   const Opnd* opnd,
+                   iv_detection_flag flag = IGNORE_BRANCH);
+    static bool inLoop(LoopTree * tree, Opnd * opnd);
+    static bool inExactLoop(LoopTree * tree, Opnd * opnd,
+                LoopNode * curnode);
+    static void writeHeaderToResult(OSROpndInfo & result,
+                    LoopTree * tree, OSROpndInfo info1,
+                    OSROpndInfo info2);
+};
+
+class OSR {
+public:
+    OSR(IRManager & irManager0, MemoryManager & memManager,
+    LoopTree * loop_Tree, DominatorTree * dtree);
+    void runPass();
+
+private:
+    SsaOpnd * iv;
+    SsaOpnd *rc;
+
+    struct OldInst {
+        Type* type;
+        VarOpnd* var;
+        SsaOpnd* ssa;
+
+        bool operator<(OldInst other) const {
+            return ((uint32) type + (int) var + (int) ssa) <
+            ((uint32) other.type + (int) other.var + (int) other.ssa);
+        }
+    };
+
+    typedef std::pair < OldInst, Operation > Entry;
+    IRManager& irManager;
+    MemoryManager& mm;
+    LoopTree* loopTree;
+    CSEHashTable* hashTable;
+    DominatorTree* dominators;
+    StlHashMap < SsaOpnd*, SsaOpnd* >leading_operands;
+
+    struct EntryComparison {
+        bool operator() (Entry x1, Entry x2) const {
+            return std::less < OldInst > () (x1.first, x2.first);
+        }
+    };
+
+    struct reduceCand {
+        reduceCand(SsaOpnd * dst, SsaOpnd * iv, SsaOpnd * rc) {
+            this->dst = dst;
+            this->iv = iv;
+            this->rc = rc;
+        } SsaOpnd *iv;
+        SsaOpnd *rc;
+        SsaOpnd *dst;
+    };
+
+    StlMap < Entry, VarOpnd*, EntryComparison > addedOpnds;
+    StlVector < reduceCand > cands;
+
+    typedef std::pair < Operation, SsaOpnd* >OperationSsaOpnd;
+    typedef std::pair < OperationSsaOpnd, SsaOpnd* >LFTREntry;
+    StlHashMap < SsaOpnd *, LFTREntry > LFTRHashMap;
+
+    void writeLeadingOperand(SsaOpnd* opnd, SsaOpnd* header);
+    SsaOpnd *getLeadingOperand(SsaOpnd* opnd);
+    void replace(SsaOpnd* opnd, SsaOpnd* iv, SsaOpnd* rc);
+    SsaOpnd *reduce(Type* type, Opcode opcode, Operation op,
+            SsaOpnd* iv, SsaOpnd* rc);
+    Inst *lookupReducedDefinition(Operation op, SsaOpnd* iv,
+                  SsaOpnd* rc);
+    Inst *copyInst(Type* type, Inst* oldDef, SsaOpnd* rc, Operation op);
+    void insertInst(Inst * toinsert, Inst * where);
+    SsaOpnd *apply(Type* type, Opcode opcode, Operation op,
+           SsaOpnd* opnd1, SsaOpnd * opnd2);
+    SsaVarOpnd *makeVar(SsaOpnd* opnd, SsaVarOpnd* var, Inst* place);
+    SsaTmpOpnd *makeTmp(SsaOpnd* opnd, Inst* place);
+    VarOpnd *createOperand(Type* newType, VarOpnd* var, SsaOpnd* rc,
+               Operation op);
+    bool isLoopInvariant(SsaOpnd * name);
+    void writeLFTR(SsaOpnd* iv, Operation op, SsaOpnd*  loop_inv,
+           SsaOpnd* result);
+    void replaceLinearFuncTest(StlVector < Node* >&postOrderNodes);
+    void performLFTR(Inst* inst);
+    SsaOpnd *followEdges(SsaOpnd* iv);
+    SsaOpnd *applyEdges(SsaOpnd* iv, SsaOpnd* bound);
+    void writeInst(Inst* inst);
+    Inst *insertNewDef(Type* type, SsaOpnd* iv, SsaOpnd* rc);
+    void replaceOperands(Type* type, Inst* newDef, SsaOpnd* iv,
+             SsaOpnd* rc, Opcode opcode, Operation op);
+    void findLeadingOpnd(Inst* newDef, SsaOpnd* opnd);
+    void replaceOperand(uint32 num, Inst* newDef, SsaOpnd* o,
+            Opnd* lead, Node* leadBlock, Type* type,
+            Opcode opcode, SsaOpnd* rc, Operation op);
+    Inst *findInsertionPlace(SsaOpnd* opnd2, SsaOpnd* opnd1);
+    void recordIVRC(Inst* inst);
+    Inst *chooseLocationForConvert(Inst* inst, Inst* place);
+    Inst *createNewVarInst(SsaOpnd* oldDst, Type* type,
+               Inst* oldDef, SsaOpnd* rc, Operation op);
+    bool isNoArrayInLoop(LoopNode* lnode, SsaOpnd* iv);
+};
+
+}
+#endif

Propchange: harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/osr.h
------------------------------------------------------------------------------
    svn:eol-style = native



Mime
View raw message