--- a/vm/jitrino/src/optimizer/Inst.h +++ b/vm/jitrino/src/optimizer/Inst.h @@ -1089,7 +1089,7 @@ protected: virtual void handlePrintEscape(::std::ostream&, char code) const; private: friend class InstFactory; - friend class Abcd; // needs to update the cond below; + friend class InsertPi; // needs to update the cond below; TauPiInst(Type::Tag type, Opnd* dst, Opnd* src, Opnd *tau, PiCondition *cond0) : Inst(Op_TauPi, Modifier(), type, dst, src, tau), cond(cond0) --- a/vm/jitrino/src/optimizer/abcd/abcd.cpp +++ b/vm/jitrino/src/optimizer/abcd/abcd.cpp @@ -94,688 +94,46 @@ void Abcd::showFlags(std::ostream& os) { os << " abcd.use_reasons[={ON|off}] - build more precise taus for eliminated instructions"; } -Abcd::Abcd(IRManager &irManager0, MemoryManager& memManager, DominatorTree& dom0) -: irManager(irManager0), -mm(memManager), -ineqGraph(0), -dominators(dom0), -piMap(0), -nextPiOpndId(0), -solver(0), -canEliminate(memManager), -canEliminateUB(memManager), -canEliminateLB(memManager), -tauUnsafe(0), -tauSafe(0), -blockTauPoint(0), -lastTauPointBlock(0), -blockTauEdge(0), -lastTauEdgeBlock(0), -flags(*irManager.getOptimizerFlags().abcdFlags) -{ -}; +Abcd::Abcd(IRManager &irManager0, MemoryManager& memManager, DominatorTree& dom0) : + irManager(irManager0), + mm(memManager), + dominators(dom0), + solver(0), + canEliminate(memManager), + canEliminateUB(memManager), + canEliminateLB(memManager), + tauUnsafe(0), + tauSafe(0), + flags(*irManager.getOptimizerFlags().abcdFlags), + insertPi(memManager, dom0, irManager0, flags.useAliases), + blockTauPoint(0), + lastTauPointBlock(0) +{} void Abcd::runPass() { - if (Log::isEnabled() || Log::isEnabled()) { + if ( Log::isEnabled() ) { Log::out() << "IR before ABCD pass" << std::endl; FlowGraph::printHIR(Log::out(), irManager.getFlowGraph(), irManager.getMethodDesc()); FlowGraph::printDotFile(irManager.getFlowGraph(), irManager.getMethodDesc(), "beforeabcd"); dominators.printDotFile(irManager.getMethodDesc(), "beforeabcd.dom"); } - insertPiNodes(); // add a pi node after each test on a variable - renamePiVariables(); // rename all uses to use the inserted Pi variables - - // WARNING: Pi var live ranges may overlap the original - // var live ranges here - - if (Log::isEnabled()) { - Log::out() << "IR after Pi insertion" << std::endl; - FlowGraph::printHIR(Log::out(), irManager.getFlowGraph(), irManager.getMethodDesc()); - FlowGraph::printDotFile(irManager.getFlowGraph(), irManager.getMethodDesc(), "withpi"); - } + insertPi.insertPi(); removeRedundantBoundsChecks(); - if (Log::isEnabled() || Log::isEnabled()) { + if ( Log::isEnabled() ) { Log::out() << "IR after removeRedundantBoundsChecks" << std::endl; FlowGraph::printHIR(Log::out(), irManager.getFlowGraph(), irManager.getMethodDesc()); } - removePiNodes(); - if (Log::isEnabled()) { + removePiEliminateChecks(); + if ( Log::isEnabled() ) { Log::out() << "IR after ABCD pass" << std::endl; FlowGraph::printHIR(Log::out(), irManager.getFlowGraph(), irManager.getMethodDesc()); } } -// a DomWalker, to be applied pre-order -class InsertPiWalker { - Abcd *thePass; -public: - void applyToDominatorNode(DominatorNode *domNode) { thePass->insertPiNodes(domNode->getNode()); }; - void enterScope() {}; // is called before a node and its children are processed - void exitScope() {}; // is called after node and children are processed - InsertPiWalker(Abcd *thePass0) : thePass(thePass0) {}; -}; - - -// Inserts Pi nodes. -// WARNING: Pi var live ranges may overlap the original var live ranges -// since we don't bother to add Phi nodes and rename subsequent uses of var. -void Abcd::insertPiNodes() -{ - // Add a Pi node on each branch after - // a test which tells something about a variable. - // For now, don't bother with Exception edges. - - InsertPiWalker insertPiWalker(this); - DomTreeWalk(dominators, insertPiWalker, mm); // pre-order -} - -PiOpnd *Abcd::getNewDestOpnd(Node *block, - Opnd *org) -{ - PiOpnd *tmpOp = irManager.getOpndManager().createPiOpnd(org); - return tmpOp; -} - -// a DomWalker, to be applied forwards/preorder -class RenamePiWalker { - Abcd *thePass; - MemoryManager &localMemManager; - SparseOpndMap* &piMap; - int sizeEstimate; -public: - void applyToDominatorNode(DominatorNode *domNode) { thePass->renamePiVariables(domNode->getNode()); }; - - void enterScope() { - if (!piMap) piMap = new (localMemManager) SparseOpndMap(sizeEstimate, - localMemManager, 1, 4, 7); - piMap->enter_scope(); }; - void exitScope() { piMap->exit_scope(); }; - RenamePiWalker(Abcd *thePass0, - MemoryManager &localMM, - SparseOpndMap* &piMap0, - int sizeEstimate0) - : thePass(thePass0), localMemManager(localMM), piMap(piMap0), - sizeEstimate(sizeEstimate0) - { - }; -}; - -// Renames variables for which we have Pi nodes. -void Abcd::renamePiVariables() -{ - MethodDesc &methodDesc= irManager.getMethodDesc(); - uint32 byteCodeSize = methodDesc.getByteCodeSize(); - MemoryManager localMemManager(byteCodeSize*16, - "Abcd::renamePiNodes"); - - RenamePiWalker theWalker(this, localMemManager, piMap, byteCodeSize); - DomTreeWalk(dominators, theWalker, - localMemManager); -} - - -void Abcd::insertPiNodeForOpnd(Node *block, - Opnd *org, - const PiCondition &cond, - Opnd *tauOpnd) -{ - if (ConstantFolder::isConstant(org)) { - if (Log::isEnabled()) { - Log::out() << "Skipping Pi Node for opnd "; - org->print(Log::out()); - Log::out() << " under condition "; - cond.print(Log::out()); - Log::out() << " since it is constant" << std::endl; - } - } else { - - PiOpnd *piOpnd = irManager.getOpndManager().createPiOpnd(org); - Inst *headInst = (Inst*)block->getFirstInst(); - PiCondition *condPtr = new (irManager.getMemoryManager()) PiCondition(cond); - if (tauOpnd == 0) - tauOpnd = getBlockTauEdge(block); - Inst *newInst = irManager.getInstFactory().makeTauPi(piOpnd, org, tauOpnd, condPtr); - Inst *place = headInst->getNextInst(); - while (place != NULL) { - Opcode opc = place->getOpcode(); - if ((opc != Op_Phi) && (opc != Op_TauPoint) && (opc != Op_TauEdge)) - break; - place = place->getNextInst(); - } - if (Log::isEnabled()) { - Log::out() << "Inserting Pi Node for opnd "; - org->print(Log::out()); - Log::out() << " under condition "; - cond.print(Log::out()); - if (place!=NULL) { - Log::out() << " just before inst "; - place->print(Log::out()); - } - Log::out() << std::endl; - } - if (place != NULL) { - newInst->insertBefore(place); - } else { - block->appendInst(newInst); - } - } -} - -void Abcd::insertPiNodeForOpndAndAliases(Node *block, - Opnd *org, - const PiCondition &cond, - Opnd *tauOpnd) -{ - if (flags.useAliases) { - if (Log::isEnabled()) { - Log::out() << "Inserting Pi Node for opnd "; - org->print(Log::out()); - Log::out() << " and its aliases"; - Log::out() << " under condition "; - cond.print(Log::out()); - Log::out() << std::endl; - } - AbcdAliases aliases(mm); - // check for aliases - insertPiNodeForOpnd(block, org, cond, tauOpnd); - if (getAliases(org, &aliases, 0)) { - if (Log::isEnabled()) { - Log::out() << "Has aliases "; - AbcdAliasesSet::iterator iter = aliases.theSet.begin(); - AbcdAliasesSet::iterator end = aliases.theSet.end(); - for ( ; iter != end; iter++) { - PiBound alias = *iter; - alias.print(Log::out()); - Log::out() << " "; - } - Log::out() << std::endl; - } - AbcdAliasesSet::iterator iter = aliases.theSet.begin(); - AbcdAliasesSet::iterator end = aliases.theSet.end(); - const PiBound &lb = cond.getLb(); - const PiBound &ub = cond.getUb(); - for ( ; iter != end; iter++) { - PiBound alias = *iter; - PiBound inverted = alias.invert(org); // org - c - // plug-in lb and ub into inverted, yields bounds: - // [ lb - c, ub - c ] - PiCondition renamedCondition(PiBound(inverted, org, lb), - PiBound(inverted, org, ub)); - insertPiNodeForOpnd(block, alias.getVar().the_var, - renamedCondition, tauOpnd); - } - } - } else { - insertPiNodeForOpnd(block, org, cond, tauOpnd); - } -} - -static ComparisonModifier -negateComparison(ComparisonModifier mod) -{ - switch (mod) { - case Cmp_GT: return Cmp_GTE; - case Cmp_GT_Un: return Cmp_GTE_Un; - case Cmp_GTE: return Cmp_GT; - case Cmp_GTE_Un: return Cmp_GT_Un; - case Cmp_EQ: return Cmp_EQ; - case Cmp_NE_Un: return Cmp_NE_Un; - default: - assert(0); return mod; - } -} - -static const char * -printableComparison(ComparisonModifier mod) -{ - switch (mod) { - case Cmp_GT: return "Cmp_GT"; - case Cmp_GT_Un: return "Cmp_GT_Un"; - case Cmp_GTE: return "Cmp_GTE"; - case Cmp_GTE_Un: return "Cmp_GTE_Un"; - case Cmp_EQ: return "Cmp_EQ"; - case Cmp_NE_Un: return "Cmp_NE_Un"; - default: - assert(0); return ""; - } -} - -static Type::Tag -unsignType(Type::Tag typetag) -{ - switch (typetag) { - case Type::IntPtr: return Type::UIntPtr; - case Type::Int8: return Type::UInt8; - case Type::Int16: return Type::UInt16; - case Type::Int32: return Type::UInt32; - case Type::Int64: return Type::UInt64; - default: - assert(0); return typetag; - } -} - -void Abcd::insertPiNodesForComparison(Node *block, - ComparisonModifier mod, - const PiCondition &bounds, - Opnd *op, - bool swap_operands, - bool negate_comparison) -{ - if (Log::isEnabled()) { - Log::out() << "insertPiNodesForComparison(..., "; - Log::out() << printableComparison(mod); - Log::out() << ", "; - bounds.print(Log::out()); - Log::out() << ", "; - op->print(Log::out()); - Log::out() << ", "; - Log::out() << (swap_operands ? "true" : "false"); - Log::out() << (negate_comparison ? "true" : "false"); - Log::out() << std::endl; - } - - PiCondition bounds0 = bounds; - // add a Pi node for immediate value. - if (negate_comparison) { - mod = negateComparison(mod); - swap_operands = !swap_operands; - if (Log::isEnabled()) { - Log::out() << "insertPiNodesForComparison: negating comparison to " ; - Log::out() << printableComparison(mod); - Log::out() << std::endl; - } - } - switch (mod) { - case Cmp_EQ: - if (!negate_comparison) - insertPiNodeForOpndAndAliases(block, op, bounds0); - else { - if (Log::isEnabled()) { - Log::out() << "insertPiNodesForComparison: cannot represent ! Cmp_EQ" << std::endl; - } - } - // we can't represent the other case - break; - case Cmp_NE_Un: - if (negate_comparison) - insertPiNodeForOpndAndAliases(block, op, bounds0); - else { - if (Log::isEnabled()) { - Log::out() << "insertPiNodesForComparison: cannot represent Cmp_NE_Un" << std::endl; - } - } - // we can't represent the other case - break; - case Cmp_GT_Un: - if (swap_operands) { // op > bounds, only a lower bound on op - Type::Tag optag = op->getType()->tag; - if (!Type::isUnsignedInteger(optag)) { - // 1 is a lower bound on int op - PiCondition oneBounds(PiBound(optag, (int64)1), - PiBound(optag, (int64)1)); - PiCondition oneLowerBound(oneBounds.only_lower_bound()); - insertPiNodeForOpndAndAliases(block, op, oneLowerBound); - } else { - // we can be more precise for an unsigned op - bounds0 = bounds0.cast(unsignType(bounds0.getType())); - PiCondition bounds1a(bounds0.only_lower_bound()); - PiCondition bounds1(bounds1a.add((int64)1)); - if (! bounds1.getLb().isUnknown()) - insertPiNodeForOpndAndAliases(block, op, bounds1); - else { - if (Log::isEnabled()) { - Log::out() << "insertPiNodesForComparison(1): bounds1 LB is Unknown;\n\tbounds is "; - bounds.print(Log::out()); - Log::out() << "\n\tbounds0 is "; - bounds0.print(Log::out()); - Log::out() << "\n\tbounds1a is "; - bounds1a.print(Log::out()); - Log::out() << "\n\tbounds1 is "; - bounds1.print(Log::out()); - Log::out() << std::endl; - } - } - } - } else { // bounds > op, only an upper bound on op - Type::Tag optag = op->getType()->tag; - if (Type::isUnsignedInteger(optag)) { - // for an unsigned upper bound, we're ok - bounds0 = bounds0.cast(unsignType(bounds0.getType())); - PiCondition bounds1(bounds0.only_upper_bound().add((int64)-1)); - if (! bounds1.getUb().isUnknown()) - insertPiNodeForOpndAndAliases(block, op, bounds1); - else { - if (Log::isEnabled()) { - Log::out() << "insertPiNodesForComparison(2): bounds1 LB is Unknown;\n\tbounds is "; - bounds.print(Log::out()); - Log::out() << "\n\tbounds0 is "; - bounds0.print(Log::out()); - Log::out() << "\n\tbounds1 is "; - bounds1.print(Log::out()); - Log::out() << std::endl; - } - } - } else { - // otherwise, we know nothing unless bound is a small constant - PiCondition bounds1(bounds0.only_upper_bound().add((int64)-1)); - if (bounds0.getUb().isConstant()) { - int64 ubConst = bounds1.getUb().getConst(); - if (((optag == Type::Int32) && - ((ubConst&0xffffffff) <= 0x7ffffff) && - ((ubConst&0xffffffff) >= 0)) || - ((optag == Type::Int64) && - ((ubConst <= 0x7ffffff) && - (ubConst >= 0)))) { - insertPiNodeForOpndAndAliases(block, op, bounds1); - } else { - if (Log::isEnabled()) { - Log::out() << "insertPiNodesForComparison(2): bounds1 LB is Unknown;\n\tbounds is "; - bounds.print(Log::out()); - Log::out() << "\n\tbounds0 is "; - bounds0.print(Log::out()); - Log::out() << "\n\tbounds1 is "; - bounds1.print(Log::out()); - Log::out() << std::endl; - } - } - } - } - } - break; - case Cmp_GT: - if (swap_operands) { // op > bounds, only a lower bound on op - PiCondition bounds1a(bounds0.only_lower_bound()); - PiCondition bounds1(bounds1a.add((int64)1)); - if (! bounds1.getLb().isUnknown()) - insertPiNodeForOpndAndAliases(block, op, bounds1); - else { - if (Log::isEnabled()) { - Log::out() << "insertPiNodesForComparison(1): bounds1 LB is Unknown;\n\tbounds is "; - bounds.print(Log::out()); - Log::out() << "\n\tbounds0 is "; - bounds0.print(Log::out()); - Log::out() << "\n\tbounds1a is "; - bounds1a.print(Log::out()); - Log::out() << "\n\tbounds1 is "; - bounds1.print(Log::out()); - Log::out() << std::endl; - } - } - } else { // bounds > op, only an upper bound on op - PiCondition bounds1(bounds0.only_upper_bound().add((int64)-1)); - if (! bounds1.getUb().isUnknown()) - insertPiNodeForOpndAndAliases(block, op, bounds1); - else { - if (Log::isEnabled()) { - Log::out() << "insertPiNodesForComparison(2): bounds1 LB is Unknown;\n\tbounds is "; - bounds.print(Log::out()); - Log::out() << "\n\tbounds0 is "; - bounds0.print(Log::out()); - Log::out() << "\n\tbounds1 is "; - bounds1.print(Log::out()); - Log::out() << std::endl; - } - } - } - break; - case Cmp_GTE_Un: - if (swap_operands) { // op >= bounds, only lower bound on op - Type::Tag optag = op->getType()->tag; - if (!Type::isUnsignedInteger(optag)) { - // 0 is a lower bound on an int op - PiCondition zeroBounds(PiBound(optag, (int64)0), - PiBound(optag, (int64)0)); - PiCondition zeroLowerBound(zeroBounds.only_lower_bound()); - insertPiNodeForOpndAndAliases(block, op, zeroLowerBound); - } else { - // we can be more precise for an unsigned op lb - bounds0 = bounds0.cast(unsignType(bounds0.getType())); - if (! bounds0.getLb().isUnknown()) { - insertPiNodeForOpndAndAliases(block, op, - bounds0.only_lower_bound()); - } else { - if (Log::isEnabled()) { - Log::out() << "insertPiNodesForComparison(3): bounds0 LB is Unknown;\n\tbounds is "; - bounds.print(Log::out()); - Log::out() << "\n\tbounds0 is "; - bounds0.print(Log::out()); - Log::out() << std::endl; - } - } - } - } else { // bounds >= op, only upper bound on op - Type::Tag optag = op->getType()->tag; - if (Type::isUnsignedInteger(optag)) { - // unsigned ub on unsigned op - bounds0 = bounds0.cast(unsignType(bounds0.getType())); - if (! bounds0.getUb().isUnknown()) - insertPiNodeForOpndAndAliases(block, op, - bounds0.only_upper_bound()); - else { - if (Log::isEnabled()) { - Log::out() << "insertPiNodesForComparison(4): bounds0 UB is Unknown;\n\tbounds is "; - bounds.print(Log::out()); - Log::out() << "\n\tbounds0 is "; - bounds0.print(Log::out()); - Log::out() << std::endl; - } - } - } else { - // otherwise, we know nothing unless bound is a small constant - if (bounds0.getUb().isConstant()) { - int64 ubConst = bounds0.getUb().getConst(); - if (((optag == Type::Int32) && - ((ubConst&0xffffffff) <= 0x7ffffff) && - ((ubConst&0xffffffff) >= 0)) || - ((optag == Type::Int64) && - ((ubConst <= 0x7ffffff) && - (ubConst >= 0)))) { - insertPiNodeForOpndAndAliases(block, op, bounds0); - } else { - if (Log::isEnabled()) { - Log::out() << "insertPiNodesForComparison(2): bounds0 LB is Unknown;\n\tbounds is "; - bounds.print(Log::out()); - Log::out() << "\n\tbounds0 is "; - bounds0.print(Log::out()); - Log::out() << std::endl; - } - } - } - } - } - break; - case Cmp_GTE: - if (swap_operands) { // op >= bounds, only lower bound on op - if (! bounds0.getLb().isUnknown()) { - insertPiNodeForOpndAndAliases(block, op, - bounds0.only_lower_bound()); - } else { - if (Log::isEnabled()) { - Log::out() << "insertPiNodesForComparison(3): bounds0 LB is Unknown;\n\tbounds is "; - bounds.print(Log::out()); - Log::out() << "\n\tbounds0 is "; - bounds0.print(Log::out()); - Log::out() << std::endl; - } - } - } else { // bounds >= op, only upper bound on op - if (! bounds0.getUb().isUnknown()) - insertPiNodeForOpndAndAliases(block, op, - bounds0.only_upper_bound()); - else { - if (Log::isEnabled()) { - Log::out() << "insertPiNodesForComparison(4): bounds0 UB is Unknown;\n\tbounds is "; - bounds.print(Log::out()); - Log::out() << "\n\tbounds0 is "; - bounds0.print(Log::out()); - Log::out() << std::endl; - } - } - } - break; - case Cmp_Zero: - case Cmp_NonZero: - case Cmp_Mask: - assert(0); - break; - default: - assert(false); - break; - } -} - -// Insert Pi Nodes for any variables occurring in the branch test -// -// Since we're examining the test anyway, let's figure out the conditions -// here, too, so we don't have to duplicate any code. Note that this -// condition may already be in terms of Pi variables from the predecessor -// block, since -// -- predecessor dominates this block -// -- we are traversing blocks in a dominator-tree preorder -// so we must have already visited the predecessor. -// -// We also must add the new Pi variable to our map. -// -void Abcd::insertPiNodesForBranch(Node *block, BranchInst *branchi, - Edge::Kind kind) // True or False only -{ - Type::Tag instTypeTag = branchi->getType(); - if (!Type::isInteger(instTypeTag)) - return; - ComparisonModifier mod = branchi->getComparisonModifier(); - if (branchi->getNumSrcOperands() == 1) { - Opnd *op0 = branchi->getSrc(0); - PiCondition zeroBounds(PiBound(instTypeTag, (int64)0), - PiBound(instTypeTag, (int64)0)); - switch (mod) { - case Cmp_Zero: - insertPiNodesForComparison(block, - Cmp_EQ, - zeroBounds, - op0, - false, - (kind == Edge::Kind_False)); // negate if false edge - break; - case Cmp_NonZero: - insertPiNodesForComparison(block, - Cmp_EQ, // use EQ - zeroBounds, - op0, - false, - (kind == Edge::Kind_True)); // but negate if true edge - break; - default: - break; - } - } else { - Opnd *op0 = branchi->getSrc(0); - Opnd *op1 = branchi->getSrc(1); - assert(branchi->getNumSrcOperands() == 2); - PiCondition bounds0(op0->getType()->tag, op0); - PiCondition bounds1(op1->getType()->tag, op1); - if (!bounds0.isUnknown()) { - insertPiNodesForComparison(block, - mod, - bounds0, - op1, - false, - (kind == Edge::Kind_False)); // negate for false edge - } - if (!bounds1.isUnknown()) { - insertPiNodesForComparison(block, - mod, - bounds1, - op0, - true, - (kind == Edge::Kind_False)); // negate for false edge - } - } -} - -SsaTmpOpnd* Abcd::getBlockTauPoint(Node *block) { - if ((lastTauPointBlock == block) && blockTauPoint) return blockTauPoint; - Inst *firstInst = (Inst*)block->getFirstInst(); - Inst *inst = (Inst*)firstInst->getNextInst(); - for (; inst != NULL; inst = inst->getNextInst()) { - if (inst->getOpcode() == Op_TauPoint) { - blockTauPoint = inst->getDst()->asSsaTmpOpnd(); - assert(blockTauPoint); - lastTauPointBlock = block; - return blockTauPoint; - } - } - for (inst = firstInst->getNextInst(); inst != NULL; inst = inst->getNextInst()) { - if (inst->getOpcode() != Op_Phi) { - break; // insert before inst. - } - } - // no non-phis, insert before inst; - TypeManager &tm = irManager.getTypeManager(); - SsaTmpOpnd *tauOpnd = irManager.getOpndManager().createSsaTmpOpnd(tm.getTauType()); - Inst* tauPoint = irManager.getInstFactory().makeTauPoint(tauOpnd); - if(Log::isEnabled()) { - Log::out() << "Inserting tauPoint inst "; - tauPoint->print(Log::out()); - if (inst!=NULL) { - Log::out() << " before inst "; - inst->print(Log::out()); - } - Log::out() << std::endl; - } - if (inst!=NULL) { - tauPoint->insertBefore(inst); - } else { - block->appendInst(tauPoint); - } - blockTauPoint = tauOpnd; - lastTauPointBlock = block; - return tauOpnd; -} - -SsaTmpOpnd* Abcd::getBlockTauEdge(Node *block) { - if ((lastTauEdgeBlock == block) && blockTauEdge) return blockTauEdge; - Inst *firstInst = (Inst*)block->getFirstInst(); - Inst *inst = firstInst->getNextInst(); - for (; inst != NULL; inst = inst->getNextInst()) { - if (inst->getOpcode() == Op_TauEdge) { - blockTauEdge = inst->getDst()->asSsaTmpOpnd(); - assert(blockTauEdge); - lastTauEdgeBlock = block; - return blockTauEdge; - } - } - for (inst = firstInst->getNextInst(); inst != NULL; inst = inst->getNextInst()) { - if ((inst->getOpcode() != Op_Phi) && (inst->getOpcode() != Op_TauPoint)) { - break; // insert before inst. - } - } - // no non-phis, insert before inst; - TypeManager &tm = irManager.getTypeManager(); - SsaTmpOpnd *tauOpnd = irManager.getOpndManager().createSsaTmpOpnd(tm.getTauType()); - Inst* tauEdge = irManager.getInstFactory().makeTauEdge(tauOpnd); - if(Log::isEnabled()) { - Log::out() << "Inserting tauEdge inst "; - tauEdge->print(Log::out()); - if (inst!=NULL) { - Log::out() << " before inst "; - inst->print(Log::out()); - } - Log::out() << std::endl; - } - if (inst != NULL) { - tauEdge->insertBefore(inst); - } else { - block->appendInst(tauEdge); - } - blockTauEdge = tauOpnd; - lastTauEdgeBlock = block; - return tauOpnd; -} - SsaTmpOpnd* Abcd::getTauUnsafe() { if (!tauUnsafe) { Node *head = irManager.getFlowGraph().getEntryNode(); @@ -868,326 +226,6 @@ SsaTmpOpnd* Abcd::getTauSafe() { return tauSafe; }; -void Abcd::insertPiNodesForUnexceptionalPEI(Node *block, Inst *lasti) -{ - switch (lasti->getOpcode()) { - case Op_TauCheckBounds: - { - // the number of newarray elements must be >= 0. - assert(lasti->getNumSrcOperands() == 2); - Opnd *idxOp = lasti->getSrc(1); - Opnd *boundsOp = lasti->getSrc(0); - - if (Log::isEnabled()) { - Log::out() << "Adding info about CheckBounds instruction "; - lasti->print(Log::out()); - Log::out() << std::endl; - } - Type::Tag typetag = idxOp->getType()->tag; - PiBound lb(typetag, int64(0)); - PiBound ub(typetag, 1, VarBound(boundsOp),int64(-1)); - PiCondition bounds0(lb, ub); - Opnd *tauOpnd = lasti->getDst(); // use the checkbounds tau - insertPiNodeForOpndAndAliases(block, idxOp, bounds0, tauOpnd); - - PiBound idxBound(typetag, 1, VarBound(idxOp), int64(1)); - PiCondition bounds1(idxBound, PiBound(typetag, false)); - insertPiNodeForOpndAndAliases(block, boundsOp, bounds1, tauOpnd); - } - break; - case Op_NewArray: - { - // the number of newarray elements must be in [0, MAXINT32] - assert(lasti->getNumSrcOperands() == 1); - Opnd *numElemOpnd = lasti->getSrc(0); - if (Log::isEnabled()) { - Log::out() << "Adding info about NewArray instruction "; - lasti->print(Log::out()); - Log::out() << std::endl; - } - Opnd *tauOpnd = getBlockTauEdge(block); // need to use a TauEdge - PiCondition bounds0(PiBound(numElemOpnd->getType()->tag, int64(0)), - PiBound(numElemOpnd->getType()->tag, int64(0x7fffffff))); - insertPiNodeForOpndAndAliases(block, numElemOpnd, bounds0, tauOpnd); - } - break; - case Op_NewMultiArray: - { - // the number of newarray dimensions must be >= 1. - uint32 numOpnds = lasti->getNumSrcOperands(); - assert(numOpnds >= 1); - StlSet done(mm); - if (Log::isEnabled()) { - Log::out() << "Adding info about NewMultiArray instruction "; - lasti->print(Log::out()); - Log::out() << std::endl; - } - Opnd *tauOpnd = 0; - // the number of newarray elements must be in [0, MAXINT32] - for (uint32 opndNum = 0; opndNum < numOpnds; opndNum++) { - Opnd *thisOpnd = lasti->getSrc(opndNum); - if (!done.has(thisOpnd)) { - done.insert(thisOpnd); - PiCondition bounds0(PiBound(thisOpnd->getType()->tag, int64(0)), - PiBound(thisOpnd->getType()->tag, int64(0x7fffffff))); - if (!tauOpnd) tauOpnd = getBlockTauEdge(block); // must use a tauEdge - insertPiNodeForOpndAndAliases(block, thisOpnd, bounds0, tauOpnd); - } - } - } - break; - default: - break; - } -} - -// Add a Pi node in the node if it is after -// a test which tells something about a variable. -// For now, don't bother with Exception edges. -void Abcd::insertPiNodes(Node *block) -{ - Edge *domEdge = 0; - - // see if there is a predecessor block idom such that - // (1) idom dominates this one - // (2) this block dominates all other predecessors - // (3) idom has multiple out-edges - // (4) idom has only 1 edge to this node - - // (1a) if a predecessor dominates it must be idom - Node *idom = dominators.getIdom(block); - - // (3) must exist and have multiple out-edges - if ((idom == NULL) || (idom->hasOnlyOneSuccEdge())) { - return; - } - - if (Log::isEnabled()) { - Log::out() << "Checking block " << (int)block->getId() << " with idom " - << (int) idom->getId() << std::endl; - } - - if (block->hasOnlyOnePredEdge()) { - // must be from idom -- (1b) - // satisfies (2) trivially - domEdge = *(block->getInEdges().begin()); - } else { - // check (1b) and (2) - const Edges &inedges = block->getInEdges(); - typedef Edges::const_iterator EdgeIter; - EdgeIter eLast = inedges.end(); - for (EdgeIter eIter = inedges.begin(); eIter != eLast; eIter++) { - Edge *inEdge = *eIter; - Node *predBlock = inEdge->getSourceNode(); - if (predBlock == idom) { - // (1b) found idom - if (domEdge) { - // failed (4): idom found on more than one incoming edge - return; - } - domEdge = inEdge; - } else if (! dominators.dominates(block, predBlock)) { - // failed (2) - return; - } - } - } - - if (domEdge) { - Edge *inEdge = domEdge; - Node *predBlock = idom; - if (Log::isEnabled()) { - Log::out() << "Checking branch for " << (int)block->getId() << " with idom " - << (int) idom->getId() << std::endl; - } - if (!predBlock->hasOnlyOneSuccEdge()) { - Edge::Kind kind = inEdge->getKind(); - switch (kind) { - case Edge::Kind_True: - case Edge::Kind_False: - { - Inst* branchi1 = (Inst*)predBlock->getLastInst(); - assert(branchi1 != NULL); - BranchInst* branchi = branchi1->asBranchInst(); - if (branchi && branchi->isConditionalBranch()) { - insertPiNodesForBranch(block, branchi, kind); - } else { - return; - } - } - break; - - case Edge::Kind_Dispatch: - return; - - case Edge::Kind_Unconditional: - // Previous block must have a PEI - // since it had multiple out-edges. - // This is the unexceptional condition. - { - Inst* lasti = (Inst*)predBlock->getLastInst(); - assert(lasti != NULL); - insertPiNodesForUnexceptionalPEI(block, lasti); - } - // We could look for a bounds check in predecessor. - - // But: since now all useful PEIs have explicit results, - // they imply a Pi-like action. - break; - - case Edge::Kind_Catch: - break; - default: - break; - }; - } - } -} - -void Abcd::renamePiVariables(Node *block) -{ - // For each variable use in the block, check for a Pi version in - // the piTable. Since we are visiting in preorder over dominator - // tree dominator order, any found version will dominate this node. - - // we defer adding any new mappings for the Pi instructions here until - // we are past the Pi instructions - - // first process any pi nodes, just the RHSs - Inst* headInst = (Inst*)block->getFirstInst(); - for (int phase=0; phase < 2; ++phase) { - // phase 0: remap just Pi node source operands - // phase 1: add Pi remappings, remap source operands of other instructions - - for (Inst* inst = headInst->getNextInst(); inst != NULL; inst = inst->getNextInst()) { - - if (inst->getOpcode() == Op_TauPi) { - if (phase == 1) { - // add any Pi node destination to the map. - - Opnd *dstOpnd = inst->getDst(); - assert(dstOpnd->isPiOpnd()); - Opnd *orgOpnd = dstOpnd->asPiOpnd()->getOrg(); - if (flags.useAliases) { - if (orgOpnd->isSsaVarOpnd()) { - orgOpnd = orgOpnd->asSsaVarOpnd()->getVar(); - } - } - piMap->insert(orgOpnd, dstOpnd); - if (Log::isEnabled()) { - Log::out() << "adding remap for Pi of "; - orgOpnd->print(Log::out()); - Log::out() << " to "; - inst->getDst()->print(Log::out()); - Log::out() << std::endl; - } - - continue; // don't remap Pi sources; - } - } else { - if (phase == 0) { - // no more Pi instructions, we're done with phase 0. - break; - } - } - - // now process source operands - uint32 numOpnds = inst->getNumSrcOperands(); - for (uint32 i=0; igetSrc(i); - if (opnd->isPiOpnd()) - opnd = opnd->asPiOpnd()->getOrg(); - Opnd *foundOpnd = piMap->lookup(opnd); - if (foundOpnd) { - inst->setSrc(i,foundOpnd); - } - } - - if (inst->getOpcode() == Op_TauPi) { - // for a Pi, remap variables appearing in the condition as well - if (Log::isEnabled()) { - Log::out() << "remapping condition in "; - inst->print(Log::out()); - Log::out() << std::endl; - } - TauPiInst *thePiInst = inst->asTauPiInst(); - assert(thePiInst); - PiCondition *cond = thePiInst->cond; - if (Log::isEnabled()) { - Log::out() << " original condition is "; - cond->print(Log::out()); - Log::out() << std::endl; - } - Opnd *lbRemap = cond->getLb().getVar().the_var; - if (lbRemap) { - if (Log::isEnabled()) { - Log::out() << " has lbRemap="; - lbRemap->print(Log::out()); - Log::out() << std::endl; - } - if (lbRemap->isPiOpnd()) - lbRemap = lbRemap->asPiOpnd()->getOrg(); - Opnd *lbRemapTo = piMap->lookup(lbRemap); - if (lbRemapTo) { - if (Log::isEnabled()) { - Log::out() << "adding remap of lbRemap="; - lbRemap->print(Log::out()); - Log::out() << " to lbRemapTo="; - lbRemapTo->print(Log::out()); - Log::out() << " to condition "; - cond->print(Log::out()); - } - PiCondition remapped(*cond, lbRemap, lbRemapTo); - if (Log::isEnabled()) { - Log::out() << " YIELDS1 "; - remapped.print(Log::out()); - } - *cond = remapped; - if (Log::isEnabled()) { - Log::out() << " YIELDS "; - cond->print(Log::out()); - Log::out() << std::endl; - } - } - } - Opnd *ubRemap = cond->getUb().getVar().the_var; - if (ubRemap && (lbRemap != ubRemap)) { - if (Log::isEnabled()) { - Log::out() << " has ubRemap="; - ubRemap->print(Log::out()); - Log::out() << std::endl; - } - if (ubRemap->isPiOpnd()) - ubRemap = ubRemap->asPiOpnd()->getOrg(); - Opnd *ubRemapTo = piMap->lookup(ubRemap); - if (ubRemapTo) { - if (Log::isEnabled()) { - Log::out() << "adding remap of ubRemap="; - ubRemap->print(Log::out()); - Log::out() << " to ubRemapTo="; - ubRemapTo->print(Log::out()); - Log::out() << " to condition "; - cond->print(Log::out()); - } - PiCondition remapped(*cond, ubRemap, ubRemapTo); - if (Log::isEnabled()) { - Log::out() << " YIELDS1 "; - remapped.print(Log::out()); - } - *cond = remapped; - if (Log::isEnabled()) { - Log::out() << " YIELDS "; - cond->print(Log::out()); - Log::out() << std::endl; - } - } - } - } - } - - } -} - // an InstWalker class AbcdSolverWalker { AbcdSolver *theSolver; @@ -1200,7 +238,6 @@ public: void Abcd::removeRedundantBoundsChecks() { - assert(!solver); solver = new (mm) AbcdSolver(this); AbcdSolverWalker solveInst(solver); // to apply to each @@ -1211,162 +248,6 @@ void Abcd::removeRedundantBoundsChecks() solver = 0; } -// a ScopedDomNodeInstWalker, forward/preorder -class RemovePiWalker { - Abcd *thePass; - Node *block; -public: - void startNode(DominatorNode *domNode) { block = domNode->getNode(); }; - void applyToInst(Inst *i) { thePass->removePiNodes(block, i); }; - void finishNode(DominatorNode *domNode) { }; - - void enterScope() { }; - void exitScope() { }; - RemovePiWalker(Abcd *thePass0) - : thePass(thePass0), block(0) // forward - { - }; -}; - - -void Abcd::removePiNodes() -{ - RemovePiWalker removePiWalker(this); - - typedef ScopedDomNodeInst2DomWalker - RemovePiDomWalker; - RemovePiDomWalker removePiDomWalker(removePiWalker); - - DomTreeWalk(dominators, removePiDomWalker, - mm); -} - -void Abcd::removePiNodes(Node *block, Inst *inst) -{ - AbcdReasons *why; - if (inst->getOpcode() == Op_TauPi) { - inst->unlink(); - } else if ((!flags.dryRun) && - (inst->getOpcode() == Op_TauCheckBounds) && - isMarkedToEliminate(inst, why)) { - Opnd* srcOpnd = (flags.useReasons - ? getReasonTau(why, inst) - : getBlockTauPoint(block)); - Opnd* dstOpnd = inst->getDst(); - inst->setDst(OpndManager::getNullOpnd()); - Inst* copy = irManager.getInstFactory().makeCopy(dstOpnd,srcOpnd); - copy->insertBefore(inst); - FlowGraph::eliminateCheck(irManager.getFlowGraph(),block, inst, false); - } else { - uint32 numOpnds = inst->getNumSrcOperands(); - for (uint32 i=0; igetSrc(i); - Opnd *opnd = opnd0; - Opnd *newOpnd = opnd0; - while (newOpnd) { - opnd = newOpnd; - newOpnd = 0; - if (opnd->isPiOpnd()) { - // it's a Pi operand, dereference directly - PiOpnd *piOpnd = opnd->asPiOpnd(); - newOpnd = piOpnd->getOrg(); - } - } - if (flags.remConv && - (!flags.dryRun) && - (opnd->getInst()->getOpcode() == Op_Conv)) { - Opnd *srcOpnd = opnd->getInst()->getSrc(0); - bool deref = isMarkedToEliminate(opnd->getInst(), why); - while (deref) { - deref = false; - if (srcOpnd->getType()->tag == - opnd->getType()->tag) { - opnd = srcOpnd; - Inst *newInst = opnd->getInst(); - if ((newInst->getOpcode() == Op_Conv) && - isMarkedToEliminate(newInst, why)) { - - deref = true; - } - } - } - } - if (flags.unmaskShifts && - (!flags.dryRun) && - ((opnd->getInst()->getOpcode() == Op_Shr) || - (opnd->getInst()->getOpcode() == Op_Shl))) { - Inst *the_inst = opnd->getInst(); - - if (isMarkedToEliminate(the_inst, why)) { - // don't eliminate, just clear shift-mask - - the_inst->setShiftMaskModifier(ShiftMask_None); - } - } - - if (opnd0 != opnd) { - inst->setSrc(i,opnd); - }; - } - - if (flags.remOneBound && - (inst->getOpcode() == Op_TauCheckBounds)) { - if (isMarkedToEliminateLB(inst, why)) { - Opnd *dstTau = inst->getDst(); - inst->setDst(OpndManager::getNullOpnd()); - Opnd *a = inst->getSrc(1); // index - Opnd *b = inst->getSrc(0); // array length - // don't bother with tauAnd, chkbound is immobile - Inst *new_check - = irManager.getInstFactory().makeTauCheckUpperBound(dstTau, a, b); - if (inst->getOverflowModifier() == Overflow_None) { - new_check->setOverflowModifier(Overflow_None); - } - if (Log::isEnabled()) { - Log::out() << " inserting "; - new_check->print(Log::out()); - Log::out() << " in place of "; - inst->print(Log::out()); - Log::out() << std::endl; - } - new_check->insertBefore(inst); - inst->unlink(); - - } else if (isMarkedToEliminateUB(inst, why)) { - Opnd *dstTau = inst->getDst(); - inst->setDst(OpndManager::getNullOpnd()); - Opnd *b = inst->getSrc(1); // index - - // build a constant 0 operand a - Type *idxType = b->getType(); - ConstInst::ConstValue constZero; - constZero.i8 = 0; - OpndManager &opndManager = irManager.getOpndManager(); - SsaTmpOpnd *a = opndManager.createSsaTmpOpnd(idxType); - InstFactory &instFactory = irManager.getInstFactory(); - Inst *ldcInst = instFactory.makeLdConst(a, constZero); - // don't bother with tauAnd, chk is immobile - Inst *new_check - = instFactory.makeTauCheckLowerBound(dstTau, a, b); - if (inst->getOverflowModifier() == Overflow_None) { - new_check->setOverflowModifier(Overflow_None); - } - if (Log::isEnabled()) { - Log::out() << " inserting "; - ldcInst->print(Log::out()); - Log::out() << ";"; - new_check->print(Log::out()); - Log::out() << "; in place of "; - inst->print(Log::out()); - Log::out() << std::endl; - } - new_check->insertBefore(inst); - ldcInst->insertBefore(new_check); - inst->unlink(); - } - } - } -} void Abcd::markInstToEliminate(Inst *i) { @@ -1541,99 +422,6 @@ bool Abcd::isMarkedToEliminateUB(Inst *i return true; } -Opnd *Abcd::getConstantOpnd(Opnd *opnd) -{ - if (ConstantFolder::isConstant(opnd)) { - return opnd; - } else { - return 0; - } -} - -bool Abcd::getAliases(Opnd *opnd, AbcdAliases *aliases, int64 addend) -{ - Inst *inst = opnd->getInst(); - switch (inst->getOpcode()) { - case Op_TauPi: - return getAliases(inst->getSrc(0), aliases, addend); - - case Op_Add: - { - Opnd *op0 = inst->getSrc(0); - Opnd *op1 = inst->getSrc(1); - Opnd *constOpnd0 = getConstantOpnd(op0); - Opnd *constOpnd1 = getConstantOpnd(op1); - if ((constOpnd0 || constOpnd1) && - (inst->getType() == Type::Int32)) { - // I assume we've done folding first - assert(!(constOpnd0 && constOpnd1)); - if (constOpnd1) { - // swap the operands; - constOpnd0 = constOpnd1; - op1 = op0; - } - // now constOpnd0 should be constant - // op1 is the non-constant operand - - Inst *inst0 = constOpnd0->getInst(); - assert(inst0); - ConstInst *cinst0 = inst0->asConstInst(); - assert(cinst0); - ConstInst::ConstValue cv = cinst0->getValue(); - int32 c = cv.i4; - int64 sumc = c + addend; - if (add_overflowed(sumc, c, addend)) { - return false; - } else { - VarBound vb(op1); - aliases->theSet.insert(PiBound(inst->getType(), 1, vb, sumc)); - getAliases(op1, aliases, sumc); - return true; - } - } - } - break; - case Op_Sub: - { - Opnd *constOpnd = getConstantOpnd(inst->getSrc(1)); - if (constOpnd && (inst->getType() == Type::Int32)) { - Opnd *op0 = inst->getSrc(0); - Opnd *op1 = constOpnd; - // now op1 should be constant - // I assume we've done folding first - if( !(!getConstantOpnd(op0)) ) assert(0); - - Inst *inst1 = op1->getInst(); - assert(inst1); - ConstInst *cinst1 = inst1->asConstInst(); - assert(cinst1); - ConstInst::ConstValue cv = cinst1->getValue(); - int64 c = cv.i4; - int64 negc = -c; - int64 subres = addend + negc; - if (neg_overflowed(negc, c) || - add_overflowed(subres, addend, negc)) { - return false; - } else { - VarBound vb(op1); - aliases->theSet.insert(PiBound(inst->getType(), 1, vb, subres)); - getAliases(op1, aliases, subres); - return true; - } - } - } - break; - case Op_Copy: - assert(0); // do copy propagation first - break; - case Op_TauCheckZero: - return false; - default: - break; - } - return false; -} - template struct NodeInst2NodeFun : ::std::unary_function { @@ -1751,46 +539,6 @@ Abcd::hasCheckableType(const Opnd *opnd) return Abcd::isCheckableType(typetag); } -// return an opnd to be used just before useSite, possibly building -// a tauAnd instruction to use. -SsaTmpOpnd *Abcd::getReasonTau(AbcdReasons *reason, - Inst *useSite) -{ - InstFactory &instFactory = irManager.getInstFactory(); - OpndManager &opndManager = irManager.getOpndManager(); - TypeManager &typeManager = irManager.getTypeManager(); - - uint32 numReasons = (uint32) reason->facts.size(); - assert(numReasons < 100); - if (numReasons == 1) { - SsaTmpOpnd *reasonOpnd = *(reason->facts.begin()); - return reasonOpnd; - } else if (numReasons == 0) { - SsaTmpOpnd *reasonOpnd = getTauSafe(); - return reasonOpnd; - } else { - // need to build a tauAnd - Opnd **newAndOpnds = new (mm) Opnd*[numReasons]; - StlSet::iterator iter = reason->facts.begin(); - for (uint32 i = 0; i < numReasons; ++i, ++iter) { - newAndOpnds[i] = *iter; - } - SsaTmpOpnd *tauDst = opndManager.createSsaTmpOpnd(typeManager.getTauType()); - Inst *tauAndInst = instFactory.makeTauAnd(tauDst, numReasons, newAndOpnds); - - if (Log::isEnabled()) { - Log::out() << "Inserting tauAndInst=("; - tauAndInst->print(Log::out()); - Log::out() << ") before useSite= "; - useSite->print(Log::out()); - Log::out() << ")" << std::endl; - } - - tauAndInst->insertBefore(useSite); - return tauDst; - } -} - // phi reasons together // derefVar definition site is a Phi which should be used for placement SsaTmpOpnd *Abcd::makeReasonPhi(Opnd *derefVar, StlVector &reasons, @@ -1871,4 +619,239 @@ SsaTmpOpnd *Abcd::makeReasonPhi(Opnd *de return tauResOpnd; } +// return an opnd to be used just before useSite, possibly building +// a tauAnd instruction to use. +SsaTmpOpnd* Abcd::getReasonTau(AbcdReasons *reason, Inst *useSite) +{ + InstFactory &instFactory = irManager.getInstFactory(); + OpndManager &opndManager = irManager.getOpndManager(); + TypeManager &typeManager = irManager.getTypeManager(); + + uint32 numReasons = (uint32) reason->facts.size(); + assert(numReasons < 100); + if (numReasons == 1) { + SsaTmpOpnd *reasonOpnd = *(reason->facts.begin()); + return reasonOpnd; + } else if (numReasons == 0) { + SsaTmpOpnd *reasonOpnd = getTauSafe(); + return reasonOpnd; + } else { + // need to build a tauAnd + Opnd **newAndOpnds = new (mm) Opnd*[numReasons]; + StlSet::iterator iter = reason->facts.begin(); + for (uint32 i = 0; i < numReasons; ++i, ++iter) { + newAndOpnds[i] = *iter; + } + SsaTmpOpnd *tauDst = opndManager.createSsaTmpOpnd(typeManager.getTauType()); + Inst *tauAndInst = instFactory.makeTauAnd(tauDst, numReasons, newAndOpnds); + + if (Log::isEnabled()) { + Log::out() << "Inserting tauAndInst=("; + tauAndInst->print(Log::out()); + Log::out() << ") before useSite= "; + useSite->print(Log::out()); + Log::out() << ")" << std::endl; + } + + tauAndInst->insertBefore(useSite); + return tauDst; + } +} + +// a ScopedDomNodeInstWalker, forward/preorder +class RemovePiEliminateChecksWalker { +public: + RemovePiEliminateChecksWalker(Abcd* abcd) : _abcd(abcd), block(0) // forward + {} + + void startNode(DominatorNode *domNode) { block = domNode->getNode(); }; + void applyToInst(Inst *i) { _abcd->removePiEliminateChecksOnInst(block, i); }; + void finishNode(DominatorNode *domNode) {} + + void enterScope() {} + void exitScope() {} +private: + Abcd* _abcd; + Node* block; +}; +//------------------------------------------------------------------------------ + +void Abcd::removePiEliminateChecks() +{ + RemovePiEliminateChecksWalker removePiWalker(this); + typedef ScopedDomNodeInst2DomWalker + RemovePiDomWalker; + RemovePiDomWalker removePiDomWalker(removePiWalker); + + DomTreeWalk(dominators, removePiDomWalker, mm); +} + +void Abcd::removePiEliminateChecksOnInst(Node *block, Inst *inst) +{ + AbcdReasons *why; + if (inst->getOpcode() == Op_TauPi) { + inst->unlink(); + } else if ((!flags.dryRun) && + (inst->getOpcode() == Op_TauCheckBounds) && + isMarkedToEliminate(inst, why)) { + Opnd* srcOpnd = (flags.useReasons + ? getReasonTau(why, inst) + : getBlockTauPoint(block)); + Opnd* dstOpnd = inst->getDst(); + inst->setDst(OpndManager::getNullOpnd()); + Inst* copy = irManager.getInstFactory().makeCopy(dstOpnd,srcOpnd); + copy->insertBefore(inst); + FlowGraph::eliminateCheck(irManager.getFlowGraph(),block, inst, false); + } else { + uint32 numOpnds = inst->getNumSrcOperands(); + for (uint32 i=0; igetSrc(i); + Opnd *opnd = opnd0; + Opnd *newOpnd = opnd0; + while (newOpnd) { + opnd = newOpnd; + newOpnd = 0; + if (opnd->isPiOpnd()) { + // it's a Pi operand, dereference directly + PiOpnd *piOpnd = opnd->asPiOpnd(); + newOpnd = piOpnd->getOrg(); + } + } + if (flags.remConv && + (!flags.dryRun) && + (opnd->getInst()->getOpcode() == Op_Conv)) { + Opnd *srcOpnd = opnd->getInst()->getSrc(0); + bool deref = isMarkedToEliminate(opnd->getInst(), why); + while (deref) { + deref = false; + if (srcOpnd->getType()->tag == + opnd->getType()->tag) { + opnd = srcOpnd; + Inst *newInst = opnd->getInst(); + if ((newInst->getOpcode() == Op_Conv) && + isMarkedToEliminate(newInst, why)) { + + deref = true; + } + } + } + } + if (flags.unmaskShifts && + (!flags.dryRun) && + ((opnd->getInst()->getOpcode() == Op_Shr) || + (opnd->getInst()->getOpcode() == Op_Shl))) { + Inst *the_inst = opnd->getInst(); + + if (isMarkedToEliminate(the_inst, why)) { + // don't eliminate, just clear shift-mask + + the_inst->setShiftMaskModifier(ShiftMask_None); + } + } + + if (opnd0 != opnd) { + inst->setSrc(i,opnd); + } + } + + if (flags.remOneBound && + (inst->getOpcode() == Op_TauCheckBounds)) { + if (isMarkedToEliminateLB(inst, why)) { + Opnd *dstTau = inst->getDst(); + inst->setDst(OpndManager::getNullOpnd()); + Opnd *a = inst->getSrc(1); // index + Opnd *b = inst->getSrc(0); // array length + // don't bother with tauAnd, chkbound is immobile + Inst *new_check + = irManager.getInstFactory().makeTauCheckUpperBound(dstTau, a, b); + if (inst->getOverflowModifier() == Overflow_None) { + new_check->setOverflowModifier(Overflow_None); + } + if (Log::isEnabled()) { + Log::out() << " inserting "; + new_check->print(Log::out()); + Log::out() << " in place of "; + inst->print(Log::out()); + Log::out() << std::endl; + } + new_check->insertBefore(inst); + inst->unlink(); + + } else if (isMarkedToEliminateUB(inst, why)) { + Opnd *dstTau = inst->getDst(); + inst->setDst(OpndManager::getNullOpnd()); + Opnd *b = inst->getSrc(1); // index + + // build a constant 0 operand a + Type *idxType = b->getType(); + ConstInst::ConstValue constZero; + constZero.i8 = 0; + OpndManager &opndManager = irManager.getOpndManager(); + SsaTmpOpnd *a = opndManager.createSsaTmpOpnd(idxType); + InstFactory &instFactory = irManager.getInstFactory(); + Inst *ldcInst = instFactory.makeLdConst(a, constZero); + // don't bother with tauAnd, chk is immobile + Inst *new_check + = instFactory.makeTauCheckLowerBound(dstTau, a, b); + if (inst->getOverflowModifier() == Overflow_None) { + new_check->setOverflowModifier(Overflow_None); + } + if (Log::isEnabled()) { + Log::out() << " inserting "; + ldcInst->print(Log::out()); + Log::out() << ";"; + new_check->print(Log::out()); + Log::out() << "; in place of "; + inst->print(Log::out()); + Log::out() << std::endl; + } + new_check->insertBefore(inst); + ldcInst->insertBefore(new_check); + inst->unlink(); + } + } + } +} + +SsaTmpOpnd* Abcd::getBlockTauPoint(Node *block) +{ + if ((lastTauPointBlock == block) && blockTauPoint) return blockTauPoint; + Inst *firstInst = (Inst*)block->getFirstInst(); + Inst *inst = (Inst*)firstInst->getNextInst(); + for (; inst != NULL; inst = inst->getNextInst()) { + if (inst->getOpcode() == Op_TauPoint) { + blockTauPoint = inst->getDst()->asSsaTmpOpnd(); + assert(blockTauPoint); + lastTauPointBlock = block; + return blockTauPoint; + } + } + for (inst = firstInst->getNextInst(); inst != NULL; inst = inst->getNextInst()) { + if (inst->getOpcode() != Op_Phi) { + break; // insert before inst. + } + } + // no non-phis, insert before inst; + TypeManager &tm = irManager.getTypeManager(); + SsaTmpOpnd *tauOpnd = irManager.getOpndManager().createSsaTmpOpnd(tm.getTauType()); + Inst* tauPoint = irManager.getInstFactory().makeTauPoint(tauOpnd); + if(Log::isEnabled()) { + Log::out() << "Inserting tauPoint inst "; + tauPoint->print(Log::out()); + if (inst!=NULL) { + Log::out() << " before inst "; + inst->print(Log::out()); + } + Log::out() << std::endl; + } + if (inst!=NULL) { + tauPoint->insertBefore(inst); + } else { + block->appendInst(tauPoint); + } + blockTauPoint = tauOpnd; + lastTauPointBlock = block; + return tauOpnd; +} + } //namespace Jitrino --- a/vm/jitrino/src/optimizer/abcd/abcd.h +++ b/vm/jitrino/src/optimizer/abcd/abcd.h @@ -29,6 +29,8 @@ #include "open/types.h" #include "Opcode.h" #include "FlowGraph.h" #include "optpass.h" +#include "insertpi.h" +#include "abcd/AbcdFlags.h" namespace Jitrino { @@ -46,92 +48,38 @@ class AbcdSolver; class AbcdAliases; class AbcdReasons; - typedef ::std::pair InstReasonPair; inline bool operator <(const InstReasonPair &pair1, const InstReasonPair &pair2) { return (pair1.first < pair2.first); } -struct AbcdFlags { - bool partial; - bool dryRun; - bool useAliases; - bool useConv; - bool remConv; - bool useShr; - bool unmaskShifts; - bool remBr; - bool remCmp; - bool remOneBound; - bool remOverflow; - bool checkOverflow; - bool useReasons; -}; - class Abcd { - IRManager& irManager; - MemoryManager &mm; - InequalityGraph *ineqGraph; - DominatorTree& dominators; - SparseOpndMap *piMap; - uint32 nextPiOpndId; - AbcdSolver *solver; - StlVector canEliminate; // sorted by Inst - StlVector canEliminateUB; // keep sorted - StlVector canEliminateLB; // keep sorted - - SsaTmpOpnd *tauUnsafe; - SsaTmpOpnd *tauSafe; - SsaTmpOpnd *blockTauPoint; - Node *lastTauPointBlock; - SsaTmpOpnd *blockTauEdge; - Node *lastTauEdgeBlock; - - AbcdFlags& flags; public: static void readFlags(Action* argSource, AbcdFlags* flags); static void showFlags(std::ostream& os); Abcd(IRManager &irManager0, MemoryManager& memManager, DominatorTree& dom0); - ~Abcd() { - }; + ~Abcd() {} void runPass(); -private: - void insertPiNodes(); // insert and rename over whole tree; - void insertPiNodes(DominatorNode *domBlock); // for each dominator - void insertPiNodes(Node *block); // for each dominator - void insertPiNodesForUnexceptionalPEI(Node *block, Inst *pei); - void insertPiNodesForBranch(Node *block, BranchInst *branchi, - Edge::Kind kind); - void insertPiNodesForComparison(Node *block, - ComparisonModifier mod, - const PiCondition &bounds, - Opnd *op, - bool swap_operands, - bool negate_comparison); - void insertPiNodeForOpnd(Node *block, Opnd *org, - const PiCondition &cond, - Opnd *tauOpnd = 0); - // checks for aliases of opnd, inserts them. - void insertPiNodeForOpndAndAliases(Node *block, Opnd *org, - const PiCondition &cond, - Opnd *tauOpnd = 0); - PiOpnd *getNewDestOpnd(Node *block, Opnd *org); - Opnd *getConstantOpnd(Opnd *opnd); // dereferencing through Pis, 0 if not constant. - void renamePiVariables(); - void renamePiVariables(Node *block); - void renamePiVariables(DominatorNode *block); + bool getAliases(Opnd *theOpnd, AbcdAliases *, + int64 addend); // adds them to aliases list, adding addend - void removePiNodes(); - void removePiNodes(Node *block, Inst *i); + static bool isConvOpnd(const Opnd *opnd); + static bool convPassesSource(const Opnd *opnd); + static Opnd *getConvSource(const Opnd *opnd); + static bool typeIncludes(Type::Tag type1, Type::Tag type2); + static bool hasTypeBounds(Type::Tag srcTag, int64 &lb, int64 &ub); + static bool isCheckableType(Type::Tag type1); + static bool hasCheckableType(const Opnd *opnd); +private: + Opnd *getConstantOpnd(Opnd *opnd); // dereferencing through Pis, 0 if not constant. - void updateSsaForm(); - void buildInequalityGraph(); void removeRedundantBoundsChecks(); + void removePiEliminateChecksOnInst(Node *block, Inst *inst); void markCheckToEliminate(Inst *); // used by solver to mark eliminable branches void markInstToEliminate(Inst *); // used by solver to mark other eliminable instructions @@ -152,31 +100,33 @@ private: bool isMarkedToEliminateUB(Inst *, AbcdReasons *&why); SsaTmpOpnd *getBlockTauPoint(Node *block); - SsaTmpOpnd *getBlockTauEdge(Node *block); SsaTmpOpnd *getTauUnsafe(); SsaTmpOpnd *getTauSafe(); - SsaTmpOpnd *getReasonTau(AbcdReasons *reason, - Inst *useSite); SsaTmpOpnd *makeReasonPhi(Opnd *derefVar, StlVector &reasons, StlVector &derefVarVersions); + SsaTmpOpnd* getReasonTau(AbcdReasons *reason, Inst *useSite); - friend class AbcdSolver; - friend class InsertPiWalker; - friend class RenamePiWalker; - friend class RemovePiWalker; - friend struct AliasCheckingFun; - void checkForAliases(); -public: - bool getAliases(Opnd *theOpnd, AbcdAliases *, - int64 addend); // adds them to aliases list, adding addend + void removePiEliminateChecks(); - static bool isConvOpnd(const Opnd *opnd); - static bool convPassesSource(const Opnd *opnd); - static Opnd *getConvSource(const Opnd *opnd); - static bool typeIncludes(Type::Tag type1, Type::Tag type2); - static bool hasTypeBounds(Type::Tag srcTag, int64 &lb, int64 &ub); - static bool isCheckableType(Type::Tag type1); - static bool hasCheckableType(const Opnd *opnd); + IRManager& irManager; + MemoryManager &mm; + DominatorTree& dominators; + AbcdSolver *solver; + StlVector canEliminate; // sorted by Inst + StlVector canEliminateUB; // keep sorted + StlVector canEliminateLB; // keep sorted + + SsaTmpOpnd *tauUnsafe; + SsaTmpOpnd *tauSafe; + + AbcdFlags& flags; + InsertPi insertPi; + + SsaTmpOpnd* blockTauPoint; + Node* lastTauPointBlock; + + friend class AbcdSolver; + friend class RemovePiEliminateChecksWalker; }; } //namespace Jitrino