harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From var...@apache.org
Subject svn commit: r544138 [2/3] - in /harmony/enhanced/drlvm/trunk: src/test/regression/H1788/ vm/jitrino/config/em64t/ vm/jitrino/config/ia32/ vm/jitrino/src/codegenerator/ia32/ vm/jitrino/src/optimizer/ vm/jitrino/src/optimizer/abcd/ vm/jitrino/src/shared/
Date Mon, 04 Jun 2007 12:12:04 GMT
Added: harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd.cpp
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd.cpp?view=auto&rev=544138
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd.cpp (added)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd.cpp Mon Jun  4 05:12:02 2007
@@ -0,0 +1,580 @@
+/*
+ *  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.
+ */
+
+#include "irmanager.h"
+#include "Dominator.h"
+#include "classic_abcd.h"
+#include "classic_abcd_solver.h"
+#include "opndmap.h"
+
+#include "Stl.h"
+#include "Log.h"
+#include "open/types.h"
+#include "Inst.h"
+#include "walkers.h"
+#include "PMFAction.h"
+#include "constantfolder.h"
+
+#include <assert.h>
+#include <iostream>
+#include <algorithm>
+
+namespace Jitrino {
+
+// eliminating Array Bounds Check on Demand
+DEFINE_SESSION_ACTION(CLASSIC_ABCDPass, classic_abcd, "Classic ABCD: eliminating Array Bounds Check on Demand");
+
+void
+CLASSIC_ABCDPass::_run(IRManager &irm) {
+    OptPass::splitCriticalEdges(irm);
+    OptPass::computeDominators(irm);
+    ClassicAbcd classic_abcd(this, irm, irm.getNestedMemoryManager(), 
+                             *irm.getDominatorTree());
+    classic_abcd.runPass();
+}
+//------------------------------------------------------------------------------
+
+class IOpndProxy : public IOpnd
+{
+public:
+    IOpndProxy(Opnd* opnd);
+
+    IOpndProxy(int32 c, uint32 id);
+
+    virtual void printName(std::ostream& os) const
+    {
+        if ( _opnd ) {
+            _opnd->print(os);
+        }else{
+            os << "_c" << getID() << "(const=" << getConstant() << ")";
+        }
+    }
+
+    Opnd* getOrg() const { assert(_opnd); return _opnd; }
+
+    static uint32 getProxyIdByOpnd(Opnd* opnd);
+private:
+    Opnd* _opnd;
+
+    /* ids of PiOpnd, SsaOpnd, VarOpnd may alias their IDs,
+     * encoding all in one ID with unaliasing
+     */
+    static const uint64 min_var_opnd = 0;
+    static const uint64 min_ssa_opnd = MAX_UINT32 / 4;
+    static const uint64 min_pi_opnd = (min_ssa_opnd) * 2;
+    static const uint64 min_const_opnd = (min_ssa_opnd) * 3;
+};
+//------------------------------------------------------------------------------
+
+bool inInt32(int64 c) {
+    return (int64)(int32)c == c;
+}
+
+bool inInt32Type(Type t) {
+    return (t.tag == Type::Int8) || 
+         (t.tag == Type::Int16) || 
+         (t.tag == Type::Int32);
+}
+
+IOpndProxy::IOpndProxy(Opnd* opnd) : 
+    IOpnd(0/* id */, 
+          opnd->getInst()->isPhi() /* is_phi */, 
+          ConstantFolder::isConstant(opnd) /* is_constant */),
+    _opnd(opnd)
+{
+    setID(getProxyIdByOpnd(_opnd));
+    if ( isConstant() ) {
+        ConstInst* c_inst = _opnd->getInst()->asConstInst();
+        assert(c_inst);
+        int64 value = c_inst->getValue().i8;
+        if ( inInt32Type(c_inst->getType()) ) {
+            value = c_inst->getValue().i4;
+        }else if ( c_inst->getType() != Type::Int64 ) {
+            setUnconstrained(true);
+            return;
+        }
+        if ( inInt32(value) ) {
+            setConstant((int32)value);
+        }else{
+            setUnconstrained(true);
+        }
+    }
+}
+//------------------------------------------------------------------------------
+
+IOpndProxy::IOpndProxy(int32 c, uint32 id) : 
+    IOpnd(0, false /* is_phi */, true /* is_constant */),
+    _opnd(NULL)
+{
+    setID(min_const_opnd + id);
+    setConstant(c);
+}
+
+uint32 IOpndProxy::getProxyIdByOpnd(Opnd* opnd)
+{
+    uint32 id = opnd->getId();
+    if ( opnd->isVarOpnd() ) {
+        id += min_var_opnd;
+    }else if ( opnd->isPiOpnd() ) { 
+        // note: PiOpnd inherits from SsaOpnd, check PiOpnd first
+        id += min_pi_opnd;
+    }else if ( opnd->isSsaOpnd() ) {
+        id += min_ssa_opnd;
+    }else {
+        assert(0);
+    }
+    return id;
+}
+//------------------------------------------------------------------------------
+
+class BuildInequalityGraphWalker {
+public:
+    BuildInequalityGraphWalker(InequalityGraph* igraph, bool isLower) :
+       _igraph(igraph), _isLower(isLower), _const_id_counter(1 /*reserve 0 for solver*/)
+    {}
+
+    void startNode(DominatorNode *domNode) {}
+    void applyToInst(Inst* i);
+    void finishNode(DominatorNode *domNode) {}
+
+    void enterScope() {}
+    void exitScope() {}
+private:
+    void updateDstForInst(Inst* inst);
+
+    // returns true if an edge to const opnd is actually added
+    bool addEdgeIfConstOpnd(IOpndProxy* dst, Opnd* const_src, Opnd* src, 
+                            bool negate_src);
+
+    void addAllSrcOpndsForPhi(Inst* inst);
+
+    // returns true if the edge is actually added
+    bool addDistance(IOpndProxy* dst, IOpndProxy* src, int64 constant, 
+                     bool negate);
+
+    // same as addDistance, but swap 'from' and 'to' if 'negate'
+    void addDistanceSwapNegate(IOpndProxy* to, IOpndProxy* from, int64 c, 
+                               bool negate);
+
+    // add edges to (or from) 'dst' induced by given bounds
+    void addPiEdgesForBounds(IOpndProxy* dst, 
+                             const PiBound& lb, const PiBound& ub);
+
+    void addPiEdgesWithOneBoundInf
+         (IOpndProxy* dst, bool lb_is_inf, const PiBound& non_inf_bound);
+
+    IOpndProxy* findProxy(Opnd* opnd);
+
+    IOpndProxy* addOldOrCreateOpnd(Opnd* opnd);
+
+    InequalityGraph* _igraph;
+    bool _isLower;
+    uint32 _const_id_counter;
+};
+//------------------------------------------------------------------------------
+ 
+IOpndProxy* BuildInequalityGraphWalker::findProxy(Opnd* opnd)
+{
+    assert(_igraph);
+    return (IOpndProxy*) _igraph->findOpnd(IOpndProxy::getProxyIdByOpnd(opnd));
+}
+//------------------------------------------------------------------------------
+
+void BuildInequalityGraphWalker::addAllSrcOpndsForPhi(Inst* inst)
+{
+    assert(inst->getOpcode() == Op_Phi);
+    for (uint32 j = 0; j < inst->getNumSrcOperands(); j++) {
+        IOpndProxy* proxy_src = addOldOrCreateOpnd(inst->getSrc(j));
+        addDistance(findProxy(inst->getDst()), proxy_src, 0, false /*negate*/);
+    }
+}
+//------------------------------------------------------------------------------
+
+void BuildInequalityGraphWalker::applyToInst(Inst* inst)
+{
+    assert(inst);
+
+    Type::Tag inst_type = inst->getType();
+    if ( !Type::isInteger(inst_type) && inst_type != Type::Boolean &&
+         inst_type != Type::Char ) {
+        // note: some operations of unsupported type can produce operands of
+        // supported (int) types, for example,
+        // inst-compare-two-unmanaged-pointers, we need these operands as
+        // unconstrained in the graph
+        Opnd* dst = inst->getDst();
+        if ( dst && !dst->isNull() &&
+                (dst->getType()->isInteger() ||
+                 dst->getType()->isBoolean() ) ) {
+            addOldOrCreateOpnd(dst)->setUnconstrained(true);
+        }
+        return;
+    }
+    if ( inst->isUnconditionalBranch() || inst->isConditionalBranch() || 
+         inst->isReturn() ) {
+        return;
+    }
+    IOpndProxy* proxy_dst;
+    Opcode opc = inst->getOpcode();
+    switch ( opc ) {
+        case Op_Phi:
+        {
+            proxy_dst = addOldOrCreateOpnd(inst->getDst());
+            addAllSrcOpndsForPhi(inst);
+        }
+            break;
+        case Op_Copy:
+        case Op_LdVar:
+        case Op_StVar:
+        {
+            proxy_dst = addOldOrCreateOpnd(inst->getDst());
+            addDistance(proxy_dst, findProxy(inst->getSrc(0)), 0, 
+                        false /* negate */);
+        }
+            break;
+        case Op_Add:
+        {
+            proxy_dst = addOldOrCreateOpnd(inst->getDst());
+            Opnd* src0 = inst->getSrc(0);
+            Opnd* src1 = inst->getSrc(1);
+            addEdgeIfConstOpnd(proxy_dst, src0, src1, false /* negate */) 
+            || addEdgeIfConstOpnd(proxy_dst, src1, src0, false /* negate */);
+        } 
+            break;
+        case Op_Sub:
+        {
+            proxy_dst = addOldOrCreateOpnd(inst->getDst());
+            addEdgeIfConstOpnd(proxy_dst, inst->getSrc(1), inst->getSrc(0),
+                               true /* negate */ );
+        } 
+            break;
+        case Op_TauPi:
+        {
+            proxy_dst = addOldOrCreateOpnd(inst->getDst());
+            IOpndProxy* src0 = findProxy(inst->getSrc(0));
+            addDistance(proxy_dst, src0, 0, false /* negate */);
+            const PiCondition* condition = inst->asTauPiInst()->getCond();
+            addPiEdgesForBounds(proxy_dst, 
+                                condition->getLb(), 
+                                condition->getUb());
+        }
+            break;
+        case Op_TauArrayLen:
+        case Op_LdConstant:
+            addOldOrCreateOpnd(inst->getDst());
+            break;
+        case Op_TauStInd: case Op_TauStElem: case Op_TauStField: 
+        case Op_TauStRef: case Op_TauStStatic:
+            break;
+        default:
+            addOldOrCreateOpnd(inst->getDst())->setUnconstrained(true);
+            break;
+    }
+}
+//------------------------------------------------------------------------------
+
+// returns true if the edge is actually added
+bool BuildInequalityGraphWalker::addDistance
+     (IOpndProxy* dst, IOpndProxy* src, int64 constant, bool negate)
+{
+    assert(dst && src);
+    // Note: is this an optimization?  It prevents adding a link from
+    // unconstrained operands.  This is always safe, and it shouldn't lose
+    // opportunity, but maybe we should discuss it to be sure?
+    if ( !src->isUnconstrained() ) {
+        if ( !inInt32(constant) ) {
+            return false;
+        }
+        if ( negate ) {
+            constant = (-1) * constant;
+        }
+        _igraph->addEdge(src->getID(), dst->getID(), constant);
+        return true;
+    }
+    return false;
+}
+//------------------------------------------------------------------------------
+
+void BuildInequalityGraphWalker::addDistanceSwapNegate
+     (IOpndProxy* to, IOpndProxy* from, int64 c, bool negate)
+{
+    addDistance(!negate ? to : from, !negate ? from : to, c, negate);
+}
+//------------------------------------------------------------------------------
+
+// returns true if an edge to const opnd is actually added
+bool BuildInequalityGraphWalker::addEdgeIfConstOpnd
+    (IOpndProxy* dst, Opnd* const_src, Opnd* src, bool negate_src)
+{
+    if ( ConstantFolder::isConstant(const_src) ) {
+        IOpnd* from = findProxy(const_src);
+        assert(from);
+        if ( !from->isUnconstrained() ) {
+            return addDistance(dst, findProxy(src), from->getConstant(), 
+                               negate_src);
+        }
+    }
+    return false;
+}
+//------------------------------------------------------------------------------
+
+/*
+ * pi (src0 \in [undef,A + c] -) dst
+ *      dst <= A + c <-> (dst - A) <= c
+ *      edge(from:A, to:dst, c)
+ *
+ * pi (src0 \in [A + c,undef] -) dst
+ *      (A + c) <= dst <-> (A - dst) <= -c
+ *      edge(from:dst, to:A, -c)
+ */
+void BuildInequalityGraphWalker::addPiEdgesForBounds
+     (IOpndProxy* dst, const PiBound& lb, const PiBound& ub)
+{
+    if ( _isLower && !lb.isUndefined() ) {
+        addPiEdgesWithOneBoundInf(dst, false, lb);
+    }
+    else if ( !_isLower && !ub.isUndefined() ) {
+        addPiEdgesWithOneBoundInf(dst, true, ub);
+    }
+}
+//------------------------------------------------------------------------------
+
+void BuildInequalityGraphWalker::addPiEdgesWithOneBoundInf
+     (IOpndProxy* dst, bool lb_is_inf, const PiBound& non_inf_bound)
+{
+    if ( non_inf_bound.isVarPlusConst()  ) {
+        Opnd* var = non_inf_bound.getVar().the_var;
+        addDistanceSwapNegate(dst /* to */, 
+                              findProxy(var) /* from */,
+                              non_inf_bound.getConst(), 
+                              false /* negate */);
+    } else if ( non_inf_bound.isConst() ) {
+        MemoryManager& mm = _igraph->getMemoryManager();
+        IOpndProxy* c_opnd = new (mm) 
+            IOpndProxy(non_inf_bound.getConst(), _const_id_counter++);
+        _igraph->addOpnd(c_opnd);
+        addDistanceSwapNegate(c_opnd /* to */, dst, 0, false /* negate */);
+    }
+}
+//------------------------------------------------------------------------------
+
+IOpndProxy* BuildInequalityGraphWalker::addOldOrCreateOpnd(Opnd* opnd)
+{
+    IOpndProxy* proxy = findProxy(opnd);
+    if ( !proxy ) {
+        MemoryManager& mm = _igraph->getMemoryManager();
+        proxy = new (mm) IOpndProxy(opnd);
+        _igraph->addOpnd(proxy);
+        if ( Log::isEnabled() ) {
+            Log::out() << "added opnd: ";
+            proxy->printFullName(Log::out());
+            Log::out() << std::endl;
+        }
+    }
+    return proxy;
+}
+
+class InequalityGraphPrinter : public PrintDotFile {
+public:
+    InequalityGraphPrinter(InequalityGraph& graph) : _graph(graph) {}
+    void printDotBody()
+    {
+        _graph.printDotBody(*os);
+    }
+private:
+    InequalityGraph& _graph;
+};
+//------------------------------------------------------------------------------
+
+void ClassicAbcd::runPass()
+{
+    static bool run_once = true;
+    if ( run_once && _runTests ) {
+        classic_abcd_test_main();
+        _runTests = false;
+        run_once = false;
+    }
+
+    MethodDesc& method_desc  = _irManager.getMethodDesc();
+    ControlFlowGraph& cfg    = _irManager.getFlowGraph();
+    TypeManager& typeManager = _irManager.getTypeManager();
+    OpndManager& opndManager = _irManager.getOpndManager();
+    InstFactory& instFactory = _irManager.getInstFactory();
+
+    if ( Log::isEnabled() ) {
+        FlowGraph::printDotFile(cfg, method_desc, "before_classic_abcd");
+        _domTree.printDotFile(method_desc, "before_classic_abcd.dom");
+        Log::out() << "ClassicAbcd pass started" << std::endl;
+    }
+
+    StlMap<Inst *, uint32> redundantChecks(_mm);
+
+    {
+        MemoryManager ineq_mm("ClassicAbcd::InequalityGraph");
+
+        InsertPi insertPi(ineq_mm, _domTree, _irManager, _useAliases, InsertPi::Upper);
+        insertPi.insertPi();
+
+        InequalityGraph igraph(ineq_mm);
+
+        BuildInequalityGraphWalker igraph_walker(&igraph, false /*lower*/);
+        typedef ScopedDomNodeInst2DomWalker<true, BuildInequalityGraphWalker>
+            IneqBuildDomWalker;
+        IneqBuildDomWalker dom_walker(igraph_walker);
+        DomTreeWalk<true, IneqBuildDomWalker>(_domTree, dom_walker, ineq_mm);
+
+        if ( Log::isEnabled() ) {
+            InequalityGraphPrinter printer(igraph);
+            printer.printDotFile(method_desc, "inequality.graph");
+        }
+
+        ClassicAbcdSolver solver(igraph, ineq_mm);
+
+        for (Nodes::const_iterator i = cfg.getNodes().begin(); i != cfg.getNodes().end(); ++i) {
+            Node *curr_node = *i;
+
+            for (Inst *curr_inst = (Inst*)curr_node->getFirstInst();
+                 curr_inst != NULL; curr_inst = curr_inst->getNextInst()) {
+
+                if (curr_inst->getOpcode() == Op_TauCheckBounds) {
+                    assert(curr_inst->getNumSrcOperands() == 2);
+                    Opnd *idxOp = curr_inst->getSrc(1);
+                    Opnd *boundsOp = curr_inst->getSrc(0);
+
+                    if (Log::isEnabled()) {
+                        Log::out() << "Trying to eliminate CheckBounds instruction ";
+                        curr_inst->print(Log::out());
+                        Log::out() << std::endl;
+                    }
+
+                    IOpnd *idxIOp = igraph.findOpnd(IOpndProxy::getProxyIdByOpnd(idxOp));
+                    IOpnd *boundsIOp = igraph.findOpnd(IOpndProxy::getProxyIdByOpnd(boundsOp));
+
+                    bool upper_res = solver.demandProve(boundsIOp, idxIOp, -1, true /*upper*/);
+                    if (upper_res) {
+                        redundantChecks[curr_inst] = 0x1 /*upper redundant*/;
+                        if (Log::isEnabled()) {
+                            Log::out() << "can eliminate upper bound check!\n";
+                        }
+                    }
+                }
+            }
+        }
+        insertPi.removePi();
+    }
+
+
+    {
+        MemoryManager ineq_mm("ClassicAbcd::InequalityGraph");
+
+        InsertPi insertPi(ineq_mm, _domTree, _irManager, _useAliases, InsertPi::Lower);
+        insertPi.insertPi();
+
+        InequalityGraph igraph(ineq_mm);
+
+        BuildInequalityGraphWalker igraph_walker(&igraph, true /*lower*/);
+        typedef ScopedDomNodeInst2DomWalker<true, BuildInequalityGraphWalker>
+            IneqBuildDomWalker;
+        IneqBuildDomWalker dom_walker(igraph_walker);
+        DomTreeWalk<true, IneqBuildDomWalker>(_domTree, dom_walker, ineq_mm);
+
+        IOpndProxy *zeroIOp = new (ineq_mm) IOpndProxy(0, 0 /*using reserved ID*/);
+        igraph.addOpnd(zeroIOp);
+        if ( Log::isEnabled() ) {
+            Log::out() << "added zero opnd for solving lower bound problem: ";
+            zeroIOp->printFullName(Log::out());
+            Log::out() << std::endl;
+        }
+
+        if ( Log::isEnabled() ) {
+            InequalityGraphPrinter printer(igraph);
+            printer.printDotFile(method_desc, "inequality.graph.inverted");
+        }
+
+        ClassicAbcdSolver solver(igraph, ineq_mm);
+
+        for (Nodes::const_iterator i = cfg.getNodes().begin(); i != cfg.getNodes().end(); ++i) {
+            Node *curr_node = *i;
+
+            for (Inst *curr_inst = (Inst*)curr_node->getFirstInst();
+                 curr_inst != NULL; curr_inst = curr_inst->getNextInst()) {
+
+                if (curr_inst->getOpcode() == Op_TauCheckBounds) {
+                    assert(curr_inst->getNumSrcOperands() == 2);
+                    Opnd *idxOp = curr_inst->getSrc(1);
+
+                    if (Log::isEnabled()) {
+                        Log::out() << "Trying to eliminate CheckBounds instruction ";
+                        curr_inst->print(Log::out());
+                        Log::out() << std::endl;
+                    }
+
+                    IOpnd *idxIOp = igraph.findOpnd(IOpndProxy::getProxyIdByOpnd(idxOp));
+
+                    bool lower_res = solver.demandProve(zeroIOp, idxIOp, 0, false /*lower*/);
+                    if (lower_res) {
+                        redundantChecks[curr_inst] |= 0x2 /*lower redundant*/;
+                        if (Log::isEnabled()) {
+                            Log::out() << "can eliminate lower bound check!\n";
+                        }
+                    }
+                }
+            }
+        }
+        insertPi.removePi();
+    }
+
+    for(StlMap<Inst *, uint32>::const_iterator i = redundantChecks.begin();
+        i != redundantChecks.end(); ++i) {
+        Inst *redundant_inst = i->first;
+        bool fully_redundant = i->second == 0x3;
+
+        if (fully_redundant) {
+            // should we check if another tau has already been placed in
+            // this block, and if so reuse it?  Also, should we be using
+            // taupoint or tauedge?
+            Opnd *tauOp = opndManager.createSsaTmpOpnd(typeManager.getTauType());
+            Inst* tau_point = instFactory.makeTauPoint(tauOp);
+            tau_point->insertBefore(redundant_inst);
+      
+            if (Log::isEnabled()) {
+                Log::out() << "Inserted taupoint inst ";
+                tau_point->print(Log::out());
+                Log::out() << " before inst ";
+                redundant_inst->print(Log::out());
+                Log::out() << std::endl;
+            }
+
+            Opnd* dstOp = redundant_inst->getDst();
+            redundant_inst->setDst(OpndManager::getNullOpnd());
+            Inst* copy = instFactory.makeCopy(dstOp, tauOp);
+            copy->insertBefore(redundant_inst);
+            FlowGraph::eliminateCheck(cfg, redundant_inst->getNode(), redundant_inst, false);
+            
+            if (Log::isEnabled()) {
+                Log::out() << "Replaced bound check with inst ";
+                copy->print(Log::out());
+                Log::out() << std::endl;
+            }
+        }
+    }
+
+    Log::out() << "ClassicAbcd pass finished" << std::endl;
+}
+//------------------------------------------------------------------------------
+
+} //namespace Jitrino 
+

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

