harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From e...@apache.org
Subject svn commit: r565011 - in /harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer: abcd/classic_abcd.cpp abcd/classic_abcd.h abcd/classic_abcd_solver.cpp abcd/classic_abcd_solver.h abcd/insertpi.cpp abcd/insertpi.h optimizer.cpp optimizer.h
Date Sun, 12 Aug 2007 07:52:38 GMT
Author: egor
Date: Sun Aug 12 00:52:37 2007
New Revision: 565011

URL: http://svn.apache.org/viewvc?view=rev&rev=565011
Log:
Applying patches from HARMONY-4476 ([drlvm][jit][opt][abcd] Two-state Inequality Graph for both Lower and Upper problems, to ensure correctness and simplify the code, ability to dump stats)


Modified:
    harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd.cpp
    harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd.h
    harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd_solver.cpp
    harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd_solver.h
    harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/insertpi.cpp
    harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/insertpi.h
    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/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=diff&rev=565011&r1=565010&r2=565011
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd.cpp (original)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd.cpp Sun Aug 12 00:52:37 2007
@@ -73,13 +73,20 @@
     /* 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;
+    static const uint32 min_var_opnd = 0;
+    static const uint32 min_ssa_opnd = MAX_UINT32 / 4;
+    static const uint32 min_pi_opnd = (min_ssa_opnd) * 2;
+    static const uint32 min_const_opnd = (min_ssa_opnd) * 3;
 };
 //------------------------------------------------------------------------------
 
+// for debugging purposes
+void printIOpnd(IOpnd* opnd)
+{
+    opnd->printName(std::cout);
+    std::cout << std::endl;
+}
+
 bool inInt32(int64 c) {
     return (int64)(int32)c == c;
 }
@@ -120,7 +127,7 @@
     IOpnd(0, false /* is_phi */, true /* is_constant */),
     _opnd(NULL)
 {
-    setID((uint32)min_const_opnd + id);
+    setID(min_const_opnd + id);
     setConstant(c);
 }
 
@@ -144,18 +151,17 @@
 class BuildInequalityGraphWalker {
 public:
     BuildInequalityGraphWalker(InequalityGraph* igraph, bool isLower) :
-       _igraph(igraph), _isLower(isLower), _const_id_counter(1 /*reserve 0 for solver*/)
+        _igraph(igraph), _const_id_counter(1 /*reserve 0 for solver*/),
+        _map_opnd_to_pi_inst(igraph->getMemoryManager())
     {}
 
-    void startNode(DominatorNode *domNode) {}
+    void startNode(DominatorNode *domNode);
     void applyToInst(Inst* i);
-    void finishNode(DominatorNode *domNode) {}
+    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);
@@ -166,27 +172,48 @@
     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 addDistanceSingleProblem(IOpndProxy* to, IOpndProxy* from, int64 c, 
+                                  bool lower_problem);
 
-    void addPiEdgesWithOneBoundInf
-         (IOpndProxy* dst, bool lb_is_inf, const PiBound& non_inf_bound);
+    void addPiEdgesSingleProblem
+         (IOpndProxy* dst, bool lower_problem, const PiBound& non_inf_bound);
 
     IOpndProxy* findProxy(Opnd* opnd);
 
     IOpndProxy* addOldOrCreateOpnd(Opnd* opnd);
 
     InequalityGraph* _igraph;
-    bool _isLower;
     uint32 _const_id_counter;
+
+    // operands are mapped to their renaming Pi instructions during the walk
+    // (applyToInst), and then this mapping is used to create edges between
+    // operands in InequalityGraph. This allows to link newer operands with
+    // constraints (edges) rather than old ones;
+    //
+    // Example:
+    //   if ( x.1 < y.1 ) {
+    //     pi( x.1 : [undef, y.1 - 1] ) -> x.2 // inst.X
+    //     pi( y.1 : [x.1 + 1, undef] ) -> y.2 // inst.Y
+    //   }
+    //
+    // we collect the mapping:
+    //     x.1 -> inst.X
+    //     y.1 -> inst.Y
+    // to deduce edges:
+    //     upper-only edge: x.2 - y.2 <= -1 // hint: 'to' - 'from'
+    //     lower-only edge: 1 <= y.2 - x.2
+    // instead of the straightforward:
+    //     upper-only edge: x.2 - y.1 <= -1 // hint: 'to' - 'from'
+    //     lower-only edge: 1 <= y.2 - x.1
+    //
+    // (ideally there should only be 2 elements in the map for each basic block
+    //  at most (taken from "if a < b" or such), but our InsertPi sometimes adds
+    //  more)
+    typedef StlMap<IOpndProxy*, TauPiInst*> OpndToPiInst2ElemMap;
+    OpndToPiInst2ElemMap _map_opnd_to_pi_inst;
 };
 //------------------------------------------------------------------------------
- 
+
 IOpndProxy* BuildInequalityGraphWalker::findProxy(Opnd* opnd)
 {
     assert(_igraph);
@@ -204,6 +231,28 @@
 }
 //------------------------------------------------------------------------------
 
+void BuildInequalityGraphWalker::startNode(DominatorNode *domNode)
+{
+    if ( Log::isEnabled() &&
+         !_map_opnd_to_pi_inst.empty() ) {
+        Log::out() << "_map_opnd_to_pi_inst before clear:" << std::endl;
+        OpndToPiInst2ElemMap::const_iterator 
+            it = _map_opnd_to_pi_inst.begin(),
+            end = _map_opnd_to_pi_inst.end();
+        for (; it != end; it++ ) {
+            IOpndProxy* opnd = it->first;
+            TauPiInst* inst = it->second;
+            Log::out() << " opnd: ";
+            opnd->printName(Log::out());
+            Log::out() << " -> inst: ";
+            inst->print(Log::out());
+            Log::out() << std::endl;
+        }
+    }
+    _map_opnd_to_pi_inst.clear();
+}
+//------------------------------------------------------------------------------
+
 void BuildInequalityGraphWalker::applyToInst(Inst* inst)
 {
     assert(inst);
@@ -266,10 +315,14 @@
             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());
