harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From mfur...@apache.org
Subject svn commit: r599448 - in /harmony/enhanced/drlvm/trunk/vm/jitrino: config/em64t/ config/ia32/ src/optimizer/
Date Thu, 29 Nov 2007 14:05:30 GMT
Author: mfursov
Date: Thu Nov 29 06:05:29 2007
New Revision: 599448

URL: http://svn.apache.org/viewvc?rev=599448&view=rev
Log:
Patch from HARMONY-2170 [drlvm][jit] New range check elimination optimization


Added:
    harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/LoopUtils.cpp   (with props)
    harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/LoopUtils.h   (with props)
    harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/dabce.cpp   (with props)
    harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/dabce.h   (with props)
Modified:
    harmony/enhanced/drlvm/trunk/vm/jitrino/config/em64t/server.emconf
    harmony/enhanced/drlvm/trunk/vm/jitrino/config/ia32/server.emconf
    harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/FastArrayFilling.cpp
    harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/memoryopt.cpp
    harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/optimizer.cpp
    harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/optimizer.h

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=599448&r1=599447&r2=599448&view=diff
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/config/em64t/server.emconf (original)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/config/em64t/server.emconf Thu Nov 29 06:05:29 2007
@@ -69,7 +69,8 @@
 -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,dessa,statprof,peel,ssa,hvn,simplify,dce,uce,lower,dce,uce,memopt,reassoc,dce,uce,hvn,dce,uce,classic_abcd,dce,uce,gcm,dessa,fastArrayFill,statprof
+-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.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
 -XX:jit.SD2_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=599448&r1=599447&r2=599448&view=diff
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/config/ia32/server.emconf (original)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/config/ia32/server.emconf Thu Nov 29 06:05:29 2007
@@ -71,7 +71,8 @@
 
 -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,so2-,hvn,simplify,dce,uce,escape,inline_helpers,purge,simplify,uce,dce,uce,dessa,statprof,peel,ssa,hvn,simplify,dce,uce,lower,dce,uce,statprof,unroll,ssa,simplify,dce,uce,memopt,reassoc,dce,uce,hvn,dce,uce,classic_abcd,dce,uce,gcm,dessa,fastArrayFill,statprof,markglobals
+-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.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
 -XX:jit.SD2_OPT.path.dce2=cg_dce

Modified: harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/FastArrayFilling.cpp
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/FastArrayFilling.cpp?rev=599448&r1=599447&r2=599448&view=diff
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/FastArrayFilling.cpp (original)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/FastArrayFilling.cpp Thu Nov 29 06:05:29 2007
@@ -90,6 +90,8 @@
     from HLO optimizations.
     */
 
+    const double FAIL_PROB = 10e-6; 
+        
     LoopTree * info = irManager.getLoopTree();
     if (!info->isValid()) {
         info->rebuild(false);
@@ -203,10 +205,14 @@
                             inst->getSrc(1) == tmpIndex) 
                         {
                             arrayBase = inst->getSrc(0);
-                            inst = inst->getPrevInst();
-                            //check Label aka beginning of BB
-                            if (inst->getOpcode() == Op_Label) {
-                                found = true;
+                            Inst* tmpInst = arrayBase->getInst();
+                            if (tmpInst->getOpcode() == Op_LdArrayBaseAddr) {
+                                arrayRef = tmpInst->getSrc(0); 
+                                inst = inst->getPrevInst();
+                                //check Label aka beginning of BB
+                                if (inst->getOpcode() == Op_Label) {
+                                    found = true;
+                                }
                             }
                         } 
                     } 
@@ -246,26 +252,6 @@
         }
 
         startNode = inEdge->getSourceNode();
-        inst = ((Inst *)startNode->getLastInst());
-        found = false;
-
-        //check StVar
-        if (inst->getOpcode() == Op_StVar && inst->getDst() == index) {
-            inst = inst->getPrevInst();
-            //check StInd
-            if (inst->getOpcode() == Op_TauStInd && inst->getSrc(0) == constValue && inst->getSrc(1) == arrayBase) {
-                inst = inst->getPrevInst();
-                //check LdBase
-                if (inst->getOpcode() == Op_LdArrayBaseAddr && inst->getDst() == arrayBase && inst->getPrevInst()->getOpcode() == Op_Label) {
-                    arrayRef = inst->getSrc(0);
-                    found = true;
-                }
-            }
-        }
-        if (!found) {
-            continue;
-        }
-
         startNode = startNode->getInEdges().front()->getSourceNode();
         inst = ((Inst *)startNode->getLastInst());
         found = false;
@@ -340,11 +326,12 @@
         ControlFlowGraph& fg = irManager.getFlowGraph();
         Node * preheader = fg.splitNodeAtInstruction(inst, true, false, irManager.getInstFactory().makeLabel());
         Inst * cmp = irManager.getInstFactory().makeBranch(Cmp_NE_Un, arrayBound->getType()->tag, arrayBound, fillBound, (LabelInst *)preheader->getFirstInst());
+        startNode->findTargetEdge(preheader)->setEdgeProb(FAIL_PROB);
         startNode->appendInst(cmp);
 
         //create a node with some instructions to prepare variables for loop
         Node * prepNode = fg.createBlockNode(irManager.getInstFactory().makeLabel());
-        fg.addEdge(startNode,prepNode);
+        fg.addEdge(startNode,prepNode, 1.0 - FAIL_PROB);
         
         OpndManager& opndManager = irManager.getOpndManager();
 

