// Use the high end of the ranges to find leading zeros.
unsigned MinLeadingZeros = BitWidth;
for (unsigned i = 0; i < NumRanges; ++i) {
- ConstantInt *Lower = cast<ConstantInt>(Ranges.getOperand(2*i + 0));
- ConstantInt *Upper = cast<ConstantInt>(Ranges.getOperand(2*i + 1));
+ ConstantInt *Lower =
+ mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
+ ConstantInt *Upper =
+ mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
ConstantRange Range(Lower->getValue(), Upper->getValue());
if (Range.isWrappedSet())
MinLeadingZeros = 0; // -1 has no zeros
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.
if (Q.ExclInvs.count(I))
continue;
- if (match(I, m_Intrinsic<Intrinsic::assume>(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<IntrinsicInst>(I) &&
+ dyn_cast<IntrinsicInst>(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();
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)),
CmpInst::Predicate Pred;
ConstantInt *C;
// assume(v = a)
- if (match(I, m_Intrinsic<Intrinsic::assume>(
- 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<Intrinsic::assume>(
- 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));
KnownZero |= RHSKnownZero & MaskKnownOne;
KnownOne |= RHSKnownOne & MaskKnownOne;
// assume(~(v & b) = a)
- } else if (match(I, m_Intrinsic<Intrinsic::assume>(
- 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));
KnownZero |= RHSKnownOne & MaskKnownOne;
KnownOne |= RHSKnownZero & MaskKnownOne;
// assume(v | b = a)
- } else if (match(I, m_Intrinsic<Intrinsic::assume>(
- 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));
KnownZero |= RHSKnownZero & BKnownZero;
KnownOne |= RHSKnownOne & BKnownZero;
// assume(~(v | b) = a)
- } else if (match(I, m_Intrinsic<Intrinsic::assume>(
- 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));
KnownZero |= RHSKnownOne & BKnownZero;
KnownOne |= RHSKnownZero & BKnownZero;
// assume(v ^ b = a)
- } else if (match(I, m_Intrinsic<Intrinsic::assume>(
- 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));
KnownZero |= RHSKnownOne & BKnownOne;
KnownOne |= RHSKnownZero & BKnownOne;
// assume(~(v ^ b) = a)
- } else if (match(I, m_Intrinsic<Intrinsic::assume>(
- 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));
KnownZero |= RHSKnownZero & BKnownOne;
KnownOne |= RHSKnownOne & BKnownOne;
// assume(v << c = a)
- } else if (match(I, m_Intrinsic<Intrinsic::assume>(
- 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));
KnownZero |= RHSKnownZero.lshr(C->getZExtValue());
KnownOne |= RHSKnownOne.lshr(C->getZExtValue());
// assume(~(v << c) = a)
- } else if (match(I, m_Intrinsic<Intrinsic::assume>(
- 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));
KnownZero |= RHSKnownOne.lshr(C->getZExtValue());
KnownOne |= RHSKnownZero.lshr(C->getZExtValue());
// assume(v >> c = a)
- } else if (match(I, m_Intrinsic<Intrinsic::assume>(
- 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));
KnownZero |= RHSKnownZero << C->getZExtValue();
KnownOne |= RHSKnownOne << C->getZExtValue();
// assume(~(v >> c) = a)
- } else if (match(I, m_Intrinsic<Intrinsic::assume>(
- 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));
KnownZero |= RHSKnownOne << C->getZExtValue();
KnownOne |= RHSKnownZero << C->getZExtValue();
// assume(v >=_s c) where c is non-negative
- } else if (match(I, m_Intrinsic<Intrinsic::assume>(
- 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);
KnownZero |= APInt::getSignBit(BitWidth);
}
// assume(v >_s c) where c is at least -1.
- } else if (match(I, m_Intrinsic<Intrinsic::assume>(
- 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);
KnownZero |= APInt::getSignBit(BitWidth);
}
// assume(v <=_s c) where c is negative
- } else if (match(I, m_Intrinsic<Intrinsic::assume>(
- 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);
KnownOne |= APInt::getSignBit(BitWidth);
}
// assume(v <_s c) where c is non-positive
- } else if (match(I, m_Intrinsic<Intrinsic::assume>(
- 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);
KnownOne |= APInt::getSignBit(BitWidth);
}
// assume(v <=_u c)
- } else if (match(I, m_Intrinsic<Intrinsic::assume>(
- 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);
KnownZero |=
APInt::getHighBitsSet(BitWidth, RHSKnownZero.countLeadingOnes());
// assume(v <_u c)
- } else if (match(I, m_Intrinsic<Intrinsic::assume>(
- 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);
return;
}
- // A weak GlobalAlias is totally unknown. A non-weak GlobalAlias has
- // the bits of its aliasee.
- if (GlobalAlias *GA = dyn_cast<GlobalAlias>(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<GlobalValue>(V)) {
- unsigned Align = GV->getAlignment();
+ if (auto *GO = dyn_cast<GlobalObject>(V)) {
+ unsigned Align = GO->getAlignment();
if (Align == 0 && TD) {
- if (GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV)) {
+ if (auto *GVar = dyn_cast<GlobalVariable>(GO)) {
Type *ObjectType = GVar->getType()->getElementType();
if (ObjectType->isSized()) {
// If the object is defined in the current Module, we'll be giving
// 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<GlobalAlias>(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);
const unsigned NumRanges = Ranges->getNumOperands() / 2;
assert(NumRanges >= 1);
for (unsigned i = 0; i < NumRanges; ++i) {
- ConstantInt *Lower = cast<ConstantInt>(Ranges->getOperand(2*i + 0));
- ConstantInt *Upper = cast<ConstantInt>(Ranges->getOperand(2*i + 1));
+ ConstantInt *Lower =
+ mdconst::extract<ConstantInt>(Ranges->getOperand(2 * i + 0));
+ ConstantInt *Upper =
+ mdconst::extract<ConstantInt>(Ranges->getOperand(2 * i + 1));
ConstantRange Range(Lower->getValue(), Upper->getValue());
if (Range.contains(Value))
return false;
// 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<PHINode>(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.
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<SelectInst>(P)) {
projects / oota-llvm.git / blobdiff