+            _map_opnd_to_pi_inst[src0] = inst->asTauPiInst();
+            if ( Log::isEnabled() ) {
+                Log::out() << "mapping (src->pi inst): src: ";
+                src0->printName(Log::out());
+                Log::out() << " inst: ";
+                inst->print(Log::out());
+                Log::out() << std::endl;
+            }
         }
             break;
         case Op_TauArrayLen:
@@ -286,14 +339,46 @@
 }
 //------------------------------------------------------------------------------
 
+void BuildInequalityGraphWalker::finishNode(DominatorNode *domNode)
+{
+    OpndToPiInst2ElemMap::const_iterator it = _map_opnd_to_pi_inst.begin(),
+        end = _map_opnd_to_pi_inst.end();
+    for (; it != end; it++ ) {
+        TauPiInst* pi_inst = it->second;
+        const PiCondition* condition = pi_inst->getCond();
+        const PiBound& lb = condition->getLb();
+        const PiBound& ub = condition->getUb();
+        IOpndProxy* dst = findProxy(pi_inst->getDst());
+        assert(dst);
+        /*
+         * 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)
+         */
+        bool lb_defined = !lb.isUndefined();
+        bool ub_defined = !ub.isUndefined();
+        if ( lb_defined ) {
+            addPiEdgesSingleProblem(dst, true /* lower_problem */, lb);
+        }
+        if ( ub_defined ) {
+            addPiEdgesSingleProblem(dst, false /* lower_problem */, ub);
+        }
+    }
+}
+
 // 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?
+    // This prevention to put some edges is *not* an optimization of any kind.
+    // Operands can be marked unconstrained by various reasons, for example:
+    // because the constant value does not fit into int32 (which is critical for
+    // array access)
     if ( !src->isUnconstrained() ) {
         if ( !inInt32(constant) ) {
             return false;
@@ -301,17 +386,21 @@
         if ( negate ) {
             constant = (-1) * constant;
         }
-        _igraph->addEdge(src->getID(), dst->getID(), (int32)constant);
+        _igraph->addEdge(src->getID(), dst->getID(), constant);
         return true;
     }
     return false;
 }
 //------------------------------------------------------------------------------
 
-void BuildInequalityGraphWalker::addDistanceSwapNegate
-     (IOpndProxy* to, IOpndProxy* from, int64 c, bool negate)
+void BuildInequalityGraphWalker::addDistanceSingleProblem
+     (IOpndProxy* to, IOpndProxy* from, int64 c, bool lower_problem)
 {
-    addDistance(!negate ? to : from, !negate ? from : to, c, negate);
+    assert(to && from);
+    if ( from->isUnconstrained() || !inInt32(c) ) {
+        return;
+    }
+    _igraph->addEdgeSingleState(from->getID(), to->getID(), c, lower_problem);
 }
 //------------------------------------------------------------------------------
 
@@ -331,42 +420,33 @@
 }
 //------------------------------------------------------------------------------
 
-/*
- * 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)
+void BuildInequalityGraphWalker::addPiEdgesSingleProblem
+     (IOpndProxy* dst, bool lower_problem, 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 */);
+        IOpndProxy* var_proxy = findProxy(var);
+        assert(var_proxy);
+        if ( _map_opnd_to_pi_inst.count(var_proxy) == 0 ) {
+            addDistanceSingleProblem(dst /* to */,
+                                  var_proxy /* from */,
+                                  non_inf_bound.getConst(),
+                                  lower_problem);
+        }else{
+            TauPiInst* pi_inst = _map_opnd_to_pi_inst[var_proxy];
+            IOpndProxy* newer_var_proxy = findProxy(pi_inst->getDst());
+            assert(newer_var_proxy);
+            addDistanceSingleProblem(dst /* to */,
+                                  newer_var_proxy /* from */,
+                                  non_inf_bound.getConst(),
+                                  lower_problem);
+        }
     } else if ( non_inf_bound.isConst() ) {
         MemoryManager& mm = _igraph->getMemoryManager();
         IOpndProxy* c_opnd = new (mm) 
-            IOpndProxy((int32)non_inf_bound.getConst(), _const_id_counter++);
+            IOpndProxy(non_inf_bound.getConst(), _const_id_counter++);
         _igraph->addOpnd(c_opnd);
-        addDistanceSwapNegate(c_opnd /* to */, dst, 0, false /* negate */);
+        addDistanceSingleProblem(c_opnd /* to */, dst, 0, lower_problem);
     }
 }
 //------------------------------------------------------------------------------
@@ -399,6 +479,85 @@
 };
 //------------------------------------------------------------------------------
 