Added: harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/LoopUtils.cpp
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/LoopUtils.cpp?rev=599448&view=auto
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/LoopUtils.cpp (added)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/LoopUtils.cpp Thu Nov 29 06:05:29 2007
@@ -0,0 +1,267 @@
+/*
+ *  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.
+ */
+
+/**
+ * @author Intel
+ * @version $Revision: 1.1 $
+ *
+ */
+
+#include "LoopUtils.h"
+#include "Inst.h"
+
+namespace Jitrino {
+
+InvariantOpndLoopInfo* InductiveOpndLoopInfo::getStartValue() {
+    return startValue;
+}
+
+InvariantOpndLoopInfo* InductiveOpndLoopInfo::getEndValue() {
+    if (boundType != UNKNOWN_BOUND) {
+        return endValue;
+    }
+    findBoundInfo();
+    return endValue;
+}
+
+void InductiveOpndLoopInfo::setStartValue(InvariantOpndLoopInfo* start) {
+    startValue = start;
+}
+
+void InductiveOpndLoopInfo::setEndValue(InvariantOpndLoopInfo* end) {
+    endValue = end;
+}
+
+BoundType InductiveOpndLoopInfo::getBoundType() {
+    if (boundType != UNKNOWN_BOUND) {
+        return boundType;
+    }
+    findBoundInfo();
+    return boundType;
+}
+
+void InductiveOpndLoopInfo::findBoundInfo() {
+    BranchInst* branchInst = NULL;
+    OpndLoopInfo* opndInfo = NULL;
+    
+    const Nodes& loopNodes =  inductionDetector->loopNode->getNodesInLoop();
+    for (Nodes::const_iterator it = loopNodes.begin(), end = loopNodes.end(); it != end; it++) {
+        Node* node = *it;
+        branchInst = ((Inst*)node->getLastInst())->asBranchInst();
+        
+        if (branchInst == NULL) continue;
+        
+        SsaOpnd* leftOpnd = branchInst->getSrc(0)->asSsaOpnd();
+        SsaOpnd* rightOpnd = (branchInst->getNumSrcOperands() == 2)
+            ? branchInst->getSrc(1)->asSsaOpnd() : NULL;
+        Edge* trueEdge = node->getTrueEdge();
+        Edge* falseEdge = node->getFalseEdge();
+        bool isTrueExit = inductionDetector->loopNode->isLoopExit(trueEdge);
+        bool isFalseExit = inductionDetector->loopNode->isLoopExit(falseEdge);
+
+        // Check if branch matches.
+        if ((isTrueExit || isFalseExit) && (leftOpnd == mainOpnd || rightOpnd == mainOpnd)) {
+
+            ComparisonModifier compMod = branchInst->getComparisonModifier();
+            switch (compMod) {
+            case Cmp_Zero:
+                boundType = isTrueExit ? NE_BOUND : EQ_BOUND;
+                endValue = inductionDetector->zero;
+                break;
+            case Cmp_NonZero:
+                boundType = isTrueExit ? EQ_BOUND : NE_BOUND;
+                endValue = inductionDetector->zero;
+                break;
+            case Cmp_EQ: {
+                boundType = isTrueExit ? NE_BOUND : EQ_BOUND;
+                opndInfo = (leftOpnd == mainOpnd)
+                    ? inductionDetector->getOpndInfo(rightOpnd)
+                    : inductionDetector->getOpndInfo(leftOpnd);
+                endValue = (opndInfo != NULL) ? opndInfo->asInvarinat() : NULL;
+                break;
+            }
+            case Cmp_NE_Un:
+                boundType = isTrueExit ? EQ_BOUND : NE_BOUND;
+                opndInfo = (leftOpnd == mainOpnd)
+                    ? inductionDetector->getOpndInfo(rightOpnd)
+                    : inductionDetector->getOpndInfo(leftOpnd);
+                endValue = (opndInfo != NULL) ? opndInfo->asInvarinat() : NULL;
+                break;
+            case Cmp_GT:
+            case Cmp_GT_Un:
+                if (leftOpnd == mainOpnd) {
+                    // indVar >= invVar
+                    boundType = isTrueExit ? UPPER_EQ_BOUND : LOW_BOUND;
+                    opndInfo = inductionDetector->getOpndInfo(rightOpnd);
+                } else {
+                    // invVar >= indVar
+                    boundType = isTrueExit ? LOW_EQ_BOUND : UPPER_BOUND;
+                    opndInfo = inductionDetector->getOpndInfo(leftOpnd);
+                }
+                endValue = (opndInfo != NULL) ? opndInfo->asInvarinat() : NULL;
+                break;
+            case Cmp_GTE:
+            case Cmp_GTE_Un:
+                if (leftOpnd == mainOpnd) {
+                    // indVar >= invVar
+                    boundType = isTrueExit ? UPPER_BOUND : LOW_EQ_BOUND;
+                    opndInfo = inductionDetector->getOpndInfo(rightOpnd);
+                } else {
+                    // invVar >= indVar
+                    boundType = isTrueExit ? LOW_BOUND : UPPER_EQ_BOUND;
+                    opndInfo = inductionDetector->getOpndInfo(leftOpnd);
+                }
+                endValue = (opndInfo != NULL) ? opndInfo->asInvarinat() : NULL;
+                break;
+            default:;
+            };
+            return;
+        }
+    }    
+}
+
+InductionDetector::InductionDetector(MemoryManager& mm, LoopNode* loop):
+    memoryManager(mm), loopNode(loop), defStack(mm) {
+
+    zero = createConstOpnd(NULL, 0);
+    one = createConstOpnd(NULL, 1);
+};
+
+OpndLoopInfo* InductionDetector::processOpnd(SsaOpnd * opnd) {
+    OpndLoopInfo* resultOpnd = NULL;
+    Inst* defInst = opnd->getInst();
+
+    if (std::find(defStack.begin(), defStack.end(), defInst) != defStack.end()) {
+        return createInductiveOpnd(opnd, one, NULL, zero);
+    }
+
+    Node* defNode = defInst->getNode();
+    Opcode opcode = defInst->getOpcode();
+
+    if (opcode == Op_LdConstant) {
+        return createConstOpnd(opnd, defInst->asConstInst()->getValue().i4);
+    }
+
+    if (!loopNode->inLoop(defNode)) {
+        return createInvariantOpnd(opnd);
+    }
+
+    defStack.push_back(defInst);
+
+    switch (opcode) {
+    case Op_Phi: {
+        OpndLoopInfo* info1 = processOpnd(defInst->getSrc(0)->asSsaOpnd());
+        OpndLoopInfo* info2 = (info1 != NULL && defInst->getNumSrcOperands() == 2)
+            ? processOpnd(defInst->getSrc(1)->asSsaOpnd()) : NULL;
+        if (info2 != NULL) {
+            InductiveOpndLoopInfo* indOpnd = (info1->isInductive() && !info1->asInductive()->isPhiSplit) ?
+                info1->asInductive() : ((info2->isInductive() && !info2->asInductive()->isPhiSplit) ?
+                info2->asInductive() : NULL);
+            InvariantOpndLoopInfo* invOpnd = info1->isInvariant() ? info1->asInvarinat() :
+                (info2->isInvariant() ? info2->asInvarinat() : NULL); 
+            if (indOpnd != NULL && invOpnd != NULL) {
+                InductiveOpndLoopInfo* resOpnd = createInductiveOpnd(opnd, one,
+                    NULL, indOpnd->getStride());
+                resOpnd->startValue = invOpnd;
+                resOpnd->header = opnd;                
+                resOpnd->isPhiSplit = true;
+                resultOpnd = resOpnd;
+            }
+        }
+        break;
+    } 
+    case Op_Add:
+    case Op_Sub:
+    case Op_Mul: {
+        SsaOpnd *op1 = defInst->getSrc(0)->asSsaOpnd();
+        SsaOpnd *op2 = defInst->getSrc(1)->asSsaOpnd();
+        OpndLoopInfo* info1 = processOpnd(op1);
+        OpndLoopInfo* info2 = (info1 != NULL) ? processOpnd(op2) : NULL;
+
+        if (info2 != NULL) {
+            if (info1->isInvariant() && info2->isInvariant()) {
+                InvariantOpndLoopInfo* invOpnd1 = info1->asInvarinat();
+                InvariantOpndLoopInfo* invOpnd2 = info2->asInvarinat();
+                if (invOpnd1->isConstant() && invOpnd2->isConstant()) {
+                    int val1 = invOpnd1->asConstant()->getValue();
+                    int val2 = invOpnd2->asConstant()->getValue();
+                    if (opcode == Op_Add) {
+                        resultOpnd = createConstOpnd(opnd, val1 + val2);                        
+                    } else if (opcode == Op_Sub) {
+                        resultOpnd = createConstOpnd(opnd, val1 - val2);
+                    } else {
+                        assert(opcode == Op_Mul);
+                        resultOpnd = createConstOpnd(opnd, val1 * val2);
+                    }
+                } else {
+                    resultOpnd = createInvariantOpnd(opnd);
+                }
+            } else {
+                InductiveOpndLoopInfo* indOpnd = (info1->isInductive() && !info1->asInductive()->isPhiSplit) ?
+                    info1->asInductive() : ((info2->isInductive() && !info2->asInductive()->isPhiSplit) ?
+                    info2->asInductive() : NULL);
+                InvariantOpndLoopInfo* invOpnd = info1->isInvariant() ? info1->asInvarinat() :
+                    (info2->isInvariant() ? info2->asInvarinat() : NULL); 
+                
+                if (indOpnd != NULL && invOpnd != NULL) {
+                    InductiveOpndLoopInfo* resOpnd = NULL;
+                    if (opcode == Op_Add || opcode == Op_Sub) {
+                        resOpnd = createInductiveOpnd(opnd, one, indOpnd, invOpnd);
+                    } else {
+                        assert(opcode == Op_Mul);
+                        resOpnd = createInductiveOpnd(opnd, invOpnd, indOpnd, zero);
+                    }
+                    resOpnd->isPhiSplit = indOpnd->isPhiSplit;
+                    resOpnd->header = indOpnd->header;
+                    resultOpnd = resOpnd;
+                }
+            }
+        }
+        break;
+    }
+    case Op_StVar:
+    case Op_LdVar: {
+        resultOpnd = processOpnd(defInst->getSrc(0)->asSsaOpnd());
+        if (resultOpnd != NULL) {
+            resultOpnd->mainOpnd = opnd;
+        }
+        break;
+    }
+    case Op_TauArrayLen: {
+        resultOpnd = processOpnd(defInst->getSrc(0)->asSsaOpnd());
+        if (resultOpnd != NULL) {
+            resultOpnd->mainOpnd = opnd;
+        }
+        break;
+    }
+    default:;
+    };
+
+    defStack.pop_back();
+    return resultOpnd;
+}
+
+OpndLoopInfo* InductionDetector::getOpndInfo(SsaOpnd * opnd,
+                                             IVDetectionMode mode) {
+    // TODO: Current implementation doesn't support other modes.
+    assert(mode == IGNORE_BRANCH);
+    defStack.clear();
+    ivMode = mode;
+    return processOpnd(opnd);
+}
+
+} // namespace Jitrino

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

