X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FValueTracking.cpp;h=5ae8574ebe13e74478b72ffd5a325273b0ab2b5e;hb=8c6097d490256cd3a89b185feb401c63ff5805d1;hp=53f3be51665e9cc732d2c79f0740be3fbf383bb0;hpb=9be94733945e1b5da59bea1d84fc40efbfafc96e;p=oota-llvm.git diff --git a/lib/Analysis/ValueTracking.cpp b/lib/Analysis/ValueTracking.cpp index 53f3be51665..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" @@ -39,8 +39,8 @@ using namespace llvm::PatternMatch; const unsigned MaxDepth = 6; -/// getBitWidth - Returns the bitwidth of the given scalar or pointer type (if -/// unknown returns 0). For vector types, returns the element type's bitwidth. +/// Returns the bitwidth of the given scalar or pointer type (if unknown returns +/// 0). For vector types, returns the element type's bitwidth. static unsigned getBitWidth(Type *Ty, const DataLayout *TD) { if (unsigned BitWidth = Ty->getScalarSizeInBits()) return BitWidth; @@ -65,22 +65,22 @@ 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); } }; } // end anonymous namespace -// Given the provided Value and, potentially, a context instruction, returned +// Given the provided Value and, potentially, a context instruction, return // the preferred context instruction (if any). static const Instruction *safeCxtI(const Value *V, const Instruction *CxtI) { // If we've been provided with a context instruction, then use that (provided @@ -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); @@ -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: { @@ -1322,8 +1325,8 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); } -/// ComputeSignBit - Determine whether the sign bit is known to be zero or -/// one. Convenience wrapper around computeKnownBits. +/// Determine whether the sign bit is known to be zero or one. +/// Convenience wrapper around computeKnownBits. void ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne, const DataLayout *TD, unsigned Depth, const Query &Q) { @@ -1340,9 +1343,9 @@ void ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne, KnownZero = ZeroBits[BitWidth - 1]; } -/// isKnownToBeAPowerOfTwo - Return true if the given value is known to have exactly one +/// Return true if the given value is known to have exactly one /// bit set when defined. For vectors return true if every element is known to -/// be a power of two when defined. Supports values with integer or pointer +/// be a power of two when defined. Supports values with integer or pointer /// types and vectors of integers. bool isKnownToBeAPowerOfTwo(Value *V, bool OrZero, unsigned Depth, const Query &Q) { @@ -1502,10 +1505,29 @@ static bool isGEPKnownNonNull(GEPOperator *GEP, const DataLayout *DL, return false; } -/// isKnownNonZero - Return true if the given value is known to be non-zero -/// when defined. For vectors return true if every element is known to be -/// non-zero when defined. Supports values with integer or pointer type and -/// vectors of integers. +/// Does the 'Range' metadata (which must be a valid MD_range operand list) +/// ensure that the value it's attached to is never Value? 'RangeType' is +/// is the type of the value described by the range. +static bool rangeMetadataExcludesValue(MDNode* Ranges, + const APInt& Value) { + const unsigned NumRanges = Ranges->getNumOperands() / 2; + assert(NumRanges >= 1); + for (unsigned i = 0; i < NumRanges; ++i) { + 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; + } + return true; +} + +/// Return true if the given value is known to be non-zero when defined. +/// For vectors return true if every element is known to be non-zero when +/// defined. Supports values with integer or pointer type and vectors of +/// integers. bool isKnownNonZero(Value *V, const DataLayout *TD, unsigned Depth, const Query &Q) { if (Constant *C = dyn_cast(V)) { @@ -1518,6 +1540,18 @@ bool isKnownNonZero(Value *V, const DataLayout *TD, unsigned Depth, return false; } + if (Instruction* I = dyn_cast(V)) { + 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())) { + const APInt ZeroValue(Ty->getBitWidth(), 0); + if (rangeMetadataExcludesValue(Ranges, ZeroValue)) + return true; + } + } + } + // The remaining tests are all recursive, so bail out if we hit the limit. if (Depth++ >= MaxDepth) return false; @@ -1638,9 +1672,9 @@ bool isKnownNonZero(Value *V, const DataLayout *TD, unsigned Depth, return KnownOne != 0; } -/// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use -/// this predicate to simplify operations downstream. Mask is known to be zero -/// for bits that V cannot have. +/// Return true if 'V & Mask' is known to be zero. We use this predicate to +/// simplify operations downstream. Mask is known to be zero for bits that V +/// cannot have. /// /// This function is defined on values with integer type, values with pointer /// type (but only if TD is non-null), and vectors of integers. In the case @@ -1657,11 +1691,11 @@ bool MaskedValueIsZero(Value *V, const APInt &Mask, -/// ComputeNumSignBits - Return the number of times the sign bit of the -/// register is replicated into the other bits. We know that at least 1 bit -/// is always equal to the sign bit (itself), but other cases can give us -/// information. For example, immediately after an "ashr X, 2", we know that -/// the top 3 bits are all equal to each other, so we return 3. +/// Return the number of times the sign bit of the register is replicated into +/// the other bits. We know that at least 1 bit is always equal to the sign bit +/// (itself), but other cases can give us information. For example, immediately +/// after an "ashr X, 2", we know that the top 3 bits are all equal to each +/// other, so we return 3. /// /// 'Op' must have a scalar integer type. /// @@ -1738,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); @@ -1763,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); @@ -1788,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, @@ -1833,9 +1870,9 @@ unsigned ComputeNumSignBits(Value *V, const DataLayout *TD, return std::max(FirstAnswer, std::min(TyBits, Mask.countLeadingZeros())); } -/// ComputeMultiple - This function computes the integer multiple of Base that -/// equals V. If successful, it returns true and returns the multiple in -/// Multiple. If unsuccessful, it returns false. It looks +/// This function computes the integer multiple of Base that equals V. +/// If successful, it returns true and returns the multiple in +/// Multiple. If unsuccessful, it returns false. It looks /// through SExt instructions only if LookThroughSExt is true. bool llvm::ComputeMultiple(Value *V, unsigned Base, Value *&Multiple, bool LookThroughSExt, unsigned Depth) { @@ -1953,8 +1990,8 @@ bool llvm::ComputeMultiple(Value *V, unsigned Base, Value *&Multiple, return false; } -/// CannotBeNegativeZero - Return true if we can prove that the specified FP -/// value is never equal to -0.0. +/// Return true if we can prove that the specified FP value is never equal to +/// -0.0. /// /// NOTE: this function will need to be revisited when we support non-default /// rounding modes! @@ -2007,8 +2044,61 @@ bool llvm::CannotBeNegativeZero(const Value *V, unsigned Depth) { return false; } -/// isBytewiseValue - 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 +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, /// i16 0xF0F0, double 0.0 etc. If the value can't be handled with a repeated /// byte store (e.g. i16 0x1234), return null. @@ -2031,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)); } } @@ -2156,7 +2236,7 @@ static Value *BuildSubAggregate(Value *From, ArrayRef idx_range, return BuildSubAggregate(From, To, IndexedType, Idxs, IdxSkip, InsertBefore); } -/// FindInsertedValue - Given an aggregrate and an sequence of indices, see if +/// Given an aggregrate and an sequence of indices, see if /// the scalar value indexed is already around as a register, for example if it /// were inserted directly into the aggregrate. /// @@ -2246,9 +2326,8 @@ Value *llvm::FindInsertedValue(Value *V, ArrayRef idx_range, return nullptr; } -/// GetPointerBaseWithConstantOffset - Analyze the specified pointer to see if -/// it can be expressed as a base pointer plus a constant offset. Return the -/// base and offset to the caller. +/// Analyze the specified pointer to see if it can be expressed as a base +/// pointer plus a constant offset. Return the base and offset to the caller. Value *llvm::GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, const DataLayout *DL) { // Without DataLayout, conservatively assume 64-bit offsets, which is @@ -2285,9 +2364,9 @@ Value *llvm::GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, } -/// getConstantStringInfo - This function computes the length of a -/// null-terminated C string pointed to by V. If successful, it returns true -/// and returns the string in Str. If unsuccessful, it returns false. +/// This function computes the length of a null-terminated C string pointed to +/// by V. If successful, it returns true and returns the string in Str. +/// If unsuccessful, it returns false. bool llvm::getConstantStringInfo(const Value *V, StringRef &Str, uint64_t Offset, bool TrimAtNul) { assert(V); @@ -2371,7 +2450,7 @@ bool llvm::getConstantStringInfo(const Value *V, StringRef &Str, // nodes. // TODO: See if we can integrate these two together. -/// GetStringLengthH - If we can compute the length of the string pointed to by +/// If we can compute the length of the string pointed to by /// the specified pointer, return 'len+1'. If we can't, return 0. static uint64_t GetStringLengthH(Value *V, SmallPtrSetImpl &PHIs) { // Look through noop bitcast instructions. @@ -2380,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. @@ -2420,7 +2499,7 @@ static uint64_t GetStringLengthH(Value *V, SmallPtrSetImpl &PHIs) { return StrData.size()+1; } -/// GetStringLength - If we can compute the length of the string pointed to by +/// If we can compute the length of the string pointed to by /// the specified pointer, return 'len+1'. If we can't, return 0. uint64_t llvm::GetStringLength(Value *V) { if (!V->getType()->isPointerTy()) return 0; @@ -2449,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; @@ -2474,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)) { @@ -2493,9 +2572,7 @@ llvm::GetUnderlyingObjects(Value *V, } while (!Worklist.empty()); } -/// onlyUsedByLifetimeMarkers - Return true if the only users of this pointer -/// are lifetime markers. -/// +/// Return true if the only users of this pointer are lifetime markers. bool llvm::onlyUsedByLifetimeMarkers(const Value *V) { for (const User *U : V->users()) { const IntrinsicInst *II = dyn_cast(U); @@ -2523,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); @@ -2550,42 +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: - 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. } @@ -2608,8 +2695,7 @@ bool llvm::isSafeToSpeculativelyExecute(const Value *V, } } -/// isKnownNonNull - Return true if we know that the specified value is never -/// null. +/// Return true if we know that the specified value is never null. bool llvm::isKnownNonNull(const Value *V, const TargetLibraryInfo *TLI) { // Alloca never returns null, malloc might. if (isa(V)) return true; @@ -2636,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; +}