+ClassicAbcd::ClassicAbcd(SessionAction* arg_source, IRManager &ir_manager,
+        MemoryManager& mem_manager, DominatorTree& dom0) :
+    _irManager(ir_manager), 
+    _mm(mem_manager),
+    _domTree(dom0),
+    _redundantChecks(mem_manager),
+    _zeroIOp(NULL),
+    _dump_abcd_stats(ir_manager.getOptimizerFlags().dump_abcd_stats)
+{
+    _runTests = arg_source->getBoolArg("run_tests", false);
+    _useAliases = arg_source->getBoolArg("use_aliases", true);
+    _zeroIOp = new (mem_manager) IOpndProxy(0, 0 /*using reserved ID*/);
+}
+//------------------------------------------------------------------------------
+
+void ClassicAbcd::updateOrInitValue
+     (InstRedundancyMap& map, Inst* inst, RedundancyType type)
+{
+    if ( map.count(inst) == 0 ) {
+        map[inst] = type;
+    }else{
+        int32 new_rtype = (int32)map[inst];
+        new_rtype |= (int32)type;
+        map[inst] = (RedundancyType)new_rtype;
+    }
+}
+//------------------------------------------------------------------------------
+
+void ClassicAbcd::markRedundantInstructions
+     (bool upper_problem, InequalityGraph& igraph, ControlFlowGraph& cfg)
+{
+    ClassicAbcdSolver solver(igraph, igraph.getMemoryManager());
+    igraph.setState(!upper_problem /* is_lower */);
+
+    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);
+                if (Log::isEnabled()) {
+                    Log::out() << "Trying to eliminate CheckBounds instruction ";
+                    curr_inst->print(Log::out());
+                    Log::out() << std::endl;
+                }
+
+                Opnd *idxOp = curr_inst->getSrc(1);
+                IOpnd *idxIOp = igraph.findOpnd(IOpndProxy::getProxyIdByOpnd(idxOp));
+
+                IOpnd *boundsIOp = _zeroIOp;
+                if ( upper_problem ) {
+                    Opnd *boundsOp = curr_inst->getSrc(0);
+                    boundsIOp = igraph.findOpnd(IOpndProxy::getProxyIdByOpnd(boundsOp));
+                }
+                bool res = solver.demandProve
+                           (boundsIOp, idxIOp, upper_problem ? -1 : 0, upper_problem);
+                if (res) {
+                    RedundancyType rt = upper_problem ? rtUPPER_MASK : rtLOWER_MASK;
+                    updateOrInitValue(_redundantChecks, curr_inst, rt);
+                    if (Log::isEnabled()) {
+                        Log::out() << "can eliminate";
+                        if ( upper_problem ) {
+                            Log::out() << " upper ";
+                        }else{
+                            Log::out() << " lower ";
+                        }
+                        Log::out() << "bound check!\n";
+                    }
+                }
+            }
+        }
+    }
+}
+//------------------------------------------------------------------------------
+
 void ClassicAbcd::runPass()
 {
     static bool run_once = true;
@@ -420,127 +579,37 @@
         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;
+    MemoryManager ineq_mm("ClassicAbcd::InequalityGraph");
+    InsertPi insertPi(ineq_mm, _domTree, _irManager, _useAliases);
+    insertPi.insertPi();
+    InequalityGraph igraph(ineq_mm);
+    igraph.addOpnd(_zeroIOp);
+    BuildInequalityGraphWalker igraph_walker(&igraph, false /*lower*/);
+    typedef ScopedDomNodeInst2DomWalker<true, BuildInequalityGraphWalker>
+        IneqBuildDomWalker;
+    IneqBuildDomWalker dom_walker(igraph_walker);
+    DomTreeWalk<true, IneqBuildDomWalker>(_domTree, dom_walker, ineq_mm);
 
-            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();
+    if ( Log::isEnabled() ) {
+        Log::out() << "added zero opnd for solving lower bound problem: ";
+        _zeroIOp->printFullName(Log::out());
+        Log::out() << std::endl;
+        InequalityGraphPrinter printer(igraph);
+        printer.printDotFile(method_desc, "inequality.graph");
     }
 
+    _redundantChecks.clear();
+    markRedundantInstructions(true /* upper_problem */, igraph, cfg);
+    markRedundantInstructions(false /* upper_problem */, igraph, cfg);
 
-    {
-        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()) {
+    insertPi.removePi();
 
-                if (curr_inst->getOpcode() == Op_TauCheckBounds) {
-                    assert(curr_inst->getNumSrcOperands() == 2);
-                    Opnd *idxOp = curr_inst->getSrc(1);
+    uint32 checks_eliminated = 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));
-
-                    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) {
+    for(InstRedundancyMap::const_iterator i = _redundantChecks.begin();
+        i != _redundantChecks.end(); ++i) {
         Inst *redundant_inst = i->first;
-        bool fully_redundant = i->second == 0x3;
+        bool fully_redundant = (i->second == rtFULL_MASK);
 
         if (fully_redundant) {
             // should we check if another tau has already been placed in
@@ -563,6 +632,7 @@
             Inst* copy = instFactory.makeCopy(dstOp, tauOp);
             copy->insertBefore(redundant_inst);
             FlowGraph::eliminateCheck(cfg, redundant_inst->getNode(), redundant_inst, false);
+            checks_eliminated++;
             
             if (Log::isEnabled()) {
                 Log::out() << "Replaced bound check with inst ";
@@ -570,6 +640,22 @@
                 Log::out() << std::endl;
             }
         }
+    }
+
+    uint32 checks_total = _redundantChecks.size();
+    if ( _dump_abcd_stats && checks_total > 0 ) {
+        std::ofstream checks_log;
+        checks_log.open("bounds_checks.log", std::fstream::out | std::fstream::app);
+        checks_log << "removed bounds checks of: "
+            << method_desc.getParentType()->getName()
+            << "." << method_desc.getName()
+            << method_desc.getSignatureString()
+            << " total checks: " << checks_total
+            << "; eliminated: " << checks_eliminated
+            << "; fraction: "
+            << (double) checks_eliminated / (double) checks_total
+            << std::endl;
+        checks_log.close();
     }
 
     Log::out() << "ClassicAbcd pass finished" << std::endl;

Modified: 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=diff&rev=565011&r1=565010&r2=565011
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd.h (original)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd.h Sun Aug 12 00:52:37 2007
@@ -31,26 +31,39 @@
 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);
-    }
-
+                MemoryManager& mem_manager, DominatorTree& dom0);
     void runPass();
 private:
     friend class BuildInequalityGraphWalker;
 