Added: harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/LoopUtils.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/LoopUtils.h?rev=599448&view=auto
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/LoopUtils.h (added)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/LoopUtils.h Thu Nov 29 06:05:29 2007
@@ -0,0 +1,259 @@
+/*
+ *  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.
+ */
+
+/**
+ * @author Intel
+ * @version $Revision: 1.1 $
+ *
+ */
+
+#ifndef _LOOP_UTILS_H_
+#define _LOOP_UTILS_H_
+
+#include "open/types.h"
+
+#include "Opnd.h"
+#include "LoopTree.h"
+
+namespace Jitrino {
+
+class OpndLoopInfo;
+class InductiveOpndLoopInfo;
+class InvariantOpndLoopInfo;
+class ConstOpndLoopInfo;
+class InductionDetector;
+
+enum IVDetectionMode {
+    CHOOSE_MAX_IN_BRANCH = 0,
+    IGNORE_BRANCH
+};
+
+enum BoundType {
+    UNKNOWN_BOUND = 0,
+    EQ_BOUND,
+    NE_BOUND,
+    LOW_BOUND,
+    LOW_EQ_BOUND,
+    UPPER_BOUND,   
+    UPPER_EQ_BOUND
+};
+
+class OpndLoopInfo {
+
+    friend class InductionDetector;
+    
+public:
+    virtual SsaOpnd* getOpnd() const { return mainOpnd; }
+    
+    virtual bool isInductive() const = 0;
+    virtual bool isInvariant() const = 0;
+    virtual bool isConstant() const = 0;
+
+    virtual InductiveOpndLoopInfo* asInductive() {
+        return isInductive() ? (InductiveOpndLoopInfo*)this : NULL; 
+    }
+    
+    virtual InvariantOpndLoopInfo* asInvarinat() {
+        return isInvariant() ? (InvariantOpndLoopInfo*)this : NULL;
+    }
+
+    virtual ConstOpndLoopInfo* asConstant() {
+        return isConstant() ? (ConstOpndLoopInfo*)this : NULL;
+    }
+    
+protected:
+    OpndLoopInfo(InductionDetector* id, SsaOpnd* opnd):
+         mainOpnd(opnd), inductionDetector(id) {};
+    
+    SsaOpnd*            mainOpnd;
+    InductionDetector*  inductionDetector;
+}; 
+
+class InductiveOpndLoopInfo : public OpndLoopInfo {
+
+    friend class InductionDetector;
+
+public:  
+    virtual bool isInductive() const { return true; }    
+    virtual bool isInvariant() const { return false; }
+    virtual bool isConstant() const { return false; }
+    
+    /**
+     * @returns scale info or null if scale operand is equal to 1.
+     * @see getBase
+     */
+    InvariantOpndLoopInfo* getScale() { return scale; } 
+
+    /**
+     * An induction variable is a variable that gets increased or decreased
+     * by a fixed amount on every iteration of a loop, or is a linear function
+     * of another induction variable. Thus it can be represented in general form
+     * as follows scale * base + stride, where scale and stride are loop invariants,
+     * base is loop induction variable.
+     *  
+     * @returns info about dependent induction variable or null if induction variable
+     * depends on itself.
+     */
+    InductiveOpndLoopInfo* getBase() { return base; }
+
+    /**
+     * @returns stride info or null if stride operand is equal to 0.
+     * @see getBase
+     */
+    InvariantOpndLoopInfo* getStride() { return stride; }
+
+    /**
+     * Any induction variable takes values between its bounds. Inductive variable is equal to
+     * its initial value at the first loop iteration.
+     *
+     * @returns info about initial value of the inductive variable or NULL if it cant be determined.
+     * @note if initial value isnt proven to be loop invariant NULL will be returned.
+     */
+    InvariantOpndLoopInfo* getStartValue();
+
+    /**
+     * Any induction variable takes values between its bounds. End value determines maximum
+     * possible range where induction variable may vary.
+     *
+     * @returns info about ending value of the inductive variable or NULL if it cant be determined.
+     * @note if ending value isnt proven to be loop invariant NULL will be returned.
+     */
+    InvariantOpndLoopInfo* getEndValue();
+
+    /**
+     * Sets up start value of inductive variable.
+     */
+    void setStartValue(InvariantOpndLoopInfo* start);
+
+    /**
+     * Sets up end value of inductive variable.
+     */
+    void setEndValue(InvariantOpndLoopInfo* end);
+
+    /**
+     * Inductive varible can be limited by different type of constraints:
+     * 1) var == endValue or var != endValue is STRICT_BOUND
+     * 2) var > endValue or var >= endValue is LOW_BOUND
+     * 3) var < endValue or var <= endValue is UPPER_BOUND
+     * 
+     * @returns type of the bound which limits inductive variable.
+     */
+    BoundType getBoundType();
+
+protected:
+    InductiveOpndLoopInfo(InductionDetector* id, SsaOpnd* opnd,
+                          InvariantOpndLoopInfo* scaleInfo,
+                          InductiveOpndLoopInfo* baseInfo,
+                          InvariantOpndLoopInfo* strideInfo):
+        OpndLoopInfo(id, opnd), scale(scaleInfo),
+        base(baseInfo), stride(strideInfo),
+        startValue(NULL), endValue(NULL), boundType(UNKNOWN_BOUND),
+        header(NULL), isPhiSplit(false) {
+        base = (base == NULL) ? this : base;         
+    }    
+
+private:   
+    void findBoundInfo();
+    
+    InvariantOpndLoopInfo*  scale;
+    InductiveOpndLoopInfo*  base;
+    InvariantOpndLoopInfo*  stride;
+    
+    InvariantOpndLoopInfo*  startValue;
+    InvariantOpndLoopInfo*  endValue;
+    BoundType               boundType;
+    
+    // implementation specific
+    SsaOpnd*    header;
+    bool        isPhiSplit;
+};
+
+class InvariantOpndLoopInfo : public OpndLoopInfo {
+
+    friend class InductionDetector;
+public:
+    
+    virtual bool isInductive() const { return false; }    
+    virtual bool isInvariant() const { return true; }
+    virtual bool isConstant() const { return false; }
+    
+protected:
+    InvariantOpndLoopInfo(InductionDetector* id, SsaOpnd* opnd): OpndLoopInfo(id, opnd) {}
+};
+
+class ConstOpndLoopInfo : public InvariantOpndLoopInfo {
+
+    friend class InductionDetector;
+public:    
+    virtual bool isConstant() const { return true; }
+
+    int32 getValue() const { return value; }
+
+protected:
+    ConstOpndLoopInfo(InductionDetector* id, SsaOpnd* opnd, int32 val):
+        InvariantOpndLoopInfo(id, opnd), value(val) {}
+
+private:
+    int32 value;
+};
+
+// TODO: Should be able to detect linear induction.
+class InductionDetector {
+
+    friend class InductiveOpndLoopInfo;
+    
+public:
+    static InductionDetector* create(MemoryManager& mm, LoopNode* loop) {
+        return new (mm) InductionDetector(mm, loop);
+    }
+    
+
+    InductiveOpndLoopInfo*
+    createInductiveOpnd(SsaOpnd* opnd,
+                        InvariantOpndLoopInfo* scaleInfo,
+                        InductiveOpndLoopInfo* baseInfo,
+                        InvariantOpndLoopInfo* strideInfo) {
+        return new (memoryManager)
+            InductiveOpndLoopInfo(this, opnd, scaleInfo, baseInfo, strideInfo);
+    }
+    
+    InvariantOpndLoopInfo* createInvariantOpnd(SsaOpnd* opnd) {
+        return new (memoryManager) InvariantOpndLoopInfo(this, opnd); 
+    }
+    
+    ConstOpndLoopInfo* createConstOpnd(SsaOpnd* opnd, int32 val) {
+        return new (memoryManager) ConstOpndLoopInfo(this, opnd, val);
+    }
+
+    OpndLoopInfo* getOpndInfo(SsaOpnd * opnd, IVDetectionMode mode = IGNORE_BRANCH);
+
+private:    
+    InductionDetector(MemoryManager& mm, LoopNode* loop);
+    OpndLoopInfo* processOpnd(SsaOpnd * opnd);
+    
+    MemoryManager&      memoryManager;
+    LoopNode*           loopNode;
+    
+    StlVector<Inst*>    defStack;
+    ConstOpndLoopInfo*  zero;
+    ConstOpndLoopInfo*  one;
+    IVDetectionMode     ivMode;
+};
+
+} // namesapce Jitrino
+
+#endif /*_LOOP_UTILS_H_*/

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