Added: harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd.h?view=auto&rev=544138
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd.h (added)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd.h Mon Jun  4 05:12:02 2007
@@ -0,0 +1,58 @@
+/*
+ *  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 _CLASSIC_ABCD_H
+#define _CLASSIC_ABCD_H
+
+#include <iostream>
+#include "open/types.h"
+#include "Opcode.h"
+#include "FlowGraph.h"
+#include "optpass.h"
+#include "classic_abcd_solver.h"
+#include "insertpi.h"
+
+namespace Jitrino {
+
+class ClassicAbcd {
+public:    
+    ClassicAbcd(SessionAction* arg_source, IRManager &ir_manager, 
+                MemoryManager& mem_manager, DominatorTree& dom0) 
+    :
+        _irManager(ir_manager), 
+        _mm(mem_manager),
+        _domTree(dom0)
+    {
+        _runTests = arg_source->getBoolArg("run_tests", false);
+        _useAliases = arg_source->getBoolArg("use_aliases", true);
+    }
+
+    void runPass();
+private:
+    friend class BuildInequalityGraphWalker;
+
+    IRManager& _irManager;
+    MemoryManager& _mm;
+    DominatorTree& _domTree;
+
+    bool _runTests;
+    bool _useAliases;
+};
+
+} //namespace Jitrino 
+
+#endif /* _CLASSIC_ABCD_H */

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