+    enum RedundancyType {
+        rtNONE_MASK = 0x0,
+        rtLOWER_MASK = 0x1,
+        rtUPPER_MASK = 0x2,
+        rtFULL_MASK  = 0x3
+    };
+
+    typedef StlMap<Inst *, RedundancyType> InstRedundancyMap;
+
+    // utility-method to update a value for markRedundantInstructions(...)
+    void updateOrInitValue
+         (InstRedundancyMap& map, Inst* inst, RedundancyType type);
+
+    // marks upper-redundant or lower-redundant operations and stores output in
+    // _redundantChecks, if an instruction was marked as redundant, the value is
+    // correctly updated with the new redundancy info
+    void markRedundantInstructions
+         (bool upper_problem, InequalityGraph& igraph, ControlFlowGraph& cfg);
+
     IRManager& _irManager;
     MemoryManager& _mm;
     DominatorTree& _domTree;
+    InstRedundancyMap _redundantChecks;
+    IOpnd* _zeroIOp;
 
     bool _runTests;
     bool _useAliases;
+    bool _dump_abcd_stats;
 };
 
 } //namespace Jitrino 

Modified: 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=diff&rev=565011&r1=565010&r2=565011
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd_solver.cpp (original)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd_solver.cpp Sun Aug 12 00:52:37 2007
@@ -39,6 +39,62 @@
 }
 
 //------------------------------------------------------------------------------
+void TwoStateOpndToEdgeListMap::setState(bool is_lower)
+{
+    _is_lower = is_lower;
+    MapIdTo2stList::iterator it = _map.begin(), end = _map.end();
+    for ( ; it != end; it++ ) {
+        assert(it->second);
+        it->second->setState(is_lower);
+    }
+}
+
+void TwoStateOpndToEdgeListMap::addEdge(uint32 opnd_id, IneqEdge* edge)
+{
+    MapIdTo2stList::iterator it = _map.find(opnd_id);
+    if ( it == _map.end() ) {
+        TwoStateEdgeList* new_lst = new (_mm) TwoStateEdgeList(_mm);
+        new_lst->addEdge(edge);
+        _map[opnd_id] = new_lst;
+    }else{
+        it->second->addEdge(edge);
+    }
+}
+
+void TwoStateOpndToEdgeListMap::addEdgeSingleState
+    (uint32 opnd_id, IneqEdge *edge, bool is_lower)
+{
+    MapIdTo2stList::iterator it = _map.find(opnd_id);
+    if ( it == _map.end() ) {
+        TwoStateEdgeList* new_lst = new (_mm) TwoStateEdgeList(_mm);
+        new_lst->addEdgeSingleState(edge, is_lower);
+        _map[opnd_id] = new_lst;
+    }else{
+        it->second->addEdgeSingleState(edge, is_lower);
+    }
+}
+
+TwoStateEdgeList::iterator
+    TwoStateOpndToEdgeListMap::eListBegin(uint32 opnd_id) const
+{
+    MapIdTo2stList::const_iterator it = _map.find(opnd_id);
+    if ( it == _map.end() ) {
+        return TwoStateEdgeList::emptyIterator();
+    }
+    return it->second->begin();
+}
+
+TwoStateEdgeList::iterator
+    TwoStateOpndToEdgeListMap::eListEnd(uint32 opnd_id) const
+{
+    MapIdTo2stList::const_iterator it = _map.find(opnd_id);
+    if ( it == _map.end() ) {
+        return TwoStateEdgeList::emptyIterator();
+    }
+    return it->second->end();
+}
+
+//------------------------------------------------------------------------------
 
 bool InequalityGraph::has_other_opnd_with_same_id(IdToOpndMap& map, IOpnd* opnd)
 {
@@ -49,38 +105,24 @@
     return false;
 }
 
-//------------------------------------------------------------------------------
-
-const InequalityGraph::EdgeList& InequalityGraph::getInEdges(IOpnd* opnd) const
-{ 
-    OpndEdgeMap::const_iterator it = _opnd_to_inedges_map.find(opnd->getID());
+InequalityGraph::edge_iterator InequalityGraph::inEdgesBegin(IOpnd* opnd) const
+{
+    return _opnd_to_inedges_map_2st.eListBegin(opnd->getID());
+}
 
-    if ( it == _opnd_to_inedges_map.end() ) {
-        return _emptyList;
-    }
-    return it->second;
+InequalityGraph::edge_iterator InequalityGraph::inEdgesEnd(IOpnd* opnd) const
+{
+    return _opnd_to_inedges_map_2st.eListEnd(opnd->getID());
 }
 
-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;
+InequalityGraph::edge_iterator InequalityGraph::outEdgesBegin(IOpnd* opnd) const
+{
+    return _opnd_to_outedges_map_2st.eListBegin(opnd->getID());
 }
 
-void InequalityGraph::addEdgeToIdMap
-     (OpndEdgeMap& mp, uint32 id, IneqEdge* edge)
+InequalityGraph::edge_iterator InequalityGraph::outEdgesEnd(IOpnd* opnd) const
 {
-    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);
-    }
+    return _opnd_to_outedges_map_2st.eListEnd(opnd->getID());
 }
 
 void InequalityGraph::addEdge(IOpnd* from, IOpnd* to, int32 distance)
@@ -94,23 +136,55 @@
     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);
+    _opnd_to_outedges_map_2st.addEdge(from->getID(), p_edge);
+    _opnd_to_inedges_map_2st.addEdge(to->getID(), p_edge);
+}
+
+void InequalityGraph::setState(bool is_lower)
+{
+    _is_lower = is_lower;
+    _opnd_to_inedges_map_2st.setState(is_lower);
+    _opnd_to_outedges_map_2st.setState(is_lower);
 }
 
 void InequalityGraph::addEdge(uint32 id_from, uint32 id_to, int32 distance)
 {
-    IOpnd *from, *to;
-    IdToOpndMap::iterator it;
+    IOpnd* from = getOpndById(id_from);
+    IOpnd* to = getOpndById(id_to);
+    addEdge(from, to, distance);
+}
 
-    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);
+IOpnd* InequalityGraph::getOpndById(uint32 id) const
+{
+    IdToOpndMap::const_iterator it = _id_to_opnd_map.find(id);
     assert(it != _id_to_opnd_map.end());
-    to = it->second;
+    return it->second;
+}
 