Added: harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/dabce.cpp
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/dabce.cpp?rev=599448&view=auto
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/dabce.cpp (added)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/dabce.cpp Thu Nov 29 06:05:29 2007
@@ -0,0 +1,804 @@
+/*
+ *  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.
+ */
+
+/**
+ * @author Evgueni Brevnov
+ * @version $Revision: 1.1 $
+ *
+ */
+
+#include <stdlib.h>
+
+#include "dabce.h"
+#include "optpass.h"
+#include "FlowGraph.h"
+
+namespace Jitrino {
+
+DEFINE_SESSION_ACTION(DynamicABCEPass, dabce, "Dynamic elimination of array bound checks")
+
+void DynamicABCEPass::_run(IRManager& irm) {
+    
+    DynamicABCE dynamicABCE(irm, this);
+    dynamicABCE.run();
+}
+
+DynamicABCE::DynamicABCE(IRManager& irm, SessionAction* sa) :
+    INC_SEQ_PROB(0.8), IN_BOUNDS_PROB(0.9), 
+   irManager(irm), memoryManager(irm.getMemoryManager()),
+   flowGraph(irm.getFlowGraph()), typeManager(irm.getTypeManager()),
+   instFactory(irm.getInstFactory()), opndManager (irm.getOpndManager()),   
+   arrayAccesses(memoryManager), inductionInfo(memoryManager),
+   eliminationInfo(memoryManager), monotonicityInfo(memoryManager),
+   loopsToOptimize(memoryManager), flags(*irm.getOptimizerFlags().dabceFlags) {
+    
+    // Build dominators.
+    OptPass::computeDominatorsAndLoops(irManager, true);
+    dce = new (memoryManager) DeadCodeEliminator(irManager);
+    sortByHotness = new (memoryManager) HotnessSorter;
+    loopTree = irm.getLoopTree();
+}
+
+void DynamicABCE::readFlags(Action* argSource, DynamicABCEFlags* flags) {
+    flags->sizeThreshold = argSource->getIntArg("dabce.sizeThreshold", 1);
+    flags->hotnessThreshold = argSource->getIntArg("dabce.hotnessThreshold", 1);       
+}
+
+void DynamicABCE::showFlags(std::ostream& os) {
+    os << "  Dynamic ABCE flags:" << std::endl;
+    os << "    dabce.sizeThreshold     - maximum number of nodes in loop" << std::endl;
+    os << "    dabce.hotnessThreshold  - minimum hotness of loop header " << std::endl;
+}
+
+void DynamicABCE::run() {
+    assert(loopTree->isValid());
+
+    // No loops, nothing to optimize.
+    if (!loopTree->hasLoops()) return;
+
+    LoopNode* topLevelLoop = (LoopNode*)loopTree->getRoot();
+    
+    // Find all loops.
+    findLoopsToOptimize(topLevelLoop);
+    
+    // Sort loops by hotness.
+    std::sort(loopsToOptimize.begin(), loopsToOptimize.end(), *sortByHotness);
+    
+    // Optimize found loops.
+    optimizeLoops();
+}
+
+void DynamicABCE::findLoopsToOptimize(LoopNode* topLevelLoop) {
+    LoopNode* innerLoop;
+    
+    if (topLevelLoop->getHeader() != NULL) {
+        loopsToOptimize.push_back(topLevelLoop->getHeader());
+    }
+    for (innerLoop = topLevelLoop->getChild(); innerLoop != NULL;
+            innerLoop = innerLoop->getSiblings()) {
+        findLoopsToOptimize(innerLoop);
+    }
+}
+
+void DynamicABCE::optimizeLoops() {
+    InductionDetector* inductionDetector = NULL;
+    Node* loopHeader = NULL;
+    StlVector<Node*>::iterator loopIt;
+    ArrayAccessInfo::iterator  accessIt;
+    
+    // Apply transformation from top level to inner most loops.
+    while (!loopsToOptimize.empty()) {     
+        clearAll();
+
+        loopIt = loopsToOptimize.begin();
+        loopHeader = *loopIt;
+        loopsToOptimize.erase(loopIt);
+        
+
+        optimizedLoop = loopTree->getLoopNode(loopHeader, false);
+        assert(optimizedLoop != NULL);
+
+        if (Log::isEnabled()) {
+            Log::out() << "Optimizing loop " << loopHeader->getId() << std::endl;
+    
+        }
+        
+        double relativeHotness = loopHeader->getExecCount() / flowGraph.getEntryNode()->getExecCount();
+        
+        if (relativeHotness < flags.hotnessThreshold) {
+            if (Log::isEnabled()) {
+                Log::out() << "FAILED: Loop is too cold.\n";
+            }
+            // No need to traverse other loops. They are even colder.
+            break;
+        }
+
+        if (optimizedLoop->getNodesInLoop().size() > relativeHotness * flags.sizeThreshold) {
+            if (Log::isEnabled()) {
+                Log::out() << "FAILED: Loop is too large.\n";
+            }
+            continue;
+        }
+               
+        // Find candidates for elimintation.
+        findArrayAccesses();
+        
+        // Check if we found at least one candidate for elimination.
+        if (Log::isEnabled() && arrayAccesses.empty()) {
+            Log::out() << "FAILED: No bound checks found.\n";
+        }
+        
+        inductionDetector = InductionDetector::create(memoryManager, optimizedLoop);
+
+        while (!arrayAccesses.empty()) {
+            accessIt = arrayAccesses.begin();            
+            const ArrayAccessTemplate& arrayAccess = **accessIt;
+            arrayAccesses.erase(accessIt);
+            
+            eliminateBoundsCheck(inductionDetector, arrayAccess);
+            
+            // Loop tree can be updated so reload related info.
+            if (optimizedLoop != loopTree->getLoopNode(loopHeader, false)) {
+                optimizedLoop = loopTree->getLoopNode(loopHeader, false);
+                inductionDetector = InductionDetector::create(memoryManager, optimizedLoop);
+                findArrayAccesses();
+            }
+        }
+    }    
+}
+
+bool DynamicABCE::eliminateBoundsCheck(InductionDetector* inductionDetector,
+                                       const ArrayAccessTemplate& arrayAccess) {
+    InductiveOpndLoopInfo* inductionInfo = NULL;
+    InductiveOpndLoopInfo* base = NULL;
+    InvariantOpndLoopInfo* scale = NULL;
+    InvariantOpndLoopInfo* stride = NULL;
+    InvariantOpndLoopInfo* start = NULL;
+    InvariantOpndLoopInfo* end = NULL;
+    IndexEliminationInfo* indexElimintaionInfo = NULL;
+    bool canReachBound = false;
+    bool result = false;
+    
+    indexElimintaionInfo = eliminationInfo[arrayAccess.array];
+    
+    if (indexElimintaionInfo == NULL) {
+        indexElimintaionInfo = new (memoryManager) IndexEliminationInfo(memoryManager);
+        eliminationInfo[arrayAccess.array] = indexElimintaionInfo;  
+    } else {
+        if (indexElimintaionInfo->has(arrayAccess.index)) {
+            // Constraints already generated. Just remove bounds check.
+            instFactory.makeTauSafe(arrayAccess.checkBoundsInst->getDst())->
+                insertAfter(arrayAccess.checkBoundsInst);
+            arrayAccess.checkBoundsInst->unlink();
+            result = true;
+            
+            if (Log::isEnabled()) {
+                Log::out() << "SUCCEED: Array bound check ";
+                arrayAccess.checkBoundsInst->print(Log::out());
+                Log::out() << " was removed.\n";
+            }
+        }
+        return result;
+    }
+    
+    // Check that array reference and array lengh defined out of the loop.
+    if (isDefInLoop(arrayAccess.array) || isDefInLoop(arrayAccess.arrayLen)) {
+        if (Log::isEnabled()) {
+            Log::out() << "FAILED: Array ";
+            arrayAccess.array->print(Log::out());
+            Log::out() << " is not loop invariant.\n";
+        }
+        goto done;
+    }
+    
+    // Create initial subgraph structure.
+    subGraph = new (memoryManager) SubGraph(memoryManager);
+    subGraph->setEntryNode(subGraph->createBlockNode(instFactory.makeLabel()));
+    subGraph->setExitNode(subGraph->createBlockNode(instFactory.makeLabel()));
+    subGraph->setSpecialExitNode(subGraph->createBlockNode(instFactory.makeLabel()));
+    subGraph->addEdge(subGraph->getEntryNode(), subGraph->getExitNode());
+    
+    
+    inductionInfo = getSimplifiedInduction(inductionDetector, arrayAccess);
+    
+    if (inductionInfo == NULL) {
+        if (Log::isEnabled()) {
+            Log::out() << "FAILED: Index ";
+            arrayAccess.index->print(Log::out());
+            Log::out() << " is not loop inductive variable.\n";
+        }
+        goto done;
+    }
+    
+    base = inductionInfo->getBase();
+    assert(base->getOpnd() == base->getBase()->getOpnd());
+    start = base->getStartValue();          
+    end = base->getEndValue();        
+    
+    // start and end values should be detected as loop invariants...
+    if (start == NULL || end == NULL) {
+        if (Log::isEnabled()) {
+            Log::out() << "FAILED: start/end value is not loop invariant.\n";
+        }
+        goto done;
+    }
+
+    // ... and should be defined out of the loop.
+    if (isDefInLoop(start->getOpnd()) || isDefInLoop(end->getOpnd())) {
+        if (Log::isEnabled()) {
+            Log::out() << "FAILED: start/end value has loop scope.\n";
+        }
+        goto done;        
+    }
+
+    // Promote start/end value from variable to temporary.
+    start = promoteVarToTmp(start, inductionDetector);
+    end   = promoteVarToTmp(end, inductionDetector);
+    base->setStartValue(start);
+    base->setEndValue(end);
+    
+    if (!isProperMonotonicity(base, start, end)) {
+        if (Log::isEnabled()) {
+            Log::out() << "FAILED: Wrong monotonicity.\n";
+        }
+        goto done;        
+    }
+    
+    if (inductionInfo != base) {
+        scale = inductionInfo->getScale();
+        stride = inductionInfo->getStride(); 
+    }
+    
+    canReachBound = base->getBoundType() == LOW_EQ_BOUND ||
+        base->getBoundType() == UPPER_EQ_BOUND; 
+    // Generate constraint for initial value.
+    genBoundConstraint(scale, start, stride, arrayAccess.arrayLen, true);
+    // Generate constraint for final value.
+    genBoundConstraint(scale, end, stride, arrayAccess.arrayLen, canReachBound);
+    // Link subGraph node.
+    linkSubGraph();
+    // Remove bounds check.    
+    instFactory.makeTauSafe(arrayAccess.checkBoundsInst->getDst())->
+        insertAfter(arrayAccess.checkBoundsInst);
+    arrayAccess.checkBoundsInst->unlink();
+
+    if (Log::isEnabled()) {
+        Log::out() << "SUCCEED: Array bound check ";
+        arrayAccess.checkBoundsInst->print(Log::out());
+        Log::out() << " was removed.\n";
+    }
+    
+    result = true;
+done:
+    (*indexElimintaionInfo)[arrayAccess.index] = result;
+    return result;
+}
+
+InvariantOpndLoopInfo*
+DynamicABCE::promoteVarToTmp(InvariantOpndLoopInfo* invOpnd,
+                             InductionDetector* inductionDetector) {
+    SsaOpnd* tmpOpnd = NULL;
+    SsaVarOpnd* varOpnd = NULL;
+    
+    if (!invOpnd->getOpnd()->isSsaVarOpnd()) {
+        return invOpnd;        
+    }
+    
+    varOpnd = invOpnd->getOpnd()->asSsaVarOpnd();
+    
+    if (varOpnd->getInst()->isStVar()) {
+        tmpOpnd = varOpnd->getInst()->getSrc(0)->asSsaTmpOpnd();
+    } else {
+        tmpOpnd = opndManager.createSsaTmpOpnd(varOpnd->getType());
+        subGraph->getEntryNode()->appendInst(instFactory.makeLdVar(tmpOpnd, varOpnd));        
+    }
+    
+    return inductionDetector->createInvariantOpnd(tmpOpnd);
+}
+
+InductiveOpndLoopInfo*
+DynamicABCE::getSimplifiedInduction(InductionDetector* inductionDetector,                                    
+                                    const ArrayAccessTemplate& arrayAccess) {
+    SsaOpnd* complexScale = NULL;
+    SsaOpnd* complexStride = NULL;
+    Modifier mulMod = Modifier(Overflow_None) | Modifier(Exception_Never);
+    Modifier addMod = mulMod | Modifier(Strict_No);
+    Node* subGraphEnter = NULL;
+    OpndLoopInfo* opndLoopInfo = NULL;
+    InvariantOpndLoopInfo* scale = NULL;
+    InductiveOpndLoopInfo* base = NULL;
+    InvariantOpndLoopInfo* stride = NULL;
+    InductiveOpndLoopInfo* indexInfo = NULL;
+    InductiveOpndLoopInfo* simplifiedInductionInfo = NULL;
+    
+
+    if (inductionInfo.has(arrayAccess.index)) {
+        return inductionInfo[arrayAccess.index];
+    }
+    
+    opndLoopInfo = inductionDetector->getOpndInfo(arrayAccess.index);    
+    
+    if (opndLoopInfo == NULL || !opndLoopInfo->isInductive()) {
+        goto done;
+    }
+
+    indexInfo = opndLoopInfo->asInductive();
+    scale = indexInfo->getScale();
+    stride = indexInfo->getStride();
+    subGraphEnter = subGraph->getEntryNode();    
+
+    // Scale and sride must be defined out of the loop.
+    if (isDefInLoop(scale->getOpnd()) || isDefInLoop(stride->getOpnd())) {
+        goto done;        
+    }
+    
+    // Check if its already simple induction.
+    if (indexInfo == indexInfo->getBase()) {
+        simplifiedInductionInfo = indexInfo;
+        goto done;
+    }
+
+    do {
+        SsaOpnd* tmpOpnd1 = NULL;
+        SsaOpnd* tmpOpnd2 = NULL;
+
+        scale = indexInfo->getScale();
+        base = indexInfo->getBase();
+        stride = indexInfo->getStride();
+        
+        assert(scale != NULL && base != NULL && stride != NULL);        
+
+        if (isDefInLoop(scale->getOpnd()) || isDefInLoop(stride->getOpnd())) {
+            goto done;        
+        }
+
+        if (complexStride == NULL) {
+            complexStride = stride->getOpnd();
+        } else if (!stride->isConstant() || stride->asConstant()->getValue() != 0) {
+            if (complexScale != NULL) {
+                tmpOpnd1 = opndManager.createSsaTmpOpnd(complexScale->getType());
+                subGraphEnter->appendInst(instFactory.makeMul(mulMod, tmpOpnd1, complexScale, stride->getOpnd()));
+            } else {
+                tmpOpnd1 = stride->getOpnd();
+            }
+            tmpOpnd2 = opndManager.createSsaTmpOpnd(complexStride->getType());
+            subGraphEnter->appendInst(instFactory.makeAdd(addMod, tmpOpnd2, complexStride, tmpOpnd1));
+            complexStride = tmpOpnd2;
+        }
+
+        if (complexScale == NULL) {
+            complexScale = scale->getOpnd();                
+        } else if (!scale->isConstant() || scale->asConstant()->getValue() != 1) {
+            tmpOpnd1 = opndManager.createSsaTmpOpnd(complexScale->getType());
+            subGraphEnter->appendInst(instFactory.makeMul(mulMod, tmpOpnd1, complexScale, scale->getOpnd()));
+            complexScale = tmpOpnd1;            
+        }
+        
+    } while (indexInfo != base &&
+        (indexInfo = inductionDetector->getOpndInfo(base->getOpnd())->asInductive()) != NULL);
+    
+    scale = complexScale ? inductionDetector->createInvariantOpnd(complexScale) : NULL;
+    stride = complexStride ? inductionDetector->createInvariantOpnd(complexStride) : NULL;
+    simplifiedInductionInfo =
+        inductionDetector->createInductiveOpnd(arrayAccess.index, scale, base, stride);
+ done:
+    inductionInfo[arrayAccess.index] = simplifiedInductionInfo;
+    return simplifiedInductionInfo;
+}
+
+bool DynamicABCE::isProperMonotonicity(InductiveOpndLoopInfo* base,
+                                       InvariantOpndLoopInfo* startValue,
+                                       InvariantOpndLoopInfo* endValue) {
+    Modifier aluMod;
+    Type* int32Type;
+    VarOpnd* fk;
+    Node* startNode = NULL;
+    Node* subGraphExit = NULL;
+    Node* increasingNode = NULL;
+    Node* decreasingNode = NULL;
+    InvariantOpndLoopInfo* scale;
+    InvariantOpndLoopInfo* stride;
+    bool isScaleEqualOne = false;
+    bool isStrideEqualZero = false;
+    bool result = false;
+    
+    assert(base->getOpnd() == base->getBase()->getOpnd());
+
+    if (monotonicityInfo.has(base->getOpnd())) {
+        return monotonicityInfo[base->getOpnd()];
+    }
+    
+    aluMod = Modifier(Overflow_None) | Modifier(Exception_Never) | Modifier(Strict_No);
+    int32Type = typeManager.getInt32Type();
+    subGraphExit = subGraph->getExitNode();
+
+    // Generate bound values check.
+    switch (base->getBoundType()) {
+    case LOW_BOUND:
+    case LOW_EQ_BOUND:
+        increasingNode = subGraph->getSpecialExitNode();
+        if (startValue->isConstant() && endValue->isConstant() &&
+            startValue->asConstant()->getValue() >= endValue->asConstant()->getValue()) {
+            decreasingNode = subGraphExit;
+        } else {
+            decreasingNode = subGraph->createBlockNode(instFactory.makeLabel());
+            subGraph->addEdge(decreasingNode, subGraph->getSpecialExitNode(), 0.1);
+            subGraph->addEdge(decreasingNode, subGraphExit, 0.9);
+            decreasingNode->appendInst(instFactory.makeBranch(Cmp_GTE,
+                int32Type->tag, startValue->getOpnd(), endValue->getOpnd(),
+                ((Inst*)subGraphExit->getLabelInst())->asLabelInst()));
+        }
+        break;
+    case UPPER_BOUND:
+    case UPPER_EQ_BOUND:
+        decreasingNode = subGraph->getSpecialExitNode();
+        if (startValue->isConstant() && endValue->isConstant() &&
+            startValue->asConstant()->getValue() <= endValue->asConstant()->getValue()) {
+            increasingNode = subGraphExit;
+        } else {
+            increasingNode = subGraph->createBlockNode(instFactory.makeLabel());
+            subGraph->addEdge(increasingNode, subGraph->getSpecialExitNode(), 0.1);
+            subGraph->addEdge(increasingNode, subGraphExit, 0.9);
+            increasingNode->appendInst(instFactory.makeBranch(Cmp_GTE,
+                int32Type->tag, endValue->getOpnd(), startValue->getOpnd(),
+                ((Inst*)subGraphExit->getLabelInst())->asLabelInst()));
+        }
+        break;
+    default:
+        goto done;
+    }
+    
+    // Generate monotonicity check.
+    fk = opndManager.createVarOpnd(int32Type, false);
+    scale = base->getScale();
+    stride = base->getStride();
+    
+    isScaleEqualOne = (scale->isConstant() && scale->asConstant()->getValue() == 1); 
+    // If scale is equal to one it doesn't affect direction of monotonicity. 
+    if (!isScaleEqualOne) {
+        startNode = subGraph->createBlockNode(instFactory.makeLabel());
+        Node* monCheckNode = flowGraph.createBlockNode(instFactory.makeLabel());
+        SsaOpnd* one = opndManager.createSsaTmpOpnd(int32Type);        
+        SsaOpnd* tk = opndManager.createSsaTmpOpnd(int32Type);
+        startNode->appendInst(instFactory.makeLdConst(one, 1));
+        startNode->appendInst(instFactory.makeSub(aluMod, tk, scale->getOpnd(), one));
+        
+        Node* trueNode = subGraph->createBlockNode(instFactory.makeLabel());
+        Node* falseNode = subGraph->createBlockNode(instFactory.makeLabel());
+
+        subGraph->addEdge(startNode, trueNode, 0.5);
+        subGraph->addEdge(trueNode, monCheckNode, 1.0);
+        subGraph->addEdge(startNode, falseNode, 0.5);
+        
+        startNode->appendInst(instFactory.makeBranch(Cmp_Zero, int32Type->tag,
+            tk, ((Inst*)trueNode->getLabelInst())->asLabelInst()));
+
+        // Generate true node instructions.
+        SsaOpnd* strideOpnd = stride->getOpnd();
+        if (strideOpnd == NULL) {
+            strideOpnd = opndManager.createSsaTmpOpnd(int32Type);
+            trueNode->appendInst(instFactory.makeLdConst(strideOpnd,
+                stride->asConstant()->getValue()));
+        }
+        trueNode->appendInst(instFactory.makeStVar(fk, strideOpnd));            
+        
+        // Generate false node instructions.
+        isStrideEqualZero = (stride->isConstant()&&
+            stride->asConstant()->getValue() == 0); 
+        SsaTmpOpnd* rk =  opndManager.createSsaTmpOpnd(int32Type);
+        if (!isStrideEqualZero) {
+            SsaTmpOpnd* tauSafe = opndManager.createSsaTmpOpnd(typeManager.getTauType());
+            SsaTmpOpnd* div = opndManager.createSsaTmpOpnd(typeManager.getFloatType());
+            falseNode->appendInst(instFactory.makeTauSafe(tauSafe));
+            falseNode->appendInst(instFactory.makeTauDiv(aluMod, div,
+                stride->getOpnd(), tk, tauSafe));
+            falseNode->appendInst(instFactory.makeAdd(aluMod, rk,
+                startValue->getOpnd(), div));
+        } else {
+            falseNode->appendInst(instFactory.makeCopy(rk, startValue->getOpnd()));
+        }
+
+        Node* subTrueNode = subGraph->createBlockNode(instFactory.makeLabel());
+        Node* subFalseNode = subGraph->createBlockNode(instFactory.makeLabel());        
+
+        subGraph->addEdge(falseNode, subTrueNode, 0.5);
+        subGraph->addEdge(falseNode, subFalseNode, 0.5);
+        subGraph->addEdge(subTrueNode, monCheckNode, 1.0);
+        subGraph->addEdge(subFalseNode, monCheckNode, 1.0);
+
+        falseNode->appendInst(instFactory.makeBranch(Cmp_GT, int32Type->tag,
+            tk, ((Inst*)subTrueNode->getLabelInst())->asLabelInst()));
+        
+        // Generate true subnode instructions.
+        trueNode->appendInst(instFactory.makeStVar(fk, rk));
+        
+        // Generate false subnode instructions.
+        SsaTmpOpnd* negrk =  opndManager.createSsaTmpOpnd(int32Type);
+        falseNode->appendInst(instFactory.makeNeg(negrk, rk));
+        falseNode->appendInst(instFactory.makeStVar(fk, negrk));
+        
+        // Generate final check.
+        SsaTmpOpnd* checkOpnd = opndManager.createSsaTmpOpnd(int32Type);
+        monCheckNode->appendInst(instFactory.makeLdVar(checkOpnd, fk));
+        monCheckNode->appendInst(instFactory.makeBranch(Cmp_GTE,
+            int32Type->tag, checkOpnd, ((Inst*)increasingNode->getLabelInst())->asLabelInst()));
+        // Link monotonicity check to bounds check nodes.
+        subGraph->addEdge(monCheckNode, increasingNode, INC_SEQ_PROB);
+        subGraph->addEdge(monCheckNode, decreasingNode, 1 - INC_SEQ_PROB);
+    } else {        
+        if (!stride->isConstant()) {
+            // Generate runtime check.
+            startNode = flowGraph.createBlockNode(instFactory.makeLabel());
+            startNode->appendInst(instFactory.makeBranch(Cmp_GTE, int32Type->tag,
+                stride->getOpnd(), ((Inst*)increasingNode->getLabelInst())->asLabelInst()));
+            subGraph->addEdge(startNode, increasingNode, INC_SEQ_PROB);
+            subGraph->addEdge(startNode, decreasingNode, 1 - INC_SEQ_PROB);
+        } else {
+            // Scale is equal to 1 here => only stride determines direction of monotonicity.
+            if (stride->asConstant()->getValue() >= 0) {
+                // That's not an inductive variable/
+                assert(stride->asConstant()->getValue() != 0);
+                // Increasing sequence.
+                if (base->getBoundType() == UPPER_BOUND || base->getBoundType() == UPPER_EQ_BOUND) {
+                    startNode = increasingNode;
+                } else {
+                    goto done;
+                }                
+            } else {
+                assert(stride->asConstant()->getValue() < 0);
+                // Decreasing sequence.
+                if (base->getBoundType() == LOW_BOUND || base->getBoundType() == LOW_EQ_BOUND) {
+                    startNode = decreasingNode;
+                } else {
+                    goto done;
+                }                
+            }
+        }        
+    }    
+    // Link monotonicity check.
+    if (startNode != NULL) {
+        // Remove link between enter & exit nodes.
+        Node* subGraphEnter = subGraph->getEntryNode();
+        Edge* edge = subGraphEnter->findEdge(true, subGraphExit); 
+        if (edge != NULL) {
+            subGraph->removeEdge(edge);
+        }
+        subGraph->addEdge(subGraphEnter, startNode);
+    }
+    result = true;
+done:
+    monotonicityInfo[base->getOpnd()] = result;
+    return result;
+}
+
+void DynamicABCE::genBoundConstraint(InvariantOpndLoopInfo* scale,
+                                     InvariantOpndLoopInfo* baseValue,
+                                     InvariantOpndLoopInfo* stride,
+                                     SsaOpnd* arrayLength,
+                                     bool canReachBound) {
+    Modifier aluMod;
+    ComparisonModifier comMod;
+    Type* int32Type = NULL;
+    SsaOpnd* mulRes = NULL;
+    SsaOpnd* addRes = NULL;
+    Node* newNode = NULL;
+    Node* subGraphExit = NULL;
+    
+    aluMod = Modifier(Overflow_None) | Modifier(Exception_Never) | Modifier(Strict_No);
+    int32Type = typeManager.getInt32Type();
+    subGraphExit = subGraph->getExitNode();
+    
+    newNode = subGraph->createBlockNode(instFactory.makeLabel());    
+
+    if (scale == NULL || (scale->isConstant() && scale->asConstant()->getValue() == 1)) {
+        mulRes = baseValue->getOpnd();
+    } else {
+        mulRes = opndManager.createSsaTmpOpnd(int32Type);
+        newNode->appendInst(instFactory.makeMul(aluMod, mulRes,
+            scale->getOpnd(), baseValue->getOpnd()));        
+    }
+    
+    if (stride == NULL || (stride->isConstant() && stride->asConstant()->getValue() == 0)) {
+        addRes = mulRes;
+    } else {
+        addRes = opndManager.createSsaTmpOpnd(int32Type);
+        newNode->appendInst(instFactory.makeAdd(aluMod, addRes,
+            mulRes, stride->getOpnd()));                
+    }
+    
+    comMod = canReachBound ? Cmp_GTE_Un : Cmp_GT_Un; 
+    newNode->appendInst(instFactory.makeBranch(comMod, int32Type->tag,
+        addRes, arrayLength, ((Inst*)subGraph->getSpecialExitNode()->getLabelInst())->asLabelInst()));
+
+    // Insert new node.
+    Edge* inEdge = findUnconditionalInEdge(subGraph->getExitNode());
+    subGraph->replaceEdgeTarget(inEdge, newNode, false);
+
+    subGraph->addEdge(newNode, subGraphExit, IN_BOUNDS_PROB);
+    subGraph->addEdge(newNode, subGraph->getSpecialExitNode(), 1 - IN_BOUNDS_PROB);
+}
+
+Node* DynamicABCE::getClonedLoop() {
+
+    if (clonedLoop != NULL) return clonedLoop;
+    
+    if (Log::isEnabled()) {
+        Log::out() << "Duplicating original loop...\n";
+    }
+    
+    uint32 maxNodeId = flowGraph.getMaxNodeId();
+    StlBitVector nodesInLoop(memoryManager, maxNodeId);
+    const Nodes& loopNodes = optimizedLoop->getNodesInLoop();
+    
+    for (Nodes::const_iterator it = loopNodes.begin(), end = loopNodes.end(); it != end; it++) {
+        Node* node = *it;
+        nodesInLoop.setBit(node->getId());
+    }
+
+    DefUseBuilder defUseBuilder(memoryManager);    
+    NodeRenameTable nodeRenameTable(memoryManager, loopNodes.size());
+    OpndRenameTable opndRenameTable(memoryManager, loopNodes.size(), true);
+    
+    defUseBuilder.initialize(flowGraph);
+    
+    clonedLoop = FlowGraph::duplicateRegion(irManager,
+        optimizedLoop->getHeader(), nodesInLoop, defUseBuilder, nodeRenameTable, opndRenameTable);
+     
+     return clonedLoop;    
+}
+
+void DynamicABCE::linkSubGraph() {
+    Node* tagetNode = NULL;
+    Edge* inEdge = NULL;
+    
+    if (Log::isEnabled()) {
+        Log::out() << "Inserting condition subgraph:\n";
+        FlowGraph::printHIR(Log::out(), *subGraph, irManager.getMethodDesc());
+    }
+    
+    inEdge = findUnconditionalInEdge(optimizedLoop->getHeader());    
+    tagetNode = inEdge->getTargetNode();
+    
+    // Insert subgraph.
+    flowGraph.spliceFlowGraphInline(inEdge, *subGraph);
+    
+    // Replace subgraph exit.
+    assert(subGraph->getExitNode()->hasOnlyOnePredEdge());
+    inEdge = subGraph->getExitNode()->getInEdges().front();
+    flowGraph.replaceEdgeTarget(inEdge, tagetNode, true);
+
+    // Cleanup phase.
+    dce->eliminateDeadCode(true);
+    dce->eliminateUnreachableCode();
+    OptPass::computeDominatorsAndLoops(irManager, true);
+
+    // Retarget all edges from specialExitNode to clonedLoop.
+    while (subGraph->getSpecialExitNode()->getInDegree() != 0) {
+        inEdge = subGraph->getSpecialExitNode()->getInEdges().front();
+        flowGraph.replaceEdgeTarget(inEdge, getClonedLoop(), true);
+    }
+    
+    /*
+    if (!irManager.isSsaUpdated()) {
+        // TODO: This would not be required if FlowGraph::duplicateRegion or
+        // OptPass::fixupSsa worked better.
+        OptPass::dessa(irManager);
+        OptPass::ssa(irManager);        
+    }
+    */
+    irManager.setSsaUpdated();
+    // Cleanup phase.
+    dce->eliminateDeadCode(true);
+    dce->eliminateUnreachableCode();
+    OptPass::computeDominatorsAndLoops(irManager, true);
+}
+
+Edge* DynamicABCE::findUnconditionalInEdge(Node* targetNode) {
+    Edge* inEdge = NULL;
+    const Edges& inEdges = targetNode->getInEdges();
+    for (Edges::const_iterator it = inEdges.begin(), end = inEdges.end(); it != end; it++) {
+        if (!optimizedLoop->isBackEdge(*it)) {
+            inEdge = *it;
+            break;
+        }
+    }
+    assert(inEdge != NULL);
+    return inEdge;
+}
+
+void DynamicABCE::findArrayAccesses() {
+    ArrayAccessTemplate* arrayAccess = NULL;
+    // Find all array accesses.
+    arrayAccesses.clear();
+    const Nodes& loopNodes = optimizedLoop->getNodesInLoop();
+    for (Nodes::const_iterator it = loopNodes.begin(), end = loopNodes.end(); it != end; ++it) {
+        Node* node = *it;
+        for (Inst* inst = (Inst*)node->getFirstInst(); inst != NULL; inst = inst->getNextInst()) {
+            switch (inst->getOpcode()) {
+            case Op_TauCheckBounds:
+            case Op_TauCheckLowerBound:
+            case Op_TauCheckUpperBound: {
+                arrayAccess = new (memoryManager) ArrayAccessTemplate();
+                fillTemplate(arrayAccess, inst);
+                
+                // Filter out not fully recognized patterns.
+                if (arrayAccess->array != NULL && arrayAccess->index != NULL) {
+                    arrayAccesses.push_back(arrayAccess);
+                } else {
+                    if (Log::isEnabled()) {
+                        Log::out() << "Skip not fully recognized pattern: ";
+                        arrayAccess->checkBoundsInst->print(Log::out());
+                        Log::out() << std::endl;
+                    }
+                }
+               break;
+            }
+            default:;
+            };
+        }
+    }
+}
+
+void DynamicABCE::fillTemplate(ArrayAccessTemplate* arrayAccess, Inst* checkInst) {
+    Inst* ldBaseInst = NULL;
+
+    assert(checkInst->getOpcode() == Op_TauCheckBounds);
+    
+    arrayAccess->checkBoundsInst = checkInst;
+    arrayAccess->index = checkInst->getSrc(1)->asSsaOpnd();
+    
+    SsaOpnd* lenOpnd = checkInst->getSrc(0)->asSsaOpnd();
+    Inst* lenInst = lenOpnd->getInst();
+    
+    if (lenInst->getOpcode() == Op_TauArrayLen) {
+        arrayAccess->array = lenInst->getSrc(0)->asSsaOpnd();
+    }    
+    arrayAccess->arrayLen = lenInst->getDst()->asSsaOpnd();
+
+    Node* node = checkInst->getNode()->getUnconditionalEdgeTarget();
+    for (Inst* inst = (Inst*)node->getFirstInst(); inst != NULL; inst = inst->getNextInst()) {
+        Opcode opcode = inst->getOpcode();
+        if (opcode == Op_LdArrayBaseAddr) {
+            if (arrayAccess->array == inst->getSrc(0)) {                
+                ldBaseInst = inst;
+            }
+        } else if (opcode == Op_AddScaledIndex &&
+            arrayAccess->index == inst->getSrc(1) && arrayAccess->array == NULL) {
+            assert(ldBaseInst == NULL);
+            ldBaseInst = inst->getSrc(0)->asSsaOpnd()->getInst();
+            assert(ldBaseInst->getOpcode() == Op_LdArrayBaseAddr);
+            arrayAccess->array = ldBaseInst->getSrc(0)->asSsaOpnd();
+            break;
+        }
+    }
+}
+
+bool DynamicABCE::isDefInLoop(SsaOpnd* opnd) {
+    return opnd != NULL && optimizedLoop->inLoop(opnd->getInst()->getNode());   
+}
+
+
+void DynamicABCE::clearAll() {
+    arrayAccesses.clear();
+    eliminationInfo.clear();
+    inductionInfo.clear();
+    optimizedLoop = NULL;
+    clonedLoop = NULL;
+    subGraph = NULL;
+}
+
+} // namespace Jitrino

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

