You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by eg...@apache.org on 2007/08/12 09:52:38 UTC
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
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;