-    addEdge(from, to, distance);
+void InequalityGraph::addEdgeSingleState
+     (uint32 id_from, uint32 id_to, int32 distance, bool is_lower)
+{
+    IOpnd* from = getOpndById(id_from);
+    IOpnd* to = getOpndById(id_to);
+    addEdgeSingleState(from, to, distance, is_lower);
+}
+
+void InequalityGraph::addEdgeSingleState
+     (IOpnd* from, IOpnd* to, int32 distance, bool is_lower)
+{
+    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);
+
+    _opnd_to_outedges_map_2st.
+        addEdgeSingleState(from->getID(), p_edge, is_lower);
+    _opnd_to_inedges_map_2st.
+        addEdgeSingleState(to->getID(), p_edge, is_lower);
 }
 
 void InequalityGraph::addOpnd(IOpnd* opnd)
@@ -152,6 +226,35 @@
     os << "}" << std::endl;
 }
 
+void InequalityGraph::printEdge(std::ostream& os, IneqEdge* e, PrnEdgeType t) const
+{
+    IOpnd* from_opnd = e->getSrc();
+    IOpnd* to_opnd = e->getDst();
+    os << "\""; from_opnd->printName(os); os << "\"";
+    os << " -> ";
+    os << "\""; to_opnd->printName(os); os << "\"";
+    os << " [label=\"" << e->getLength() << "\"";
+    switch (t) {
+        case tPERM_EDGE  : break;
+        case tLOWER_EDGE : os << "color=\"red\""; break;
+        case tUPPER_EDGE : os << "color=\"blue\""; break;
+    };
+    os << "];" << std::endl;
+}
+
+void InequalityGraph::printListWithSetExcluded (std::ostream& os, 
+    EdgeSet* edge_set, EdgeList* elist, PrnEdgeType ptype) const
+{
+    EdgeList::iterator it = elist->begin(),
+        end = elist->end();
+    for (; it != end; it++) {
+        IneqEdge* edge = (*it);
+        if ( edge_set->count(edge) == 0 ) {
+            printEdge(os, edge, ptype);
+        }
+    }
+}
+
 void InequalityGraph::printDotBody(std::ostream& os) const
 {
     IdToOpndMap::const_iterator it = _id_to_opnd_map.begin(), 
@@ -163,19 +266,31 @@
         opnd->printFullName(os);
         os << "}\"];" << std::endl;
     }
+
+    MemoryManager print_graph_mm("InequalityGraph::printDotBody.mm");
+    EdgeSet edge_set(print_graph_mm);
+
     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;
+        TwoStateEdgeList* out_list =
+            _opnd_to_outedges_map_2st.get2stListByOpnd(from_opnd);
+        if ( !out_list ) {
+            continue;
         }
+        EdgeList *perm_lst = out_list->getPermanentEdgeList(),
+              *lower_lst = out_list->getOneStateEdgeList(true /* lower */ ),
+              *upper_lst = out_list->getOneStateEdgeList(false/* upper */ );
+
+        edge_set.clear();
+        EdgeList::iterator out_lst_it = perm_lst->begin(),
+            out_lst_end = perm_lst->end();
+        for (;out_lst_it != out_lst_end; out_lst_it++) {
+            IneqEdge* edge = (*out_lst_it);
+            edge_set.insert(edge);
+            printEdge(os, edge, tPERM_EDGE);
+        }
+        printListWithSetExcluded(os, &edge_set, lower_lst, tLOWER_EDGE);
+        printListWithSetExcluded(os, &edge_set, upper_lst, tUPPER_EDGE);
     }
 }
 
@@ -187,6 +302,7 @@
     }
     return it->second;
 }
+
 //------------------------------------------------------------------------------
 
 TrueReducedFalseChart* BoundAllocator::create_empty_TRFChart()
@@ -553,11 +669,10 @@
                                                            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);
+    InequalityGraph::edge_iterator in_it = _igraph.inEdgesBegin(dest);
+    InequalityGraph::edge_iterator in_end = _igraph.inEdgesEnd(dest);
+    assert(in_it != in_end);
+    IneqEdge* in_edge = in_it.get();
     assert(in_edge->getDst() == dest);
     ProveResult res;
     assert(!_mem_distance.hasLeqBoundResult(dest, bound));
@@ -565,8 +680,8 @@
                 _bound_alloc.create_dec_const(bound, 
                                               in_edge->getLength()),
                 prn_level + 1);
-    in_iter++;
-    for (; in_iter != in_last; in_iter++) {
+    in_it.next();
+    for (; in_it != in_end; in_it.next()) {
         if(((res >= Reduced)  && (meet_f == meetBest)) ||
            ((res == False) && (meet_f == meetWorst))) {
             // For any x, meetBest(True, x)    == True
@@ -580,7 +695,7 @@
             }
             break;
         }
-        in_edge = (*in_iter);
+        in_edge = in_it.get();
         assert(in_edge->getDst() == dest);
         IOpnd* pred = in_edge->getSrc();
         res = meet_f(res, 
@@ -648,7 +763,9 @@
     }
     
     // if dest has no predecessor then fail
-    if ( _igraph.getInEdges(dest).empty() ) {
+    InequalityGraph::edge_iterator in_it = _igraph.inEdgesBegin(dest);
+    InequalityGraph::edge_iterator in_end = _igraph.inEdgesEnd(dest);
+    if ( in_it == in_end ) {
         prn.prnStrLn("no predecessors => False");
         return False;
     }
@@ -976,6 +1093,7 @@
     graph.addEdge(0, 1, 3);
     graph.addEdge(1, 2, -3);
     graph.addEdge(2, 0, 1);
+
     graph.printDotFile(std::cout);
 }
 
@@ -1057,18 +1175,175 @@
     //g.printDotFile(std::cout);
 
     intmax.setConstant(25);
-    (*g.getOutEdges(&i2).begin())->setLength(INT_MAX - 5);
+    InequalityGraph::edge_iterator it = g.outEdgesBegin(&i2);
+    it.get()->setLength(INT_MAX - 5);
     //g.printDotFile(std::cout);
     assert(!solver.demandProve(&zero, &i2, 0, false));
     //logfile << " testOverflow: OK" << std::endl;
 }
 
