X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FValueTracking.cpp;h=d3cc52d87e0dcbe3f90dd020cde5948a9ac5645e;hb=a098c770e1f96f6f728cc220ae6f4f5297d0603d;hp=e9bbf83fa963142b390b8340ec7741562fd1a213;hpb=5401ba7099b9f3cd32b3399276b549bea15e5d1e;p=oota-llvm.git diff --git a/lib/Analysis/ValueTracking.cpp b/lib/Analysis/ValueTracking.cpp index e9bbf83fa96..d3cc52d87e0 100644 --- a/lib/Analysis/ValueTracking.cpp +++ b/lib/Analysis/ValueTracking.cpp @@ -312,8 +312,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 @@ -491,7 +493,17 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, 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 +511,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 +523,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 +543,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 +556,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 +569,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 +582,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 +598,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 +614,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 +624,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 +634,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 +647,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 +659,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 +670,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 +681,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 +692,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 +703,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 +713,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 +793,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 @@ -849,8 +841,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); @@ -1507,8 +1509,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;