diff options
Diffstat (limited to 'lib/Analysis/ValueTracking.cpp')
| -rw-r--r-- | lib/Analysis/ValueTracking.cpp | 741 |
1 files changed, 479 insertions, 262 deletions
diff --git a/lib/Analysis/ValueTracking.cpp b/lib/Analysis/ValueTracking.cpp index 0458d28..f329e3a 100644 --- a/lib/Analysis/ValueTracking.cpp +++ b/lib/Analysis/ValueTracking.cpp @@ -39,13 +39,41 @@ using namespace llvm::PatternMatch; 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 @@ -97,73 +125,73 @@ static const Instruction *safeCxtI(const Value *V, const Instruction *CxtI) { } 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)) { @@ -175,7 +203,7 @@ static void computeKnownBitsAddSub(bool Add, Value *Op0, Value *Op1, bool NSW, 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 @@ -194,8 +222,8 @@ static void computeKnownBitsAddSub(bool Add, Value *Op0, Value *Op1, bool NSW, // 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); @@ -243,11 +271,11 @@ static void computeKnownBitsAddSub(bool Add, Value *Op0, Value *Op1, bool NSW, 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; @@ -268,9 +296,9 @@ static void computeKnownBitsMul(Value *Op0, Value *Op1, bool NSW, // 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)); } } @@ -382,8 +410,7 @@ static bool isAssumeLikeIntrinsic(const Instruction *I) { 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: @@ -403,8 +430,7 @@ static bool isValidAssumeForContext(Value *V, const Query &Q, 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); @@ -428,8 +454,7 @@ static bool isValidAssumeForContext(Value *V, const Query &Q, 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); @@ -440,10 +465,9 @@ static bool isValidAssumeForContext(Value *V, const Query &Q, 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> @@ -474,9 +498,181 @@ m_c_Xor(const LHS &L, const RHS &R) { 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! @@ -504,8 +700,7 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, 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(); @@ -525,15 +720,15 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, 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); @@ -546,7 +741,7 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, // 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); @@ -557,9 +752,9 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, 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); @@ -572,7 +767,7 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, // 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); @@ -583,9 +778,9 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, 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); @@ -601,7 +796,7 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, // 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); @@ -617,7 +812,7 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, // 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 @@ -627,7 +822,7 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, // 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 @@ -637,10 +832,9 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, // 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 @@ -649,10 +843,10 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, 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 @@ -661,8 +855,7 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, 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)); @@ -672,8 +865,7 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, } // 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)); @@ -683,8 +875,7 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, } // 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)); @@ -694,8 +885,7 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, } // 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)); @@ -705,8 +895,7 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, } // 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)); @@ -715,14 +904,13 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, 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 @@ -743,13 +931,12 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero, /// 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(); @@ -757,8 +944,7 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, 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 && @@ -797,7 +983,7 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, // 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()) { @@ -805,9 +991,9 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, // 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); } } } @@ -823,11 +1009,11 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, 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) @@ -838,7 +1024,12 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, // 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; } @@ -854,12 +1045,18 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, // 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; @@ -873,8 +1070,8 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, 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; @@ -883,8 +1080,8 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, 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; @@ -893,8 +1090,8 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, 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); @@ -905,21 +1102,20 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, } 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, @@ -929,8 +1125,8 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, 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; @@ -946,8 +1142,6 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, 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: { @@ -956,17 +1150,12 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, 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. @@ -980,7 +1169,7 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, // 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; @@ -991,7 +1180,7 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, 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); @@ -1007,7 +1196,7 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, // (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 @@ -1020,7 +1209,7 @@ 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, DL, Depth + 1, Q); KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); // high bits known zero. @@ -1034,7 +1223,7 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, 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); @@ -1048,15 +1237,15 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, 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: @@ -1064,8 +1253,8 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, 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; @@ -1089,8 +1278,8 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, // 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); @@ -1102,8 +1291,8 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, 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; @@ -1112,8 +1301,8 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, // 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()); @@ -1125,8 +1314,8 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, 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)); @@ -1136,8 +1325,8 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, // 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); @@ -1145,10 +1334,6 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, 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); @@ -1159,7 +1344,7 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, 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)); @@ -1171,9 +1356,10 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, 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())); @@ -1215,11 +1401,11 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, 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(), @@ -1250,8 +1436,8 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, 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 @@ -1303,19 +1489,19 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, 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; } } @@ -1328,9 +1514,8 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne, /// 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; @@ -1338,7 +1523,7 @@ void ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne, } 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]; } @@ -1348,7 +1533,7 @@ void ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne, /// 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; @@ -1375,20 +1560,19 @@ bool isKnownToBeAPowerOfTwo(Value *V, bool OrZero, unsigned Depth, // 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)))) @@ -1403,19 +1587,19 @@ bool isKnownToBeAPowerOfTwo(Value *V, bool OrZero, unsigned Depth, 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 @@ -1433,7 +1617,7 @@ bool isKnownToBeAPowerOfTwo(Value *V, bool OrZero, unsigned Depth, 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; @@ -1445,7 +1629,7 @@ bool isKnownToBeAPowerOfTwo(Value *V, bool OrZero, unsigned Depth, /// 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; @@ -1458,10 +1642,6 @@ static bool isGEPKnownNonNull(GEPOperator *GEP, const DataLayout *DL, 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. @@ -1471,7 +1651,7 @@ static bool isGEPKnownNonNull(GEPOperator *GEP, const DataLayout *DL, 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; @@ -1479,7 +1659,7 @@ static bool isGEPKnownNonNull(GEPOperator *GEP, const DataLayout *DL, } // 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 @@ -1528,7 +1708,7 @@ static bool rangeMetadataExcludesValue(MDNode* Ranges, /// 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()) @@ -1561,21 +1741,20 @@ bool isKnownNonZero(Value *V, const DataLayout *TD, unsigned Depth, 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. @@ -1583,11 +1762,11 @@ bool isKnownNonZero(Value *V, const DataLayout *TD, unsigned Depth, // 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; } @@ -1597,29 +1776,28 @@ bool isKnownNonZero(Value *V, const DataLayout *TD, unsigned Depth, // 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 @@ -1630,22 +1808,22 @@ bool isKnownNonZero(Value *V, const DataLayout *TD, unsigned Depth, 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. @@ -1654,21 +1832,20 @@ bool isKnownNonZero(Value *V, const DataLayout *TD, unsigned Depth, // 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; } @@ -1677,15 +1854,14 @@ bool isKnownNonZero(Value *V, const DataLayout *TD, unsigned Depth, /// 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; } @@ -1699,14 +1875,9 @@ bool MaskedValueIsZero(Value *V, const APInt &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; @@ -1721,10 +1892,63 @@ unsigned ComputeNumSignBits(Value *V, const DataLayout *TD, 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 [-C+1,C) when C is a + // positive constant. This let us put a lower bound on the number of sign + // bits. + 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. Given that the denominator is positive, there are two + // cases: + // + // 1. the numerator is positive. The result range is [0,C) and [0,C) u< + // (1 << ceilLogBase2(C)). + // + // 2. the numerator is negative. Then the result range is (-C,0] and + // integers in (-C,0] are either 0 or >u (-1 << ceilLogBase2(C)). + // + // Thus a lower bound on the number of sign bits is `TyBits - + // ceilLogBase2(C)`. + + unsigned ResBits = TyBits - Denominator->ceilLogBase2(); + 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))) { @@ -1737,7 +1961,7 @@ unsigned ComputeNumSignBits(Value *V, const DataLayout *TD, 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. @@ -1749,9 +1973,9 @@ unsigned ComputeNumSignBits(Value *V, const DataLayout *TD, 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 @@ -1760,22 +1984,23 @@ unsigned ComputeNumSignBits(Value *V, const DataLayout *TD, 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. @@ -1788,19 +2013,20 @@ unsigned ComputeNumSignBits(Value *V, const DataLayout *TD, 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()) @@ -1816,7 +2042,7 @@ unsigned ComputeNumSignBits(Value *V, const DataLayout *TD, // 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; @@ -1830,12 +2056,11 @@ unsigned ComputeNumSignBits(Value *V, const DataLayout *TD, // 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; } @@ -1850,7 +2075,7 @@ unsigned ComputeNumSignBits(Value *V, const DataLayout *TD, // 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; @@ -2132,9 +2357,7 @@ Value *llvm::isBytewiseValue(Value *V) { 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)) + if (!CI->getValue().isSplat(8)) return nullptr; return ConstantInt::get(V->getContext(), CI->getValue().trunc(8)); } @@ -2335,23 +2558,19 @@ Value *llvm::FindInsertedValue(Value *V, ArrayRef<unsigned> idx_range, /// 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 || @@ -2380,7 +2599,7 @@ bool llvm::getConstantStringInfo(const Value *V, StringRef &Str, // Look through bitcast instructions and geps. V = V->stripPointerCasts(); - // If the value is a GEP instructionor constant expression, treat it as an + // If the value is a GEP instruction or constant expression, treat it as an // offset. if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { // Make sure the GEP has exactly three arguments. @@ -2407,7 +2626,8 @@ bool llvm::getConstantStringInfo(const Value *V, StringRef &Str, StartIdx = CI->getZExtValue(); else return false; - return getConstantStringInfo(GEP->getOperand(0), Str, StartIdx+Offset); + return getConstantStringInfo(GEP->getOperand(0), Str, StartIdx + Offset, + TrimAtNul); } // The GEP instruction, constant or instruction, must reference a global @@ -2517,8 +2737,8 @@ uint64_t llvm::GetStringLength(Value *V) { 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) { @@ -2535,7 +2755,7 @@ llvm::GetUnderlyingObject(Value *V, const DataLayout *TD, unsigned MaxLookup) { // 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; } @@ -2547,17 +2767,14 @@ llvm::GetUnderlyingObject(Value *V, const DataLayout *TD, unsigned MaxLookup) { 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; @@ -2591,8 +2808,7 @@ bool llvm::onlyUsedByLifetimeMarkers(const Value *V) { 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; @@ -2638,7 +2854,8 @@ bool llvm::isSafeToSpeculativelyExecute(const Value *V, // 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)) { @@ -2730,7 +2947,7 @@ bool llvm::isKnownNonNull(const Value *V, const TargetLibraryInfo *TLI) { } OverflowResult llvm::computeOverflowForUnsignedMul(Value *LHS, Value *RHS, - const DataLayout *DL, + const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT) { @@ -2780,7 +2997,7 @@ OverflowResult llvm::computeOverflowForUnsignedMul(Value *LHS, Value *RHS, } OverflowResult llvm::computeOverflowForUnsignedAdd(Value *LHS, Value *RHS, - const DataLayout *DL, + const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT) { |