+void verifyNodesRange
+     (const uint32* ids_gold, uint32 id_count,
+      const InequalityGraph::edge_iterator& begin_range,
+      const InequalityGraph::edge_iterator& end_range, bool check_src_nodes)
+{
+    // note: this implementation is intended for use with small arrays,
+    //    it is far from optimal asymptotically
+    InequalityGraph::edge_iterator it = begin_range;
+    InequalityGraph::edge_iterator end = end_range;
+    uint32 found_count = 0;
+    for (; it != end; it.next()) {
+        IneqEdge* edge = it.get();
+        IOpnd* op = check_src_nodes ? edge->getSrc() : edge->getDst();
+        uint32 op_id = op->getID();
+        bool found = false;
+        for (uint32 i = 0; i < id_count; i++) {
+            if ( op_id == ids_gold[i] ) {
+                found = true;
+                found_count++;
+            }
+        }
+        assert(found);
+    }
+    assert(found_count == id_count);
+}
+
+void assertInNodesEqual(InequalityGraph& g,
+     IOpnd& opnd, const uint32* ids_gold, uint32 id_count)
+{
+    const InequalityGraph::edge_iterator in_iter = g.inEdgesBegin(&opnd),
+          in_end = g.inEdgesEnd(&opnd);
+    verifyNodesRange(ids_gold, id_count,
+            in_iter, in_end, true /* check_src_nodes */);
+}
+
+void assertOutNodesEqual(InequalityGraph& g,
+     IOpnd& opnd, const uint32* ids_gold, uint32 id_count)
+{
+    const InequalityGraph::edge_iterator out_iter = g.outEdgesBegin(&opnd),
+          out_end = g.outEdgesEnd(&opnd);
+
+    verifyNodesRange(ids_gold, id_count,
+            out_iter, out_end, false /* check_src_nodes */);
+}
+
+void testTwoStateOpndToEdgeListMap()
+{
+    MemoryManager mm("testTwoStateOpndToEdgeListMap.MemoryManager");
+    TwoStateOpndToEdgeListMap edges_map_2st(mm);
+
+    IOpnd o0(0), o1(1), o2(2), o3(3), o4(4);
+    IneqEdge e1(&o0, &o1, 0),
+             e2(&o0, &o2, 0),
+             e3(&o0, &o3, 0);
+
+    // e1: o0, o1
+    // e2: o0, o2
+    // e3: o0, o3 .. not_lower
+    edges_map_2st.addEdge(1, &e1);
+    edges_map_2st.addEdge(1, &e2);
+    edges_map_2st.addEdgeSingleState(1, &e3, false);
+
+    edges_map_2st.setState(false);
+    {
+        TwoStateEdgeList::iterator it = edges_map_2st.eListBegin(1),
+            it_end = edges_map_2st.eListEnd(1);
+        uint32 found = 0;
+        for (; it != it_end; it.next() ) {
+            IneqEdge* e = it.get();
+            assert(e == &e1 || e == &e2 || e == &e3);
+            found++;
+        }
+        assert(found == 3);
+    }
+
+    edges_map_2st.setState(true);
+    {
+        TwoStateEdgeList::iterator it = edges_map_2st.eListBegin(1),
+            it_end = edges_map_2st.eListEnd(1);
+        uint32 found = 0;
+        for (; it != it_end; it.next() ) {
+            IneqEdge* e = it.get();
+            assert(e == &e1 || e == &e2);
+            found++;
+        }
+        assert(found == 2);
+    }
+}
+
+void testBasicIGraphOperations()
+{
+    MemoryManager mm("testOverflow.MemoryManager");
+    InequalityGraph 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.getID(), i3.getID(), 1);
+    g.addEdge(&i3, &i1, 0);
+    g.addEdge(&length, &i2, -1);
+
+    g.addEdgeSingleState(&length, &i1, -1, true /* is_lower */);
+    g.addEdgeSingleState(i3.getID(), i2.getID(), -1, false /* is_lower */);
+
+    g.setState(true /* is_lower */);
+    {
+        const uint32 i1_in_gold[] = {0, 3, length.getID()};
+        assertInNodesEqual(g, i1, i1_in_gold, 3);
+        const uint32 i1_out_gold[] = {2};
+        assertOutNodesEqual(g, i1, i1_out_gold, 1);
+        const uint32 i2_in_gold[] = {1, length.getID()};
+        assertInNodesEqual(g, i2, i2_in_gold, 2);
+        const uint32 i3_out_gold[] = {1};
+        assertOutNodesEqual(g, i3, i3_out_gold, 1);
+    }
+
+    g.setState(false /* is_lower */);
+    {
+        const uint32 i1_in_gold[] = {0, 3};
+        assertInNodesEqual(g, i1, i1_in_gold, 2);
+        const uint32 i1_out_gold[] = {2};
+        assertOutNodesEqual(g, i1, i1_out_gold, 1);
+        const uint32 i2_in_gold[] = {1, length.getID(), 3};
+        assertInNodesEqual(g, i2, i2_in_gold, 3);
+        const uint32 i3_out_gold[] = {1, 2};
+        assertOutNodesEqual(g, i3, i3_out_gold, 2);
+    }
+
+    g.setState(true /* is_lower */);
+    {
+        const uint32 i3_out_gold[] = {1};
+        assertOutNodesEqual(g, i3, i3_out_gold, 1);
+    }
+    std::ofstream f;
+    f.open("testBasicIGraphOperations.dot");
+    g.printDotFile(f);
+}
+
 //------------------------------------------------------------------------------
 
 int classic_abcd_test_main()
 {
     std::cout << "running ABCD self-tests" << std::endl;
+    testTwoStateOpndToEdgeListMap();
     testMemoizedDistances();
+    testBasicIGraphOperations();
     testSimpleIGraph();
     testDoubleCycleGraph();
     testPaperIGraph();

Modified: 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=diff&rev=565011&r1=565010&r2=565011
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd_solver.h (original)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/classic_abcd_solver.h Sun Aug 12 00:52:37 2007
@@ -98,28 +98,216 @@
     int32 _length;
 };
 