Added: harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/dabce.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/dabce.h?rev=599448&view=auto
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/dabce.h (added)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/dabce.h Thu Nov 29 06:05:29 2007
@@ -0,0 +1,150 @@
+/*
+ *  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.
+ */
+
+/**
+ * @author Evgueni Brevnov
+ * @version $Revision: 1.1 $
+ *
+ */
+
+#ifndef _DYNAMICABCE_H_
+#define _DYNAMICABCE_H_
+
+#include "Stl.h"
+#include "VMInterface.h"
+#include "irmanager.h"
+#include "PMFAction.h"
+#include "Opnd.h"
+#include "Loop.h"
+#include "LoopTree.h"
+#include "LoopUtils.h"
+#include "deadcodeeliminator.h"
+#include "escapeanalyzer.h"
+
+namespace Jitrino {
+
+struct DynamicABCEFlags {
+    unsigned int    sizeThreshold;
+    double          hotnessThreshold;
+};
+
+// TODO: Index bounds check for nested loop sould be moved outside of the top level loop if possible.
+class DynamicABCE {
+
+    struct ArrayAccessTemplate;
+    struct ConstraintInfo;
+    
+    typedef StlList<ArrayAccessTemplate*> ArrayAccessInfo;
+    // Association bewteen array index and its bounds check info.   
+    typedef StlHashMap<SsaOpnd*, bool> IndexEliminationInfo;
+    // Association between array reference and its index info.
+    typedef StlHashMap<SsaOpnd*, IndexEliminationInfo*> ArrayEliminationInfo;
+    // Association between array index and its induction info.
+    typedef StlHashMap<SsaOpnd*, InductiveOpndLoopInfo*> IndexInductiveInfo;
+    // Association bewteen induction variable and its monotonicity.   
+    typedef StlHashMap<SsaOpnd*, bool> MonotonicityInfo;
+    
+    struct ArrayAccessTemplate {
+        
+        ArrayAccessTemplate(): array(NULL), arrayLen(NULL), index(NULL), checkBoundsInst(NULL) {}
+        SsaOpnd* array;
+        SsaOpnd* arrayLen;
+        SsaOpnd* index;
+        Inst* checkBoundsInst;
+    };
+    
+    struct HotnessSorter {
+         bool operator()(Node* const& lhs, Node* const& rhs) {
+              return lhs->getExecCount() >= rhs->getExecCount();
+         }
+    };
+    
+    class SubGraph: public ControlFlowGraph {
+    public:
+        SubGraph(MemoryManager& memoryManager): ControlFlowGraph(memoryManager) {}
+        Node* getSpecialExitNode() { return specialExit; }
+        void  setSpecialExitNode(Node* node) { specialExit = node; } 
+    private:
+        Node* specialExit;        
+    };
+    
+public:
+    DynamicABCE(IRManager& irm, SessionAction* sa = NULL);
+    
+    static void readFlags(Action* argSource, DynamicABCEFlags* flags);
+    static void showFlags(std::ostream& os);
+    
+    void run();
+
+private:
+    void optimizeLoops();
+    void findLoopsToOptimize(LoopNode* topLevelLoop);
+    bool eliminateBoundsCheck(InductionDetector* inductionDetector,
+                              const ArrayAccessTemplate& arrayAccess);    
+    InvariantOpndLoopInfo*
+    promoteVarToTmp(InvariantOpndLoopInfo* invOpnd,
+                    InductionDetector* inductionDetector);
+    
+    InductiveOpndLoopInfo*
+    getSimplifiedInduction(InductionDetector* inductionDetector,
+                           const ArrayAccessTemplate& arrayAccess);
+    bool isProperMonotonicity(InductiveOpndLoopInfo* base,
+                              InvariantOpndLoopInfo* startValue,
+                              InvariantOpndLoopInfo* endValue);
+    void genBoundConstraint(InvariantOpndLoopInfo* scale,
+                            InvariantOpndLoopInfo* baseValue,
+                            InvariantOpndLoopInfo* stride,
+                            SsaOpnd* arrayLength,
+                            bool canReachBound);
+    void fillTemplate(ArrayAccessTemplate* arrayAccesses, Inst* checkInst);    
+    Edge* findUnconditionalInEdge(Node* targetNode);
+    Node* getClonedLoop();
+    void findArrayAccesses();
+    void linkSubGraph();
+    bool isDefInLoop(SsaOpnd* opnd);
+    void clearAll();
+
+    const double INC_SEQ_PROB;
+    const double IN_BOUNDS_PROB;
+    
+    IRManager&          irManager;
+    MemoryManager&      memoryManager;
+    ControlFlowGraph&   flowGraph;
+    TypeManager&        typeManager;
+    InstFactory&        instFactory;
+    OpndManager&        opndManager;
+    
+    ArrayAccessInfo         arrayAccesses;
+    IndexInductiveInfo      inductionInfo;        
+    ArrayEliminationInfo    eliminationInfo;
+    MonotonicityInfo        monotonicityInfo;
+    StlVector<Node*>        loopsToOptimize;
+    DynamicABCEFlags&       flags;
+    
+    DeadCodeEliminator* dce;
+    HotnessSorter*      sortByHotness;        
+    LoopTree*           loopTree;
+    SubGraph*           subGraph;
+    // Original loop which get transformed.
+    LoopNode*           optimizedLoop;
+    // Unmodified clone of the original loop.
+    Node*               clonedLoop;
+};
+
+} // namespace Jitrino
+
+#endif /*_DYNAMICABCE_H_*/

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

