/* * Licensed to the Apache Software Foundation (ASF) under one or more * contributor license agreements. See the NOTICE file distributed with * this work for additional information regarding copyright ownership. * The ASF licenses this file to You under the Apache License, Version 2.0 * (the "License"); you may not use this file except in compliance with * the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ #include "insertpi.h" #include "walkers.h" #include "abcdbounds.h" #include "constantfolder.h" namespace Jitrino { 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; } } // a DomWalker, to be applied in pre-order class InsertPiWalker { public: InsertPiWalker(InsertPi* insert_pi) : _insertPi(insert_pi) {}; void applyToDominatorNode(DominatorNode *domNode) { _insertPi->insertPiToNode(domNode->getNode()); } // is called before a node and its children are processed void enterScope() {}; // is called after node and children are processed void exitScope() {}; private: InsertPi* _insertPi; }; //------------------------------------------------------------------------------ // Add a Pi node in the node if it is after each test // which tells something about a variable // // 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 InsertPi::insertPi() { InsertPiWalker insert_pi_walker(this); // dom-pre-order traversal DomTreeWalk(_domTree, insert_pi_walker, _mm); renamePiVariables(); 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"); } } //------------------------------------------------------------------------------ // add Pi in the node iff after a test which tells something about the var void InsertPi::insertPiToNode(Node* block) { Edge *dom_edge = 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 = _domTree.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 dom_edge = *(block->getInEdges().begin()); } else { // check (1b) and (2) const Edges &inedges = block->getInEdges(); typedef Edges::const_iterator EdgeIter; EdgeIter e_last = inedges.end(); for (EdgeIter e_iter = inedges.begin(); e_iter != e_last; e_iter++) { Edge *in_edge = *e_iter; Node *pred_block = in_edge->getSourceNode(); if (pred_block == idom) { // (1b) found idom if (dom_edge) { // failed (4): idom found on more than one incoming edge return; } dom_edge = in_edge; } else if (! _domTree.dominates(block, pred_block)) { // failed (2) return; } } } if (dom_edge) { Edge *in_edge = dom_edge; Node *pred_block = idom; if (Log::isEnabled()) { Log::out() << "Checking branch for " << (int)block->getId() << " with idom " << (int) idom->getId() << std::endl; } if (!pred_block->hasOnlyOneSuccEdge()) { Edge::Kind kind = in_edge->getKind(); switch (kind) { case Edge::Kind_True: case Edge::Kind_False: { Inst* branchi1 = (Inst*)pred_block->getLastInst(); assert(branchi1 != NULL); BranchInst* branchi = branchi1->asBranchInst(); if (branchi && branchi->isConditionalBranch()) { insertPiForBranch(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*)pred_block->getLastInst(); assert(lasti != NULL); insertPiForUnexceptionalPEI(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 InsertPi::insertPiForUnexceptionalPEI(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 insertPiForOpndAndAliases(block, idxOp, bounds0, tauOpnd); PiBound idxBound(typetag, 1, VarBound(idxOp), int64(1)); PiCondition bounds1(idxBound, PiBound(typetag, false)); insertPiForOpndAndAliases(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))); insertPiForOpndAndAliases(block, numElemOpnd, bounds0, tauOpnd); } break; case Op_NewMultiArray: { // the number of newarray dimensions must be >= 1. U_32 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 (U_32 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 } insertPiForOpndAndAliases(block, thisOpnd, bounds0, tauOpnd); } } } break; default: break; } } //------------------------------------------------------------------------------ SsaTmpOpnd* InsertPi::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; } //------------------------------------------------------------------------------ // 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 InsertPi::insertPiForBranch(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: insertPiForComparison(block, Cmp_EQ, zeroBounds, op0, false, // negate if false edge (kind == Edge::Kind_False)); break; case Cmp_NonZero: insertPiForComparison(block, Cmp_EQ, // use EQ zeroBounds, op0, false, // but negate if true edge (kind == Edge::Kind_True)); 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()) { insertPiForComparison(block, mod, bounds0, op1, false, // negate for false edge (kind == Edge::Kind_False)); } if (!bounds1.isUnknown()) { insertPiForComparison(block, mod, bounds1, op0, true, // negate for false edge (kind == Edge::Kind_False)); } } } //------------------------------------------------------------------------------ void InsertPi::insertPiForComparison(Node* block, ComparisonModifier mod, const PiCondition &bounds, Opnd* op, bool swap_operands, bool negate_comparison) { if (Log::isEnabled()) { Log::out() << "insertPiForComparison(..., "; 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() << ", "; Log::out() << (negate_comparison ? "true" : "false"); Log::out() << ")" << std::endl; // Print last inst from all prev blocks. Edges::const_iterator it = block->getInEdges().begin(), end = block->getInEdges().end(); for(; it != end; ++it) { Edge* edge = (*it); Log::out() << "pred inst---> "; ((Inst*)edge->getSourceNode()->getLastInst())->print(Log::out()); 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() << "insertPiForComparison: negating comparison to " ; Log::out() << printableComparison(mod); Log::out() << std::endl; } } switch (mod) { case Cmp_EQ: if (!negate_comparison) insertPiForOpndAndAliases(block, op, bounds0, NULL); else { if (Log::isEnabled()) { Log::out() << "insertPiForComparison: cannot represent ! Cmp_EQ" << std::endl; } } // we can't represent the other case break; case Cmp_NE_Un: if (negate_comparison) insertPiForOpndAndAliases(block, op, bounds0, NULL); else { if (Log::isEnabled()) { Log::out() << "insertPiForComparison: 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()); insertPiForOpndAndAliases(block, op, oneLowerBound, NULL); } 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()) insertPiForOpndAndAliases(block, op, bounds1, NULL); else { if (Log::isEnabled()) { Log::out() << "insertPiForComparison(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()) insertPiForOpndAndAliases(block, op, bounds1, NULL); else { if (Log::isEnabled()) { Log::out() << "insertPiForComparison(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)))) { insertPiForOpndAndAliases(block, op, bounds1, NULL); } else { if (Log::isEnabled()) { Log::out() << "insertPiForComparison(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()) insertPiForOpndAndAliases(block, op, bounds1, NULL); else { if (Log::isEnabled()) { Log::out() << "insertPiForComparison(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()) insertPiForOpndAndAliases(block, op, bounds1, NULL); else { if (Log::isEnabled()) { Log::out() << "insertPiForComparison(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()); insertPiForOpndAndAliases(block, op, zeroLowerBound, NULL); } else { // we can be more precise for an unsigned op lb bounds0 = bounds0.cast(unsignType(bounds0.getType())); if (! bounds0.getLb().isUnknown()) { insertPiForOpndAndAliases(block, op, bounds0.only_lower_bound(), NULL); } else { if (Log::isEnabled()) { Log::out() << "insertPiForComparison(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()) insertPiForOpndAndAliases(block, op, bounds0.only_upper_bound(), NULL); else { if (Log::isEnabled()) { Log::out() << "insertPiForComparison(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)))) { insertPiForOpndAndAliases(block, op, bounds0, NULL); } else { if (Log::isEnabled()) { Log::out() << "insertPiForComparison(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()) { insertPiForOpndAndAliases(block, op, bounds0.only_lower_bound(), NULL); } else { if (Log::isEnabled()) { Log::out() << "insertPiForComparison(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()) insertPiForOpndAndAliases(block, op, bounds0.only_upper_bound(), NULL); else { if (Log::isEnabled()) { Log::out() << "insertPiForComparison(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; } } //------------------------------------------------------------------------------ void InsertPi::insertPiForOpnd(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); } } } //------------------------------------------------------------------------------ // dereferencing through Pis, 0 if not constant. Opnd* InsertPi::getConstantOpnd(Opnd *opnd) { return ConstantFolder::isConstant(opnd) ? opnd : NULL; } //------------------------------------------------------------------------------ bool InsertPi::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(); I_32 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 *op1 = constOpnd; 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; } //------------------------------------------------------------------------------ // checks for aliases of opnd, inserts them. void InsertPi::insertPiForOpndAndAliases(Node *block, Opnd *org, const PiCondition &cond, Opnd *tauOpnd) { const PiBound &lb = cond.getLb(); const PiBound &ub = cond.getUb(); if (_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 insertPiForOpnd(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(); 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)); insertPiForOpnd(block, alias.getVar().the_var, renamedCondition, tauOpnd); } } } else { insertPiForOpnd(block, org, cond, tauOpnd); } } //------------------------------------------------------------------------------ // a DomWalker, to be applied forwards/preorder class RenamePiWalker { public: RenamePiWalker(InsertPi *insert_pi, MemoryManager &localMM, SparseOpndMap* &piMap0, int sizeEstimate0) : _insertPi(insert_pi), localMemManager(localMM), _piMap(piMap0), sizeEstimate(sizeEstimate0) {} void applyToDominatorNode(DominatorNode *domNode) { _insertPi->renamePiVariablesInNode(domNode->getNode()); } void enterScope() { if (!_piMap) _piMap = new (localMemManager) SparseOpndMap(sizeEstimate, localMemManager, 1, 4, 7); _piMap->enter_scope(); } void exitScope() { _piMap->exit_scope(); } private: InsertPi* _insertPi; MemoryManager &localMemManager; SparseOpndMap* &_piMap; int sizeEstimate; }; //------------------------------------------------------------------------------ void InsertPi::renamePiVariables() { MethodDesc &methodDesc= _irManager.getMethodDesc(); U_32 byteCodeSize = methodDesc.getByteCodeSize(); MemoryManager localMemManager("Abcd::renamePiNodes"); RenamePiWalker theWalker(this, localMemManager, _piMap, byteCodeSize); DomTreeWalk(_domTree, theWalker, localMemManager); } //------------------------------------------------------------------------------ void InsertPi::renamePiVariablesInNode(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. // Phase 0: remap just Pi inst source operands. Inst* headInst = (Inst*)block->getFirstInst(); for (Inst* inst = headInst->getNextInst(); inst != NULL; inst = inst->getNextInst()) { if (inst->getOpcode() == Op_TauPi) { // Replace Pi source operands with renames from the map. Opnd *dstOpnd = inst->getDst(); assert(dstOpnd->isPiOpnd()); Opnd *srcOpnd = inst->getSrc(0); if (_useAliases) { if (srcOpnd->isSsaVarOpnd()) { srcOpnd = srcOpnd->asSsaVarOpnd()->getVar(); } } // Find the end of the operand replace chain. // The most constrained operand is being used, the more // opportunities we have for optimization. Opnd *replaceOpnd = _piMap->lookupTillEnd(srcOpnd); if (replaceOpnd) { // Disallow remapping source operand of Pi Nodes to their // destination operands. if (Log::isEnabled()) { Log::out() << "remapping src in Pi: "; inst->print(Log::out()); Log::out() << ", replaceOpnd: "; replaceOpnd->print(Log::out()); } if (dstOpnd->getId() != replaceOpnd->getId()) { inst->setSrc(0, replaceOpnd); srcOpnd = replaceOpnd; if (Log::isEnabled()) { Log::out() << "... done" << std::endl; } } else { if (Log::isEnabled()) { Log::out() << "... defines this opnd, cannot remap" << std::endl; } } } // We now replaced the source. Add any Pi node destination to the map. _piMap->insert(srcOpnd, dstOpnd); if (Log::isEnabled()) { Log::out() << "adding remap for Pi of "; srcOpnd->print(Log::out()); Log::out() << " to "; inst->getDst()->print(Log::out()); Log::out() << std::endl; } } } // Phase 1: add Pi remappings, remap source operands of other instructions // and pi conditions. for (Inst* inst = headInst->getNextInst(); inst != NULL; inst = inst->getNextInst()) { // Remap source operands if they match a Pi definition. U_32 numOpnds = inst->getNumSrcOperands(); for (U_32 i=0; igetSrc(i); while (opnd->isPiOpnd()) { opnd = opnd->asPiOpnd()->getOrg(); } // Transitively look up for deepest Pi renamings of this operand. // The most constrained operand is being used, the more // opportunities we have for optimization. Opnd *foundOpnd = _piMap->lookupTillEnd(opnd); if (foundOpnd) { // Remap the source operand except for Pi instruction and for // array argument for chkbounds instruction. The latter is // because (a) we do not need any facts provided by pi renaming // for this operand, (b) we should limit array operand renaming // to be able to search the proof path by exact array operand // id. if (inst->getOpcode() != Op_TauPi && (inst->getOpcode() != Op_TauCheckBounds || i != 0)) { inst->setSrc(i, foundOpnd); } } } // Remap variables appearing in the condition of the Pi node. if (inst->getOpcode() == Op_TauPi) { TauPiInst *thePiInst = inst->asTauPiInst(); assert(thePiInst); if (Log::isEnabled()) { Log::out() << "remapping condition in "; inst->print(Log::out()); Log::out() << std::endl; } 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->lookupTillEnd(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->lookupTillEnd(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; } } } } } } //------------------------------------------------------------------------------ // a ScopedDomNodeInstWalker, forward/preorder class RemovePiWalker { public: RemovePiWalker(InsertPi* ins) : _insertPi(ins), block(0) // forward {} void startNode(DominatorNode *domNode) { block = domNode->getNode(); }; void applyToInst(Inst *i) { _insertPi->removePiOnInst(block, i); } void finishNode(DominatorNode *domNode) {} void enterScope() {} void exitScope() {} private: InsertPi* _insertPi; Node* block; }; //------------------------------------------------------------------------------ void InsertPi::removePi() { RemovePiWalker removePiWalker(this); typedef ScopedDomNodeInst2DomWalker RemovePiDomWalker; RemovePiDomWalker removePiDomWalker(removePiWalker); DomTreeWalk(_domTree, removePiDomWalker, _mm); } //------------------------------------------------------------------------------ void InsertPi::removePiOnInst(Node* block, Inst *inst) { if ( inst->getOpcode() == Op_TauPi ) { inst->unlink(); }else{ // replace Pi operands with original ones U_32 num_opnds = inst->getNumSrcOperands(); for (U_32 i = 0; i < num_opnds; i++) { Opnd* pi_opnd = inst->getSrc(i); while ( pi_opnd->isPiOpnd() ) { pi_opnd = pi_opnd->asPiOpnd()->getOrg(); } inst->setSrc(i, pi_opnd); } } } //------------------------------------------------------------------------------ } //namespace Jitrino