+typedef StlList<IneqEdge*> EdgeList;
+typedef StlSet<IneqEdge*> EdgeSet;
+
+class TwoStateEdgeList {
+public:
+    TwoStateEdgeList(MemoryManager& mm) :
+        _mm(mm),
+        _permanent(mm),
+        _lower(mm),
+        _upper(mm),
+        _is_lower(false)
+    {
+    }
+
+    bool isLowerState() { return _is_lower; }
+
+    void addEdge(IneqEdge* edge)
+    {
+        _permanent.push_back(edge);
+    }
+
+    void addEdgeSingleState(IneqEdge *edge, bool is_lower)
+    {
+        EdgeList* list = is_lower ? (&_lower) : (&_upper);
+        list->push_back(edge);
+    }
+
+    // the iterator is 'invalidated' when the state of the TwoStateEdgeList
+    // changes
+    class iterator {
+    public:
+        void next()
+        {
+            if ( _first_it != _first_end ) {
+                _first_it++;
+            }else if ( _second_it != _second_end ) {
+                _second_it++;
+            }else{
+                assert(0);
+            }
+        }
+
+        IneqEdge* get()
+        {
+            if ( _first_it != _first_end ) {
+                return (*_first_it);
+            }else if ( _second_it != _second_end ) {
+                return (*_second_it);
+            }else{
+                return NULL;
+            }
+        }
+
+        bool operator==(iterator& other)
+        {
+            return _first_it == other._first_it &&
+                _second_it == other._second_it;
+        }
+
+        bool operator!=(iterator& other)
+        {
+            return !(*this == other);
+        }
+    private:
+        friend class TwoStateEdgeList;
+        iterator(EdgeList* first, EdgeList* second, bool is_end)
+        {
+            assert(first && second);
+            _first_end = first->end();
+            _second_end = second->end();
+            if ( !is_end ) {
+                _first_it = first->begin();
+                _second_it = second->begin();
+            }else{
+                _first_it = _first_end;
+                _second_it = _second_end;
+            }
+        }
+
+        void moveEnd()
+        {
+            _first_it = _first_end;
+            _second_it = _second_end;
+        }
+
+        EdgeList::iterator _first_it, _second_it, _first_end, _second_end;
+    };
+
+    iterator begin()
+    {
+        iterator ret(&_permanent, getSecond(), false /* is_end */);
+        return ret;
+    }
+
+    iterator end()
+    {
+        iterator ret(&_permanent, getSecond(), true);
+        return ret;
+    }
+
+    static iterator emptyIterator()
+    {
+        static MemoryManager mm("Memory Manager for EdgeList::empty_iterator");
+        static EdgeList* empty_list = new(mm) EdgeList(mm);
+        iterator ret(empty_list, empty_list, false /* is_end */);
+        return ret;
+    }
+
+private:
+    friend class TwoStateOpndToEdgeListMap;
+    friend class InequalityGraph;
+
+    void setState(bool is_lower) { _is_lower = is_lower; }
+
+    EdgeList* getSecond() { return getOneStateEdgeList(_is_lower); }
+
+    EdgeList* getPermanentEdgeList() { return &_permanent; }
+
+    EdgeList* getOneStateEdgeList(bool lower_state)
+    {
+        return lower_state ? &_lower : &_upper;
+    }
+
+    MemoryManager& _mm;
+    EdgeList _permanent, _lower, _upper;
+    bool _is_lower;
+};
+
+class TwoStateOpndToEdgeListMap {
+    typedef StlMap<uint32, TwoStateEdgeList* > MapIdTo2stList;
+public:
+    TwoStateOpndToEdgeListMap(MemoryManager& mm) :
+        _is_lower(false),
+        _mm(mm),
+        _map(mm)
+    {}
+
+    void setState(bool is_lower);
+
+    bool isLowerState() { return _is_lower; }
+
+    void addEdge(uint32 opnd_id, IneqEdge* edge);
+
+    void addEdgeSingleState(uint32 opnd_id, IneqEdge *edge, bool is_lower);
+
+    TwoStateEdgeList::iterator eListBegin(uint32 opnd_id) const;
+
+    TwoStateEdgeList::iterator eListEnd(uint32 opnd_id) const;
+private:
+    friend class InequalityGraph;
+
+    // return the corresponding list or NULL
+    TwoStateEdgeList* get2stListByOpnd(IOpnd* opnd) const
+    {
+        MapIdTo2stList::const_iterator it = _map.find(opnd->getID());
+        if ( it == _map.end() ) {
+            return NULL;
+        }
+        return it->second;
+    }
+
+    bool _is_lower;
+    MemoryManager& _mm;
+    MapIdTo2stList _map;
+};
+
 class InequalityGraph {
+public:
+    typedef TwoStateEdgeList::iterator edge_iterator;
+private:
     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)
+        _opnd_to_inedges_map_2st(mem_mgr),
+        _opnd_to_outedges_map_2st(mem_mgr),
+        _is_lower(false)
     {}
 
+    // Inequality Graph can be visible in two states: lower and upper
+    // In both states operands are the same. Some edges are visible in both
+    // states, some only in one of two
+    void setState(bool is_lower);
+
+    bool isLowerState() { return _is_lower; }
+
+    // add edge by operands visible in all states
     void addEdge(IOpnd* from, IOpnd* to, int32 distance);
 
+    // add edge by operand IDs visible in all states
     void addEdge(uint32 id_from, uint32 id_to, int32 distance);
 