Added: harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd_solver.cpp
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd_solver.cpp?view=auto&rev=544138
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd_solver.cpp (added)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd_solver.cpp Mon Jun  4 05:12:02 2007
@@ -0,0 +1,1083 @@
+/*
+ *  Copyright 2005-2006 The Apache Software Foundation or its licensors, as applicable.
+ *
+ *  Licensed 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.
+ */
+
+#include <fstream>
+#include "classic_abcd_solver.h"
+#include "Log.h"
+
+namespace Jitrino {
+
+void IOpnd::printName(std::ostream& os) const
+{
+    os << "o" << getID();
+}
+
+void IOpnd::printFullName(std::ostream& os) const
+{
+    printName(os);
+    assert((!isPhi()) || (!isConstant()));
+    if ( isPhi() ) {
+        os << "(phi)";
+    }
+    if ( isConstant() ) {
+        os << "(const=" << getConstant() << ")";
+    }
+}
+
+//------------------------------------------------------------------------------
+
+bool InequalityGraph::has_other_opnd_with_same_id(IdToOpndMap& map, IOpnd* opnd)
+{
+    IdToOpndMap::iterator it = map.find(opnd->getID());
+    if ( it != map.end() && it->second != opnd ) {
+        return true;
+    }
+    return false;
+}
+
+//------------------------------------------------------------------------------
+
+const InequalityGraph::EdgeList& InequalityGraph::getInEdges(IOpnd* opnd) const
+{ 
+    OpndEdgeMap::const_iterator it = _opnd_to_inedges_map.find(opnd->getID());
+
+    if ( it == _opnd_to_inedges_map.end() ) {
+        return _emptyList;
+    }
+    return it->second;
+}
+
+const InequalityGraph::EdgeList& InequalityGraph::getOutEdges(IOpnd* opnd) const
+{ 
+    OpndEdgeMap::const_iterator it = _opnd_to_outedges_map.find(opnd->getID());
+    if ( it == _opnd_to_outedges_map.end() ) {
+        return _emptyList;
+    }
+    return it->second;
+}
+
+void InequalityGraph::addEdgeToIdMap
+     (OpndEdgeMap& mp, uint32 id, IneqEdge* edge)
+{
+    OpndEdgeMap::iterator it = mp.find(id);
+    if ( it == mp.end() ) {
+        StlList<IneqEdge*> * new_list = new (_mem_mgr) StlList<IneqEdge*>(_mem_mgr);
+        new_list->push_back(edge);
+        mp.insert(std::make_pair(id, *new_list));
+    }else{
+        it->second.push_back(edge);
+    }
+}
+
+void InequalityGraph::addEdge(IOpnd* from, IOpnd* to, int32 distance)
+{
+    assert(!has_other_opnd_with_same_id(_id_to_opnd_map, from));
+    assert(!has_other_opnd_with_same_id(_id_to_opnd_map, to));
+
+    _id_to_opnd_map[from->getID()] = from;
+    _id_to_opnd_map[to->getID()] = to;
+
+    IneqEdge* p_edge = new (_mem_mgr) IneqEdge(from, to, distance);
+    _edges.push_back(p_edge);
+
+    addEdgeToIdMap(_opnd_to_outedges_map, from->getID(), p_edge);
+    addEdgeToIdMap(_opnd_to_inedges_map, to->getID(), p_edge);
+}
+
+void InequalityGraph::addEdge(uint32 id_from, uint32 id_to, int32 distance)
+{
+    IOpnd *from, *to;
+    IdToOpndMap::iterator it;
+
+    it = _id_to_opnd_map.find(id_from);
+    assert(it != _id_to_opnd_map.end());
+    from = it->second;
+    it = _id_to_opnd_map.find(id_to);
+    assert(it != _id_to_opnd_map.end());
+    to = it->second;
+
+    addEdge(from, to, distance);
+}
+
+void InequalityGraph::addOpnd(IOpnd* opnd)
+{
+    assert(!has_other_opnd_with_same_id(_id_to_opnd_map, opnd));
+    _id_to_opnd_map[opnd->getID()] = opnd;
+}
+
+void InequalityGraph::printDotHeader(std::ostream& os) const
+{
+    os << "digraph dotgraph {" << std::endl;
+    os << "node [shape=record,fontname=\"Courier\",fontsize=9];" << std::endl;
+    os << "label=\"Inequality Graph\";" << std::endl;
+}
+
+/*
+ * example:
+ *
+ * digraph dotgraph {
+ * node [shape=record,fontname="Courier",fontsize=9];
+ * label="Label";
+ * ENTRY [label="{ENTRY}"]
+ * L1 [label="{L1}"]
+ * L2 [label="{L2}"]
+ * ENTRY -> L1 [label="55"];
+ * L1 -> L2;
+ * L2 -> ENTRY;
+ * }
+ */
+void InequalityGraph::printDotFile(std::ostream& os) const
+{
+    printDotHeader(os);
+    printDotBody(os);
+    printDotEnd(os);
+}
+
+void InequalityGraph::printDotEnd(std::ostream& os) const
+{
+    os << "}" << std::endl;
+}
+
+void InequalityGraph::printDotBody(std::ostream& os) const
+{
+    IdToOpndMap::const_iterator it = _id_to_opnd_map.begin(), 
+        last = _id_to_opnd_map.end();
+    for (; it != last; it++ ) {
+        IOpnd* opnd = it->second;
+        os << "\""; opnd->printName(os); os << "\"";
+        os << " [label=\"{"; 
+        opnd->printFullName(os);
+        os << "}\"];" << std::endl;
+    }
+    for (it = _id_to_opnd_map.begin(); it != last; it++ ) {
+        IOpnd* from_opnd = it->second;
+        const EdgeList& out_edges_list = getOutEdges(from_opnd);
+        EdgeList::const_iterator out_iter = out_edges_list.begin(), 
+            out_last = out_edges_list.end();
+        for (; out_iter != out_last; out_iter++) {
+            IOpnd* to_opnd = (*out_iter)->getDst();
+            os << "\""; from_opnd->printName(os); os << "\"";
+            os << " -> ";
+            os << "\""; to_opnd->printName(os); os << "\"";
+            os << " [label=\"" << (*out_iter)->getLength() << "\"];" 
+               << std::endl;
+        }
+    }
+}
+
+IOpnd* InequalityGraph::findOpnd(uint32 id) const
+{
+    IdToOpndMap::const_iterator it = _id_to_opnd_map.find(id);
+    if ( it == _id_to_opnd_map.end() ) {
+        return NULL;
+    }
+    return it->second;
+}
+//------------------------------------------------------------------------------
+
+TrueReducedFalseChart* BoundAllocator::create_empty_TRFChart()
+{
+    return new (_mem_mgr) TrueReducedFalseChart(this);
+}
+
+Bound* BoundAllocator::newBound(int32 val, const BoundState& bs)
+{
+    return new (_mem_mgr) Bound(val, bs);
+}
+
+Bound* BoundAllocator::create_inc1(Bound* bound)
+{
+    return newBound(bound->isUpper() ? bound->_bound + 1 : bound->_bound - 1, 
+                    bound->getBoundState());
+}
+
+Bound* BoundAllocator::create_dec1(Bound* bound)
+{
+    return newBound(bound->isUpper() ? bound->_bound - 1 :  bound->_bound + 1, 
+                    bound->getBoundState());
+}
+
+Bound* BoundAllocator::create_dec_const(Bound* bound, int32 cnst)
+{
+    return newBound(bound->_bound - cnst, bound->getBoundState());
+}
+
+//------------------------------------------------------------------------------
+
+void Bound::printFullName(std::ostream& os) 
+{ 
+    os << "Bound(";
+    if ( isUpper() ) {
+        os << "upper";
+    }else{
+        os << "lower";
+    }
+    os << ", " << _bound << ")"; 
+}
+
+bool Bound::leq(Bound* bound1, Bound* bound2) 
+{ 
+    assert(bound1 && bound2);
+    assert(bound1->isUpper() == bound2->isUpper());
+    return Bound::int32_leq(bound1->_bound, bound2);
+}
+
+bool Bound::eq(Bound* bound1, Bound* bound2)
+{
+    assert(!bound1 || !bound2 || bound1->isUpper() == bound2->isUpper());
+    return bound1 && bound2 && 
+        Bound::leq(bound1, bound2) && Bound::leq(bound2, bound1);
+}
+
+bool Bound::leq_int32(Bound* bound1, int32 value) 
+{ 
+    assert(bound1);
+    return bound1->isUpper() ? 
+        bound1->_bound <= value : 
+        bound1->_bound >= value;
+}
+
+bool Bound::int32_leq(int32 value, Bound* bound1) 
+{ 
+    assert(bound1);
+    return bound1->isUpper() ? 
+        value <= bound1->_bound :
+        value >= bound1->_bound;
+}
+
+// returns (dst_val - src_val <= bound)
+bool Bound::const_distance_leq(int32 src_val, int32 dst_val, Bound* bound)
+{
+    assert(bound);
+    int32 distance = dst_val - src_val;
+    assert(distance + src_val == dst_val);
+    return Bound::int32_leq(distance, bound);
+}
+
+//------------------------------------------------------------------------------
+
+ProveResult meetBest(ProveResult res1, ProveResult res2)
+{
+    return (ProveResult) std::max(res1, res2);
+}
+
+ProveResult meetWorst(ProveResult res1, ProveResult res2)
+{
+    return (ProveResult) std::min(res1, res2);
+}
+
+void print_result(ProveResult r, std::ostream& os)
+{
+    switch (r) {
+        case True : os << "True"; break;
+        case Reduced : os << "Reduced"; break;
+        case False : os << "False"; break;
+    }
+}
+
+//------------------------------------------------------------------------------
+
+void TrueReducedFalseChart::addFalse(Bound* f_bound)
+{
+    if ( !_max_false || Bound::leq(_max_false, f_bound) ) {
+        _max_false = f_bound;
+    }
+
+    /* make none of 3 bounds equal */
+    if ( Bound::eq(_max_false, _min_reduced) ) {
+        _min_reduced = _bound_alloc->create_inc1(_min_reduced);
+    }
+    if ( Bound::eq(_max_false, _min_true) ) {
+        _min_true = _bound_alloc->create_inc1(_min_true);
+    }
+    if ( Bound::eq(_min_reduced, _min_true) ) {
+        _min_reduced = NULL;
+    }
+
+    clearRedundantReduced();
+    assert(!_min_true || Bound::leq(_max_false, _min_true));
+    assert(!_min_reduced || Bound::leq(_max_false, _min_reduced));
+}
+
+void TrueReducedFalseChart::addReduced(Bound* r_bound)
+{
+    if ( !_min_reduced || Bound::leq(r_bound, _min_reduced) ) {
+        _min_reduced = r_bound;
+    }
+
+    /* make none of 3 bounds equal */
+    if ( Bound::eq(_min_reduced, _min_true) ) {
+        _min_true = _bound_alloc->create_inc1(_min_true);
+    }
+    if ( Bound::eq(_min_reduced, _max_false) ) {
+        _max_false = _bound_alloc->create_dec1(_max_false);
+    }
+
+    assert(!_min_true || Bound::leq(_min_reduced, _min_true));
+    assert(!_max_false || Bound::leq(_max_false, _min_reduced));
+}
+
+void TrueReducedFalseChart::addTrue(Bound* t_bound)
+{
+    if ( !_min_true || Bound::leq(t_bound, _min_true) ) {
+        _min_true = t_bound;
+    }
+
+    /* make none of 3 bounds equal */
+    if ( Bound::eq(_min_true, _min_reduced) ) {
+        _min_reduced = _bound_alloc->create_dec1(_min_reduced);
+    }
+    if ( Bound::eq(_min_true, _max_false) ) {
+        _max_false = _bound_alloc->create_dec1(_max_false);
+    }
+    if ( Bound::eq(_max_false, _min_reduced) ) {
+        _min_reduced = NULL;
+    }
+
+    clearRedundantReduced();
+    assert(!_min_reduced || Bound::leq(_min_reduced, _min_true));
+    assert(!_max_false || !_min_reduced || 
+           Bound::leq(_max_false, _min_reduced));
+}
+
+bool TrueReducedFalseChart::hasBoundResult(Bound* bound) const
+{
+    assert(!Bound::eq(_min_true, _max_false));
+    assert(!Bound::eq(_min_true, _min_reduced));
+    assert(!Bound::eq(_max_false, _min_reduced));
+
+    if ( (_max_false && Bound::leq(bound, _max_false)) ||
+         (_min_reduced && Bound::leq(_min_reduced, bound)) ||
+         (_min_true && Bound::leq(_min_true, bound)) ) {
+        return true;
+    }
+    return false;
+}
+
+ProveResult TrueReducedFalseChart::getBoundResult(Bound* bound) const
+{
+    assert(hasBoundResult(bound));
+    if ( (_max_false && Bound::leq(bound, _max_false)) ) {
+        return False;
+    }
+    if ( _min_true && Bound::leq(_min_true, bound) ) {
+        return True;
+    }
+    if ( _min_reduced && Bound::leq(_min_reduced, bound) ) {
+        return Reduced;
+    }
+    assert(0);
+    return False;
+}
+
+void TrueReducedFalseChart::print(std::ostream& os) const
+{
+    os << "maxF=";
+    printBound(_max_false, os);
+    os << ", minR=";
+    printBound(_min_reduced, os);
+    os << ", minT=";
+    printBound(_min_true, os);
+}
+
+void TrueReducedFalseChart::printBound(Bound* b, std::ostream& os) const
+{
+    if ( !b ) {
+        os << "NULL";
+    }else{
+        b->printFullName(os);
+    }
+}
+
+void TrueReducedFalseChart::clearRedundantReduced()
+{
+    if ( _min_true && _min_reduced && Bound::leq(_min_true, _min_reduced) &&
+         !Bound::eq(_min_true, _min_reduced) ) {
+        _min_reduced = NULL;
+    }
+    if ( _max_false && _min_reduced && Bound::leq(_min_reduced, _max_false) &&
+         !Bound::eq(_min_reduced, _max_false) ) {
+        _min_reduced = NULL;
+    }
+}
+
+//------------------------------------------------------------------------------
+
+void MemoizedDistances::makeEmpty()
+{
+    _map.clear();
+}
+
+void MemoizedDistances::initOpnd(IOpnd* op)
+{
+    OpndToTRFChart::const_iterator it = _map.find(op);
+    if ( it == _map.end() ) {
+        _map.insert(std::make_pair(op, *_bound_alloc.create_empty_TRFChart()));
+    }
+}
+
+void MemoizedDistances::updateLeqBound(IOpnd* dest, Bound* bound, ProveResult res)
+{
+    initOpnd(dest);
+    if ( res == False ) {
+        _map[dest].addFalse(bound);
+    }else if ( res == True ) {
+        _map[dest].addTrue(bound);
+    }else{
+        _map[dest].addReduced(bound);
+    }
+}
+
+bool MemoizedDistances::hasLeqBoundResult(IOpnd* dest, Bound* bound) const
+{
+    OpndToTRFChart::const_iterator it = _map.find(dest);
+    if ( it == _map.end() ) {
+        return false;
+    }
+    return (it->second).hasBoundResult(bound);
+}
+
+ProveResult MemoizedDistances::getLeqBoundResult(IOpnd* dest, Bound* bound) const
+{
+    assert(hasLeqBoundResult(dest, bound));
+    return (_map.find(dest)->second).getBoundResult(bound);
+}
+
+// true iff: (there is a distance to 'dest') && (distance <= bound)
+bool MemoizedDistances::minTrueDistanceLeqBound(IOpnd* dest, Bound* bound)
+{
+    initOpnd(dest);
+    Bound* stored_bound = _map[dest].getMinTrueBound();
+    return stored_bound && Bound::leq(stored_bound, bound);
+}
+
+bool MemoizedDistances::maxFalseDistanceGeqBound(IOpnd* dest, Bound* bound)
+{
+    initOpnd(dest);
+    Bound* stored_bound = _map[dest].getMaxFalseBound();
+    return stored_bound && Bound::leq(bound, stored_bound);
+}
+
+bool MemoizedDistances::minReducedDistanceLeqBound(IOpnd* dest, Bound* bound)
+{
+    initOpnd(dest);
+    Bound* stored_bound = _map[dest].getMinReducedBound();
+    return stored_bound && Bound::leq(stored_bound, bound);
+}
+
+void MemoizedDistances::print(std::ostream& os) const
+{
+    OpndToTRFChart::const_iterator it = _map.begin(), last = _map.end();
+    os << "--- begin MemoizedDistances dump ---" << std::endl;
+    for (; it != last; it++) {
+        it->first->printFullName(os);
+        os << " --> ";
+        (it->second).print(os);
+        os << std::endl;
+    }
+    os << "---   end MemoizedDistances dump ---" << std::endl;
+}
+
+//------------------------------------------------------------------------------
+
+Bound* ActiveOpnds::getBound(IOpnd* opnd) const
+{ 
+    assert(hasOpnd(opnd)); 
+    
+    return _map.find(opnd)->second;
+}
+
+void ActiveOpnds::print(std::ostream& os) const
+{
+    os << "--- begin ActiveOpnds dump ---" << std::endl;
+    for (iter_t it = _map.begin(), last = _map.end(); it != last; it++) {
+        it->first->printFullName(os);
+        os << " --> ";
+        it->second->printFullName(os);
+        os << std::endl;
+    }
+    os << "---   end ActiveOpnds dump ---" << std::endl;
+}
+
+//------------------------------------------------------------------------------
+
+bool ClassicAbcdSolver::demandProve
+     (IOpnd* source, IOpnd* dest, int32 bound_int, bool prove_upper_bound)
+{
+    assert(source && dest);
+    _source_opnd = source;
+    BoundState bs(prove_upper_bound);
+    Bound bound(bound_int, bs);
+
+    _active.makeEmpty();
+    _mem_distance.makeEmpty();
+
+    if (Log::isEnabled() ) {
+        Log::out() << "demandProve(";
+        _source_opnd->printFullName(Log::out());
+        Log::out() << ", "; 
+        dest->printFullName(Log::out());
+        Log::out() << ", ";
+        bound.printFullName(Log::out());
+        Log::out() << std::endl;
+    }
+
+    if ( prove(dest, &bound, 0) == False ) {
+        if (Log::isEnabled() ) {
+            Log::out() << "demandProve: cannot eliminate check" << std::endl;
+        }
+        return false;
+    }
+    if (Log::isEnabled() ) {
+        Log::out() << "demandProve: !!!CAN!!! eliminate check" << std::endl;
+    }
+    return true;
+}
+
+void ClassicAbcdSolver::updateMemDistanceWithPredecessors (IOpnd* dest, 
+                                                           Bound* bound, 
+                                                           uint32 prn_level, 
+                                                      meet_func_t meet_f)
+{
+    const InequalityGraph::EdgeList& in_edges = _igraph.getInEdges(dest);
+    assert(!in_edges.empty());
+    InequalityGraph::EdgeList::const_iterator in_iter = in_edges.begin();
+    InequalityGraph::EdgeList::const_iterator in_last = in_edges.end();
+    IneqEdge* in_edge = (*in_iter);
+    assert(in_edge->getDst() == dest);
+    ProveResult res;
+    assert(!_mem_distance.hasLeqBoundResult(dest, bound));
+    res = prove(in_edge->getSrc(), 
+                _bound_alloc.create_dec_const(bound, 
+                                              in_edge->getLength()),
+                prn_level + 1);
+    in_iter++;
+    for (; in_iter != in_last; in_iter++) {
+        if(((res >= Reduced)  && (meet_f == meetBest)) ||
+           ((res == False) && (meet_f == meetWorst))) {
+            // For any x, meetBest(True, x)    == True
+            //            meetBest(Reduced, x) >= Reduced  
+            //        and meetWorst(False, x)  == False
+            if (Log::isEnabled() ) {
+                Printer prn(prn_level, Log::out());
+                prn.prnStr("skipping remaining preds, proven: ");
+                print_result(res, Log::out());
+                Log::out() << std::endl;
+            }
+            break;
+        }
+        in_edge = (*in_iter);
+        assert(in_edge->getDst() == dest);
+        IOpnd* pred = in_edge->getSrc();
+        res = meet_f(res, 
+                     prove(pred, 
+                           _bound_alloc.create_dec_const(bound, 
+                                                         in_edge->getLength()),
+                           prn_level + 1));
+    }
+    _mem_distance.updateLeqBound(dest, bound, res);
+}
+
+//
+// prove that distance between '_source_opnd' and 'dest' is <= bound
+//
+ProveResult ClassicAbcdSolver::prove(IOpnd* dest, Bound* bound, 
+        uint32 prn_level)
+{
+    Printer prn(prn_level, Log::out());
+    if ( Log::isEnabled() ) {
+        prn.prnStr("prove("); 
+        dest->printFullName(Log::out());
+        Log::out() << ", "; 
+        bound->printFullName(Log::out()); Log::out() << ")" << std::endl;
+    }
+
+    // if ( C[dest - _source_opnd <= e] == True    for some e<=bound ) 
+    //     return True
+    if ( _mem_distance.minTrueDistanceLeqBound(dest, bound) ) {
+        prn.prnStrLn("case 3: => True");
+        return True;
+    }
+
+    // if ( C[dest - _source_opnd <= e] == False   for some e>=bound ) 
+    //     return False
+    if ( _mem_distance.maxFalseDistanceGeqBound(dest, bound) ) {
+        prn.prnStrLn("case 4: => False");
+        return False;
+    }
+
+    // if ( C[dest - _source_opnd <= e] == Reduced for some e<=bound ) 
+    //     return Reduced
+    if ( _mem_distance.minReducedDistanceLeqBound(dest, bound) ) {
+        prn.prnStrLn("case 5: => Reduced");
+        return Reduced;
+    }
+    
+    // traversal reached the _source_opnd vertex
+    if ( (dest->getID() == _source_opnd->getID()) && 
+          Bound::int32_leq(0, bound) ) {
+        prn.prnStrLn("reached source vertex => True");
+        return True;
+    }
+
+    // all constant operands are implicitly connected
+    if ( dest->isConstant() && _source_opnd->isConstant() ) {
+        if ( Bound::const_distance_leq(_source_opnd->getConstant(), 
+                                       dest->getConstant(), 
+                                       bound) ) {
+            prn.prnStrLn("reached source vertex (const) => True");
+            return True;
+        }else {
+            prn.prnStrLn("reached source vertex (bad const) => False");
+            return False;
+        }
+    }
+    
+    // if dest has no predecessor then fail
+    if ( _igraph.getInEdges(dest).empty() ) {
+        prn.prnStrLn("no predecessors => False");
+        return False;
+    }
+
+    // a cycle was encountered
+    if ( _active.hasOpnd(dest) ) {
+        if ( Bound::leq(_active.getBound(dest), bound) ) {
+            prn.prnStrLn("harmless cycle => Reduced");
+            return Reduced; // a harmless cycle
+        }else{
+            prn.prnStrLn("amplifying cycle => False");
+            return False; // an amplifying cycle
+        }
+    }
+
+    _active.setBound(dest, bound);
+    if ( dest->isPhi() ) {
+        prn.prnStrLn("phi => worst");
+        updateMemDistanceWithPredecessors(dest, bound, prn_level, meetWorst);
+    }else{
+        prn.prnStrLn("non_phi => best");
+        updateMemDistanceWithPredecessors(dest, bound, prn_level, meetBest);
+    }
+    _active.clearOpnd(dest);
+
+    ProveResult res = _mem_distance.getLeqBoundResult(dest, bound);
+    if (Log::isEnabled() ) {
+        prn.prnStr("proven: "); print_result(res, Log::out()); Log::out() << std::endl;
+    }
+    return res;
+}
+
+void ClassicAbcdSolver::Printer::prnLevel()
+{
+    if (Log::isEnabled()) {
+        for (uint32 i = 0; i < _level; i++) {
+            _os << "    ";
+        }
+    }
+}
+
+void ClassicAbcdSolver::Printer::prnStr(char* str)
+{
+    prnLevel();
+    if (Log::isEnabled()) {
+        _os << str;
+    }
+}
+
+void ClassicAbcdSolver::Printer::prnStrLn(char* str)
+{
+    if (Log::isEnabled()) {
+        prnStr(str);
+        _os << std::endl;
+    }
+}
+
+//------------------------------------------------------------------------------
+
+/*
+ * for(i = 5; i < A.length; i++) {
+ *     check(-1 < i);
+ *     check(i < A.length);
+ *     ...
+ * }
+ *
+ * i0 = 5
+ * for:
+ * i1 = phi(i0, i2)
+ * if (i1 < A.length) {
+ *     i3 = pi(i1)
+ *     __check(i3 > -1);
+ *     __check(i3 < A.length);
+ *     ...
+ *     i2 = i3 + 1;
+ *     goto for
+ * }
+ * 
+ * 0 -(0)-> i0 -(0)-> i1(phi)
+ * i1(phi) -(0)-> i3 -(1)-> i2 -(0)-> i1(phi)
+ * A.length -(-1)-> i3
+ *
+ * upper: prove(i3 - A.length <= -1) // trivial :)
+ * lower: prove(i3 - (-1) >= 1) // not so trivial
+ */
+void testSimpleIGraph()
+{
+    MemoryManager mm("testSimpleIGraph.MemoryManager");
+    InequalityGraph g(mm);
+    ClassicAbcdSolver solver(g, mm);
+    assert(g.isEmpty());
+
+    IOpnd op0(0), op1(1, true /*phi*/), op2(2), op3(3);
+    g.addOpnd(&op0);
+    g.addOpnd(&op1);
+    g.addOpnd(&op2);
+    g.addOpnd(&op3);
+
+    IOpnd op_const_5(4, false, true);
+    op_const_5.setConstant(5);
+    g.addOpnd(&op_const_5);
+
+    IOpnd length(5);
+
+    g.addOpnd(&length);
+    g.addEdge(0, 1, 0);
+    g.addEdge(1, 3, 0);
+    g.addEdge(3, 2, 1);
+    g.addEdge(2, 1, 0);
+    g.addEdge(5, 3, -1);
+    g.addEdge(4, 0, 0);
+
+    assert(solver.demandProve(g.findOpnd(5), g.findOpnd(3), -1, true));
+    //logfile << " testSimpleIGraph: OK" << std::endl;
+
+    IOpnd op_m1(6, false /* phi */, true /* constant */);
+    op_m1.setConstant(-1);
+    g.addOpnd(&op_m1);
+
+    assert(solver.demandProve(&op_m1, g.findOpnd(3), 1, false));
+    op_const_5.setConstant(-5);
+    assert(!solver.demandProve(&op_m1, g.findOpnd(3), 1, false));
+    op_const_5.setConstant(0);
+    assert(solver.demandProve(&op_m1, g.findOpnd(3), 1, false));
+    op_const_5.setConstant(-1);
+    assert(!solver.demandProve(&op_m1, g.findOpnd(3), 1, false));
+    op_const_5.setConstant(5);
+
+    //logfile << " lower_testSimpleIGraph: OK" << std::endl;
+    //g.printDotFile(std::cout);
+}
+
+/*
+ * for(i = 0; i < A.length; i++) {
+ *     for (j = 0; j < i; j++) {
+ *         check(j < A.length);
+ *     }
+ * }
+ * i0 = 0
+ * for1:
+ * i1 = phi(i0, i3)
+ * if (i1 < A.length) {
+ *     i2 = pi(i1)
+ *     j0 = 0
+ *     for2:
+ *     j1 = phi(j0, j3)
+ *     if (j1 < i2) {
+ *         j2 = pi(j1)
+ *         __check(j2 < A.length)
+ *         j3 = j2 + 1
+ *         goto for2
+ *     }
+ *     i3 = i2 + 1
+ *     goto for1
+ * }
+ * 0 -(0)-> i0 -(0)-> i1(phi) -(0)-> i2 -(1)-> i3 -(0)-> i1 (phi)
+ * A.length -(-1)-> i2 
+ * 0 -(0)-> j0 -(0)-> j1(phi) -(0)-> j2 -(1)-> j3 -(0)-> j1 (phi)
+ * i2 -(-1)-> j2
+ *
+ * upper: prove(j2 - A.length <= -1)
+ * lower: prove(j2 - (-1) >= 1)
+ */
+void testDoubleCycleGraph()
+{
+    MemoryManager mm("testDoubleCycleGraph.MemoryManager");
+    InequalityGraph g(mm);
+    ClassicAbcdSolver solver(g, mm);
+
+    IOpnd i0(0), i1(1, true /*phi*/), i2(2), i3(3), 
+          j0(10), j1(11, true /*phi*/), j2(12), j3(13), length(20);
+    assert(g.isEmpty());
+    g.addOpnd(&i0);
+    g.addOpnd(&i1);
+    g.addOpnd(&i2);
+    g.addOpnd(&i3);
+    g.addOpnd(&j0);
+    g.addOpnd(&j1);
+    g.addOpnd(&j2);
+    g.addOpnd(&j3);
+    g.addOpnd(&length);
+
+    IOpnd op_const_0(21, false, true /*constant*/);
+    op_const_0.setConstant(0);
+    g.addOpnd(&op_const_0);
+
+    g.addEdge(21, 0, 0);
+
+    g.addEdge(0, 1, 0);
+    g.addEdge(1, 2, 0);
+    g.addEdge(2, 3, 1);
+    g.addEdge(3, 1, 0);
+    g.addEdge(20, 2, -1);
+    g.addEdge(21, 10, 0);
+    g.addEdge(10, 11, 0);
+    g.addEdge(11, 12, 0);
+    g.addEdge(12, 13, 1);
+    g.addEdge(13, 11, 0);
+    g.addEdge(2, 12, -1);
+
+    assert(solver.demandProve(g.findOpnd(20), g.findOpnd(12), -1, true));
+    //logfile << " testDoubleCycleGraph: OK" << std::endl;
+
+    IOpnd op_m1(6, false /* phi */, true /* constant */);
+    op_m1.setConstant(-1);
+    g.addOpnd(&op_m1);
+
+    assert(solver.demandProve(&op_m1, g.findOpnd(12), 1, false));
+    //logfile << " lower_testDoubleCycleGraph: OK" << std::endl;
+    //g.printDotFile(std::cout);
+}
+
+/*
+ * limit = A.length
+ * st = -1
+ * while ( st < limit ) {
+ *     st++
+ *     limit--
+ *     for (j = st; j < limit; j++) {
+ *         check(limit >= 0) // should *not* be removable (amplifying)
+ *         check(limit - j >= 0)
+ *         check(j < A.length)
+ *         t = j + 1;
+ *         check(t < A.length)
+ *     }
+ * }
+ *
+ * limit0 = A.length // 00
+ * st0 = -1          // 10
+ * while:
+ *     limit1 = phi(limit0, limit3)     // 01
+ *     st1 = phi(st0, st3)              // 11
+ *     if ( st1 < limit1 ) {
+ *         st2 = pi(st1)                // 12
+ *         limit2 = pi(limit1)          // 02
+ *         st3 = st2 + 1                // 13
+ *         limit3 = limit2 - 1          // 03
+ *         j0 = st3                     // 20
+ *     for:
+ *         j1 = phi(j0, j4)             // 21
+ *         if ( j1 < limit3 ) {
+ *             j2 = pi(j1)              // 22
+ *             limit4 = pi(limit3)      // 04
+ *             __check(j2 < A.length)   //(22 < 55)
+ *             __check(limit4 >= 0)
+ *             j3 = pi(j2)              // 23
+ *             __check(limit2 - j3 >= 0)
+ *             t0 = j3 + 1              // 30
+ *             __check(t0 < A.length)   //(30 < 55)
+ *             t1 = pi(t0)              // 31
+ *             j4 = j3 + 1              // 24
+ *             goto for
+ *         }
+ *         goto while
+ *     }
+ */
+void testPaperIGraph()
+{
+    MemoryManager mm("testPaperIGraph.MemoryManager");
+    InequalityGraph g(mm);
+    ClassicAbcdSolver solver(g, mm);
+
+    assert(g.isEmpty());
+    IOpnd minus_1(66, false /* phi */, true /*constant*/);
+    minus_1.setConstant(-1);
+    IOpnd length(55); // A.length
+
+    IOpnd limit0(00), st0(10), limit1(01, true /*phi*/), st1(11, true /*phi*/),
+          st2(12), limit2(02), st3(13), limit3(03), j0(20), 
+          j1(21, true /*phi*/), j2(22), limit4(04), j3(23), t0(30), t1(31),
+          j4(24);
+ 
+    g.addOpnd(&limit0); g.addOpnd(&limit1); g.addOpnd(&limit2); 
+        g.addOpnd(&limit3); g.addOpnd(&limit4);
+    g.addOpnd(&st0); g.addOpnd(&st1); g.addOpnd(&st2); g.addOpnd(&st3);
+    g.addOpnd(&j0); g.addOpnd(&j1); g.addOpnd(&j2); g.addOpnd(&j3); 
+        g.addOpnd(&j4);
+    g.addOpnd(&t0); g.addOpnd(&t1);
+
+    g.addEdge(&minus_1, &st0, 0);
+    g.addEdge(&st0, &st1, 0);
+    g.addEdge(&st1, &st2, 0);
+    g.addEdge(&st2, &st3, 1);
+    g.addEdge(&st3, &st1, 0);
+    g.addEdge(&st3, &j0, 0);
+    g.addEdge(&limit2, &st2, -1);
+    g.addEdge(&length, &limit0, 0);
+    g.addEdge(&limit0, &limit1, 0);
+    g.addEdge(&limit1, &limit2, 0);
+    g.addEdge(&limit2, &limit3, -1);
+    g.addEdge(&limit3, &limit1, 0);
+    g.addEdge(&limit3, &limit4, 0);
+    g.addEdge(&limit4, &j2, -1);
+    g.addEdge(&j0, &j1, 0);
+    g.addEdge(&j1, &j2, 0);
+    g.addEdge(&j2, &j3, 0);
+    g.addEdge(&j3, &j4, 1);
+    g.addEdge(&j4, &j1, 0);
+    g.addEdge(&j3, &t0, 1);
+    g.addEdge(&length, &j3, -1);
+    g.addEdge(&t0, &t1, 0);
+
+    assert(solver.demandProve(&length, &j2, -1, true));
+    assert(solver.demandProve(&length, &t0, -1, true));
+    //logfile << " testPaperIGraph: OK" << std::endl;
+
+    assert(!solver.demandProve(&minus_1, &limit4, 1, false));
+
+    assert(solver.demandProve(&limit2, &j3, 0, false));
+    //logfile << " lower_testPaperIGraph: OK" << std::endl;
+    //g.printDotFile(std::cout);
+}
+
+void printExampleGraph()
+{
+    uint32 opnd_id = 0;
+    IOpnd op0(opnd_id++), op1(opnd_id++, true), op2(opnd_id++, true, true);
+
+    op2.setConstant(25);
+    MemoryManager mm("printExampleGraph.MemoryManager");
+    InequalityGraph graph(mm);
+    graph.addOpnd(&op0);
+    graph.addOpnd(&op1);
+    graph.addOpnd(&op2);
+    graph.addEdge(0, 1, 3);
+    graph.addEdge(1, 2, -3);
+    graph.addEdge(2, 0, 1);
+    graph.printDotFile(std::cout);
+}
+
+void testMemoizedDistances()
+{
+    MemoryManager mm("testMemoizedDistances.MemoryManager");
+    BoundState bs(true);
+    InequalityGraph graph(mm);
+    BoundAllocator b_alloc(mm);
+    MemoizedDistances mem_distances(b_alloc);
+    IOpnd op0(0), op1(1), op2(2);
+    Bound bnd1(-1, bs), bnd2(5, bs), bnd3(10, bs), bndXX(5, bs);
+
+    assert(!mem_distances.hasLeqBoundResult(&op0, &bnd1));
+    mem_distances.updateLeqBound(&op0, &bnd2, Reduced);
+    mem_distances.updateLeqBound(&op0, &bnd2, False);
+    mem_distances.updateLeqBound(&op0, &bnd2, True);
+    assert(mem_distances.getLeqBoundResult(&op0, &bnd2) == True);
+}
+
+/*
+ * for(i = INT_MAX; i < A.length; i+= 25) {
+ *     check(-1 < i);
+ * }
+ *
+ * i0 = INT_MAX
+ * for:
+ * i1 = phi(i0, i2)
+ * if (i1 < A.length) {
+ *     i2 = pi(i1)
+ *     __check(i2 > -1);
+ *     ...
+ *     i3 = i2 + 1;
+ *     goto for
+ * }
+ * 
+ * INT_MAX -(0)-> i0 -(0)-> i1(phi)
+ * i1(phi) -(0)-> i2 -(1)-> i3 -(0)-> i1(phi)
+ * A.length -(-1)-> i2
+ *
+ * lower: prove(i2 - (0) >= 0)
+ *
+ * -----------------------------------------
+ * for(i = 25; i < A.length; i+= INT_MAX) {
+ *     check(0 <= i);
+ * }
+ */
+void testOverflow()
+{
+    MemoryManager mm("testOverflow.MemoryManager");
+    InequalityGraph g(mm);
+    ClassicAbcdSolver solver(g, mm);
+
+    assert(g.isEmpty());
+    IOpnd i0(00), i1(01, true /*phi */), i2(02), i3(03), 
+          intmax(20, false /* phi */, true /* constant */), 
+          zero(22, false /* phi */, true /* constant */), 
+          length(21);
+    
+    intmax.setConstant(INT_MAX);
+    zero.setConstant(0);
+    g.addOpnd(&zero);
+    g.addOpnd(&i0);
+    g.addOpnd(&i1);
+    g.addOpnd(&i2);
+    g.addOpnd(&i3);
+    g.addOpnd(&intmax);
+    g.addOpnd(&length);
+
+    g.addEdge(&intmax, &i0, 0);
+    g.addEdge(&i0, &i1, 0);
+    g.addEdge(&i1, &i2, 0);
+    g.addEdge(&i2, &i3, 1);
+    g.addEdge(&i3, &i1, 0);
+    g.addEdge(&length, &i2, -1);
+
+    assert(!solver.demandProve(&zero, &i2, 0, false));
+    // well, array size is too big
+    //g.printDotFile(std::cout);
+
+    intmax.setConstant(25);
+    (*g.getOutEdges(&i2).begin())->setLength(INT_MAX - 5);
+    //g.printDotFile(std::cout);
+    assert(!solver.demandProve(&zero, &i2, 0, false));
+    //logfile << " testOverflow: OK" << std::endl;
+}
+
+//------------------------------------------------------------------------------
+
+int classic_abcd_test_main()
+{
+    std::cout << "running ABCD self-tests" << std::endl;
+    testMemoizedDistances();
+    testSimpleIGraph();
+    testDoubleCycleGraph();
+    testPaperIGraph();
+
+    // OK, testOverflow should fail
+    //testOverflow();
+    std::cout << "ABCD self-tests PASSED" << std::endl;
+
+    return 0;
+}
+
+} //namespace Jitrino 
+

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

