X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FValueTracking.cpp;h=5ae8574ebe13e74478b72ffd5a325273b0ab2b5e;hb=4db669fb26764b55bd9c0b8b2c2b917b135efe24;hp=3e8cb933a7af0f5011d729d2ea63178aea645dab;hpb=0bbad0131a01011e1f37e22721e7685c221ba6c8;p=oota-llvm.git diff --git a/lib/Analysis/ValueTracking.cpp b/lib/Analysis/ValueTracking.cpp index 3e8cb933a7a..5ae8574ebe1 100644 --- a/lib/Analysis/ValueTracking.cpp +++ b/lib/Analysis/ValueTracking.cpp @@ -13,8 +13,8 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/ValueTracking.h" -#include "llvm/Analysis/AssumptionTracker.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/IR/CallSite.h" @@ -65,16 +65,16 @@ namespace { // figuring out if we can use it. struct Query { ExclInvsSet ExclInvs; - AssumptionTracker *AT; + AssumptionCache *AC; const Instruction *CxtI; const DominatorTree *DT; - Query(AssumptionTracker *AT = nullptr, const Instruction *CxtI = nullptr, + Query(AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr, const DominatorTree *DT = nullptr) - : AT(AT), CxtI(CxtI), DT(DT) {} + : AC(AC), CxtI(CxtI), DT(DT) {} Query(const Query &Q, const Value *NewExcl) - : ExclInvs(Q.ExclInvs), AT(Q.AT), CxtI(Q.CxtI), DT(Q.DT) { + : ExclInvs(Q.ExclInvs), AC(Q.AC), CxtI(Q.CxtI), DT(Q.DT) { ExclInvs.insert(NewExcl); } }; @@ -102,10 +102,10 @@ static void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, void llvm::computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, const DataLayout *TD, unsigned Depth, - AssumptionTracker *AT, const Instruction *CxtI, + AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT) { ::computeKnownBits(V, KnownZero, KnownOne, TD, Depth, - Query(AT, safeCxtI(V, CxtI), DT)); + Query(AC, safeCxtI(V, CxtI), DT)); } static void ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne, @@ -114,52 +114,50 @@ static void ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne, void llvm::ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne, const DataLayout *TD, unsigned Depth, - AssumptionTracker *AT, const Instruction *CxtI, + AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT) { ::ComputeSignBit(V, KnownZero, KnownOne, TD, Depth, - Query(AT, safeCxtI(V, CxtI), DT)); + Query(AC, safeCxtI(V, CxtI), DT)); } static bool isKnownToBeAPowerOfTwo(Value *V, bool OrZero, unsigned Depth, const Query &Q); bool llvm::isKnownToBeAPowerOfTwo(Value *V, bool OrZero, unsigned Depth, - AssumptionTracker *AT, - const Instruction *CxtI, + AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT) { return ::isKnownToBeAPowerOfTwo(V, OrZero, Depth, - Query(AT, safeCxtI(V, CxtI), DT)); + Query(AC, safeCxtI(V, CxtI), DT)); } static bool isKnownNonZero(Value *V, const DataLayout *TD, unsigned Depth, const Query &Q); bool llvm::isKnownNonZero(Value *V, const DataLayout *TD, unsigned Depth, - AssumptionTracker *AT, const Instruction *CxtI, + AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT) { - return ::isKnownNonZero(V, TD, Depth, Query(AT, safeCxtI(V, CxtI), DT)); + return ::isKnownNonZero(V, TD, Depth, Query(AC, safeCxtI(V, CxtI), DT)); } static bool MaskedValueIsZero(Value *V, const APInt &Mask, const DataLayout *TD, unsigned Depth, const Query &Q); -bool llvm::MaskedValueIsZero(Value *V, const APInt &Mask, - const DataLayout *TD, unsigned Depth, - AssumptionTracker *AT, const Instruction *CxtI, - const DominatorTree *DT) { +bool llvm::MaskedValueIsZero(Value *V, const APInt &Mask, const DataLayout *TD, + unsigned Depth, AssumptionCache *AC, + const Instruction *CxtI, const DominatorTree *DT) { return ::MaskedValueIsZero(V, Mask, TD, Depth, - Query(AT, safeCxtI(V, CxtI), DT)); + Query(AC, safeCxtI(V, CxtI), DT)); } static unsigned ComputeNumSignBits(Value *V, const DataLayout *TD, unsigned Depth, const Query &Q); unsigned llvm::ComputeNumSignBits(Value *V, const DataLayout *TD, - unsigned Depth, AssumptionTracker *AT, + unsigned Depth, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT) { - return ::ComputeNumSignBits(V, TD, Depth, Query(AT, safeCxtI(V, CxtI), DT)); + return ::ComputeNumSignBits(V, TD, Depth, Query(AC, safeCxtI(V, CxtI), DT)); } static void computeKnownBitsAddSub(bool Add, Value *Op0, Value *Op1, bool NSW, @@ -312,8 +310,10 @@ void llvm::computeKnownBitsFromRangeMetadata(const MDNode &Ranges, // Use the high end of the ranges to find leading zeros. unsigned MinLeadingZeros = BitWidth; for (unsigned i = 0; i < NumRanges; ++i) { - ConstantInt *Lower = cast(Ranges.getOperand(2*i + 0)); - ConstantInt *Upper = cast(Ranges.getOperand(2*i + 1)); + ConstantInt *Lower = + mdconst::extract(Ranges.getOperand(2 * i + 0)); + ConstantInt *Upper = + mdconst::extract(Ranges.getOperand(2 * i + 1)); ConstantRange Range(Lower->getValue(), Upper->getValue()); if (Range.isWrappedSet()) MinLeadingZeros = 0; // -1 has no zeros @@ -331,7 +331,7 @@ static bool isEphemeralValueOf(Instruction *I, const Value *E) { while (!WorkSet.empty()) { const Value *V = WorkSet.pop_back_val(); - if (!Visited.insert(V)) + if (!Visited.insert(V).second) continue; // If all uses of this value are ephemeral, then so is this value. @@ -480,18 +480,31 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, unsigned Depth, const Query &Q) { // Use of assumptions is context-sensitive. If we don't have a context, we // cannot use them! - if (!Q.AT || !Q.CxtI) + if (!Q.AC || !Q.CxtI) return; unsigned BitWidth = KnownZero.getBitWidth(); - Function *F = const_cast(Q.CxtI->getParent()->getParent()); - for (auto &CI : Q.AT->assumptions(F)) { - CallInst *I = CI; + for (auto &AssumeVH : Q.AC->assumptions()) { + if (!AssumeVH) + continue; + CallInst *I = cast(AssumeVH); + assert(I->getParent()->getParent() == Q.CxtI->getParent()->getParent() && + "Got assumption for the wrong function!"); if (Q.ExclInvs.count(I)) continue; - if (match(I, m_Intrinsic(m_Specific(V))) && + // Warning: This loop can end up being somewhat performance sensetive. + // We're running this loop for once for each value queried resulting in a + // runtime of ~O(#assumes * #values). + + assert(isa(I) && + dyn_cast(I)->getIntrinsicID() == Intrinsic::assume && + "must be an assume intrinsic"); + + Value *Arg = I->getArgOperand(0); + + if (Arg == V && isValidAssumeForContext(I, Q, DL)) { assert(BitWidth == 1 && "assume operand is not i1?"); KnownZero.clearAllBits(); @@ -499,6 +512,10 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, return; } + // The remaining tests are all recursive, so bail out if we hit the limit. + if (Depth == MaxDepth) + continue; + Value *A, *B; auto m_V = m_CombineOr(m_Specific(V), m_CombineOr(m_PtrToInt(m_Specific(V)), @@ -507,16 +524,15 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, CmpInst::Predicate Pred; ConstantInt *C; // assume(v = a) - if (match(I, m_Intrinsic( - m_c_ICmp(Pred, m_V, m_Value(A)))) && + if (match(Arg, m_c_ICmp(Pred, m_V, m_Value(A))) && Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q, DL)) { APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0); computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I)); KnownZero |= RHSKnownZero; KnownOne |= RHSKnownOne; // assume(v & b = a) - } else if (match(I, m_Intrinsic( - m_c_ICmp(Pred, m_c_And(m_V, m_Value(B)), m_Value(A)))) && + } else if (match(Arg, m_c_ICmp(Pred, m_c_And(m_V, m_Value(B)), + m_Value(A))) && Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q, DL)) { APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0); computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I)); @@ -528,9 +544,8 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, KnownZero |= RHSKnownZero & MaskKnownOne; KnownOne |= RHSKnownOne & MaskKnownOne; // assume(~(v & b) = a) - } else if (match(I, m_Intrinsic( - m_c_ICmp(Pred, m_Not(m_c_And(m_V, m_Value(B))), - m_Value(A)))) && + } else if (match(Arg, m_c_ICmp(Pred, m_Not(m_c_And(m_V, m_Value(B))), + m_Value(A))) && Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q, DL)) { APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0); computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I)); @@ -542,8 +557,8 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, KnownZero |= RHSKnownOne & MaskKnownOne; KnownOne |= RHSKnownZero & MaskKnownOne; // assume(v | b = a) - } else if (match(I, m_Intrinsic( - m_c_ICmp(Pred, m_c_Or(m_V, m_Value(B)), m_Value(A)))) && + } else if (match(Arg, m_c_ICmp(Pred, m_c_Or(m_V, m_Value(B)), + m_Value(A))) && Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q, DL)) { APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0); computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I)); @@ -555,9 +570,8 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, KnownZero |= RHSKnownZero & BKnownZero; KnownOne |= RHSKnownOne & BKnownZero; // assume(~(v | b) = a) - } else if (match(I, m_Intrinsic( - m_c_ICmp(Pred, m_Not(m_c_Or(m_V, m_Value(B))), - m_Value(A)))) && + } else if (match(Arg, m_c_ICmp(Pred, m_Not(m_c_Or(m_V, m_Value(B))), + m_Value(A))) && Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q, DL)) { APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0); computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I)); @@ -569,8 +583,8 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, KnownZero |= RHSKnownOne & BKnownZero; KnownOne |= RHSKnownZero & BKnownZero; // assume(v ^ b = a) - } else if (match(I, m_Intrinsic( - m_c_ICmp(Pred, m_c_Xor(m_V, m_Value(B)), m_Value(A)))) && + } else if (match(Arg, m_c_ICmp(Pred, m_c_Xor(m_V, m_Value(B)), + m_Value(A))) && Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q, DL)) { APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0); computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I)); @@ -585,9 +599,8 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, KnownZero |= RHSKnownOne & BKnownOne; KnownOne |= RHSKnownZero & BKnownOne; // assume(~(v ^ b) = a) - } else if (match(I, m_Intrinsic( - m_c_ICmp(Pred, m_Not(m_c_Xor(m_V, m_Value(B))), - m_Value(A)))) && + } else if (match(Arg, m_c_ICmp(Pred, m_Not(m_c_Xor(m_V, m_Value(B))), + m_Value(A))) && Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q, DL)) { APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0); computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I)); @@ -602,9 +615,8 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, KnownZero |= RHSKnownZero & BKnownOne; KnownOne |= RHSKnownOne & BKnownOne; // assume(v << c = a) - } else if (match(I, m_Intrinsic( - m_c_ICmp(Pred, m_Shl(m_V, m_ConstantInt(C)), - m_Value(A)))) && + } else if (match(Arg, m_c_ICmp(Pred, m_Shl(m_V, m_ConstantInt(C)), + m_Value(A))) && Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q, DL)) { APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0); computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I)); @@ -613,9 +625,8 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, KnownZero |= RHSKnownZero.lshr(C->getZExtValue()); KnownOne |= RHSKnownOne.lshr(C->getZExtValue()); // assume(~(v << c) = a) - } else if (match(I, m_Intrinsic( - m_c_ICmp(Pred, m_Not(m_Shl(m_V, m_ConstantInt(C))), - m_Value(A)))) && + } else if (match(Arg, m_c_ICmp(Pred, m_Not(m_Shl(m_V, m_ConstantInt(C))), + m_Value(A))) && Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q, DL)) { APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0); computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I)); @@ -624,11 +635,11 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, KnownZero |= RHSKnownOne.lshr(C->getZExtValue()); KnownOne |= RHSKnownZero.lshr(C->getZExtValue()); // assume(v >> c = a) - } else if (match(I, m_Intrinsic( - m_c_ICmp(Pred, m_CombineOr(m_LShr(m_V, m_ConstantInt(C)), + } else if (match(Arg, + m_c_ICmp(Pred, m_CombineOr(m_LShr(m_V, m_ConstantInt(C)), m_AShr(m_V, m_ConstantInt(C))), - m_Value(A)))) && + m_Value(A))) && Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q, DL)) { APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0); computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I)); @@ -637,11 +648,10 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, KnownZero |= RHSKnownZero << C->getZExtValue(); KnownOne |= RHSKnownOne << C->getZExtValue(); // assume(~(v >> c) = a) - } else if (match(I, m_Intrinsic( - m_c_ICmp(Pred, m_Not(m_CombineOr( + } else if (match(Arg, m_c_ICmp(Pred, m_Not(m_CombineOr( m_LShr(m_V, m_ConstantInt(C)), m_AShr(m_V, m_ConstantInt(C)))), - m_Value(A)))) && + m_Value(A))) && Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q, DL)) { APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0); computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I)); @@ -650,8 +660,7 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, KnownZero |= RHSKnownOne << C->getZExtValue(); KnownOne |= RHSKnownZero << C->getZExtValue(); // assume(v >=_s c) where c is non-negative - } else if (match(I, m_Intrinsic( - m_ICmp(Pred, m_V, m_Value(A)))) && + } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) && Pred == ICmpInst::ICMP_SGE && isValidAssumeForContext(I, Q, DL)) { APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0); @@ -662,8 +671,7 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, KnownZero |= APInt::getSignBit(BitWidth); } // assume(v >_s c) where c is at least -1. - } else if (match(I, m_Intrinsic( - m_ICmp(Pred, m_V, m_Value(A)))) && + } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) && Pred == ICmpInst::ICMP_SGT && isValidAssumeForContext(I, Q, DL)) { APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0); @@ -674,8 +682,7 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, KnownZero |= APInt::getSignBit(BitWidth); } // assume(v <=_s c) where c is negative - } else if (match(I, m_Intrinsic( - m_ICmp(Pred, m_V, m_Value(A)))) && + } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) && Pred == ICmpInst::ICMP_SLE && isValidAssumeForContext(I, Q, DL)) { APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0); @@ -686,8 +693,7 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, KnownOne |= APInt::getSignBit(BitWidth); } // assume(v <_s c) where c is non-positive - } else if (match(I, m_Intrinsic( - m_ICmp(Pred, m_V, m_Value(A)))) && + } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) && Pred == ICmpInst::ICMP_SLT && isValidAssumeForContext(I, Q, DL)) { APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0); @@ -698,8 +704,7 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, KnownOne |= APInt::getSignBit(BitWidth); } // assume(v <=_u c) - } else if (match(I, m_Intrinsic( - m_ICmp(Pred, m_V, m_Value(A)))) && + } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) && Pred == ICmpInst::ICMP_ULE && isValidAssumeForContext(I, Q, DL)) { APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0); @@ -709,8 +714,7 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, KnownZero |= APInt::getHighBitsSet(BitWidth, RHSKnownZero.countLeadingOnes()); // assume(v <_u c) - } else if (match(I, m_Intrinsic( - m_ICmp(Pred, m_V, m_Value(A)))) && + } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) && Pred == ICmpInst::ICMP_ULT && isValidAssumeForContext(I, Q, DL)) { APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0); @@ -790,22 +794,11 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, return; } - // A weak GlobalAlias is totally unknown. A non-weak GlobalAlias has - // the bits of its aliasee. - if (GlobalAlias *GA = dyn_cast(V)) { - if (GA->mayBeOverridden()) { - KnownZero.clearAllBits(); KnownOne.clearAllBits(); - } else { - computeKnownBits(GA->getAliasee(), KnownZero, KnownOne, TD, Depth+1, Q); - } - return; - } - // The address of an aligned GlobalValue has trailing zeros. - if (GlobalValue *GV = dyn_cast(V)) { - unsigned Align = GV->getAlignment(); + if (auto *GO = dyn_cast(V)) { + unsigned Align = GO->getAlignment(); if (Align == 0 && TD) { - if (GlobalVariable *GVar = dyn_cast(GV)) { + if (auto *GVar = dyn_cast(GO)) { Type *ObjectType = GVar->getType()->getElementType(); if (ObjectType->isSized()) { // If the object is defined in the current Module, we'll be giving @@ -839,6 +832,9 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, if (Align) KnownZero = APInt::getLowBitsSet(BitWidth, countTrailingZeros(Align)); + else + KnownZero.clearAllBits(); + KnownOne.clearAllBits(); // Don't give up yet... there might be an assumption that provides more // information... @@ -849,8 +845,18 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, // Start out not knowing anything. KnownZero.clearAllBits(); KnownOne.clearAllBits(); + // Limit search depth. + // All recursive calls that increase depth must come after this. if (Depth == MaxDepth) - return; // Limit search depth. + return; + + // A weak GlobalAlias is totally unknown. A non-weak GlobalAlias has + // the bits of its aliasee. + if (GlobalAlias *GA = dyn_cast(V)) { + if (!GA->mayBeOverridden()) + computeKnownBits(GA->getAliasee(), KnownZero, KnownOne, TD, Depth + 1, Q); + return; + } // Check whether a nearby assume intrinsic can determine some known bits. computeKnownBitsFromAssume(V, KnownZero, KnownOne, TD, Depth, Q); @@ -862,7 +868,7 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, switch (I->getOpcode()) { default: break; case Instruction::Load: - if (MDNode *MD = cast(I)->getMDNode(LLVMContext::MD_range)) + if (MDNode *MD = cast(I)->getMetadata(LLVMContext::MD_range)) computeKnownBitsFromRangeMetadata(*MD, KnownZero); break; case Instruction::And: { @@ -1005,7 +1011,6 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, KnownZero <<= ShiftAmt; KnownOne <<= ShiftAmt; KnownZero |= APInt::getLowBitsSet(BitWidth, ShiftAmt); // low bits known 0 - break; } break; case Instruction::LShr: @@ -1015,12 +1020,11 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, uint64_t ShiftAmt = SA->getLimitedValue(BitWidth); // Unsigned shift right. - computeKnownBits(I->getOperand(0), KnownZero,KnownOne, TD, Depth+1, Q); + computeKnownBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1, Q); KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); // high bits known zero. KnownZero |= APInt::getHighBitsSet(BitWidth, ShiftAmt); - break; } break; case Instruction::AShr: @@ -1039,7 +1043,6 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, KnownZero |= HighBits; else if (KnownOne[BitWidth-ShiftAmt-1]) // New bits are known one. KnownOne |= HighBits; - break; } break; case Instruction::Sub: { @@ -1261,7 +1264,7 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, } case Instruction::Call: case Instruction::Invoke: - if (MDNode *MD = cast(I)->getMDNode(LLVMContext::MD_range)) + if (MDNode *MD = cast(I)->getMetadata(LLVMContext::MD_range)) computeKnownBitsFromRangeMetadata(*MD, KnownZero); // If a range metadata is attached to this IntrinsicInst, intersect the // explicit range specified by the metadata and the implicit range of @@ -1510,8 +1513,10 @@ static bool rangeMetadataExcludesValue(MDNode* Ranges, const unsigned NumRanges = Ranges->getNumOperands() / 2; assert(NumRanges >= 1); for (unsigned i = 0; i < NumRanges; ++i) { - ConstantInt *Lower = cast(Ranges->getOperand(2*i + 0)); - ConstantInt *Upper = cast(Ranges->getOperand(2*i + 1)); + ConstantInt *Lower = + mdconst::extract(Ranges->getOperand(2 * i + 0)); + ConstantInt *Upper = + mdconst::extract(Ranges->getOperand(2 * i + 1)); ConstantRange Range(Lower->getValue(), Upper->getValue()); if (Range.contains(Value)) return false; @@ -1536,7 +1541,7 @@ bool isKnownNonZero(Value *V, const DataLayout *TD, unsigned Depth, } if (Instruction* I = dyn_cast(V)) { - if (MDNode *Ranges = I->getMDNode(LLVMContext::MD_range)) { + if (MDNode *Ranges = I->getMetadata(LLVMContext::MD_range)) { // If the possible ranges don't contain zero, then the value is // definitely non-zero. if (IntegerType* Ty = dyn_cast(V->getType())) { @@ -1767,7 +1772,7 @@ unsigned ComputeNumSignBits(Value *V, const DataLayout *TD, if (Tmp == 1) return 1; // Early out. // Special case decrementing a value (ADD X, -1): - if (ConstantInt *CRHS = dyn_cast(U->getOperand(1))) + if (const auto *CRHS = dyn_cast(U->getOperand(1))) if (CRHS->isAllOnesValue()) { APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0); computeKnownBits(U->getOperand(0), KnownZero, KnownOne, TD, Depth+1, Q); @@ -1792,7 +1797,7 @@ unsigned ComputeNumSignBits(Value *V, const DataLayout *TD, if (Tmp2 == 1) return 1; // Handle NEG. - if (ConstantInt *CLHS = dyn_cast(U->getOperand(0))) + if (const auto *CLHS = dyn_cast(U->getOperand(0))) if (CLHS->isNullValue()) { APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0); computeKnownBits(U->getOperand(1), KnownZero, KnownOne, TD, Depth+1, Q); @@ -1817,13 +1822,16 @@ unsigned ComputeNumSignBits(Value *V, const DataLayout *TD, case Instruction::PHI: { PHINode *PN = cast(U); + unsigned NumIncomingValues = PN->getNumIncomingValues(); // Don't analyze large in-degree PHIs. - if (PN->getNumIncomingValues() > 4) break; + if (NumIncomingValues > 4) break; + // Unreachable blocks may have zero-operand PHI nodes. + if (NumIncomingValues == 0) break; // Take the minimum of all incoming values. This can't infinitely loop // because of our depth threshold. Tmp = ComputeNumSignBits(PN->getIncomingValue(0), TD, Depth+1, Q); - for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) { + for (unsigned i = 1, e = NumIncomingValues; i != e; ++i) { if (Tmp == 1) return Tmp; Tmp = std::min(Tmp, ComputeNumSignBits(PN->getIncomingValue(i), TD, @@ -2036,6 +2044,59 @@ bool llvm::CannotBeNegativeZero(const Value *V, unsigned Depth) { return false; } +bool llvm::CannotBeOrderedLessThanZero(const Value *V, unsigned Depth) { + if (const ConstantFP *CFP = dyn_cast(V)) + return !CFP->getValueAPF().isNegative() || CFP->getValueAPF().isZero(); + + if (Depth == 6) + return false; // Limit search depth. + + const Operator *I = dyn_cast(V); + if (!I) return false; + + switch (I->getOpcode()) { + default: break; + case Instruction::FMul: + // x*x is always non-negative or a NaN. + if (I->getOperand(0) == I->getOperand(1)) + return true; + // Fall through + case Instruction::FAdd: + case Instruction::FDiv: + case Instruction::FRem: + return CannotBeOrderedLessThanZero(I->getOperand(0), Depth+1) && + CannotBeOrderedLessThanZero(I->getOperand(1), Depth+1); + case Instruction::FPExt: + case Instruction::FPTrunc: + // Widening/narrowing never change sign. + return CannotBeOrderedLessThanZero(I->getOperand(0), Depth+1); + case Instruction::Call: + if (const IntrinsicInst *II = dyn_cast(I)) + switch (II->getIntrinsicID()) { + default: break; + case Intrinsic::exp: + case Intrinsic::exp2: + case Intrinsic::fabs: + case Intrinsic::sqrt: + return true; + case Intrinsic::powi: + if (ConstantInt *CI = dyn_cast(I->getOperand(1))) { + // powi(x,n) is non-negative if n is even. + if (CI->getBitWidth() <= 64 && CI->getSExtValue() % 2u == 0) + return true; + } + return CannotBeOrderedLessThanZero(I->getOperand(0), Depth+1); + case Intrinsic::fma: + case Intrinsic::fmuladd: + // x*x+y is non-negative if y is non-negative. + return I->getOperand(0) == I->getOperand(1) && + CannotBeOrderedLessThanZero(I->getOperand(2), Depth+1); + } + break; + } + return false; +} + /// If the specified value can be set by repeating the same byte in memory, /// return the i8 value that it is represented with. This is /// true for all i8 values obviously, but is also true for i32 0, i32 -1, @@ -2060,26 +2121,16 @@ Value *llvm::isBytewiseValue(Value *V) { // Don't handle long double formats, which have strange constraints. } - // We can handle constant integers that are power of two in size and a - // multiple of 8 bits. + // We can handle constant integers that are multiple of 8 bits. if (ConstantInt *CI = dyn_cast(V)) { - unsigned Width = CI->getBitWidth(); - if (isPowerOf2_32(Width) && Width > 8) { - // We can handle this value if the recursive binary decomposition is the - // same at all levels. - APInt Val = CI->getValue(); - APInt Val2; - while (Val.getBitWidth() != 8) { - unsigned NextWidth = Val.getBitWidth()/2; - Val2 = Val.lshr(NextWidth); - Val2 = Val2.trunc(Val.getBitWidth()/2); - Val = Val.trunc(Val.getBitWidth()/2); - - // If the top/bottom halves aren't the same, reject it. - if (Val != Val2) - return nullptr; - } - return ConstantInt::get(V->getContext(), Val); + if (CI->getBitWidth() % 8 == 0) { + assert(CI->getBitWidth() > 8 && "8 bits should be handled above!"); + + // We can check that all bytes of an integer are equal by making use of a + // little trick: rotate by 8 and check if it's still the same value. + if (CI->getValue() != CI->getValue().rotl(8)) + return nullptr; + return ConstantInt::get(V->getContext(), CI->getValue().trunc(8)); } } @@ -2408,7 +2459,7 @@ static uint64_t GetStringLengthH(Value *V, SmallPtrSetImpl &PHIs) { // If this is a PHI node, there are two cases: either we have already seen it // or we haven't. if (PHINode *PN = dyn_cast(V)) { - if (!PHIs.insert(PN)) + if (!PHIs.insert(PN).second) return ~0ULL; // already in the set. // If it was new, see if all the input strings are the same length. @@ -2477,7 +2528,7 @@ llvm::GetUnderlyingObject(Value *V, const DataLayout *TD, unsigned MaxLookup) { } else { // See if InstructionSimplify knows any relevant tricks. if (Instruction *I = dyn_cast(V)) - // TODO: Acquire a DominatorTree and AssumptionTracker and use them. + // TODO: Acquire a DominatorTree and AssumptionCache and use them. if (Value *Simplified = SimplifyInstruction(I, TD, nullptr)) { V = Simplified; continue; @@ -2502,7 +2553,7 @@ llvm::GetUnderlyingObjects(Value *V, Value *P = Worklist.pop_back_val(); P = GetUnderlyingObject(P, TD, MaxLookup); - if (!Visited.insert(P)) + if (!Visited.insert(P).second) continue; if (SelectInst *SI = dyn_cast(P)) { @@ -2549,23 +2600,31 @@ bool llvm::isSafeToSpeculativelyExecute(const Value *V, default: return true; case Instruction::UDiv: - case Instruction::URem: - // x / y is undefined if y == 0, but calculations like x / 3 are safe. - return isKnownNonZero(Inst->getOperand(1), TD); + case Instruction::URem: { + // x / y is undefined if y == 0. + const APInt *V; + if (match(Inst->getOperand(1), m_APInt(V))) + return *V != 0; + return false; + } case Instruction::SDiv: case Instruction::SRem: { - Value *Op = Inst->getOperand(1); - // x / y is undefined if y == 0 - if (!isKnownNonZero(Op, TD)) + // x / y is undefined if y == 0 or x == INT_MIN and y == -1 + const APInt *Numerator, *Denominator; + if (!match(Inst->getOperand(1), m_APInt(Denominator))) return false; - // x / y might be undefined if y == -1 - unsigned BitWidth = getBitWidth(Op->getType(), TD); - if (BitWidth == 0) + // We cannot hoist this division if the denominator is 0. + if (*Denominator == 0) return false; - APInt KnownZero(BitWidth, 0); - APInt KnownOne(BitWidth, 0); - computeKnownBits(Op, KnownZero, KnownOne, TD); - return !!KnownZero; + // It's safe to hoist if the denominator is not 0 or -1. + if (*Denominator != -1) + return true; + // At this point we know that the denominator is -1. It is safe to hoist as + // long we know that the numerator is not INT_MIN. + if (match(Inst->getOperand(0), m_APInt(Numerator))) + return !Numerator->isMinSignedValue(); + // The numerator *might* be MinSignedValue. + return false; } case Instruction::Load: { const LoadInst *LI = cast(Inst); @@ -2576,44 +2635,44 @@ bool llvm::isSafeToSpeculativelyExecute(const Value *V, return LI->getPointerOperand()->isDereferenceablePointer(TD); } case Instruction::Call: { - if (const IntrinsicInst *II = dyn_cast(Inst)) { - switch (II->getIntrinsicID()) { - // These synthetic intrinsics have no side-effects and just mark - // information about their operands. - // FIXME: There are other no-op synthetic instructions that potentially - // should be considered at least *safe* to speculate... - case Intrinsic::dbg_declare: - case Intrinsic::dbg_value: - return true; - - case Intrinsic::bswap: - case Intrinsic::ctlz: - case Intrinsic::ctpop: - case Intrinsic::cttz: - case Intrinsic::objectsize: - case Intrinsic::sadd_with_overflow: - case Intrinsic::smul_with_overflow: - case Intrinsic::ssub_with_overflow: - case Intrinsic::uadd_with_overflow: - case Intrinsic::umul_with_overflow: - case Intrinsic::usub_with_overflow: - return true; - // Sqrt should be OK, since the llvm sqrt intrinsic isn't defined to set - // errno like libm sqrt would. - case Intrinsic::sqrt: - case Intrinsic::fma: - case Intrinsic::fmuladd: - case Intrinsic::fabs: - case Intrinsic::minnum: - case Intrinsic::maxnum: - return true; - // TODO: some fp intrinsics are marked as having the same error handling - // as libm. They're safe to speculate when they won't error. - // TODO: are convert_{from,to}_fp16 safe? - // TODO: can we list target-specific intrinsics here? - default: break; - } - } + if (const IntrinsicInst *II = dyn_cast(Inst)) { + switch (II->getIntrinsicID()) { + // These synthetic intrinsics have no side-effects and just mark + // information about their operands. + // FIXME: There are other no-op synthetic instructions that potentially + // should be considered at least *safe* to speculate... + case Intrinsic::dbg_declare: + case Intrinsic::dbg_value: + return true; + + case Intrinsic::bswap: + case Intrinsic::ctlz: + case Intrinsic::ctpop: + case Intrinsic::cttz: + case Intrinsic::objectsize: + case Intrinsic::sadd_with_overflow: + case Intrinsic::smul_with_overflow: + case Intrinsic::ssub_with_overflow: + case Intrinsic::uadd_with_overflow: + case Intrinsic::umul_with_overflow: + case Intrinsic::usub_with_overflow: + return true; + // Sqrt should be OK, since the llvm sqrt intrinsic isn't defined to set + // errno like libm sqrt would. + case Intrinsic::sqrt: + case Intrinsic::fma: + case Intrinsic::fmuladd: + case Intrinsic::fabs: + case Intrinsic::minnum: + case Intrinsic::maxnum: + return true; + // TODO: some fp intrinsics are marked as having the same error handling + // as libm. They're safe to speculate when they won't error. + // TODO: are convert_{from,to}_fp16 safe? + // TODO: can we list target-specific intrinsics here? + default: break; + } + } return false; // The called function could have undefined behavior or // side-effects, even if marked readnone nounwind. } @@ -2663,3 +2722,82 @@ bool llvm::isKnownNonNull(const Value *V, const TargetLibraryInfo *TLI) { return false; } + +OverflowResult llvm::computeOverflowForUnsignedMul(Value *LHS, Value *RHS, + const DataLayout *DL, + AssumptionCache *AC, + const Instruction *CxtI, + const DominatorTree *DT) { + // Multiplying n * m significant bits yields a result of n + m significant + // bits. If the total number of significant bits does not exceed the + // result bit width (minus 1), there is no overflow. + // This means if we have enough leading zero bits in the operands + // we can guarantee that the result does not overflow. + // Ref: "Hacker's Delight" by Henry Warren + unsigned BitWidth = LHS->getType()->getScalarSizeInBits(); + APInt LHSKnownZero(BitWidth, 0); + APInt LHSKnownOne(BitWidth, 0); + APInt RHSKnownZero(BitWidth, 0); + APInt RHSKnownOne(BitWidth, 0); + computeKnownBits(LHS, LHSKnownZero, LHSKnownOne, DL, /*Depth=*/0, AC, CxtI, + DT); + computeKnownBits(RHS, RHSKnownZero, RHSKnownOne, DL, /*Depth=*/0, AC, CxtI, + DT); + // Note that underestimating the number of zero bits gives a more + // conservative answer. + unsigned ZeroBits = LHSKnownZero.countLeadingOnes() + + RHSKnownZero.countLeadingOnes(); + // First handle the easy case: if we have enough zero bits there's + // definitely no overflow. + if (ZeroBits >= BitWidth) + return OverflowResult::NeverOverflows; + + // Get the largest possible values for each operand. + APInt LHSMax = ~LHSKnownZero; + APInt RHSMax = ~RHSKnownZero; + + // We know the multiply operation doesn't overflow if the maximum values for + // each operand will not overflow after we multiply them together. + bool MaxOverflow; + LHSMax.umul_ov(RHSMax, MaxOverflow); + if (!MaxOverflow) + return OverflowResult::NeverOverflows; + + // We know it always overflows if multiplying the smallest possible values for + // the operands also results in overflow. + bool MinOverflow; + LHSKnownOne.umul_ov(RHSKnownOne, MinOverflow); + if (MinOverflow) + return OverflowResult::AlwaysOverflows; + + return OverflowResult::MayOverflow; +} + +OverflowResult llvm::computeOverflowForUnsignedAdd(Value *LHS, Value *RHS, + const DataLayout *DL, + AssumptionCache *AC, + const Instruction *CxtI, + const DominatorTree *DT) { + bool LHSKnownNonNegative, LHSKnownNegative; + ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, DL, /*Depth=*/0, + AC, CxtI, DT); + if (LHSKnownNonNegative || LHSKnownNegative) { + bool RHSKnownNonNegative, RHSKnownNegative; + ComputeSignBit(RHS, RHSKnownNonNegative, RHSKnownNegative, DL, /*Depth=*/0, + AC, CxtI, DT); + + if (LHSKnownNegative && RHSKnownNegative) { + // The sign bit is set in both cases: this MUST overflow. + // Create a simple add instruction, and insert it into the struct. + return OverflowResult::AlwaysOverflows; + } + + if (LHSKnownNonNegative && RHSKnownNonNegative) { + // The sign bit is clear in both cases: this CANNOT overflow. + // Create a simple add instruction, and insert it into the struct. + return OverflowResult::NeverOverflows; + } + } + + return OverflowResult::MayOverflow; +}