+    // add edge by operand IDs visible in a given state
+    void addEdgeSingleState(uint32 id_from, uint32 id_to, int32 distance, bool is_lower);
+
+    // add edge by operands visible in a given state
+    void addEdgeSingleState(IOpnd* from, IOpnd* to, int32 distance, bool is_lower);
+
     void addOpnd(IOpnd* opnd);
 
-    const EdgeList& getInEdges(IOpnd* opnd) const;
+    edge_iterator inEdgesBegin(IOpnd* opnd) const;
 
-    const EdgeList& getOutEdges(IOpnd* opnd) const;
+    edge_iterator inEdgesEnd(IOpnd* opnd) const;
+
+    edge_iterator outEdgesBegin(IOpnd* opnd) const;
+
+    edge_iterator outEdgesEnd(IOpnd* opnd) const;
 
     void printDotFile(std::ostream& os) const;
 
@@ -139,14 +327,31 @@
     void printDotBody(std::ostream& os) const;
     void printDotEnd(std::ostream& os) const;
 
-    void addEdgeToIdMap (OpndEdgeMap& mp, uint32 id, IneqEdge* edge);
+    IOpnd* getOpndById(uint32 id) const;
+
+    enum PrnEdgeType
+    {
+        tPERM_EDGE,
+        tLOWER_EDGE,
+        tUPPER_EDGE
+    };
+
+    void printEdge(std::ostream& os, IneqEdge* e, PrnEdgeType t) const;
+
+    void prnDotEdgeList
+        (std::ostream& os, IOpnd* from_opnd, 
+         EdgeList* lst, PrnEdgeType type) const;
+
+    void printListWithSetExcluded (std::ostream& os,
+         StlSet<IneqEdge*>* edge_set, EdgeList* elist, PrnEdgeType ptype) const;
 
     MemoryManager& _mem_mgr;
     IdToOpndMap _id_to_opnd_map;
     EdgeList _edges;
 
-    OpndEdgeMap _opnd_to_inedges_map, _opnd_to_outedges_map;
-    EdgeList _emptyList;
+    TwoStateOpndToEdgeListMap
+        _opnd_to_inedges_map_2st, _opnd_to_outedges_map_2st;
+    bool _is_lower;
 };
 
 class Bound : public HasBoundState {

Modified: harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/insertpi.cpp
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/insertpi.cpp?view=diff&rev=565011&r1=565010&r2=565011
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/insertpi.cpp (original)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/insertpi.cpp Sun Aug 12 00:52:37 2007
@@ -827,9 +827,6 @@
     const PiBound &lb = cond.getLb();
     const PiBound &ub = cond.getUb();
 
-    if((_problemType == Lower) && lb.isUndefined()) return;
-    else if((_problemType == Upper) && ub.isUndefined()) return;
-
     if (_useAliases) {
         if (Log::isEnabled()) {
             Log::out() << "Inserting Pi Node for opnd ";

Modified: harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/insertpi.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/insertpi.h?view=diff&rev=565011&r1=565010&r2=565011
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/insertpi.h (original)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/abcd/insertpi.h Sun Aug 12 00:52:37 2007
@@ -30,18 +30,11 @@
 
 class InsertPi {
 public:
-    enum ProblemType {
-        Upper = 2,
-        Lower = 1,
-        Both = 0
-    };
-
     InsertPi(MemoryManager& mm, DominatorTree& dom_tree, IRManager& irm, 
-             bool use_aliases, ProblemType type = Both) :
+             bool use_aliases) :
         _mm(mm), 
         _domTree(dom_tree), 
         _useAliases(use_aliases),
-        _problemType(type),
         _irManager(irm),
         _blockTauEdge(0),
         _lastTauEdgeBlock(0),
@@ -107,7 +100,6 @@
     MemoryManager& _mm;
     DominatorTree& _domTree;
     bool _useAliases;
-    ProblemType _problemType;
     IRManager& _irManager;
 
     SsaTmpOpnd* _blockTauEdge;

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?view=diff&rev=565011&r1=565010&r2=565011
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/optimizer.cpp (original)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/optimizer.cpp Sun Aug 12 00:52:37 2007
@@ -167,6 +167,8 @@
     optimizerFlags.unguard_dcall_percent = getIntArg("unguard_dcall_percent", 30);
     optimizerFlags.unguard_dcall_percent_of_entry= getIntArg("unguard_dcall_percent_of_entry", 10);
 
+    //classic_abcd
+    optimizerFlags.dump_abcd_stats = getBoolArg("dump_abcd_stats", false);
 
     optimizerFlags.abcdFlags = new (mm) AbcdFlags;
     memset(optimizerFlags.abcdFlags, sizeof(AbcdFlags), 0);
@@ -208,6 +210,8 @@
     os << "    hvn_constants[={ON|off}]    - value-number constants from equality tests" << std::endl;
     os << "    sink_constants[={ON|off}]   - eliminate globals whose values are constant" << std::endl;
     os << "    sink_constants1[={on|OFF}]  - make sink_constants more aggressive" << std::endl;
+    os << "    dump_abcd_stats[={on|OFF}]  - dump (to bounds_checks.log) how many bounds checks "
+                                         << "were eliminated per method" << std::endl;
 
     Abcd::showFlags(os);
     GlobalCodeMotion::showFlags(os);

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?view=diff&rev=565011&r1=565010&r2=565011
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/optimizer.h (original)
+++ harmony/enhanced/drlvm/trunk/vm/jitrino/src/optimizer/optimizer.h Sun Aug 12 00:52:37 2007
@@ -101,6 +101,9 @@
     int unguard_dcall_percent;
     int unguard_dcall_percent_of_entry;
 
+    //classic_abcd
+    bool dump_abcd_stats;
+
 
     AbcdFlags*              abcdFlags;
     GcmFlags*               gcmFlags;



Mime
View raw message