Added: harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd_solver.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd_solver.h?view=auto&rev=544138
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd_solver.h (added)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd_solver.h Mon Jun  4 05:12:02 2007
@@ -0,0 +1,350 @@
+/*
+ *  Copyright 2005-2006 The Apache Software Foundation or its licensors, as applicable.
+ *
+ *  Licensed 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 _CLASSIC_ABCD_SOLVER_H
+#define _CLASSIC_ABCD_SOLVER_H
+
+#include <assert.h>
+#include <iostream>
+#include <climits>
+
+#include "open/types.h"
+#include "Stl.h"
+
+namespace Jitrino {
+
+class IOpnd {
+public:
+    IOpnd(uint32 id, bool is_phi = false, bool is_constant = false) :
+        _id(id), _phi(is_phi), _const(is_constant), 
+        _unconstrained(false), _value(0)
+    {}
+
+    IOpnd() { assert(0); }
+    virtual ~IOpnd() {};
+
+    void setPhi(bool s = true) { _phi = s; }
+    bool isPhi() const { return _phi; }
+
+    void setIsConstant(bool s = true) { _const = s; }
+    bool isConstant() const { return _const; }
+
+    void setConstant(int32 val) { setIsConstant(true); _value = val; }
+    int32 getConstant() const { assert(isConstant()); return _value; }
+
+    void setUnconstrained(bool unc) { _unconstrained = unc; }
+    bool isUnconstrained() { return _unconstrained; }
+
+    void setID(uint32 id) { _id = id; }
+    uint32 getID() const { return _id; }
+
+    virtual void printName(std::ostream& os) const;
+    void printFullName(std::ostream& os) const;
+private:
+    uint32 _id;
+    bool   _phi, _const, _unconstrained;
+    int32  _value;
+};
+
+class BoundState {
+public:
+    BoundState() : _upper(true) {}
+    BoundState(bool upper) : _upper(upper) {}
+
+    void setUpper(bool upper = true) { _upper = upper; }
+
+    bool isUpper() const { return _upper; }
+private:
+
+    bool _upper;
+};
+
+class HasBoundState {
+public:
+    HasBoundState(const BoundState& bs) : _bound_state(bs) {}
+
+    const BoundState& getBoundState() { return _bound_state; }
+
+    bool isUpper() const { return _bound_state.isUpper(); }
+private:
+    const BoundState& _bound_state;
+};
+
+class IneqEdge {
+public:
+    IneqEdge(IOpnd* src, IOpnd* dst, int32 len) :
+        _src(src), _dst(dst), _length(len)
+    {}
+    IOpnd* getSrc() const { return _src; }
+    IOpnd* getDst() const { return _dst; }
+    int32 getLength() const { return _length; }
+    void setLength(int32 len) { _length = len; }
+private:
+    IOpnd *_src, *_dst;
+    int32 _length;
+};
+
+class InequalityGraph {
+    typedef StlMap<uint32, StlList<IneqEdge*> > OpndEdgeMap;
+public:
+    typedef StlList<IneqEdge*> EdgeList;
+    InequalityGraph(MemoryManager& mem_mgr) : 
+        _mem_mgr(mem_mgr), 
+        _id_to_opnd_map(mem_mgr),
+        _edges(mem_mgr),
+        _opnd_to_inedges_map(mem_mgr), 
+        _opnd_to_outedges_map(mem_mgr),
+        _emptyList(mem_mgr)
+    {}
+
+    void addEdge(IOpnd* from, IOpnd* to, int32 distance);
+
+    void addEdge(uint32 id_from, uint32 id_to, int32 distance);
+
+    void addOpnd(IOpnd* opnd);
+
+    const EdgeList& getInEdges(IOpnd* opnd) const;
+
+    const EdgeList& getOutEdges(IOpnd* opnd) const;
+
+    void printDotFile(std::ostream& os) const;
+
+    bool isEmpty() const { return _id_to_opnd_map.empty(); }
+
+    IOpnd* findOpnd(uint32 id) const;
+
+    MemoryManager& getMemoryManager() { return _mem_mgr; }
+private:
+    friend class InequalityOpndIterator;
+    friend class InequalityGraphPrinter;
+    typedef StlMap<uint32, IOpnd*> IdToOpndMap;
+
+    static bool has_other_opnd_with_same_id(IdToOpndMap& map, IOpnd* opnd);
+
+    void printDotHeader(std::ostream& os) const;
+    void printDotBody(std::ostream& os) const;
+    void printDotEnd(std::ostream& os) const;
+
+    void addEdgeToIdMap (OpndEdgeMap& mp, uint32 id, IneqEdge* edge);
+
+    MemoryManager& _mem_mgr;
+    IdToOpndMap _id_to_opnd_map;
+    EdgeList _edges;
+
+    OpndEdgeMap _opnd_to_inedges_map, _opnd_to_outedges_map;
+    EdgeList _emptyList;
+};
+
+class Bound : public HasBoundState {
+public:
+    Bound(int32 bnd, const BoundState& bs) : HasBoundState(bs), _bound(bnd) {}
+
+    // bound - int32 -> Bound
+    Bound(Bound* bound, int32 val, const BoundState& bs);
+
+    void printFullName(std::ostream& os);
+
+    static bool leq(Bound* bound1, Bound* bound2);
+
+    static bool eq(Bound* bound1, Bound* bound2);
+
+    static bool leq_int32(Bound* bound1, int32 value);
+
+    static bool int32_leq(int32 value, Bound* bound1);
+
+    // returns (dst_val - src_val <= bound)
+    static bool const_distance_leq(int32 src_val, int32 dst_val, Bound* bound);
+
+private:
+    friend class BoundAllocator;
+    int32 _bound;
+};
+
+class TrueReducedFalseChart;
+
+class BoundAllocator {
+public:
+    BoundAllocator(MemoryManager& mem_mgr) : _mem_mgr(mem_mgr) {}
+
+    Bound* create_inc1(Bound* bound);
+
+    Bound* create_dec1(Bound* bound);
+
+    Bound* create_dec_const(Bound* bound, int32 cnst);
+
+    TrueReducedFalseChart* create_empty_TRFChart();
+
+private:
+    friend class MemoizedDistances;
+
+    MemoryManager& getMemoryManager() { return _mem_mgr; }
+
+    Bound* newBound(int32 val, const BoundState& bs);
+    MemoryManager& _mem_mgr;
+};
+
+enum ProveResult {
+    True = 2,
+    Reduced = 1,
+    False = 0
+};
+
+typedef ProveResult (*meet_func_t)(ProveResult, ProveResult);
+
+class TrueReducedFalseChart {
+public:
+    TrueReducedFalseChart() :
+        _max_false(NULL),
+        _min_true(NULL),
+        _min_reduced(NULL),
+        _bound_alloc(NULL)
+    {assert(0);}
+
+    TrueReducedFalseChart(BoundAllocator* alloc) :
+        _max_false(NULL),
+        _min_true(NULL),
+        _min_reduced(NULL),
+        _bound_alloc(alloc)
+    {}
+
+    void addFalse(Bound* f_bound);
+
+    void addReduced(Bound* r_bound);
+
+    void addTrue(Bound* t_bound);
+
+    bool hasBoundResult(Bound* bound) const;
+
+    ProveResult getBoundResult(Bound* bound) const;
+
+    Bound* getMaxFalseBound() { return _max_false; }
+
+    Bound* getMinTrueBound() { return _min_true; }
+
+    Bound* getMinReducedBound() { return _min_reduced; }
+
+    void print(std::ostream& os) const;
+
+private:
+    void printBound(Bound* b, std::ostream& os) const;
+
+    void clearRedundantReduced();
+
+    Bound *_max_false, *_min_true, *_min_reduced;
+    BoundAllocator* _bound_alloc;
+};
+
+class MemoizedDistances {
+public:
+    MemoizedDistances(BoundAllocator& alloc) : 
+        _bound_alloc(alloc),
+        _map(_bound_alloc.getMemoryManager()) 
+    {}
+
+    void makeEmpty();
+
+    // set [dest - source <= bound] 
+    void updateLeqBound(IOpnd* dest, Bound* bound, ProveResult res);
+
+    bool hasLeqBoundResult(IOpnd* dest, Bound* bound) const;
+
+    // returns [dest - source <= bound] 
+    //      that is True, Reduced or False
+    ProveResult getLeqBoundResult(IOpnd* dest, Bound* bound) const;
+
+    bool minTrueDistanceLeqBound(IOpnd* dest, Bound* bound);
+
+    bool maxFalseDistanceGeqBound(IOpnd* dest, Bound* bound);
+
+    bool minReducedDistanceLeqBound(IOpnd* dest, Bound* bound);
+
+    void print(std::ostream& os) const;
+
+private:
+    void initOpnd(IOpnd* op);
+
+    typedef StlMap<IOpnd*, TrueReducedFalseChart> OpndToTRFChart;
+    BoundAllocator& _bound_alloc;
+    OpndToTRFChart _map;
+};
+
+class ActiveOpnds {
+typedef StlMap<IOpnd*, Bound*>::const_iterator iter_t;
+public:
+    ActiveOpnds(MemoryManager& mem_mgr) : _map(mem_mgr) {}
+
+    void makeEmpty() { _map.clear(); }
+
+    bool hasOpnd(IOpnd* opnd) const { return _map.find(opnd) != _map.end(); }
+
+    Bound* getBound(IOpnd* opnd) const;
+
+    void setBound(IOpnd* opnd, Bound* bound) { _map[opnd] = bound; }
+
+    void clearOpnd(IOpnd* opnd) { _map.erase(_map.find(opnd)); }
+
+    void print(std::ostream& os) const;
+
+private:
+    StlMap<IOpnd*, Bound*> _map;
+};
+
+class ClassicAbcdSolver {
+public:
+    ClassicAbcdSolver(InequalityGraph& i, MemoryManager& solver_mem_mgr) : 
+        _igraph(i), 
+        _source_opnd(NULL), 
+        _bound_alloc(solver_mem_mgr),
+        _mem_distance(_bound_alloc),
+        _active(solver_mem_mgr)
+    {}
+
+    bool demandProve
+        (IOpnd* source, IOpnd* dest, int32 bound_int, bool prove_upper_bound);
+
+private:
+    ProveResult prove(IOpnd* dest, Bound* bound, uint32 prn_level);
+
+    void updateMemDistanceWithPredecessors
+        (IOpnd* dest, Bound* bound, uint32 prn_level, meet_func_t meet_f);
+
+    class Printer {
+    public:
+        Printer(uint32 level, std::ostream& os) : _level(level), _os(os) {}
+
+        void prnLevel();
+
+        void prnStr(char* str);
+
+        void prnStrLn(char* str);
+
+    private:
+        uint32 _level;
+        std::ostream& _os; 
+    };
+
+    InequalityGraph& _igraph;
+    IOpnd* _source_opnd;
+    BoundAllocator _bound_alloc;
+    MemoizedDistances _mem_distance;
+    ActiveOpnds _active;
+};
+
+int classic_abcd_test_main();
+
+} //namespace Jitrino 
+
+#endif /* _CLASSIC_ABCD_SOLVER_H */

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



Mime
View raw message