#include "llvm/Analysis/ValueTracking.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/IR/CallSite.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/GetElementPtrTypeIterator.h"
#include "llvm/IR/GlobalAlias.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Statepoint.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/MathExtras.h"
#include <cstring>
using namespace llvm;
using namespace llvm::PatternMatch;
const unsigned MaxDepth = 6;
static cl::opt<bool> EnableDomConditions("value-tracking-dom-conditions",
cl::Hidden, cl::init(false));
static cl::opt<unsigned> DomConditionsMaxDepth("dom-conditions-max-depth",
cl::Hidden, cl::init(1));
static cl::opt<unsigned> DomConditionsMaxDomBlocks("dom-conditions-dom-blocks",
cl::Hidden,
cl::init(20));
static cl::opt<unsigned> DomConditionsMaxUses("dom-conditions-max-uses",
cl::Hidden, cl::init(20));
static cl::opt<bool> DomConditionsSingleCmpUse("dom-conditions-single-cmp-use",
cl::Hidden, cl::init(false));
static unsigned getBitWidth(Type *Ty, const DataLayout &DL) {
if (unsigned BitWidth = Ty->getScalarSizeInBits())
return BitWidth;
return DL.getPointerTypeSizeInBits(Ty);
}
typedef SmallPtrSet<const Value *, 8> ExclInvsSet;
namespace {
struct Query {
ExclInvsSet ExclInvs;
AssumptionCache *AC;
const Instruction *CxtI;
const DominatorTree *DT;
Query(AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr,
const DominatorTree *DT = nullptr)
: AC(AC), CxtI(CxtI), DT(DT) {}
Query(const Query &Q, const Value *NewExcl)
: ExclInvs(Q.ExclInvs), AC(Q.AC), CxtI(Q.CxtI), DT(Q.DT) {
ExclInvs.insert(NewExcl);
}
};
}
static const Instruction *safeCxtI(const Value *V, const Instruction *CxtI) {
if (CxtI && CxtI->getParent())
return CxtI;
CxtI = dyn_cast<Instruction>(V);
if (CxtI && CxtI->getParent())
return CxtI;
return nullptr;
}
static void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne,
const DataLayout &DL, unsigned Depth,
const Query &Q);
void llvm::computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne,
const DataLayout &DL, unsigned Depth,
AssumptionCache *AC, const Instruction *CxtI,
const DominatorTree *DT) {
::computeKnownBits(V, KnownZero, KnownOne, DL, Depth,
Query(AC, safeCxtI(V, CxtI), DT));
}
bool llvm::haveNoCommonBitsSet(Value *LHS, Value *RHS, const DataLayout &DL,
AssumptionCache *AC, const Instruction *CxtI,
const DominatorTree *DT) {
assert(LHS->getType() == RHS->getType() &&
"LHS and RHS should have the same type");
assert(LHS->getType()->isIntOrIntVectorTy() &&
"LHS and RHS should be integers");
IntegerType *IT = cast<IntegerType>(LHS->getType()->getScalarType());
APInt LHSKnownZero(IT->getBitWidth(), 0), LHSKnownOne(IT->getBitWidth(), 0);
APInt RHSKnownZero(IT->getBitWidth(), 0), RHSKnownOne(IT->getBitWidth(), 0);
computeKnownBits(LHS, LHSKnownZero, LHSKnownOne, DL, 0, AC, CxtI, DT);
computeKnownBits(RHS, RHSKnownZero, RHSKnownOne, DL, 0, AC, CxtI, DT);
return (LHSKnownZero | RHSKnownZero).isAllOnesValue();
}
static void ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne,
const DataLayout &DL, unsigned Depth,
const Query &Q);
void llvm::ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne,
const DataLayout &DL, unsigned Depth,
AssumptionCache *AC, const Instruction *CxtI,
const DominatorTree *DT) {
::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 DataLayout &DL);
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), DL);
}
static bool isKnownNonZero(Value *V, const DataLayout &DL, unsigned Depth,
const Query &Q);
bool llvm::isKnownNonZero(Value *V, const DataLayout &DL, unsigned Depth,
AssumptionCache *AC, const Instruction *CxtI,
const DominatorTree *DT) {
return ::isKnownNonZero(V, DL, Depth, Query(AC, safeCxtI(V, CxtI), DT));
}
bool llvm::isKnownNonNegative(Value *V, const DataLayout &DL, unsigned Depth,
AssumptionCache *AC, const Instruction *CxtI,
const DominatorTree *DT) {
bool NonNegative, Negative;
ComputeSignBit(V, NonNegative, Negative, DL, Depth, AC, CxtI, DT);
return NonNegative;
}
static bool isKnownNonEqual(Value *V1, Value *V2, const DataLayout &DL,
const Query &Q);
bool llvm::isKnownNonEqual(Value *V1, Value *V2, const DataLayout &DL,
AssumptionCache *AC, const Instruction *CxtI,
const DominatorTree *DT) {
return ::isKnownNonEqual(V1, V2, DL, Query(AC,
safeCxtI(V1, safeCxtI(V2, CxtI)),
DT));
}
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 &DL,
unsigned Depth, AssumptionCache *AC,
const Instruction *CxtI, const DominatorTree *DT) {
return ::MaskedValueIsZero(V, Mask, DL, Depth,
Query(AC, safeCxtI(V, CxtI), DT));
}
static unsigned ComputeNumSignBits(Value *V, const DataLayout &DL,
unsigned Depth, const Query &Q);
unsigned llvm::ComputeNumSignBits(Value *V, const DataLayout &DL,
unsigned Depth, AssumptionCache *AC,
const Instruction *CxtI,
const DominatorTree *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 &DL, unsigned Depth,
const Query &Q) {
if (!Add) {
if (ConstantInt *CLHS = dyn_cast<ConstantInt>(Op0)) {
if (!CLHS->getValue().isNegative()) {
unsigned BitWidth = KnownZero.getBitWidth();
unsigned NLZ = (CLHS->getValue()+1).countLeadingZeros();
APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
computeKnownBits(Op1, KnownZero2, KnownOne2, DL, Depth + 1, Q);
if ((KnownZero2 & MaskV) == MaskV) {
unsigned NLZ2 = CLHS->getValue().countLeadingZeros();
KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
}
}
}
}
unsigned BitWidth = KnownZero.getBitWidth();
APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0);
computeKnownBits(Op0, LHSKnownZero, LHSKnownOne, DL, Depth + 1, Q);
computeKnownBits(Op1, KnownZero2, KnownOne2, DL, Depth + 1, Q);
APInt CarryIn(BitWidth, 0);
if (!Add) {
std::swap(KnownZero2, KnownOne2);
CarryIn.setBit(0);
}
APInt PossibleSumZero = ~LHSKnownZero + ~KnownZero2 + CarryIn;
APInt PossibleSumOne = LHSKnownOne + KnownOne2 + CarryIn;
APInt CarryKnownZero = ~(PossibleSumZero ^ LHSKnownZero ^ KnownZero2);
APInt CarryKnownOne = PossibleSumOne ^ LHSKnownOne ^ KnownOne2;
APInt LHSKnown = LHSKnownZero | LHSKnownOne;
APInt RHSKnown = KnownZero2 | KnownOne2;
APInt CarryKnown = CarryKnownZero | CarryKnownOne;
APInt Known = LHSKnown & RHSKnown & CarryKnown;
assert((PossibleSumZero & Known) == (PossibleSumOne & Known) &&
"known bits of sum differ");
KnownZero = ~PossibleSumOne & Known;
KnownOne = PossibleSumOne & Known;
if (!Known.isNegative()) {
if (NSW) {
if (LHSKnownZero.isNegative() && KnownZero2.isNegative())
KnownZero |= APInt::getSignBit(BitWidth);
else if (LHSKnownOne.isNegative() && KnownOne2.isNegative())
KnownOne |= APInt::getSignBit(BitWidth);
}
}
}
static void computeKnownBitsMul(Value *Op0, Value *Op1, bool NSW,
APInt &KnownZero, APInt &KnownOne,
APInt &KnownZero2, APInt &KnownOne2,
const DataLayout &DL, unsigned Depth,
const Query &Q) {
unsigned BitWidth = KnownZero.getBitWidth();
computeKnownBits(Op1, KnownZero, KnownOne, DL, Depth + 1, Q);
computeKnownBits(Op0, KnownZero2, KnownOne2, DL, Depth + 1, Q);
bool isKnownNegative = false;
bool isKnownNonNegative = false;
if (NSW) {
if (Op0 == Op1) {
isKnownNonNegative = true;
} else {
bool isKnownNonNegativeOp1 = KnownZero.isNegative();
bool isKnownNonNegativeOp0 = KnownZero2.isNegative();
bool isKnownNegativeOp1 = KnownOne.isNegative();
bool isKnownNegativeOp0 = KnownOne2.isNegative();
isKnownNonNegative = (isKnownNegativeOp1 && isKnownNegativeOp0) ||
(isKnownNonNegativeOp1 && isKnownNonNegativeOp0);
if (!isKnownNonNegative)
isKnownNegative = (isKnownNegativeOp1 && isKnownNonNegativeOp0 &&
isKnownNonZero(Op0, DL, Depth, Q)) ||
(isKnownNegativeOp0 && isKnownNonNegativeOp1 &&
isKnownNonZero(Op1, DL, Depth, Q));
}
}
KnownOne.clearAllBits();
unsigned TrailZ = KnownZero.countTrailingOnes() +
KnownZero2.countTrailingOnes();
unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
KnownZero2.countLeadingOnes(),
BitWidth) - BitWidth;
TrailZ = std::min(TrailZ, BitWidth);
LeadZ = std::min(LeadZ, BitWidth);
KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
APInt::getHighBitsSet(BitWidth, LeadZ);
if (isKnownNonNegative && !KnownOne.isNegative())
KnownZero.setBit(BitWidth - 1);
else if (isKnownNegative && !KnownZero.isNegative())
KnownOne.setBit(BitWidth - 1);
}
void llvm::computeKnownBitsFromRangeMetadata(const MDNode &Ranges,
APInt &KnownZero,
APInt &KnownOne) {
unsigned BitWidth = KnownZero.getBitWidth();
unsigned NumRanges = Ranges.getNumOperands() / 2;
assert(NumRanges >= 1);
KnownZero.setAllBits();
KnownOne.setAllBits();
for (unsigned i = 0; i < NumRanges; ++i) {
ConstantInt *Lower =
mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
ConstantInt *Upper =
mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
ConstantRange Range(Lower->getValue(), Upper->getValue());
unsigned CommonPrefixBits =
(Range.getUnsignedMax() ^ Range.getUnsignedMin()).countLeadingZeros();
APInt Mask = APInt::getHighBitsSet(BitWidth, CommonPrefixBits);
KnownOne &= Range.getUnsignedMax() & Mask;
KnownZero &= ~Range.getUnsignedMax() & Mask;
}
}
static bool isEphemeralValueOf(Instruction *I, const Value *E) {
SmallVector<const Value *, 16> WorkSet(1, I);
SmallPtrSet<const Value *, 32> Visited;
SmallPtrSet<const Value *, 16> EphValues;
if (std::find(I->op_begin(), I->op_end(), E) != I->op_end())
return true;
while (!WorkSet.empty()) {
const Value *V = WorkSet.pop_back_val();
if (!Visited.insert(V).second)
continue;
if (std::all_of(V->user_begin(), V->user_end(),
[&](const User *U) { return EphValues.count(U); })) {
if (V == E)
return true;
EphValues.insert(V);
if (const User *U = dyn_cast<User>(V))
for (User::const_op_iterator J = U->op_begin(), JE = U->op_end();
J != JE; ++J) {
if (isSafeToSpeculativelyExecute(*J))
WorkSet.push_back(*J);
}
}
}
return false;
}
static bool isAssumeLikeIntrinsic(const Instruction *I) {
if (const CallInst *CI = dyn_cast<CallInst>(I))
if (Function *F = CI->getCalledFunction())
switch (F->getIntrinsicID()) {
default: break;
case Intrinsic::assume:
case Intrinsic::dbg_declare:
case Intrinsic::dbg_value:
case Intrinsic::invariant_start:
case Intrinsic::invariant_end:
case Intrinsic::lifetime_start:
case Intrinsic::lifetime_end:
case Intrinsic::objectsize:
case Intrinsic::ptr_annotation:
case Intrinsic::var_annotation:
return true;
}
return false;
}
static bool isValidAssumeForContext(Value *V, const Query &Q) {
Instruction *Inv = cast<Instruction>(V);
if (Q.DT) {
if (Q.DT->dominates(Inv, Q.CxtI)) {
return true;
} else if (Inv->getParent() == Q.CxtI->getParent()) {
for (BasicBlock::const_iterator I =
std::next(BasicBlock::const_iterator(Q.CxtI)),
IE(Inv); I != IE; ++I)
if (!isSafeToSpeculativelyExecute(&*I) && !isAssumeLikeIntrinsic(&*I))
return false;
return !isEphemeralValueOf(Inv, Q.CxtI);
}
return false;
}
if (Inv->getParent() == Q.CxtI->getParent()->getSinglePredecessor()) {
return true;
} else if (Inv->getParent() == Q.CxtI->getParent()) {
for (BasicBlock::iterator I = std::next(BasicBlock::iterator(Inv)),
IE = Inv->getParent()->end(); I != IE; ++I)
if (&*I == Q.CxtI)
return true;
for (BasicBlock::const_iterator I =
std::next(BasicBlock::const_iterator(Q.CxtI)),
IE(Inv); I != IE; ++I)
if (!isSafeToSpeculativelyExecute(&*I) && !isAssumeLikeIntrinsic(&*I))
return false;
return !isEphemeralValueOf(Inv, Q.CxtI);
}
return false;
}
bool llvm::isValidAssumeForContext(const Instruction *I,
const Instruction *CxtI,
const DominatorTree *DT) {
return ::isValidAssumeForContext(const_cast<Instruction *>(I),
Query(nullptr, CxtI, DT));
}
template<typename LHS, typename RHS>
inline match_combine_or<CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>,
CmpClass_match<RHS, LHS, ICmpInst, ICmpInst::Predicate>>
m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
return m_CombineOr(m_ICmp(Pred, L, R), m_ICmp(Pred, R, L));
}
template<typename LHS, typename RHS>
inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::And>,
BinaryOp_match<RHS, LHS, Instruction::And>>
m_c_And(const LHS &L, const RHS &R) {
return m_CombineOr(m_And(L, R), m_And(R, L));
}
template<typename LHS, typename RHS>
inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::Or>,
BinaryOp_match<RHS, LHS, Instruction::Or>>
m_c_Or(const LHS &L, const RHS &R) {
return m_CombineOr(m_Or(L, R), m_Or(R, L));
}
template<typename LHS, typename RHS>
inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::Xor>,
BinaryOp_match<RHS, LHS, Instruction::Xor>>
m_c_Xor(const LHS &L, const RHS &R) {
return m_CombineOr(m_Xor(L, R), m_Xor(R, L));
}
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);
if (LHS != V && RHS != V)
return;
const unsigned BitWidth = KnownZero.getBitWidth();
switch (Cmp->getPredicate()) {
default:
break;
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()) {
KnownZero |= APInt::getSignBit(BitWidth);
}
}
break;
case ICmpInst::ICMP_EQ:
{
APInt KnownZeroTemp(BitWidth, 0), KnownOneTemp(BitWidth, 0);
if (LHS == V)
computeKnownBits(RHS, KnownZeroTemp, KnownOneTemp, DL, Depth + 1, Q);
else if (RHS == V)
computeKnownBits(LHS, KnownZeroTemp, KnownOneTemp, DL, Depth + 1, Q);
else
llvm_unreachable("missing use?");
KnownZero |= KnownZeroTemp;
KnownOne |= KnownOneTemp;
}
break;
case ICmpInst::ICMP_ULE:
if (LHS == V) {
APInt KnownZeroTemp(BitWidth, 0), KnownOneTemp(BitWidth, 0);
computeKnownBits(RHS, KnownZeroTemp, KnownOneTemp, DL, Depth + 1, Q);
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);
unsigned SignBits = KnownZeroTemp.countLeadingOnes();
if (isKnownToBeAPowerOfTwo(RHS, false, Depth + 1, Query(Q, Cmp), DL))
SignBits++;
KnownZero |= APInt::getHighBitsSet(BitWidth, SignBits);
}
break;
};
}
static void computeKnownBitsFromDominatingCondition(Value *V, APInt &KnownZero,
APInt &KnownOne,
const DataLayout &DL,
unsigned Depth,
const Query &Q) {
if (!Q.DT || !Q.CxtI)
return;
Instruction *Cxt = const_cast<Instruction *>(Q.CxtI);
if (!Q.DT->isReachableFromEntry(Cxt->getParent()))
return;
if (auto VI = dyn_cast<Instruction>(V))
if (VI->getParent() == Cxt->getParent())
return;
unsigned NumBlocksExplored = 0;
BasicBlock *Current = Cxt->getParent();
while (true) {
if (NumBlocksExplored >= DomConditionsMaxDomBlocks)
break;
NumBlocksExplored++;
if (!Q.DT->getNode(Current)->getIDom())
break;
Current = Q.DT->getNode(Current)->getIDom()->getBlock();
if (!Current)
break;
BranchInst *BI = dyn_cast<BranchInst>(Current->getTerminator());
if (!BI || BI->isUnconditional())
continue;
ICmpInst *Cmp = dyn_cast<ICmpInst>(BI->getCondition());
if (!Cmp)
continue;
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);
}
unsigned NumUsesExplored = 0;
for (auto U : V->users()) {
if (NumUsesExplored >= DomConditionsMaxUses)
break;
NumUsesExplored++;
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;
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,
unsigned Depth, const Query &Q) {
if (!Q.AC || !Q.CxtI)
return;
unsigned BitWidth = KnownZero.getBitWidth();
for (auto &AssumeVH : Q.AC->assumptions()) {
if (!AssumeVH)
continue;
CallInst *I = cast<CallInst>(AssumeVH);
assert(I->getParent()->getParent() == Q.CxtI->getParent()->getParent() &&
"Got assumption for the wrong function!");
if (Q.ExclInvs.count(I))
continue;
assert(I->getCalledFunction()->getIntrinsicID() == Intrinsic::assume &&
"must be an assume intrinsic");
Value *Arg = I->getArgOperand(0);
if (Arg == V && isValidAssumeForContext(I, Q)) {
assert(BitWidth == 1 && "assume operand is not i1?");
KnownZero.clearAllBits();
KnownOne.setAllBits();
return;
}
if (Depth == MaxDepth)
continue;
Value *A, *B;
auto m_V = m_CombineOr(m_Specific(V),
m_CombineOr(m_PtrToInt(m_Specific(V)),
m_BitCast(m_Specific(V))));
CmpInst::Predicate Pred;
ConstantInt *C;
if (match(Arg, m_c_ICmp(Pred, m_V, 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));
KnownZero |= RHSKnownZero;
KnownOne |= RHSKnownOne;
} 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);
computeKnownBits(B, MaskKnownZero, MaskKnownOne, DL, Depth+1, Query(Q, I));
KnownZero |= RHSKnownZero & MaskKnownOne;
KnownOne |= RHSKnownOne & MaskKnownOne;
} 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)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
APInt MaskKnownZero(BitWidth, 0), MaskKnownOne(BitWidth, 0);
computeKnownBits(B, MaskKnownZero, MaskKnownOne, DL, Depth+1, Query(Q, I));
KnownZero |= RHSKnownOne & MaskKnownOne;
KnownOne |= RHSKnownZero & MaskKnownOne;
} 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);
computeKnownBits(B, BKnownZero, BKnownOne, DL, Depth+1, Query(Q, I));
KnownZero |= RHSKnownZero & BKnownZero;
KnownOne |= RHSKnownOne & BKnownZero;
} 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)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
APInt BKnownZero(BitWidth, 0), BKnownOne(BitWidth, 0);
computeKnownBits(B, BKnownZero, BKnownOne, DL, Depth+1, Query(Q, I));
KnownZero |= RHSKnownOne & BKnownZero;
KnownOne |= RHSKnownZero & BKnownZero;
} 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);
computeKnownBits(B, BKnownZero, BKnownOne, DL, Depth+1, Query(Q, I));
KnownZero |= RHSKnownZero & BKnownZero;
KnownOne |= RHSKnownOne & BKnownZero;
KnownZero |= RHSKnownOne & BKnownOne;
KnownOne |= RHSKnownZero & BKnownOne;
} 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)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
APInt BKnownZero(BitWidth, 0), BKnownOne(BitWidth, 0);
computeKnownBits(B, BKnownZero, BKnownOne, DL, Depth+1, Query(Q, I));
KnownZero |= RHSKnownOne & BKnownZero;
KnownOne |= RHSKnownZero & BKnownZero;
KnownZero |= RHSKnownZero & BKnownOne;
KnownOne |= RHSKnownOne & BKnownOne;
} 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)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
KnownZero |= RHSKnownZero.lshr(C->getZExtValue());
KnownOne |= RHSKnownOne.lshr(C->getZExtValue());
} 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)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
KnownZero |= RHSKnownOne.lshr(C->getZExtValue());
KnownOne |= RHSKnownZero.lshr(C->getZExtValue());
} 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)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
KnownZero |= RHSKnownZero << C->getZExtValue();
KnownOne |= RHSKnownOne << C->getZExtValue();
} else if (match(Arg, m_c_ICmp(Pred, m_Not(m_CombineOr(
m_LShr(m_V, m_ConstantInt(C)),
m_AShr(m_V, m_ConstantInt(C)))),
m_Value(A))) &&
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 |= RHSKnownOne << C->getZExtValue();
KnownOne |= RHSKnownZero << C->getZExtValue();
} else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
Pred == ICmpInst::ICMP_SGE && isValidAssumeForContext(I, Q)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
if (RHSKnownZero.isNegative()) {
KnownZero |= APInt::getSignBit(BitWidth);
}
} else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
Pred == ICmpInst::ICMP_SGT && isValidAssumeForContext(I, Q)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
if (RHSKnownOne.isAllOnesValue() || RHSKnownZero.isNegative()) {
KnownZero |= APInt::getSignBit(BitWidth);
}
} else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
Pred == ICmpInst::ICMP_SLE && isValidAssumeForContext(I, Q)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
if (RHSKnownOne.isNegative()) {
KnownOne |= APInt::getSignBit(BitWidth);
}
} else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
Pred == ICmpInst::ICMP_SLT && isValidAssumeForContext(I, Q)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
if (RHSKnownZero.isAllOnesValue() || RHSKnownOne.isNegative()) {
KnownOne |= APInt::getSignBit(BitWidth);
}
} else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
Pred == ICmpInst::ICMP_ULE && isValidAssumeForContext(I, Q)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
KnownZero |=
APInt::getHighBitsSet(BitWidth, RHSKnownZero.countLeadingOnes());
} else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
Pred == ICmpInst::ICMP_ULT && isValidAssumeForContext(I, Q)) {
APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
computeKnownBits(A, RHSKnownZero, RHSKnownOne, DL, Depth+1, Query(Q, I));
if (isKnownToBeAPowerOfTwo(A, false, Depth + 1, Query(Q, I), DL))
KnownZero |=
APInt::getHighBitsSet(BitWidth, RHSKnownZero.countLeadingOnes()+1);
else
KnownZero |=
APInt::getHighBitsSet(BitWidth, RHSKnownZero.countLeadingOnes());
}
}
}
template <typename KZFunctor, typename KOFunctor>
static void computeKnownBitsFromShiftOperator(Operator *I,
APInt &KnownZero, APInt &KnownOne,
APInt &KnownZero2, APInt &KnownOne2,
const DataLayout &DL, unsigned Depth, const Query &Q,
KZFunctor KZF, KOFunctor KOF) {
unsigned BitWidth = KnownZero.getBitWidth();
if (auto *SA = dyn_cast<ConstantInt>(I->getOperand(1))) {
unsigned ShiftAmt = SA->getLimitedValue(BitWidth-1);
computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1, Q);
KnownZero = KZF(KnownZero, ShiftAmt);
KnownOne = KOF(KnownOne, ShiftAmt);
return;
}
computeKnownBits(I->getOperand(1), KnownZero, KnownOne, DL, Depth + 1, Q);
uint64_t ShiftAmtKZ = KnownZero.zextOrTrunc(64).getZExtValue();
uint64_t ShiftAmtKO = KnownOne.zextOrTrunc(64).getZExtValue();
KnownZero.clearAllBits(), KnownOne.clearAllBits();
if (!(ShiftAmtKZ & (BitWidth-1)) && !(ShiftAmtKO & (BitWidth-1)))
return;
computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, DL, Depth + 1, Q);
KnownZero = KnownOne = APInt::getAllOnesValue(BitWidth);
for (unsigned ShiftAmt = 0; ShiftAmt < BitWidth; ++ShiftAmt) {
if ((ShiftAmt & ~ShiftAmtKZ) != ShiftAmt)
continue;
if ((ShiftAmt | ShiftAmtKO) != ShiftAmt)
continue;
KnownZero &= KZF(KnownZero2, ShiftAmt);
KnownOne &= KOF(KnownOne2, ShiftAmt);
}
if ((KnownZero & KnownOne) != 0)
KnownZero.clearAllBits(), KnownOne.clearAllBits();
}
static void computeKnownBitsFromOperator(Operator *I, APInt &KnownZero,
APInt &KnownOne, const DataLayout &DL,
unsigned Depth, const Query &Q) {
unsigned BitWidth = KnownZero.getBitWidth();
APInt KnownZero2(KnownZero), KnownOne2(KnownOne);
switch (I->getOpcode()) {
default: break;
case Instruction::Load:
if (MDNode *MD = cast<LoadInst>(I)->getMetadata(LLVMContext::MD_range))
computeKnownBitsFromRangeMetadata(*MD, KnownZero, KnownOne);
break;
case Instruction::And: {
computeKnownBits(I->getOperand(1), KnownZero, KnownOne, DL, Depth + 1, Q);
computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, DL, Depth + 1, Q);
KnownOne &= KnownOne2;
KnownZero |= KnownZero2;
break;
}
case Instruction::Or: {
computeKnownBits(I->getOperand(1), KnownZero, KnownOne, DL, Depth + 1, Q);
computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, DL, Depth + 1, Q);
KnownZero &= KnownZero2;
KnownOne |= KnownOne2;
break;
}
case Instruction::Xor: {
computeKnownBits(I->getOperand(1), KnownZero, KnownOne, DL, Depth + 1, Q);
computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, DL, Depth + 1, Q);
APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
KnownZero = KnownZeroOut;
break;
}
case Instruction::Mul: {
bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap();
computeKnownBitsMul(I->getOperand(0), I->getOperand(1), NSW, KnownZero,
KnownOne, KnownZero2, KnownOne2, DL, Depth, Q);
break;
}
case Instruction::UDiv: {
computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, DL, Depth + 1, Q);
unsigned LeadZ = KnownZero2.countLeadingOnes();
KnownOne2.clearAllBits();
KnownZero2.clearAllBits();
computeKnownBits(I->getOperand(1), KnownZero2, KnownOne2, DL, Depth + 1, Q);
unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
if (RHSUnknownLeadingOnes != BitWidth)
LeadZ = std::min(BitWidth,
LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
break;
}
case Instruction::Select:
computeKnownBits(I->getOperand(2), KnownZero, KnownOne, DL, Depth + 1, Q);
computeKnownBits(I->getOperand(1), KnownZero2, KnownOne2, DL, Depth + 1, Q);
KnownOne &= KnownOne2;
KnownZero &= KnownZero2;
break;
case Instruction::FPTrunc:
case Instruction::FPExt:
case Instruction::FPToUI:
case Instruction::FPToSI:
case Instruction::SIToFP:
case Instruction::UIToFP:
break; case Instruction::PtrToInt:
case Instruction::IntToPtr:
case Instruction::AddrSpaceCast: case Instruction::ZExt:
case Instruction::Trunc: {
Type *SrcTy = I->getOperand(0)->getType();
unsigned SrcBitWidth;
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, DL, Depth + 1, Q);
KnownZero = KnownZero.zextOrTrunc(BitWidth);
KnownOne = KnownOne.zextOrTrunc(BitWidth);
if (BitWidth > SrcBitWidth)
KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth);
break;
}
case Instruction::BitCast: {
Type *SrcTy = I->getOperand(0)->getType();
if ((SrcTy->isIntegerTy() || SrcTy->isPointerTy() ||
SrcTy->isFloatingPointTy()) &&
!I->getType()->isVectorTy()) {
computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1, Q);
break;
}
break;
}
case Instruction::SExt: {
unsigned SrcBitWidth = I->getOperand(0)->getType()->getScalarSizeInBits();
KnownZero = KnownZero.trunc(SrcBitWidth);
KnownOne = KnownOne.trunc(SrcBitWidth);
computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1, Q);
KnownZero = KnownZero.zext(BitWidth);
KnownOne = KnownOne.zext(BitWidth);
if (KnownZero[SrcBitWidth-1]) KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth);
else if (KnownOne[SrcBitWidth-1]) KnownOne |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth);
break;
}
case Instruction::Shl: {
auto KZF = [BitWidth](const APInt &KnownZero, unsigned ShiftAmt) {
return (KnownZero << ShiftAmt) |
APInt::getLowBitsSet(BitWidth, ShiftAmt); };
auto KOF = [BitWidth](const APInt &KnownOne, unsigned ShiftAmt) {
return KnownOne << ShiftAmt;
};
computeKnownBitsFromShiftOperator(I, KnownZero, KnownOne,
KnownZero2, KnownOne2, DL, Depth, Q,
KZF, KOF);
break;
}
case Instruction::LShr: {
auto KZF = [BitWidth](const APInt &KnownZero, unsigned ShiftAmt) {
return APIntOps::lshr(KnownZero, ShiftAmt) |
APInt::getHighBitsSet(BitWidth, ShiftAmt);
};
auto KOF = [BitWidth](const APInt &KnownOne, unsigned ShiftAmt) {
return APIntOps::lshr(KnownOne, ShiftAmt);
};
computeKnownBitsFromShiftOperator(I, KnownZero, KnownOne,
KnownZero2, KnownOne2, DL, Depth, Q,
KZF, KOF);
break;
}
case Instruction::AShr: {
auto KZF = [BitWidth](const APInt &KnownZero, unsigned ShiftAmt) {
return APIntOps::ashr(KnownZero, ShiftAmt);
};
auto KOF = [BitWidth](const APInt &KnownOne, unsigned ShiftAmt) {
return APIntOps::ashr(KnownOne, ShiftAmt);
};
computeKnownBitsFromShiftOperator(I, KnownZero, KnownOne,
KnownZero2, KnownOne2, DL, Depth, Q,
KZF, KOF);
break;
}
case Instruction::Sub: {
bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap();
computeKnownBitsAddSub(false, I->getOperand(0), I->getOperand(1), NSW,
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, DL,
Depth, Q);
break;
}
case Instruction::SRem:
if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) {
APInt RA = Rem->getValue().abs();
if (RA.isPowerOf2()) {
APInt LowBits = RA - 1;
computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, DL, Depth + 1,
Q);
KnownZero = KnownZero2 & LowBits;
KnownOne = KnownOne2 & LowBits;
if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
KnownZero |= ~LowBits;
if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
KnownOne |= ~LowBits;
assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
}
}
if (KnownZero.isNonNegative()) {
APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0);
computeKnownBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, DL,
Depth + 1, Q);
if (LHSKnownZero.isNegative())
KnownZero.setBit(BitWidth - 1);
}
break;
case Instruction::URem: {
if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) {
APInt RA = Rem->getValue();
if (RA.isPowerOf2()) {
APInt LowBits = (RA - 1);
computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1,
Q);
KnownZero |= ~LowBits;
KnownOne &= LowBits;
break;
}
}
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());
KnownOne.clearAllBits();
KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
break;
}
case Instruction::Alloca: {
AllocaInst *AI = cast<AllocaInst>(I);
unsigned Align = AI->getAlignment();
if (Align == 0)
Align = DL.getABITypeAlignment(AI->getType()->getElementType());
if (Align > 0)
KnownZero = APInt::getLowBitsSet(BitWidth, countTrailingZeros(Align));
break;
}
case Instruction::GetElementPtr: {
APInt LocalKnownZero(BitWidth, 0), LocalKnownOne(BitWidth, 0);
computeKnownBits(I->getOperand(0), LocalKnownZero, LocalKnownOne, DL,
Depth + 1, Q);
unsigned TrailZ = LocalKnownZero.countTrailingOnes();
gep_type_iterator GTI = gep_type_begin(I);
for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i, ++GTI) {
Value *Index = I->getOperand(i);
if (StructType *STy = dyn_cast<StructType>(*GTI)) {
Constant *CIndex = cast<Constant>(Index);
if (CIndex->isZeroValue())
continue;
if (CIndex->getType()->isVectorTy())
Index = CIndex->getSplatValue();
unsigned Idx = cast<ConstantInt>(Index)->getZExtValue();
const StructLayout *SL = DL.getStructLayout(STy);
uint64_t Offset = SL->getElementOffset(Idx);
TrailZ = std::min<unsigned>(TrailZ,
countTrailingZeros(Offset));
} else {
Type *IndexedTy = GTI.getIndexedType();
if (!IndexedTy->isSized()) {
TrailZ = 0;
break;
}
unsigned GEPOpiBits = Index->getType()->getScalarSizeInBits();
uint64_t TypeSize = DL.getTypeAllocSize(IndexedTy);
LocalKnownZero = LocalKnownOne = APInt(GEPOpiBits, 0);
computeKnownBits(Index, LocalKnownZero, LocalKnownOne, DL, Depth + 1,
Q);
TrailZ = std::min(TrailZ,
unsigned(countTrailingZeros(TypeSize) +
LocalKnownZero.countTrailingOnes()));
}
}
KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ);
break;
}
case Instruction::PHI: {
PHINode *P = cast<PHINode>(I);
if (P->getNumIncomingValues() == 2) {
for (unsigned i = 0; i != 2; ++i) {
Value *L = P->getIncomingValue(i);
Value *R = P->getIncomingValue(!i);
Operator *LU = dyn_cast<Operator>(L);
if (!LU)
continue;
unsigned Opcode = LU->getOpcode();
if (Opcode == Instruction::Add ||
Opcode == Instruction::Sub ||
Opcode == Instruction::And ||
Opcode == Instruction::Or ||
Opcode == Instruction::Mul) {
Value *LL = LU->getOperand(0);
Value *LR = LU->getOperand(1);
if (LL == I)
L = LR;
else if (LR == I)
L = LL;
else
break;
computeKnownBits(R, KnownZero2, KnownOne2, DL, Depth + 1, Q);
APInt KnownZero3(KnownZero), KnownOne3(KnownOne);
computeKnownBits(L, KnownZero3, KnownOne3, DL, Depth + 1, Q);
KnownZero = APInt::getLowBitsSet(BitWidth,
std::min(KnownZero2.countTrailingOnes(),
KnownZero3.countTrailingOnes()));
break;
}
}
}
if (P->getNumIncomingValues() == 0)
break;
if (Depth < MaxDepth - 1 && !KnownZero && !KnownOne) {
if (dyn_cast_or_null<UndefValue>(P->hasConstantValue()))
break;
KnownZero = APInt::getAllOnesValue(BitWidth);
KnownOne = APInt::getAllOnesValue(BitWidth);
for (Value *IncValue : P->incoming_values()) {
if (IncValue == P) continue;
KnownZero2 = APInt(BitWidth, 0);
KnownOne2 = APInt(BitWidth, 0);
computeKnownBits(IncValue, KnownZero2, KnownOne2, DL,
MaxDepth - 1, Q);
KnownZero &= KnownZero2;
KnownOne &= KnownOne2;
if (!KnownZero && !KnownOne)
break;
}
}
break;
}
case Instruction::Call:
case Instruction::Invoke:
if (MDNode *MD = cast<Instruction>(I)->getMetadata(LLVMContext::MD_range))
computeKnownBitsFromRangeMetadata(*MD, KnownZero, KnownOne);
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
switch (II->getIntrinsicID()) {
default: break;
case Intrinsic::bswap:
computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, DL,
Depth + 1, Q);
KnownZero |= KnownZero2.byteSwap();
KnownOne |= KnownOne2.byteSwap();
break;
case Intrinsic::ctlz:
case Intrinsic::cttz: {
unsigned LowBits = Log2_32(BitWidth)+1;
if (II->getArgOperand(1) == ConstantInt::getTrue(II->getContext()))
LowBits -= 1;
KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
break;
}
case Intrinsic::ctpop: {
computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, DL,
Depth + 1, Q);
unsigned BitsPossiblySet = BitWidth - KnownZero2.countPopulation();
unsigned LeadingZeros =
APInt(BitWidth, BitsPossiblySet).countLeadingZeros();
assert(LeadingZeros <= BitWidth);
KnownZero |= APInt::getHighBitsSet(BitWidth, LeadingZeros);
KnownOne &= ~KnownZero;
break;
}
case Intrinsic::fabs: {
Type *Ty = II->getType();
APInt SignBit = APInt::getSignBit(Ty->getScalarSizeInBits());
KnownZero |= APInt::getSplat(Ty->getPrimitiveSizeInBits(), SignBit);
break;
}
case Intrinsic::x86_sse42_crc32_64_64:
KnownZero |= APInt::getHighBitsSet(64, 32);
break;
}
}
break;
case Instruction::ExtractValue:
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I->getOperand(0))) {
ExtractValueInst *EVI = cast<ExtractValueInst>(I);
if (EVI->getNumIndices() != 1) break;
if (EVI->getIndices()[0] == 0) {
switch (II->getIntrinsicID()) {
default: break;
case Intrinsic::uadd_with_overflow:
case Intrinsic::sadd_with_overflow:
computeKnownBitsAddSub(true, II->getArgOperand(0),
II->getArgOperand(1), false, KnownZero,
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, 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, DL,
Depth, Q);
break;
}
}
}
}
}
static unsigned getAlignment(const Value *V, const DataLayout &DL) {
unsigned Align = 0;
if (auto *GO = dyn_cast<GlobalObject>(V)) {
Align = GO->getAlignment();
if (Align == 0) {
if (auto *GVar = dyn_cast<GlobalVariable>(GO)) {
Type *ObjectType = GVar->getType()->getElementType();
if (ObjectType->isSized()) {
if (GVar->isStrongDefinitionForLinker())
Align = DL.getPreferredAlignment(GVar);
else
Align = DL.getABITypeAlignment(ObjectType);
}
}
}
} else if (const Argument *A = dyn_cast<Argument>(V)) {
Align = A->getType()->isPointerTy() ? A->getParamAlignment() : 0;
if (!Align && A->hasStructRetAttr()) {
Type *EltTy = cast<PointerType>(A->getType())->getElementType();
if (EltTy->isSized())
Align = DL.getABITypeAlignment(EltTy);
}
} else if (const AllocaInst *AI = dyn_cast<AllocaInst>(V))
Align = AI->getAlignment();
else if (auto CS = ImmutableCallSite(V))
Align = CS.getAttributes().getParamAlignment(AttributeSet::ReturnIndex);
else if (const LoadInst *LI = dyn_cast<LoadInst>(V))
if (MDNode *MD = LI->getMetadata(LLVMContext::MD_align)) {
ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
Align = CI->getLimitedValue();
}
return Align;
}
void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne,
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()->isFPOrFPVectorTy() ||
V->getType()->getScalarType()->isPointerTy()) &&
"Not integer, floating point, or pointer type!");
assert((DL.getTypeSizeInBits(V->getType()->getScalarType()) == BitWidth) &&
(!V->getType()->isIntOrIntVectorTy() ||
V->getType()->getScalarSizeInBits() == BitWidth) &&
KnownZero.getBitWidth() == BitWidth &&
KnownOne.getBitWidth() == BitWidth &&
"V, KnownOne and KnownZero should have same BitWidth");
if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
KnownOne = CI->getValue();
KnownZero = ~KnownOne;
return;
}
if (isa<ConstantPointerNull>(V) ||
isa<ConstantAggregateZero>(V)) {
KnownOne.clearAllBits();
KnownZero = APInt::getAllOnesValue(BitWidth);
return;
}
if (ConstantDataSequential *CDS = dyn_cast<ConstantDataSequential>(V)) {
KnownZero.setAllBits(); KnownOne.setAllBits();
APInt Elt(KnownZero.getBitWidth(), 0);
for (unsigned i = 0, e = CDS->getNumElements(); i != e; ++i) {
Elt = CDS->getElementAsInteger(i);
KnownZero &= ~Elt;
KnownOne &= Elt;
}
return;
}
KnownZero.clearAllBits(); KnownOne.clearAllBits();
if (Depth == MaxDepth)
return;
if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
if (!GA->mayBeOverridden())
computeKnownBits(GA->getAliasee(), KnownZero, KnownOne, DL, Depth + 1, Q);
return;
}
if (Operator *I = dyn_cast<Operator>(V))
computeKnownBitsFromOperator(I, KnownZero, KnownOne, DL, Depth, Q);
if (V->getType()->isPointerTy()) {
unsigned Align = getAlignment(V, DL);
if (Align)
KnownZero |= APInt::getLowBitsSet(BitWidth, countTrailingZeros(Align));
}
computeKnownBitsFromAssume(V, KnownZero, KnownOne, DL, Depth, Q);
if (EnableDomConditions && Depth <= DomConditionsMaxDepth)
computeKnownBitsFromDominatingCondition(V, KnownZero, KnownOne, DL, Depth,
Q);
assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
}
void ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne,
const DataLayout &DL, unsigned Depth, const Query &Q) {
unsigned BitWidth = getBitWidth(V->getType(), DL);
if (!BitWidth) {
KnownZero = false;
KnownOne = false;
return;
}
APInt ZeroBits(BitWidth, 0);
APInt OneBits(BitWidth, 0);
computeKnownBits(V, ZeroBits, OneBits, DL, Depth, Q);
KnownOne = OneBits[BitWidth - 1];
KnownZero = ZeroBits[BitWidth - 1];
}
bool isKnownToBeAPowerOfTwo(Value *V, bool OrZero, unsigned Depth,
const Query &Q, const DataLayout &DL) {
if (Constant *C = dyn_cast<Constant>(V)) {
if (C->isNullValue())
return OrZero;
if (ConstantInt *CI = dyn_cast<ConstantInt>(C))
return CI->getValue().isPowerOf2();
}
if (match(V, m_Shl(m_One(), m_Value())))
return true;
if (match(V, m_LShr(m_SignBit(), m_Value())))
return true;
if (Depth++ == MaxDepth)
return false;
Value *X = nullptr, *Y = nullptr;
if (OrZero && (match(V, m_Shl(m_Value(X), m_Value())) ||
match(V, m_Shr(m_Value(X), m_Value()))))
return isKnownToBeAPowerOfTwo(X, true, Depth, Q, DL);
if (ZExtInst *ZI = dyn_cast<ZExtInst>(V))
return isKnownToBeAPowerOfTwo(ZI->getOperand(0), OrZero, Depth, Q, DL);
if (SelectInst *SI = dyn_cast<SelectInst>(V))
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)))) {
if (isKnownToBeAPowerOfTwo(X, true, Depth, Q, DL) ||
isKnownToBeAPowerOfTwo(Y, true, Depth, Q, DL))
return true;
if (match(X, m_Neg(m_Specific(Y))) || match(Y, m_Neg(m_Specific(X))))
return true;
return false;
}
if (match(V, m_Add(m_Value(X), m_Value(Y)))) {
OverflowingBinaryOperator *VOBO = cast<OverflowingBinaryOperator>(V);
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, 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, DL))
return true;
unsigned BitWidth = V->getType()->getScalarSizeInBits();
APInt LHSZeroBits(BitWidth, 0), LHSOneBits(BitWidth, 0);
computeKnownBits(X, LHSZeroBits, LHSOneBits, DL, Depth, Q);
APInt RHSZeroBits(BitWidth, 0), RHSOneBits(BitWidth, 0);
computeKnownBits(Y, RHSZeroBits, RHSOneBits, DL, Depth, Q);
if ((~(LHSZeroBits & RHSZeroBits)).isPowerOf2())
if (OrZero || RHSOneBits.getBoolValue() || LHSOneBits.getBoolValue())
return true;
}
}
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, DL);
}
return false;
}
static bool isGEPKnownNonNull(GEPOperator *GEP, const DataLayout &DL,
unsigned Depth, const Query &Q) {
if (!GEP->isInBounds() || GEP->getPointerAddressSpace() != 0)
return false;
assert(GEP->getType()->isPointerTy() && "We only support plain pointer GEP");
if (isKnownNonZero(GEP->getPointerOperand(), DL, Depth, Q))
return true;
for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP);
GTI != GTE; ++GTI) {
if (StructType *STy = dyn_cast<StructType>(*GTI)) {
ConstantInt *OpC = cast<ConstantInt>(GTI.getOperand());
unsigned ElementIdx = OpC->getZExtValue();
const StructLayout *SL = DL.getStructLayout(STy);
uint64_t ElementOffset = SL->getElementOffset(ElementIdx);
if (ElementOffset > 0)
return true;
continue;
}
if (DL.getTypeAllocSize(GTI.getIndexedType()) == 0)
continue;
if (ConstantInt *OpC = dyn_cast<ConstantInt>(GTI.getOperand())) {
if (!OpC->isZero())
return true;
continue;
}
if (Depth++ >= MaxDepth)
continue;
if (isKnownNonZero(GTI.getOperand(), DL, Depth, Q))
return true;
}
return false;
}
static bool rangeMetadataExcludesValue(MDNode* Ranges,
const APInt& Value) {
const unsigned NumRanges = Ranges->getNumOperands() / 2;
assert(NumRanges >= 1);
for (unsigned i = 0; i < NumRanges; ++i) {
ConstantInt *Lower =
mdconst::extract<ConstantInt>(Ranges->getOperand(2 * i + 0));
ConstantInt *Upper =
mdconst::extract<ConstantInt>(Ranges->getOperand(2 * i + 1));
ConstantRange Range(Lower->getValue(), Upper->getValue());
if (Range.contains(Value))
return false;
}
return true;
}
bool isKnownNonZero(Value *V, const DataLayout &DL, unsigned Depth,
const Query &Q) {
if (Constant *C = dyn_cast<Constant>(V)) {
if (C->isNullValue())
return false;
if (isa<ConstantInt>(C))
return true;
return false;
}
if (Instruction* I = dyn_cast<Instruction>(V)) {
if (MDNode *Ranges = I->getMetadata(LLVMContext::MD_range)) {
if (IntegerType* Ty = dyn_cast<IntegerType>(V->getType())) {
const APInt ZeroValue(Ty->getBitWidth(), 0);
if (rangeMetadataExcludesValue(Ranges, ZeroValue))
return true;
}
}
}
if (Depth++ >= MaxDepth)
return false;
if (V->getType()->isPointerTy()) {
if (isKnownNonNull(V))
return true;
if (GEPOperator *GEP = dyn_cast<GEPOperator>(V))
if (isGEPKnownNonNull(GEP, DL, Depth, Q))
return true;
}
unsigned BitWidth = getBitWidth(V->getType()->getScalarType(), DL);
Value *X = nullptr, *Y = nullptr;
if (match(V, m_Or(m_Value(X), m_Value(Y))))
return isKnownNonZero(X, DL, Depth, Q) || isKnownNonZero(Y, DL, Depth, Q);
if (isa<SExtInst>(V) || isa<ZExtInst>(V))
return isKnownNonZero(cast<Instruction>(V)->getOperand(0), DL, Depth, Q);
if (BitWidth && match(V, m_Shl(m_Value(X), m_Value(Y)))) {
OverflowingBinaryOperator *BO = cast<OverflowingBinaryOperator>(V);
if (BO->hasNoUnsignedWrap())
return isKnownNonZero(X, DL, Depth, Q);
APInt KnownZero(BitWidth, 0);
APInt KnownOne(BitWidth, 0);
computeKnownBits(X, KnownZero, KnownOne, DL, Depth, Q);
if (KnownOne[0])
return true;
}
else if (match(V, m_Shr(m_Value(X), m_Value(Y)))) {
PossiblyExactOperator *BO = cast<PossiblyExactOperator>(V);
if (BO->isExact())
return isKnownNonZero(X, DL, Depth, Q);
bool XKnownNonNegative, XKnownNegative;
ComputeSignBit(X, XKnownNonNegative, XKnownNegative, DL, Depth, Q);
if (XKnownNegative)
return true;
if (ConstantInt *Shift = dyn_cast<ConstantInt>(Y)) {
APInt KnownZero(BitWidth, 0);
APInt KnownOne(BitWidth, 0);
computeKnownBits(X, KnownZero, KnownOne, DL, Depth, Q);
auto ShiftVal = Shift->getLimitedValue(BitWidth - 1);
if (KnownOne.countLeadingZeros() < BitWidth - ShiftVal)
return true;
if (KnownZero.countTrailingOnes() >= ShiftVal)
return isKnownNonZero(X, DL, Depth, Q);
}
}
else if (match(V, m_Exact(m_IDiv(m_Value(X), m_Value())))) {
return isKnownNonZero(X, DL, Depth, Q);
}
else if (match(V, m_Add(m_Value(X), m_Value(Y)))) {
bool XKnownNonNegative, XKnownNegative;
bool YKnownNonNegative, YKnownNegative;
ComputeSignBit(X, XKnownNonNegative, XKnownNegative, DL, Depth, Q);
ComputeSignBit(Y, YKnownNonNegative, YKnownNegative, DL, Depth, Q);
if (XKnownNonNegative && YKnownNonNegative)
if (isKnownNonZero(X, DL, Depth, Q) || isKnownNonZero(Y, DL, Depth, Q))
return true;
if (BitWidth && XKnownNegative && YKnownNegative) {
APInt KnownZero(BitWidth, 0);
APInt KnownOne(BitWidth, 0);
APInt Mask = APInt::getSignedMaxValue(BitWidth);
computeKnownBits(X, KnownZero, KnownOne, DL, Depth, Q);
if ((KnownOne & Mask) != 0)
return true;
computeKnownBits(Y, KnownZero, KnownOne, DL, Depth, Q);
if ((KnownOne & Mask) != 0)
return true;
}
if (XKnownNonNegative &&
isKnownToBeAPowerOfTwo(Y, false, Depth, Q, DL))
return true;
if (YKnownNonNegative &&
isKnownToBeAPowerOfTwo(X, false, Depth, Q, DL))
return true;
}
else if (match(V, m_Mul(m_Value(X), m_Value(Y)))) {
OverflowingBinaryOperator *BO = cast<OverflowingBinaryOperator>(V);
if ((BO->hasNoSignedWrap() || BO->hasNoUnsignedWrap()) &&
isKnownNonZero(X, DL, Depth, Q) && isKnownNonZero(Y, DL, Depth, Q))
return true;
}
else if (SelectInst *SI = dyn_cast<SelectInst>(V)) {
if (isKnownNonZero(SI->getTrueValue(), DL, Depth, Q) &&
isKnownNonZero(SI->getFalseValue(), DL, Depth, Q))
return true;
}
else if (PHINode *PN = dyn_cast<PHINode>(V)) {
if (PN->getNumIncomingValues() == 2) {
Value *Start = PN->getIncomingValue(0);
Value *Induction = PN->getIncomingValue(1);
if (isa<ConstantInt>(Induction) && !isa<ConstantInt>(Start))
std::swap(Start, Induction);
if (ConstantInt *C = dyn_cast<ConstantInt>(Start)) {
if (!C->isZero() && !C->isNegative()) {
ConstantInt *X;
if ((match(Induction, m_NSWAdd(m_Specific(PN), m_ConstantInt(X))) ||
match(Induction, m_NUWAdd(m_Specific(PN), m_ConstantInt(X)))) &&
!X->isNegative())
return true;
}
}
}
}
if (!BitWidth) return false;
APInt KnownZero(BitWidth, 0);
APInt KnownOne(BitWidth, 0);
computeKnownBits(V, KnownZero, KnownOne, DL, Depth, Q);
return KnownOne != 0;
}
static bool isAddOfNonZero(Value *V1, Value *V2, const DataLayout &DL,
const Query &Q) {
BinaryOperator *BO = dyn_cast<BinaryOperator>(V1);
if (!BO || BO->getOpcode() != Instruction::Add)
return false;
Value *Op = nullptr;
if (V2 == BO->getOperand(0))
Op = BO->getOperand(1);
else if (V2 == BO->getOperand(1))
Op = BO->getOperand(0);
else
return false;
return isKnownNonZero(Op, DL, 0, Q);
}
static bool isKnownNonEqual(Value *V1, Value *V2, const DataLayout &DL,
const Query &Q) {
if (V1->getType()->isVectorTy() || V1 == V2)
return false;
if (V1->getType() != V2->getType())
return false;
if (isAddOfNonZero(V1, V2, DL, Q) || isAddOfNonZero(V2, V1, DL, Q))
return true;
if (IntegerType *Ty = dyn_cast<IntegerType>(V1->getType())) {
auto BitWidth = Ty->getBitWidth();
APInt KnownZero1(BitWidth, 0);
APInt KnownOne1(BitWidth, 0);
computeKnownBits(V1, KnownZero1, KnownOne1, DL, 0, Q);
APInt KnownZero2(BitWidth, 0);
APInt KnownOne2(BitWidth, 0);
computeKnownBits(V2, KnownZero2, KnownOne2, DL, 0, Q);
auto OppositeBits = (KnownZero1 & KnownOne2) | (KnownZero2 & KnownOne1);
if (OppositeBits.getBoolValue())
return true;
}
return false;
}
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, DL, Depth, Q);
return (KnownZero & Mask) == Mask;
}
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;
if (Depth == 6)
return 1;
Operator *U = dyn_cast<Operator>(V);
switch (Operator::getOpcode(V)) {
default: break;
case Instruction::SExt:
Tmp = TyBits - U->getOperand(0)->getType()->getScalarSizeInBits();
return ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q) + Tmp;
case Instruction::SDiv: {
const APInt *Denominator;
if (match(U->getOperand(1), m_APInt(Denominator))) {
if (!Denominator->isStrictlyPositive())
break;
unsigned NumBits = ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q);
return std::min(TyBits, NumBits + Denominator->logBase2());
}
break;
}
case Instruction::SRem: {
const APInt *Denominator;
if (match(U->getOperand(1), m_APInt(Denominator))) {
if (!Denominator->isStrictlyPositive())
break;
unsigned NumrBits =
ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q);
unsigned ResBits = TyBits - Denominator->ceilLogBase2();
return std::max(NumrBits, ResBits);
}
break;
}
case Instruction::AShr: {
Tmp = ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q);
const APInt *ShAmt;
if (match(U->getOperand(1), m_APInt(ShAmt))) {
Tmp += ShAmt->getZExtValue();
if (Tmp > TyBits) Tmp = TyBits;
}
return Tmp;
}
case Instruction::Shl: {
const APInt *ShAmt;
if (match(U->getOperand(1), m_APInt(ShAmt))) {
Tmp = ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q);
Tmp2 = ShAmt->getZExtValue();
if (Tmp2 >= TyBits || Tmp2 >= Tmp) break; return Tmp - Tmp2;
}
break;
}
case Instruction::And:
case Instruction::Or:
case Instruction::Xor: Tmp = ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q);
if (Tmp != 1) {
Tmp2 = ComputeNumSignBits(U->getOperand(1), DL, Depth + 1, Q);
FirstAnswer = std::min(Tmp, Tmp2);
}
break;
case Instruction::Select:
Tmp = ComputeNumSignBits(U->getOperand(1), DL, Depth + 1, Q);
if (Tmp == 1) return 1; Tmp2 = ComputeNumSignBits(U->getOperand(2), DL, Depth + 1, Q);
return std::min(Tmp, Tmp2);
case Instruction::Add:
Tmp = ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q);
if (Tmp == 1) return 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, DL, Depth + 1,
Q);
if ((KnownZero | APInt(TyBits, 1)).isAllOnesValue())
return TyBits;
if (KnownZero.isNegative())
return Tmp;
}
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), DL, Depth + 1, Q);
if (Tmp2 == 1) return 1;
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, DL, Depth + 1,
Q);
if ((KnownZero | APInt(TyBits, 1)).isAllOnesValue())
return TyBits;
if (KnownZero.isNegative())
return Tmp2;
}
Tmp = ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q);
if (Tmp == 1) return 1; return std::min(Tmp, Tmp2)-1;
case Instruction::PHI: {
PHINode *PN = cast<PHINode>(U);
unsigned NumIncomingValues = PN->getNumIncomingValues();
if (NumIncomingValues > 4) break;
if (NumIncomingValues == 0) break;
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), DL, Depth + 1, Q));
}
return Tmp;
}
case Instruction::Trunc:
break;
}
APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0);
APInt Mask;
computeKnownBits(V, KnownZero, KnownOne, DL, Depth, Q);
if (KnownZero.isNegative()) { Mask = KnownZero;
} else if (KnownOne.isNegative()) { Mask = KnownOne;
} else {
return FirstAnswer;
}
Mask = ~Mask;
Mask <<= Mask.getBitWidth()-TyBits;
return std::max(FirstAnswer, std::min(TyBits, Mask.countLeadingZeros()));
}
bool llvm::ComputeMultiple(Value *V, unsigned Base, Value *&Multiple,
bool LookThroughSExt, unsigned Depth) {
const unsigned MaxDepth = 6;
assert(V && "No Value?");
assert(Depth <= MaxDepth && "Limit Search Depth");
assert(V->getType()->isIntegerTy() && "Not integer or pointer type!");
Type *T = V->getType();
ConstantInt *CI = dyn_cast<ConstantInt>(V);
if (Base == 0)
return false;
if (Base == 1) {
Multiple = V;
return true;
}
ConstantExpr *CO = dyn_cast<ConstantExpr>(V);
Constant *BaseVal = ConstantInt::get(T, Base);
if (CO && CO == BaseVal) {
Multiple = ConstantInt::get(T, 1);
return true;
}
if (CI && CI->getZExtValue() % Base == 0) {
Multiple = ConstantInt::get(T, CI->getZExtValue() / Base);
return true;
}
if (Depth == MaxDepth) return false;
Operator *I = dyn_cast<Operator>(V);
if (!I) return false;
switch (I->getOpcode()) {
default: break;
case Instruction::SExt:
if (!LookThroughSExt) return false;
case Instruction::ZExt:
return ComputeMultiple(I->getOperand(0), Base, Multiple,
LookThroughSExt, Depth+1);
case Instruction::Shl:
case Instruction::Mul: {
Value *Op0 = I->getOperand(0);
Value *Op1 = I->getOperand(1);
if (I->getOpcode() == Instruction::Shl) {
ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1);
if (!Op1CI) return false;
APInt Op1Int = Op1CI->getValue();
uint64_t BitToSet = Op1Int.getLimitedValue(Op1Int.getBitWidth() - 1);
APInt API(Op1Int.getBitWidth(), 0);
API.setBit(BitToSet);
Op1 = ConstantInt::get(V->getContext(), API);
}
Value *Mul0 = nullptr;
if (ComputeMultiple(Op0, Base, Mul0, LookThroughSExt, Depth+1)) {
if (Constant *Op1C = dyn_cast<Constant>(Op1))
if (Constant *MulC = dyn_cast<Constant>(Mul0)) {
if (Op1C->getType()->getPrimitiveSizeInBits() <
MulC->getType()->getPrimitiveSizeInBits())
Op1C = ConstantExpr::getZExt(Op1C, MulC->getType());
if (Op1C->getType()->getPrimitiveSizeInBits() >
MulC->getType()->getPrimitiveSizeInBits())
MulC = ConstantExpr::getZExt(MulC, Op1C->getType());
Multiple = ConstantExpr::getMul(MulC, Op1C);
return true;
}
if (ConstantInt *Mul0CI = dyn_cast<ConstantInt>(Mul0))
if (Mul0CI->getValue() == 1) {
Multiple = Op1;
return true;
}
}
Value *Mul1 = nullptr;
if (ComputeMultiple(Op1, Base, Mul1, LookThroughSExt, Depth+1)) {
if (Constant *Op0C = dyn_cast<Constant>(Op0))
if (Constant *MulC = dyn_cast<Constant>(Mul1)) {
if (Op0C->getType()->getPrimitiveSizeInBits() <
MulC->getType()->getPrimitiveSizeInBits())
Op0C = ConstantExpr::getZExt(Op0C, MulC->getType());
if (Op0C->getType()->getPrimitiveSizeInBits() >
MulC->getType()->getPrimitiveSizeInBits())
MulC = ConstantExpr::getZExt(MulC, Op0C->getType());
Multiple = ConstantExpr::getMul(MulC, Op0C);
return true;
}
if (ConstantInt *Mul1CI = dyn_cast<ConstantInt>(Mul1))
if (Mul1CI->getValue() == 1) {
Multiple = Op0;
return true;
}
}
}
}
return false;
}
bool llvm::CannotBeNegativeZero(const Value *V, unsigned Depth) {
if (const ConstantFP *CFP = dyn_cast<ConstantFP>(V))
return !CFP->getValueAPF().isNegZero();
if (Depth == 6)
return false;
const Operator *I = dyn_cast<Operator>(V);
if (!I) return false;
if (const FPMathOperator *FPO = dyn_cast<FPMathOperator>(I))
if (FPO->hasNoSignedZeros())
return true;
if (I->getOpcode() == Instruction::FAdd)
if (ConstantFP *CFP = dyn_cast<ConstantFP>(I->getOperand(1)))
if (CFP->isNullValue())
return true;
if (isa<SIToFPInst>(I) || isa<UIToFPInst>(I))
return true;
if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
if (II->getIntrinsicID() == Intrinsic::sqrt)
return CannotBeNegativeZero(II->getArgOperand(0), Depth+1);
if (const CallInst *CI = dyn_cast<CallInst>(I))
if (const Function *F = CI->getCalledFunction()) {
if (F->isDeclaration()) {
if (F->getName() == "abs") return true;
if (F->getName() == "fabs") return true;
if (F->getName() == "fabsf") return true;
if (F->getName() == "fabsl") return true;
if (F->getName() == "sqrt" || F->getName() == "sqrtf" ||
F->getName() == "sqrtl")
return CannotBeNegativeZero(CI->getArgOperand(0), Depth+1);
}
}
return false;
}
bool llvm::CannotBeOrderedLessThanZero(const Value *V, unsigned Depth) {
if (const ConstantFP *CFP = dyn_cast<ConstantFP>(V))
return !CFP->getValueAPF().isNegative() || CFP->getValueAPF().isZero();
if (Depth == 6)
return false;
const Operator *I = dyn_cast<Operator>(V);
if (!I) return false;
switch (I->getOpcode()) {
default: break;
case Instruction::FMul:
if (I->getOperand(0) == I->getOperand(1))
return true;
case Instruction::FAdd:
case Instruction::FDiv:
case Instruction::FRem:
return CannotBeOrderedLessThanZero(I->getOperand(0), Depth+1) &&
CannotBeOrderedLessThanZero(I->getOperand(1), Depth+1);
case Instruction::FPExt:
case Instruction::FPTrunc:
return CannotBeOrderedLessThanZero(I->getOperand(0), Depth+1);
case Instruction::Call:
if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
switch (II->getIntrinsicID()) {
default: break;
case Intrinsic::exp:
case Intrinsic::exp2:
case Intrinsic::fabs:
case Intrinsic::sqrt:
return true;
case Intrinsic::powi:
if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
if (CI->getBitWidth() <= 64 && CI->getSExtValue() % 2u == 0)
return true;
}
return CannotBeOrderedLessThanZero(I->getOperand(0), Depth+1);
case Intrinsic::fma:
case Intrinsic::fmuladd:
return I->getOperand(0) == I->getOperand(1) &&
CannotBeOrderedLessThanZero(I->getOperand(2), Depth+1);
}
break;
}
return false;
}
Value *llvm::isBytewiseValue(Value *V) {
if (V->getType()->isIntegerTy(8)) return V;
if (Constant *C = dyn_cast<Constant>(V))
if (C->isNullValue())
return Constant::getNullValue(Type::getInt8Ty(V->getContext()));
if (ConstantFP *CFP = dyn_cast<ConstantFP>(V)) {
if (CFP->getType()->isFloatTy())
V = ConstantExpr::getBitCast(CFP, Type::getInt32Ty(V->getContext()));
if (CFP->getType()->isDoubleTy())
V = ConstantExpr::getBitCast(CFP, Type::getInt64Ty(V->getContext()));
}
if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
if (CI->getBitWidth() % 8 == 0) {
assert(CI->getBitWidth() > 8 && "8 bits should be handled above!");
if (!CI->getValue().isSplat(8))
return nullptr;
return ConstantInt::get(V->getContext(), CI->getValue().trunc(8));
}
}
if (ConstantDataSequential *CA = dyn_cast<ConstantDataSequential>(V)) {
Value *Elt = CA->getElementAsConstant(0);
Value *Val = isBytewiseValue(Elt);
if (!Val)
return nullptr;
for (unsigned I = 1, E = CA->getNumElements(); I != E; ++I)
if (CA->getElementAsConstant(I) != Elt)
return nullptr;
return Val;
}
return nullptr;
}
static Value *BuildSubAggregate(Value *From, Value* To, Type *IndexedType,
SmallVectorImpl<unsigned> &Idxs,
unsigned IdxSkip,
Instruction *InsertBefore) {
llvm::StructType *STy = dyn_cast<llvm::StructType>(IndexedType);
if (STy) {
Value *OrigTo = To;
for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
Idxs.push_back(i);
Value *PrevTo = To;
To = BuildSubAggregate(From, To, STy->getElementType(i), Idxs, IdxSkip,
InsertBefore);
Idxs.pop_back();
if (!To) {
while (PrevTo != OrigTo) {
InsertValueInst* Del = cast<InsertValueInst>(PrevTo);
PrevTo = Del->getAggregateOperand();
Del->eraseFromParent();
}
break;
}
}
if (To)
return To;
}
Value *V = FindInsertedValue(From, Idxs);
if (!V)
return nullptr;
return llvm::InsertValueInst::Create(To, V, makeArrayRef(Idxs).slice(IdxSkip),
"tmp", InsertBefore);
}
static Value *BuildSubAggregate(Value *From, ArrayRef<unsigned> idx_range,
Instruction *InsertBefore) {
assert(InsertBefore && "Must have someplace to insert!");
Type *IndexedType = ExtractValueInst::getIndexedType(From->getType(),
idx_range);
Value *To = UndefValue::get(IndexedType);
SmallVector<unsigned, 10> Idxs(idx_range.begin(), idx_range.end());
unsigned IdxSkip = Idxs.size();
return BuildSubAggregate(From, To, IndexedType, Idxs, IdxSkip, InsertBefore);
}
Value *llvm::FindInsertedValue(Value *V, ArrayRef<unsigned> idx_range,
Instruction *InsertBefore) {
if (idx_range.empty())
return V;
assert((V->getType()->isStructTy() || V->getType()->isArrayTy()) &&
"Not looking at a struct or array?");
assert(ExtractValueInst::getIndexedType(V->getType(), idx_range) &&
"Invalid indices for type?");
if (Constant *C = dyn_cast<Constant>(V)) {
C = C->getAggregateElement(idx_range[0]);
if (!C) return nullptr;
return FindInsertedValue(C, idx_range.slice(1), InsertBefore);
}
if (InsertValueInst *I = dyn_cast<InsertValueInst>(V)) {
const unsigned *req_idx = idx_range.begin();
for (const unsigned *i = I->idx_begin(), *e = I->idx_end();
i != e; ++i, ++req_idx) {
if (req_idx == idx_range.end()) {
if (!InsertBefore)
return nullptr;
return BuildSubAggregate(V, makeArrayRef(idx_range.begin(), req_idx),
InsertBefore);
}
if (*req_idx != *i)
return FindInsertedValue(I->getAggregateOperand(), idx_range,
InsertBefore);
}
return FindInsertedValue(I->getInsertedValueOperand(),
makeArrayRef(req_idx, idx_range.end()),
InsertBefore);
}
if (ExtractValueInst *I = dyn_cast<ExtractValueInst>(V)) {
unsigned size = I->getNumIndices() + idx_range.size();
SmallVector<unsigned, 5> Idxs;
Idxs.reserve(size);
Idxs.append(I->idx_begin(), I->idx_end());
Idxs.append(idx_range.begin(), idx_range.end());
assert(Idxs.size() == size
&& "Number of indices added not correct?");
return FindInsertedValue(I->getAggregateOperand(), Idxs, InsertBefore);
}
return nullptr;
}
Value *llvm::GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset,
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)) {
APInt GEPOffset(BitWidth, 0);
if (!GEP->accumulateConstantOffset(DL, GEPOffset))
break;
ByteOffset += GEPOffset;
Ptr = GEP->getPointerOperand();
} else if (Operator::getOpcode(Ptr) == Instruction::BitCast ||
Operator::getOpcode(Ptr) == Instruction::AddrSpaceCast) {
Ptr = cast<Operator>(Ptr)->getOperand(0);
} else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(Ptr)) {
if (GA->mayBeOverridden())
break;
Ptr = GA->getAliasee();
} else {
break;
}
}
Offset = ByteOffset.getSExtValue();
return Ptr;
}
bool llvm::getConstantStringInfo(const Value *V, StringRef &Str,
uint64_t Offset, bool TrimAtNul) {
assert(V);
V = V->stripPointerCasts();
if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
if (GEP->getNumOperands() != 3)
return false;
PointerType *PT = cast<PointerType>(GEP->getOperand(0)->getType());
ArrayType *AT = dyn_cast<ArrayType>(PT->getElementType());
if (!AT || !AT->getElementType()->isIntegerTy(8))
return false;
const ConstantInt *FirstIdx = dyn_cast<ConstantInt>(GEP->getOperand(1));
if (!FirstIdx || !FirstIdx->isZero())
return false;
uint64_t StartIdx = 0;
if (const ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(2)))
StartIdx = CI->getZExtValue();
else
return false;
return getConstantStringInfo(GEP->getOperand(0), Str, StartIdx + Offset,
TrimAtNul);
}
const GlobalVariable *GV = dyn_cast<GlobalVariable>(V);
if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer())
return false;
if (GV->getInitializer()->isNullValue()) {
Str = "";
return true;
}
const ConstantDataArray *Array =
dyn_cast<ConstantDataArray>(GV->getInitializer());
if (!Array || !Array->isString())
return false;
uint64_t NumElts = Array->getType()->getArrayNumElements();
Str = Array->getAsString();
if (Offset > NumElts)
return false;
Str = Str.substr(Offset);
if (TrimAtNul) {
Str = Str.substr(0, Str.find('\0'));
}
return true;
}
static uint64_t GetStringLengthH(Value *V, SmallPtrSetImpl<PHINode*> &PHIs) {
V = V->stripPointerCasts();
if (PHINode *PN = dyn_cast<PHINode>(V)) {
if (!PHIs.insert(PN).second)
return ~0ULL;
uint64_t LenSoFar = ~0ULL;
for (Value *IncValue : PN->incoming_values()) {
uint64_t Len = GetStringLengthH(IncValue, PHIs);
if (Len == 0) return 0;
if (Len == ~0ULL) continue;
if (Len != LenSoFar && LenSoFar != ~0ULL)
return 0; LenSoFar = Len;
}
return LenSoFar;
}
if (SelectInst *SI = dyn_cast<SelectInst>(V)) {
uint64_t Len1 = GetStringLengthH(SI->getTrueValue(), PHIs);
if (Len1 == 0) return 0;
uint64_t Len2 = GetStringLengthH(SI->getFalseValue(), PHIs);
if (Len2 == 0) return 0;
if (Len1 == ~0ULL) return Len2;
if (Len2 == ~0ULL) return Len1;
if (Len1 != Len2) return 0;
return Len1;
}
StringRef StrData;
if (!getConstantStringInfo(V, StrData))
return 0;
return StrData.size()+1;
}
uint64_t llvm::GetStringLength(Value *V) {
if (!V->getType()->isPointerTy()) return 0;
SmallPtrSet<PHINode*, 32> PHIs;
uint64_t Len = GetStringLengthH(V, PHIs);
return Len == ~0ULL ? 1 : Len;
}
static bool isSameUnderlyingObjectInLoop(PHINode *PN, LoopInfo *LI) {
Loop *L = LI->getLoopFor(PN->getParent());
if (PN->getNumIncomingValues() != 2)
return true;
auto *PrevValue = dyn_cast<Instruction>(PN->getIncomingValue(0));
if (!PrevValue || LI->getLoopFor(PrevValue->getParent()) != L)
PrevValue = dyn_cast<Instruction>(PN->getIncomingValue(1));
if (!PrevValue || LI->getLoopFor(PrevValue->getParent()) != L)
return true;
if (auto *Load = dyn_cast<LoadInst>(PrevValue))
if (!L->isLoopInvariant(Load->getPointerOperand()))
return false;
return true;
}
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) {
if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
V = GEP->getPointerOperand();
} else if (Operator::getOpcode(V) == Instruction::BitCast ||
Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
V = cast<Operator>(V)->getOperand(0);
} else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
if (GA->mayBeOverridden())
return V;
V = GA->getAliasee();
} else {
if (Instruction *I = dyn_cast<Instruction>(V))
if (Value *Simplified = SimplifyInstruction(I, DL, nullptr)) {
V = Simplified;
continue;
}
return V;
}
assert(V->getType()->isPointerTy() && "Unexpected operand type!");
}
return V;
}
void llvm::GetUnderlyingObjects(Value *V, SmallVectorImpl<Value *> &Objects,
const DataLayout &DL, LoopInfo *LI,
unsigned MaxLookup) {
SmallPtrSet<Value *, 4> Visited;
SmallVector<Value *, 4> Worklist;
Worklist.push_back(V);
do {
Value *P = Worklist.pop_back_val();
P = GetUnderlyingObject(P, DL, MaxLookup);
if (!Visited.insert(P).second)
continue;
if (SelectInst *SI = dyn_cast<SelectInst>(P)) {
Worklist.push_back(SI->getTrueValue());
Worklist.push_back(SI->getFalseValue());
continue;
}
if (PHINode *PN = dyn_cast<PHINode>(P)) {
if (!LI || !LI->isLoopHeader(PN->getParent()) ||
isSameUnderlyingObjectInLoop(PN, LI))
for (Value *IncValue : PN->incoming_values())
Worklist.push_back(IncValue);
continue;
}
Objects.push_back(P);
} while (!Worklist.empty());
}
bool llvm::onlyUsedByLifetimeMarkers(const Value *V) {
for (const User *U : V->users()) {
const IntrinsicInst *II = dyn_cast<IntrinsicInst>(U);
if (!II) return false;
if (II->getIntrinsicID() != Intrinsic::lifetime_start &&
II->getIntrinsicID() != Intrinsic::lifetime_end)
return false;
}
return true;
}
static bool isDereferenceableFromAttribute(const Value *BV, APInt Offset,
Type *Ty, const DataLayout &DL,
const Instruction *CtxI,
const DominatorTree *DT,
const TargetLibraryInfo *TLI) {
assert(Offset.isNonNegative() && "offset can't be negative");
assert(Ty->isSized() && "must be sized");
APInt DerefBytes(Offset.getBitWidth(), 0);
bool CheckForNonNull = false;
if (const Argument *A = dyn_cast<Argument>(BV)) {
DerefBytes = A->getDereferenceableBytes();
if (!DerefBytes.getBoolValue()) {
DerefBytes = A->getDereferenceableOrNullBytes();
CheckForNonNull = true;
}
} else if (auto CS = ImmutableCallSite(BV)) {
DerefBytes = CS.getDereferenceableBytes(0);
if (!DerefBytes.getBoolValue()) {
DerefBytes = CS.getDereferenceableOrNullBytes(0);
CheckForNonNull = true;
}
} else if (const LoadInst *LI = dyn_cast<LoadInst>(BV)) {
if (MDNode *MD = LI->getMetadata(LLVMContext::MD_dereferenceable)) {
ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
DerefBytes = CI->getLimitedValue();
}
if (!DerefBytes.getBoolValue()) {
if (MDNode *MD =
LI->getMetadata(LLVMContext::MD_dereferenceable_or_null)) {
ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
DerefBytes = CI->getLimitedValue();
}
CheckForNonNull = true;
}
}
if (DerefBytes.getBoolValue())
if (DerefBytes.uge(Offset + DL.getTypeStoreSize(Ty)))
if (!CheckForNonNull || isKnownNonNullAt(BV, CtxI, DT, TLI))
return true;
return false;
}
static bool isDereferenceableFromAttribute(const Value *V, const DataLayout &DL,
const Instruction *CtxI,
const DominatorTree *DT,
const TargetLibraryInfo *TLI) {
Type *VTy = V->getType();
Type *Ty = VTy->getPointerElementType();
if (!Ty->isSized())
return false;
APInt Offset(DL.getTypeStoreSizeInBits(VTy), 0);
return isDereferenceableFromAttribute(V, Offset, Ty, DL, CtxI, DT, TLI);
}
static bool isAligned(const Value *Base, APInt Offset, unsigned Align,
const DataLayout &DL) {
APInt BaseAlign(Offset.getBitWidth(), getAlignment(Base, DL));
if (!BaseAlign) {
Type *Ty = Base->getType()->getPointerElementType();
if (!Ty->isSized())
return false;
BaseAlign = DL.getABITypeAlignment(Ty);
}
APInt Alignment(Offset.getBitWidth(), Align);
assert(Alignment.isPowerOf2() && "must be a power of 2!");
return BaseAlign.uge(Alignment) && !(Offset & (Alignment-1));
}
static bool isAligned(const Value *Base, unsigned Align, const DataLayout &DL) {
Type *Ty = Base->getType();
assert(Ty->isSized() && "must be sized");
APInt Offset(DL.getTypeStoreSizeInBits(Ty), 0);
return isAligned(Base, Offset, Align, DL);
}
static bool isDereferenceableAndAlignedPointer(
const Value *V, unsigned Align, const DataLayout &DL,
const Instruction *CtxI, const DominatorTree *DT,
const TargetLibraryInfo *TLI, SmallPtrSetImpl<const Value *> &Visited) {
if (isa<AllocaInst>(V))
return isAligned(V, Align, DL);
if (const BitCastOperator *BC = dyn_cast<BitCastOperator>(V)) {
Type *STy = BC->getSrcTy()->getPointerElementType(),
*DTy = BC->getDestTy()->getPointerElementType();
if (STy->isSized() && DTy->isSized() &&
(DL.getTypeStoreSize(STy) >= DL.getTypeStoreSize(DTy)) &&
(DL.getABITypeAlignment(STy) >= DL.getABITypeAlignment(DTy)))
return isDereferenceableAndAlignedPointer(BC->getOperand(0), Align, DL,
CtxI, DT, TLI, Visited);
}
if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
if (!GV->hasExternalWeakLinkage())
return isAligned(V, Align, DL);
if (const Argument *A = dyn_cast<Argument>(V))
if (A->hasByValAttr())
return isAligned(V, Align, DL);
if (isDereferenceableFromAttribute(V, DL, CtxI, DT, TLI))
return isAligned(V, Align, DL);
if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
Type *VTy = GEP->getType();
Type *Ty = VTy->getPointerElementType();
const Value *Base = GEP->getPointerOperand();
if (!Visited.insert(Base).second)
return false;
if (!isDereferenceableAndAlignedPointer(Base, Align, DL, CtxI, DT, TLI,
Visited))
return false;
APInt Offset(DL.getPointerTypeSizeInBits(VTy), 0);
if (!GEP->accumulateConstantOffset(DL, Offset))
return false;
uint64_t LoadSize = DL.getTypeStoreSize(Ty);
Type *BaseType = Base->getType()->getPointerElementType();
assert(isPowerOf2_32(Align) && "must be a power of 2!");
return (Offset + LoadSize).ule(DL.getTypeAllocSize(BaseType)) &&
!(Offset & APInt(Offset.getBitWidth(), Align-1));
}
if (const IntrinsicInst *I = dyn_cast<IntrinsicInst>(V))
if (I->getIntrinsicID() == Intrinsic::experimental_gc_relocate) {
GCRelocateOperands RelocateInst(I);
return isDereferenceableAndAlignedPointer(
RelocateInst.getDerivedPtr(), Align, DL, CtxI, DT, TLI, Visited);
}
if (const AddrSpaceCastInst *ASC = dyn_cast<AddrSpaceCastInst>(V))
return isDereferenceableAndAlignedPointer(ASC->getOperand(0), Align, DL,
CtxI, DT, TLI, Visited);
return false;
}
bool llvm::isDereferenceableAndAlignedPointer(const Value *V, unsigned Align,
const DataLayout &DL,
const Instruction *CtxI,
const DominatorTree *DT,
const TargetLibraryInfo *TLI) {
Type *VTy = V->getType();
Type *Ty = VTy->getPointerElementType();
if (Align == 0)
Align = DL.getABITypeAlignment(Ty);
if (Ty->isSized()) {
APInt Offset(DL.getTypeStoreSizeInBits(VTy), 0);
const Value *BV = V->stripAndAccumulateInBoundsConstantOffsets(DL, Offset);
if (Offset.isNonNegative())
if (isDereferenceableFromAttribute(BV, Offset, Ty, DL, CtxI, DT, TLI) &&
isAligned(BV, Offset, Align, DL))
return true;
}
SmallPtrSet<const Value *, 32> Visited;
return ::isDereferenceableAndAlignedPointer(V, Align, DL, CtxI, DT, TLI,
Visited);
}
bool llvm::isDereferenceablePointer(const Value *V, const DataLayout &DL,
const Instruction *CtxI,
const DominatorTree *DT,
const TargetLibraryInfo *TLI) {
return isDereferenceableAndAlignedPointer(V, 1, DL, CtxI, DT, TLI);
}
bool llvm::isSafeToSpeculativelyExecute(const Value *V,
const Instruction *CtxI,
const DominatorTree *DT,
const TargetLibraryInfo *TLI) {
const Operator *Inst = dyn_cast<Operator>(V);
if (!Inst)
return false;
for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i)
if (Constant *C = dyn_cast<Constant>(Inst->getOperand(i)))
if (C->canTrap())
return false;
switch (Inst->getOpcode()) {
default:
return true;
case Instruction::UDiv:
case Instruction::URem: {
const APInt *V;
if (match(Inst->getOperand(1), m_APInt(V)))
return *V != 0;
return false;
}
case Instruction::SDiv:
case Instruction::SRem: {
const APInt *Numerator, *Denominator;
if (!match(Inst->getOperand(1), m_APInt(Denominator)))
return false;
if (*Denominator == 0)
return false;
if (*Denominator != -1)
return true;
if (match(Inst->getOperand(0), m_APInt(Numerator)))
return !Numerator->isMinSignedValue();
return false;
}
case Instruction::Load: {
const LoadInst *LI = cast<LoadInst>(Inst);
if (!LI->isUnordered() ||
LI->getParent()->getParent()->hasFnAttribute(
Attribute::SanitizeThread) ||
LI->getParent()->getParent()->hasFnAttribute(
Attribute::SanitizeAddress))
return false;
const DataLayout &DL = LI->getModule()->getDataLayout();
return isDereferenceableAndAlignedPointer(
LI->getPointerOperand(), LI->getAlignment(), DL, CtxI, DT, TLI);
}
case Instruction::Call: {
if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
switch (II->getIntrinsicID()) {
case Intrinsic::dbg_declare:
case Intrinsic::dbg_value:
return true;
case Intrinsic::bswap:
case Intrinsic::ctlz:
case Intrinsic::ctpop:
case Intrinsic::cttz:
case Intrinsic::objectsize:
case Intrinsic::sadd_with_overflow:
case Intrinsic::smul_with_overflow:
case Intrinsic::ssub_with_overflow:
case Intrinsic::uadd_with_overflow:
case Intrinsic::umul_with_overflow:
case Intrinsic::usub_with_overflow:
return true;
case Intrinsic::sqrt:
case Intrinsic::fma:
case Intrinsic::fmuladd:
case Intrinsic::fabs:
case Intrinsic::minnum:
case Intrinsic::maxnum:
return true;
default: break;
}
}
return false; }
case Instruction::VAArg:
case Instruction::Alloca:
case Instruction::Invoke:
case Instruction::PHI:
case Instruction::Store:
case Instruction::Ret:
case Instruction::Br:
case Instruction::IndirectBr:
case Instruction::Switch:
case Instruction::Unreachable:
case Instruction::Fence:
case Instruction::AtomicRMW:
case Instruction::AtomicCmpXchg:
case Instruction::LandingPad:
case Instruction::Resume:
case Instruction::CatchPad:
case Instruction::CatchEndPad:
case Instruction::CatchRet:
case Instruction::CleanupPad:
case Instruction::CleanupEndPad:
case Instruction::CleanupRet:
case Instruction::TerminatePad:
return false; }
}
bool llvm::mayBeMemoryDependent(const Instruction &I) {
return I.mayReadOrWriteMemory() || !isSafeToSpeculativelyExecute(&I);
}
bool llvm::isKnownNonNull(const Value *V, const TargetLibraryInfo *TLI) {
assert(V->getType()->isPointerTy() && "V must be pointer type");
if (isa<AllocaInst>(V)) return true;
if (const Argument *A = dyn_cast<Argument>(V))
return A->hasByValOrInAllocaAttr() || A->hasNonNullAttr();
if (const GlobalValue *GV = dyn_cast<GlobalValue>(V))
return !GV->hasExternalWeakLinkage() &&
GV->getType()->getAddressSpace() == 0;
if (const LoadInst *LI = dyn_cast<LoadInst>(V))
return LI->getMetadata(LLVMContext::MD_nonnull);
if (auto CS = ImmutableCallSite(V))
if (CS.isReturnNonNull())
return true;
if (isOperatorNewLikeFn(V, TLI, true))
return true;
return false;
}
static bool isKnownNonNullFromDominatingCondition(const Value *V,
const Instruction *CtxI,
const DominatorTree *DT) {
assert(V->getType()->isPointerTy() && "V must be pointer type");
unsigned NumUsesExplored = 0;
for (auto U : V->users()) {
if (NumUsesExplored >= DomConditionsMaxUses)
break;
NumUsesExplored++;
const ICmpInst *Cmp = dyn_cast<ICmpInst>(U);
if (!Cmp)
continue;
if (DomConditionsSingleCmpUse && !Cmp->hasOneUse())
continue;
for (auto *CmpU : Cmp->users()) {
const BranchInst *BI = dyn_cast<BranchInst>(CmpU);
if (!BI)
continue;
assert(BI->isConditional() && "uses a comparison!");
BasicBlock *NonNullSuccessor = nullptr;
CmpInst::Predicate Pred;
if (match(const_cast<ICmpInst*>(Cmp),
m_c_ICmp(Pred, m_Specific(V), m_Zero()))) {
if (Pred == ICmpInst::ICMP_EQ)
NonNullSuccessor = BI->getSuccessor(1);
else if (Pred == ICmpInst::ICMP_NE)
NonNullSuccessor = BI->getSuccessor(0);
}
if (NonNullSuccessor) {
BasicBlockEdge Edge(BI->getParent(), NonNullSuccessor);
if (Edge.isSingleEdge() && DT->dominates(Edge, CtxI->getParent()))
return true;
}
}
}
return false;
}
bool llvm::isKnownNonNullAt(const Value *V, const Instruction *CtxI,
const DominatorTree *DT, const TargetLibraryInfo *TLI) {
if (isKnownNonNull(V, TLI))
return true;
return CtxI ? ::isKnownNonNullFromDominatingCondition(V, CtxI, DT) : false;
}
OverflowResult llvm::computeOverflowForUnsignedMul(Value *LHS, Value *RHS,
const DataLayout &DL,
AssumptionCache *AC,
const Instruction *CxtI,
const DominatorTree *DT) {
unsigned BitWidth = LHS->getType()->getScalarSizeInBits();
APInt LHSKnownZero(BitWidth, 0);
APInt LHSKnownOne(BitWidth, 0);
APInt RHSKnownZero(BitWidth, 0);
APInt RHSKnownOne(BitWidth, 0);
computeKnownBits(LHS, LHSKnownZero, LHSKnownOne, DL, 0, AC, CxtI,
DT);
computeKnownBits(RHS, RHSKnownZero, RHSKnownOne, DL, 0, AC, CxtI,
DT);
unsigned ZeroBits = LHSKnownZero.countLeadingOnes() +
RHSKnownZero.countLeadingOnes();
if (ZeroBits >= BitWidth)
return OverflowResult::NeverOverflows;
APInt LHSMax = ~LHSKnownZero;
APInt RHSMax = ~RHSKnownZero;
bool MaxOverflow;
LHSMax.umul_ov(RHSMax, MaxOverflow);
if (!MaxOverflow)
return OverflowResult::NeverOverflows;
bool MinOverflow;
LHSKnownOne.umul_ov(RHSKnownOne, MinOverflow);
if (MinOverflow)
return OverflowResult::AlwaysOverflows;
return OverflowResult::MayOverflow;
}
OverflowResult llvm::computeOverflowForUnsignedAdd(Value *LHS, Value *RHS,
const DataLayout &DL,
AssumptionCache *AC,
const Instruction *CxtI,
const DominatorTree *DT) {
bool LHSKnownNonNegative, LHSKnownNegative;
ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, DL, 0,
AC, CxtI, DT);
if (LHSKnownNonNegative || LHSKnownNegative) {
bool RHSKnownNonNegative, RHSKnownNegative;
ComputeSignBit(RHS, RHSKnownNonNegative, RHSKnownNegative, DL, 0,
AC, CxtI, DT);
if (LHSKnownNegative && RHSKnownNegative) {
return OverflowResult::AlwaysOverflows;
}
if (LHSKnownNonNegative && RHSKnownNonNegative) {
return OverflowResult::NeverOverflows;
}
}
return OverflowResult::MayOverflow;
}
static OverflowResult computeOverflowForSignedAdd(
Value *LHS, Value *RHS, AddOperator *Add, const DataLayout &DL,
AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT) {
if (Add && Add->hasNoSignedWrap()) {
return OverflowResult::NeverOverflows;
}
bool LHSKnownNonNegative, LHSKnownNegative;
bool RHSKnownNonNegative, RHSKnownNegative;
ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, DL, 0,
AC, CxtI, DT);
ComputeSignBit(RHS, RHSKnownNonNegative, RHSKnownNegative, DL, 0,
AC, CxtI, DT);
if ((LHSKnownNonNegative && RHSKnownNegative) ||
(LHSKnownNegative && RHSKnownNonNegative)) {
return OverflowResult::NeverOverflows;
}
if (!Add)
return OverflowResult::MayOverflow;
bool LHSOrRHSKnownNonNegative =
(LHSKnownNonNegative || RHSKnownNonNegative);
bool LHSOrRHSKnownNegative = (LHSKnownNegative || RHSKnownNegative);
if (LHSOrRHSKnownNonNegative || LHSOrRHSKnownNegative) {
bool AddKnownNonNegative, AddKnownNegative;
ComputeSignBit(Add, AddKnownNonNegative, AddKnownNegative, DL,
0, AC, CxtI, DT);
if ((AddKnownNonNegative && LHSOrRHSKnownNonNegative) ||
(AddKnownNegative && LHSOrRHSKnownNegative)) {
return OverflowResult::NeverOverflows;
}
}
return OverflowResult::MayOverflow;
}
OverflowResult llvm::computeOverflowForSignedAdd(AddOperator *Add,
const DataLayout &DL,
AssumptionCache *AC,
const Instruction *CxtI,
const DominatorTree *DT) {
return ::computeOverflowForSignedAdd(Add->getOperand(0), Add->getOperand(1),
Add, DL, AC, CxtI, DT);
}
OverflowResult llvm::computeOverflowForSignedAdd(Value *LHS, Value *RHS,
const DataLayout &DL,
AssumptionCache *AC,
const Instruction *CxtI,
const DominatorTree *DT) {
return ::computeOverflowForSignedAdd(LHS, RHS, nullptr, DL, AC, CxtI, DT);
}
bool llvm::isGuaranteedToTransferExecutionToSuccessor(const Instruction *I) {
return !I->isAtomic() && !isa<CallInst>(I) && !isa<InvokeInst>(I) && !isa<ResumeInst>(I) && !isa<ReturnInst>(I); }
bool llvm::isGuaranteedToExecuteForEveryIteration(const Instruction *I,
const Loop *L) {
if (I->getParent() != L->getHeader()) return false;
for (const Instruction &LI : *L->getHeader()) {
if (&LI == I) return true;
if (!isGuaranteedToTransferExecutionToSuccessor(&LI)) return false;
}
llvm_unreachable("Instruction not contained in its own parent basic block.");
}
bool llvm::propagatesFullPoison(const Instruction *I) {
switch (I->getOpcode()) {
case Instruction::Add:
case Instruction::Sub:
case Instruction::Xor:
case Instruction::Trunc:
case Instruction::BitCast:
case Instruction::AddrSpaceCast:
return true;
case Instruction::AShr:
case Instruction::SExt:
return true;
case Instruction::Shl: {
auto *OBO = cast<OverflowingBinaryOperator>(I);
return OBO->hasNoUnsignedWrap() || OBO->hasNoSignedWrap();
}
case Instruction::Mul: {
auto *OBO = cast<OverflowingBinaryOperator>(I);
if (OBO->hasNoUnsignedWrap() || OBO->hasNoSignedWrap()) {
for (Value *V : OBO->operands()) {
if (auto *CI = dyn_cast<ConstantInt>(V)) {
return !CI->isZero();
}
}
}
return false;
}
case Instruction::GetElementPtr:
return cast<GEPOperator>(I)->isInBounds();
default:
return false;
}
}
const Value *llvm::getGuaranteedNonFullPoisonOp(const Instruction *I) {
switch (I->getOpcode()) {
case Instruction::Store:
return cast<StoreInst>(I)->getPointerOperand();
case Instruction::Load:
return cast<LoadInst>(I)->getPointerOperand();
case Instruction::AtomicCmpXchg:
return cast<AtomicCmpXchgInst>(I)->getPointerOperand();
case Instruction::AtomicRMW:
return cast<AtomicRMWInst>(I)->getPointerOperand();
case Instruction::UDiv:
case Instruction::SDiv:
case Instruction::URem:
case Instruction::SRem:
return I->getOperand(1);
default:
return nullptr;
}
}
bool llvm::isKnownNotFullPoison(const Instruction *PoisonI) {
const BasicBlock *BB = PoisonI->getParent();
SmallSet<const Value *, 16> YieldsPoison;
YieldsPoison.insert(PoisonI);
for (BasicBlock::const_iterator I = PoisonI->getIterator(), E = BB->end();
I != E; ++I) {
if (&*I != PoisonI) {
const Value *NotPoison = getGuaranteedNonFullPoisonOp(&*I);
if (NotPoison != nullptr && YieldsPoison.count(NotPoison)) return true;
if (!isGuaranteedToTransferExecutionToSuccessor(&*I))
return false;
}
if (YieldsPoison.count(&*I)) {
for (const User *User : I->users()) {
const Instruction *UserI = cast<Instruction>(User);
if (UserI->getParent() == BB && propagatesFullPoison(UserI))
YieldsPoison.insert(User);
}
}
}
return false;
}
static bool isKnownNonNaN(Value *V, FastMathFlags FMF) {
if (FMF.noNaNs())
return true;
if (auto *C = dyn_cast<ConstantFP>(V))
return !C->isNaN();
return false;
}
static bool isKnownNonZero(Value *V) {
if (auto *C = dyn_cast<ConstantFP>(V))
return !C->isZero();
return false;
}
static SelectPatternResult matchSelectPattern(CmpInst::Predicate Pred,
FastMathFlags FMF,
Value *CmpLHS, Value *CmpRHS,
Value *TrueVal, Value *FalseVal,
Value *&LHS, Value *&RHS) {
LHS = CmpLHS;
RHS = CmpRHS;
switch (Pred) {
default: break;
case CmpInst::FCMP_OGE: case CmpInst::FCMP_OLE:
case CmpInst::FCMP_UGE: case CmpInst::FCMP_ULE:
if (!FMF.noSignedZeros() && !isKnownNonZero(CmpLHS) &&
!isKnownNonZero(CmpRHS))
return {SPF_UNKNOWN, SPNB_NA, false};
}
SelectPatternNaNBehavior NaNBehavior = SPNB_NA;
bool Ordered = false;
if (CmpInst::isFPPredicate(Pred)) {
bool LHSSafe = isKnownNonNaN(CmpLHS, FMF);
bool RHSSafe = isKnownNonNaN(CmpRHS, FMF);
if (LHSSafe && RHSSafe) {
NaNBehavior = SPNB_RETURNS_ANY;
} else if (CmpInst::isOrdered(Pred)) {
Ordered = true;
if (LHSSafe)
NaNBehavior = SPNB_RETURNS_NAN;
else if (RHSSafe)
NaNBehavior = SPNB_RETURNS_OTHER;
else
return {SPF_UNKNOWN, SPNB_NA, false};
} else {
Ordered = false;
if (LHSSafe)
NaNBehavior = SPNB_RETURNS_OTHER;
else if (RHSSafe)
NaNBehavior = SPNB_RETURNS_NAN;
else
return {SPF_UNKNOWN, SPNB_NA, false};
}
}
if (TrueVal == CmpRHS && FalseVal == CmpLHS) {
std::swap(CmpLHS, CmpRHS);
Pred = CmpInst::getSwappedPredicate(Pred);
if (NaNBehavior == SPNB_RETURNS_NAN)
NaNBehavior = SPNB_RETURNS_OTHER;
else if (NaNBehavior == SPNB_RETURNS_OTHER)
NaNBehavior = SPNB_RETURNS_NAN;
Ordered = !Ordered;
}
if (TrueVal == CmpLHS && FalseVal == CmpRHS) {
switch (Pred) {
default: return {SPF_UNKNOWN, SPNB_NA, false}; case ICmpInst::ICMP_UGT:
case ICmpInst::ICMP_UGE: return {SPF_UMAX, SPNB_NA, false};
case ICmpInst::ICMP_SGT:
case ICmpInst::ICMP_SGE: return {SPF_SMAX, SPNB_NA, false};
case ICmpInst::ICMP_ULT:
case ICmpInst::ICMP_ULE: return {SPF_UMIN, SPNB_NA, false};
case ICmpInst::ICMP_SLT:
case ICmpInst::ICMP_SLE: return {SPF_SMIN, SPNB_NA, false};
case FCmpInst::FCMP_UGT:
case FCmpInst::FCMP_UGE:
case FCmpInst::FCMP_OGT:
case FCmpInst::FCMP_OGE: return {SPF_FMAXNUM, NaNBehavior, Ordered};
case FCmpInst::FCMP_ULT:
case FCmpInst::FCMP_ULE:
case FCmpInst::FCMP_OLT:
case FCmpInst::FCMP_OLE: return {SPF_FMINNUM, NaNBehavior, Ordered};
}
}
if (ConstantInt *C1 = dyn_cast<ConstantInt>(CmpRHS)) {
if ((CmpLHS == TrueVal && match(FalseVal, m_Neg(m_Specific(CmpLHS)))) ||
(CmpLHS == FalseVal && match(TrueVal, m_Neg(m_Specific(CmpLHS))))) {
if (Pred == ICmpInst::ICMP_SGT && (C1->isZero() || C1->isMinusOne())) {
return {(CmpLHS == TrueVal) ? SPF_ABS : SPF_NABS, SPNB_NA, false};
}
if (Pred == ICmpInst::ICMP_SLT && (C1->isZero() || C1->isOne())) {
return {(CmpLHS == FalseVal) ? SPF_ABS : SPF_NABS, SPNB_NA, false};
}
}
if (const auto *C2 = dyn_cast<ConstantInt>(FalseVal)) {
if (C1->getType() == C2->getType() && ~C1->getValue() == C2->getValue() &&
(match(TrueVal, m_Not(m_Specific(CmpLHS))) ||
match(CmpLHS, m_Not(m_Specific(TrueVal))))) {
LHS = TrueVal;
RHS = FalseVal;
return {SPF_SMIN, SPNB_NA, false};
}
}
}
return {SPF_UNKNOWN, SPNB_NA, false};
}
static Value *lookThroughCast(CmpInst *CmpI, Value *V1, Value *V2,
Instruction::CastOps *CastOp) {
CastInst *CI = dyn_cast<CastInst>(V1);
Constant *C = dyn_cast<Constant>(V2);
CastInst *CI2 = dyn_cast<CastInst>(V2);
if (!CI)
return nullptr;
*CastOp = CI->getOpcode();
if (CI2) {
if (CI2->getOpcode() == CI->getOpcode() &&
CI2->getSrcTy() == CI->getSrcTy())
return CI2->getOperand(0);
return nullptr;
} else if (!C) {
return nullptr;
}
if (isa<SExtInst>(CI) && CmpI->isSigned()) {
Constant *T = ConstantExpr::getTrunc(C, CI->getSrcTy());
if (ConstantExpr::getSExt(T, C->getType()) == C)
return T;
return nullptr;
}
if (isa<ZExtInst>(CI) && CmpI->isUnsigned())
return ConstantExpr::getTrunc(C, CI->getSrcTy());
if (isa<TruncInst>(CI))
return ConstantExpr::getIntegerCast(C, CI->getSrcTy(), CmpI->isSigned());
if (isa<FPToUIInst>(CI))
return ConstantExpr::getUIToFP(C, CI->getSrcTy(), true);
if (isa<FPToSIInst>(CI))
return ConstantExpr::getSIToFP(C, CI->getSrcTy(), true);
if (isa<UIToFPInst>(CI))
return ConstantExpr::getFPToUI(C, CI->getSrcTy(), true);
if (isa<SIToFPInst>(CI))
return ConstantExpr::getFPToSI(C, CI->getSrcTy(), true);
if (isa<FPTruncInst>(CI))
return ConstantExpr::getFPExtend(C, CI->getSrcTy(), true);
if (isa<FPExtInst>(CI))
return ConstantExpr::getFPTrunc(C, CI->getSrcTy(), true);
return nullptr;
}
SelectPatternResult llvm::matchSelectPattern(Value *V,
Value *&LHS, Value *&RHS,
Instruction::CastOps *CastOp) {
SelectInst *SI = dyn_cast<SelectInst>(V);
if (!SI) return {SPF_UNKNOWN, SPNB_NA, false};
CmpInst *CmpI = dyn_cast<CmpInst>(SI->getCondition());
if (!CmpI) return {SPF_UNKNOWN, SPNB_NA, false};
CmpInst::Predicate Pred = CmpI->getPredicate();
Value *CmpLHS = CmpI->getOperand(0);
Value *CmpRHS = CmpI->getOperand(1);
Value *TrueVal = SI->getTrueValue();
Value *FalseVal = SI->getFalseValue();
FastMathFlags FMF;
if (isa<FPMathOperator>(CmpI))
FMF = CmpI->getFastMathFlags();
if (CmpI->isEquality())
return {SPF_UNKNOWN, SPNB_NA, false};
if (CastOp && CmpLHS->getType() != TrueVal->getType()) {
if (Value *C = lookThroughCast(CmpI, TrueVal, FalseVal, CastOp))
return ::matchSelectPattern(Pred, FMF, CmpLHS, CmpRHS,
cast<CastInst>(TrueVal)->getOperand(0), C,
LHS, RHS);
if (Value *C = lookThroughCast(CmpI, FalseVal, TrueVal, CastOp))
return ::matchSelectPattern(Pred, FMF, CmpLHS, CmpRHS,
C, cast<CastInst>(FalseVal)->getOperand(0),
LHS, RHS);
}
return ::matchSelectPattern(Pred, FMF, CmpLHS, CmpRHS, TrueVal, FalseVal,
LHS, RHS);
}
ConstantRange llvm::getConstantRangeFromMetadata(MDNode &Ranges) {
const unsigned NumRanges = Ranges.getNumOperands() / 2;
assert(NumRanges >= 1 && "Must have at least one range!");
assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
for (unsigned i = 1; i < NumRanges; ++i) {
auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));
}
return CR;
}
static bool isTruePredicate(CmpInst::Predicate Pred, Value *LHS, Value *RHS,
const DataLayout &DL, unsigned Depth,
AssumptionCache *AC, const Instruction *CxtI,
const DominatorTree *DT) {
if (ICmpInst::isTrueWhenEqual(Pred) && LHS == RHS)
return true;
switch (Pred) {
default:
return false;
case CmpInst::ICMP_SLT:
case CmpInst::ICMP_SLE: {
ConstantInt *CI;
if (match(RHS, m_NSWAdd(m_Specific(LHS), m_ConstantInt(CI)))) {
if (Pred == CmpInst::ICMP_SLT)
return CI->getValue().isStrictlyPositive();
return !CI->isNegative();
}
return false;
}
case CmpInst::ICMP_ULT:
case CmpInst::ICMP_ULE: {
ConstantInt *CI;
if (match(RHS, m_NUWAdd(m_Specific(LHS), m_ConstantInt(CI)))) {
if (Pred == CmpInst::ICMP_ULT)
return !CI->isZero();
return true;
}
return false;
}
}
}
static bool isImpliedCondOperands(CmpInst::Predicate Pred, Value *ALHS,
Value *ARHS, Value *BLHS, Value *BRHS,
const DataLayout &DL, unsigned Depth,
AssumptionCache *AC, const Instruction *CxtI,
const DominatorTree *DT) {
switch (Pred) {
default:
return false;
case CmpInst::ICMP_SLT:
case CmpInst::ICMP_SLE:
return isTruePredicate(CmpInst::ICMP_SLE, BLHS, ALHS, DL, Depth, AC, CxtI,
DT) &&
isTruePredicate(CmpInst::ICMP_SLE, ARHS, BRHS, DL, Depth, AC, CxtI,
DT);
case CmpInst::ICMP_ULT:
case CmpInst::ICMP_ULE:
return isTruePredicate(CmpInst::ICMP_ULE, BLHS, ALHS, DL, Depth, AC, CxtI,
DT) &&
isTruePredicate(CmpInst::ICMP_ULE, ARHS, BRHS, DL, Depth, AC, CxtI,
DT);
}
}
bool llvm::isImpliedCondition(Value *LHS, Value *RHS, const DataLayout &DL,
unsigned Depth, AssumptionCache *AC,
const Instruction *CxtI,
const DominatorTree *DT) {
assert(LHS->getType() == RHS->getType() && "mismatched type");
Type *OpTy = LHS->getType();
assert(OpTy->getScalarType()->isIntegerTy(1));
if (LHS == RHS) return true;
if (OpTy->isVectorTy())
return false;
assert(OpTy->isIntegerTy(1) && "implied by above");
ICmpInst::Predicate APred, BPred;
Value *ALHS, *ARHS;
Value *BLHS, *BRHS;
if (!match(LHS, m_ICmp(APred, m_Value(ALHS), m_Value(ARHS))) ||
!match(RHS, m_ICmp(BPred, m_Value(BLHS), m_Value(BRHS))))
return false;
if (APred == BPred)
return isImpliedCondOperands(APred, ALHS, ARHS, BLHS, BRHS, DL, Depth, AC,
CxtI, DT);
return false;
}