summaryrefslogtreecommitdiff
path: root/lib/Analysis
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Analysis')
-rw-r--r--lib/Analysis/AliasSetTracker.cpp4
-rw-r--r--lib/Analysis/AssumptionCache.cpp11
-rw-r--r--lib/Analysis/BasicAliasAnalysis.cpp19
-rw-r--r--lib/Analysis/CFLSteensAliasAnalysis.cpp3
-rw-r--r--lib/Analysis/DemandedBits.cpp2
-rw-r--r--lib/Analysis/InlineCost.cpp16
-rw-r--r--lib/Analysis/InstructionSimplify.cpp6
-rw-r--r--lib/Analysis/LazyValueInfo.cpp30
-rw-r--r--lib/Analysis/Loads.cpp10
-rw-r--r--lib/Analysis/MemoryDependenceAnalysis.cpp6
-rw-r--r--lib/Analysis/ScalarEvolution.cpp133
-rw-r--r--lib/Analysis/ScalarEvolutionExpander.cpp48
-rw-r--r--lib/Analysis/TypeBasedAliasAnalysis.cpp2
-rw-r--r--lib/Analysis/ValueTracking.cpp7
14 files changed, 176 insertions, 121 deletions
diff --git a/lib/Analysis/AliasSetTracker.cpp b/lib/Analysis/AliasSetTracker.cpp
index ee17ad3ba5863..4dfa25490d00d 100644
--- a/lib/Analysis/AliasSetTracker.cpp
+++ b/lib/Analysis/AliasSetTracker.cpp
@@ -218,8 +218,8 @@ bool AliasSet::aliasesUnknownInst(const Instruction *Inst,
return false;
for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
- if (auto *Inst = getUnknownInst(i)) {
- ImmutableCallSite C1(Inst), C2(Inst);
+ if (auto *UnknownInst = getUnknownInst(i)) {
+ ImmutableCallSite C1(UnknownInst), C2(Inst);
if (!C1 || !C2 || AA.getModRefInfo(C1, C2) != MRI_NoModRef ||
AA.getModRefInfo(C2, C1) != MRI_NoModRef)
return true;
diff --git a/lib/Analysis/AssumptionCache.cpp b/lib/Analysis/AssumptionCache.cpp
index 0468c794e81dd..3ff27890dc385 100644
--- a/lib/Analysis/AssumptionCache.cpp
+++ b/lib/Analysis/AssumptionCache.cpp
@@ -84,18 +84,11 @@ void AssumptionCache::updateAffectedValues(CallInst *CI) {
Value *B;
ConstantInt *C;
// (A & B) or (A | B) or (A ^ B).
- if (match(V,
- m_CombineOr(m_And(m_Value(A), m_Value(B)),
- m_CombineOr(m_Or(m_Value(A), m_Value(B)),
- m_Xor(m_Value(A), m_Value(B)))))) {
+ if (match(V, m_BitwiseLogic(m_Value(A), m_Value(B)))) {
AddAffected(A);
AddAffected(B);
// (A << C) or (A >>_s C) or (A >>_u C) where C is some constant.
- } else if (match(V,
- m_CombineOr(m_Shl(m_Value(A), m_ConstantInt(C)),
- m_CombineOr(m_LShr(m_Value(A), m_ConstantInt(C)),
- m_AShr(m_Value(A),
- m_ConstantInt(C)))))) {
+ } else if (match(V, m_Shift(m_Value(A), m_ConstantInt(C)))) {
AddAffected(A);
}
};
diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp
index dbb1b01b94ac2..b52a1d7b24d62 100644
--- a/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/lib/Analysis/BasicAliasAnalysis.cpp
@@ -1021,11 +1021,14 @@ static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
// asking about values from different loop iterations. See PR32314.
// TODO: We may be able to change the check so we only do this when
// we definitely looked through a PHINode.
- KnownBits Known1 = computeKnownBits(GEP1LastIdx, DL);
- KnownBits Known2 = computeKnownBits(GEP2LastIdx, DL);
- if (Known1.Zero.intersects(Known2.One) ||
- Known1.One.intersects(Known2.Zero))
- return NoAlias;
+ if (GEP1LastIdx != GEP2LastIdx &&
+ GEP1LastIdx->getType() == GEP2LastIdx->getType()) {
+ KnownBits Known1 = computeKnownBits(GEP1LastIdx, DL);
+ KnownBits Known2 = computeKnownBits(GEP2LastIdx, DL);
+ if (Known1.Zero.intersects(Known2.One) ||
+ Known1.One.intersects(Known2.Zero))
+ return NoAlias;
+ }
} else if (isKnownNonEqual(GEP1LastIdx, GEP2LastIdx, DL))
return NoAlias;
}
@@ -1345,11 +1348,7 @@ AliasResult BasicAAResult::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size,
// Statically, we can see that the base objects are the same, but the
// pointers have dynamic offsets which we can't resolve. And none of our
// little tricks above worked.
- //
- // TODO: Returning PartialAlias instead of MayAlias is a mild hack; the
- // practical effect of this is protecting TBAA in the case of dynamic
- // indices into arrays of unions or malloc'd memory.
- return PartialAlias;
+ return MayAlias;
}
static AliasResult MergeAliasResults(AliasResult A, AliasResult B) {
diff --git a/lib/Analysis/CFLSteensAliasAnalysis.cpp b/lib/Analysis/CFLSteensAliasAnalysis.cpp
index dde24ef5fdd57..6e4263920e586 100644
--- a/lib/Analysis/CFLSteensAliasAnalysis.cpp
+++ b/lib/Analysis/CFLSteensAliasAnalysis.cpp
@@ -80,9 +80,6 @@ public:
const AliasSummary &getAliasSummary() const { return Summary; }
};
-/// Try to go from a Value* to a Function*. Never returns nullptr.
-static Optional<Function *> parentFunctionOfValue(Value *);
-
const StratifiedIndex StratifiedLink::SetSentinel =
std::numeric_limits<StratifiedIndex>::max();
diff --git a/lib/Analysis/DemandedBits.cpp b/lib/Analysis/DemandedBits.cpp
index 8f808f3e78719..926b28d6094a5 100644
--- a/lib/Analysis/DemandedBits.cpp
+++ b/lib/Analysis/DemandedBits.cpp
@@ -107,6 +107,8 @@ void DemandedBits::determineLiveOperandBits(
AB = AOut.byteSwap();
break;
case Intrinsic::bitreverse:
+ // The alive bits of the input are the reversed alive bits of
+ // the output.
AB = AOut.reverseBits();
break;
case Intrinsic::ctlz:
diff --git a/lib/Analysis/InlineCost.cpp b/lib/Analysis/InlineCost.cpp
index 6ff5938a3175a..77ad6f1e166fd 100644
--- a/lib/Analysis/InlineCost.cpp
+++ b/lib/Analysis/InlineCost.cpp
@@ -1022,12 +1022,15 @@ bool CallAnalyzer::visitSwitchInst(SwitchInst &SI) {
// inlining those. It will prevent inlining in cases where the optimization
// does not (yet) fire.
+ // Maximum valid cost increased in this function.
+ int CostUpperBound = INT_MAX - InlineConstants::InstrCost - 1;
+
// Exit early for a large switch, assuming one case needs at least one
// instruction.
// FIXME: This is not true for a bit test, but ignore such case for now to
// save compile-time.
int64_t CostLowerBound =
- std::min((int64_t)INT_MAX,
+ std::min((int64_t)CostUpperBound,
(int64_t)SI.getNumCases() * InlineConstants::InstrCost + Cost);
if (CostLowerBound > Threshold) {
@@ -1044,7 +1047,8 @@ bool CallAnalyzer::visitSwitchInst(SwitchInst &SI) {
if (JumpTableSize) {
int64_t JTCost = (int64_t)JumpTableSize * InlineConstants::InstrCost +
4 * InlineConstants::InstrCost;
- Cost = std::min((int64_t)INT_MAX, JTCost + Cost);
+
+ Cost = std::min((int64_t)CostUpperBound, JTCost + Cost);
return false;
}
@@ -1068,10 +1072,12 @@ bool CallAnalyzer::visitSwitchInst(SwitchInst &SI) {
Cost += NumCaseCluster * 2 * InlineConstants::InstrCost;
return false;
}
- int64_t ExpectedNumberOfCompare = 3 * (uint64_t)NumCaseCluster / 2 - 1;
- uint64_t SwitchCost =
+
+ int64_t ExpectedNumberOfCompare = 3 * (int64_t)NumCaseCluster / 2 - 1;
+ int64_t SwitchCost =
ExpectedNumberOfCompare * 2 * InlineConstants::InstrCost;
- Cost = std::min((uint64_t)INT_MAX, SwitchCost + Cost);
+
+ Cost = std::min((int64_t)CostUpperBound, SwitchCost + Cost);
return false;
}
diff --git a/lib/Analysis/InstructionSimplify.cpp b/lib/Analysis/InstructionSimplify.cpp
index a975be79619b7..d9e32a3c417e0 100644
--- a/lib/Analysis/InstructionSimplify.cpp
+++ b/lib/Analysis/InstructionSimplify.cpp
@@ -2688,16 +2688,14 @@ static Value *simplifyICmpWithBinOp(CmpInst::Predicate Pred, Value *LHS,
}
// icmp pred (and X, Y), X
- if (LBO && match(LBO, m_CombineOr(m_And(m_Value(), m_Specific(RHS)),
- m_And(m_Specific(RHS), m_Value())))) {
+ if (LBO && match(LBO, m_c_And(m_Value(), m_Specific(RHS)))) {
if (Pred == ICmpInst::ICMP_UGT)
return getFalse(ITy);
if (Pred == ICmpInst::ICMP_ULE)
return getTrue(ITy);
}
// icmp pred X, (and X, Y)
- if (RBO && match(RBO, m_CombineOr(m_And(m_Value(), m_Specific(LHS)),
- m_And(m_Specific(LHS), m_Value())))) {
+ if (RBO && match(RBO, m_c_And(m_Value(), m_Specific(LHS)))) {
if (Pred == ICmpInst::ICMP_UGE)
return getTrue(ITy);
if (Pred == ICmpInst::ICMP_ULT)
diff --git a/lib/Analysis/LazyValueInfo.cpp b/lib/Analysis/LazyValueInfo.cpp
index 3ed61a79478ad..102081e721ac6 100644
--- a/lib/Analysis/LazyValueInfo.cpp
+++ b/lib/Analysis/LazyValueInfo.cpp
@@ -1324,12 +1324,12 @@ getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest,
return getValueFromICmpCondition(Val, ICI, isTrueDest);
// Handle conditions in the form of (cond1 && cond2), we know that on the
- // true dest path both of the conditions hold.
- if (!isTrueDest)
- return LVILatticeVal::getOverdefined();
-
+ // true dest path both of the conditions hold. Similarly for conditions of
+ // the form (cond1 || cond2), we know that on the false dest path neither
+ // condition holds.
BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond);
- if (!BO || BO->getOpcode() != BinaryOperator::And)
+ if (!BO || (isTrueDest && BO->getOpcode() != BinaryOperator::And) ||
+ (!isTrueDest && BO->getOpcode() != BinaryOperator::Or))
return LVILatticeVal::getOverdefined();
auto RHS = getValueFromCondition(Val, BO->getOperand(0), isTrueDest, Visited);
@@ -1660,6 +1660,26 @@ Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
return nullptr;
}
+ConstantRange LazyValueInfo::getConstantRangeOnEdge(Value *V,
+ BasicBlock *FromBB,
+ BasicBlock *ToBB,
+ Instruction *CxtI) {
+ unsigned Width = V->getType()->getIntegerBitWidth();
+ const DataLayout &DL = FromBB->getModule()->getDataLayout();
+ LVILatticeVal Result =
+ getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
+
+ if (Result.isUndefined())
+ return ConstantRange(Width, /*isFullSet=*/false);
+ if (Result.isConstantRange())
+ return Result.getConstantRange();
+ // We represent ConstantInt constants as constant ranges but other kinds
+ // of integer constants, i.e. ConstantExpr will be tagged as constants
+ assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
+ "ConstantInt value must be represented as constantrange");
+ return ConstantRange(Width, /*isFullSet=*/true);
+}
+
static LazyValueInfo::Tristate getPredicateResult(unsigned Pred, Constant *C,
const LVILatticeVal &Val,
const DataLayout &DL,
diff --git a/lib/Analysis/Loads.cpp b/lib/Analysis/Loads.cpp
index 96799a459bfc4..591b0fc481d24 100644
--- a/lib/Analysis/Loads.cpp
+++ b/lib/Analysis/Loads.cpp
@@ -117,6 +117,16 @@ static bool isDereferenceableAndAlignedPointer(
}
bool llvm::isDereferenceableAndAlignedPointer(const Value *V, unsigned Align,
+ const APInt &Size,
+ const DataLayout &DL,
+ const Instruction *CtxI,
+ const DominatorTree *DT) {
+ SmallPtrSet<const Value *, 32> Visited;
+ return ::isDereferenceableAndAlignedPointer(V, Align, Size, DL, CtxI, DT,
+ Visited);
+}
+
+bool llvm::isDereferenceableAndAlignedPointer(const Value *V, unsigned Align,
const DataLayout &DL,
const Instruction *CtxI,
const DominatorTree *DT) {
diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp
index 3fdedbb0ab3c2..263cf42ebe271 100644
--- a/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -310,11 +310,11 @@ unsigned MemoryDependenceResults::getLoadLoadClobberFullWidthSize(
}
static bool isVolatile(Instruction *Inst) {
- if (LoadInst *LI = dyn_cast<LoadInst>(Inst))
+ if (auto *LI = dyn_cast<LoadInst>(Inst))
return LI->isVolatile();
- else if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
+ if (auto *SI = dyn_cast<StoreInst>(Inst))
return SI->isVolatile();
- else if (AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(Inst))
+ if (auto *AI = dyn_cast<AtomicCmpXchgInst>(Inst))
return AI->isVolatile();
return false;
}
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index aebc80a0a8851..73a95ec405c7b 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -126,11 +126,11 @@ static cl::opt<bool>
static cl::opt<unsigned> MulOpsInlineThreshold(
"scev-mulops-inline-threshold", cl::Hidden,
cl::desc("Threshold for inlining multiplication operands into a SCEV"),
- cl::init(1000));
+ cl::init(32));
static cl::opt<unsigned> AddOpsInlineThreshold(
"scev-addops-inline-threshold", cl::Hidden,
- cl::desc("Threshold for inlining multiplication operands into a SCEV"),
+ cl::desc("Threshold for inlining addition operands into a SCEV"),
cl::init(500));
static cl::opt<unsigned> MaxSCEVCompareDepth(
@@ -1259,12 +1259,12 @@ static const SCEV *getSignedOverflowLimitForStep(const SCEV *Step,
if (SE->isKnownPositive(Step)) {
*Pred = ICmpInst::ICMP_SLT;
return SE->getConstant(APInt::getSignedMinValue(BitWidth) -
- SE->getSignedRange(Step).getSignedMax());
+ SE->getSignedRangeMax(Step));
}
if (SE->isKnownNegative(Step)) {
*Pred = ICmpInst::ICMP_SGT;
return SE->getConstant(APInt::getSignedMaxValue(BitWidth) -
- SE->getSignedRange(Step).getSignedMin());
+ SE->getSignedRangeMin(Step));
}
return nullptr;
}
@@ -1279,7 +1279,7 @@ static const SCEV *getUnsignedOverflowLimitForStep(const SCEV *Step,
*Pred = ICmpInst::ICMP_ULT;
return SE->getConstant(APInt::getMinValue(BitWidth) -
- SE->getUnsignedRange(Step).getUnsignedMax());
+ SE->getUnsignedRangeMax(Step));
}
namespace {
@@ -1670,7 +1670,7 @@ const SCEV *ScalarEvolution::getZeroExtendExprImpl(const SCEV *Op, Type *Ty,
// is safe.
if (isKnownPositive(Step)) {
const SCEV *N = getConstant(APInt::getMinValue(BitWidth) -
- getUnsignedRange(Step).getUnsignedMax());
+ getUnsignedRangeMax(Step));
if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_ULT, AR, N) ||
(isLoopEntryGuardedByCond(L, ICmpInst::ICMP_ULT, Start, N) &&
isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_ULT,
@@ -1686,7 +1686,7 @@ const SCEV *ScalarEvolution::getZeroExtendExprImpl(const SCEV *Op, Type *Ty,
}
} else if (isKnownNegative(Step)) {
const SCEV *N = getConstant(APInt::getMaxValue(BitWidth) -
- getSignedRange(Step).getSignedMin());
+ getSignedRangeMin(Step));
if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_UGT, AR, N) ||
(isLoopEntryGuardedByCond(L, ICmpInst::ICMP_UGT, Start, N) &&
isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_UGT,
@@ -3745,7 +3745,7 @@ const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
// makes it so that we cannot make much use of NUW.
auto AddFlags = SCEV::FlagAnyWrap;
const bool RHSIsNotMinSigned =
- !getSignedRange(RHS).getSignedMin().isMinSignedValue();
+ !getSignedRangeMin(RHS).isMinSignedValue();
if (maskFlags(Flags, SCEV::FlagNSW) == SCEV::FlagNSW) {
// Let M be the minimum representable signed value. Then (-1)*RHS
// signed-wraps if and only if RHS is M. That can happen even for
@@ -4758,9 +4758,9 @@ static Optional<ConstantRange> GetRangeFromMetadata(Value *V) {
/// Determine the range for a particular SCEV. If SignHint is
/// HINT_RANGE_UNSIGNED (resp. HINT_RANGE_SIGNED) then getRange prefers ranges
/// with a "cleaner" unsigned (resp. signed) representation.
-ConstantRange
-ScalarEvolution::getRange(const SCEV *S,
- ScalarEvolution::RangeSignHint SignHint) {
+const ConstantRange &
+ScalarEvolution::getRangeRef(const SCEV *S,
+ ScalarEvolution::RangeSignHint SignHint) {
DenseMap<const SCEV *, ConstantRange> &Cache =
SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
: SignedRanges;
@@ -4791,54 +4791,54 @@ ScalarEvolution::getRange(const SCEV *S,
}
if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
- ConstantRange X = getRange(Add->getOperand(0), SignHint);
+ ConstantRange X = getRangeRef(Add->getOperand(0), SignHint);
for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i)
- X = X.add(getRange(Add->getOperand(i), SignHint));
+ X = X.add(getRangeRef(Add->getOperand(i), SignHint));
return setRange(Add, SignHint, ConservativeResult.intersectWith(X));
}
if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) {
- ConstantRange X = getRange(Mul->getOperand(0), SignHint);
+ ConstantRange X = getRangeRef(Mul->getOperand(0), SignHint);
for (unsigned i = 1, e = Mul->getNumOperands(); i != e; ++i)
- X = X.multiply(getRange(Mul->getOperand(i), SignHint));
+ X = X.multiply(getRangeRef(Mul->getOperand(i), SignHint));
return setRange(Mul, SignHint, ConservativeResult.intersectWith(X));
}
if (const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(S)) {
- ConstantRange X = getRange(SMax->getOperand(0), SignHint);
+ ConstantRange X = getRangeRef(SMax->getOperand(0), SignHint);
for (unsigned i = 1, e = SMax->getNumOperands(); i != e; ++i)
- X = X.smax(getRange(SMax->getOperand(i), SignHint));
+ X = X.smax(getRangeRef(SMax->getOperand(i), SignHint));
return setRange(SMax, SignHint, ConservativeResult.intersectWith(X));
}
if (const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(S)) {
- ConstantRange X = getRange(UMax->getOperand(0), SignHint);
+ ConstantRange X = getRangeRef(UMax->getOperand(0), SignHint);
for (unsigned i = 1, e = UMax->getNumOperands(); i != e; ++i)
- X = X.umax(getRange(UMax->getOperand(i), SignHint));
+ X = X.umax(getRangeRef(UMax->getOperand(i), SignHint));
return setRange(UMax, SignHint, ConservativeResult.intersectWith(X));
}
if (const SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(S)) {
- ConstantRange X = getRange(UDiv->getLHS(), SignHint);
- ConstantRange Y = getRange(UDiv->getRHS(), SignHint);
+ ConstantRange X = getRangeRef(UDiv->getLHS(), SignHint);
+ ConstantRange Y = getRangeRef(UDiv->getRHS(), SignHint);
return setRange(UDiv, SignHint,
ConservativeResult.intersectWith(X.udiv(Y)));
}
if (const SCEVZeroExtendExpr *ZExt = dyn_cast<SCEVZeroExtendExpr>(S)) {
- ConstantRange X = getRange(ZExt->getOperand(), SignHint);
+ ConstantRange X = getRangeRef(ZExt->getOperand(), SignHint);
return setRange(ZExt, SignHint,
ConservativeResult.intersectWith(X.zeroExtend(BitWidth)));
}
if (const SCEVSignExtendExpr *SExt = dyn_cast<SCEVSignExtendExpr>(S)) {
- ConstantRange X = getRange(SExt->getOperand(), SignHint);
+ ConstantRange X = getRangeRef(SExt->getOperand(), SignHint);
return setRange(SExt, SignHint,
ConservativeResult.intersectWith(X.signExtend(BitWidth)));
}
if (const SCEVTruncateExpr *Trunc = dyn_cast<SCEVTruncateExpr>(S)) {
- ConstantRange X = getRange(Trunc->getOperand(), SignHint);
+ ConstantRange X = getRangeRef(Trunc->getOperand(), SignHint);
return setRange(Trunc, SignHint,
ConservativeResult.intersectWith(X.truncate(BitWidth)));
}
@@ -5005,8 +5005,7 @@ ConstantRange ScalarEvolution::getRangeForAffineAR(const SCEV *Start,
"Precondition!");
MaxBECount = getNoopOrZeroExtend(MaxBECount, Start->getType());
- ConstantRange MaxBECountRange = getUnsignedRange(MaxBECount);
- APInt MaxBECountValue = MaxBECountRange.getUnsignedMax();
+ APInt MaxBECountValue = getUnsignedRangeMax(MaxBECount);
// First, consider step signed.
ConstantRange StartSRange = getSignedRange(Start);
@@ -5023,7 +5022,7 @@ ConstantRange ScalarEvolution::getRangeForAffineAR(const SCEV *Start,
// Next, consider step unsigned.
ConstantRange UR = getRangeForAffineARHelper(
- getUnsignedRange(Step).getUnsignedMax(), getUnsignedRange(Start),
+ getUnsignedRangeMax(Step), getUnsignedRange(Start),
MaxBECountValue, BitWidth, /* Signed = */ false);
// Finally, intersect signed and unsigned ranges.
@@ -6373,7 +6372,7 @@ ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
// to not.
if (isa<SCEVCouldNotCompute>(MaxBECount) &&
!isa<SCEVCouldNotCompute>(BECount))
- MaxBECount = getConstant(getUnsignedRange(BECount).getUnsignedMax());
+ MaxBECount = getConstant(getUnsignedRangeMax(BECount));
return ExitLimit(BECount, MaxBECount, false,
{&EL0.Predicates, &EL1.Predicates});
@@ -7647,7 +7646,7 @@ ScalarEvolution::howFarToZero(const SCEV *V, const Loop *L, bool ControlsExit,
// 1*N = -Start; -1*N = Start (mod 2^BW), so:
// N = Distance (as unsigned)
if (StepC->getValue()->equalsInt(1) || StepC->getValue()->isAllOnesValue()) {
- APInt MaxBECount = getUnsignedRange(Distance).getUnsignedMax();
+ APInt MaxBECount = getUnsignedRangeMax(Distance);
// When a loop like "for (int i = 0; i != n; ++i) { /* body */ }" is rotated,
// we end up with a loop whose backedge-taken count is n - 1. Detect this
@@ -7680,7 +7679,7 @@ ScalarEvolution::howFarToZero(const SCEV *V, const Loop *L, bool ControlsExit,
const SCEV *Max =
Exact == getCouldNotCompute()
? Exact
- : getConstant(getUnsignedRange(Exact).getUnsignedMax());
+ : getConstant(getUnsignedRangeMax(Exact));
return ExitLimit(Exact, Max, false, Predicates);
}
@@ -7689,7 +7688,7 @@ ScalarEvolution::howFarToZero(const SCEV *V, const Loop *L, bool ControlsExit,
getNegativeSCEV(Start), *this);
const SCEV *M = E == getCouldNotCompute()
? E
- : getConstant(getUnsignedRange(E).getUnsignedMax());
+ : getConstant(getUnsignedRangeMax(E));
return ExitLimit(E, M, false, Predicates);
}
@@ -7886,12 +7885,12 @@ bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred,
// adding or subtracting 1 from one of the operands.
switch (Pred) {
case ICmpInst::ICMP_SLE:
- if (!getSignedRange(RHS).getSignedMax().isMaxSignedValue()) {
+ if (!getSignedRangeMax(RHS).isMaxSignedValue()) {
RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS,
SCEV::FlagNSW);
Pred = ICmpInst::ICMP_SLT;
Changed = true;
- } else if (!getSignedRange(LHS).getSignedMin().isMinSignedValue()) {
+ } else if (!getSignedRangeMin(LHS).isMinSignedValue()) {
LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS,
SCEV::FlagNSW);
Pred = ICmpInst::ICMP_SLT;
@@ -7899,12 +7898,12 @@ bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred,
}
break;
case ICmpInst::ICMP_SGE:
- if (!getSignedRange(RHS).getSignedMin().isMinSignedValue()) {
+ if (!getSignedRangeMin(RHS).isMinSignedValue()) {
RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS,
SCEV::FlagNSW);
Pred = ICmpInst::ICMP_SGT;
Changed = true;
- } else if (!getSignedRange(LHS).getSignedMax().isMaxSignedValue()) {
+ } else if (!getSignedRangeMax(LHS).isMaxSignedValue()) {
LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS,
SCEV::FlagNSW);
Pred = ICmpInst::ICMP_SGT;
@@ -7912,23 +7911,23 @@ bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred,
}
break;
case ICmpInst::ICMP_ULE:
- if (!getUnsignedRange(RHS).getUnsignedMax().isMaxValue()) {
+ if (!getUnsignedRangeMax(RHS).isMaxValue()) {
RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS,
SCEV::FlagNUW);
Pred = ICmpInst::ICMP_ULT;
Changed = true;
- } else if (!getUnsignedRange(LHS).getUnsignedMin().isMinValue()) {
+ } else if (!getUnsignedRangeMin(LHS).isMinValue()) {
LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS);
Pred = ICmpInst::ICMP_ULT;
Changed = true;
}
break;
case ICmpInst::ICMP_UGE:
- if (!getUnsignedRange(RHS).getUnsignedMin().isMinValue()) {
+ if (!getUnsignedRangeMin(RHS).isMinValue()) {
RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS);
Pred = ICmpInst::ICMP_UGT;
Changed = true;
- } else if (!getUnsignedRange(LHS).getUnsignedMax().isMaxValue()) {
+ } else if (!getUnsignedRangeMax(LHS).isMaxValue()) {
LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS,
SCEV::FlagNUW);
Pred = ICmpInst::ICMP_UGT;
@@ -7962,19 +7961,19 @@ trivially_false:
}
bool ScalarEvolution::isKnownNegative(const SCEV *S) {
- return getSignedRange(S).getSignedMax().isNegative();
+ return getSignedRangeMax(S).isNegative();
}
bool ScalarEvolution::isKnownPositive(const SCEV *S) {
- return getSignedRange(S).getSignedMin().isStrictlyPositive();
+ return getSignedRangeMin(S).isStrictlyPositive();
}
bool ScalarEvolution::isKnownNonNegative(const SCEV *S) {
- return !getSignedRange(S).getSignedMin().isNegative();
+ return !getSignedRangeMin(S).isNegative();
}
bool ScalarEvolution::isKnownNonPositive(const SCEV *S) {
- return !getSignedRange(S).getSignedMax().isStrictlyPositive();
+ return !getSignedRangeMax(S).isStrictlyPositive();
}
bool ScalarEvolution::isKnownNonZero(const SCEV *S) {
@@ -8560,7 +8559,7 @@ bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS,
// predicate we're interested in folding.
APInt Min = ICmpInst::isSigned(Pred) ?
- getSignedRange(V).getSignedMin() : getUnsignedRange(V).getUnsignedMin();
+ getSignedRangeMin(V) : getUnsignedRangeMin(V);
if (Min == C->getAPInt()) {
// Given (V >= Min && V != Min) we conclude V >= (Min + 1).
@@ -9115,19 +9114,17 @@ bool ScalarEvolution::doesIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride,
const SCEV *One = getOne(Stride->getType());
if (IsSigned) {
- APInt MaxRHS = getSignedRange(RHS).getSignedMax();
+ APInt MaxRHS = getSignedRangeMax(RHS);
APInt MaxValue = APInt::getSignedMaxValue(BitWidth);
- APInt MaxStrideMinusOne = getSignedRange(getMinusSCEV(Stride, One))
- .getSignedMax();
+ APInt MaxStrideMinusOne = getSignedRangeMax(getMinusSCEV(Stride, One));
// SMaxRHS + SMaxStrideMinusOne > SMaxValue => overflow!
return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
}
- APInt MaxRHS = getUnsignedRange(RHS).getUnsignedMax();
+ APInt MaxRHS = getUnsignedRangeMax(RHS);
APInt MaxValue = APInt::getMaxValue(BitWidth);
- APInt MaxStrideMinusOne = getUnsignedRange(getMinusSCEV(Stride, One))
- .getUnsignedMax();
+ APInt MaxStrideMinusOne = getUnsignedRangeMax(getMinusSCEV(Stride, One));
// UMaxRHS + UMaxStrideMinusOne > UMaxValue => overflow!
return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
@@ -9141,19 +9138,17 @@ bool ScalarEvolution::doesIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride,
const SCEV *One = getOne(Stride->getType());
if (IsSigned) {
- APInt MinRHS = getSignedRange(RHS).getSignedMin();
+ APInt MinRHS = getSignedRangeMin(RHS);
APInt MinValue = APInt::getSignedMinValue(BitWidth);
- APInt MaxStrideMinusOne = getSignedRange(getMinusSCEV(Stride, One))
- .getSignedMax();
+ APInt MaxStrideMinusOne = getSignedRangeMax(getMinusSCEV(Stride, One));
// SMinRHS - SMaxStrideMinusOne < SMinValue => overflow!
return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
}
- APInt MinRHS = getUnsignedRange(RHS).getUnsignedMin();
+ APInt MinRHS = getUnsignedRangeMin(RHS);
APInt MinValue = APInt::getMinValue(BitWidth);
- APInt MaxStrideMinusOne = getUnsignedRange(getMinusSCEV(Stride, One))
- .getUnsignedMax();
+ APInt MaxStrideMinusOne = getUnsignedRangeMax(getMinusSCEV(Stride, One));
// UMinRHS - UMaxStrideMinusOne < UMinValue => overflow!
return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
@@ -9292,8 +9287,8 @@ ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS,
} else {
// Calculate the maximum backedge count based on the range of values
// permitted by Start, End, and Stride.
- APInt MinStart = IsSigned ? getSignedRange(Start).getSignedMin()
- : getUnsignedRange(Start).getUnsignedMin();
+ APInt MinStart = IsSigned ? getSignedRangeMin(Start)
+ : getUnsignedRangeMin(Start);
unsigned BitWidth = getTypeSizeInBits(LHS->getType());
@@ -9301,8 +9296,8 @@ ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS,
if (PositiveStride)
StrideForMaxBECount =
- IsSigned ? getSignedRange(Stride).getSignedMin()
- : getUnsignedRange(Stride).getUnsignedMin();
+ IsSigned ? getSignedRangeMin(Stride)
+ : getUnsignedRangeMin(Stride);
else
// Using a stride of 1 is safe when computing max backedge taken count for
// a loop with unknown stride.
@@ -9316,8 +9311,8 @@ ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS,
// the case End = RHS. This is safe because in the other case (End - Start)
// is zero, leading to a zero maximum backedge taken count.
APInt MaxEnd =
- IsSigned ? APIntOps::smin(getSignedRange(RHS).getSignedMax(), Limit)
- : APIntOps::umin(getUnsignedRange(RHS).getUnsignedMax(), Limit);
+ IsSigned ? APIntOps::smin(getSignedRangeMax(RHS), Limit)
+ : APIntOps::umin(getUnsignedRangeMax(RHS), Limit);
MaxBECount = computeBECount(getConstant(MaxEnd - MinStart),
getConstant(StrideForMaxBECount), false);
@@ -9325,7 +9320,7 @@ ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS,
if (isa<SCEVCouldNotCompute>(MaxBECount) &&
!isa<SCEVCouldNotCompute>(BECount))
- MaxBECount = getConstant(getUnsignedRange(BECount).getUnsignedMax());
+ MaxBECount = getConstant(getUnsignedRangeMax(BECount));
return ExitLimit(BECount, MaxBECount, MaxOrZero, Predicates);
}
@@ -9376,11 +9371,11 @@ ScalarEvolution::howManyGreaterThans(const SCEV *LHS, const SCEV *RHS,
const SCEV *BECount = computeBECount(getMinusSCEV(Start, End), Stride, false);
- APInt MaxStart = IsSigned ? getSignedRange(Start).getSignedMax()
- : getUnsignedRange(Start).getUnsignedMax();
+ APInt MaxStart = IsSigned ? getSignedRangeMax(Start)
+ : getUnsignedRangeMax(Start);
- APInt MinStride = IsSigned ? getSignedRange(Stride).getSignedMin()
- : getUnsignedRange(Stride).getUnsignedMin();
+ APInt MinStride = IsSigned ? getSignedRangeMin(Stride)
+ : getUnsignedRangeMin(Stride);
unsigned BitWidth = getTypeSizeInBits(LHS->getType());
APInt Limit = IsSigned ? APInt::getSignedMinValue(BitWidth) + (MinStride - 1)
@@ -9390,8 +9385,8 @@ ScalarEvolution::howManyGreaterThans(const SCEV *LHS, const SCEV *RHS,
// the case End = RHS. This is safe because in the other case (Start - End)
// is zero, leading to a zero maximum backedge taken count.
APInt MinEnd =
- IsSigned ? APIntOps::smax(getSignedRange(RHS).getSignedMin(), Limit)
- : APIntOps::umax(getUnsignedRange(RHS).getUnsignedMin(), Limit);
+ IsSigned ? APIntOps::smax(getSignedRangeMin(RHS), Limit)
+ : APIntOps::umax(getUnsignedRangeMin(RHS), Limit);
const SCEV *MaxBECount = getCouldNotCompute();
diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp
index f9b9df2bc707d..47bdac00ae1f3 100644
--- a/lib/Analysis/ScalarEvolutionExpander.cpp
+++ b/lib/Analysis/ScalarEvolutionExpander.cpp
@@ -748,18 +748,56 @@ Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) {
// Emit instructions to mul all the operands. Hoist as much as possible
// out of loops.
Value *Prod = nullptr;
- for (const auto &I : OpsAndLoops) {
- const SCEV *Op = I.second;
+ auto I = OpsAndLoops.begin();
+
+ // Expand the calculation of X pow N in the following manner:
+ // Let N = P1 + P2 + ... + PK, where all P are powers of 2. Then:
+ // X pow N = (X pow P1) * (X pow P2) * ... * (X pow PK).
+ const auto ExpandOpBinPowN = [this, &I, &OpsAndLoops, &Ty]() {
+ auto E = I;
+ // Calculate how many times the same operand from the same loop is included
+ // into this power.
+ uint64_t Exponent = 0;
+ const uint64_t MaxExponent = UINT64_MAX >> 1;
+ // No one sane will ever try to calculate such huge exponents, but if we
+ // need this, we stop on UINT64_MAX / 2 because we need to exit the loop
+ // below when the power of 2 exceeds our Exponent, and we want it to be
+ // 1u << 31 at most to not deal with unsigned overflow.
+ while (E != OpsAndLoops.end() && *I == *E && Exponent != MaxExponent) {
+ ++Exponent;
+ ++E;
+ }
+ assert(Exponent > 0 && "Trying to calculate a zeroth exponent of operand?");
+
+ // Calculate powers with exponents 1, 2, 4, 8 etc. and include those of them
+ // that are needed into the result.
+ Value *P = expandCodeFor(I->second, Ty);
+ Value *Result = nullptr;
+ if (Exponent & 1)
+ Result = P;
+ for (uint64_t BinExp = 2; BinExp <= Exponent; BinExp <<= 1) {
+ P = InsertBinop(Instruction::Mul, P, P);
+ if (Exponent & BinExp)
+ Result = Result ? InsertBinop(Instruction::Mul, Result, P) : P;
+ }
+
+ I = E;
+ assert(Result && "Nothing was expanded?");
+ return Result;
+ };
+
+ while (I != OpsAndLoops.end()) {
if (!Prod) {
// This is the first operand. Just expand it.
- Prod = expand(Op);
- } else if (Op->isAllOnesValue()) {
+ Prod = ExpandOpBinPowN();
+ } else if (I->second->isAllOnesValue()) {
// Instead of doing a multiply by negative one, just do a negate.
Prod = InsertNoopCastOfTo(Prod, Ty);
Prod = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), Prod);
+ ++I;
} else {
// A simple mul.
- Value *W = expandCodeFor(Op, Ty);
+ Value *W = ExpandOpBinPowN();
Prod = InsertNoopCastOfTo(Prod, Ty);
// Canonicalize a constant to the RHS.
if (isa<Constant>(Prod)) std::swap(Prod, W);
diff --git a/lib/Analysis/TypeBasedAliasAnalysis.cpp b/lib/Analysis/TypeBasedAliasAnalysis.cpp
index e920c4c4e6b2b..cd9972ab56a68 100644
--- a/lib/Analysis/TypeBasedAliasAnalysis.cpp
+++ b/lib/Analysis/TypeBasedAliasAnalysis.cpp
@@ -58,7 +58,7 @@
//
// The struct type node has a name and a list of pairs, one pair for each member
// of the struct. The first element of each pair is a type node (a struct type
-// node or a sclar type node), specifying the type of the member, the second
+// node or a scalar type node), specifying the type of the member, the second
// element of each pair is the offset of the member.
//
// Given an example
diff --git a/lib/Analysis/ValueTracking.cpp b/lib/Analysis/ValueTracking.cpp
index b065f427b06cb..fd6e3a643bf03 100644
--- a/lib/Analysis/ValueTracking.cpp
+++ b/lib/Analysis/ValueTracking.cpp
@@ -686,8 +686,7 @@ static void computeKnownBitsFromAssume(const Value *V, KnownBits &Known,
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)),
- m_AShr(m_V, m_ConstantInt(C))),
+ m_c_ICmp(Pred, m_Shr(m_V, m_ConstantInt(C)),
m_Value(A))) &&
Pred == ICmpInst::ICMP_EQ &&
isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
@@ -698,9 +697,7 @@ static void computeKnownBitsFromAssume(const Value *V, KnownBits &Known,
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)),
- m_AShr(m_V, m_ConstantInt(C)))),
+ } else if (match(Arg, m_c_ICmp(Pred, m_Not(m_Shr(m_V, m_ConstantInt(C))),
m_Value(A))) &&
Pred == ICmpInst::ICMP_EQ &&
isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
generated by cgit v1.2.3 (git 2.25.1) at 2025-06-30 01:23:09 +0000