aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Analysis')
-rw-r--r--lib/Analysis/BasicAliasAnalysis.cpp12
-rw-r--r--lib/Analysis/ConstantFolding.cpp17
-rw-r--r--lib/Analysis/DemandedBits.cpp31
-rw-r--r--lib/Analysis/DomPrinter.cpp16
-rw-r--r--lib/Analysis/IVUsers.cpp12
-rw-r--r--lib/Analysis/InlineCost.cpp1
-rw-r--r--lib/Analysis/InstructionSimplify.cpp535
-rw-r--r--lib/Analysis/Lint.cpp14
-rw-r--r--lib/Analysis/MemorySSAUpdater.cpp9
-rw-r--r--lib/Analysis/ScalarEvolution.cpp259
-rw-r--r--lib/Analysis/ScalarEvolutionNormalization.cpp71
-rw-r--r--lib/Analysis/ValueTracking.cpp849
12 files changed, 1003 insertions, 823 deletions
diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp
index 3db041cc0fa6..537823020301 100644
--- a/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/lib/Analysis/BasicAliasAnalysis.cpp
@@ -924,8 +924,8 @@ static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
uint64_t V2Size,
const DataLayout &DL) {
- assert(GEP1->getPointerOperand()->stripPointerCasts() ==
- GEP2->getPointerOperand()->stripPointerCasts() &&
+ assert(GEP1->getPointerOperand()->stripPointerCastsAndBarriers() ==
+ GEP2->getPointerOperand()->stripPointerCastsAndBarriers() &&
GEP1->getPointerOperandType() == GEP2->getPointerOperandType() &&
"Expected GEPs with the same pointer operand");
@@ -1184,8 +1184,8 @@ AliasResult BasicAAResult::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size,
// If we know the two GEPs are based off of the exact same pointer (and not
// just the same underlying object), see if that tells us anything about
// the resulting pointers.
- if (GEP1->getPointerOperand()->stripPointerCasts() ==
- GEP2->getPointerOperand()->stripPointerCasts() &&
+ if (GEP1->getPointerOperand()->stripPointerCastsAndBarriers() ==
+ GEP2->getPointerOperand()->stripPointerCastsAndBarriers() &&
GEP1->getPointerOperandType() == GEP2->getPointerOperandType()) {
AliasResult R = aliasSameBasePointerGEPs(GEP1, V1Size, GEP2, V2Size, DL);
// If we couldn't find anything interesting, don't abandon just yet.
@@ -1500,8 +1500,8 @@ AliasResult BasicAAResult::aliasCheck(const Value *V1, uint64_t V1Size,
return NoAlias;
// Strip off any casts if they exist.
- V1 = V1->stripPointerCasts();
- V2 = V2->stripPointerCasts();
+ V1 = V1->stripPointerCastsAndBarriers();
+ V2 = V2->stripPointerCastsAndBarriers();
// If V1 or V2 is undef, the result is NoAlias because we can always pick a
// value for undef that aliases nothing in the program.
diff --git a/lib/Analysis/ConstantFolding.cpp b/lib/Analysis/ConstantFolding.cpp
index 14176dac2104..863fbdba7e67 100644
--- a/lib/Analysis/ConstantFolding.cpp
+++ b/lib/Analysis/ConstantFolding.cpp
@@ -42,6 +42,7 @@
#include "llvm/IR/Value.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/KnownBits.h"
#include "llvm/Support/MathExtras.h"
#include <cassert>
#include <cerrno>
@@ -687,21 +688,21 @@ Constant *SymbolicallyEvaluateBinop(unsigned Opc, Constant *Op0, Constant *Op1,
if (Opc == Instruction::And) {
unsigned BitWidth = DL.getTypeSizeInBits(Op0->getType()->getScalarType());
- APInt KnownZero0(BitWidth, 0), KnownOne0(BitWidth, 0);
- APInt KnownZero1(BitWidth, 0), KnownOne1(BitWidth, 0);
- computeKnownBits(Op0, KnownZero0, KnownOne0, DL);
- computeKnownBits(Op1, KnownZero1, KnownOne1, DL);
- if ((KnownOne1 | KnownZero0).isAllOnesValue()) {
+ KnownBits Known0(BitWidth);
+ KnownBits Known1(BitWidth);
+ computeKnownBits(Op0, Known0, DL);
+ computeKnownBits(Op1, Known1, DL);
+ if ((Known1.One | Known0.Zero).isAllOnesValue()) {
// All the bits of Op0 that the 'and' could be masking are already zero.
return Op0;
}
- if ((KnownOne0 | KnownZero1).isAllOnesValue()) {
+ if ((Known0.One | Known1.Zero).isAllOnesValue()) {
// All the bits of Op1 that the 'and' could be masking are already zero.
return Op1;
}
- APInt KnownZero = KnownZero0 | KnownZero1;
- APInt KnownOne = KnownOne0 & KnownOne1;
+ APInt KnownZero = Known0.Zero | Known1.Zero;
+ APInt KnownOne = Known0.One & Known1.One;
if ((KnownZero | KnownOne).isAllOnesValue()) {
return ConstantInt::get(Op0->getType(), KnownOne);
}
diff --git a/lib/Analysis/DemandedBits.cpp b/lib/Analysis/DemandedBits.cpp
index 151c0b0e6c93..285339deaaf5 100644
--- a/lib/Analysis/DemandedBits.cpp
+++ b/lib/Analysis/DemandedBits.cpp
@@ -37,6 +37,7 @@
#include "llvm/IR/Operator.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/KnownBits.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
@@ -72,8 +73,7 @@ static bool isAlwaysLive(Instruction *I) {
void DemandedBits::determineLiveOperandBits(
const Instruction *UserI, const Instruction *I, unsigned OperandNo,
- const APInt &AOut, APInt &AB, APInt &KnownZero, APInt &KnownOne,
- APInt &KnownZero2, APInt &KnownOne2) {
+ const APInt &AOut, APInt &AB, KnownBits &Known, KnownBits &Known2) {
unsigned BitWidth = AB.getBitWidth();
// We're called once per operand, but for some instructions, we need to
@@ -85,15 +85,13 @@ void DemandedBits::determineLiveOperandBits(
auto ComputeKnownBits =
[&](unsigned BitWidth, const Value *V1, const Value *V2) {
const DataLayout &DL = I->getModule()->getDataLayout();
- KnownZero = APInt(BitWidth, 0);
- KnownOne = APInt(BitWidth, 0);
- computeKnownBits(const_cast<Value *>(V1), KnownZero, KnownOne, DL, 0,
+ Known = KnownBits(BitWidth);
+ computeKnownBits(const_cast<Value *>(V1), Known, DL, 0,
&AC, UserI, &DT);
if (V2) {
- KnownZero2 = APInt(BitWidth, 0);
- KnownOne2 = APInt(BitWidth, 0);
- computeKnownBits(const_cast<Value *>(V2), KnownZero2, KnownOne2, DL,
+ Known2 = KnownBits(BitWidth);
+ computeKnownBits(const_cast<Value *>(V2), Known2, DL,
0, &AC, UserI, &DT);
}
};
@@ -120,7 +118,7 @@ void DemandedBits::determineLiveOperandBits(
// known to be one.
ComputeKnownBits(BitWidth, I, nullptr);
AB = APInt::getHighBitsSet(BitWidth,
- std::min(BitWidth, KnownOne.countLeadingZeros()+1));
+ std::min(BitWidth, Known.One.countLeadingZeros()+1));
}
break;
case Intrinsic::cttz:
@@ -130,7 +128,7 @@ void DemandedBits::determineLiveOperandBits(
// known to be one.
ComputeKnownBits(BitWidth, I, nullptr);
AB = APInt::getLowBitsSet(BitWidth,
- std::min(BitWidth, KnownOne.countTrailingZeros()+1));
+ std::min(BitWidth, Known.One.countTrailingZeros()+1));
}
break;
}
@@ -200,11 +198,11 @@ void DemandedBits::determineLiveOperandBits(
// dead).
if (OperandNo == 0) {
ComputeKnownBits(BitWidth, I, UserI->getOperand(1));
- AB &= ~KnownZero2;
+ AB &= ~Known2.Zero;
} else {
if (!isa<Instruction>(UserI->getOperand(0)))
ComputeKnownBits(BitWidth, UserI->getOperand(0), I);
- AB &= ~(KnownZero & ~KnownZero2);
+ AB &= ~(Known.Zero & ~Known2.Zero);
}
break;
case Instruction::Or:
@@ -216,11 +214,11 @@ void DemandedBits::determineLiveOperandBits(
// dead).
if (OperandNo == 0) {
ComputeKnownBits(BitWidth, I, UserI->getOperand(1));
- AB &= ~KnownOne2;
+ AB &= ~Known2.One;
} else {
if (!isa<Instruction>(UserI->getOperand(0)))
ComputeKnownBits(BitWidth, UserI->getOperand(0), I);
- AB &= ~(KnownOne & ~KnownOne2);
+ AB &= ~(Known.One & ~Known2.One);
}
break;
case Instruction::Xor:
@@ -318,7 +316,7 @@ void DemandedBits::performAnalysis() {
if (!UserI->getType()->isIntegerTy())
Visited.insert(UserI);
- APInt KnownZero, KnownOne, KnownZero2, KnownOne2;
+ KnownBits Known, Known2;
// Compute the set of alive bits for each operand. These are anded into the
// existing set, if any, and if that changes the set of alive bits, the
// operand is added to the work-list.
@@ -335,8 +333,7 @@ void DemandedBits::performAnalysis() {
// Bits of each operand that are used to compute alive bits of the
// output are alive, all others are dead.
determineLiveOperandBits(UserI, I, OI.getOperandNo(), AOut, AB,
- KnownZero, KnownOne,
- KnownZero2, KnownOne2);
+ Known, Known2);
}
// If we've added to the set of alive bits (or the operand has not
diff --git a/lib/Analysis/DomPrinter.cpp b/lib/Analysis/DomPrinter.cpp
index 7acfb41500d4..8abc0e7d0df9 100644
--- a/lib/Analysis/DomPrinter.cpp
+++ b/lib/Analysis/DomPrinter.cpp
@@ -80,6 +80,22 @@ struct DOTGraphTraits<PostDominatorTree*>
};
}
+void DominatorTree::viewGraph(const Twine &Name, const Twine &Title) {
+#ifndef NDEBUG
+ ViewGraph(this, Name, false, Title);
+#else
+ errs() << "DomTree dump not available, build with DEBUG\n";
+#endif // NDEBUG
+}
+
+void DominatorTree::viewGraph() {
+#ifndef NDEBUG
+ this->viewGraph("domtree", "Dominator Tree for function");
+#else
+ errs() << "DomTree dump not available, build with DEBUG\n";
+#endif // NDEBUG
+}
+
namespace {
struct DominatorTreeWrapperPassAnalysisGraphTraits {
static DominatorTree *getGraph(DominatorTreeWrapperPass *DTWP) {
diff --git a/lib/Analysis/IVUsers.cpp b/lib/Analysis/IVUsers.cpp
index fde805a5fde5..c30feb973e60 100644
--- a/lib/Analysis/IVUsers.cpp
+++ b/lib/Analysis/IVUsers.cpp
@@ -253,18 +253,8 @@ bool IVUsers::AddUsersImpl(Instruction *I,
const SCEV *OriginalISE = ISE;
auto NormalizePred = [&](const SCEVAddRecExpr *AR) {
- // We only allow affine AddRecs to be normalized, otherwise we would not
- // be able to correctly denormalize.
- // e.g. {1,+,3,+,2} == {-2,+,1,+,2} + {3,+,2}
- // Normalized form: {-2,+,1,+,2}
- // Denormalized form: {1,+,3,+,2}
- //
- // However, denormalization would use a different step expression than
- // normalization (see getPostIncExpr), generating the wrong final
- // expression: {-2,+,1,+,2} + {1,+,2} => {-1,+,3,+,2}
auto *L = AR->getLoop();
- bool Result =
- AR->isAffine() && IVUseShouldUsePostIncValue(User, I, L, DT);
+ bool Result = IVUseShouldUsePostIncValue(User, I, L, DT);
if (Result)
NewUse.PostIncLoops.insert(L);
return Result;
diff --git a/lib/Analysis/InlineCost.cpp b/lib/Analysis/InlineCost.cpp
index 1f8dec2aed80..788f908bafca 100644
--- a/lib/Analysis/InlineCost.cpp
+++ b/lib/Analysis/InlineCost.cpp
@@ -1557,7 +1557,6 @@ InlineParams llvm::getInlineParams(int Threshold) {
Params.ColdCallSiteThreshold = ColdCallSiteThreshold;
// Set the OptMinSizeThreshold and OptSizeThreshold params only if the
- // Set the OptMinSizeThreshold and OptSizeThreshold params only if the
// -inlinehint-threshold commandline option is not explicitly given. If that
// option is present, then its value applies even for callees with size and
// minsize attributes.
diff --git a/lib/Analysis/InstructionSimplify.cpp b/lib/Analysis/InstructionSimplify.cpp
index 2259fbaeb982..e720e3ebecdb 100644
--- a/lib/Analysis/InstructionSimplify.cpp
+++ b/lib/Analysis/InstructionSimplify.cpp
@@ -35,6 +35,7 @@
#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ValueHandle.h"
+#include "llvm/Support/KnownBits.h"
#include <algorithm>
using namespace llvm;
using namespace llvm::PatternMatch;
@@ -46,34 +47,19 @@ enum { RecursionLimit = 3 };
STATISTIC(NumExpand, "Number of expansions");
STATISTIC(NumReassoc, "Number of reassociations");
-namespace {
-struct Query {
- const DataLayout &DL;
- const TargetLibraryInfo *TLI;
- const DominatorTree *DT;
- AssumptionCache *AC;
- const Instruction *CxtI;
-
- Query(const DataLayout &DL, const TargetLibraryInfo *tli,
- const DominatorTree *dt, AssumptionCache *ac = nullptr,
- const Instruction *cxti = nullptr)
- : DL(DL), TLI(tli), DT(dt), AC(ac), CxtI(cxti) {}
-};
-} // end anonymous namespace
-
-static Value *SimplifyAndInst(Value *, Value *, const Query &, unsigned);
-static Value *SimplifyBinOp(unsigned, Value *, Value *, const Query &,
+static Value *SimplifyAndInst(Value *, Value *, const SimplifyQuery &, unsigned);
+static Value *SimplifyBinOp(unsigned, Value *, Value *, const SimplifyQuery &,
unsigned);
static Value *SimplifyFPBinOp(unsigned, Value *, Value *, const FastMathFlags &,
- const Query &, unsigned);
-static Value *SimplifyCmpInst(unsigned, Value *, Value *, const Query &,
+ const SimplifyQuery &, unsigned);
+static Value *SimplifyCmpInst(unsigned, Value *, Value *, const SimplifyQuery &,
unsigned);
static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
- const Query &Q, unsigned MaxRecurse);
-static Value *SimplifyOrInst(Value *, Value *, const Query &, unsigned);
-static Value *SimplifyXorInst(Value *, Value *, const Query &, unsigned);
+ const SimplifyQuery &Q, unsigned MaxRecurse);
+static Value *SimplifyOrInst(Value *, Value *, const SimplifyQuery &, unsigned);
+static Value *SimplifyXorInst(Value *, Value *, const SimplifyQuery &, unsigned);
static Value *SimplifyCastInst(unsigned, Value *, Type *,
- const Query &, unsigned);
+ const SimplifyQuery &, unsigned);
/// For a boolean type or a vector of boolean type, return false or a vector
/// with every element false.
@@ -138,7 +124,7 @@ static bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) {
/// Also performs the transform "(A op' B) op C" -> "(A op C) op' (B op C)".
/// Returns the simplified value, or null if no simplification was performed.
static Value *ExpandBinOp(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,
- Instruction::BinaryOps OpcodeToExpand, const Query &Q,
+ Instruction::BinaryOps OpcodeToExpand, const SimplifyQuery &Q,
unsigned MaxRecurse) {
// Recursion is always used, so bail out at once if we already hit the limit.
if (!MaxRecurse--)
@@ -196,7 +182,7 @@ static Value *ExpandBinOp(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,
/// Generic simplifications for associative binary operations.
/// Returns the simpler value, or null if none was found.
static Value *SimplifyAssociativeBinOp(Instruction::BinaryOps Opcode,
- Value *LHS, Value *RHS, const Query &Q,
+ Value *LHS, Value *RHS, const SimplifyQuery &Q,
unsigned MaxRecurse) {
assert(Instruction::isAssociative(Opcode) && "Not an associative operation!");
@@ -295,7 +281,7 @@ static Value *SimplifyAssociativeBinOp(Instruction::BinaryOps Opcode,
/// of the select results in the same value. Returns the common value if so,
/// otherwise returns null.
static Value *ThreadBinOpOverSelect(Instruction::BinaryOps Opcode, Value *LHS,
- Value *RHS, const Query &Q,
+ Value *RHS, const SimplifyQuery &Q,
unsigned MaxRecurse) {
// Recursion is always used, so bail out at once if we already hit the limit.
if (!MaxRecurse--)
@@ -367,7 +353,7 @@ static Value *ThreadBinOpOverSelect(Instruction::BinaryOps Opcode, Value *LHS,
/// comparison by seeing whether both branches of the select result in the same
/// value. Returns the common value if so, otherwise returns null.
static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS,
- Value *RHS, const Query &Q,
+ Value *RHS, const SimplifyQuery &Q,
unsigned MaxRecurse) {
// Recursion is always used, so bail out at once if we already hit the limit.
if (!MaxRecurse--)
@@ -449,7 +435,7 @@ static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS,
/// phi values yields the same result for every value. If so returns the common
/// value, otherwise returns null.
static Value *ThreadBinOpOverPHI(Instruction::BinaryOps Opcode, Value *LHS,
- Value *RHS, const Query &Q,
+ Value *RHS, const SimplifyQuery &Q,
unsigned MaxRecurse) {
// Recursion is always used, so bail out at once if we already hit the limit.
if (!MaxRecurse--)
@@ -492,7 +478,7 @@ static Value *ThreadBinOpOverPHI(Instruction::BinaryOps Opcode, Value *LHS,
/// yields the same result every time. If so returns the common result,
/// otherwise returns null.
static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS,
- const Query &Q, unsigned MaxRecurse) {
+ const SimplifyQuery &Q, unsigned MaxRecurse) {
// Recursion is always used, so bail out at once if we already hit the limit.
if (!MaxRecurse--)
return nullptr;
@@ -527,7 +513,7 @@ static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS,
static Constant *foldOrCommuteConstant(Instruction::BinaryOps Opcode,
Value *&Op0, Value *&Op1,
- const Query &Q) {
+ const SimplifyQuery &Q) {
if (auto *CLHS = dyn_cast<Constant>(Op0)) {
if (auto *CRHS = dyn_cast<Constant>(Op1))
return ConstantFoldBinaryOpOperands(Opcode, CLHS, CRHS, Q.DL);
@@ -542,7 +528,7 @@ static Constant *foldOrCommuteConstant(Instruction::BinaryOps Opcode,
/// Given operands for an Add, see if we can fold the result.
/// If not, this returns null.
static Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
- const Query &Q, unsigned MaxRecurse) {
+ const SimplifyQuery &Q, unsigned MaxRecurse) {
if (Constant *C = foldOrCommuteConstant(Instruction::Add, Op0, Op1, Q))
return C;
@@ -601,10 +587,15 @@ Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
const DataLayout &DL, const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, Query(DL, TLI, DT, AC, CxtI),
+ return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, {DL, TLI, DT, AC, CxtI},
RecursionLimit);
}
+Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
+ const SimplifyQuery &Query) {
+ return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, Query, RecursionLimit);
+}
+
/// \brief Compute the base pointer and cumulative constant offsets for V.
///
/// This strips all constant offsets off of V, leaving it the base pointer, and
@@ -679,7 +670,7 @@ static Constant *computePointerDifference(const DataLayout &DL, Value *LHS,
/// Given operands for a Sub, see if we can fold the result.
/// If not, this returns null.
static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
- const Query &Q, unsigned MaxRecurse) {
+ const SimplifyQuery &Q, unsigned MaxRecurse) {
if (Constant *C = foldOrCommuteConstant(Instruction::Sub, Op0, Op1, Q))
return C;
@@ -703,10 +694,9 @@ static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
return Op0;
unsigned BitWidth = Op1->getType()->getScalarSizeInBits();
- APInt KnownZero(BitWidth, 0);
- APInt KnownOne(BitWidth, 0);
- computeKnownBits(Op1, KnownZero, KnownOne, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
- if (KnownZero.isMaxSignedValue()) {
+ KnownBits Known(BitWidth);
+ computeKnownBits(Op1, Known, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
+ if (Known.Zero.isMaxSignedValue()) {
// Op1 is either 0 or the minimum signed value. If the sub is NSW, then
// Op1 must be 0 because negating the minimum signed value is undefined.
if (isNSW)
@@ -813,14 +803,19 @@ Value *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
const DataLayout &DL, const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, Query(DL, TLI, DT, AC, CxtI),
+ return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, {DL, TLI, DT, AC, CxtI},
RecursionLimit);
}
+Value *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
+ const SimplifyQuery &Q) {
+ return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, Q, RecursionLimit);
+}
+
/// Given operands for an FAdd, see if we can fold the result. If not, this
/// returns null.
static Value *SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF,
- const Query &Q, unsigned MaxRecurse) {
+ const SimplifyQuery &Q, unsigned MaxRecurse) {
if (Constant *C = foldOrCommuteConstant(Instruction::FAdd, Op0, Op1, Q))
return C;
@@ -854,7 +849,7 @@ static Value *SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF,
/// Given operands for an FSub, see if we can fold the result. If not, this
/// returns null.
static Value *SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF,
- const Query &Q, unsigned MaxRecurse) {
+ const SimplifyQuery &Q, unsigned MaxRecurse) {
if (Constant *C = foldOrCommuteConstant(Instruction::FSub, Op0, Op1, Q))
return C;
@@ -886,7 +881,7 @@ static Value *SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF,
/// Given the operands for an FMul, see if we can fold the result
static Value *SimplifyFMulInst(Value *Op0, Value *Op1, FastMathFlags FMF,
- const Query &Q, unsigned MaxRecurse) {
+ const SimplifyQuery &Q, unsigned MaxRecurse) {
if (Constant *C = foldOrCommuteConstant(Instruction::FMul, Op0, Op1, Q))
return C;
@@ -903,7 +898,7 @@ static Value *SimplifyFMulInst(Value *Op0, Value *Op1, FastMathFlags FMF,
/// Given operands for a Mul, see if we can fold the result.
/// If not, this returns null.
-static Value *SimplifyMulInst(Value *Op0, Value *Op1, const Query &Q,
+static Value *SimplifyMulInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
unsigned MaxRecurse) {
if (Constant *C = foldOrCommuteConstant(Instruction::Mul, Op0, Op1, Q))
return C;
@@ -963,34 +958,52 @@ Value *llvm::SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF,
const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifyFAddInst(Op0, Op1, FMF, Query(DL, TLI, DT, AC, CxtI),
+ return ::SimplifyFAddInst(Op0, Op1, FMF, {DL, TLI, DT, AC, CxtI},
RecursionLimit);
}
+Value *llvm::SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF,
+ const SimplifyQuery &Q) {
+ return ::SimplifyFAddInst(Op0, Op1, FMF, Q, RecursionLimit);
+}
+
Value *llvm::SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF,
const DataLayout &DL,
const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifyFSubInst(Op0, Op1, FMF, Query(DL, TLI, DT, AC, CxtI),
+ return ::SimplifyFSubInst(Op0, Op1, FMF, {DL, TLI, DT, AC, CxtI},
RecursionLimit);
}
+Value *llvm::SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF,
+ const SimplifyQuery &Q) {
+ return ::SimplifyFSubInst(Op0, Op1, FMF, Q, RecursionLimit);
+}
+
Value *llvm::SimplifyFMulInst(Value *Op0, Value *Op1, FastMathFlags FMF,
const DataLayout &DL,
const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifyFMulInst(Op0, Op1, FMF, Query(DL, TLI, DT, AC, CxtI),
+ return ::SimplifyFMulInst(Op0, Op1, FMF, {DL, TLI, DT, AC, CxtI},
RecursionLimit);
}
+Value *llvm::SimplifyFMulInst(Value *Op0, Value *Op1, FastMathFlags FMF,
+ const SimplifyQuery &Q) {
+ return ::SimplifyFMulInst(Op0, Op1, FMF, Q, RecursionLimit);
+}
+
Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const DataLayout &DL,
const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifyMulInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI),
- RecursionLimit);
+ return ::SimplifyMulInst(Op0, Op1, {DL, TLI, DT, AC, CxtI}, RecursionLimit);
+}
+
+Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
+ return ::SimplifyMulInst(Op0, Op1, Q, RecursionLimit);
}
/// Check for common or similar folds of integer division or integer remainder.
@@ -1047,7 +1060,7 @@ static Value *simplifyDivRem(Value *Op0, Value *Op1, bool IsDiv) {
/// Given operands for an SDiv or UDiv, see if we can fold the result.
/// If not, this returns null.
static Value *SimplifyDiv(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
- const Query &Q, unsigned MaxRecurse) {
+ const SimplifyQuery &Q, unsigned MaxRecurse) {
if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q))
return C;
@@ -1103,7 +1116,7 @@ static Value *SimplifyDiv(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
/// Given operands for an SDiv, see if we can fold the result.
/// If not, this returns null.
-static Value *SimplifySDivInst(Value *Op0, Value *Op1, const Query &Q,
+static Value *SimplifySDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
unsigned MaxRecurse) {
if (Value *V = SimplifyDiv(Instruction::SDiv, Op0, Op1, Q, MaxRecurse))
return V;
@@ -1115,13 +1128,16 @@ Value *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const DataLayout &DL,
const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifySDivInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI),
- RecursionLimit);
+ return ::SimplifySDivInst(Op0, Op1, {DL, TLI, DT, AC, CxtI}, RecursionLimit);
+}
+
+Value *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
+ return ::SimplifySDivInst(Op0, Op1, Q, RecursionLimit);
}
/// Given operands for a UDiv, see if we can fold the result.
/// If not, this returns null.
-static Value *SimplifyUDivInst(Value *Op0, Value *Op1, const Query &Q,
+static Value *SimplifyUDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
unsigned MaxRecurse) {
if (Value *V = SimplifyDiv(Instruction::UDiv, Op0, Op1, Q, MaxRecurse))
return V;
@@ -1143,12 +1159,15 @@ Value *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const DataLayout &DL,
const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifyUDivInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI),
- RecursionLimit);
+ return ::SimplifyUDivInst(Op0, Op1, {DL, TLI, DT, AC, CxtI}, RecursionLimit);
+}
+
+Value *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
+ return ::SimplifyUDivInst(Op0, Op1, Q, RecursionLimit);
}
static Value *SimplifyFDivInst(Value *Op0, Value *Op1, FastMathFlags FMF,
- const Query &Q, unsigned) {
+ const SimplifyQuery &Q, unsigned) {
if (Constant *C = foldOrCommuteConstant(Instruction::FDiv, Op0, Op1, Q))
return C;
@@ -1193,14 +1212,19 @@ Value *llvm::SimplifyFDivInst(Value *Op0, Value *Op1, FastMathFlags FMF,
const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifyFDivInst(Op0, Op1, FMF, Query(DL, TLI, DT, AC, CxtI),
+ return ::SimplifyFDivInst(Op0, Op1, FMF, {DL, TLI, DT, AC, CxtI},
RecursionLimit);
}
+Value *llvm::SimplifyFDivInst(Value *Op0, Value *Op1, FastMathFlags FMF,
+ const SimplifyQuery &Q) {
+ return ::SimplifyFDivInst(Op0, Op1, FMF, Q, RecursionLimit);
+}
+
/// Given operands for an SRem or URem, see if we can fold the result.
/// If not, this returns null.
static Value *SimplifyRem(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
- const Query &Q, unsigned MaxRecurse) {
+ const SimplifyQuery &Q, unsigned MaxRecurse) {
if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q))
return C;
@@ -1231,7 +1255,7 @@ static Value *SimplifyRem(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
/// Given operands for an SRem, see if we can fold the result.
/// If not, this returns null.
-static Value *SimplifySRemInst(Value *Op0, Value *Op1, const Query &Q,
+static Value *SimplifySRemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
unsigned MaxRecurse) {
if (Value *V = SimplifyRem(Instruction::SRem, Op0, Op1, Q, MaxRecurse))
return V;
@@ -1243,13 +1267,16 @@ Value *llvm::SimplifySRemInst(Value *Op0, Value *Op1, const DataLayout &DL,
const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifySRemInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI),
- RecursionLimit);
+ return ::SimplifySRemInst(Op0, Op1, {DL, TLI, DT, AC, CxtI}, RecursionLimit);
+}
+
+Value *llvm::SimplifySRemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
+ return ::SimplifySRemInst(Op0, Op1, Q, RecursionLimit);
}
/// Given operands for a URem, see if we can fold the result.
/// If not, this returns null.
-static Value *SimplifyURemInst(Value *Op0, Value *Op1, const Query &Q,
+static Value *SimplifyURemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
unsigned MaxRecurse) {
if (Value *V = SimplifyRem(Instruction::URem, Op0, Op1, Q, MaxRecurse))
return V;
@@ -1271,12 +1298,15 @@ Value *llvm::SimplifyURemInst(Value *Op0, Value *Op1, const DataLayout &DL,
const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifyURemInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI),
- RecursionLimit);
+ return ::SimplifyURemInst(Op0, Op1, {DL, TLI, DT, AC, CxtI}, RecursionLimit);
+}
+
+Value *llvm::SimplifyURemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
+ return ::SimplifyURemInst(Op0, Op1, Q, RecursionLimit);
}
static Value *SimplifyFRemInst(Value *Op0, Value *Op1, FastMathFlags FMF,
- const Query &Q, unsigned) {
+ const SimplifyQuery &Q, unsigned) {
if (Constant *C = foldOrCommuteConstant(Instruction::FRem, Op0, Op1, Q))
return C;
@@ -1302,10 +1332,15 @@ Value *llvm::SimplifyFRemInst(Value *Op0, Value *Op1, FastMathFlags FMF,
const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifyFRemInst(Op0, Op1, FMF, Query(DL, TLI, DT, AC, CxtI),
+ return ::SimplifyFRemInst(Op0, Op1, FMF, {DL, TLI, DT, AC, CxtI},
RecursionLimit);
}
+Value *llvm::SimplifyFRemInst(Value *Op0, Value *Op1, FastMathFlags FMF,
+ const SimplifyQuery &Q) {
+ return ::SimplifyFRemInst(Op0, Op1, FMF, Q, RecursionLimit);
+}
+
/// Returns true if a shift by \c Amount always yields undef.
static bool isUndefShift(Value *Amount) {
Constant *C = dyn_cast<Constant>(Amount);
@@ -1336,7 +1371,7 @@ static bool isUndefShift(Value *Amount) {
/// Given operands for an Shl, LShr or AShr, see if we can fold the result.
/// If not, this returns null.
static Value *SimplifyShift(Instruction::BinaryOps Opcode, Value *Op0,
- Value *Op1, const Query &Q, unsigned MaxRecurse) {
+ Value *Op1, const SimplifyQuery &Q, unsigned MaxRecurse) {
if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q))
return C;
@@ -1367,17 +1402,15 @@ static Value *SimplifyShift(Instruction::BinaryOps Opcode, Value *Op0,
// If any bits in the shift amount make that value greater than or equal to
// the number of bits in the type, the shift is undefined.
unsigned BitWidth = Op1->getType()->getScalarSizeInBits();
- APInt KnownZero(BitWidth, 0);
- APInt KnownOne(BitWidth, 0);
- computeKnownBits(Op1, KnownZero, KnownOne, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
- if (KnownOne.getLimitedValue() >= BitWidth)
+ KnownBits Known(BitWidth);
+ computeKnownBits(Op1, Known, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
+ if (Known.One.getLimitedValue() >= BitWidth)
return UndefValue::get(Op0->getType());
// If all valid bits in the shift amount are known zero, the first operand is
// unchanged.
unsigned NumValidShiftBits = Log2_32_Ceil(BitWidth);
- APInt ShiftAmountMask = APInt::getLowBitsSet(BitWidth, NumValidShiftBits);
- if ((KnownZero & ShiftAmountMask) == ShiftAmountMask)
+ if (Known.Zero.countTrailingOnes() >= NumValidShiftBits)
return Op0;
return nullptr;
@@ -1386,7 +1419,7 @@ static Value *SimplifyShift(Instruction::BinaryOps Opcode, Value *Op0,
/// \brief Given operands for an Shl, LShr or AShr, see if we can
/// fold the result. If not, this returns null.
static Value *SimplifyRightShift(Instruction::BinaryOps Opcode, Value *Op0,
- Value *Op1, bool isExact, const Query &Q,
+ Value *Op1, bool isExact, const SimplifyQuery &Q,
unsigned MaxRecurse) {
if (Value *V = SimplifyShift(Opcode, Op0, Op1, Q, MaxRecurse))
return V;
@@ -1403,11 +1436,9 @@ static Value *SimplifyRightShift(Instruction::BinaryOps Opcode, Value *Op0,
// The low bit cannot be shifted out of an exact shift if it is set.
if (isExact) {
unsigned BitWidth = Op0->getType()->getScalarSizeInBits();
- APInt Op0KnownZero(BitWidth, 0);
- APInt Op0KnownOne(BitWidth, 0);
- computeKnownBits(Op0, Op0KnownZero, Op0KnownOne, Q.DL, /*Depth=*/0, Q.AC,
- Q.CxtI, Q.DT);
- if (Op0KnownOne[0])
+ KnownBits Op0Known(BitWidth);
+ computeKnownBits(Op0, Op0Known, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT);
+ if (Op0Known.One[0])
return Op0;
}
@@ -1417,7 +1448,7 @@ static Value *SimplifyRightShift(Instruction::BinaryOps Opcode, Value *Op0,
/// Given operands for an Shl, see if we can fold the result.
/// If not, this returns null.
static Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
- const Query &Q, unsigned MaxRecurse) {
+ const SimplifyQuery &Q, unsigned MaxRecurse) {
if (Value *V = SimplifyShift(Instruction::Shl, Op0, Op1, Q, MaxRecurse))
return V;
@@ -1437,14 +1468,19 @@ Value *llvm::SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
const DataLayout &DL, const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifyShlInst(Op0, Op1, isNSW, isNUW, Query(DL, TLI, DT, AC, CxtI),
+ return ::SimplifyShlInst(Op0, Op1, isNSW, isNUW, {DL, TLI, DT, AC, CxtI},
RecursionLimit);
}
+Value *llvm::SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
+ const SimplifyQuery &Q) {
+ return ::SimplifyShlInst(Op0, Op1, isNSW, isNUW, Q, RecursionLimit);
+}
+
/// Given operands for an LShr, see if we can fold the result.
/// If not, this returns null.
static Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
- const Query &Q, unsigned MaxRecurse) {
+ const SimplifyQuery &Q, unsigned MaxRecurse) {
if (Value *V = SimplifyRightShift(Instruction::LShr, Op0, Op1, isExact, Q,
MaxRecurse))
return V;
@@ -1462,14 +1498,19 @@ Value *llvm::SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifyLShrInst(Op0, Op1, isExact, Query(DL, TLI, DT, AC, CxtI),
+ return ::SimplifyLShrInst(Op0, Op1, isExact, {DL, TLI, DT, AC, CxtI},
RecursionLimit);
}
+Value *llvm::SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
+ const SimplifyQuery &Q) {
+ return ::SimplifyLShrInst(Op0, Op1, isExact, Q, RecursionLimit);
+}
+
/// Given operands for an AShr, see if we can fold the result.
/// If not, this returns null.
static Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
- const Query &Q, unsigned MaxRecurse) {
+ const SimplifyQuery &Q, unsigned MaxRecurse) {
if (Value *V = SimplifyRightShift(Instruction::AShr, Op0, Op1, isExact, Q,
MaxRecurse))
return V;
@@ -1496,10 +1537,15 @@ Value *llvm::SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifyAShrInst(Op0, Op1, isExact, Query(DL, TLI, DT, AC, CxtI),
+ return ::SimplifyAShrInst(Op0, Op1, isExact, {DL, TLI, DT, AC, CxtI},
RecursionLimit);
}
+Value *llvm::SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
+ const SimplifyQuery &Q) {
+ return ::SimplifyAShrInst(Op0, Op1, isExact, Q, RecursionLimit);
+}
+
static Value *simplifyUnsignedRangeCheck(ICmpInst *ZeroICmp,
ICmpInst *UnsignedICmp, bool IsAnd) {
Value *X, *Y;
@@ -1575,6 +1621,7 @@ static Value *SimplifyAndOfICmps(ICmpInst *Op0, ICmpInst *Op1) {
if (Value *X = simplifyAndOfICmpsWithSameOperands(Op0, Op1))
return X;
+ // FIXME: This should be shared with or-of-icmps.
// Look for this pattern: (icmp V, C0) & (icmp V, C1)).
Type *ITy = Op0->getType();
ICmpInst::Predicate Pred0, Pred1;
@@ -1584,10 +1631,16 @@ static Value *SimplifyAndOfICmps(ICmpInst *Op0, ICmpInst *Op1) {
match(Op1, m_ICmp(Pred1, m_Specific(V), m_APInt(C1)))) {
// Make a constant range that's the intersection of the two icmp ranges.
// If the intersection is empty, we know that the result is false.
- auto Range0 = ConstantRange::makeAllowedICmpRegion(Pred0, *C0);
- auto Range1 = ConstantRange::makeAllowedICmpRegion(Pred1, *C1);
+ auto Range0 = ConstantRange::makeExactICmpRegion(Pred0, *C0);
+ auto Range1 = ConstantRange::makeExactICmpRegion(Pred1, *C1);
if (Range0.intersectWith(Range1).isEmptySet())
return getFalse(ITy);
+
+ // If a range is a superset of the other, the smaller set is all we need.
+ if (Range0.contains(Range1))
+ return Op1;
+ if (Range1.contains(Range0))
+ return Op0;
}
// (icmp (add V, C0), C1) & (icmp V, C0)
@@ -1633,7 +1686,7 @@ static Value *SimplifyAndOfICmps(ICmpInst *Op0, ICmpInst *Op1) {
/// Given operands for an And, see if we can fold the result.
/// If not, this returns null.
-static Value *SimplifyAndInst(Value *Op0, Value *Op1, const Query &Q,
+static Value *SimplifyAndInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
unsigned MaxRecurse) {
if (Constant *C = foldOrCommuteConstant(Instruction::And, Op0, Op1, Q))
return C;
@@ -1744,8 +1797,11 @@ Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const DataLayout &DL,
const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifyAndInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI),
- RecursionLimit);
+ return ::SimplifyAndInst(Op0, Op1, {DL, TLI, DT, AC, CxtI}, RecursionLimit);
+}
+
+Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
+ return ::SimplifyAndInst(Op0, Op1, Q, RecursionLimit);
}
/// Commuted variants are assumed to be handled by calling this function again
@@ -1830,7 +1886,7 @@ static Value *SimplifyOrOfICmps(ICmpInst *Op0, ICmpInst *Op1) {
/// Given operands for an Or, see if we can fold the result.
/// If not, this returns null.
-static Value *SimplifyOrInst(Value *Op0, Value *Op1, const Query &Q,
+static Value *SimplifyOrInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
unsigned MaxRecurse) {
if (Constant *C = foldOrCommuteConstant(Instruction::Or, Op0, Op1, Q))
return C;
@@ -1877,6 +1933,25 @@ static Value *SimplifyOrInst(Value *Op0, Value *Op1, const Query &Q,
(A == Op0 || B == Op0))
return Constant::getAllOnesValue(Op0->getType());
+ // (A & ~B) | (A ^ B) -> (A ^ B)
+ // (~B & A) | (A ^ B) -> (A ^ B)
+ // (A & ~B) | (B ^ A) -> (B ^ A)
+ // (~B & A) | (B ^ A) -> (B ^ A)
+ if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
+ (match(Op0, m_c_And(m_Specific(A), m_Not(m_Specific(B)))) ||
+ match(Op0, m_c_And(m_Not(m_Specific(A)), m_Specific(B)))))
+ return Op1;
+
+ // Commute the 'or' operands.
+ // (A ^ B) | (A & ~B) -> (A ^ B)
+ // (A ^ B) | (~B & A) -> (A ^ B)
+ // (B ^ A) | (A & ~B) -> (B ^ A)
+ // (B ^ A) | (~B & A) -> (B ^ A)
+ if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
+ (match(Op1, m_c_And(m_Specific(A), m_Not(m_Specific(B)))) ||
+ match(Op1, m_c_And(m_Not(m_Specific(A)), m_Specific(B)))))
+ return Op0;
+
if (auto *ICILHS = dyn_cast<ICmpInst>(Op0)) {
if (auto *ICIRHS = dyn_cast<ICmpInst>(Op1)) {
if (Value *V = SimplifyOrOfICmps(ICILHS, ICIRHS))
@@ -1952,13 +2027,16 @@ Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const DataLayout &DL,
const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifyOrInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI),
- RecursionLimit);
+ return ::SimplifyOrInst(Op0, Op1, {DL, TLI, DT, AC, CxtI}, RecursionLimit);
+}
+
+Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
+ return ::SimplifyOrInst(Op0, Op1, Q, RecursionLimit);
}
/// Given operands for a Xor, see if we can fold the result.
/// If not, this returns null.
-static Value *SimplifyXorInst(Value *Op0, Value *Op1, const Query &Q,
+static Value *SimplifyXorInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
unsigned MaxRecurse) {
if (Constant *C = foldOrCommuteConstant(Instruction::Xor, Op0, Op1, Q))
return C;
@@ -2001,10 +2079,14 @@ Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const DataLayout &DL,
const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifyXorInst(Op0, Op1, Query(DL, TLI, DT, AC, CxtI),
- RecursionLimit);
+ return ::SimplifyXorInst(Op0, Op1, {DL, TLI, DT, AC, CxtI}, RecursionLimit);
+}
+
+Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
+ return ::SimplifyXorInst(Op0, Op1, Q, RecursionLimit);
}
+
static Type *GetCompareTy(Value *Op) {
return CmpInst::makeCmpResultType(Op->getType());
}
@@ -2238,7 +2320,7 @@ computePointerICmp(const DataLayout &DL, const TargetLibraryInfo *TLI,
/// Fold an icmp when its operands have i1 scalar type.
static Value *simplifyICmpOfBools(CmpInst::Predicate Pred, Value *LHS,
- Value *RHS, const Query &Q) {
+ Value *RHS, const SimplifyQuery &Q) {
Type *ITy = GetCompareTy(LHS); // The return type.
Type *OpTy = LHS->getType(); // The operand type.
if (!OpTy->getScalarType()->isIntegerTy(1))
@@ -2301,7 +2383,7 @@ static Value *simplifyICmpOfBools(CmpInst::Predicate Pred, Value *LHS,
/// Try hard to fold icmp with zero RHS because this is a common case.
static Value *simplifyICmpWithZero(CmpInst::Predicate Pred, Value *LHS,
- Value *RHS, const Query &Q) {
+ Value *RHS, const SimplifyQuery &Q) {
if (!match(RHS, m_Zero()))
return nullptr;
@@ -2556,7 +2638,7 @@ static Value *simplifyICmpWithConstant(CmpInst::Predicate Pred, Value *LHS,
}
static Value *simplifyICmpWithBinOp(CmpInst::Predicate Pred, Value *LHS,
- Value *RHS, const Query &Q,
+ Value *RHS, const SimplifyQuery &Q,
unsigned MaxRecurse) {
Type *ITy = GetCompareTy(LHS); // The return type.
@@ -2866,7 +2948,7 @@ static Value *simplifyICmpWithBinOp(CmpInst::Predicate Pred, Value *LHS,
/// Simplify integer comparisons where at least one operand of the compare
/// matches an integer min/max idiom.
static Value *simplifyICmpWithMinMax(CmpInst::Predicate Pred, Value *LHS,
- Value *RHS, const Query &Q,
+ Value *RHS, const SimplifyQuery &Q,
unsigned MaxRecurse) {
Type *ITy = GetCompareTy(LHS); // The return type.
Value *A, *B;
@@ -3070,7 +3152,7 @@ static Value *simplifyICmpWithMinMax(CmpInst::Predicate Pred, Value *LHS,
/// Given operands for an ICmpInst, see if we can fold the result.
/// If not, this returns null.
static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
- const Query &Q, unsigned MaxRecurse) {
+ const SimplifyQuery &Q, unsigned MaxRecurse) {
CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
@@ -3342,11 +3424,10 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
const APInt *RHSVal;
if (match(RHS, m_APInt(RHSVal))) {
unsigned BitWidth = RHSVal->getBitWidth();
- APInt LHSKnownZero(BitWidth, 0);
- APInt LHSKnownOne(BitWidth, 0);
- computeKnownBits(LHS, LHSKnownZero, LHSKnownOne, Q.DL, /*Depth=*/0, Q.AC,
- Q.CxtI, Q.DT);
- if (((LHSKnownZero & *RHSVal) != 0) || ((LHSKnownOne & ~(*RHSVal)) != 0))
+ KnownBits LHSKnown(BitWidth);
+ computeKnownBits(LHS, LHSKnown, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT);
+ if (LHSKnown.Zero.intersects(*RHSVal) ||
+ !LHSKnown.One.isSubsetOf(*RHSVal))
return Pred == ICmpInst::ICMP_EQ ? ConstantInt::getFalse(ITy)
: ConstantInt::getTrue(ITy);
}
@@ -3372,14 +3453,19 @@ Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifyICmpInst(Predicate, LHS, RHS, Query(DL, TLI, DT, AC, CxtI),
+ return ::SimplifyICmpInst(Predicate, LHS, RHS, {DL, TLI, DT, AC, CxtI},
RecursionLimit);
}
+Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
+ const SimplifyQuery &Q) {
+ return ::SimplifyICmpInst(Predicate, LHS, RHS, Q, RecursionLimit);
+}
+
/// Given operands for an FCmpInst, see if we can fold the result.
/// If not, this returns null.
static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
- FastMathFlags FMF, const Query &Q,
+ FastMathFlags FMF, const SimplifyQuery &Q,
unsigned MaxRecurse) {
CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
@@ -3505,13 +3591,18 @@ Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifyFCmpInst(Predicate, LHS, RHS, FMF,
- Query(DL, TLI, DT, AC, CxtI), RecursionLimit);
+ return ::SimplifyFCmpInst(Predicate, LHS, RHS, FMF, {DL, TLI, DT, AC, CxtI},
+ RecursionLimit);
+}
+
+Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
+ FastMathFlags FMF, const SimplifyQuery &Q) {
+ return ::SimplifyFCmpInst(Predicate, LHS, RHS, FMF, Q, RecursionLimit);
}
/// See if V simplifies when its operand Op is replaced with RepOp.
static const Value *SimplifyWithOpReplaced(Value *V, Value *Op, Value *RepOp,
- const Query &Q,
+ const SimplifyQuery &Q,
unsigned MaxRecurse) {
// Trivial replacement.
if (V == Op)
@@ -3659,7 +3750,7 @@ static Value *simplifySelectWithFakeICmpEq(Value *CmpLHS, Value *TrueVal,
/// Try to simplify a select instruction when its condition operand is an
/// integer comparison.
static Value *simplifySelectWithICmpCond(Value *CondVal, Value *TrueVal,
- Value *FalseVal, const Query &Q,
+ Value *FalseVal, const SimplifyQuery &Q,
unsigned MaxRecurse) {
ICmpInst::Predicate Pred;
Value *CmpLHS, *CmpRHS;
@@ -3738,7 +3829,7 @@ static Value *simplifySelectWithICmpCond(Value *CondVal, Value *TrueVal,
/// Given operands for a SelectInst, see if we can fold the result.
/// If not, this returns null.
static Value *SimplifySelectInst(Value *CondVal, Value *TrueVal,
- Value *FalseVal, const Query &Q,
+ Value *FalseVal, const SimplifyQuery &Q,
unsigned MaxRecurse) {
// select true, X, Y -> X
// select false, X, Y -> Y
@@ -3775,14 +3866,19 @@ Value *llvm::SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,
const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifySelectInst(Cond, TrueVal, FalseVal,
- Query(DL, TLI, DT, AC, CxtI), RecursionLimit);
+ return ::SimplifySelectInst(Cond, TrueVal, FalseVal, {DL, TLI, DT, AC, CxtI},
+ RecursionLimit);
+}
+
+Value *llvm::SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,
+ const SimplifyQuery &Q) {
+ return ::SimplifySelectInst(Cond, TrueVal, FalseVal, Q, RecursionLimit);
}
/// Given operands for an GetElementPtrInst, see if we can fold the result.
/// If not, this returns null.
static Value *SimplifyGEPInst(Type *SrcTy, ArrayRef<Value *> Ops,
- const Query &Q, unsigned) {
+ const SimplifyQuery &Q, unsigned) {
// The type of the GEP pointer operand.
unsigned AS =
cast<PointerType>(Ops[0]->getType()->getScalarType())->getAddressSpace();
@@ -3896,14 +3992,18 @@ Value *llvm::SimplifyGEPInst(Type *SrcTy, ArrayRef<Value *> Ops,
const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifyGEPInst(SrcTy, Ops,
- Query(DL, TLI, DT, AC, CxtI), RecursionLimit);
+ return ::SimplifyGEPInst(SrcTy, Ops, {DL, TLI, DT, AC, CxtI}, RecursionLimit);
+}
+
+Value *llvm::SimplifyGEPInst(Type *SrcTy, ArrayRef<Value *> Ops,
+ const SimplifyQuery &Q) {
+ return ::SimplifyGEPInst(SrcTy, Ops, Q, RecursionLimit);
}
/// Given operands for an InsertValueInst, see if we can fold the result.
/// If not, this returns null.
static Value *SimplifyInsertValueInst(Value *Agg, Value *Val,
- ArrayRef<unsigned> Idxs, const Query &Q,
+ ArrayRef<unsigned> Idxs, const SimplifyQuery &Q,
unsigned) {
if (Constant *CAgg = dyn_cast<Constant>(Agg))
if (Constant *CVal = dyn_cast<Constant>(Val))
@@ -3933,14 +4033,20 @@ Value *llvm::SimplifyInsertValueInst(
Value *Agg, Value *Val, ArrayRef<unsigned> Idxs, const DataLayout &DL,
const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifyInsertValueInst(Agg, Val, Idxs, Query(DL, TLI, DT, AC, CxtI),
+ return ::SimplifyInsertValueInst(Agg, Val, Idxs, {DL, TLI, DT, AC, CxtI},
RecursionLimit);
}
+Value *llvm::SimplifyInsertValueInst(Value *Agg, Value *Val,
+ ArrayRef<unsigned> Idxs,
+ const SimplifyQuery &Q) {
+ return ::SimplifyInsertValueInst(Agg, Val, Idxs, Q, RecursionLimit);
+}
+
/// Given operands for an ExtractValueInst, see if we can fold the result.
/// If not, this returns null.
static Value *SimplifyExtractValueInst(Value *Agg, ArrayRef<unsigned> Idxs,
- const Query &, unsigned) {
+ const SimplifyQuery &, unsigned) {
if (auto *CAgg = dyn_cast<Constant>(Agg))
return ConstantFoldExtractValueInstruction(CAgg, Idxs);
@@ -3968,13 +4074,18 @@ Value *llvm::SimplifyExtractValueInst(Value *Agg, ArrayRef<unsigned> Idxs,
const DominatorTree *DT,
AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifyExtractValueInst(Agg, Idxs, Query(DL, TLI, DT, AC, CxtI),
+ return ::SimplifyExtractValueInst(Agg, Idxs, {DL, TLI, DT, AC, CxtI},
RecursionLimit);
}
+Value *llvm::SimplifyExtractValueInst(Value *Agg, ArrayRef<unsigned> Idxs,
+ const SimplifyQuery &Q) {
+ return ::SimplifyExtractValueInst(Agg, Idxs, Q, RecursionLimit);
+}
+
/// Given operands for an ExtractElementInst, see if we can fold the result.
/// If not, this returns null.
-static Value *SimplifyExtractElementInst(Value *Vec, Value *Idx, const Query &,
+static Value *SimplifyExtractElementInst(Value *Vec, Value *Idx, const SimplifyQuery &,
unsigned) {
if (auto *CVec = dyn_cast<Constant>(Vec)) {
if (auto *CIdx = dyn_cast<Constant>(Idx))
@@ -4000,12 +4111,17 @@ static Value *SimplifyExtractElementInst(Value *Vec, Value *Idx, const Query &,
Value *llvm::SimplifyExtractElementInst(
Value *Vec, Value *Idx, const DataLayout &DL, const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) {
- return ::SimplifyExtractElementInst(Vec, Idx, Query(DL, TLI, DT, AC, CxtI),
+ return ::SimplifyExtractElementInst(Vec, Idx, {DL, TLI, DT, AC, CxtI},
RecursionLimit);
}
+Value *llvm::SimplifyExtractElementInst(Value *Vec, Value *Idx,
+ const SimplifyQuery &Q) {
+ return ::SimplifyExtractElementInst(Vec, Idx, Q, RecursionLimit);
+}
+
/// See if we can fold the given phi. If not, returns null.
-static Value *SimplifyPHINode(PHINode *PN, const Query &Q) {
+static Value *SimplifyPHINode(PHINode *PN, const SimplifyQuery &Q) {
// If all of the PHI's incoming values are the same then replace the PHI node
// with the common value.
Value *CommonValue = nullptr;
@@ -4038,7 +4154,7 @@ static Value *SimplifyPHINode(PHINode *PN, const Query &Q) {
}
static Value *SimplifyCastInst(unsigned CastOpc, Value *Op,
- Type *Ty, const Query &Q, unsigned MaxRecurse) {
+ Type *Ty, const SimplifyQuery &Q, unsigned MaxRecurse) {
if (auto *C = dyn_cast<Constant>(Op))
return ConstantFoldCastOperand(CastOpc, C, Ty, Q.DL);
@@ -4076,10 +4192,15 @@ Value *llvm::SimplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty,
const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifyCastInst(CastOpc, Op, Ty, Query(DL, TLI, DT, AC, CxtI),
+ return ::SimplifyCastInst(CastOpc, Op, Ty, {DL, TLI, DT, AC, CxtI},
RecursionLimit);
}
+Value *llvm::SimplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty,
+ const SimplifyQuery &Q) {
+ return ::SimplifyCastInst(CastOpc, Op, Ty, Q, RecursionLimit);
+}
+
/// For the given destination element of a shuffle, peek through shuffles to
/// match a root vector source operand that contains that element in the same
/// vector lane (ie, the same mask index), so we can eliminate the shuffle(s).
@@ -4135,7 +4256,7 @@ static Value *foldIdentityShuffles(int DestElt, Value *Op0, Value *Op1,
}
static Value *SimplifyShuffleVectorInst(Value *Op0, Value *Op1, Constant *Mask,
- Type *RetTy, const Query &Q,
+ Type *RetTy, const SimplifyQuery &Q,
unsigned MaxRecurse) {
Type *InVecTy = Op0->getType();
unsigned MaskNumElts = Mask->getType()->getVectorNumElements();
@@ -4207,8 +4328,13 @@ Value *llvm::SimplifyShuffleVectorInst(
Value *Op0, Value *Op1, Constant *Mask, Type *RetTy,
const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT,
AssumptionCache *AC, const Instruction *CxtI) {
- return ::SimplifyShuffleVectorInst(
- Op0, Op1, Mask, RetTy, Query(DL, TLI, DT, AC, CxtI), RecursionLimit);
+ return ::SimplifyShuffleVectorInst(Op0, Op1, Mask, RetTy,
+ {DL, TLI, DT, AC, CxtI}, RecursionLimit);
+}
+
+Value *llvm::SimplifyShuffleVectorInst(Value *Op0, Value *Op1, Constant *Mask,
+ Type *RetTy, const SimplifyQuery &Q) {
+ return ::SimplifyShuffleVectorInst(Op0, Op1, Mask, RetTy, Q, RecursionLimit);
}
//=== Helper functions for higher up the class hierarchy.
@@ -4216,7 +4342,7 @@ Value *llvm::SimplifyShuffleVectorInst(
/// Given operands for a BinaryOperator, see if we can fold the result.
/// If not, this returns null.
static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
- const Query &Q, unsigned MaxRecurse) {
+ const SimplifyQuery &Q, unsigned MaxRecurse) {
switch (Opcode) {
case Instruction::Add:
return SimplifyAddInst(LHS, RHS, false, false, Q, MaxRecurse);
@@ -4264,7 +4390,7 @@ static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
/// In contrast to SimplifyBinOp, try to use FastMathFlag when folding the
/// result. In case we don't need FastMathFlags, simply fall to SimplifyBinOp.
static Value *SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS,
- const FastMathFlags &FMF, const Query &Q,
+ const FastMathFlags &FMF, const SimplifyQuery &Q,
unsigned MaxRecurse) {
switch (Opcode) {
case Instruction::FAdd:
@@ -4284,22 +4410,32 @@ Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
const DataLayout &DL, const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifyBinOp(Opcode, LHS, RHS, Query(DL, TLI, DT, AC, CxtI),
+ return ::SimplifyBinOp(Opcode, LHS, RHS, {DL, TLI, DT, AC, CxtI},
RecursionLimit);
}
+Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
+ const SimplifyQuery &Q) {
+ return ::SimplifyBinOp(Opcode, LHS, RHS, Q, RecursionLimit);
+}
+
Value *llvm::SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS,
- const FastMathFlags &FMF, const DataLayout &DL,
+ FastMathFlags FMF, const DataLayout &DL,
const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifyFPBinOp(Opcode, LHS, RHS, FMF, Query(DL, TLI, DT, AC, CxtI),
+ return ::SimplifyFPBinOp(Opcode, LHS, RHS, FMF, {DL, TLI, DT, AC, CxtI},
RecursionLimit);
}
+Value *llvm::SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS,
+ FastMathFlags FMF, const SimplifyQuery &Q) {
+ return ::SimplifyFPBinOp(Opcode, LHS, RHS, FMF, Q, RecursionLimit);
+}
+
/// Given operands for a CmpInst, see if we can fold the result.
static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
- const Query &Q, unsigned MaxRecurse) {
+ const SimplifyQuery &Q, unsigned MaxRecurse) {
if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
return SimplifyICmpInst(Predicate, LHS, RHS, Q, MaxRecurse);
return SimplifyFCmpInst(Predicate, LHS, RHS, FastMathFlags(), Q, MaxRecurse);
@@ -4309,10 +4445,15 @@ Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
const DataLayout &DL, const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifyCmpInst(Predicate, LHS, RHS, Query(DL, TLI, DT, AC, CxtI),
+ return ::SimplifyCmpInst(Predicate, LHS, RHS, {DL, TLI, DT, AC, CxtI},
RecursionLimit);
}
+Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
+ const SimplifyQuery &Q) {
+ return ::SimplifyCmpInst(Predicate, LHS, RHS, Q, RecursionLimit);
+}
+
static bool IsIdempotent(Intrinsic::ID ID) {
switch (ID) {
default: return false;
@@ -4403,7 +4544,7 @@ static bool maskIsAllZeroOrUndef(Value *Mask) {
template <typename IterTy>
static Value *SimplifyIntrinsic(Function *F, IterTy ArgBegin, IterTy ArgEnd,
- const Query &Q, unsigned MaxRecurse) {
+ const SimplifyQuery &Q, unsigned MaxRecurse) {
Intrinsic::ID IID = F->getIntrinsicID();
unsigned NumOperands = std::distance(ArgBegin, ArgEnd);
@@ -4497,7 +4638,7 @@ static Value *SimplifyIntrinsic(Function *F, IterTy ArgBegin, IterTy ArgEnd,
template <typename IterTy>
static Value *SimplifyCall(Value *V, IterTy ArgBegin, IterTy ArgEnd,
- const Query &Q, unsigned MaxRecurse) {
+ const SimplifyQuery &Q, unsigned MaxRecurse) {
Type *Ty = V->getType();
if (PointerType *PTy = dyn_cast<PointerType>(Ty))
Ty = PTy->getElementType();
@@ -4535,16 +4676,26 @@ Value *llvm::SimplifyCall(Value *V, User::op_iterator ArgBegin,
User::op_iterator ArgEnd, const DataLayout &DL,
const TargetLibraryInfo *TLI, const DominatorTree *DT,
AssumptionCache *AC, const Instruction *CxtI) {
- return ::SimplifyCall(V, ArgBegin, ArgEnd, Query(DL, TLI, DT, AC, CxtI),
+ return ::SimplifyCall(V, ArgBegin, ArgEnd, {DL, TLI, DT, AC, CxtI},
RecursionLimit);
}
+Value *llvm::SimplifyCall(Value *V, User::op_iterator ArgBegin,
+ User::op_iterator ArgEnd, const SimplifyQuery &Q) {
+ return ::SimplifyCall(V, ArgBegin, ArgEnd, Q, RecursionLimit);
+}
+
Value *llvm::SimplifyCall(Value *V, ArrayRef<Value *> Args,
const DataLayout &DL, const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
const Instruction *CxtI) {
- return ::SimplifyCall(V, Args.begin(), Args.end(),
- Query(DL, TLI, DT, AC, CxtI), RecursionLimit);
+ return ::SimplifyCall(V, Args.begin(), Args.end(), {DL, TLI, DT, AC, CxtI},
+ RecursionLimit);
+}
+
+Value *llvm::SimplifyCall(Value *V, ArrayRef<Value *> Args,
+ const SimplifyQuery &Q) {
+ return ::SimplifyCall(V, Args.begin(), Args.end(), Q, RecursionLimit);
}
/// See if we can compute a simplified version of this instruction.
@@ -4553,152 +4704,141 @@ Value *llvm::SimplifyInstruction(Instruction *I, const DataLayout &DL,
const TargetLibraryInfo *TLI,
const DominatorTree *DT, AssumptionCache *AC,
OptimizationRemarkEmitter *ORE) {
+ return SimplifyInstruction(I, {DL, TLI, DT, AC, I}, ORE);
+}
+
+Value *llvm::SimplifyInstruction(Instruction *I, const SimplifyQuery &Q,
+ OptimizationRemarkEmitter *ORE) {
Value *Result;
switch (I->getOpcode()) {
default:
- Result = ConstantFoldInstruction(I, DL, TLI);
+ Result = ConstantFoldInstruction(I, Q.DL, Q.TLI);
break;
case Instruction::FAdd:
Result = SimplifyFAddInst(I->getOperand(0), I->getOperand(1),
- I->getFastMathFlags(), DL, TLI, DT, AC, I);
+ I->getFastMathFlags(), Q);
break;
case Instruction::Add:
Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1),
cast<BinaryOperator>(I)->hasNoSignedWrap(),
- cast<BinaryOperator>(I)->hasNoUnsignedWrap(), DL,
- TLI, DT, AC, I);
+ cast<BinaryOperator>(I)->hasNoUnsignedWrap(), Q);
break;
case Instruction::FSub:
Result = SimplifyFSubInst(I->getOperand(0), I->getOperand(1),
- I->getFastMathFlags(), DL, TLI, DT, AC, I);
+ I->getFastMathFlags(), Q);
break;
case Instruction::Sub:
Result = SimplifySubInst(I->getOperand(0), I->getOperand(1),
cast<BinaryOperator>(I)->hasNoSignedWrap(),
- cast<BinaryOperator>(I)->hasNoUnsignedWrap(), DL,
- TLI, DT, AC, I);
+ cast<BinaryOperator>(I)->hasNoUnsignedWrap(), Q);
break;
case Instruction::FMul:
Result = SimplifyFMulInst(I->getOperand(0), I->getOperand(1),
- I->getFastMathFlags(), DL, TLI, DT, AC, I);
+ I->getFastMathFlags(), Q);
break;
case Instruction::Mul:
- Result =
- SimplifyMulInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, AC, I);
+ Result = SimplifyMulInst(I->getOperand(0), I->getOperand(1), Q);
break;
case Instruction::SDiv:
- Result = SimplifySDivInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT,
- AC, I);
+ Result = SimplifySDivInst(I->getOperand(0), I->getOperand(1), Q);
break;
case Instruction::UDiv:
- Result = SimplifyUDivInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT,
- AC, I);
+ Result = SimplifyUDivInst(I->getOperand(0), I->getOperand(1), Q);
break;
case Instruction::FDiv:
Result = SimplifyFDivInst(I->getOperand(0), I->getOperand(1),
- I->getFastMathFlags(), DL, TLI, DT, AC, I);
+ I->getFastMathFlags(), Q);
break;
case Instruction::SRem:
- Result = SimplifySRemInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT,
- AC, I);
+ Result = SimplifySRemInst(I->getOperand(0), I->getOperand(1), Q);
break;
case Instruction::URem:
- Result = SimplifyURemInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT,
- AC, I);
+ Result = SimplifyURemInst(I->getOperand(0), I->getOperand(1), Q);
break;
case Instruction::FRem:
Result = SimplifyFRemInst(I->getOperand(0), I->getOperand(1),
- I->getFastMathFlags(), DL, TLI, DT, AC, I);
+ I->getFastMathFlags(), Q);
break;
case Instruction::Shl:
Result = SimplifyShlInst(I->getOperand(0), I->getOperand(1),
cast<BinaryOperator>(I)->hasNoSignedWrap(),
- cast<BinaryOperator>(I)->hasNoUnsignedWrap(), DL,
- TLI, DT, AC, I);
+ cast<BinaryOperator>(I)->hasNoUnsignedWrap(), Q);
break;
case Instruction::LShr:
Result = SimplifyLShrInst(I->getOperand(0), I->getOperand(1),
- cast<BinaryOperator>(I)->isExact(), DL, TLI, DT,
- AC, I);
+ cast<BinaryOperator>(I)->isExact(), Q);
break;
case Instruction::AShr:
Result = SimplifyAShrInst(I->getOperand(0), I->getOperand(1),
- cast<BinaryOperator>(I)->isExact(), DL, TLI, DT,
- AC, I);
+ cast<BinaryOperator>(I)->isExact(), Q);
break;
case Instruction::And:
- Result =
- SimplifyAndInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, AC, I);
+ Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), Q);
break;
case Instruction::Or:
- Result =
- SimplifyOrInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, AC, I);
+ Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), Q);
break;
case Instruction::Xor:
- Result =
- SimplifyXorInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT, AC, I);
+ Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), Q);
break;
case Instruction::ICmp:
- Result =
- SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(), I->getOperand(0),
- I->getOperand(1), DL, TLI, DT, AC, I);
+ Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
+ I->getOperand(0), I->getOperand(1), Q);
break;
case Instruction::FCmp:
- Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(),
- I->getOperand(0), I->getOperand(1),
- I->getFastMathFlags(), DL, TLI, DT, AC, I);
+ Result =
+ SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(), I->getOperand(0),
+ I->getOperand(1), I->getFastMathFlags(), Q);
break;
case Instruction::Select:
Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1),
- I->getOperand(2), DL, TLI, DT, AC, I);
+ I->getOperand(2), Q);
break;
case Instruction::GetElementPtr: {
- SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
+ SmallVector<Value *, 8> Ops(I->op_begin(), I->op_end());
Result = SimplifyGEPInst(cast<GetElementPtrInst>(I)->getSourceElementType(),
- Ops, DL, TLI, DT, AC, I);
+ Ops, Q);
break;
}
case Instruction::InsertValue: {
InsertValueInst *IV = cast<InsertValueInst>(I);
Result = SimplifyInsertValueInst(IV->getAggregateOperand(),
IV->getInsertedValueOperand(),
- IV->getIndices(), DL, TLI, DT, AC, I);
+ IV->getIndices(), Q);
break;
}
case Instruction::ExtractValue: {
auto *EVI = cast<ExtractValueInst>(I);
Result = SimplifyExtractValueInst(EVI->getAggregateOperand(),
- EVI->getIndices(), DL, TLI, DT, AC, I);
+ EVI->getIndices(), Q);
break;
}
case Instruction::ExtractElement: {
auto *EEI = cast<ExtractElementInst>(I);
- Result = SimplifyExtractElementInst(
- EEI->getVectorOperand(), EEI->getIndexOperand(), DL, TLI, DT, AC, I);
+ Result = SimplifyExtractElementInst(EEI->getVectorOperand(),
+ EEI->getIndexOperand(), Q);
break;
}
case Instruction::ShuffleVector: {
auto *SVI = cast<ShuffleVectorInst>(I);
Result = SimplifyShuffleVectorInst(SVI->getOperand(0), SVI->getOperand(1),
- SVI->getMask(), SVI->getType(), DL, TLI,
- DT, AC, I);
+ SVI->getMask(), SVI->getType(), Q);
break;
}
case Instruction::PHI:
- Result = SimplifyPHINode(cast<PHINode>(I), Query(DL, TLI, DT, AC, I));
+ Result = SimplifyPHINode(cast<PHINode>(I), Q);
break;
case Instruction::Call: {
CallSite CS(cast<CallInst>(I));
- Result = SimplifyCall(CS.getCalledValue(), CS.arg_begin(), CS.arg_end(), DL,
- TLI, DT, AC, I);
+ Result = SimplifyCall(CS.getCalledValue(), CS.arg_begin(), CS.arg_end(), Q);
break;
}
#define HANDLE_CAST_INST(num, opc, clas) case Instruction::opc:
#include "llvm/IR/Instruction.def"
#undef HANDLE_CAST_INST
- Result = SimplifyCastInst(I->getOpcode(), I->getOperand(0), I->getType(),
- DL, TLI, DT, AC, I);
+ Result =
+ SimplifyCastInst(I->getOpcode(), I->getOperand(0), I->getType(), Q);
break;
case Instruction::Alloca:
// No simplifications for Alloca and it can't be constant folded.
@@ -4710,11 +4850,10 @@ Value *llvm::SimplifyInstruction(Instruction *I, const DataLayout &DL,
// value even when the operands are not all constants.
if (!Result && I->getType()->isIntOrIntVectorTy()) {
unsigned BitWidth = I->getType()->getScalarSizeInBits();
- APInt KnownZero(BitWidth, 0);
- APInt KnownOne(BitWidth, 0);
- computeKnownBits(I, KnownZero, KnownOne, DL, /*Depth*/0, AC, I, DT, ORE);
- if ((KnownZero | KnownOne).isAllOnesValue())
- Result = ConstantInt::get(I->getType(), KnownOne);
+ KnownBits Known(BitWidth);
+ computeKnownBits(I, Known, Q.DL, /*Depth*/ 0, Q.AC, I, Q.DT, ORE);
+ if ((Known.Zero | Known.One).isAllOnesValue())
+ Result = ConstantInt::get(I->getType(), Known.One);
}
/// If called on unreachable code, the above logic may report that the
diff --git a/lib/Analysis/Lint.cpp b/lib/Analysis/Lint.cpp
index 2ca46b1fe872..0f04af54cdc7 100644
--- a/lib/Analysis/Lint.cpp
+++ b/lib/Analysis/Lint.cpp
@@ -70,6 +70,7 @@
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/KnownBits.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
@@ -534,10 +535,9 @@ static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT,
VectorType *VecTy = dyn_cast<VectorType>(V->getType());
if (!VecTy) {
unsigned BitWidth = V->getType()->getIntegerBitWidth();
- APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
- computeKnownBits(V, KnownZero, KnownOne, DL, 0, AC,
- dyn_cast<Instruction>(V), DT);
- return KnownZero.isAllOnesValue();
+ KnownBits Known(BitWidth);
+ computeKnownBits(V, Known, DL, 0, AC, dyn_cast<Instruction>(V), DT);
+ return Known.Zero.isAllOnesValue();
}
// Per-component check doesn't work with zeroinitializer
@@ -556,9 +556,9 @@ static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT,
if (isa<UndefValue>(Elem))
return true;
- APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
- computeKnownBits(Elem, KnownZero, KnownOne, DL);
- if (KnownZero.isAllOnesValue())
+ KnownBits Known(BitWidth);
+ computeKnownBits(Elem, Known, DL);
+ if (Known.Zero.isAllOnesValue())
return true;
}
diff --git a/lib/Analysis/MemorySSAUpdater.cpp b/lib/Analysis/MemorySSAUpdater.cpp
index c63677fe5502..da5c79ab6c81 100644
--- a/lib/Analysis/MemorySSAUpdater.cpp
+++ b/lib/Analysis/MemorySSAUpdater.cpp
@@ -29,7 +29,7 @@
#define DEBUG_TYPE "memoryssa"
using namespace llvm;
-namespace llvm {
+
// This is the marker algorithm from "Simple and Efficient Construction of
// Static Single Assignment Form"
// The simple, non-marker algorithm places phi nodes at any join
@@ -211,8 +211,8 @@ void MemorySSAUpdater::insertUse(MemoryUse *MU) {
}
// Set every incoming edge {BB, MP->getBlock()} of MemoryPhi MP to NewDef.
-void setMemoryPhiValueForBlock(MemoryPhi *MP, const BasicBlock *BB,
- MemoryAccess *NewDef) {
+static void setMemoryPhiValueForBlock(MemoryPhi *MP, const BasicBlock *BB,
+ MemoryAccess *NewDef) {
// Replace any operand with us an incoming block with the new defining
// access.
int i = MP->getBasicBlockIndex(BB);
@@ -415,6 +415,7 @@ static MemoryAccess *onlySingleValue(MemoryPhi *MP) {
}
return MA;
}
+
void MemorySSAUpdater::removeMemoryAccess(MemoryAccess *MA) {
assert(!MSSA->isLiveOnEntryDef(MA) &&
"Trying to remove the live on entry def");
@@ -490,5 +491,3 @@ MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessAfter(
++InsertPt->getIterator());
return NewAccess;
}
-
-} // namespace llvm
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 700c383a9dd4..3ac4bf1276eb 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -89,6 +89,7 @@
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/KnownBits.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Support/SaveAndRestore.h"
@@ -4575,10 +4576,10 @@ uint32_t ScalarEvolution::GetMinTrailingZerosImpl(const SCEV *S) {
if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
// For a SCEVUnknown, ask ValueTracking.
unsigned BitWidth = getTypeSizeInBits(U->getType());
- APInt Zeros(BitWidth, 0), Ones(BitWidth, 0);
- computeKnownBits(U->getValue(), Zeros, Ones, getDataLayout(), 0, &AC,
+ KnownBits Known(BitWidth);
+ computeKnownBits(U->getValue(), Known, getDataLayout(), 0, &AC,
nullptr, &DT);
- return Zeros.countTrailingOnes();
+ return Known.Zero.countTrailingOnes();
}
// SCEVUDivExpr
@@ -4757,11 +4758,12 @@ ScalarEvolution::getRange(const SCEV *S,
const DataLayout &DL = getDataLayout();
if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
// For a SCEVUnknown, ask ValueTracking.
- APInt Zeros(BitWidth, 0), Ones(BitWidth, 0);
- computeKnownBits(U->getValue(), Zeros, Ones, DL, 0, &AC, nullptr, &DT);
- if (Ones != ~Zeros + 1)
+ KnownBits Known(BitWidth);
+ computeKnownBits(U->getValue(), Known, DL, 0, &AC, nullptr, &DT);
+ if (Known.One != ~Known.Zero + 1)
ConservativeResult =
- ConservativeResult.intersectWith(ConstantRange(Ones, ~Zeros + 1));
+ ConservativeResult.intersectWith(ConstantRange(Known.One,
+ ~Known.Zero + 1));
} else {
assert(SignHint == ScalarEvolution::HINT_RANGE_SIGNED &&
"generalize as needed!");
@@ -5292,13 +5294,13 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) {
unsigned LZ = A.countLeadingZeros();
unsigned TZ = A.countTrailingZeros();
unsigned BitWidth = A.getBitWidth();
- APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
- computeKnownBits(BO->LHS, KnownZero, KnownOne, getDataLayout(),
+ KnownBits Known(BitWidth);
+ computeKnownBits(BO->LHS, Known, getDataLayout(),
0, &AC, nullptr, &DT);
APInt EffectiveMask =
APInt::getLowBitsSet(BitWidth, BitWidth - LZ - TZ).shl(TZ);
- if ((LZ != 0 || TZ != 0) && !((~A & ~KnownZero) & EffectiveMask)) {
+ if ((LZ != 0 || TZ != 0) && !((~A & ~Known.Zero) & EffectiveMask)) {
const SCEV *MulCount = getConstant(APInt::getOneBitSet(BitWidth, TZ));
const SCEV *LHS = getSCEV(BO->LHS);
const SCEV *ShiftedLHS = nullptr;
@@ -5328,12 +5330,28 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) {
break;
case Instruction::Or:
- // Use ValueTracking to check whether this is actually an add.
- if (haveNoCommonBitsSet(BO->LHS, BO->RHS, getDataLayout(), &AC,
- nullptr, &DT)) {
- // There aren't any common bits set, so the add can't wrap.
- auto Flags = SCEV::NoWrapFlags(SCEV::FlagNUW | SCEV::FlagNSW);
- return getAddExpr(getSCEV(BO->LHS), getSCEV(BO->RHS), Flags);
+ // If the RHS of the Or is a constant, we may have something like:
+ // X*4+1 which got turned into X*4|1. Handle this as an Add so loop
+ // optimizations will transparently handle this case.
+ //
+ // In order for this transformation to be safe, the LHS must be of the
+ // form X*(2^n) and the Or constant must be less than 2^n.
+ if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->RHS)) {
+ const SCEV *LHS = getSCEV(BO->LHS);
+ const APInt &CIVal = CI->getValue();
+ if (GetMinTrailingZeros(LHS) >=
+ (CIVal.getBitWidth() - CIVal.countLeadingZeros())) {
+ // Build a plain add SCEV.
+ const SCEV *S = getAddExpr(LHS, getSCEV(CI));
+ // If the LHS of the add was an addrec and it has no-wrap flags,
+ // transfer the no-wrap flags, since an or won't introduce a wrap.
+ if (const SCEVAddRecExpr *NewAR = dyn_cast<SCEVAddRecExpr>(S)) {
+ const SCEVAddRecExpr *OldAR = cast<SCEVAddRecExpr>(LHS);
+ const_cast<SCEVAddRecExpr *>(NewAR)->setNoWrapFlags(
+ OldAR->getNoWrapFlags());
+ }
+ return S;
+ }
}
break;
@@ -6063,24 +6081,74 @@ ScalarEvolution::computeExitLimit(const Loop *L, BasicBlock *ExitingBlock,
return getCouldNotCompute();
}
-ScalarEvolution::ExitLimit
-ScalarEvolution::computeExitLimitFromCond(const Loop *L,
- Value *ExitCond,
- BasicBlock *TBB,
- BasicBlock *FBB,
- bool ControlsExit,
- bool AllowPredicates) {
+ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCond(
+ const Loop *L, Value *ExitCond, BasicBlock *TBB, BasicBlock *FBB,
+ bool ControlsExit, bool AllowPredicates) {
+ ScalarEvolution::ExitLimitCacheTy Cache(L, TBB, FBB, AllowPredicates);
+ return computeExitLimitFromCondCached(Cache, L, ExitCond, TBB, FBB,
+ ControlsExit, AllowPredicates);
+}
+
+Optional<ScalarEvolution::ExitLimit>
+ScalarEvolution::ExitLimitCache::find(const Loop *L, Value *ExitCond,
+ BasicBlock *TBB, BasicBlock *FBB,
+ bool ControlsExit, bool AllowPredicates) {
+ (void)this->L;
+ (void)this->TBB;
+ (void)this->FBB;
+ (void)this->AllowPredicates;
+
+ assert(this->L == L && this->TBB == TBB && this->FBB == FBB &&
+ this->AllowPredicates == AllowPredicates &&
+ "Variance in assumed invariant key components!");
+ auto Itr = TripCountMap.find({ExitCond, ControlsExit});
+ if (Itr == TripCountMap.end())
+ return None;
+ return Itr->second;
+}
+
+void ScalarEvolution::ExitLimitCache::insert(const Loop *L, Value *ExitCond,
+ BasicBlock *TBB, BasicBlock *FBB,
+ bool ControlsExit,
+ bool AllowPredicates,
+ const ExitLimit &EL) {
+ assert(this->L == L && this->TBB == TBB && this->FBB == FBB &&
+ this->AllowPredicates == AllowPredicates &&
+ "Variance in assumed invariant key components!");
+
+ auto InsertResult = TripCountMap.insert({{ExitCond, ControlsExit}, EL});
+ assert(InsertResult.second && "Expected successful insertion!");
+ (void)InsertResult;
+}
+
+ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
+ ExitLimitCacheTy &Cache, const Loop *L, Value *ExitCond, BasicBlock *TBB,
+ BasicBlock *FBB, bool ControlsExit, bool AllowPredicates) {
+
+ if (auto MaybeEL =
+ Cache.find(L, ExitCond, TBB, FBB, ControlsExit, AllowPredicates))
+ return *MaybeEL;
+
+ ExitLimit EL = computeExitLimitFromCondImpl(Cache, L, ExitCond, TBB, FBB,
+ ControlsExit, AllowPredicates);
+ Cache.insert(L, ExitCond, TBB, FBB, ControlsExit, AllowPredicates, EL);
+ return EL;
+}
+
+ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
+ ExitLimitCacheTy &Cache, const Loop *L, Value *ExitCond, BasicBlock *TBB,
+ BasicBlock *FBB, bool ControlsExit, bool AllowPredicates) {
// Check if the controlling expression for this loop is an And or Or.
if (BinaryOperator *BO = dyn_cast<BinaryOperator>(ExitCond)) {
if (BO->getOpcode() == Instruction::And) {
// Recurse on the operands of the and.
bool EitherMayExit = L->contains(TBB);
- ExitLimit EL0 = computeExitLimitFromCond(L, BO->getOperand(0), TBB, FBB,
- ControlsExit && !EitherMayExit,
- AllowPredicates);
- ExitLimit EL1 = computeExitLimitFromCond(L, BO->getOperand(1), TBB, FBB,
- ControlsExit && !EitherMayExit,
- AllowPredicates);
+ ExitLimit EL0 = computeExitLimitFromCondCached(
+ Cache, L, BO->getOperand(0), TBB, FBB, ControlsExit && !EitherMayExit,
+ AllowPredicates);
+ ExitLimit EL1 = computeExitLimitFromCondCached(
+ Cache, L, BO->getOperand(1), TBB, FBB, ControlsExit && !EitherMayExit,
+ AllowPredicates);
const SCEV *BECount = getCouldNotCompute();
const SCEV *MaxBECount = getCouldNotCompute();
if (EitherMayExit) {
@@ -6124,12 +6192,12 @@ ScalarEvolution::computeExitLimitFromCond(const Loop *L,
if (BO->getOpcode() == Instruction::Or) {
// Recurse on the operands of the or.
bool EitherMayExit = L->contains(FBB);
- ExitLimit EL0 = computeExitLimitFromCond(L, BO->getOperand(0), TBB, FBB,
- ControlsExit && !EitherMayExit,
- AllowPredicates);
- ExitLimit EL1 = computeExitLimitFromCond(L, BO->getOperand(1), TBB, FBB,
- ControlsExit && !EitherMayExit,
- AllowPredicates);
+ ExitLimit EL0 = computeExitLimitFromCondCached(
+ Cache, L, BO->getOperand(0), TBB, FBB, ControlsExit && !EitherMayExit,
+ AllowPredicates);
+ ExitLimit EL1 = computeExitLimitFromCondCached(
+ Cache, L, BO->getOperand(1), TBB, FBB, ControlsExit && !EitherMayExit,
+ AllowPredicates);
const SCEV *BECount = getCouldNotCompute();
const SCEV *MaxBECount = getCouldNotCompute();
if (EitherMayExit) {
@@ -10221,84 +10289,75 @@ void ScalarEvolution::forgetMemoizedResults(const SCEV *S) {
RemoveSCEVFromBackedgeMap(PredicatedBackedgeTakenCounts);
}
-typedef DenseMap<const Loop *, std::string> VerifyMap;
+void ScalarEvolution::verify() const {
+ ScalarEvolution &SE = *const_cast<ScalarEvolution *>(this);
+ ScalarEvolution SE2(F, TLI, AC, DT, LI);
-/// replaceSubString - Replaces all occurrences of From in Str with To.
-static void replaceSubString(std::string &Str, StringRef From, StringRef To) {
- size_t Pos = 0;
- while ((Pos = Str.find(From, Pos)) != std::string::npos) {
- Str.replace(Pos, From.size(), To.data(), To.size());
- Pos += To.size();
- }
-}
+ SmallVector<Loop *, 8> LoopStack(LI.begin(), LI.end());
-/// getLoopBackedgeTakenCounts - Helper method for verifyAnalysis.
-static void
-getLoopBackedgeTakenCounts(Loop *L, VerifyMap &Map, ScalarEvolution &SE) {
- std::string &S = Map[L];
- if (S.empty()) {
- raw_string_ostream OS(S);
- SE.getBackedgeTakenCount(L)->print(OS);
+ // Map's SCEV expressions from one ScalarEvolution "universe" to another.
+ struct SCEVMapper : public SCEVRewriteVisitor<SCEVMapper> {
+ const SCEV *visitConstant(const SCEVConstant *Constant) {
+ return SE.getConstant(Constant->getAPInt());
+ }
+ const SCEV *visitUnknown(const SCEVUnknown *Expr) {
+ return SE.getUnknown(Expr->getValue());
+ }
- // false and 0 are semantically equivalent. This can happen in dead loops.
- replaceSubString(OS.str(), "false", "0");
- // Remove wrap flags, their use in SCEV is highly fragile.
- // FIXME: Remove this when SCEV gets smarter about them.
- replaceSubString(OS.str(), "<nw>", "");
- replaceSubString(OS.str(), "<nsw>", "");
- replaceSubString(OS.str(), "<nuw>", "");
- }
+ const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) {
+ return SE.getCouldNotCompute();
+ }
+ SCEVMapper(ScalarEvolution &SE) : SCEVRewriteVisitor<SCEVMapper>(SE) {}
+ };
- for (auto *R : reverse(*L))
- getLoopBackedgeTakenCounts(R, Map, SE); // recurse.
-}
+ SCEVMapper SCM(SE2);
-void ScalarEvolution::verify() const {
- ScalarEvolution &SE = *const_cast<ScalarEvolution *>(this);
+ while (!LoopStack.empty()) {
+ auto *L = LoopStack.pop_back_val();
+ LoopStack.insert(LoopStack.end(), L->begin(), L->end());
- // Gather stringified backedge taken counts for all loops using SCEV's caches.
- // FIXME: It would be much better to store actual values instead of strings,
- // but SCEV pointers will change if we drop the caches.
- VerifyMap BackedgeDumpsOld, BackedgeDumpsNew;
- for (LoopInfo::reverse_iterator I = LI.rbegin(), E = LI.rend(); I != E; ++I)
- getLoopBackedgeTakenCounts(*I, BackedgeDumpsOld, SE);
+ auto *CurBECount = SCM.visit(
+ const_cast<ScalarEvolution *>(this)->getBackedgeTakenCount(L));
+ auto *NewBECount = SE2.getBackedgeTakenCount(L);
- // Gather stringified backedge taken counts for all loops using a fresh
- // ScalarEvolution object.
- ScalarEvolution SE2(F, TLI, AC, DT, LI);
- for (LoopInfo::reverse_iterator I = LI.rbegin(), E = LI.rend(); I != E; ++I)
- getLoopBackedgeTakenCounts(*I, BackedgeDumpsNew, SE2);
+ if (CurBECount == SE2.getCouldNotCompute() ||
+ NewBECount == SE2.getCouldNotCompute()) {
+ // NB! This situation is legal, but is very suspicious -- whatever pass
+ // change the loop to make a trip count go from could not compute to
+ // computable or vice-versa *should have* invalidated SCEV. However, we
+ // choose not to assert here (for now) since we don't want false
+ // positives.
+ continue;
+ }
- // Now compare whether they're the same with and without caches. This allows
- // verifying that no pass changed the cache.
- assert(BackedgeDumpsOld.size() == BackedgeDumpsNew.size() &&
- "New loops suddenly appeared!");
+ if (containsUndefs(CurBECount) || containsUndefs(NewBECount)) {
+ // SCEV treats "undef" as an unknown but consistent value (i.e. it does
+ // not propagate undef aggressively). This means we can (and do) fail
+ // verification in cases where a transform makes the trip count of a loop
+ // go from "undef" to "undef+1" (say). The transform is fine, since in
+ // both cases the loop iterates "undef" times, but SCEV thinks we
+ // increased the trip count of the loop by 1 incorrectly.
+ continue;
+ }
- for (VerifyMap::iterator OldI = BackedgeDumpsOld.begin(),
- OldE = BackedgeDumpsOld.end(),
- NewI = BackedgeDumpsNew.begin();
- OldI != OldE; ++OldI, ++NewI) {
- assert(OldI->first == NewI->first && "Loop order changed!");
+ if (SE.getTypeSizeInBits(CurBECount->getType()) >
+ SE.getTypeSizeInBits(NewBECount->getType()))
+ NewBECount = SE2.getZeroExtendExpr(NewBECount, CurBECount->getType());
+ else if (SE.getTypeSizeInBits(CurBECount->getType()) <
+ SE.getTypeSizeInBits(NewBECount->getType()))
+ CurBECount = SE2.getZeroExtendExpr(CurBECount, NewBECount->getType());
- // Compare the stringified SCEVs. We don't care if undef backedgetaken count
- // changes.
- // FIXME: We currently ignore SCEV changes from/to CouldNotCompute. This
- // means that a pass is buggy or SCEV has to learn a new pattern but is
- // usually not harmful.
- if (OldI->second != NewI->second &&
- OldI->second.find("undef") == std::string::npos &&
- NewI->second.find("undef") == std::string::npos &&
- OldI->second != "***COULDNOTCOMPUTE***" &&
- NewI->second != "***COULDNOTCOMPUTE***") {
- dbgs() << "SCEVValidator: SCEV for loop '"
- << OldI->first->getHeader()->getName()
- << "' changed from '" << OldI->second
- << "' to '" << NewI->second << "'!\n";
+ auto *ConstantDelta =
+ dyn_cast<SCEVConstant>(SE2.getMinusSCEV(CurBECount, NewBECount));
+
+ if (ConstantDelta && ConstantDelta->getAPInt() != 0) {
+ dbgs() << "Trip Count Changed!\n";
+ dbgs() << "Old: " << *CurBECount << "\n";
+ dbgs() << "New: " << *NewBECount << "\n";
+ dbgs() << "Delta: " << *ConstantDelta << "\n";
std::abort();
}
}
-
- // TODO: Verify more things.
}
bool ScalarEvolution::invalidate(
diff --git a/lib/Analysis/ScalarEvolutionNormalization.cpp b/lib/Analysis/ScalarEvolutionNormalization.cpp
index 2aaa4c1ae117..54c44c8e542d 100644
--- a/lib/Analysis/ScalarEvolutionNormalization.cpp
+++ b/lib/Analysis/ScalarEvolutionNormalization.cpp
@@ -51,40 +51,47 @@ NormalizeDenormalizeRewriter::visitAddRecExpr(const SCEVAddRecExpr *AR) {
transform(AR->operands(), std::back_inserter(Operands),
[&](const SCEV *Op) { return visit(Op); });
- // Conservatively use AnyWrap until/unless we need FlagNW.
- const SCEV *Result =
- SE.getAddRecExpr(Operands, AR->getLoop(), SCEV::FlagAnyWrap);
- switch (Kind) {
- case Normalize:
- // We want to normalize step expression, because otherwise we might not be
- // able to denormalize to the original expression.
+ if (!Pred(AR))
+ return SE.getAddRecExpr(Operands, AR->getLoop(), SCEV::FlagAnyWrap);
+
+ // Normalization and denormalization are fancy names for decrementing and
+ // incrementing a SCEV expression with respect to a set of loops. Since
+ // Pred(AR) has returned true, we know we need to normalize or denormalize AR
+ // with respect to its loop.
+
+ if (Kind == Denormalize) {
+ // Denormalization / "partial increment" is essentially the same as \c
+ // SCEVAddRecExpr::getPostIncExpr. Here we use an explicit loop to make the
+ // symmetry with Normalization clear.
+ for (int i = 0, e = Operands.size() - 1; i < e; i++)
+ Operands[i] = SE.getAddExpr(Operands[i], Operands[i + 1]);
+ } else {
+ assert(Kind == Normalize && "Only two possibilities!");
+
+ // Normalization / "partial decrement" is a bit more subtle. Since
+ // incrementing a SCEV expression (in general) changes the step of the SCEV
+ // expression as well, we cannot use the step of the current expression.
+ // Instead, we have to use the step of the very expression we're trying to
+ // compute!
+ //
+ // We solve the issue by recursively building up the result, starting from
+ // the "least significant" operand in the add recurrence:
//
- // Here is an example what will happen if we don't normalize step:
- // ORIGINAL ISE:
- // {(100 /u {1,+,1}<%bb16>),+,(100 /u {1,+,1}<%bb16>)}<%bb25>
- // NORMALIZED ISE:
- // {((-1 * (100 /u {1,+,1}<%bb16>)) + (100 /u {0,+,1}<%bb16>)),+,
- // (100 /u {0,+,1}<%bb16>)}<%bb25>
- // DENORMALIZED BACK ISE:
- // {((2 * (100 /u {1,+,1}<%bb16>)) + (-1 * (100 /u {2,+,1}<%bb16>))),+,
- // (100 /u {1,+,1}<%bb16>)}<%bb25>
- // Note that the initial value changes after normalization +
- // denormalization, which isn't correct.
- if (Pred(AR)) {
- const SCEV *TransformedStep = visit(AR->getStepRecurrence(SE));
- Result = SE.getMinusSCEV(Result, TransformedStep);
- }
- break;
- case Denormalize:
- // Here we want to normalize step expressions for the same reasons, as
- // stated above.
- if (Pred(AR)) {
- const SCEV *TransformedStep = visit(AR->getStepRecurrence(SE));
- Result = SE.getAddExpr(Result, TransformedStep);
- }
- break;
+ // Base case:
+ // Single operand add recurrence. It's its own normalization.
+ //
+ // N-operand case:
+ // {S_{N-1},+,S_{N-2},+,...,+,S_0} = S
+ //
+ // Since the step recurrence of S is {S_{N-2},+,...,+,S_0}, we know its
+ // normalization by induction. We subtract the normalized step
+ // recurrence from S_{N-1} to get the normalization of S.
+
+ for (int i = Operands.size() - 2; i >= 0; i--)
+ Operands[i] = SE.getMinusSCEV(Operands[i], Operands[i + 1]);
}
- return Result;
+
+ return SE.getAddRecExpr(Operands, AR->getLoop(), SCEV::FlagAnyWrap);
}
const SCEV *llvm::normalizeForPostIncUse(const SCEV *S,
diff --git a/lib/Analysis/ValueTracking.cpp b/lib/Analysis/ValueTracking.cpp
index 900a2363e60d..af964b6259bb 100644
--- a/lib/Analysis/ValueTracking.cpp
+++ b/lib/Analysis/ValueTracking.cpp
@@ -38,6 +38,7 @@
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Statepoint.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/KnownBits.h"
#include "llvm/Support/MathExtras.h"
#include <algorithm>
#include <array>
@@ -130,15 +131,15 @@ static const Instruction *safeCxtI(const Value *V, const Instruction *CxtI) {
return nullptr;
}
-static void computeKnownBits(const Value *V, APInt &KnownZero, APInt &KnownOne,
+static void computeKnownBits(const Value *V, KnownBits &Known,
unsigned Depth, const Query &Q);
-void llvm::computeKnownBits(const Value *V, APInt &KnownZero, APInt &KnownOne,
+void llvm::computeKnownBits(const Value *V, KnownBits &Known,
const DataLayout &DL, unsigned Depth,
AssumptionCache *AC, const Instruction *CxtI,
const DominatorTree *DT,
OptimizationRemarkEmitter *ORE) {
- ::computeKnownBits(V, KnownZero, KnownOne, Depth,
+ ::computeKnownBits(V, Known, Depth,
Query(DL, AC, safeCxtI(V, CxtI), DT, ORE));
}
@@ -151,11 +152,11 @@ bool llvm::haveNoCommonBitsSet(const Value *LHS, const Value *RHS,
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();
+ KnownBits LHSKnown(IT->getBitWidth());
+ KnownBits RHSKnown(IT->getBitWidth());
+ computeKnownBits(LHS, LHSKnown, DL, 0, AC, CxtI, DT);
+ computeKnownBits(RHS, RHSKnown, DL, 0, AC, CxtI, DT);
+ return (LHSKnown.Zero | RHSKnown.Zero).isAllOnesValue();
}
static void ComputeSignBit(const Value *V, bool &KnownZero, bool &KnownOne,
@@ -252,67 +253,65 @@ unsigned llvm::ComputeNumSignBits(const Value *V, const DataLayout &DL,
static void computeKnownBitsAddSub(bool Add, const Value *Op0, const Value *Op1,
bool NSW,
- APInt &KnownZero, APInt &KnownOne,
- APInt &KnownZero2, APInt &KnownOne2,
+ KnownBits &KnownOut, KnownBits &Known2,
unsigned Depth, const Query &Q) {
- unsigned BitWidth = KnownZero.getBitWidth();
+ unsigned BitWidth = KnownOut.getBitWidth();
// If an initial sequence of bits in the result is not needed, the
// corresponding bits in the operands are not needed.
- APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0);
- computeKnownBits(Op0, LHSKnownZero, LHSKnownOne, Depth + 1, Q);
- computeKnownBits(Op1, KnownZero2, KnownOne2, Depth + 1, Q);
+ KnownBits LHSKnown(BitWidth);
+ computeKnownBits(Op0, LHSKnown, Depth + 1, Q);
+ computeKnownBits(Op1, Known2, Depth + 1, Q);
// Carry in a 1 for a subtract, rather than a 0.
uint64_t CarryIn = 0;
if (!Add) {
// Sum = LHS + ~RHS + 1
- std::swap(KnownZero2, KnownOne2);
+ std::swap(Known2.Zero, Known2.One);
CarryIn = 1;
}
- APInt PossibleSumZero = ~LHSKnownZero + ~KnownZero2 + CarryIn;
- APInt PossibleSumOne = LHSKnownOne + KnownOne2 + CarryIn;
+ APInt PossibleSumZero = ~LHSKnown.Zero + ~Known2.Zero + CarryIn;
+ APInt PossibleSumOne = LHSKnown.One + Known2.One + CarryIn;
// Compute known bits of the carry.
- APInt CarryKnownZero = ~(PossibleSumZero ^ LHSKnownZero ^ KnownZero2);
- APInt CarryKnownOne = PossibleSumOne ^ LHSKnownOne ^ KnownOne2;
+ APInt CarryKnownZero = ~(PossibleSumZero ^ LHSKnown.Zero ^ Known2.Zero);
+ APInt CarryKnownOne = PossibleSumOne ^ LHSKnown.One ^ Known2.One;
// Compute set of known bits (where all three relevant bits are known).
- APInt LHSKnown = LHSKnownZero | LHSKnownOne;
- APInt RHSKnown = KnownZero2 | KnownOne2;
- APInt CarryKnown = CarryKnownZero | CarryKnownOne;
- APInt Known = LHSKnown & RHSKnown & CarryKnown;
+ APInt LHSKnownUnion = LHSKnown.Zero | LHSKnown.One;
+ APInt RHSKnownUnion = Known2.Zero | Known2.One;
+ APInt CarryKnownUnion = CarryKnownZero | CarryKnownOne;
+ APInt Known = LHSKnownUnion & RHSKnownUnion & CarryKnownUnion;
assert((PossibleSumZero & Known) == (PossibleSumOne & Known) &&
"known bits of sum differ");
// Compute known bits of the result.
- KnownZero = ~PossibleSumOne & Known;
- KnownOne = PossibleSumOne & Known;
+ KnownOut.Zero = ~PossibleSumOne & Known;
+ KnownOut.One = PossibleSumOne & Known;
// Are we still trying to solve for the sign bit?
if (!Known.isSignBitSet()) {
if (NSW) {
// Adding two non-negative numbers, or subtracting a negative number from
// a non-negative one, can't wrap into negative.
- if (LHSKnownZero.isSignBitSet() && KnownZero2.isSignBitSet())
- KnownZero.setSignBit();
+ if (LHSKnown.Zero.isSignBitSet() && Known2.Zero.isSignBitSet())
+ KnownOut.Zero.setSignBit();
// Adding two negative numbers, or subtracting a non-negative number from
// a negative one, can't wrap into non-negative.
- else if (LHSKnownOne.isSignBitSet() && KnownOne2.isSignBitSet())
- KnownOne.setSignBit();
+ else if (LHSKnown.One.isSignBitSet() && Known2.One.isSignBitSet())
+ KnownOut.One.setSignBit();
}
}
}
static void computeKnownBitsMul(const Value *Op0, const Value *Op1, bool NSW,
- APInt &KnownZero, APInt &KnownOne,
- APInt &KnownZero2, APInt &KnownOne2,
+ KnownBits &Known, KnownBits &Known2,
unsigned Depth, const Query &Q) {
- unsigned BitWidth = KnownZero.getBitWidth();
- computeKnownBits(Op1, KnownZero, KnownOne, Depth + 1, Q);
- computeKnownBits(Op0, KnownZero2, KnownOne2, Depth + 1, Q);
+ unsigned BitWidth = Known.getBitWidth();
+ computeKnownBits(Op1, Known, Depth + 1, Q);
+ computeKnownBits(Op0, Known2, Depth + 1, Q);
bool isKnownNegative = false;
bool isKnownNonNegative = false;
@@ -322,10 +321,10 @@ static void computeKnownBitsMul(const Value *Op0, const Value *Op1, bool NSW,
// The product of a number with itself is non-negative.
isKnownNonNegative = true;
} else {
- bool isKnownNonNegativeOp1 = KnownZero.isSignBitSet();
- bool isKnownNonNegativeOp0 = KnownZero2.isSignBitSet();
- bool isKnownNegativeOp1 = KnownOne.isSignBitSet();
- bool isKnownNegativeOp0 = KnownOne2.isSignBitSet();
+ bool isKnownNonNegativeOp1 = Known.Zero.isSignBitSet();
+ bool isKnownNonNegativeOp0 = Known2.Zero.isSignBitSet();
+ bool isKnownNegativeOp1 = Known.One.isSignBitSet();
+ bool isKnownNegativeOp0 = Known2.One.isSignBitSet();
// The product of two numbers with the same sign is non-negative.
isKnownNonNegative = (isKnownNegativeOp1 && isKnownNegativeOp0) ||
(isKnownNonNegativeOp1 && isKnownNonNegativeOp0);
@@ -343,28 +342,28 @@ static void computeKnownBitsMul(const Value *Op0, const Value *Op1, bool NSW,
// Also compute a conservative estimate for high known-0 bits.
// More trickiness is possible, but this is sufficient for the
// interesting case of alignment computation.
- KnownOne.clearAllBits();
- unsigned TrailZ = KnownZero.countTrailingOnes() +
- KnownZero2.countTrailingOnes();
- unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
- KnownZero2.countLeadingOnes(),
+ Known.One.clearAllBits();
+ unsigned TrailZ = Known.Zero.countTrailingOnes() +
+ Known2.Zero.countTrailingOnes();
+ unsigned LeadZ = std::max(Known.Zero.countLeadingOnes() +
+ Known2.Zero.countLeadingOnes(),
BitWidth) - BitWidth;
TrailZ = std::min(TrailZ, BitWidth);
LeadZ = std::min(LeadZ, BitWidth);
- KnownZero.clearAllBits();
- KnownZero.setLowBits(TrailZ);
- KnownZero.setHighBits(LeadZ);
+ Known.Zero.clearAllBits();
+ Known.Zero.setLowBits(TrailZ);
+ Known.Zero.setHighBits(LeadZ);
// Only make use of no-wrap flags if we failed to compute the sign bit
// directly. This matters if the multiplication always overflows, in
// which case we prefer to follow the result of the direct computation,
// though as the program is invoking undefined behaviour we can choose
// whatever we like here.
- if (isKnownNonNegative && !KnownOne.isSignBitSet())
- KnownZero.setSignBit();
- else if (isKnownNegative && !KnownZero.isSignBitSet())
- KnownOne.setSignBit();
+ if (isKnownNonNegative && !Known.One.isSignBitSet())
+ Known.Zero.setSignBit();
+ else if (isKnownNegative && !Known.Zero.isSignBitSet())
+ Known.One.setSignBit();
}
void llvm::computeKnownBitsFromRangeMetadata(const MDNode &Ranges,
@@ -499,15 +498,14 @@ bool llvm::isValidAssumeForContext(const Instruction *Inv,
return !isEphemeralValueOf(Inv, CxtI);
}
-static void computeKnownBitsFromAssume(const Value *V, APInt &KnownZero,
- APInt &KnownOne, unsigned Depth,
- const Query &Q) {
+static void computeKnownBitsFromAssume(const Value *V, KnownBits &Known,
+ unsigned Depth, const Query &Q) {
// Use of assumptions is context-sensitive. If we don't have a context, we
// cannot use them!
if (!Q.AC || !Q.CxtI)
return;
- unsigned BitWidth = KnownZero.getBitWidth();
+ unsigned BitWidth = Known.getBitWidth();
// Note that the patterns below need to be kept in sync with the code
// in AssumptionCache::updateAffectedValues.
@@ -532,15 +530,15 @@ static void computeKnownBitsFromAssume(const Value *V, APInt &KnownZero,
if (Arg == V && isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
assert(BitWidth == 1 && "assume operand is not i1?");
- KnownZero.clearAllBits();
- KnownOne.setAllBits();
+ Known.Zero.clearAllBits();
+ Known.One.setAllBits();
return;
}
if (match(Arg, m_Not(m_Specific(V))) &&
isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
assert(BitWidth == 1 && "assume operand is not i1?");
- KnownZero.setAllBits();
- KnownOne.clearAllBits();
+ Known.Zero.setAllBits();
+ Known.One.clearAllBits();
return;
}
@@ -558,126 +556,126 @@ static void computeKnownBitsFromAssume(const Value *V, APInt &KnownZero,
// assume(v = a)
if (match(Arg, m_c_ICmp(Pred, m_V, m_Value(A))) &&
Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
- APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
- computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
- KnownZero |= RHSKnownZero;
- KnownOne |= RHSKnownOne;
+ KnownBits RHSKnown(BitWidth);
+ computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
+ Known.Zero |= RHSKnown.Zero;
+ Known.One |= RHSKnown.One;
// assume(v & b = a)
} else if (match(Arg,
m_c_ICmp(Pred, m_c_And(m_V, m_Value(B)), m_Value(A))) &&
Pred == ICmpInst::ICMP_EQ &&
isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
- APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
- computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
- APInt MaskKnownZero(BitWidth, 0), MaskKnownOne(BitWidth, 0);
- computeKnownBits(B, MaskKnownZero, MaskKnownOne, Depth+1, Query(Q, I));
+ KnownBits RHSKnown(BitWidth);
+ computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
+ KnownBits MaskKnown(BitWidth);
+ computeKnownBits(B, MaskKnown, Depth+1, Query(Q, I));
// For those bits in the mask that are known to be one, we can propagate
// known bits from the RHS to V.
- KnownZero |= RHSKnownZero & MaskKnownOne;
- KnownOne |= RHSKnownOne & MaskKnownOne;
+ Known.Zero |= RHSKnown.Zero & MaskKnown.One;
+ Known.One |= RHSKnown.One & MaskKnown.One;
// assume(~(v & b) = a)
} else if (match(Arg, m_c_ICmp(Pred, m_Not(m_c_And(m_V, m_Value(B))),
m_Value(A))) &&
Pred == ICmpInst::ICMP_EQ &&
isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
- APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
- computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
- APInt MaskKnownZero(BitWidth, 0), MaskKnownOne(BitWidth, 0);
- computeKnownBits(B, MaskKnownZero, MaskKnownOne, Depth+1, Query(Q, I));
+ KnownBits RHSKnown(BitWidth);
+ computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
+ KnownBits MaskKnown(BitWidth);
+ computeKnownBits(B, MaskKnown, Depth+1, Query(Q, I));
// For those bits in the mask that are known to be one, we can propagate
// inverted known bits from the RHS to V.
- KnownZero |= RHSKnownOne & MaskKnownOne;
- KnownOne |= RHSKnownZero & MaskKnownOne;
+ Known.Zero |= RHSKnown.One & MaskKnown.One;
+ Known.One |= RHSKnown.Zero & MaskKnown.One;
// assume(v | b = a)
} else if (match(Arg,
m_c_ICmp(Pred, m_c_Or(m_V, m_Value(B)), m_Value(A))) &&
Pred == ICmpInst::ICMP_EQ &&
isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
- APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
- computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
- APInt BKnownZero(BitWidth, 0), BKnownOne(BitWidth, 0);
- computeKnownBits(B, BKnownZero, BKnownOne, Depth+1, Query(Q, I));
+ KnownBits RHSKnown(BitWidth);
+ computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
+ KnownBits BKnown(BitWidth);
+ computeKnownBits(B, BKnown, Depth+1, Query(Q, I));
// For those bits in B that are known to be zero, we can propagate known
// bits from the RHS to V.
- KnownZero |= RHSKnownZero & BKnownZero;
- KnownOne |= RHSKnownOne & BKnownZero;
+ Known.Zero |= RHSKnown.Zero & BKnown.Zero;
+ Known.One |= RHSKnown.One & BKnown.Zero;
// assume(~(v | b) = a)
} else if (match(Arg, m_c_ICmp(Pred, m_Not(m_c_Or(m_V, m_Value(B))),
m_Value(A))) &&
Pred == ICmpInst::ICMP_EQ &&
isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
- APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
- computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
- APInt BKnownZero(BitWidth, 0), BKnownOne(BitWidth, 0);
- computeKnownBits(B, BKnownZero, BKnownOne, Depth+1, Query(Q, I));
+ KnownBits RHSKnown(BitWidth);
+ computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
+ KnownBits BKnown(BitWidth);
+ computeKnownBits(B, BKnown, Depth+1, Query(Q, I));
// For those bits in B that are known to be zero, we can propagate
// inverted known bits from the RHS to V.
- KnownZero |= RHSKnownOne & BKnownZero;
- KnownOne |= RHSKnownZero & BKnownZero;
+ Known.Zero |= RHSKnown.One & BKnown.Zero;
+ Known.One |= RHSKnown.Zero & BKnown.Zero;
// assume(v ^ b = a)
} else if (match(Arg,
m_c_ICmp(Pred, m_c_Xor(m_V, m_Value(B)), m_Value(A))) &&
Pred == ICmpInst::ICMP_EQ &&
isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
- APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
- computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
- APInt BKnownZero(BitWidth, 0), BKnownOne(BitWidth, 0);
- computeKnownBits(B, BKnownZero, BKnownOne, Depth+1, Query(Q, I));
+ KnownBits RHSKnown(BitWidth);
+ computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
+ KnownBits BKnown(BitWidth);
+ computeKnownBits(B, BKnown, Depth+1, Query(Q, I));
// For those bits in B that are known to be zero, we can propagate known
// bits from the RHS to V. For those bits in B that are known to be one,
// we can propagate inverted known bits from the RHS to V.
- KnownZero |= RHSKnownZero & BKnownZero;
- KnownOne |= RHSKnownOne & BKnownZero;
- KnownZero |= RHSKnownOne & BKnownOne;
- KnownOne |= RHSKnownZero & BKnownOne;
+ Known.Zero |= RHSKnown.Zero & BKnown.Zero;
+ Known.One |= RHSKnown.One & BKnown.Zero;
+ Known.Zero |= RHSKnown.One & BKnown.One;
+ Known.One |= RHSKnown.Zero & BKnown.One;
// assume(~(v ^ b) = a)
} else if (match(Arg, m_c_ICmp(Pred, m_Not(m_c_Xor(m_V, m_Value(B))),
m_Value(A))) &&
Pred == ICmpInst::ICMP_EQ &&
isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
- APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
- computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
- APInt BKnownZero(BitWidth, 0), BKnownOne(BitWidth, 0);
- computeKnownBits(B, BKnownZero, BKnownOne, Depth+1, Query(Q, I));
+ KnownBits RHSKnown(BitWidth);
+ computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
+ KnownBits BKnown(BitWidth);
+ computeKnownBits(B, BKnown, Depth+1, Query(Q, I));
// For those bits in B that are known to be zero, we can propagate
// inverted known bits from the RHS to V. For those bits in B that are
// known to be one, we can propagate known bits from the RHS to V.
- KnownZero |= RHSKnownOne & BKnownZero;
- KnownOne |= RHSKnownZero & BKnownZero;
- KnownZero |= RHSKnownZero & BKnownOne;
- KnownOne |= RHSKnownOne & BKnownOne;
+ Known.Zero |= RHSKnown.One & BKnown.Zero;
+ Known.One |= RHSKnown.Zero & BKnown.Zero;
+ Known.Zero |= RHSKnown.Zero & BKnown.One;
+ Known.One |= RHSKnown.One & BKnown.One;
// assume(v << c = a)
} else if (match(Arg, m_c_ICmp(Pred, m_Shl(m_V, m_ConstantInt(C)),
m_Value(A))) &&
Pred == ICmpInst::ICMP_EQ &&
isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
- APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
- computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+ KnownBits RHSKnown(BitWidth);
+ computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
// For those bits in RHS that are known, we can propagate them to known
// bits in V shifted to the right by C.
- RHSKnownZero.lshrInPlace(C->getZExtValue());
- KnownZero |= RHSKnownZero;
- RHSKnownOne.lshrInPlace(C->getZExtValue());
- KnownOne |= RHSKnownOne;
+ RHSKnown.Zero.lshrInPlace(C->getZExtValue());
+ Known.Zero |= RHSKnown.Zero;
+ RHSKnown.One.lshrInPlace(C->getZExtValue());
+ Known.One |= RHSKnown.One;
// assume(~(v << c) = a)
} else if (match(Arg, m_c_ICmp(Pred, m_Not(m_Shl(m_V, m_ConstantInt(C))),
m_Value(A))) &&
Pred == ICmpInst::ICMP_EQ &&
isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
- APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
- computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+ KnownBits RHSKnown(BitWidth);
+ computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
// For those bits in RHS that are known, we can propagate them inverted
// to known bits in V shifted to the right by C.
- RHSKnownOne.lshrInPlace(C->getZExtValue());
- KnownZero |= RHSKnownOne;
- RHSKnownZero.lshrInPlace(C->getZExtValue());
- KnownOne |= RHSKnownZero;
+ RHSKnown.One.lshrInPlace(C->getZExtValue());
+ Known.Zero |= RHSKnown.One;
+ RHSKnown.Zero.lshrInPlace(C->getZExtValue());
+ Known.One |= RHSKnown.Zero;
// assume(v >> c = a)
} else if (match(Arg,
m_c_ICmp(Pred, m_CombineOr(m_LShr(m_V, m_ConstantInt(C)),
@@ -685,12 +683,12 @@ static void computeKnownBitsFromAssume(const Value *V, APInt &KnownZero,
m_Value(A))) &&
Pred == ICmpInst::ICMP_EQ &&
isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
- APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
- computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+ KnownBits RHSKnown(BitWidth);
+ computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
// For those bits in RHS that are known, we can propagate them to known
// bits in V shifted to the right by C.
- KnownZero |= RHSKnownZero << C->getZExtValue();
- KnownOne |= RHSKnownOne << C->getZExtValue();
+ Known.Zero |= RHSKnown.Zero << C->getZExtValue();
+ Known.One |= RHSKnown.One << C->getZExtValue();
// assume(~(v >> c) = a)
} else if (match(Arg, m_c_ICmp(Pred, m_Not(m_CombineOr(
m_LShr(m_V, m_ConstantInt(C)),
@@ -698,78 +696,78 @@ static void computeKnownBitsFromAssume(const Value *V, APInt &KnownZero,
m_Value(A))) &&
Pred == ICmpInst::ICMP_EQ &&
isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
- APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
- computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+ KnownBits RHSKnown(BitWidth);
+ computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
// For those bits in RHS that are known, we can propagate them inverted
// to known bits in V shifted to the right by C.
- KnownZero |= RHSKnownOne << C->getZExtValue();
- KnownOne |= RHSKnownZero << C->getZExtValue();
+ Known.Zero |= RHSKnown.One << C->getZExtValue();
+ Known.One |= RHSKnown.Zero << C->getZExtValue();
// assume(v >=_s c) where c is non-negative
} else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
Pred == ICmpInst::ICMP_SGE &&
isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
- APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
- computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+ KnownBits RHSKnown(BitWidth);
+ computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
- if (RHSKnownZero.isSignBitSet()) {
+ if (RHSKnown.Zero.isSignBitSet()) {
// We know that the sign bit is zero.
- KnownZero.setSignBit();
+ Known.Zero.setSignBit();
}
// assume(v >_s c) where c is at least -1.
} else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
Pred == ICmpInst::ICMP_SGT &&
isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
- APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
- computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+ KnownBits RHSKnown(BitWidth);
+ computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
- if (RHSKnownOne.isAllOnesValue() || RHSKnownZero.isSignBitSet()) {
+ if (RHSKnown.One.isAllOnesValue() || RHSKnown.Zero.isSignBitSet()) {
// We know that the sign bit is zero.
- KnownZero.setSignBit();
+ Known.Zero.setSignBit();
}
// assume(v <=_s c) where c is negative
} else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
Pred == ICmpInst::ICMP_SLE &&
isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
- APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
- computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+ KnownBits RHSKnown(BitWidth);
+ computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
- if (RHSKnownOne.isSignBitSet()) {
+ if (RHSKnown.One.isSignBitSet()) {
// We know that the sign bit is one.
- KnownOne.setSignBit();
+ Known.One.setSignBit();
}
// assume(v <_s c) where c is non-positive
} else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
Pred == ICmpInst::ICMP_SLT &&
isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
- APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
- computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+ KnownBits RHSKnown(BitWidth);
+ computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
- if (RHSKnownZero.isAllOnesValue() || RHSKnownOne.isSignBitSet()) {
+ if (RHSKnown.Zero.isAllOnesValue() || RHSKnown.One.isSignBitSet()) {
// We know that the sign bit is one.
- KnownOne.setSignBit();
+ Known.One.setSignBit();
}
// assume(v <=_u c)
} else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
Pred == ICmpInst::ICMP_ULE &&
isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
- APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
- computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+ KnownBits RHSKnown(BitWidth);
+ computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
// Whatever high bits in c are zero are known to be zero.
- KnownZero.setHighBits(RHSKnownZero.countLeadingOnes());
+ Known.Zero.setHighBits(RHSKnown.Zero.countLeadingOnes());
// assume(v <_u c)
} else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
Pred == ICmpInst::ICMP_ULT &&
isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
- APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
- computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+ KnownBits RHSKnown(BitWidth);
+ computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
// Whatever high bits in c are zero are known to be zero (if c is a power
// of 2, then one more).
if (isKnownToBeAPowerOfTwo(A, false, Depth + 1, Query(Q, I)))
- KnownZero.setHighBits(RHSKnownZero.countLeadingOnes()+1);
+ Known.Zero.setHighBits(RHSKnown.Zero.countLeadingOnes()+1);
else
- KnownZero.setHighBits(RHSKnownZero.countLeadingOnes());
+ Known.Zero.setHighBits(RHSKnown.Zero.countLeadingOnes());
}
}
@@ -778,9 +776,9 @@ static void computeKnownBitsFromAssume(const Value *V, APInt &KnownZero,
// so this isn't a real bug. On the other hand, the program may have undefined
// behavior, or we might have a bug in the compiler. We can't assert/crash, so
// clear out the known bits, try to warn the user, and hope for the best.
- if ((KnownZero & KnownOne) != 0) {
- KnownZero.clearAllBits();
- KnownOne.clearAllBits();
+ if (Known.Zero.intersects(Known.One)) {
+ Known.Zero.clearAllBits();
+ Known.One.clearAllBits();
if (Q.ORE) {
auto *CxtI = const_cast<Instruction *>(Q.CxtI);
@@ -793,57 +791,57 @@ static void computeKnownBitsFromAssume(const Value *V, APInt &KnownZero,
}
// Compute known bits from a shift operator, including those with a
-// non-constant shift amount. KnownZero and KnownOne are the outputs of this
-// function. KnownZero2 and KnownOne2 are pre-allocated temporaries with the
-// same bit width as KnownZero and KnownOne. KZF and KOF are operator-specific
-// functors that, given the known-zero or known-one bits respectively, and a
-// shift amount, compute the implied known-zero or known-one bits of the shift
-// operator's result respectively for that shift amount. The results from calling
-// KZF and KOF are conservatively combined for all permitted shift amounts.
+// non-constant shift amount. Known is the outputs of this function. Known2 is a
+// pre-allocated temporary with the/ same bit width as Known. KZF and KOF are
+// operator-specific functors that, given the known-zero or known-one bits
+// respectively, and a shift amount, compute the implied known-zero or known-one
+// bits of the shift operator's result respectively for that shift amount. The
+// results from calling KZF and KOF are conservatively combined for all
+// permitted shift amounts.
static void computeKnownBitsFromShiftOperator(
- const Operator *I, APInt &KnownZero, APInt &KnownOne, APInt &KnownZero2,
- APInt &KnownOne2, unsigned Depth, const Query &Q,
+ const Operator *I, KnownBits &Known, KnownBits &Known2,
+ unsigned Depth, const Query &Q,
function_ref<APInt(const APInt &, unsigned)> KZF,
function_ref<APInt(const APInt &, unsigned)> KOF) {
- unsigned BitWidth = KnownZero.getBitWidth();
+ unsigned BitWidth = Known.getBitWidth();
if (auto *SA = dyn_cast<ConstantInt>(I->getOperand(1))) {
unsigned ShiftAmt = SA->getLimitedValue(BitWidth-1);
- computeKnownBits(I->getOperand(0), KnownZero, KnownOne, Depth + 1, Q);
- KnownZero = KZF(KnownZero, ShiftAmt);
- KnownOne = KOF(KnownOne, ShiftAmt);
- // If there is conflict between KnownZero and KnownOne, this must be an
- // overflowing left shift, so the shift result is undefined. Clear KnownZero
- // and KnownOne bits so that other code could propagate this undef.
- if ((KnownZero & KnownOne) != 0) {
- KnownZero.clearAllBits();
- KnownOne.clearAllBits();
+ computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
+ Known.Zero = KZF(Known.Zero, ShiftAmt);
+ Known.One = KOF(Known.One, ShiftAmt);
+ // If there is conflict between Known.Zero and Known.One, this must be an
+ // overflowing left shift, so the shift result is undefined. Clear Known
+ // bits so that other code could propagate this undef.
+ if ((Known.Zero & Known.One) != 0) {
+ Known.Zero.clearAllBits();
+ Known.One.clearAllBits();
}
return;
}
- computeKnownBits(I->getOperand(1), KnownZero, KnownOne, Depth + 1, Q);
+ computeKnownBits(I->getOperand(1), Known, Depth + 1, Q);
// If the shift amount could be greater than or equal to the bit-width of the LHS, the
// value could be undef, so we don't know anything about it.
- if ((~KnownZero).uge(BitWidth)) {
- KnownZero.clearAllBits();
- KnownOne.clearAllBits();
+ if ((~Known.Zero).uge(BitWidth)) {
+ Known.Zero.clearAllBits();
+ Known.One.clearAllBits();
return;
}
- // Note: We cannot use KnownZero.getLimitedValue() here, because if
+ // Note: We cannot use Known.Zero.getLimitedValue() here, because if
// BitWidth > 64 and any upper bits are known, we'll end up returning the
// limit value (which implies all bits are known).
- uint64_t ShiftAmtKZ = KnownZero.zextOrTrunc(64).getZExtValue();
- uint64_t ShiftAmtKO = KnownOne.zextOrTrunc(64).getZExtValue();
+ uint64_t ShiftAmtKZ = Known.Zero.zextOrTrunc(64).getZExtValue();
+ uint64_t ShiftAmtKO = Known.One.zextOrTrunc(64).getZExtValue();
// It would be more-clearly correct to use the two temporaries for this
// calculation. Reusing the APInts here to prevent unnecessary allocations.
- KnownZero.clearAllBits();
- KnownOne.clearAllBits();
+ Known.Zero.clearAllBits();
+ Known.One.clearAllBits();
// If we know the shifter operand is nonzero, we can sometimes infer more
// known bits. However this is expensive to compute, so be lazy about it and
@@ -858,9 +856,10 @@ static void computeKnownBitsFromShiftOperator(
return;
}
- computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, Depth + 1, Q);
+ computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
- KnownZero = KnownOne = APInt::getAllOnesValue(BitWidth);
+ Known.Zero.setAllBits();
+ Known.One.setAllBits();
for (unsigned ShiftAmt = 0; ShiftAmt < BitWidth; ++ShiftAmt) {
// Combine the shifted known input bits only for those shift amounts
// compatible with its known constraints.
@@ -879,8 +878,8 @@ static void computeKnownBitsFromShiftOperator(
continue;
}
- KnownZero &= KZF(KnownZero2, ShiftAmt);
- KnownOne &= KOF(KnownOne2, ShiftAmt);
+ Known.Zero &= KZF(Known2.Zero, ShiftAmt);
+ Known.One &= KOF(Known2.One, ShiftAmt);
}
// If there are no compatible shift amounts, then we've proven that the shift
@@ -888,33 +887,32 @@ static void computeKnownBitsFromShiftOperator(
// return anything we'd like, but we need to make sure the sets of known bits
// stay disjoint (it should be better for some other code to actually
// propagate the undef than to pick a value here using known bits).
- if ((KnownZero & KnownOne) != 0) {
- KnownZero.clearAllBits();
- KnownOne.clearAllBits();
+ if (Known.Zero.intersects(Known.One)) {
+ Known.Zero.clearAllBits();
+ Known.One.clearAllBits();
}
}
-static void computeKnownBitsFromOperator(const Operator *I, APInt &KnownZero,
- APInt &KnownOne, unsigned Depth,
- const Query &Q) {
- unsigned BitWidth = KnownZero.getBitWidth();
+static void computeKnownBitsFromOperator(const Operator *I, KnownBits &Known,
+ unsigned Depth, const Query &Q) {
+ unsigned BitWidth = Known.getBitWidth();
- APInt KnownZero2(KnownZero), KnownOne2(KnownOne);
+ KnownBits Known2(Known);
switch (I->getOpcode()) {
default: break;
case Instruction::Load:
if (MDNode *MD = cast<LoadInst>(I)->getMetadata(LLVMContext::MD_range))
- computeKnownBitsFromRangeMetadata(*MD, KnownZero, KnownOne);
+ computeKnownBitsFromRangeMetadata(*MD, Known.Zero, Known.One);
break;
case Instruction::And: {
// If either the LHS or the RHS are Zero, the result is zero.
- computeKnownBits(I->getOperand(1), KnownZero, KnownOne, Depth + 1, Q);
- computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, Depth + 1, Q);
+ computeKnownBits(I->getOperand(1), Known, Depth + 1, Q);
+ computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
// Output known-1 bits are only known if set in both the LHS & RHS.
- KnownOne &= KnownOne2;
+ Known.One &= Known2.One;
// Output known-0 are known to be clear if zero in either the LHS | RHS.
- KnownZero |= KnownZero2;
+ Known.Zero |= Known2.Zero;
// and(x, add (x, -1)) is a common idiom that always clears the low bit;
// here we handle the more general case of adding any odd number by
@@ -922,115 +920,115 @@ static void computeKnownBitsFromOperator(const Operator *I, APInt &KnownZero,
// TODO: This could be generalized to clearing any bit set in y where the
// following bit is known to be unset in y.
Value *Y = nullptr;
- if (!KnownZero[0] && !KnownOne[0] &&
+ if (!Known.Zero[0] && !Known.One[0] &&
(match(I->getOperand(0), m_Add(m_Specific(I->getOperand(1)),
m_Value(Y))) ||
match(I->getOperand(1), m_Add(m_Specific(I->getOperand(0)),
m_Value(Y))))) {
- KnownZero2.clearAllBits(); KnownOne2.clearAllBits();
- computeKnownBits(Y, KnownZero2, KnownOne2, Depth + 1, Q);
- if (KnownOne2.countTrailingOnes() > 0)
- KnownZero.setBit(0);
+ Known2.Zero.clearAllBits(); Known2.One.clearAllBits();
+ computeKnownBits(Y, Known2, Depth + 1, Q);
+ if (Known2.One.countTrailingOnes() > 0)
+ Known.Zero.setBit(0);
}
break;
}
case Instruction::Or: {
- computeKnownBits(I->getOperand(1), KnownZero, KnownOne, Depth + 1, Q);
- computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, Depth + 1, Q);
+ computeKnownBits(I->getOperand(1), Known, Depth + 1, Q);
+ computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
// Output known-0 bits are only known if clear in both the LHS & RHS.
- KnownZero &= KnownZero2;
+ Known.Zero &= Known2.Zero;
// Output known-1 are known to be set if set in either the LHS | RHS.
- KnownOne |= KnownOne2;
+ Known.One |= Known2.One;
break;
}
case Instruction::Xor: {
- computeKnownBits(I->getOperand(1), KnownZero, KnownOne, Depth + 1, Q);
- computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, Depth + 1, Q);
+ computeKnownBits(I->getOperand(1), Known, Depth + 1, Q);
+ computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
// Output known-0 bits are known if clear or set in both the LHS & RHS.
- APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
+ APInt KnownZeroOut = (Known.Zero & Known2.Zero) | (Known.One & Known2.One);
// Output known-1 are known to be set if set in only one of the LHS, RHS.
- KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
- KnownZero = std::move(KnownZeroOut);
+ Known.One = (Known.Zero & Known2.One) | (Known.One & Known2.Zero);
+ Known.Zero = std::move(KnownZeroOut);
break;
}
case Instruction::Mul: {
bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap();
- computeKnownBitsMul(I->getOperand(0), I->getOperand(1), NSW, KnownZero,
- KnownOne, KnownZero2, KnownOne2, Depth, Q);
+ computeKnownBitsMul(I->getOperand(0), I->getOperand(1), NSW, Known,
+ Known2, Depth, Q);
break;
}
case Instruction::UDiv: {
// For the purposes of computing leading zeros we can conservatively
// treat a udiv as a logical right shift by the power of 2 known to
// be less than the denominator.
- computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, Depth + 1, Q);
- unsigned LeadZ = KnownZero2.countLeadingOnes();
+ computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
+ unsigned LeadZ = Known2.Zero.countLeadingOnes();
- KnownOne2.clearAllBits();
- KnownZero2.clearAllBits();
- computeKnownBits(I->getOperand(1), KnownZero2, KnownOne2, Depth + 1, Q);
- unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
+ Known2.One.clearAllBits();
+ Known2.Zero.clearAllBits();
+ computeKnownBits(I->getOperand(1), Known2, Depth + 1, Q);
+ unsigned RHSUnknownLeadingOnes = Known2.One.countLeadingZeros();
if (RHSUnknownLeadingOnes != BitWidth)
LeadZ = std::min(BitWidth,
LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
- KnownZero.setHighBits(LeadZ);
+ Known.Zero.setHighBits(LeadZ);
break;
}
case Instruction::Select: {
const Value *LHS, *RHS;
SelectPatternFlavor SPF = matchSelectPattern(I, LHS, RHS).Flavor;
if (SelectPatternResult::isMinOrMax(SPF)) {
- computeKnownBits(RHS, KnownZero, KnownOne, Depth + 1, Q);
- computeKnownBits(LHS, KnownZero2, KnownOne2, Depth + 1, Q);
+ computeKnownBits(RHS, Known, Depth + 1, Q);
+ computeKnownBits(LHS, Known2, Depth + 1, Q);
} else {
- computeKnownBits(I->getOperand(2), KnownZero, KnownOne, Depth + 1, Q);
- computeKnownBits(I->getOperand(1), KnownZero2, KnownOne2, Depth + 1, Q);
+ computeKnownBits(I->getOperand(2), Known, Depth + 1, Q);
+ computeKnownBits(I->getOperand(1), Known2, Depth + 1, Q);
}
unsigned MaxHighOnes = 0;
unsigned MaxHighZeros = 0;
if (SPF == SPF_SMAX) {
// If both sides are negative, the result is negative.
- if (KnownOne.isSignBitSet() && KnownOne2.isSignBitSet())
+ if (Known.One.isSignBitSet() && Known2.One.isSignBitSet())
// We can derive a lower bound on the result by taking the max of the
// leading one bits.
- MaxHighOnes =
- std::max(KnownOne.countLeadingOnes(), KnownOne2.countLeadingOnes());
+ MaxHighOnes = std::max(Known.One.countLeadingOnes(),
+ Known2.One.countLeadingOnes());
// If either side is non-negative, the result is non-negative.
- else if (KnownZero.isSignBitSet() || KnownZero2.isSignBitSet())
+ else if (Known.Zero.isSignBitSet() || Known2.Zero.isSignBitSet())
MaxHighZeros = 1;
} else if (SPF == SPF_SMIN) {
// If both sides are non-negative, the result is non-negative.
- if (KnownZero.isSignBitSet() && KnownZero2.isSignBitSet())
+ if (Known.Zero.isSignBitSet() && Known2.Zero.isSignBitSet())
// We can derive an upper bound on the result by taking the max of the
// leading zero bits.
- MaxHighZeros = std::max(KnownZero.countLeadingOnes(),
- KnownZero2.countLeadingOnes());
+ MaxHighZeros = std::max(Known.Zero.countLeadingOnes(),
+ Known2.Zero.countLeadingOnes());
// If either side is negative, the result is negative.
- else if (KnownOne.isSignBitSet() || KnownOne2.isSignBitSet())
+ else if (Known.One.isSignBitSet() || Known2.One.isSignBitSet())
MaxHighOnes = 1;
} else if (SPF == SPF_UMAX) {
// We can derive a lower bound on the result by taking the max of the
// leading one bits.
MaxHighOnes =
- std::max(KnownOne.countLeadingOnes(), KnownOne2.countLeadingOnes());
+ std::max(Known.One.countLeadingOnes(), Known2.One.countLeadingOnes());
} else if (SPF == SPF_UMIN) {
// We can derive an upper bound on the result by taking the max of the
// leading zero bits.
MaxHighZeros =
- std::max(KnownZero.countLeadingOnes(), KnownZero2.countLeadingOnes());
+ std::max(Known.Zero.countLeadingOnes(), Known2.Zero.countLeadingOnes());
}
// Only known if known in both the LHS and RHS.
- KnownOne &= KnownOne2;
- KnownZero &= KnownZero2;
+ Known.One &= Known2.One;
+ Known.Zero &= Known2.Zero;
if (MaxHighOnes > 0)
- KnownOne.setHighBits(MaxHighOnes);
+ Known.One.setHighBits(MaxHighOnes);
if (MaxHighZeros > 0)
- KnownZero.setHighBits(MaxHighZeros);
+ Known.Zero.setHighBits(MaxHighZeros);
break;
}
case Instruction::FPTrunc:
@@ -1054,14 +1052,14 @@ static void computeKnownBitsFromOperator(const Operator *I, APInt &KnownZero,
SrcBitWidth = Q.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, Depth + 1, Q);
- KnownZero = KnownZero.zextOrTrunc(BitWidth);
- KnownOne = KnownOne.zextOrTrunc(BitWidth);
+ Known.Zero = Known.Zero.zextOrTrunc(SrcBitWidth);
+ Known.One = Known.One.zextOrTrunc(SrcBitWidth);
+ computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
+ Known.Zero = Known.Zero.zextOrTrunc(BitWidth);
+ Known.One = Known.One.zextOrTrunc(BitWidth);
// Any top bits are known to be zero.
if (BitWidth > SrcBitWidth)
- KnownZero.setBitsFrom(SrcBitWidth);
+ Known.Zero.setBitsFrom(SrcBitWidth);
break;
}
case Instruction::BitCast: {
@@ -1070,7 +1068,7 @@ static void computeKnownBitsFromOperator(const Operator *I, APInt &KnownZero,
// TODO: For now, not handling conversions like:
// (bitcast i64 %x to <2 x i32>)
!I->getType()->isVectorTy()) {
- computeKnownBits(I->getOperand(0), KnownZero, KnownOne, Depth + 1, Q);
+ computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
break;
}
break;
@@ -1079,13 +1077,13 @@ static void computeKnownBitsFromOperator(const Operator *I, APInt &KnownZero,
// Compute the bits in the result that are not present in the input.
unsigned SrcBitWidth = I->getOperand(0)->getType()->getScalarSizeInBits();
- KnownZero = KnownZero.trunc(SrcBitWidth);
- KnownOne = KnownOne.trunc(SrcBitWidth);
- computeKnownBits(I->getOperand(0), KnownZero, KnownOne, Depth + 1, Q);
+ Known.Zero = Known.Zero.trunc(SrcBitWidth);
+ Known.One = Known.One.trunc(SrcBitWidth);
+ computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
// If the sign bit of the input is known set or clear, then we know the
// top bits of the result.
- KnownZero = KnownZero.sext(BitWidth);
- KnownOne = KnownOne.sext(BitWidth);
+ Known.Zero = Known.Zero.sext(BitWidth);
+ Known.One = Known.One.sext(BitWidth);
break;
}
case Instruction::Shl: {
@@ -1108,9 +1106,7 @@ static void computeKnownBitsFromOperator(const Operator *I, APInt &KnownZero,
return KOResult;
};
- computeKnownBitsFromShiftOperator(I, KnownZero, KnownOne,
- KnownZero2, KnownOne2, Depth, Q, KZF,
- KOF);
+ computeKnownBitsFromShiftOperator(I, Known, Known2, Depth, Q, KZF, KOF);
break;
}
case Instruction::LShr: {
@@ -1126,9 +1122,7 @@ static void computeKnownBitsFromOperator(const Operator *I, APInt &KnownZero,
return KnownOne.lshr(ShiftAmt);
};
- computeKnownBitsFromShiftOperator(I, KnownZero, KnownOne,
- KnownZero2, KnownOne2, Depth, Q, KZF,
- KOF);
+ computeKnownBitsFromShiftOperator(I, Known, Known2, Depth, Q, KZF, KOF);
break;
}
case Instruction::AShr: {
@@ -1141,23 +1135,19 @@ static void computeKnownBitsFromOperator(const Operator *I, APInt &KnownZero,
return KnownOne.ashr(ShiftAmt);
};
- computeKnownBitsFromShiftOperator(I, KnownZero, KnownOne,
- KnownZero2, KnownOne2, Depth, Q, KZF,
- KOF);
+ computeKnownBitsFromShiftOperator(I, Known, Known2, 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, Depth,
- Q);
+ Known, Known2, 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, Depth,
- Q);
+ Known, Known2, Depth, Q);
break;
}
case Instruction::SRem:
@@ -1165,34 +1155,33 @@ static void computeKnownBitsFromOperator(const Operator *I, APInt &KnownZero,
APInt RA = Rem->getValue().abs();
if (RA.isPowerOf2()) {
APInt LowBits = RA - 1;
- computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, Depth + 1,
- Q);
+ computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
// The low bits of the first operand are unchanged by the srem.
- KnownZero = KnownZero2 & LowBits;
- KnownOne = KnownOne2 & LowBits;
+ Known.Zero = Known2.Zero & LowBits;
+ Known.One = Known2.One & LowBits;
// If the first operand is non-negative or has all low bits zero, then
// the upper bits are all zero.
- if (KnownZero2.isSignBitSet() || ((KnownZero2 & LowBits) == LowBits))
- KnownZero |= ~LowBits;
+ if (Known2.Zero.isSignBitSet() || ((Known2.Zero & LowBits) == LowBits))
+ Known.Zero |= ~LowBits;
// If the first operand is negative and not all low bits are zero, then
// the upper bits are all one.
- if (KnownOne2.isSignBitSet() && ((KnownOne2 & LowBits) != 0))
- KnownOne |= ~LowBits;
+ if (Known2.One.isSignBitSet() && ((Known2.One & LowBits) != 0))
+ Known.One |= ~LowBits;
- assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
+ assert((Known.Zero & Known.One) == 0 && "Bits known to be one AND zero?");
break;
}
}
// The sign bit is the LHS's sign bit, except when the result of the
// remainder is zero.
- computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, Depth + 1, Q);
+ computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
// If it's known zero, our sign bit is also zero.
- if (KnownZero2.isSignBitSet())
- KnownZero.setSignBit();
+ if (Known2.Zero.isSignBitSet())
+ Known.Zero.setSignBit();
break;
case Instruction::URem: {
@@ -1200,23 +1189,23 @@ static void computeKnownBitsFromOperator(const Operator *I, APInt &KnownZero,
const APInt &RA = Rem->getValue();
if (RA.isPowerOf2()) {
APInt LowBits = (RA - 1);
- computeKnownBits(I->getOperand(0), KnownZero, KnownOne, Depth + 1, Q);
- KnownZero |= ~LowBits;
- KnownOne &= LowBits;
+ computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
+ Known.Zero |= ~LowBits;
+ Known.One &= LowBits;
break;
}
}
// Since the result is less than or equal to either operand, any leading
// zero bits in either operand must also exist in the result.
- computeKnownBits(I->getOperand(0), KnownZero, KnownOne, Depth + 1, Q);
- computeKnownBits(I->getOperand(1), KnownZero2, KnownOne2, Depth + 1, Q);
+ computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
+ computeKnownBits(I->getOperand(1), Known2, Depth + 1, Q);
- unsigned Leaders = std::max(KnownZero.countLeadingOnes(),
- KnownZero2.countLeadingOnes());
- KnownOne.clearAllBits();
- KnownZero.clearAllBits();
- KnownZero.setHighBits(Leaders);
+ unsigned Leaders = std::max(Known.Zero.countLeadingOnes(),
+ Known2.Zero.countLeadingOnes());
+ Known.One.clearAllBits();
+ Known.Zero.clearAllBits();
+ Known.Zero.setHighBits(Leaders);
break;
}
@@ -1227,16 +1216,15 @@ static void computeKnownBitsFromOperator(const Operator *I, APInt &KnownZero,
Align = Q.DL.getABITypeAlignment(AI->getAllocatedType());
if (Align > 0)
- KnownZero.setLowBits(countTrailingZeros(Align));
+ Known.Zero.setLowBits(countTrailingZeros(Align));
break;
}
case Instruction::GetElementPtr: {
// Analyze all of the subscripts of this getelementptr instruction
// to determine if we can prove known low zero bits.
- APInt LocalKnownZero(BitWidth, 0), LocalKnownOne(BitWidth, 0);
- computeKnownBits(I->getOperand(0), LocalKnownZero, LocalKnownOne, Depth + 1,
- Q);
- unsigned TrailZ = LocalKnownZero.countTrailingOnes();
+ KnownBits LocalKnown(BitWidth);
+ computeKnownBits(I->getOperand(0), LocalKnown, Depth + 1, Q);
+ unsigned TrailZ = LocalKnown.Zero.countTrailingOnes();
gep_type_iterator GTI = gep_type_begin(I);
for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i, ++GTI) {
@@ -1266,15 +1254,15 @@ static void computeKnownBitsFromOperator(const Operator *I, APInt &KnownZero,
}
unsigned GEPOpiBits = Index->getType()->getScalarSizeInBits();
uint64_t TypeSize = Q.DL.getTypeAllocSize(IndexedTy);
- LocalKnownZero = LocalKnownOne = APInt(GEPOpiBits, 0);
- computeKnownBits(Index, LocalKnownZero, LocalKnownOne, Depth + 1, Q);
+ LocalKnown.Zero = LocalKnown.One = APInt(GEPOpiBits, 0);
+ computeKnownBits(Index, LocalKnown, Depth + 1, Q);
TrailZ = std::min(TrailZ,
unsigned(countTrailingZeros(TypeSize) +
- LocalKnownZero.countTrailingOnes()));
+ LocalKnown.Zero.countTrailingOnes()));
}
}
- KnownZero.setLowBits(TrailZ);
+ Known.Zero.setLowBits(TrailZ);
break;
}
case Instruction::PHI: {
@@ -1309,14 +1297,14 @@ static void computeKnownBitsFromOperator(const Operator *I, APInt &KnownZero,
break;
// Ok, we have a PHI of the form L op= R. Check for low
// zero bits.
- computeKnownBits(R, KnownZero2, KnownOne2, Depth + 1, Q);
+ computeKnownBits(R, Known2, Depth + 1, Q);
// We need to take the minimum number of known bits
- APInt KnownZero3(KnownZero), KnownOne3(KnownOne);
- computeKnownBits(L, KnownZero3, KnownOne3, Depth + 1, Q);
+ KnownBits Known3(Known);
+ computeKnownBits(L, Known3, Depth + 1, Q);
- KnownZero.setLowBits(std::min(KnownZero2.countTrailingOnes(),
- KnownZero3.countTrailingOnes()));
+ Known.Zero.setLowBits(std::min(Known2.Zero.countTrailingOnes(),
+ Known3.Zero.countTrailingOnes()));
if (DontImproveNonNegativePhiBits)
break;
@@ -1333,25 +1321,25 @@ static void computeKnownBitsFromOperator(const Operator *I, APInt &KnownZero,
// (add non-negative, non-negative) --> non-negative
// (add negative, negative) --> negative
if (Opcode == Instruction::Add) {
- if (KnownZero2.isSignBitSet() && KnownZero3.isSignBitSet())
- KnownZero.setSignBit();
- else if (KnownOne2.isSignBitSet() && KnownOne3.isSignBitSet())
- KnownOne.setSignBit();
+ if (Known2.Zero.isSignBitSet() && Known3.Zero.isSignBitSet())
+ Known.Zero.setSignBit();
+ else if (Known2.One.isSignBitSet() && Known3.One.isSignBitSet())
+ Known.One.setSignBit();
}
// (sub nsw non-negative, negative) --> non-negative
// (sub nsw negative, non-negative) --> negative
else if (Opcode == Instruction::Sub && LL == I) {
- if (KnownZero2.isSignBitSet() && KnownOne3.isSignBitSet())
- KnownZero.setSignBit();
- else if (KnownOne2.isSignBitSet() && KnownZero3.isSignBitSet())
- KnownOne.setSignBit();
+ if (Known2.Zero.isSignBitSet() && Known3.One.isSignBitSet())
+ Known.Zero.setSignBit();
+ else if (Known2.One.isSignBitSet() && Known3.Zero.isSignBitSet())
+ Known.One.setSignBit();
}
// (mul nsw non-negative, non-negative) --> non-negative
- else if (Opcode == Instruction::Mul && KnownZero2.isSignBitSet() &&
- KnownZero3.isSignBitSet())
- KnownZero.setSignBit();
+ else if (Opcode == Instruction::Mul && Known2.Zero.isSignBitSet() &&
+ Known3.Zero.isSignBitSet())
+ Known.Zero.setSignBit();
}
break;
@@ -1365,27 +1353,26 @@ static void computeKnownBitsFromOperator(const Operator *I, APInt &KnownZero,
// Otherwise take the unions of the known bit sets of the operands,
// taking conservative care to avoid excessive recursion.
- if (Depth < MaxDepth - 1 && !KnownZero && !KnownOne) {
+ if (Depth < MaxDepth - 1 && !Known.Zero && !Known.One) {
// Skip if every incoming value references to ourself.
if (dyn_cast_or_null<UndefValue>(P->hasConstantValue()))
break;
- KnownZero.setAllBits();
- KnownOne.setAllBits();
+ Known.Zero.setAllBits();
+ Known.One.setAllBits();
for (Value *IncValue : P->incoming_values()) {
// Skip direct self references.
if (IncValue == P) continue;
- KnownZero2 = APInt(BitWidth, 0);
- KnownOne2 = APInt(BitWidth, 0);
+ Known2 = KnownBits(BitWidth);
// Recurse, but cap the recursion to one level, because we don't
// want to waste time spinning around in loops.
- computeKnownBits(IncValue, KnownZero2, KnownOne2, MaxDepth - 1, Q);
- KnownZero &= KnownZero2;
- KnownOne &= KnownOne2;
+ computeKnownBits(IncValue, Known2, MaxDepth - 1, Q);
+ Known.Zero &= Known2.Zero;
+ Known.One &= Known2.One;
// If all bits have been ruled out, there's no need to check
// more operands.
- if (!KnownZero && !KnownOne)
+ if (!Known.Zero && !Known.One)
break;
}
}
@@ -1397,24 +1384,24 @@ static void computeKnownBitsFromOperator(const Operator *I, APInt &KnownZero,
// and then intersect with known bits based on other properties of the
// function.
if (MDNode *MD = cast<Instruction>(I)->getMetadata(LLVMContext::MD_range))
- computeKnownBitsFromRangeMetadata(*MD, KnownZero, KnownOne);
+ computeKnownBitsFromRangeMetadata(*MD, Known.Zero, Known.One);
if (const Value *RV = ImmutableCallSite(I).getReturnedArgOperand()) {
- computeKnownBits(RV, KnownZero2, KnownOne2, Depth + 1, Q);
- KnownZero |= KnownZero2;
- KnownOne |= KnownOne2;
+ computeKnownBits(RV, Known2, Depth + 1, Q);
+ Known.Zero |= Known2.Zero;
+ Known.One |= Known2.One;
}
if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
switch (II->getIntrinsicID()) {
default: break;
case Intrinsic::bitreverse:
- computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, Depth + 1, Q);
- KnownZero |= KnownZero2.reverseBits();
- KnownOne |= KnownOne2.reverseBits();
+ computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
+ Known.Zero |= Known2.Zero.reverseBits();
+ Known.One |= Known2.One.reverseBits();
break;
case Intrinsic::bswap:
- computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, Depth + 1, Q);
- KnownZero |= KnownZero2.byteSwap();
- KnownOne |= KnownOne2.byteSwap();
+ computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
+ Known.Zero |= Known2.Zero.byteSwap();
+ Known.One |= Known2.One.byteSwap();
break;
case Intrinsic::ctlz:
case Intrinsic::cttz: {
@@ -1422,22 +1409,22 @@ static void computeKnownBitsFromOperator(const Operator *I, APInt &KnownZero,
// If this call is undefined for 0, the result will be less than 2^n.
if (II->getArgOperand(1) == ConstantInt::getTrue(II->getContext()))
LowBits -= 1;
- KnownZero.setBitsFrom(LowBits);
+ Known.Zero.setBitsFrom(LowBits);
break;
}
case Intrinsic::ctpop: {
- computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, Depth + 1, Q);
+ computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
// We can bound the space the count needs. Also, bits known to be zero
// can't contribute to the population.
- unsigned BitsPossiblySet = BitWidth - KnownZero2.countPopulation();
+ unsigned BitsPossiblySet = BitWidth - Known2.Zero.countPopulation();
unsigned LowBits = Log2_32(BitsPossiblySet)+1;
- KnownZero.setBitsFrom(LowBits);
+ Known.Zero.setBitsFrom(LowBits);
// TODO: we could bound KnownOne using the lower bound on the number
// of bits which might be set provided by popcnt KnownOne2.
break;
}
case Intrinsic::x86_sse42_crc32_64_64:
- KnownZero.setBitsFrom(32);
+ Known.Zero.setBitsFrom(32);
break;
}
}
@@ -1447,7 +1434,7 @@ static void computeKnownBitsFromOperator(const Operator *I, APInt &KnownZero,
// tracking the specific element. But at least we might find information
// valid for all elements of the vector (for example if vector is sign
// extended, shifted, etc).
- computeKnownBits(I->getOperand(0), KnownZero, KnownOne, Depth + 1, Q);
+ computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
break;
case Instruction::ExtractValue:
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I->getOperand(0))) {
@@ -1459,20 +1446,19 @@ static void computeKnownBitsFromOperator(const Operator *I, APInt &KnownZero,
case Intrinsic::uadd_with_overflow:
case Intrinsic::sadd_with_overflow:
computeKnownBitsAddSub(true, II->getArgOperand(0),
- II->getArgOperand(1), false, KnownZero,
- KnownOne, KnownZero2, KnownOne2, Depth, Q);
+ II->getArgOperand(1), false, Known, Known2,
+ 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, Depth, Q);
+ II->getArgOperand(1), false, Known, Known2,
+ 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, Depth,
- Q);
+ Known, Known2, Depth, Q);
break;
}
}
@@ -1481,7 +1467,7 @@ static void computeKnownBitsFromOperator(const Operator *I, APInt &KnownZero,
}
/// Determine which bits of V are known to be either zero or one and return
-/// them in the KnownZero/KnownOne bit sets.
+/// them in the Known bit set.
///
/// NOTE: we cannot consider 'undef' to be "IsZero" here. The problem is that
/// we cannot optimize based on the assumption that it is zero without changing
@@ -1495,11 +1481,11 @@ static void computeKnownBitsFromOperator(const Operator *I, APInt &KnownZero,
/// where V is a vector, known zero, and known one values are the
/// same width as the vector element, and the bit is set only if it is true
/// for all of the elements in the vector.
-void computeKnownBits(const Value *V, APInt &KnownZero, APInt &KnownOne,
- unsigned Depth, const Query &Q) {
+void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth,
+ const Query &Q) {
assert(V && "No Value?");
assert(Depth <= MaxDepth && "Limit Search Depth");
- unsigned BitWidth = KnownZero.getBitWidth();
+ unsigned BitWidth = Known.getBitWidth();
assert((V->getType()->isIntOrIntVectorTy() ||
V->getType()->getScalarType()->isPointerTy()) &&
@@ -1507,22 +1493,20 @@ void computeKnownBits(const Value *V, APInt &KnownZero, APInt &KnownOne,
assert((Q.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");
+ "V and Known should have same BitWidth");
(void)BitWidth;
const APInt *C;
if (match(V, m_APInt(C))) {
// We know all of the bits for a scalar constant or a splat vector constant!
- KnownOne = *C;
- KnownZero = ~KnownOne;
+ Known.One = *C;
+ Known.Zero = ~Known.One;
return;
}
// Null and aggregate-zero are all-zeros.
if (isa<ConstantPointerNull>(V) || isa<ConstantAggregateZero>(V)) {
- KnownOne.clearAllBits();
- KnownZero.setAllBits();
+ Known.One.clearAllBits();
+ Known.Zero.setAllBits();
return;
}
// Handle a constant vector by taking the intersection of the known bits of
@@ -1530,12 +1514,12 @@ void computeKnownBits(const Value *V, APInt &KnownZero, APInt &KnownOne,
if (const ConstantDataSequential *CDS = dyn_cast<ConstantDataSequential>(V)) {
// We know that CDS must be a vector of integers. Take the intersection of
// each element.
- KnownZero.setAllBits(); KnownOne.setAllBits();
- APInt Elt(KnownZero.getBitWidth(), 0);
+ Known.Zero.setAllBits(); Known.One.setAllBits();
+ APInt Elt(BitWidth, 0);
for (unsigned i = 0, e = CDS->getNumElements(); i != e; ++i) {
Elt = CDS->getElementAsInteger(i);
- KnownZero &= ~Elt;
- KnownOne &= Elt;
+ Known.Zero &= ~Elt;
+ Known.One &= Elt;
}
return;
}
@@ -1543,25 +1527,25 @@ void computeKnownBits(const Value *V, APInt &KnownZero, APInt &KnownOne,
if (const auto *CV = dyn_cast<ConstantVector>(V)) {
// We know that CV must be a vector of integers. Take the intersection of
// each element.
- KnownZero.setAllBits(); KnownOne.setAllBits();
- APInt Elt(KnownZero.getBitWidth(), 0);
+ Known.Zero.setAllBits(); Known.One.setAllBits();
+ APInt Elt(BitWidth, 0);
for (unsigned i = 0, e = CV->getNumOperands(); i != e; ++i) {
Constant *Element = CV->getAggregateElement(i);
auto *ElementCI = dyn_cast_or_null<ConstantInt>(Element);
if (!ElementCI) {
- KnownZero.clearAllBits();
- KnownOne.clearAllBits();
+ Known.Zero.clearAllBits();
+ Known.One.clearAllBits();
return;
}
Elt = ElementCI->getValue();
- KnownZero &= ~Elt;
- KnownOne &= Elt;
+ Known.Zero &= ~Elt;
+ Known.One &= Elt;
}
return;
}
// Start out not knowing anything.
- KnownZero.clearAllBits(); KnownOne.clearAllBits();
+ Known.Zero.clearAllBits(); Known.One.clearAllBits();
// We can't imply anything about undefs.
if (isa<UndefValue>(V))
@@ -1580,27 +1564,27 @@ void computeKnownBits(const Value *V, APInt &KnownZero, APInt &KnownOne,
// the bits of its aliasee.
if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
if (!GA->isInterposable())
- computeKnownBits(GA->getAliasee(), KnownZero, KnownOne, Depth + 1, Q);
+ computeKnownBits(GA->getAliasee(), Known, Depth + 1, Q);
return;
}
if (const Operator *I = dyn_cast<Operator>(V))
- computeKnownBitsFromOperator(I, KnownZero, KnownOne, Depth, Q);
+ computeKnownBitsFromOperator(I, Known, Depth, Q);
- // Aligned pointers have trailing zeros - refine KnownZero set
+ // Aligned pointers have trailing zeros - refine Known.Zero set
if (V->getType()->isPointerTy()) {
unsigned Align = V->getPointerAlignment(Q.DL);
if (Align)
- KnownZero.setLowBits(countTrailingZeros(Align));
+ Known.Zero.setLowBits(countTrailingZeros(Align));
}
- // computeKnownBitsFromAssume strictly refines KnownZero and
- // KnownOne. Therefore, we run them after computeKnownBitsFromOperator.
+ // computeKnownBitsFromAssume strictly refines Known.
+ // Therefore, we run them after computeKnownBitsFromOperator.
// Check whether a nearby assume intrinsic can determine some known bits.
- computeKnownBitsFromAssume(V, KnownZero, KnownOne, Depth, Q);
+ computeKnownBitsFromAssume(V, Known, Depth, Q);
- assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
+ assert((Known.Zero & Known.One) == 0 && "Bits known to be one AND zero?");
}
/// Determine whether the sign bit is known to be zero or one.
@@ -1613,11 +1597,10 @@ void ComputeSignBit(const Value *V, bool &KnownZero, bool &KnownOne,
KnownOne = false;
return;
}
- APInt ZeroBits(BitWidth, 0);
- APInt OneBits(BitWidth, 0);
- computeKnownBits(V, ZeroBits, OneBits, Depth, Q);
- KnownOne = OneBits.isSignBitSet();
- KnownZero = ZeroBits.isSignBitSet();
+ KnownBits Bits(BitWidth);
+ computeKnownBits(V, Bits, Depth, Q);
+ KnownOne = Bits.One.isSignBitSet();
+ KnownZero = Bits.Zero.isSignBitSet();
}
/// Return true if the given value is known to have exactly one
@@ -1689,18 +1672,18 @@ bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero, unsigned Depth,
return true;
unsigned BitWidth = V->getType()->getScalarSizeInBits();
- APInt LHSZeroBits(BitWidth, 0), LHSOneBits(BitWidth, 0);
- computeKnownBits(X, LHSZeroBits, LHSOneBits, Depth, Q);
+ KnownBits LHSBits(BitWidth);
+ computeKnownBits(X, LHSBits, Depth, Q);
- APInt RHSZeroBits(BitWidth, 0), RHSOneBits(BitWidth, 0);
- computeKnownBits(Y, RHSZeroBits, RHSOneBits, Depth, Q);
+ KnownBits RHSBits(BitWidth);
+ computeKnownBits(Y, RHSBits, Depth, Q);
// If i8 V is a power of two or zero:
// ZeroBits: 1 1 1 0 1 1 1 1
// ~ZeroBits: 0 0 0 1 0 0 0 0
- if ((~(LHSZeroBits & RHSZeroBits)).isPowerOf2())
+ if ((~(LHSBits.Zero & RHSBits.Zero)).isPowerOf2())
// If OrZero isn't set, we cannot give back a zero result.
// Make sure either the LHS or RHS has a bit set.
- if (OrZero || RHSOneBits.getBoolValue() || LHSOneBits.getBoolValue())
+ if (OrZero || RHSBits.One.getBoolValue() || LHSBits.One.getBoolValue())
return true;
}
}
@@ -1871,10 +1854,9 @@ bool isKnownNonZero(const Value *V, unsigned Depth, const Query &Q) {
if (BO->hasNoUnsignedWrap())
return isKnownNonZero(X, Depth, Q);
- APInt KnownZero(BitWidth, 0);
- APInt KnownOne(BitWidth, 0);
- computeKnownBits(X, KnownZero, KnownOne, Depth, Q);
- if (KnownOne[0])
+ KnownBits Known(BitWidth);
+ computeKnownBits(X, Known, Depth, Q);
+ if (Known.One[0])
return true;
}
// shr X, Y != 0 if X is negative. Note that the value of the shift is not
@@ -1894,16 +1876,15 @@ bool isKnownNonZero(const Value *V, unsigned Depth, const Query &Q) {
// out are known to be zero, and X is known non-zero then at least one
// non-zero bit must remain.
if (ConstantInt *Shift = dyn_cast<ConstantInt>(Y)) {
- APInt KnownZero(BitWidth, 0);
- APInt KnownOne(BitWidth, 0);
- computeKnownBits(X, KnownZero, KnownOne, Depth, Q);
+ KnownBits Known(BitWidth);
+ computeKnownBits(X, Known, Depth, Q);
auto ShiftVal = Shift->getLimitedValue(BitWidth - 1);
// Is there a known one in the portion not shifted out?
- if (KnownOne.countLeadingZeros() < BitWidth - ShiftVal)
+ if (Known.One.countLeadingZeros() < BitWidth - ShiftVal)
return true;
// Are all the bits to be shifted out known zero?
- if (KnownZero.countTrailingOnes() >= ShiftVal)
+ if (Known.Zero.countTrailingOnes() >= ShiftVal)
return isKnownNonZero(X, Depth, Q);
}
}
@@ -1927,18 +1908,17 @@ bool isKnownNonZero(const Value *V, unsigned Depth, const Query &Q) {
// If X and Y are both negative (as signed values) then their sum is not
// zero unless both X and Y equal INT_MIN.
if (BitWidth && XKnownNegative && YKnownNegative) {
- APInt KnownZero(BitWidth, 0);
- APInt KnownOne(BitWidth, 0);
+ KnownBits Known(BitWidth);
APInt Mask = APInt::getSignedMaxValue(BitWidth);
// The sign bit of X is set. If some other bit is set then X is not equal
// to INT_MIN.
- computeKnownBits(X, KnownZero, KnownOne, Depth, Q);
- if ((KnownOne & Mask) != 0)
+ computeKnownBits(X, Known, Depth, Q);
+ if (Known.One.intersects(Mask))
return true;
// The sign bit of Y is set. If some other bit is set then Y is not equal
// to INT_MIN.
- computeKnownBits(Y, KnownZero, KnownOne, Depth, Q);
- if ((KnownOne & Mask) != 0)
+ computeKnownBits(Y, Known, Depth, Q);
+ if (Known.One.intersects(Mask))
return true;
}
@@ -1993,10 +1973,9 @@ bool isKnownNonZero(const Value *V, unsigned Depth, const Query &Q) {
}
if (!BitWidth) return false;
- APInt KnownZero(BitWidth, 0);
- APInt KnownOne(BitWidth, 0);
- computeKnownBits(V, KnownZero, KnownOne, Depth, Q);
- return KnownOne != 0;
+ KnownBits Known(BitWidth);
+ computeKnownBits(V, Known, Depth, Q);
+ return Known.One != 0;
}
/// Return true if V2 == V1 + X, where X is known non-zero.
@@ -2028,14 +2007,13 @@ static bool isKnownNonEqual(const Value *V1, const Value *V2, const Query &Q) {
// Are any known bits in V1 contradictory to known bits in V2? If V1
// has a known zero where V2 has a known one, they must not be equal.
auto BitWidth = Ty->getBitWidth();
- APInt KnownZero1(BitWidth, 0);
- APInt KnownOne1(BitWidth, 0);
- computeKnownBits(V1, KnownZero1, KnownOne1, 0, Q);
- APInt KnownZero2(BitWidth, 0);
- APInt KnownOne2(BitWidth, 0);
- computeKnownBits(V2, KnownZero2, KnownOne2, 0, Q);
+ KnownBits Known1(BitWidth);
+ computeKnownBits(V1, Known1, 0, Q);
+ KnownBits Known2(BitWidth);
+ computeKnownBits(V2, Known2, 0, Q);
- auto OppositeBits = (KnownZero1 & KnownOne2) | (KnownZero2 & KnownOne1);
+ APInt OppositeBits = (Known1.Zero & Known2.One) |
+ (Known2.Zero & Known1.One);
if (OppositeBits.getBoolValue())
return true;
}
@@ -2053,9 +2031,9 @@ static bool isKnownNonEqual(const Value *V1, const Value *V2, const Query &Q) {
/// for all of the elements in the vector.
bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth,
const Query &Q) {
- APInt KnownZero(Mask.getBitWidth(), 0), KnownOne(Mask.getBitWidth(), 0);
- computeKnownBits(V, KnownZero, KnownOne, Depth, Q);
- return (KnownZero & Mask) == Mask;
+ KnownBits Known(Mask.getBitWidth());
+ computeKnownBits(V, Known, Depth, Q);
+ return Mask.isSubsetOf(Known.Zero);
}
/// For vector constants, loop over the elements and find the constant with the
@@ -2233,17 +2211,17 @@ static unsigned ComputeNumSignBitsImpl(const Value *V, unsigned Depth,
// Special case decrementing a value (ADD X, -1):
if (const auto *CRHS = dyn_cast<Constant>(U->getOperand(1)))
if (CRHS->isAllOnesValue()) {
- APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0);
- computeKnownBits(U->getOperand(0), KnownZero, KnownOne, Depth + 1, Q);
+ KnownBits Known(TyBits);
+ computeKnownBits(U->getOperand(0), Known, Depth + 1, Q);
// If the input is known to be 0 or 1, the output is 0/-1, which is all
// sign bits set.
- if ((KnownZero | APInt(TyBits, 1)).isAllOnesValue())
+ if ((Known.Zero | 1).isAllOnesValue())
return TyBits;
// If we are subtracting one from a positive number, there is no carry
// out of the result.
- if (KnownZero.isSignBitSet())
+ if (Known.Zero.isSignBitSet())
return Tmp;
}
@@ -2258,16 +2236,16 @@ static unsigned ComputeNumSignBitsImpl(const Value *V, unsigned Depth,
// Handle NEG.
if (const auto *CLHS = dyn_cast<Constant>(U->getOperand(0)))
if (CLHS->isNullValue()) {
- APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0);
- computeKnownBits(U->getOperand(1), KnownZero, KnownOne, Depth + 1, Q);
+ KnownBits Known(TyBits);
+ computeKnownBits(U->getOperand(1), Known, Depth + 1, Q);
// If the input is known to be 0 or 1, the output is 0/-1, which is all
// sign bits set.
- if ((KnownZero | APInt(TyBits, 1)).isAllOnesValue())
+ if ((Known.Zero | 1).isAllOnesValue())
return TyBits;
// If the input is known to be positive (the sign bit is known clear),
// the output of the NEG has the same number of sign bits as the input.
- if (KnownZero.isSignBitSet())
+ if (Known.Zero.isSignBitSet())
return Tmp2;
// Otherwise, we treat this like a SUB.
@@ -2319,16 +2297,16 @@ static unsigned ComputeNumSignBitsImpl(const Value *V, unsigned Depth,
if (unsigned VecSignBits = computeNumSignBitsVectorConstant(V, TyBits))
return VecSignBits;
- APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0);
- computeKnownBits(V, KnownZero, KnownOne, Depth, Q);
+ KnownBits Known(TyBits);
+ computeKnownBits(V, Known, Depth, Q);
// If we know that the sign bit is either zero or one, determine the number of
// identical bits in the top of the input value.
- if (KnownZero.isSignBitSet())
- return std::max(FirstAnswer, KnownZero.countLeadingOnes());
+ if (Known.Zero.isSignBitSet())
+ return std::max(FirstAnswer, Known.Zero.countLeadingOnes());
- if (KnownOne.isSignBitSet())
- return std::max(FirstAnswer, KnownOne.countLeadingOnes());
+ if (Known.One.isSignBitSet())
+ return std::max(FirstAnswer, Known.One.countLeadingOnes());
// computeKnownBits gave us no extra information about the top bits.
return FirstAnswer;
@@ -3534,26 +3512,22 @@ OverflowResult llvm::computeOverflowForUnsignedMul(const Value *LHS,
// we can guarantee that the result does not overflow.
// Ref: "Hacker's Delight" by Henry Warren
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, /*Depth=*/0, AC, CxtI,
- DT);
- computeKnownBits(RHS, RHSKnownZero, RHSKnownOne, DL, /*Depth=*/0, AC, CxtI,
- DT);
+ KnownBits LHSKnown(BitWidth);
+ KnownBits RHSKnown(BitWidth);
+ computeKnownBits(LHS, LHSKnown, DL, /*Depth=*/0, AC, CxtI, DT);
+ computeKnownBits(RHS, RHSKnown, DL, /*Depth=*/0, AC, CxtI, DT);
// Note that underestimating the number of zero bits gives a more
// conservative answer.
- unsigned ZeroBits = LHSKnownZero.countLeadingOnes() +
- RHSKnownZero.countLeadingOnes();
+ unsigned ZeroBits = LHSKnown.Zero.countLeadingOnes() +
+ RHSKnown.Zero.countLeadingOnes();
// First handle the easy case: if we have enough zero bits there's
// definitely no overflow.
if (ZeroBits >= BitWidth)
return OverflowResult::NeverOverflows;
// Get the largest possible values for each operand.
- APInt LHSMax = ~LHSKnownZero;
- APInt RHSMax = ~RHSKnownZero;
+ APInt LHSMax = ~LHSKnown.Zero;
+ APInt RHSMax = ~RHSKnown.Zero;
// We know the multiply operation doesn't overflow if the maximum values for
// each operand will not overflow after we multiply them together.
@@ -3565,7 +3539,7 @@ OverflowResult llvm::computeOverflowForUnsignedMul(const Value *LHS,
// We know it always overflows if multiplying the smallest possible values for
// the operands also results in overflow.
bool MinOverflow;
- (void)LHSKnownOne.umul_ov(RHSKnownOne, MinOverflow);
+ (void)LHSKnown.One.umul_ov(RHSKnown.One, MinOverflow);
if (MinOverflow)
return OverflowResult::AlwaysOverflows;
@@ -4284,11 +4258,10 @@ static bool isTruePredicate(CmpInst::Predicate Pred,
// If X & C == 0 then (X | C) == X +_{nuw} C
if (match(A, m_Or(m_Value(X), m_APInt(CA))) &&
match(B, m_Or(m_Specific(X), m_APInt(CB)))) {
- unsigned BitWidth = CA->getBitWidth();
- APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
- computeKnownBits(X, KnownZero, KnownOne, DL, Depth + 1, AC, CxtI, DT);
+ KnownBits Known(CA->getBitWidth());
+ computeKnownBits(X, Known, DL, Depth + 1, AC, CxtI, DT);
- if ((KnownZero & *CA) == *CA && (KnownZero & *CB) == *CB)
+ if (CA->isSubsetOf(Known.Zero) && CB->isSubsetOf(Known.Zero))
return true;
}
generated by cgit v1.3 (git 2.53.0) at 2026-07-31 00:29:19 +0000