diff From ba171adec61880c015fa8cf5a8071109ccabc8b1 Mon Sep 17 00:00:00 2001 From: Egor Pasko Date: Tue, 17 Jul 2007 00:44:22 +0400 Subject: [PATCH] Two state Inequality Graph with ABCD Stats option --- vm/jitrino/src/optimizer/abcd/classic_abcd.cpp | 426 ++++++++++++-------- vm/jitrino/src/optimizer/abcd/classic_abcd.h | 33 +- .../src/optimizer/abcd/classic_abcd_solver.cpp | 387 +++++++++++++++--- .../src/optimizer/abcd/classic_abcd_solver.h | 223 ++++++++++- vm/jitrino/src/optimizer/abcd/insertpi.cpp | 3 - vm/jitrino/src/optimizer/abcd/insertpi.h | 10 +- vm/jitrino/src/optimizer/optimizer.cpp | 4 + vm/jitrino/src/optimizer/optimizer.h | 3 + 8 files changed, 832 insertions(+), 257 deletions(-) diff --git a/vm/jitrino/src/optimizer/abcd/classic_abcd.cpp b/vm/jitrino/src/optimizer/abcd/classic_abcd.cpp index 2bc4ef9..b505ce4 100644 --- a/vm/jitrino/src/optimizer/abcd/classic_abcd.cpp +++ b/vm/jitrino/src/optimizer/abcd/classic_abcd.cpp @@ -80,6 +80,13 @@ private: }; //------------------------------------------------------------------------------ +// for debugging purposes +void printIOpnd(IOpnd* opnd) +{ + opnd->printName(std::cout); + std::cout << std::endl; +} + bool inInt32(int64 c) { return (int64)(int32)c == c; } @@ -144,18 +151,17 @@ uint32 IOpndProxy::getProxyIdByOpnd(Opnd 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 @@ private: 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); + void addDistanceSingleProblem(IOpndProxy* to, IOpndProxy* from, int64 c, + bool lower_problem); - // 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); + 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 + // constrints (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 OpndToPiInst2ElemMap; + OpndToPiInst2ElemMap _map_opnd_to_pi_inst; }; //------------------------------------------------------------------------------ - + IOpndProxy* BuildInequalityGraphWalker::findProxy(Opnd* opnd) { assert(_igraph); @@ -204,6 +231,28 @@ void BuildInequalityGraphWalker::addAllS } //------------------------------------------------------------------------------ +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 @@ void BuildInequalityGraphWalker::applyTo 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::applyTo } //------------------------------------------------------------------------------ +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 @@ bool BuildInequalityGraphWalker::addDist 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 @@ bool BuildInequalityGraphWalker::addEdge } //------------------------------------------------------------------------------ -/* - * 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 @@ private: }; //------------------------------------------------------------------------------ +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 @@ void ClassicAbcd::runPass() Log::out() << "ClassicAbcd pass started" << std::endl; } - StlMap 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 - IneqBuildDomWalker; - IneqBuildDomWalker dom_walker(igraph_walker); - DomTreeWalk(_domTree, dom_walker, ineq_mm); - - if ( Log::isEnabled() ) { - InequalityGraphPrinter printer(igraph); - printer.printDotFile(method_desc, "inequality.graph"); - } - - ClassicAbcdSolver solver(igraph, ineq_mm); + 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 + IneqBuildDomWalker; + IneqBuildDomWalker dom_walker(igraph_walker); + DomTreeWalk(_domTree, dom_walker, 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(); + 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 - IneqBuildDomWalker; - IneqBuildDomWalker dom_walker(igraph_walker); - DomTreeWalk(_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::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 @@ void ClassicAbcd::runPass() 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 "; @@ -572,6 +642,22 @@ void ClassicAbcd::runPass() } } + 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; } //------------------------------------------------------------------------------ diff --git a/vm/jitrino/src/optimizer/abcd/classic_abcd.h b/vm/jitrino/src/optimizer/abcd/classic_abcd.h index d1056dd..26cfd09 100644 --- a/vm/jitrino/src/optimizer/abcd/classic_abcd.h +++ b/vm/jitrino/src/optimizer/abcd/classic_abcd.h @@ -31,26 +31,39 @@ 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); - } - + 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 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 diff --git a/vm/jitrino/src/optimizer/abcd/classic_abcd_solver.cpp b/vm/jitrino/src/optimizer/abcd/classic_abcd_solver.cpp index 4291339..a5f6f28 100644 --- a/vm/jitrino/src/optimizer/abcd/classic_abcd_solver.cpp +++ b/vm/jitrino/src/optimizer/abcd/classic_abcd_solver.cpp @@ -38,6 +38,62 @@ void IOpnd::printFullName(std::ostream& } //------------------------------------------------------------------------------ +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) { @@ -48,38 +104,24 @@ bool InequalityGraph::has_other_opnd_wit 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 * new_list = new (_mem_mgr) StlList(_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) @@ -93,23 +135,55 @@ void InequalityGraph::addEdge(IOpnd* fro 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) @@ -151,6 +225,35 @@ void InequalityGraph::printDotEnd(std::o 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(), @@ -162,19 +265,31 @@ void InequalityGraph::printDotBody(std:: 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); } } @@ -186,6 +301,7 @@ IOpnd* InequalityGraph::findOpnd(uint32 } return it->second; } + //------------------------------------------------------------------------------ TrueReducedFalseChart* BoundAllocator::create_empty_TRFChart() @@ -552,11 +668,10 @@ void ClassicAbcdSolver::updateMemDistanc 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)); @@ -564,8 +679,8 @@ void ClassicAbcdSolver::updateMemDistanc _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 @@ -579,7 +694,7 @@ void ClassicAbcdSolver::updateMemDistanc } break; } - in_edge = (*in_iter); + in_edge = in_it.get(); assert(in_edge->getDst() == dest); IOpnd* pred = in_edge->getSrc(); res = meet_f(res, @@ -647,7 +762,9 @@ ProveResult ClassicAbcdSolver::prove(IOp } // 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; } @@ -975,6 +1092,7 @@ void printExampleGraph() graph.addEdge(0, 1, 3); graph.addEdge(1, 2, -3); graph.addEdge(2, 0, 1); + graph.printDotFile(std::cout); } @@ -1056,18 +1174,175 @@ void testOverflow() //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(); diff --git a/vm/jitrino/src/optimizer/abcd/classic_abcd_solver.h b/vm/jitrino/src/optimizer/abcd/classic_abcd_solver.h index 1934431..922a3ad 100644 --- a/vm/jitrino/src/optimizer/abcd/classic_abcd_solver.h +++ b/vm/jitrino/src/optimizer/abcd/classic_abcd_solver.h @@ -97,28 +97,216 @@ private: int32 _length; }; +typedef StlList EdgeList; +typedef StlSet 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 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 > OpndEdgeMap; + public: - typedef StlList 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; + + edge_iterator inEdgesEnd(IOpnd* opnd) const; + + edge_iterator outEdgesBegin(IOpnd* opnd) const; - const EdgeList& getOutEdges(IOpnd* opnd) const; + edge_iterator outEdgesEnd(IOpnd* opnd) const; void printDotFile(std::ostream& os) const; @@ -138,14 +326,31 @@ private: 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* 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 { diff --git a/vm/jitrino/src/optimizer/abcd/insertpi.cpp b/vm/jitrino/src/optimizer/abcd/insertpi.cpp index 75f60ad..8dfd686 100644 --- a/vm/jitrino/src/optimizer/abcd/insertpi.cpp +++ b/vm/jitrino/src/optimizer/abcd/insertpi.cpp @@ -827,9 +827,6 @@ void InsertPi::insertPiForOpndAndAliases 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 "; diff --git a/vm/jitrino/src/optimizer/abcd/insertpi.h b/vm/jitrino/src/optimizer/abcd/insertpi.h index fc13faa..ade3fd3 100644 --- a/vm/jitrino/src/optimizer/abcd/insertpi.h +++ b/vm/jitrino/src/optimizer/abcd/insertpi.h @@ -30,18 +30,11 @@ namespace Jitrino { 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 @@ private: MemoryManager& _mm; DominatorTree& _domTree; bool _useAliases; - ProblemType _problemType; IRManager& _irManager; SsaTmpOpnd* _blockTauEdge; diff --git a/vm/jitrino/src/optimizer/optimizer.cpp b/vm/jitrino/src/optimizer/optimizer.cpp index a661d5a..4b3a3fe 100644 --- a/vm/jitrino/src/optimizer/optimizer.cpp +++ b/vm/jitrino/src/optimizer/optimizer.cpp @@ -176,6 +176,8 @@ void OptInitAction::readFlags() 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); @@ -217,6 +219,8 @@ void showFlags(std::ostream& os) { 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); diff --git a/vm/jitrino/src/optimizer/optimizer.h b/vm/jitrino/src/optimizer/optimizer.h index 2bfdbaa..9fe25d5 100644 --- a/vm/jitrino/src/optimizer/optimizer.h +++ b/vm/jitrino/src/optimizer/optimizer.h @@ -101,6 +101,9 @@ struct OptimizerFlags { int unguard_dcall_percent; int unguard_dcall_percent_of_entry; + //classic_abcd + bool dump_abcd_stats; + AbcdFlags* abcdFlags; GcmFlags* gcmFlags;