const unsigned MaxDepth = 6;
+/// Enable an experimental feature to leverage information about dominating
+/// conditions to compute known bits. The individual options below control how
+/// hard we search. The defaults are choosen to be fairly aggressive. If you
+/// run into compile time problems when testing, scale them back and report
+/// your findings.
+static cl::opt<bool> EnableDomConditions("value-tracking-dom-conditions",
+ cl::Hidden, cl::init(false));
+
+// This is expensive, so we only do it for the top level query value.
+// (TODO: evaluate cost vs profit, consider higher thresholds)
+static cl::opt<unsigned> DomConditionsMaxDepth("dom-conditions-max-depth",
+ cl::Hidden, cl::init(1));
+
+/// How many dominating blocks should be scanned looking for dominating
+/// conditions?
+static cl::opt<unsigned> DomConditionsMaxDomBlocks("dom-conditions-dom-blocks",
+ cl::Hidden,
+ cl::init(20000));
+
+// Controls the number of uses of the value searched for possible
+// dominating comparisons.
+static cl::opt<unsigned> DomConditionsMaxUses("dom-conditions-max-uses",
+ cl::Hidden, cl::init(2000));
+
+// If true, don't consider only compares whose only use is a branch.
+static cl::opt<bool> DomConditionsSingleCmpUse("dom-conditions-single-cmp-use",
+ cl::Hidden, cl::init(false));
+
/// 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) {
+static unsigned getBitWidth(Type *Ty, const DataLayout &DL) {
if (unsigned BitWidth = Ty->getScalarSizeInBits())
return BitWidth;
- return TD ? TD->getPointerTypeSizeInBits(Ty) : 0;
+ return DL.getPointerTypeSizeInBits(Ty);
}
// Many of these functions have internal versions that take an assumption
}
static void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne,
- const DataLayout *TD, unsigned Depth,
- const Query &Q);
+ const DataLayout &DL, unsigned Depth,
+ const Query &Q);
void llvm::computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne,
- const DataLayout *TD, unsigned Depth,
+ const DataLayout &DL, unsigned Depth,
AssumptionCache *AC, const Instruction *CxtI,
const DominatorTree *DT) {
- ::computeKnownBits(V, KnownZero, KnownOne, TD, Depth,
+ ::computeKnownBits(V, KnownZero, KnownOne, DL, Depth,
Query(AC, safeCxtI(V, CxtI), DT));
}
static void ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne,
- const DataLayout *TD, unsigned Depth,
- const Query &Q);
+ const DataLayout &DL, unsigned Depth,
+ const Query &Q);
void llvm::ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne,
- const DataLayout *TD, unsigned Depth,
+ const DataLayout &DL, unsigned Depth,
AssumptionCache *AC, const Instruction *CxtI,
const DominatorTree *DT) {
- ::ComputeSignBit(V, KnownZero, KnownOne, TD, Depth,
+ ::ComputeSignBit(V, KnownZero, KnownOne, DL, Depth,
Query(AC, safeCxtI(V, CxtI), DT));
}
static bool isKnownToBeAPowerOfTwo(Value *V, bool OrZero, unsigned Depth,
- const Query &Q);
+ const Query &Q, const DataLayout &DL);
-bool llvm::isKnownToBeAPowerOfTwo(Value *V, bool OrZero, unsigned Depth,
- AssumptionCache *AC, const Instruction *CxtI,
+bool llvm::isKnownToBeAPowerOfTwo(Value *V, const DataLayout &DL, bool OrZero,
+ unsigned Depth, AssumptionCache *AC,
+ const Instruction *CxtI,
const DominatorTree *DT) {
return ::isKnownToBeAPowerOfTwo(V, OrZero, Depth,
- Query(AC, safeCxtI(V, CxtI), DT));
+ Query(AC, safeCxtI(V, CxtI), DT), DL);
}
-static bool isKnownNonZero(Value *V, const DataLayout *TD, unsigned Depth,
+static bool isKnownNonZero(Value *V, const DataLayout &DL, unsigned Depth,
const Query &Q);
-bool llvm::isKnownNonZero(Value *V, const DataLayout *TD, unsigned Depth,
+bool llvm::isKnownNonZero(Value *V, const DataLayout &DL, unsigned Depth,
AssumptionCache *AC, const Instruction *CxtI,
const DominatorTree *DT) {
- return ::isKnownNonZero(V, TD, Depth, Query(AC, safeCxtI(V, CxtI), DT));
+ return ::isKnownNonZero(V, DL, Depth, Query(AC, safeCxtI(V, CxtI), DT));
}
-static bool MaskedValueIsZero(Value *V, const APInt &Mask,
- const DataLayout *TD, unsigned Depth,
- const Query &Q);
+static bool MaskedValueIsZero(Value *V, const APInt &Mask, const DataLayout &DL,
+ unsigned Depth, const Query &Q);
-bool llvm::MaskedValueIsZero(Value *V, const APInt &Mask, const DataLayout *TD,
+bool llvm::MaskedValueIsZero(Value *V, const APInt &Mask, const DataLayout &DL,
unsigned Depth, AssumptionCache *AC,
const Instruction *CxtI, const DominatorTree *DT) {
- return ::MaskedValueIsZero(V, Mask, TD, Depth,
+ return ::MaskedValueIsZero(V, Mask, DL, Depth,
Query(AC, safeCxtI(V, CxtI), DT));
}
-static unsigned ComputeNumSignBits(Value *V, const DataLayout *TD,
+static unsigned ComputeNumSignBits(Value *V, const DataLayout &DL,
unsigned Depth, const Query &Q);
-unsigned llvm::ComputeNumSignBits(Value *V, const DataLayout *TD,
+unsigned llvm::ComputeNumSignBits(Value *V, const DataLayout &DL,
unsigned Depth, AssumptionCache *AC,
const Instruction *CxtI,
const DominatorTree *DT) {
- return ::ComputeNumSignBits(V, TD, Depth, Query(AC, safeCxtI(V, CxtI), DT));
+ return ::ComputeNumSignBits(V, DL, Depth, Query(AC, safeCxtI(V, CxtI), DT));
}
static void computeKnownBitsAddSub(bool Add, Value *Op0, Value *Op1, bool NSW,
APInt &KnownZero, APInt &KnownOne,
APInt &KnownZero2, APInt &KnownOne2,
- const DataLayout *TD, unsigned Depth,
+ const DataLayout &DL, unsigned Depth,
const Query &Q) {
if (!Add) {
if (ConstantInt *CLHS = dyn_cast<ConstantInt>(Op0)) {
unsigned NLZ = (CLHS->getValue()+1).countLeadingZeros();
// NLZ can't be BitWidth with no sign bit
APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
- computeKnownBits(Op1, KnownZero2, KnownOne2, TD, Depth+1, Q);
+ computeKnownBits(Op1, KnownZero2, KnownOne2, DL, Depth + 1, Q);
// If all of the MaskV bits are known to be zero, then we know the
// output top bits are zero, because we now know that the output is
// If an initial sequence of bits in the result is not needed, the
// corresponding bits in the operands are not needed.
APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0);
- computeKnownBits(Op0, LHSKnownZero, LHSKnownOne, TD, Depth+1, Q);
- computeKnownBits(Op1, KnownZero2, KnownOne2, TD, Depth+1, Q);
+ computeKnownBits(Op0, LHSKnownZero, LHSKnownOne, DL, Depth + 1, Q);
+ computeKnownBits(Op1, KnownZero2, KnownOne2, DL, Depth + 1, Q);
// Carry in a 1 for a subtract, rather than a 0.
APInt CarryIn(BitWidth, 0);
static void computeKnownBitsMul(Value *Op0, Value *Op1, bool NSW,
APInt &KnownZero, APInt &KnownOne,
APInt &KnownZero2, APInt &KnownOne2,
- const DataLayout *TD, unsigned Depth,
+ const DataLayout &DL, unsigned Depth,
const Query &Q) {
unsigned BitWidth = KnownZero.getBitWidth();
- computeKnownBits(Op1, KnownZero, KnownOne, TD, Depth+1, Q);
- computeKnownBits(Op0, KnownZero2, KnownOne2, TD, Depth+1, Q);
+ computeKnownBits(Op1, KnownZero, KnownOne, DL, Depth + 1, Q);
+ computeKnownBits(Op0, KnownZero2, KnownOne2, DL, Depth + 1, Q);
bool isKnownNegative = false;
bool isKnownNonNegative = false;
// negative or zero.
if (!isKnownNonNegative)
isKnownNegative = (isKnownNegativeOp1 && isKnownNonNegativeOp0 &&
- isKnownNonZero(Op0, TD, Depth, Q)) ||
+ isKnownNonZero(Op0, DL, Depth, Q)) ||
(isKnownNegativeOp0 && isKnownNonNegativeOp1 &&
- isKnownNonZero(Op1, TD, Depth, Q));
+ isKnownNonZero(Op1, DL, Depth, Q));
}
}
return false;
}
-static bool isValidAssumeForContext(Value *V, const Query &Q,
- const DataLayout *DL) {
+static bool isValidAssumeForContext(Value *V, const Query &Q) {
Instruction *Inv = cast<Instruction>(V);
// There are two restrictions on the use of an assume:
for (BasicBlock::const_iterator I =
std::next(BasicBlock::const_iterator(Q.CxtI)),
IE(Inv); I != IE; ++I)
- if (!isSafeToSpeculativelyExecute(I, DL) &&
- !isAssumeLikeIntrinsic(I))
+ if (!isSafeToSpeculativelyExecute(I) && !isAssumeLikeIntrinsic(I))
return false;
return !isEphemeralValueOf(Inv, Q.CxtI);
for (BasicBlock::const_iterator I =
std::next(BasicBlock::const_iterator(Q.CxtI)),
IE(Inv); I != IE; ++I)
- if (!isSafeToSpeculativelyExecute(I, DL) &&
- !isAssumeLikeIntrinsic(I))
+ if (!isSafeToSpeculativelyExecute(I) && !isAssumeLikeIntrinsic(I))
return false;
return !isEphemeralValueOf(Inv, Q.CxtI);
bool llvm::isValidAssumeForContext(const Instruction *I,
const Instruction *CxtI,
- const DataLayout *DL,
const DominatorTree *DT) {
- return ::isValidAssumeForContext(const_cast<Instruction*>(I),
- Query(nullptr, CxtI, DT), DL);
+ return ::isValidAssumeForContext(const_cast<Instruction *>(I),
+ Query(nullptr, CxtI, DT));
}
template<typename LHS, typename RHS>
return m_CombineOr(m_Xor(L, R), m_Xor(R, L));
}
+/// Compute known bits in 'V' under the assumption that the condition 'Cmp' is
+/// true (at the context instruction.) This is mostly a utility function for
+/// the prototype dominating conditions reasoning below.
+static void computeKnownBitsFromTrueCondition(Value *V, ICmpInst *Cmp,
+ APInt &KnownZero,
+ APInt &KnownOne,
+ const DataLayout &DL,
+ unsigned Depth, const Query &Q) {
+ Value *LHS = Cmp->getOperand(0);
+ Value *RHS = Cmp->getOperand(1);
+ // TODO: We could potentially be more aggressive here. This would be worth
+ // evaluating. If we can, explore commoning this code with the assume
+ // handling logic.
+ if (LHS != V && RHS != V)
+ return;
+
+ const unsigned BitWidth = KnownZero.getBitWidth();
+
+ switch (Cmp->getPredicate()) {
+ default:
+ // We know nothing from this condition
+ break;
+ // TODO: implement unsigned bound from below (known one bits)
+ // TODO: common condition check implementations with assumes
+ // TODO: implement other patterns from assume (e.g. V & B == A)
+ case ICmpInst::ICMP_SGT:
+ if (LHS == V) {
+ APInt KnownZeroTemp(BitWidth, 0), KnownOneTemp(BitWidth, 0);
+ computeKnownBits(RHS, KnownZeroTemp, KnownOneTemp, DL, Depth + 1, Q);
+ if (KnownOneTemp.isAllOnesValue() || KnownZeroTemp.isNegative()) {
+ // We know that the sign bit is zero.
+ KnownZero |= APInt::getSignBit(BitWidth);
+ }
+ }
+ break;
+ case ICmpInst::ICMP_EQ:
+ if (LHS == V)
+ computeKnownBits(RHS, KnownZero, KnownOne, DL, Depth + 1, Q);
+ else if (RHS == V)
+ computeKnownBits(LHS, KnownZero, KnownOne, DL, Depth + 1, Q);
+ else
+ llvm_unreachable("missing use?");
+ break;
+ case ICmpInst::ICMP_ULE:
+ if (LHS == V) {
+ APInt KnownZeroTemp(BitWidth, 0), KnownOneTemp(BitWidth, 0);
+ computeKnownBits(RHS, KnownZeroTemp, KnownOneTemp, DL, Depth + 1, Q);
+ // The known zero bits carry over
+ unsigned SignBits = KnownZeroTemp.countLeadingOnes();
+ KnownZero |= APInt::getHighBitsSet(BitWidth, SignBits);
+ }
+ break;
+ case ICmpInst::ICMP_ULT:
+ if (LHS == V) {
+ APInt KnownZeroTemp(BitWidth, 0), KnownOneTemp(BitWidth, 0);
+ computeKnownBits(RHS, KnownZeroTemp, KnownOneTemp, DL, Depth + 1, Q);
+ // Whatever high bits in rhs are zero are known to be zero (if rhs is a
+ // power of 2, then one more).
+ unsigned SignBits = KnownZeroTemp.countLeadingOnes();
+ if (isKnownToBeAPowerOfTwo(RHS, false, Depth + 1, Query(Q, Cmp), DL))
+ SignBits++;
+ KnownZero |= APInt::getHighBitsSet(BitWidth, SignBits);
+ }
+ break;
+ };
+}
+
+/// Compute known bits in 'V' from conditions which are known to be true along
+/// all paths leading to the context instruction. In particular, look for
+/// cases where one branch of an interesting condition dominates the context
+/// instruction. This does not do general dataflow.
+/// NOTE: This code is EXPERIMENTAL and currently off by default.
+static void computeKnownBitsFromDominatingCondition(Value *V, APInt &KnownZero,
+ APInt &KnownOne,
+ const DataLayout &DL,
+ unsigned Depth,
+ const Query &Q) {
+ // Need both the dominator tree and the query location to do anything useful
+ if (!Q.DT || !Q.CxtI)
+ return;
+ Instruction *Cxt = const_cast<Instruction *>(Q.CxtI);
+
+ // Avoid useless work
+ if (auto VI = dyn_cast<Instruction>(V))
+ if (VI->getParent() == Cxt->getParent())
+ return;
+
+ // Note: We currently implement two options. It's not clear which of these
+ // will survive long term, we need data for that.
+ // Option 1 - Try walking the dominator tree looking for conditions which
+ // might apply. This works well for local conditions (loop guards, etc..),
+ // but not as well for things far from the context instruction (presuming a
+ // low max blocks explored). If we can set an high enough limit, this would
+ // be all we need.
+ // Option 2 - We restrict out search to those conditions which are uses of
+ // the value we're interested in. This is independent of dom structure,
+ // but is slightly less powerful without looking through lots of use chains.
+ // It does handle conditions far from the context instruction (e.g. early
+ // function exits on entry) really well though.
+
+ // Option 1 - Search the dom tree
+ unsigned NumBlocksExplored = 0;
+ BasicBlock *Current = Cxt->getParent();
+ while (true) {
+ // Stop searching if we've gone too far up the chain
+ if (NumBlocksExplored >= DomConditionsMaxDomBlocks)
+ break;
+ NumBlocksExplored++;
+
+ if (!Q.DT->getNode(Current)->getIDom())
+ break;
+ Current = Q.DT->getNode(Current)->getIDom()->getBlock();
+ if (!Current)
+ // found function entry
+ break;
+
+ BranchInst *BI = dyn_cast<BranchInst>(Current->getTerminator());
+ if (!BI || BI->isUnconditional())
+ continue;
+ ICmpInst *Cmp = dyn_cast<ICmpInst>(BI->getCondition());
+ if (!Cmp)
+ continue;
+
+ // We're looking for conditions that are guaranteed to hold at the context
+ // instruction. Finding a condition where one path dominates the context
+ // isn't enough because both the true and false cases could merge before
+ // the context instruction we're actually interested in. Instead, we need
+ // to ensure that the taken *edge* dominates the context instruction.
+ BasicBlock *BB0 = BI->getSuccessor(0);
+ BasicBlockEdge Edge(BI->getParent(), BB0);
+ if (!Edge.isSingleEdge() || !Q.DT->dominates(Edge, Q.CxtI->getParent()))
+ continue;
+
+ computeKnownBitsFromTrueCondition(V, Cmp, KnownZero, KnownOne, DL, Depth,
+ Q);
+ }
+
+ // Option 2 - Search the other uses of V
+ unsigned NumUsesExplored = 0;
+ for (auto U : V->users()) {
+ // Avoid massive lists
+ if (NumUsesExplored >= DomConditionsMaxUses)
+ break;
+ NumUsesExplored++;
+ // Consider only compare instructions uniquely controlling a branch
+ ICmpInst *Cmp = dyn_cast<ICmpInst>(U);
+ if (!Cmp)
+ continue;
+
+ if (DomConditionsSingleCmpUse && !Cmp->hasOneUse())
+ continue;
+
+ for (auto *CmpU : Cmp->users()) {
+ BranchInst *BI = dyn_cast<BranchInst>(CmpU);
+ if (!BI || BI->isUnconditional())
+ continue;
+ // We're looking for conditions that are guaranteed to hold at the
+ // context instruction. Finding a condition where one path dominates
+ // the context isn't enough because both the true and false cases could
+ // merge before the context instruction we're actually interested in.
+ // Instead, we need to ensure that the taken *edge* dominates the context
+ // instruction.
+ BasicBlock *BB0 = BI->getSuccessor(0);
+ BasicBlockEdge Edge(BI->getParent(), BB0);
+ if (!Edge.isSingleEdge() || !Q.DT->dominates(Edge, Q.CxtI->getParent()))
+ continue;
+
+ computeKnownBitsFromTrueCondition(V, Cmp, KnownZero, KnownOne, DL, Depth,
+ Q);
+ }
+ }
+}
+
static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero,
- APInt &KnownOne,
- const DataLayout *DL,
+ APInt &KnownOne, const DataLayout &DL,
unsigned Depth, const Query &Q) {
// Use of assumptions is context-sensitive. If we don't have a context, we
// cannot use them!
Value *Arg = I->getArgOperand(0);
- if (Arg == V &&
- isValidAssumeForContext(I, Q, DL)) {
+ if (Arg == V && isValidAssumeForContext(I, Q)) {
assert(BitWidth == 1 && "assume operand is not i1?");
KnownZero.clearAllBits();
KnownOne.setAllBits();
ConstantInt *C;
// assume(v = a)
if (match(Arg, m_c_ICmp(Pred, m_V, m_Value(A))) &&
- Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q, DL)) {
+ Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q)) {
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(Arg, m_c_ICmp(Pred, m_c_And(m_V, m_Value(B)),
- m_Value(A))) &&
- Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q, DL)) {
+ } 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)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
APInt MaskKnownZero(BitWidth, 0), MaskKnownOne(BitWidth, 0);
// assume(~(v & b) = 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)) {
+ Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
APInt MaskKnownZero(BitWidth, 0), MaskKnownOne(BitWidth, 0);
KnownZero |= RHSKnownOne & MaskKnownOne;
KnownOne |= RHSKnownZero & MaskKnownOne;
// assume(v | b = 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)) {
+ } 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)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
APInt BKnownZero(BitWidth, 0), BKnownOne(BitWidth, 0);
// assume(~(v | b) = 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)) {
+ Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
APInt BKnownZero(BitWidth, 0), BKnownOne(BitWidth, 0);
KnownZero |= RHSKnownOne & BKnownZero;
KnownOne |= RHSKnownZero & BKnownZero;
// assume(v ^ b = 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)) {
+ } 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)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
APInt BKnownZero(BitWidth, 0), BKnownOne(BitWidth, 0);
// assume(~(v ^ b) = 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)) {
+ Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
APInt BKnownZero(BitWidth, 0), BKnownOne(BitWidth, 0);
// assume(v << c = 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)) {
+ Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
// For those bits in RHS that are known, we can propagate them to known
// assume(~(v << c) = 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)) {
+ Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
// For those bits in RHS that are known, we can propagate them inverted
// assume(v >> c = a)
} 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))) &&
- Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q, DL)) {
+ m_AShr(m_V, m_ConstantInt(C))),
+ m_Value(A))) &&
+ Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
// For those bits in RHS that are known, we can propagate them to known
KnownOne |= RHSKnownOne << C->getZExtValue();
// assume(~(v >> c) = a)
} 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_LShr(m_V, m_ConstantInt(C)),
+ m_AShr(m_V, m_ConstantInt(C)))),
m_Value(A))) &&
- Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q, DL)) {
+ Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
// For those bits in RHS that are known, we can propagate them inverted
KnownOne |= RHSKnownZero << C->getZExtValue();
// assume(v >=_s c) where c is non-negative
} else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
- Pred == ICmpInst::ICMP_SGE &&
- isValidAssumeForContext(I, Q, DL)) {
+ Pred == ICmpInst::ICMP_SGE && isValidAssumeForContext(I, Q)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
}
// assume(v >_s c) where c is at least -1.
} else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
- Pred == ICmpInst::ICMP_SGT &&
- isValidAssumeForContext(I, Q, DL)) {
+ Pred == ICmpInst::ICMP_SGT && isValidAssumeForContext(I, Q)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
}
// assume(v <=_s c) where c is negative
} else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
- Pred == ICmpInst::ICMP_SLE &&
- isValidAssumeForContext(I, Q, DL)) {
+ Pred == ICmpInst::ICMP_SLE && isValidAssumeForContext(I, Q)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
}
// assume(v <_s c) where c is non-positive
} else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
- Pred == ICmpInst::ICMP_SLT &&
- isValidAssumeForContext(I, Q, DL)) {
+ Pred == ICmpInst::ICMP_SLT && isValidAssumeForContext(I, Q)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
}
// assume(v <=_u c)
} else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
- Pred == ICmpInst::ICMP_ULE &&
- isValidAssumeForContext(I, Q, DL)) {
+ Pred == ICmpInst::ICMP_ULE && isValidAssumeForContext(I, Q)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
APInt::getHighBitsSet(BitWidth, RHSKnownZero.countLeadingOnes());
// assume(v <_u c)
} else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
- Pred == ICmpInst::ICMP_ULT &&
- isValidAssumeForContext(I, Q, DL)) {
+ Pred == ICmpInst::ICMP_ULT && isValidAssumeForContext(I, Q)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
// Whatever high bits in c are zero are known to be zero (if c is a power
// of 2, then one more).
- if (isKnownToBeAPowerOfTwo(A, false, Depth+1, Query(Q, I)))
+ if (isKnownToBeAPowerOfTwo(A, false, Depth + 1, Query(Q, I), DL))
KnownZero |=
APInt::getHighBitsSet(BitWidth, RHSKnownZero.countLeadingOnes()+1);
else
/// this won't lose us code quality.
///
/// 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
+/// type, and vectors of integers. In the case
/// where V is a vector, known zero, and known one values are the
/// same width as the vector element, and the bit is set only if it is true
/// for all of the elements in the vector.
void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne,
- const DataLayout *TD, unsigned Depth,
- const Query &Q) {
+ const DataLayout &DL, unsigned Depth, const Query &Q) {
assert(V && "No Value?");
assert(Depth <= MaxDepth && "Limit Search Depth");
unsigned BitWidth = KnownZero.getBitWidth();
assert((V->getType()->isIntOrIntVectorTy() ||
V->getType()->getScalarType()->isPointerTy()) &&
"Not integer or pointer type!");
- assert((!TD ||
- TD->getTypeSizeInBits(V->getType()->getScalarType()) == BitWidth) &&
+ assert((DL.getTypeSizeInBits(V->getType()->getScalarType()) == BitWidth) &&
(!V->getType()->isIntOrIntVectorTy() ||
V->getType()->getScalarSizeInBits() == BitWidth) &&
KnownZero.getBitWidth() == BitWidth &&
// The address of an aligned GlobalValue has trailing zeros.
if (auto *GO = dyn_cast<GlobalObject>(V)) {
unsigned Align = GO->getAlignment();
- if (Align == 0 && TD) {
+ if (Align == 0) {
if (auto *GVar = dyn_cast<GlobalVariable>(GO)) {
Type *ObjectType = GVar->getType()->getElementType();
if (ObjectType->isSized()) {
// it the preferred alignment. Otherwise, we have to assume that it
// may only have the minimum ABI alignment.
if (!GVar->isDeclaration() && !GVar->isWeakForLinker())
- Align = TD->getPreferredAlignment(GVar);
+ Align = DL.getPreferredAlignment(GVar);
else
- Align = TD->getABITypeAlignment(ObjectType);
+ Align = DL.getABITypeAlignment(ObjectType);
}
}
}
if (Argument *A = dyn_cast<Argument>(V)) {
unsigned Align = A->getType()->isPointerTy() ? A->getParamAlignment() : 0;
- if (!Align && TD && A->hasStructRetAttr()) {
+ if (!Align && A->hasStructRetAttr()) {
// An sret parameter has at least the ABI alignment of the return type.
Type *EltTy = cast<PointerType>(A->getType())->getElementType();
if (EltTy->isSized())
- Align = TD->getABITypeAlignment(EltTy);
+ Align = DL.getABITypeAlignment(EltTy);
}
if (Align)
// Don't give up yet... there might be an assumption that provides more
// information...
- computeKnownBitsFromAssume(V, KnownZero, KnownOne, TD, Depth, Q);
+ computeKnownBitsFromAssume(V, KnownZero, KnownOne, DL, Depth, Q);
+
+ // Or a dominating condition for that matter
+ if (EnableDomConditions && Depth <= DomConditionsMaxDepth)
+ computeKnownBitsFromDominatingCondition(V, KnownZero, KnownOne, DL,
+ Depth, Q);
return;
}
// the bits of its aliasee.
if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
if (!GA->mayBeOverridden())
- computeKnownBits(GA->getAliasee(), KnownZero, KnownOne, TD, Depth + 1, Q);
+ computeKnownBits(GA->getAliasee(), KnownZero, KnownOne, DL, Depth + 1, Q);
return;
}
// Check whether a nearby assume intrinsic can determine some known bits.
- computeKnownBitsFromAssume(V, KnownZero, KnownOne, TD, Depth, Q);
+ computeKnownBitsFromAssume(V, KnownZero, KnownOne, DL, Depth, Q);
+
+ // Check whether there's a dominating condition which implies something about
+ // this value at the given context.
+ if (EnableDomConditions && Depth <= DomConditionsMaxDepth)
+ computeKnownBitsFromDominatingCondition(V, KnownZero, KnownOne, DL, Depth,
+ Q);
Operator *I = dyn_cast<Operator>(V);
if (!I) return;
break;
case Instruction::And: {
// If either the LHS or the RHS are Zero, the result is zero.
- computeKnownBits(I->getOperand(1), KnownZero, KnownOne, TD, Depth+1, Q);
- computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1, Q);
+ computeKnownBits(I->getOperand(1), KnownZero, KnownOne, DL, Depth + 1, Q);
+ computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, DL, Depth + 1, Q);
// Output known-1 bits are only known if set in both the LHS & RHS.
KnownOne &= KnownOne2;
break;
}
case Instruction::Or: {
- computeKnownBits(I->getOperand(1), KnownZero, KnownOne, TD, Depth+1, Q);
- computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1, Q);
+ computeKnownBits(I->getOperand(1), KnownZero, KnownOne, DL, Depth + 1, Q);
+ computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, DL, Depth + 1, Q);
// Output known-0 bits are only known if clear in both the LHS & RHS.
KnownZero &= KnownZero2;
break;
}
case Instruction::Xor: {
- computeKnownBits(I->getOperand(1), KnownZero, KnownOne, TD, Depth+1, Q);
- computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1, Q);
+ computeKnownBits(I->getOperand(1), KnownZero, KnownOne, DL, Depth + 1, Q);
+ computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, DL, Depth + 1, Q);
// Output known-0 bits are known if clear or set in both the LHS & RHS.
APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
}
case Instruction::Mul: {
bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap();
- computeKnownBitsMul(I->getOperand(0), I->getOperand(1), NSW,
- KnownZero, KnownOne, KnownZero2, KnownOne2, TD,
- Depth, Q);
+ computeKnownBitsMul(I->getOperand(0), I->getOperand(1), NSW, KnownZero,
+ KnownOne, KnownZero2, KnownOne2, DL, Depth, Q);
break;
}
case Instruction::UDiv: {
// For the purposes of computing leading zeros we can conservatively
// treat a udiv as a logical right shift by the power of 2 known to
// be less than the denominator.
- computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1, Q);
+ computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, DL, Depth + 1, Q);
unsigned LeadZ = KnownZero2.countLeadingOnes();
KnownOne2.clearAllBits();
KnownZero2.clearAllBits();
- computeKnownBits(I->getOperand(1), KnownZero2, KnownOne2, TD, Depth+1, Q);
+ computeKnownBits(I->getOperand(1), KnownZero2, KnownOne2, DL, Depth + 1, Q);
unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
if (RHSUnknownLeadingOnes != BitWidth)
LeadZ = std::min(BitWidth,
break;
}
case Instruction::Select:
- computeKnownBits(I->getOperand(2), KnownZero, KnownOne, TD, Depth+1, Q);
- computeKnownBits(I->getOperand(1), KnownZero2, KnownOne2, TD, Depth+1, Q);
+ computeKnownBits(I->getOperand(2), KnownZero, KnownOne, DL, Depth + 1, Q);
+ computeKnownBits(I->getOperand(1), KnownZero2, KnownOne2, DL, Depth + 1, Q);
// Only known if known in both the LHS and RHS.
KnownOne &= KnownOne2;
case Instruction::PtrToInt:
case Instruction::IntToPtr:
case Instruction::AddrSpaceCast: // Pointers could be different sizes.
- // We can't handle these if we don't know the pointer size.
- if (!TD) break;
// FALL THROUGH and handle them the same as zext/trunc.
case Instruction::ZExt:
case Instruction::Trunc: {
unsigned SrcBitWidth;
// Note that we handle pointer operands here because of inttoptr/ptrtoint
// which fall through here.
- if(TD) {
- SrcBitWidth = TD->getTypeSizeInBits(SrcTy->getScalarType());
- } else {
- SrcBitWidth = SrcTy->getScalarSizeInBits();
- if (!SrcBitWidth) break;
- }
+ SrcBitWidth = DL.getTypeSizeInBits(SrcTy->getScalarType());
assert(SrcBitWidth && "SrcBitWidth can't be zero");
KnownZero = KnownZero.zextOrTrunc(SrcBitWidth);
KnownOne = KnownOne.zextOrTrunc(SrcBitWidth);
- computeKnownBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1, Q);
+ computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1, Q);
KnownZero = KnownZero.zextOrTrunc(BitWidth);
KnownOne = KnownOne.zextOrTrunc(BitWidth);
// Any top bits are known to be zero.
// TODO: For now, not handling conversions like:
// (bitcast i64 %x to <2 x i32>)
!I->getType()->isVectorTy()) {
- computeKnownBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1, Q);
+ computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1, Q);
break;
}
break;
KnownZero = KnownZero.trunc(SrcBitWidth);
KnownOne = KnownOne.trunc(SrcBitWidth);
- computeKnownBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1, Q);
+ computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1, Q);
KnownZero = KnownZero.zext(BitWidth);
KnownOne = KnownOne.zext(BitWidth);
// (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) {
uint64_t ShiftAmt = SA->getLimitedValue(BitWidth);
- computeKnownBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1, Q);
+ computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1, Q);
KnownZero <<= ShiftAmt;
KnownOne <<= ShiftAmt;
KnownZero |= APInt::getLowBitsSet(BitWidth, ShiftAmt); // low bits known 0
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, DL, Depth + 1, Q);
KnownZero = APIntOps::lshr(KnownZero, ShiftAmt);
KnownOne = APIntOps::lshr(KnownOne, ShiftAmt);
// high bits known zero.
uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1);
// Signed shift right.
- computeKnownBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1, Q);
+ computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1, Q);
KnownZero = APIntOps::lshr(KnownZero, ShiftAmt);
KnownOne = APIntOps::lshr(KnownOne, ShiftAmt);
case Instruction::Sub: {
bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap();
computeKnownBitsAddSub(false, I->getOperand(0), I->getOperand(1), NSW,
- KnownZero, KnownOne, KnownZero2, KnownOne2, TD,
- Depth, Q);
+ KnownZero, KnownOne, KnownZero2, KnownOne2, DL,
+ Depth, Q);
break;
}
case Instruction::Add: {
bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap();
computeKnownBitsAddSub(true, I->getOperand(0), I->getOperand(1), NSW,
- KnownZero, KnownOne, KnownZero2, KnownOne2, TD,
- Depth, Q);
+ KnownZero, KnownOne, KnownZero2, KnownOne2, DL,
+ Depth, Q);
break;
}
case Instruction::SRem:
APInt RA = Rem->getValue().abs();
if (RA.isPowerOf2()) {
APInt LowBits = RA - 1;
- computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, TD,
- Depth+1, Q);
+ computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, DL, Depth + 1,
+ Q);
// The low bits of the first operand are unchanged by the srem.
KnownZero = KnownZero2 & LowBits;
// remainder is zero.
if (KnownZero.isNonNegative()) {
APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0);
- computeKnownBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, TD,
- Depth+1, Q);
+ computeKnownBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, DL,
+ Depth + 1, Q);
// If it's known zero, our sign bit is also zero.
if (LHSKnownZero.isNegative())
KnownZero.setBit(BitWidth - 1);
APInt RA = Rem->getValue();
if (RA.isPowerOf2()) {
APInt LowBits = (RA - 1);
- computeKnownBits(I->getOperand(0), KnownZero, KnownOne, TD,
- Depth+1, Q);
+ computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1,
+ Q);
KnownZero |= ~LowBits;
KnownOne &= LowBits;
break;
// Since the result is less than or equal to either operand, any leading
// zero bits in either operand must also exist in the result.
- computeKnownBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1, Q);
- computeKnownBits(I->getOperand(1), KnownZero2, KnownOne2, TD, Depth+1, Q);
+ computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1, Q);
+ computeKnownBits(I->getOperand(1), KnownZero2, KnownOne2, DL, Depth + 1, Q);
unsigned Leaders = std::max(KnownZero.countLeadingOnes(),
KnownZero2.countLeadingOnes());
case Instruction::Alloca: {
AllocaInst *AI = cast<AllocaInst>(V);
unsigned Align = AI->getAlignment();
- if (Align == 0 && TD)
- Align = TD->getABITypeAlignment(AI->getType()->getElementType());
+ if (Align == 0)
+ Align = DL.getABITypeAlignment(AI->getType()->getElementType());
if (Align > 0)
KnownZero = APInt::getLowBitsSet(BitWidth, countTrailingZeros(Align));
// Analyze all of the subscripts of this getelementptr instruction
// to determine if we can prove known low zero bits.
APInt LocalKnownZero(BitWidth, 0), LocalKnownOne(BitWidth, 0);
- computeKnownBits(I->getOperand(0), LocalKnownZero, LocalKnownOne, TD,
- Depth+1, Q);
+ computeKnownBits(I->getOperand(0), LocalKnownZero, LocalKnownOne, DL,
+ Depth + 1, Q);
unsigned TrailZ = LocalKnownZero.countTrailingOnes();
gep_type_iterator GTI = gep_type_begin(I);
Value *Index = I->getOperand(i);
if (StructType *STy = dyn_cast<StructType>(*GTI)) {
// Handle struct member offset arithmetic.
- if (!TD) {
- TrailZ = 0;
- break;
- }
// Handle case when index is vector zeroinitializer
Constant *CIndex = cast<Constant>(Index);
Index = CIndex->getSplatValue();
unsigned Idx = cast<ConstantInt>(Index)->getZExtValue();
- const StructLayout *SL = TD->getStructLayout(STy);
+ const StructLayout *SL = DL.getStructLayout(STy);
uint64_t Offset = SL->getElementOffset(Idx);
TrailZ = std::min<unsigned>(TrailZ,
countTrailingZeros(Offset));
break;
}
unsigned GEPOpiBits = Index->getType()->getScalarSizeInBits();
- uint64_t TypeSize = TD ? TD->getTypeAllocSize(IndexedTy) : 1;
+ uint64_t TypeSize = DL.getTypeAllocSize(IndexedTy);
LocalKnownZero = LocalKnownOne = APInt(GEPOpiBits, 0);
- computeKnownBits(Index, LocalKnownZero, LocalKnownOne, TD, Depth+1, Q);
+ computeKnownBits(Index, LocalKnownZero, LocalKnownOne, DL, Depth + 1,
+ Q);
TrailZ = std::min(TrailZ,
unsigned(countTrailingZeros(TypeSize) +
LocalKnownZero.countTrailingOnes()));
break;
// Ok, we have a PHI of the form L op= R. Check for low
// zero bits.
- computeKnownBits(R, KnownZero2, KnownOne2, TD, Depth+1, Q);
+ computeKnownBits(R, KnownZero2, KnownOne2, DL, Depth + 1, Q);
// We need to take the minimum number of known bits
APInt KnownZero3(KnownZero), KnownOne3(KnownOne);
- computeKnownBits(L, KnownZero3, KnownOne3, TD, Depth+1, Q);
+ computeKnownBits(L, KnownZero3, KnownOne3, DL, Depth + 1, Q);
KnownZero = APInt::getLowBitsSet(BitWidth,
std::min(KnownZero2.countTrailingOnes(),
KnownOne2 = APInt(BitWidth, 0);
// Recurse, but cap the recursion to one level, because we don't
// want to waste time spinning around in loops.
- computeKnownBits(P->getIncomingValue(i), KnownZero2, KnownOne2, TD,
- MaxDepth-1, Q);
+ computeKnownBits(P->getIncomingValue(i), KnownZero2, KnownOne2, DL,
+ MaxDepth - 1, Q);
KnownZero &= KnownZero2;
KnownOne &= KnownOne2;
// If all bits have been ruled out, there's no need to check
case Intrinsic::sadd_with_overflow:
computeKnownBitsAddSub(true, II->getArgOperand(0),
II->getArgOperand(1), false, KnownZero,
- KnownOne, KnownZero2, KnownOne2, TD, Depth, Q);
+ KnownOne, KnownZero2, KnownOne2, DL, Depth, Q);
break;
case Intrinsic::usub_with_overflow:
case Intrinsic::ssub_with_overflow:
computeKnownBitsAddSub(false, II->getArgOperand(0),
II->getArgOperand(1), false, KnownZero,
- KnownOne, KnownZero2, KnownOne2, TD, Depth, Q);
+ KnownOne, KnownZero2, KnownOne2, DL, Depth, Q);
break;
case Intrinsic::umul_with_overflow:
case Intrinsic::smul_with_overflow:
- computeKnownBitsMul(II->getArgOperand(0), II->getArgOperand(1),
- false, KnownZero, KnownOne,
- KnownZero2, KnownOne2, TD, Depth, Q);
+ computeKnownBitsMul(II->getArgOperand(0), II->getArgOperand(1), false,
+ KnownZero, KnownOne, KnownZero2, KnownOne2, DL,
+ Depth, Q);
break;
}
}
/// 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) {
- unsigned BitWidth = getBitWidth(V->getType(), TD);
+ const DataLayout &DL, unsigned Depth, const Query &Q) {
+ unsigned BitWidth = getBitWidth(V->getType(), DL);
if (!BitWidth) {
KnownZero = false;
KnownOne = false;
}
APInt ZeroBits(BitWidth, 0);
APInt OneBits(BitWidth, 0);
- computeKnownBits(V, ZeroBits, OneBits, TD, Depth, Q);
+ computeKnownBits(V, ZeroBits, OneBits, DL, Depth, Q);
KnownOne = OneBits[BitWidth - 1];
KnownZero = ZeroBits[BitWidth - 1];
}
/// 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) {
+ const Query &Q, const DataLayout &DL) {
if (Constant *C = dyn_cast<Constant>(V)) {
if (C->isNullValue())
return OrZero;
// A shift of a power of two is a power of two or zero.
if (OrZero && (match(V, m_Shl(m_Value(X), m_Value())) ||
match(V, m_Shr(m_Value(X), m_Value()))))
- return isKnownToBeAPowerOfTwo(X, /*OrZero*/true, Depth, Q);
+ return isKnownToBeAPowerOfTwo(X, /*OrZero*/ true, Depth, Q, DL);
if (ZExtInst *ZI = dyn_cast<ZExtInst>(V))
- return isKnownToBeAPowerOfTwo(ZI->getOperand(0), OrZero, Depth, Q);
+ return isKnownToBeAPowerOfTwo(ZI->getOperand(0), OrZero, Depth, Q, DL);
if (SelectInst *SI = dyn_cast<SelectInst>(V))
- return
- isKnownToBeAPowerOfTwo(SI->getTrueValue(), OrZero, Depth, Q) &&
- isKnownToBeAPowerOfTwo(SI->getFalseValue(), OrZero, Depth, Q);
+ return isKnownToBeAPowerOfTwo(SI->getTrueValue(), OrZero, Depth, Q, DL) &&
+ isKnownToBeAPowerOfTwo(SI->getFalseValue(), OrZero, Depth, Q, DL);
if (OrZero && match(V, m_And(m_Value(X), m_Value(Y)))) {
// A power of two and'd with anything is a power of two or zero.
- if (isKnownToBeAPowerOfTwo(X, /*OrZero*/true, Depth, Q) ||
- isKnownToBeAPowerOfTwo(Y, /*OrZero*/true, Depth, Q))
+ if (isKnownToBeAPowerOfTwo(X, /*OrZero*/ true, Depth, Q, DL) ||
+ isKnownToBeAPowerOfTwo(Y, /*OrZero*/ true, Depth, Q, DL))
return true;
// X & (-X) is always a power of two or zero.
if (match(X, m_Neg(m_Specific(Y))) || match(Y, m_Neg(m_Specific(X))))
if (OrZero || VOBO->hasNoUnsignedWrap() || VOBO->hasNoSignedWrap()) {
if (match(X, m_And(m_Specific(Y), m_Value())) ||
match(X, m_And(m_Value(), m_Specific(Y))))
- if (isKnownToBeAPowerOfTwo(Y, OrZero, Depth, Q))
+ if (isKnownToBeAPowerOfTwo(Y, OrZero, Depth, Q, DL))
return true;
if (match(Y, m_And(m_Specific(X), m_Value())) ||
match(Y, m_And(m_Value(), m_Specific(X))))
- if (isKnownToBeAPowerOfTwo(X, OrZero, Depth, Q))
+ if (isKnownToBeAPowerOfTwo(X, OrZero, Depth, Q, DL))
return true;
unsigned BitWidth = V->getType()->getScalarSizeInBits();
APInt LHSZeroBits(BitWidth, 0), LHSOneBits(BitWidth, 0);
- computeKnownBits(X, LHSZeroBits, LHSOneBits, nullptr, Depth, Q);
+ computeKnownBits(X, LHSZeroBits, LHSOneBits, DL, Depth, Q);
APInt RHSZeroBits(BitWidth, 0), RHSOneBits(BitWidth, 0);
- computeKnownBits(Y, RHSZeroBits, RHSOneBits, nullptr, Depth, Q);
+ computeKnownBits(Y, RHSZeroBits, RHSOneBits, DL, Depth, Q);
// If i8 V is a power of two or zero:
// ZeroBits: 1 1 1 0 1 1 1 1
// ~ZeroBits: 0 0 0 1 0 0 0 0
if (match(V, m_Exact(m_LShr(m_Value(), m_Value()))) ||
match(V, m_Exact(m_UDiv(m_Value(), m_Value())))) {
return isKnownToBeAPowerOfTwo(cast<Operator>(V)->getOperand(0), OrZero,
- Depth, Q);
+ Depth, Q, DL);
}
return false;
/// to be non-null.
///
/// Currently this routine does not support vector GEPs.
-static bool isGEPKnownNonNull(GEPOperator *GEP, const DataLayout *DL,
+static bool isGEPKnownNonNull(GEPOperator *GEP, const DataLayout &DL,
unsigned Depth, const Query &Q) {
if (!GEP->isInBounds() || GEP->getPointerAddressSpace() != 0)
return false;
if (isKnownNonZero(GEP->getPointerOperand(), DL, Depth, Q))
return true;
- // Past this, if we don't have DataLayout, we can't do much.
- if (!DL)
- return false;
-
// Walk the GEP operands and see if any operand introduces a non-zero offset.
// If so, then the GEP cannot produce a null pointer, as doing so would
// inherently violate the inbounds contract within address space zero.
if (StructType *STy = dyn_cast<StructType>(*GTI)) {
ConstantInt *OpC = cast<ConstantInt>(GTI.getOperand());
unsigned ElementIdx = OpC->getZExtValue();
- const StructLayout *SL = DL->getStructLayout(STy);
+ const StructLayout *SL = DL.getStructLayout(STy);
uint64_t ElementOffset = SL->getElementOffset(ElementIdx);
if (ElementOffset > 0)
return true;
}
// If we have a zero-sized type, the index doesn't matter. Keep looping.
- if (DL->getTypeAllocSize(GTI.getIndexedType()) == 0)
+ if (DL.getTypeAllocSize(GTI.getIndexedType()) == 0)
continue;
// Fast path the constant operand case both for efficiency and so we don't
/// 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,
+bool isKnownNonZero(Value *V, const DataLayout &DL, unsigned Depth,
const Query &Q) {
if (Constant *C = dyn_cast<Constant>(V)) {
if (C->isNullValue())
if (isKnownNonNull(V))
return true;
if (GEPOperator *GEP = dyn_cast<GEPOperator>(V))
- if (isGEPKnownNonNull(GEP, TD, Depth, Q))
+ if (isGEPKnownNonNull(GEP, DL, Depth, Q))
return true;
}
- unsigned BitWidth = getBitWidth(V->getType()->getScalarType(), TD);
+ unsigned BitWidth = getBitWidth(V->getType()->getScalarType(), DL);
// X | Y != 0 if X != 0 or Y != 0.
Value *X = nullptr, *Y = nullptr;
if (match(V, m_Or(m_Value(X), m_Value(Y))))
- return isKnownNonZero(X, TD, Depth, Q) ||
- isKnownNonZero(Y, TD, Depth, Q);
+ return isKnownNonZero(X, DL, Depth, Q) || isKnownNonZero(Y, DL, Depth, Q);
// ext X != 0 if X != 0.
if (isa<SExtInst>(V) || isa<ZExtInst>(V))
- return isKnownNonZero(cast<Instruction>(V)->getOperand(0), TD, Depth, Q);
+ return isKnownNonZero(cast<Instruction>(V)->getOperand(0), DL, Depth, Q);
// shl X, Y != 0 if X is odd. Note that the value of the shift is undefined
// if the lowest bit is shifted off the end.
// shl nuw can't remove any non-zero bits.
OverflowingBinaryOperator *BO = cast<OverflowingBinaryOperator>(V);
if (BO->hasNoUnsignedWrap())
- return isKnownNonZero(X, TD, Depth, Q);
+ return isKnownNonZero(X, DL, Depth, Q);
APInt KnownZero(BitWidth, 0);
APInt KnownOne(BitWidth, 0);
- computeKnownBits(X, KnownZero, KnownOne, TD, Depth, Q);
+ computeKnownBits(X, KnownZero, KnownOne, DL, Depth, Q);
if (KnownOne[0])
return true;
}
// shr exact can only shift out zero bits.
PossiblyExactOperator *BO = cast<PossiblyExactOperator>(V);
if (BO->isExact())
- return isKnownNonZero(X, TD, Depth, Q);
+ return isKnownNonZero(X, DL, Depth, Q);
bool XKnownNonNegative, XKnownNegative;
- ComputeSignBit(X, XKnownNonNegative, XKnownNegative, TD, Depth, Q);
+ ComputeSignBit(X, XKnownNonNegative, XKnownNegative, DL, Depth, Q);
if (XKnownNegative)
return true;
}
// div exact can only produce a zero if the dividend is zero.
else if (match(V, m_Exact(m_IDiv(m_Value(X), m_Value())))) {
- return isKnownNonZero(X, TD, Depth, Q);
+ return isKnownNonZero(X, DL, Depth, Q);
}
// X + Y.
else if (match(V, m_Add(m_Value(X), m_Value(Y)))) {
bool XKnownNonNegative, XKnownNegative;
bool YKnownNonNegative, YKnownNegative;
- ComputeSignBit(X, XKnownNonNegative, XKnownNegative, TD, Depth, Q);
- ComputeSignBit(Y, YKnownNonNegative, YKnownNegative, TD, Depth, Q);
+ ComputeSignBit(X, XKnownNonNegative, XKnownNegative, DL, Depth, Q);
+ ComputeSignBit(Y, YKnownNonNegative, YKnownNegative, DL, Depth, Q);
// If X and Y are both non-negative (as signed values) then their sum is not
// zero unless both X and Y are zero.
if (XKnownNonNegative && YKnownNonNegative)
- if (isKnownNonZero(X, TD, Depth, Q) ||
- isKnownNonZero(Y, TD, Depth, Q))
+ if (isKnownNonZero(X, DL, Depth, Q) || isKnownNonZero(Y, DL, Depth, Q))
return true;
// If X and Y are both negative (as signed values) then their sum is not
APInt Mask = APInt::getSignedMaxValue(BitWidth);
// The sign bit of X is set. If some other bit is set then X is not equal
// to INT_MIN.
- computeKnownBits(X, KnownZero, KnownOne, TD, Depth, Q);
+ computeKnownBits(X, KnownZero, KnownOne, DL, Depth, Q);
if ((KnownOne & Mask) != 0)
return true;
// The sign bit of Y is set. If some other bit is set then Y is not equal
// to INT_MIN.
- computeKnownBits(Y, KnownZero, KnownOne, TD, Depth, Q);
+ computeKnownBits(Y, KnownZero, KnownOne, DL, Depth, Q);
if ((KnownOne & Mask) != 0)
return true;
}
// The sum of a non-negative number and a power of two is not zero.
if (XKnownNonNegative &&
- isKnownToBeAPowerOfTwo(Y, /*OrZero*/false, Depth, Q))
+ isKnownToBeAPowerOfTwo(Y, /*OrZero*/ false, Depth, Q, DL))
return true;
if (YKnownNonNegative &&
- isKnownToBeAPowerOfTwo(X, /*OrZero*/false, Depth, Q))
+ isKnownToBeAPowerOfTwo(X, /*OrZero*/ false, Depth, Q, DL))
return true;
}
// X * Y.
// If X and Y are non-zero then so is X * Y as long as the multiplication
// does not overflow.
if ((BO->hasNoSignedWrap() || BO->hasNoUnsignedWrap()) &&
- isKnownNonZero(X, TD, Depth, Q) &&
- isKnownNonZero(Y, TD, Depth, Q))
+ isKnownNonZero(X, DL, Depth, Q) && isKnownNonZero(Y, DL, Depth, Q))
return true;
}
// (C ? X : Y) != 0 if X != 0 and Y != 0.
else if (SelectInst *SI = dyn_cast<SelectInst>(V)) {
- if (isKnownNonZero(SI->getTrueValue(), TD, Depth, Q) &&
- isKnownNonZero(SI->getFalseValue(), TD, Depth, Q))
+ if (isKnownNonZero(SI->getTrueValue(), DL, Depth, Q) &&
+ isKnownNonZero(SI->getFalseValue(), DL, Depth, Q))
return true;
}
if (!BitWidth) return false;
APInt KnownZero(BitWidth, 0);
APInt KnownOne(BitWidth, 0);
- computeKnownBits(V, KnownZero, KnownOne, TD, Depth, Q);
+ computeKnownBits(V, KnownZero, KnownOne, DL, Depth, Q);
return KnownOne != 0;
}
/// 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
+/// type, and vectors of integers. In the case
/// where V is a vector, the mask, known zero, and known one values are the
/// same width as the vector element, and the bit is set only if it is true
/// for all of the elements in the vector.
-bool MaskedValueIsZero(Value *V, const APInt &Mask,
- const DataLayout *TD, unsigned Depth,
- const Query &Q) {
+bool MaskedValueIsZero(Value *V, const APInt &Mask, const DataLayout &DL,
+ unsigned Depth, const Query &Q) {
APInt KnownZero(Mask.getBitWidth(), 0), KnownOne(Mask.getBitWidth(), 0);
- computeKnownBits(V, KnownZero, KnownOne, TD, Depth, Q);
+ computeKnownBits(V, KnownZero, KnownOne, DL, Depth, Q);
return (KnownZero & Mask) == Mask;
}
///
/// 'Op' must have a scalar integer type.
///
-unsigned ComputeNumSignBits(Value *V, const DataLayout *TD,
- unsigned Depth, const Query &Q) {
- assert((TD || V->getType()->isIntOrIntVectorTy()) &&
- "ComputeNumSignBits requires a DataLayout object to operate "
- "on non-integer values!");
- Type *Ty = V->getType();
- unsigned TyBits = TD ? TD->getTypeSizeInBits(V->getType()->getScalarType()) :
- Ty->getScalarSizeInBits();
+unsigned ComputeNumSignBits(Value *V, const DataLayout &DL, unsigned Depth,
+ const Query &Q) {
+ unsigned TyBits = DL.getTypeSizeInBits(V->getType()->getScalarType());
unsigned Tmp, Tmp2;
unsigned FirstAnswer = 1;
default: break;
case Instruction::SExt:
Tmp = TyBits - U->getOperand(0)->getType()->getScalarSizeInBits();
- return ComputeNumSignBits(U->getOperand(0), TD, Depth+1, Q) + Tmp;
+ return ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q) + Tmp;
+
+ case Instruction::SDiv: {
+ const APInt *Denominator;
+ // sdiv X, C -> adds log(C) sign bits.
+ if (match(U->getOperand(1), m_APInt(Denominator))) {
+
+ // Ignore non-positive denominator.
+ if (!Denominator->isStrictlyPositive())
+ break;
+
+ // Calculate the incoming numerator bits.
+ unsigned NumBits = ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q);
+
+ // Add floor(log(C)) bits to the numerator bits.
+ return std::min(TyBits, NumBits + Denominator->logBase2());
+ }
+ break;
+ }
+
+ case Instruction::SRem: {
+ const APInt *Denominator;
+ // srem X, C -> we know that the result is within 0..C-1 when C is a
+ // positive constant and the sign bits are at most TypeBits - log2(C).
+ if (match(U->getOperand(1), m_APInt(Denominator))) {
+
+ // Ignore non-positive denominator.
+ if (!Denominator->isStrictlyPositive())
+ break;
+
+ // Calculate the incoming numerator bits. SRem by a positive constant
+ // can't lower the number of sign bits.
+ unsigned NumrBits =
+ ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q);
+
+ // Calculate the leading sign bit constraints by examining the
+ // denominator. The remainder is in the range 0..C-1, which is
+ // calculated by the log2(denominator). The sign bits are the bit-width
+ // minus this value. The result of this subtraction has to be positive.
+ unsigned ResBits = TyBits - Denominator->logBase2();
+
+ return std::max(NumrBits, ResBits);
+ }
+ break;
+ }
case Instruction::AShr: {
- Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1, Q);
+ Tmp = ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q);
// ashr X, C -> adds C sign bits. Vectors too.
const APInt *ShAmt;
if (match(U->getOperand(1), m_APInt(ShAmt))) {
const APInt *ShAmt;
if (match(U->getOperand(1), m_APInt(ShAmt))) {
// shl destroys sign bits.
- Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1, Q);
+ Tmp = ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q);
Tmp2 = ShAmt->getZExtValue();
if (Tmp2 >= TyBits || // Bad shift.
Tmp2 >= Tmp) break; // Shifted all sign bits out.
case Instruction::Or:
case Instruction::Xor: // NOT is handled here.
// Logical binary ops preserve the number of sign bits at the worst.
- Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1, Q);
+ Tmp = ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q);
if (Tmp != 1) {
- Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1, Q);
+ Tmp2 = ComputeNumSignBits(U->getOperand(1), DL, Depth + 1, Q);
FirstAnswer = std::min(Tmp, Tmp2);
// We computed what we know about the sign bits as our first
// answer. Now proceed to the generic code that uses
break;
case Instruction::Select:
- Tmp = ComputeNumSignBits(U->getOperand(1), TD, Depth+1, Q);
+ Tmp = ComputeNumSignBits(U->getOperand(1), DL, Depth + 1, Q);
if (Tmp == 1) return 1; // Early out.
- Tmp2 = ComputeNumSignBits(U->getOperand(2), TD, Depth+1, Q);
+ Tmp2 = ComputeNumSignBits(U->getOperand(2), DL, Depth + 1, Q);
return std::min(Tmp, Tmp2);
case Instruction::Add:
// Add can have at most one carry bit. Thus we know that the output
// is, at worst, one more bit than the inputs.
- Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1, Q);
+ Tmp = ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q);
if (Tmp == 1) return 1; // Early out.
// Special case decrementing a value (ADD X, -1):
if (const auto *CRHS = dyn_cast<Constant>(U->getOperand(1)))
if (CRHS->isAllOnesValue()) {
APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0);
- computeKnownBits(U->getOperand(0), KnownZero, KnownOne, TD, Depth+1, Q);
+ computeKnownBits(U->getOperand(0), KnownZero, KnownOne, DL, Depth + 1,
+ Q);
// If the input is known to be 0 or 1, the output is 0/-1, which is all
// sign bits set.
return Tmp;
}
- Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1, Q);
+ Tmp2 = ComputeNumSignBits(U->getOperand(1), DL, Depth + 1, Q);
if (Tmp2 == 1) return 1;
return std::min(Tmp, Tmp2)-1;
case Instruction::Sub:
- Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1, Q);
+ Tmp2 = ComputeNumSignBits(U->getOperand(1), DL, Depth + 1, Q);
if (Tmp2 == 1) return 1;
// Handle NEG.
if (const auto *CLHS = dyn_cast<Constant>(U->getOperand(0)))
if (CLHS->isNullValue()) {
APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0);
- computeKnownBits(U->getOperand(1), KnownZero, KnownOne, TD, Depth+1, Q);
+ computeKnownBits(U->getOperand(1), KnownZero, KnownOne, DL, Depth + 1,
+ Q);
// If the input is known to be 0 or 1, the output is 0/-1, which is all
// sign bits set.
if ((KnownZero | APInt(TyBits, 1)).isAllOnesValue())
// Sub can have at most one carry bit. Thus we know that the output
// is, at worst, one more bit than the inputs.
- Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1, Q);
+ Tmp = ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q);
if (Tmp == 1) return 1; // Early out.
return std::min(Tmp, Tmp2)-1;
// 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);
+ Tmp = ComputeNumSignBits(PN->getIncomingValue(0), DL, Depth + 1, Q);
for (unsigned i = 1, e = NumIncomingValues; i != e; ++i) {
if (Tmp == 1) return Tmp;
- Tmp = std::min(Tmp,
- ComputeNumSignBits(PN->getIncomingValue(i), TD,
- Depth+1, Q));
+ Tmp = std::min(
+ Tmp, ComputeNumSignBits(PN->getIncomingValue(i), DL, Depth + 1, Q));
}
return Tmp;
}
// use this information.
APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0);
APInt Mask;
- computeKnownBits(V, KnownZero, KnownOne, TD, Depth, Q);
+ computeKnownBits(V, KnownZero, KnownOne, DL, Depth, Q);
if (KnownZero.isNegative()) { // sign bit is 0
Mask = KnownZero;
if (const ConstantFP *CFP = dyn_cast<ConstantFP>(V))
return !CFP->getValueAPF().isNegZero();
+ // FIXME: Magic number! At the least, this should be given a name because it's
+ // used similarly in CannotBeOrderedLessThanZero(). A better fix may be to
+ // expose it as a parameter, so it can be used for testing / experimenting.
if (Depth == 6)
- return 1; // Limit search depth.
+ return false; // Limit search depth.
const Operator *I = dyn_cast<Operator>(V);
if (!I) return false;
if (const ConstantFP *CFP = dyn_cast<ConstantFP>(V))
return !CFP->getValueAPF().isNegative() || CFP->getValueAPF().isZero();
+ // FIXME: Magic number! At the least, this should be given a name because it's
+ // used similarly in CannotBeNegativeZero(). A better fix may be to
+ // expose it as a parameter, so it can be used for testing / experimenting.
if (Depth == 6)
return false; // Limit search depth.
// 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<ConstantInt>(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));
}
}
/// 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
- // the widest we support.
- unsigned BitWidth = DL ? DL->getPointerTypeSizeInBits(Ptr->getType()) : 64;
+ const DataLayout &DL) {
+ unsigned BitWidth = DL.getPointerTypeSizeInBits(Ptr->getType());
APInt ByteOffset(BitWidth, 0);
while (1) {
if (Ptr->getType()->isVectorTy())
break;
if (GEPOperator *GEP = dyn_cast<GEPOperator>(Ptr)) {
- if (DL) {
- APInt GEPOffset(BitWidth, 0);
- if (!GEP->accumulateConstantOffset(*DL, GEPOffset))
- break;
+ APInt GEPOffset(BitWidth, 0);
+ if (!GEP->accumulateConstantOffset(DL, GEPOffset))
+ break;
- ByteOffset += GEPOffset;
- }
+ ByteOffset += GEPOffset;
Ptr = GEP->getPointerOperand();
} else if (Operator::getOpcode(Ptr) == Instruction::BitCast ||
return Len == ~0ULL ? 1 : Len;
}
-Value *
-llvm::GetUnderlyingObject(Value *V, const DataLayout *TD, unsigned MaxLookup) {
+Value *llvm::GetUnderlyingObject(Value *V, const DataLayout &DL,
+ unsigned MaxLookup) {
if (!V->getType()->isPointerTy())
return V;
for (unsigned Count = 0; MaxLookup == 0 || Count < MaxLookup; ++Count) {
// See if InstructionSimplify knows any relevant tricks.
if (Instruction *I = dyn_cast<Instruction>(V))
// TODO: Acquire a DominatorTree and AssumptionCache and use them.
- if (Value *Simplified = SimplifyInstruction(I, TD, nullptr)) {
+ if (Value *Simplified = SimplifyInstruction(I, DL, nullptr)) {
V = Simplified;
continue;
}
return V;
}
-void
-llvm::GetUnderlyingObjects(Value *V,
- SmallVectorImpl<Value *> &Objects,
- const DataLayout *TD,
- unsigned MaxLookup) {
+void llvm::GetUnderlyingObjects(Value *V, SmallVectorImpl<Value *> &Objects,
+ const DataLayout &DL, unsigned MaxLookup) {
SmallPtrSet<Value *, 4> Visited;
SmallVector<Value *, 4> Worklist;
Worklist.push_back(V);
do {
Value *P = Worklist.pop_back_val();
- P = GetUnderlyingObject(P, TD, MaxLookup);
+ P = GetUnderlyingObject(P, DL, MaxLookup);
if (!Visited.insert(P).second)
continue;
return true;
}
-bool llvm::isSafeToSpeculativelyExecute(const Value *V,
- const DataLayout *TD) {
+bool llvm::isSafeToSpeculativelyExecute(const Value *V) {
const Operator *Inst = dyn_cast<Operator>(V);
if (!Inst)
return false;
// Speculative load may create a race that did not exist in the source.
LI->getParent()->getParent()->hasFnAttribute(Attribute::SanitizeThread))
return false;
- return LI->getPointerOperand()->isDereferenceablePointer(TD);
+ const DataLayout &DL = LI->getModule()->getDataLayout();
+ return LI->getPointerOperand()->isDereferenceablePointer(DL);
}
case Instruction::Call: {
if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
}
OverflowResult llvm::computeOverflowForUnsignedMul(Value *LHS, Value *RHS,
- const DataLayout *DL,
+ const DataLayout &DL,
AssumptionCache *AC,
const Instruction *CxtI,
const DominatorTree *DT) {
}
OverflowResult llvm::computeOverflowForUnsignedAdd(Value *LHS, Value *RHS,
- const DataLayout *DL,
+ const DataLayout &DL,
AssumptionCache *AC,
const Instruction *CxtI,
const DominatorTree *DT) {
projects / oota-llvm.git / blobdiff