Modified: harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/memoryopt.cpp
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/memoryopt.cpp?rev=599448&r1=599447&r2=599448&view=diff
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/memoryopt.cpp (original)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/memoryopt.cpp Thu Nov 29 06:05:29 2007
@@ -668,6 +668,7 @@
             case AddValueProfileValue:
             case StringCompareTo:
             case StringRegionMatches:
+            case FillArrayWithConst: 
             case ClassIsArray:
             case ClassGetAllocationHandle:
             case ClassGetTypeSize:

Modified: harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/optimizer.cpp
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/optimizer.cpp?rev=599448&r1=599447&r2=599448&view=diff
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/optimizer.cpp (original)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/optimizer.cpp Thu Nov 29 06:05:29 2007
@@ -44,6 +44,7 @@
 #include "devirtualizer.h"
 
 #include "abcd/abcd.h"
+#include "dabce.h"
 
 #include "Jitrino.h"
 #include "codelowerer.h"
@@ -190,11 +191,15 @@
     optimizerFlags.loopBuilderFlags = new (mm) LoopBuilderFlags;
     memset(optimizerFlags.loopBuilderFlags, sizeof(LoopBuilderFlags), 0);
 
+    optimizerFlags.dabceFlags = new (mm) DynamicABCEFlags;
+    memset(optimizerFlags.dabceFlags, sizeof(DynamicABCEFlags), 0);
+
     Abcd::readFlags(this, optimizerFlags.abcdFlags);
     GlobalCodeMotion::readFlags(this, optimizerFlags.gcmFlags);
     MemoryOpt::readFlags(this, optimizerFlags.memOptFlags);
     SyncOpt::readFlags(this, optimizerFlags.syncOptFlags);
     LoopBuilder::readFlags(this, optimizerFlags.loopBuilderFlags);
+    DynamicABCE::readFlags(this, optimizerFlags.dabceFlags);
 }
 
 
@@ -224,6 +229,7 @@
     MemoryOpt::showFlags(os);
     SyncOpt::showFlags(os);
     LoopBuilder::showFlags(os);
+    DynamicABCE::showFlags(os);
 }
 
 } //namespace Jitrino 

Modified: harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/optimizer.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/optimizer.h?rev=599448&r1=599447&r2=599448&view=diff
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/optimizer.h (original)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/optimizer.h Thu Nov 29 06:05:29 2007
@@ -33,6 +33,7 @@
 struct GcmFlags;
 struct SyncOptFlags;
 struct LoopBuilderFlags;
+struct DynamicABCEFlags;
 
 struct OptimizerFlags {
     
@@ -114,7 +115,8 @@
     GcmFlags*               gcmFlags;
     MemoptFlags*            memOptFlags;
     SyncOptFlags*           syncOptFlags;
-    LoopBuilderFlags*       loopBuilderFlags;    
+    LoopBuilderFlags*       loopBuilderFlags;
+    DynamicABCEFlags*       dabceFlags;
 };
 
 } //namespace Jitrino 



Mime
View raw message