83#include "llvm/Config/llvm-config.h"
138#define DEBUG_TYPE "scalar-evolution"
141 "Number of loop exits with predictable exit counts");
143 "Number of loop exits without predictable exit counts");
145 "Number of loops with trip counts computed by force");
147#ifdef EXPENSIVE_CHECKS
155 cl::desc(
"Maximum number of iterations SCEV will "
156 "symbolically execute a constant "
162 cl::desc(
"Verify ScalarEvolution's backedge taken counts (slow)"));
165 cl::desc(
"Enable stricter verification with -verify-scev is passed"));
169 cl::desc(
"Verify IR correctness when making sensitive SCEV queries (slow)"),
174 cl::desc(
"Threshold for inlining multiplication operands into a SCEV"),
179 cl::desc(
"Threshold for inlining addition operands into a SCEV"),
183 "scalar-evolution-max-scev-compare-depth",
cl::Hidden,
184 cl::desc(
"Maximum depth of recursive SCEV complexity comparisons"),
188 "scalar-evolution-max-scev-operations-implication-depth",
cl::Hidden,
189 cl::desc(
"Maximum depth of recursive SCEV operations implication analysis"),
193 "scalar-evolution-max-value-compare-depth",
cl::Hidden,
194 cl::desc(
"Maximum depth of recursive value complexity comparisons"),
199 cl::desc(
"Maximum depth of recursive arithmetics"),
203 "scalar-evolution-max-constant-evolving-depth",
cl::Hidden,
208 cl::desc(
"Maximum depth of recursive SExt/ZExt/Trunc"),
213 cl::desc(
"Max coefficients in AddRec during evolving"),
218 cl::desc(
"Size of the expression which is considered huge"),
223 cl::desc(
"Threshold for switching to iteratively computing SCEV ranges"),
227 "scalar-evolution-max-loop-guard-collection-depth",
cl::Hidden,
228 cl::desc(
"Maximum depth for recursive loop guard collection"),
cl::init(1));
233 cl::desc(
"When printing analysis, include information on every instruction"));
236 "scalar-evolution-use-expensive-range-sharpening",
cl::Hidden,
238 cl::desc(
"Use more powerful methods of sharpening expression ranges. May "
239 "be costly in terms of compile time"));
243 cl::desc(
"Handle <= and >= in finite loops"),
247 "scalar-evolution-use-context-for-no-wrap-flag-strenghening",
cl::Hidden,
248 cl::desc(
"Infer nuw/nsw flags using context where suitable"),
290#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
308 OS <<
"(ptrtoaddr " << *
Op->getType() <<
" " <<
Op <<
" to "
315 OS <<
"(trunc " << *
Op->getType() <<
" " <<
Op <<
" to "
322 OS <<
"(zext " << *
Op->getType() <<
" " <<
Op <<
" to " << *ZExt->
getType()
329 OS <<
"(sext " << *
Op->getType() <<
" " <<
Op <<
" to " << *SExt->
getType()
358 const char *OpStr =
nullptr;
371 OpStr =
" umin_seq ";
393 OS <<
"(" << UDiv->
getLHS() <<
" /u " << UDiv->
getRHS() <<
")";
400 OS <<
"***COULDNOTCOMPUTE***";
442 if (!
Mul)
return false;
446 if (!SC)
return false;
460 auto &Entry = ConstantSCEVs[V];
469 static_cast<SCEVConstant *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP)))
472 new (SCEVAllocator)
SCEVConstant(ID.Intern(SCEVAllocator), V);
473 UniqueSCEVs.InsertNode(S, IP);
488 ConstantInt::get(ITy, V,
isSigned,
true));
496 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
498 SCEV *S =
new (SCEVAllocator)
SCEVVScale(ID.Intern(SCEVAllocator), Ty);
499 UniqueSCEVs.InsertNode(S, IP);
520 "Must be a non-bit-width-changing pointer-to-integer cast!");
532 "Cannot truncate non-integer value!");
539 "Cannot zero extend non-integer value!");
546 "Cannot sign extend non-integer value!");
551 SE->forgetMemoizedResults({
this});
554 SE->UniqueSCEVs.RemoveNode(
this);
560void SCEVUnknown::allUsesReplacedWith(
Value *New) {
562 SE->forgetMemoizedResults({
this});
565 SE->UniqueSCEVs.RemoveNode(
this);
587 if (LIsPointer != RIsPointer)
588 return (
int)LIsPointer - (int)RIsPointer;
593 return (
int)LID - (int)RID;
598 unsigned LArgNo = LA->getArgNo(), RArgNo =
RA->getArgNo();
599 return (
int)LArgNo - (int)RArgNo;
605 if (
auto L = LGV->getLinkage() - RGV->getLinkage())
608 const auto IsGVNameSemantic = [&](
const GlobalValue *GV) {
609 auto LT = GV->getLinkage();
616 if (IsGVNameSemantic(LGV) && IsGVNameSemantic(RGV))
617 return LGV->getName().compare(RGV->getName());
628 if (LParent != RParent) {
631 if (LDepth != RDepth)
632 return (
int)LDepth - (int)RDepth;
636 unsigned LNumOps = LInst->getNumOperands(),
637 RNumOps = RInst->getNumOperands();
638 if (LNumOps != RNumOps)
639 return (
int)LNumOps - (int)RNumOps;
641 for (
unsigned Idx :
seq(LNumOps)) {
643 RInst->getOperand(Idx),
Depth + 1);
657static std::optional<int>
667 return (
int)LType - (int)RType;
692 unsigned LBitWidth = LA.
getBitWidth(), RBitWidth =
RA.getBitWidth();
693 if (LBitWidth != RBitWidth)
694 return (
int)LBitWidth - (int)RBitWidth;
695 return LA.
ult(
RA) ? -1 : 1;
701 return LTy->getBitWidth() - RTy->getBitWidth();
712 if (LLoop != RLoop) {
714 assert(LHead != RHead &&
"Two loops share the same header?");
718 "No dominance between recurrences used by one SCEV?");
741 unsigned LNumOps = LOps.
size(), RNumOps = ROps.
size();
742 if (LNumOps != RNumOps)
743 return (
int)LNumOps - (int)RNumOps;
745 for (
unsigned i = 0; i != LNumOps; ++i) {
771 if (
Ops.size() < 2)
return;
776 return Complexity && *Complexity < 0;
778 if (
Ops.size() == 2) {
782 if (IsLessComplex(
RHS,
LHS))
795 for (
unsigned i = 0, e =
Ops.size(); i != e-2; ++i) {
801 for (
unsigned j = i+1; j != e &&
Ops[j]->getSCEVType() == Complexity; ++j) {
806 if (i == e-2)
return;
828template <
typename FoldT,
typename IsIdentityT,
typename IsAbsorberT>
832 IsIdentityT IsIdentity, IsAbsorberT IsAbsorber) {
834 for (
unsigned Idx = 0; Idx <
Ops.size();) {
842 Ops.erase(
Ops.begin() + Idx);
849 assert(Folded &&
"Must have folded value");
853 if (Folded && IsAbsorber(Folded->
getAPInt()))
857 if (Folded && !IsIdentity(Folded->
getAPInt()))
858 Ops.insert(
Ops.begin(), Folded);
860 return Ops.size() == 1 ?
Ops[0] :
nullptr;
935 APInt OddFactorial(W, 1);
937 for (
unsigned i = 3; i <= K; ++i) {
940 OddFactorial *= (i >> TwoFactors);
944 unsigned CalculationBits = W +
T;
958 for (
unsigned i = 1; i != K; ++i) {
991 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
1020 ConversionFn CreatePtrCast;
1024 ConversionFn CreatePtrCast)
1025 : Base(
SE), TargetTy(TargetTy), CreatePtrCast(
std::
move(CreatePtrCast)) {}
1028 Type *TargetTy, ConversionFn CreatePtrCast) {
1030 return Rewriter.visit(Scev);
1056 "Should only reach pointer-typed SCEVUnknown's.");
1061 return SE.getZero(TargetTy);
1062 return CreatePtrCast(Expr);
1067 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
1071 if (DL.hasUnstableRepresentation(
Op->getType()))
1074 Type *Ty = DL.getAddressType(
Op->getType());
1085 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
1087 SCEV *S =
new (SCEVAllocator)
1089 UniqueSCEVs.InsertNode(S, IP);
1092 return static_cast<const SCEV *
>(S);
1095 "We must have succeeded in sinking the cast, "
1096 "and ending up with an integer-typed expression!");
1103 "This is not a truncating conversion!");
1105 "This is not a conversion to a SCEVable type!");
1106 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1111 ID.AddPointer(
Op.getOpaqueValue());
1114 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
1136 UniqueSCEVs.InsertNode(S, IP);
1149 unsigned numTruncs = 0;
1150 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1158 if (numTruncs < 2) {
1168 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
1175 for (
const SCEV *
Op : AddRec->operands())
1190 UniqueSCEVs.InsertNode(S, IP);
1231struct ExtendOpTraitsBase {
1232 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(
SCEVUse,
Type *,
1237template <
typename ExtendOp>
struct ExtendOpTraits {
1253 static const GetExtendExprTy GetExtendExpr;
1255 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1256 ICmpInst::Predicate *Pred,
1257 ScalarEvolution *SE) {
1262const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1269 static const GetExtendExprTy GetExtendExpr;
1271 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1272 ICmpInst::Predicate *Pred,
1273 ScalarEvolution *SE) {
1278const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1290template <
typename ExtendOpTy>
1293 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1294 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1310 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1323 auto PreStartFlags =
1341 const SCEV *OperandExtendedStart =
1343 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1344 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1356 const SCEV *OverflowLimit =
1357 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1359 if (OverflowLimit &&
1367template <
typename ExtendOpTy>
1371 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1379 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1414template <
typename ExtendOpTy>
1415bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1418 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1428 APInt StartAI = StartC->
getAPInt();
1430 for (
unsigned Delta : {-2, -1, 1, 2}) {
1431 const SCEV *PreStart =
getConstant(StartAI - Delta);
1433 FoldingSetNodeID
ID;
1435 ID.AddPointer(PreStart);
1436 ID.AddPointer(Step);
1440 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
1444 if (PreAR &&
any(PreAR->getNoWrapFlags(WrapType))) {
1447 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1448 DeltaS, &Pred,
this);
1466 const unsigned BitWidth =
C.getBitWidth();
1484 const APInt &ConstantStart,
1499 auto I = FoldCache.
insert({ID, S});
1503 auto &UserIDs = FoldCacheUser[
I.first->second];
1504 assert(
count(UserIDs, ID) == 1 &&
"unexpected duplicates in UserIDs");
1505 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1506 if (UserIDs[
I] == ID) {
1511 I.first->second = S;
1513 FoldCacheUser[S].push_back(ID);
1519 "This is not an extending conversion!");
1521 "This is not a conversion to a SCEVable type!");
1522 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1526 if (
const SCEV *S = FoldCache.lookup(ID))
1538 "This is not an extending conversion!");
1540 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1552 const SCEV *Start, *Step;
1557 if (AR->hasNoUnsignedWrap()) {
1568 ID.AddPointer(
Op.getOpaqueValue());
1571 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
1575 UniqueSCEVs.InsertNode(S, IP);
1585 const SCEV *
X = ST->getOperand();
1618 const SCEV *CastedMaxBECount =
1622 if (MaxBECount == RecastedMaxBECount) {
1631 const SCEV *WideMaxBECount =
1633 const SCEV *OperandExtendedAdd =
1639 if (ZAdd == OperandExtendedAdd) {
1650 OperandExtendedAdd =
1656 if (ZAdd == OperandExtendedAdd) {
1677 !AC.assumptions().empty()) {
1679 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1681 if (AR->hasNoUnsignedWrap()) {
1716 const APInt &
C = SC->getAPInt();
1720 const SCEV *SResidual =
1728 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1752 if (SA->hasNoUnsignedWrap()) {
1765 if (SA->hasNoSignedWrap() &&
1768 C->isNegative() && !
C->isMinSignedValue() && C2->
sge(
C->abs())) {
1787 const SCEV *SResidual =
1798 if (SM->hasNoUnsignedWrap()) {
1820 const SCEV *TruncRHS;
1857 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
1860 UniqueSCEVs.InsertNode(S, IP);
1869 "This is not an extending conversion!");
1871 "This is not a conversion to a SCEVable type!");
1872 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1876 if (
const SCEV *S = FoldCache.lookup(ID))
1888 "This is not an extending conversion!");
1890 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1907 const SCEV *Start, *Step;
1912 if (AR->hasNoSignedWrap()) {
1923 ID.AddPointer(
Op.getOpaqueValue());
1926 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
1931 UniqueSCEVs.InsertNode(S, IP);
1941 const SCEV *
X = ST->getOperand();
1952 if (SA->hasNoSignedWrap()) {
1974 const SCEV *SResidual =
2007 const SCEV *CastedMaxBECount =
2011 if (MaxBECount == RecastedMaxBECount) {
2020 const SCEV *WideMaxBECount =
2022 const SCEV *OperandExtendedAdd =
2028 if (SAdd == OperandExtendedAdd) {
2039 OperandExtendedAdd =
2045 if (SAdd == OperandExtendedAdd) {
2065 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2067 if (AR->hasNoSignedWrap()) {
2081 const APInt &
C = SC->getAPInt();
2085 const SCEV *SResidual =
2093 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2120 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
2123 UniqueSCEVs.InsertNode(S, IP);
2139 assert(Expr->
getType() == Ty &&
"requested type must match");
2151 "This is not an extending conversion!");
2153 "This is not a conversion to a SCEVable type!");
2158 if (SC->getAPInt().isNegative())
2163 const SCEV *NewOp =
T->getOperand();
2182 for (
const SCEV *
Op : AR->operands())
2220 APInt &AccumulatedConstant,
2224 bool Interesting =
false;
2231 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2233 AccumulatedConstant += Scale *
C->getAPInt();
2238 for (; i !=
Ops.size(); ++i) {
2247 M, NewOps, AccumulatedConstant,
Add->operands(), NewScale, SE);
2253 auto Pair = M.insert({
Key, NewScale});
2257 Pair.first->second += NewScale;
2265 auto Pair = M.insert({
Ops[i], Scale});
2269 Pair.first->second += Scale;
2288 case Instruction::Add:
2291 case Instruction::Sub:
2294 case Instruction::Mul:
2308 const SCEV *
A = (this->*Extension)(
2310 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2311 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2319 if (BinOp == Instruction::Mul)
2325 APInt C = RHSC->getAPInt();
2326 unsigned NumBits =
C.getBitWidth();
2327 bool IsSub = (BinOp == Instruction::Sub);
2328 bool IsNegativeConst = (
Signed &&
C.isNegative());
2330 bool OverflowDown = IsSub ^ IsNegativeConst;
2332 if (IsNegativeConst) {
2345 APInt Limit = Min + Magnitude;
2351 APInt Limit = Max - Magnitude;
2356std::optional<SCEV::NoWrapFlags>
2361 return std::nullopt;
2370 bool Deduced =
false;
2376 bool CanUseNSW =
true;
2377 const APInt *ShiftAmt;
2382 return std::nullopt;
2386 Opcode = Instruction::Mul;
2388 }
else if (Opcode != Instruction::Add && Opcode != Instruction::Sub &&
2389 Opcode != Instruction::Mul) {
2390 return std::nullopt;
2409 return std::nullopt;
2419 using namespace std::placeholders;
2426 assert(CanAnalyze &&
"don't call from other places!");
2433 auto IsKnownNonNegative = [&](
SCEVUse U) {
2442 if (SignOrUnsignWrap != SignOrUnsignMask &&
2449 return Instruction::Add;
2451 return Instruction::Mul;
2462 Opcode,
C, OBO::NoSignedWrap);
2470 Opcode,
C, OBO::NoUnsignedWrap);
2480 Ops[0]->isZero() && IsKnownNonNegative(
Ops[1]))
2487 if (UDiv->getOperand(1) ==
Ops[1])
2490 if (UDiv->getOperand(1) ==
Ops[0])
2506 "only nuw or nsw allowed");
2507 assert(!
Ops.empty() &&
"Cannot get empty add!");
2508 if (
Ops.size() == 1)
return Ops[0];
2511 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
2513 "SCEVAddExpr operand types don't match!");
2515 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2516 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2521 [](
const APInt &C1,
const APInt &C2) {
return C1 + C2; },
2522 [](
const APInt &
C) {
return C.isZero(); },
2523 [](
const APInt &
C) {
return false; });
2536 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
2541 if (
Add->getNoWrapFlags(OrigFlags) != OrigFlags)
2542 Add->setNoWrapFlags(ComputeFlags(
Ops));
2550 bool FoundMatch =
false;
2551 for (
unsigned i = 0, e =
Ops.size(); i != e-1; ++i)
2552 if (
Ops[i] ==
Ops[i+1]) {
2564 --i; e -=
Count - 1;
2574 auto FindTruncSrcType = [&]() ->
Type * {
2580 return T->getOperand()->getType();
2582 SCEVUse LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2584 return T->getOperand()->getType();
2588 if (
auto *SrcType = FindTruncSrcType()) {
2595 if (
T->getOperand()->getType() != SrcType) {
2604 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2607 if (
T->getOperand()->getType() != SrcType) {
2635 if (
Ops.size() == 2) {
2645 auto C2 =
C->getAPInt();
2648 APInt ConstAdd = C1 + C2;
2649 auto AddFlags = AddExpr->getNoWrapFlags();
2690 if (
Ops.size() == 2 &&
2701 if (Idx <
Ops.size()) {
2702 bool DeletedAdd =
false;
2713 Ops.erase(
Ops.begin()+Idx);
2716 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2739 struct APIntCompare {
2740 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2741 return LHS.ult(RHS);
2748 std::map<APInt, SmallVector<SCEVUse, 4>, APIntCompare> MulOpLists;
2749 for (
const SCEV *NewOp : NewOps)
2750 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2753 if (AccumulatedConstant != 0)
2755 for (
auto &MulOp : MulOpLists) {
2756 if (MulOp.first == 1) {
2758 }
else if (MulOp.first != 0) {
2767 if (
Ops.size() == 1)
2776 if (M->getNumOperands() == 2)
2777 return M->getOperand(OpIdx == 0);
2779 append_range(Remaining, M->operands().drop_front(OpIdx + 1));
2788 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2792 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2800 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp) {
2801 if (MulOpSCEV ==
Ops[AddOp]) {
2812 for (
unsigned OMulOp = 0, OE = OtherMul->
getNumOperands(); OMulOp != OE;
2814 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2816 Cofactors.
push_back(StripFactor(OtherMul, OMulOp));
2825 if (!Cofactors.
empty()) {
2833 if (
Ops.size() == DeadIndices.
size() + 1)
2840 Ops.erase(
Ops.begin() + Idx);
2844 Ops.push_back(OuterMul);
2863 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
2866 Ops.erase(
Ops.begin()+i);
2871 if (!LIOps.
empty()) {
2896 auto *DefI = getDefiningScopeBound(LIOps);
2898 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
2910 if (
Ops.size() == 1)
return NewRec;
2913 for (
unsigned i = 0;; ++i)
2914 if (
Ops[i] == AddRec) {
2924 for (
unsigned OtherIdx = Idx+1;
2932 "AddRecExprs are not sorted in reverse dominance order?");
2939 if (OtherAddRec->getLoop() == AddRecLoop) {
2940 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
2942 if (i >= AddRecOps.
size()) {
2943 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
2947 getAddExpr(AddRecOps[i], OtherAddRec->getOperand(i),
2950 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
2965 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
2973 ID.AddPointer(
Op.getOpaqueValue());
2976 static_cast<SCEVAddExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
2980 S =
new (SCEVAllocator)
2982 UniqueSCEVs.InsertNode(S, IP);
2993 FoldingSetNodeID
ID;
2996 ID.AddPointer(
Op.getOpaqueValue());
3000 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
3004 S =
new (SCEVAllocator)
3005 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
3006 UniqueSCEVs.InsertNode(S, IP);
3008 LoopUsers[
L].push_back(S);
3017 FoldingSetNodeID
ID;
3020 ID.AddPointer(
Op.getOpaqueValue());
3023 static_cast<SCEVMulExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
3027 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3029 UniqueSCEVs.InsertNode(S, IP);
3038 FoldingSetNodeID
ID;
3040 ID.AddPointer(
LHS.getOpaqueValue());
3041 ID.AddPointer(
RHS.getOpaqueValue());
3043 SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
3045 S =
new (SCEVAllocator) SCEVUDivExpr(
ID.Intern(SCEVAllocator),
LHS,
RHS);
3046 UniqueSCEVs.InsertNode(S, IP);
3055 if (j > 1 && k / j != i) Overflow =
true;
3071 if (n == 0 || n == k)
return 1;
3072 if (k > n)
return 0;
3078 for (
uint64_t i = 1; i <= k; ++i) {
3079 r =
umul_ov(r, n-(i-1), Overflow);
3088 struct FindConstantInAddMulChain {
3089 bool FoundConstant =
false;
3091 bool follow(
const SCEV *S) {
3096 bool isDone()
const {
3097 return FoundConstant;
3101 FindConstantInAddMulChain
F;
3103 ST.visitAll(StartExpr);
3104 return F.FoundConstant;
3112 "only nuw or nsw allowed");
3113 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3114 if (
Ops.size() == 1)
return Ops[0];
3116 Type *ETy =
Ops[0]->getType();
3118 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3120 "SCEVMulExpr operand types don't match!");
3125 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3126 [](
const APInt &
C) {
return C.isOne(); },
3127 [](
const APInt &
C) {
return C.isZero(); });
3138 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3143 if (
Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3144 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3149 if (
Ops.size() == 2) {
3157 const SCEV *Op0, *Op1;
3165 if (
Ops[0]->isAllOnesValue()) {
3170 bool AnyFolded =
false;
3171 for (
const SCEV *AddOp :
Add->operands()) {
3191 if (AddRec->hasNoSignedWrap()) {
3198 AddRec->getNoWrapFlags(FlagsMask));
3221 APInt C1V = LHSC->getAPInt();
3231 const SCEV *NewMul =
nullptr;
3235 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3250 if (Idx <
Ops.size()) {
3251 bool DeletedMul =
false;
3257 Ops.erase(
Ops.begin()+Idx);
3281 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3284 Ops.erase(
Ops.begin()+i);
3289 if (!LIOps.
empty()) {
3302 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3318 if (
Ops.size() == 1)
return NewRec;
3321 for (
unsigned i = 0;; ++i)
3322 if (
Ops[i] == AddRec) {
3343 bool OpsModified =
false;
3344 for (
unsigned OtherIdx = Idx+1;
3358 bool Overflow =
false;
3365 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3366 uint64_t Coeff1 =
Choose(x, 2*x - y, Overflow);
3369 z < ze && !Overflow; ++z) {
3370 uint64_t Coeff2 =
Choose(2*x - y, x-z, Overflow);
3372 if (LargerThan64Bits)
3373 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3375 Coeff = Coeff1*Coeff2;
3390 if (
Ops.size() == 2)
return NewAddRec;
3391 Ops[Idx] = NewAddRec;
3392 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3408 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3415 "SCEVURemExpr operand types don't match!");
3420 if (RHSC->getValue()->isOne())
3421 return getZero(LHS->getType());
3424 if (RHSC->getAPInt().isPowerOf2()) {
3425 Type *FullTy = LHS->getType();
3441 assert(!LHS->getType()->isPointerTy() &&
3442 "SCEVUDivExpr operand can't be pointer!");
3443 assert(LHS->getType() == RHS->getType() &&
3444 "SCEVUDivExpr operand types don't match!");
3455 if (RHSC->getValue()->isOne())
3460 if (!RHSC->getValue()->isZero()) {
3464 Type *Ty = LHS->getType();
3465 unsigned LZ = RHSC->getAPInt().countl_zero();
3469 if (!RHSC->getAPInt().isPowerOf2())
3477 const APInt &StepInt = Step->getAPInt();
3478 const APInt &DivInt = RHSC->getAPInt();
3479 if (!StepInt.
urem(DivInt) &&
3485 for (
const SCEV *
Op : AR->operands())
3491 const APInt *StartRem;
3504 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3508 const SCEV *NewStart =
3510 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3512 const SCEV *NewLHS =
3522 if (M->hasNoUnsignedWrap()) {
3524 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3525 const SCEV *
Op = M->getOperand(i);
3552 if (
auto *DivisorConstant =
3554 bool Overflow =
false;
3556 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3567 if (
A->hasNoUnsignedWrap()) {
3569 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3576 if (
Operands.size() ==
A->getNumOperands())
3588 const APInt &
N = RHSC->getAPInt();
3589 const APInt *NMinusM, *M;
3593 if (
N.isPowerOf2() && M->isPowerOf2() && M->ult(
N) &&
3594 *NMinusM ==
N - *M) {
3603 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3613 return getZero(LHS->getType());
3617 if (
Mul &&
Mul->hasNoUnsignedWrap()) {
3618 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3619 if (
Mul->getOperand(i) == RHS) {
3630 const SCEV *NewLHS, *NewRHS;
3635 return getOrCreateUDivExpr(LHS, RHS);
3655 if (StepChrec->getLoop() == L) {
3674 "SCEVAddRecExpr operand types don't match!");
3675 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3679 "SCEVAddRecExpr operand is not available at loop entry!");
3697 const Loop *NestedLoop = NestedAR->getLoop();
3698 if (L->contains(NestedLoop)
3701 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3703 Operands[0] = NestedAR->getStart();
3707 bool AllInvariant =
all_of(
3719 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3730 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3740 return getOrCreateAddRecExpr(
Operands, L, Flags);
3756 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3760 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3774 bool FirstIter =
true;
3776 for (
SCEVUse IndexExpr : IndexExprs) {
3783 Offsets.push_back(FieldOffset);
3786 CurTy = STy->getTypeAtIndex(Index);
3791 "The first index of a GEP indexes a pointer");
3792 CurTy = SrcElementTy;
3803 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3804 Offsets.push_back(LocalOffset);
3809 if (Offsets.empty())
3822 "GEP should not change type mid-flight.");
3826SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3831 ID.AddPointer(
Op.getOpaqueValue());
3833 return UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
3843 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3844 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3845 if (
Ops.size() == 1)
return Ops[0];
3848 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
3850 "Operand types don't match!");
3853 "min/max should be consistently pointerish");
3879 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3881 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3886 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3888 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3894 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
3900 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
3905 if (Idx <
Ops.size()) {
3906 bool DeletedAny =
false;
3907 while (
Ops[Idx]->getSCEVType() == Kind) {
3909 Ops.erase(
Ops.begin()+Idx);
3927 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
3928 if (
Ops[i] ==
Ops[i + 1] ||
3929 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
3932 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
3935 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
3938 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
3944 if (
Ops.size() == 1)
return Ops[0];
3946 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
3953 ID.AddPointer(
Op.getOpaqueValue());
3955 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
3957 return ExistingSCEV;
3960 SCEV *S =
new (SCEVAllocator)
3963 UniqueSCEVs.InsertNode(S, IP);
3971class SCEVSequentialMinMaxDeduplicatingVisitor final
3972 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
3973 std::optional<const SCEV *>> {
3974 using RetVal = std::optional<const SCEV *>;
3982 bool canRecurseInto(
SCEVTypes Kind)
const {
3985 return RootKind == Kind || NonSequentialRootKind == Kind;
3988 RetVal visitAnyMinMaxExpr(
const SCEV *S) {
3990 "Only for min/max expressions.");
3993 if (!canRecurseInto(Kind))
4003 return std::nullopt;
4010 RetVal
visit(
const SCEV *S) {
4012 if (!SeenOps.
insert(S).second)
4013 return std::nullopt;
4014 return Base::visit(S);
4018 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4020 : SE(SE), RootKind(RootKind),
4021 NonSequentialRootKind(
4022 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4026 SmallVectorImpl<SCEVUse> &NewOps) {
4031 for (
const SCEV *
Op : OrigOps) {
4036 Ops.emplace_back(*NewOp);
4040 NewOps = std::move(
Ops);
4044 RetVal visitConstant(
const SCEVConstant *Constant) {
return Constant; }
4046 RetVal visitVScale(
const SCEVVScale *VScale) {
return VScale; }
4048 RetVal visitPtrToAddrExpr(
const SCEVPtrToAddrExpr *Expr) {
return Expr; }
4050 RetVal visitTruncateExpr(
const SCEVTruncateExpr *Expr) {
return Expr; }
4052 RetVal visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
return Expr; }
4054 RetVal visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
return Expr; }
4056 RetVal visitAddExpr(
const SCEVAddExpr *Expr) {
return Expr; }
4058 RetVal visitMulExpr(
const SCEVMulExpr *Expr) {
return Expr; }
4060 RetVal visitUDivExpr(
const SCEVUDivExpr *Expr) {
return Expr; }
4062 RetVal visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
return Expr; }
4064 RetVal visitSMaxExpr(
const SCEVSMaxExpr *Expr) {
4065 return visitAnyMinMaxExpr(Expr);
4068 RetVal visitUMaxExpr(
const SCEVUMaxExpr *Expr) {
4069 return visitAnyMinMaxExpr(Expr);
4072 RetVal visitSMinExpr(
const SCEVSMinExpr *Expr) {
4073 return visitAnyMinMaxExpr(Expr);
4076 RetVal visitUMinExpr(
const SCEVUMinExpr *Expr) {
4077 return visitAnyMinMaxExpr(Expr);
4080 RetVal visitSequentialUMinExpr(
const SCEVSequentialUMinExpr *Expr) {
4081 return visitAnyMinMaxExpr(Expr);
4084 RetVal visitUnknown(
const SCEVUnknown *Expr) {
return Expr; }
4086 RetVal visitCouldNotCompute(
const SCEVCouldNotCompute *Expr) {
return Expr; }
4128struct SCEVPoisonCollector {
4129 bool LookThroughMaybePoisonBlocking;
4130 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4131 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4132 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4134 bool follow(
const SCEV *S) {
4135 if (!LookThroughMaybePoisonBlocking &&
4145 bool isDone()
const {
return false; }
4155 SCEVPoisonCollector PC1(
true);
4160 if (PC1.MaybePoison.
empty())
4166 SCEVPoisonCollector PC2(
false);
4176 SCEVPoisonCollector PC(
false);
4199 while (!Worklist.
empty()) {
4201 if (!Visited.
insert(V).second)
4205 if (Visited.
size() > 16)
4221 if (PDI->isDisjoint())
4228 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4235 if (
I->hasPoisonGeneratingAnnotations())
4246 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4247 "Not a SCEVSequentialMinMaxExpr!");
4248 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4249 if (
Ops.size() == 1)
4253 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4255 "Operand types don't match!");
4258 "min/max should be consistently pointerish");
4266 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4273 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4283 bool DeletedAny =
false;
4284 while (Idx <
Ops.size()) {
4285 if (
Ops[Idx]->getSCEVType() != Kind) {
4290 Ops.erase(
Ops.begin() + Idx);
4291 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4292 SMME->operands().end());
4300 const SCEV *SaturationPoint;
4311 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4312 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4324 Ops.erase(
Ops.begin() + i);
4329 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4330 Ops.erase(
Ops.begin() + i);
4340 ID.AddPointer(
Op.getOpaqueValue());
4342 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
4344 return ExistingSCEV;
4348 SCEV *S =
new (SCEVAllocator)
4351 UniqueSCEVs.InsertNode(S, IP);
4399 if (
Size.isScalable())
4420 "Cannot get offset for structure containing scalable vector types");
4434 if (
SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) {
4436 "Stale SCEVUnknown in uniquing map!");
4439 SCEV *S =
new (SCEVAllocator)
SCEVUnknown(ID.Intern(SCEVAllocator), V,
this,
4442 UniqueSCEVs.InsertNode(S, IP);
4457 return Ty->isIntOrPtrTy();
4464 if (Ty->isPointerTy())
4475 if (Ty->isIntegerTy())
4479 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4491 bool PreciseA, PreciseB;
4492 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4493 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4494 if (!PreciseA || !PreciseB)
4497 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4498 DT.dominates(ScopeB, ScopeA);
4502 return CouldNotCompute.get();
4505bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4508 return SU && SU->getValue() ==
nullptr;
4511 return !ContainsNulls;
4516 if (
I != HasRecMap.end())
4521 HasRecMap.insert({S, FoundAddRec});
4529 if (
SI == ExprValueMap.
end())
4531 return SI->second.getArrayRef();
4537void ScalarEvolution::eraseValueFromMap(
Value *V) {
4539 if (
I != ValueExprMap.end()) {
4540 auto EVIt = ExprValueMap.find(
I->second);
4541 bool Removed = EVIt->second.remove(V);
4543 assert(Removed &&
"Value not in ExprValueMap?");
4544 ValueExprMap.erase(
I);
4548void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4552 auto It = ValueExprMap.find_as(V);
4553 if (It == ValueExprMap.end()) {
4555 ExprValueMap[S].insert(V);
4566 return createSCEVIter(V);
4573 if (
I != ValueExprMap.end()) {
4574 const SCEV *S =
I->second;
4575 assert(checkValidity(S) &&
4576 "existing SCEV has not been properly invalidated");
4589 Type *Ty = V->getType();
4605 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4618 return (
const SCEV *)
nullptr;
4624 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4628 Type *Ty = V->getType();
4634 assert(
P->getType()->isPointerTy());
4649 if (AddOp->getType()->isPointerTy()) {
4650 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4668 return getZero(LHS->getType());
4673 if (RHS->getType()->isPointerTy()) {
4674 if (!LHS->getType()->isPointerTy() ||
4684 const bool RHSIsNotMinSigned =
4715 Type *SrcTy = V->getType();
4716 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4717 "Cannot truncate or zero extend with non-integer arguments!");
4727 Type *SrcTy = V->getType();
4728 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4729 "Cannot truncate or zero extend with non-integer arguments!");
4738 Type *SrcTy = V->getType();
4739 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4740 "Cannot noop or zero extend with non-integer arguments!");
4742 "getNoopOrZeroExtend cannot truncate!");
4749 Type *SrcTy = V->getType();
4750 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4751 "Cannot noop or sign extend with non-integer arguments!");
4753 "getNoopOrSignExtend cannot truncate!");
4760 Type *SrcTy = V->getType();
4761 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4762 "Cannot noop or any extend with non-integer arguments!");
4764 "getNoopOrAnyExtend cannot truncate!");
4771 Type *SrcTy = V->getType();
4772 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4773 "Cannot truncate or noop with non-integer arguments!");
4775 "getTruncateOrNoop cannot extend!");
4783 const SCEV *PromotedLHS = LHS;
4784 const SCEV *PromotedRHS = RHS;
4804 assert(!
Ops.empty() &&
"At least one operand must be!");
4806 if (
Ops.size() == 1)
4810 Type *MaxType =
nullptr;
4816 assert(MaxType &&
"Failed to find maximum type!");
4829 if (!V->getType()->isPointerTy())
4834 V = AddRec->getStart();
4836 const SCEV *PtrOp =
nullptr;
4837 for (
const SCEV *AddOp :
Add->operands()) {
4838 if (AddOp->getType()->isPointerTy()) {
4839 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4843 assert(PtrOp &&
"Must have pointer op");
4855 for (
User *U :
I->users()) {
4857 if (Visited.
insert(UserInsn).second)
4871 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4872 bool IgnoreOtherLoops =
true) {
4875 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4877 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4882 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4884 SeenLoopVariantSCEVUnknown =
true;
4888 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4892 SeenOtherLoops =
true;
4896 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4898 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4901 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
4902 : SCEVRewriteVisitor(SE),
L(
L) {}
4905 bool SeenLoopVariantSCEVUnknown =
false;
4906 bool SeenOtherLoops =
false;
4915 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
4916 SCEVPostIncRewriter
Rewriter(L, SE);
4918 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4923 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4925 SeenLoopVariantSCEVUnknown =
true;
4929 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4933 SeenOtherLoops =
true;
4937 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4939 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4942 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
4943 : SCEVRewriteVisitor(SE),
L(
L) {}
4946 bool SeenLoopVariantSCEVUnknown =
false;
4947 bool SeenOtherLoops =
false;
4953class SCEVBackedgeConditionFolder
4956 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4957 ScalarEvolution &SE) {
4958 bool IsPosBECond =
false;
4959 Value *BECond =
nullptr;
4960 if (BasicBlock *Latch =
L->getLoopLatch()) {
4962 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
4963 "Both outgoing branches should not target same header!");
4964 BECond = BI->getCondition();
4965 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
4970 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
4974 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4975 const SCEV *
Result = Expr;
4980 switch (
I->getOpcode()) {
4981 case Instruction::Select: {
4983 std::optional<const SCEV *> Res =
4984 compareWithBackedgeCondition(
SI->getCondition());
4992 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
5003 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
5004 bool IsPosBECond, ScalarEvolution &SE)
5005 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
5006 IsPositiveBECond(IsPosBECond) {}
5008 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5012 Value *BackedgeCond =
nullptr;
5014 bool IsPositiveBECond;
5017std::optional<const SCEV *>
5018SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5023 if (BackedgeCond == IC)
5026 return std::nullopt;
5031 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5032 ScalarEvolution &SE) {
5038 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5045 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5055 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5056 : SCEVRewriteVisitor(SE),
L(
L) {}
5064void ScalarEvolution::inferNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5080 const APInt &BECountAP = BECountMax->getAPInt();
5081 unsigned NoOverflowBitWidth =
5090ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5100 if (!SignedWrapViaInductionTried.insert(AR).second)
5125 AC.assumptions().empty())
5133 const SCEV *OverflowLimit =
5135 if (OverflowLimit &&
5143ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5153 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5178 AC.assumptions().empty())
5187 const SCEV *OverflowLimit =
5216 IsNSW = OBO->hasNoSignedWrap();
5217 IsNUW = OBO->hasNoUnsignedWrap();
5223 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5235 return std::nullopt;
5241 switch (
Op->getOpcode()) {
5242 case Instruction::Add:
5243 case Instruction::Sub:
5244 case Instruction::Mul:
5245 case Instruction::UDiv:
5246 case Instruction::URem:
5247 case Instruction::And:
5248 case Instruction::AShr:
5249 case Instruction::Shl:
5252 case Instruction::Or: {
5255 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5265 case Instruction::Xor:
5269 if (RHSC->getValue().isSignMask())
5270 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5272 if (V->getType()->isIntegerTy(1))
5273 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5276 case Instruction::LShr:
5285 if (SA->getValue().ult(
BitWidth)) {
5287 ConstantInt::get(SA->getContext(),
5289 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5294 case Instruction::ExtractValue: {
5296 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5304 bool Signed = WO->isSigned();
5307 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5312 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5323 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5324 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5326 return std::nullopt;
5352 if (
Op == SymbolicPHI)
5357 if (SourceBits != NewBits)
5375 if (!L || L->getHeader() != PN->
getParent())
5433std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5434ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5442 assert(L &&
"Expecting an integer loop header phi");
5447 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5448 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5449 Value *
V = PN->getIncomingValue(i);
5450 if (
L->contains(PN->getIncomingBlock(i))) {
5453 }
else if (BEValueV != V) {
5457 }
else if (!StartValueV) {
5459 }
else if (StartValueV != V) {
5460 StartValueV =
nullptr;
5464 if (!BEValueV || !StartValueV)
5465 return std::nullopt;
5467 const SCEV *BEValue =
getSCEV(BEValueV);
5474 return std::nullopt;
5478 unsigned FoundIndex =
Add->getNumOperands();
5479 Type *TruncTy =
nullptr;
5481 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5484 if (FoundIndex == e) {
5489 if (FoundIndex ==
Add->getNumOperands())
5490 return std::nullopt;
5494 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5495 if (i != FoundIndex)
5496 Ops.push_back(
Add->getOperand(i));
5502 return std::nullopt;
5555 const SCEV *StartVal =
getSCEV(StartValueV);
5556 const SCEV *PHISCEV =
5583 auto getExtendedExpr = [&](
const SCEV *Expr,
5584 bool CreateSignExtend) ->
const SCEV * {
5587 const SCEV *ExtendedExpr =
5590 return ExtendedExpr;
5598 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5599 const SCEV *ExtendedExpr) ->
bool {
5600 return Expr != ExtendedExpr &&
5604 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5605 if (PredIsKnownFalse(StartVal, StartExtended)) {
5607 return std::nullopt;
5612 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5613 if (PredIsKnownFalse(Accum, AccumExtended)) {
5615 return std::nullopt;
5618 auto AppendPredicate = [&](
const SCEV *Expr,
5619 const SCEV *ExtendedExpr) ->
void {
5620 if (Expr != ExtendedExpr &&
5628 AppendPredicate(StartVal, StartExtended);
5629 AppendPredicate(Accum, AccumExtended);
5637 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5638 std::make_pair(NewAR, Predicates);
5640 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5644std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5649 return std::nullopt;
5652 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5653 if (
I != PredicatedSCEVRewrites.end()) {
5654 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5657 if (Rewrite.first == SymbolicPHI)
5658 return std::nullopt;
5662 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5666 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5667 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5672 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5673 return std::nullopt;
5693 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5694 if (Expr1 != Expr2 &&
5695 !AllPreds.
implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5696 !AllPreds.
implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5713const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5715 Value *StartValueV) {
5718 assert(BEValueV && StartValueV);
5724 if (BO->Opcode != Instruction::Add)
5727 const SCEV *Accum =
nullptr;
5728 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5730 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5744 insertValueToMap(PN, PHISCEV);
5747 inferNoWrapViaConstantRanges(AR);
5754 "Accum is defined outside L, but is not invariant?");
5755 if (isAddRecNeverPoison(BEInst, L))
5762const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5770 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5776 }
else if (BEValueV != V) {
5780 }
else if (!StartValueV) {
5782 }
else if (StartValueV != V) {
5783 StartValueV =
nullptr;
5787 if (!BEValueV || !StartValueV)
5790 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5791 "PHI node already processed?");
5795 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5800 insertValueToMap(PN, SymbolicName);
5804 const SCEV *BEValue =
getSCEV(BEValueV);
5814 unsigned FoundIndex =
Add->getNumOperands();
5815 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5816 if (
Add->getOperand(i) == SymbolicName)
5817 if (FoundIndex == e) {
5822 if (FoundIndex !=
Add->getNumOperands()) {
5825 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5826 if (i != FoundIndex)
5827 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5839 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5846 if (
GEP->getOperand(0) == PN) {
5847 GEPNoWrapFlags NW =
GEP->getNoWrapFlags();
5865 const SCEV *StartVal =
getSCEV(StartValueV);
5866 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5871 forgetMemoizedResults({SymbolicName});
5872 insertValueToMap(PN, PHISCEV);
5875 inferNoWrapViaConstantRanges(AR);
5899 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5900 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5902 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
5903 const SCEV *StartVal =
getSCEV(StartValueV);
5904 if (Start == StartVal) {
5908 forgetMemoizedResults({SymbolicName});
5909 insertValueToMap(PN, Shifted);
5919 eraseValueFromMap(PN);
5934 Use &LeftUse =
Merge->getOperandUse(0);
5935 Use &RightUse =
Merge->getOperandUse(1);
5971 assert(IDom &&
"At least the entry block should dominate PN");
5979const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
5984 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
6001 CommonInst = IncomingInst;
6017ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6023 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6024 bool SCEVExprsIdentical =
6026 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6027 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6030const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6031 if (
const SCEV *S = createAddRecFromPHI(PN))
6041 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6044 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6053 struct FindClosure {
6054 const SCEV *OperandToFind;
6060 bool canRecurseInto(
SCEVTypes Kind)
const {
6063 return RootKind == Kind || NonSequentialRootKind == Kind ||
6068 : OperandToFind(OperandToFind), RootKind(RootKind),
6069 NonSequentialRootKind(
6073 bool follow(
const SCEV *S) {
6074 Found = S == OperandToFind;
6076 return !isDone() && canRecurseInto(S->
getSCEVType());
6079 bool isDone()
const {
return Found; }
6082 FindClosure FC(OperandToFind, RootKind);
6087std::optional<const SCEV *>
6088ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6098 switch (ICI->getPredicate()) {
6112 bool Signed = ICI->isSigned();
6113 const SCEV *LA =
getSCEV(TrueVal);
6121 if (LA == LS &&
RA == RS)
6123 if (LA == RS &&
RA == LS)
6126 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6127 if (
Op->getType()->isPointerTy()) {
6138 LS = CoerceOperand(LS);
6139 RS = CoerceOperand(RS);
6163 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6164 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6178 X = ZExt->getOperand();
6180 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6191 return std::nullopt;
6194static std::optional<const SCEV *>
6196 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6200 "Unexpected operands of a select.");
6212 return std::nullopt;
6227static std::optional<const SCEV *>
6231 return std::nullopt;
6234 const auto *SETrue = SE->
getSCEV(TrueVal);
6235 const auto *SEFalse = SE->
getSCEV(FalseVal);
6239const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6241 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6243 V->getType() ==
TrueVal->getType() &&
6244 "Types of select hands and of the result must match.");
6247 if (!
V->getType()->isIntegerTy(1))
6250 if (std::optional<const SCEV *> S =
6263 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6267 if (std::optional<const SCEV *> S =
6268 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6274 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6280 assert(
GEP->getSourceElementType()->isSized() &&
6281 "GEP source element type must be sized");
6284 for (
Value *Index :
GEP->indices())
6289APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6292 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6295 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6297 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6300 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6318 return GetShiftedByZeros(TZ);
6328 return GetShiftedByZeros(TZ);
6332 if (
M->hasNoUnsignedWrap()) {
6335 for (
const SCEV *Operand :
M->operands().drop_front())
6343 for (
const SCEV *Operand :
M->operands())
6345 return GetShiftedByZeros(TZ);
6350 if (
N->hasNoUnsignedWrap())
6351 return GetGCDMultiple(
N);
6354 for (
const SCEV *Operand :
N->operands().drop_front())
6356 return GetShiftedByZeros(TZ);
6373 CtxI = &*F.getEntryBlock().begin();
6380 .allowEphemerals(
true))
6381 .countMinTrailingZeros();
6382 return GetShiftedByZeros(
Known);
6395 return getConstantMultipleImpl(S, CtxI);
6397 auto I = ConstantMultipleCache.find(S);
6398 if (
I != ConstantMultipleCache.end())
6401 APInt Result = getConstantMultipleImpl(S, CtxI);
6402 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6403 assert(InsertPair.second &&
"Should insert a new key");
6404 return InsertPair.first->second;
6421 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6424 if (std::optional<ConstantRange>
Range = CB->getRange())
6428 if (std::optional<ConstantRange>
Range =
A->getRange())
6431 return std::nullopt;
6438 UnsignedRanges.erase(AddRec);
6439 SignedRanges.erase(AddRec);
6440 ConstantMultipleCache.erase(AddRec);
6445getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6471 Value *Start, *Step;
6478 assert(L && L->getHeader() ==
P->getParent());
6491 case Instruction::AShr:
6492 case Instruction::LShr:
6493 case Instruction::Shl:
6508 KnownStep.getBitWidth() ==
BitWidth);
6511 auto MaxShiftAmt = KnownStep.getMaxValue();
6513 bool Overflow =
false;
6514 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6521 case Instruction::AShr: {
6529 if (KnownStart.isNonNegative())
6532 KnownStart.getMaxValue() + 1);
6533 if (KnownStart.isNegative())
6536 KnownEnd.getMaxValue() + 1);
6539 case Instruction::LShr: {
6548 KnownStart.getMaxValue() + 1);
6550 case Instruction::Shl: {
6554 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6555 return ConstantRange(KnownStart.getMinValue(),
6556 KnownEnd.getMaxValue() + 1);
6581 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6588ScalarEvolution::getRangeRefIter(
const SCEV *S,
6589 ScalarEvolution::RangeSignHint SignHint) {
6590 DenseMap<const SCEV *, ConstantRange> &Cache =
6591 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6594 SmallPtrSet<const SCEV *, 8> Seen;
6598 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6599 if (!Seen.
insert(Expr).second)
6632 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6633 const SCEV *
P = WorkList[
I];
6637 for (
const SCEV *
Op :
P->operands())
6650 if (!WorkList.
empty()) {
6655 getRangeRef(
P, SignHint);
6659 return getRangeRef(S, SignHint, 0);
6662const APInt *ScalarEvolution::getConstantAPIntOrNull(
const SCEV *S) {
6664 return &
C->getAPInt();
6672 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6673 DenseMap<const SCEV *, ConstantRange> &Cache =
6674 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6681 auto I = Cache.
find(S);
6682 if (
I != Cache.
end())
6686 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6691 return getRangeRefIter(S, SignHint);
6694 ConstantRange ConservativeResult(
BitWidth,
true);
6695 using OBO = OverflowingBinaryOperator;
6699 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6703 ConservativeResult =
6710 ConservativeResult = ConstantRange(
6726 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6733 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6740 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6745 return setRange(Cast, SignHint,
X);
6750 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6751 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6753 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6754 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6755 ConservativeResult =
6756 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6758 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6759 unsigned WrapType = OBO::AnyWrap;
6760 if (
Add->hasNoSignedWrap())
6761 WrapType |= OBO::NoSignedWrap;
6762 if (
Add->hasNoUnsignedWrap())
6763 WrapType |= OBO::NoUnsignedWrap;
6765 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6767 return setRange(
Add, SignHint,
6768 ConservativeResult.intersectWith(
X, RangeType));
6772 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6774 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6775 return setRange(
Mul, SignHint,
6776 ConservativeResult.intersectWith(
X, RangeType));
6780 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6781 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6782 return setRange(UDiv, SignHint,
6783 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6791 if (!UnsignedMinValue.
isZero())
6792 ConservativeResult = ConservativeResult.intersectWith(
6793 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6802 bool AllNonNeg =
true;
6803 bool AllNonPos =
true;
6804 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6811 ConservativeResult = ConservativeResult.intersectWith(
6816 ConservativeResult = ConservativeResult.intersectWith(
6825 const SCEV *MaxBEScev =
6839 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
6841 ConservativeResult =
6842 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6845 auto RangeFromFactoring = getRangeViaFactoring(
6847 ConservativeResult =
6848 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6854 const SCEV *SymbolicMaxBECount =
6859 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6860 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6861 ConservativeResult =
6862 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6867 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6877 ID = Intrinsic::umax;
6880 ID = Intrinsic::smax;
6884 ID = Intrinsic::umin;
6887 ID = Intrinsic::smin;
6894 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6895 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6897 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6898 return setRange(S, SignHint,
6899 ConservativeResult.intersectWith(
X, RangeType));
6908 ConservativeResult =
6909 ConservativeResult.intersectWith(*MDRange, RangeType);
6914 auto CR = getRangeForUnknownRecurrence(U);
6915 ConservativeResult = ConservativeResult.intersectWith(CR);
6926 if (
U->getType()->isPointerTy()) {
6929 unsigned ptrSize = DL.getPointerTypeSizeInBits(
U->getType());
6930 int ptrIdxDiff = ptrSize -
BitWidth;
6931 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
6937 if (!
Known.Zero.getHiBits(NS).isZero())
6938 Known.Zero.setHighBits(NS);
6939 if (!
Known.One.getHiBits(NS).isZero())
6940 Known.One.setHighBits(NS);
6943 if (
Known.getMinValue() !=
Known.getMaxValue() + 1)
6944 ConservativeResult = ConservativeResult.intersectWith(
6945 ConstantRange(
Known.getMinValue(),
Known.getMaxValue() + 1),
6948 ConservativeResult = ConservativeResult.intersectWith(
6953 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6957 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
6958 DL, CanBeNull,
nullptr);
6974 ConservativeResult = ConservativeResult.intersectWith(
6984 return getRangeRef(AR, SignHint,
Depth + 1);
6988 ConstantRange RangeFromOps(
BitWidth,
false);
6990 for (
const auto &
Op :
Phi->operands()) {
6992 RangeFromOps = RangeFromOps.unionWith(OpRange);
6994 if (RangeFromOps.isFullSet())
6997 ConservativeResult =
6998 ConservativeResult.intersectWith(RangeFromOps, RangeType);
7004 if (
II->getIntrinsicID() == Intrinsic::vscale) {
7006 ConservativeResult = ConservativeResult.difference(Disallowed);
7009 return setRange(U, SignHint, std::move(ConservativeResult));
7015 return setRange(S, SignHint, std::move(ConservativeResult));
7023static std::pair<ConstantRange, bool>
7031 if (Step == 0 || MaxBECount == 0)
7032 return {StartRange,
true};
7038 return {ConstantRange::getFull(
BitWidth),
false};
7054 return {ConstantRange::getFull(
BitWidth),
false};
7067 APInt MovedBoundary;
7072 MovedBoundary = StartLower - std::move(
Offset);
7075 MovedBoundary = StartUpper + std::move(
Offset);
7079 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
7086 if (StartRange.
contains(MovedBoundary))
7087 return {ConstantRange::getFull(
BitWidth),
false};
7090 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7092 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7100std::pair<ConstantRange, SCEV::NoWrapFlags>
7101ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
7102 const APInt &MaxBECount) {
7106 "mismatched bit widths");
7115 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7117 StartSRange, MaxBECount,
7119 ConstantRange SR = SR1.unionWith(SR2);
7136ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7138 ScalarEvolution::RangeSignHint SignHint) {
7139 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7141 "This only works for non-self-wrapping AddRecs!");
7142 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7146 return ConstantRange::getFull(
BitWidth);
7154 return ConstantRange::getFull(
BitWidth);
7158 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7160 MaxItersWithoutWrap))
7161 return ConstantRange::getFull(
BitWidth);
7182 ConstantRange StartRange = getRangeRef(Start, SignHint);
7183 ConstantRange EndRange = getRangeRef(End, SignHint);
7184 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7188 return RangeBetween;
7193 return ConstantRange::getFull(
BitWidth);
7196 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7197 return RangeBetween;
7199 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7200 return RangeBetween;
7201 return ConstantRange::getFull(
BitWidth);
7206 const APInt &MaxBECount) {
7213 "mismatched bit widths");
7215 struct SelectPattern {
7216 Value *Condition =
nullptr;
7220 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7222 std::optional<unsigned> CastOp;
7236 CastOp = SCast->getSCEVType();
7237 S = SCast->getOperand();
7240 using namespace llvm::PatternMatch;
7247 Condition =
nullptr;
7279 bool isRecognized() {
return Condition !=
nullptr; }
7282 SelectPattern StartPattern(*
this,
BitWidth, Start);
7283 if (!StartPattern.isRecognized())
7284 return ConstantRange::getFull(
BitWidth);
7286 SelectPattern StepPattern(*
this,
BitWidth, Step);
7287 if (!StepPattern.isRecognized())
7288 return ConstantRange::getFull(
BitWidth);
7290 if (StartPattern.Condition != StepPattern.Condition) {
7294 return ConstantRange::getFull(
BitWidth);
7305 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7306 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7307 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7308 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7310 ConstantRange TrueRange =
7311 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7312 ConstantRange FalseRange =
7313 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7325 PDI && PDI->isDisjoint()) {
7340ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7353 SmallPtrSet<const SCEV *, 16> Visited;
7355 auto pushOp = [&](
const SCEV *S) {
7356 if (!Visited.
insert(S).second)
7359 if (Visited.
size() > 30) {
7370 while (!Worklist.
empty()) {
7372 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7373 if (!Bound || DT.dominates(Bound, DefI))
7380 return Bound ? Bound : &*F.getEntryBlock().begin();
7386 return getDefiningScopeBound(
Ops, Discard);
7389bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7391 if (
A->getParent() ==
B->getParent() &&
7396 auto *BLoop = LI.getLoopFor(
B->getParent());
7397 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7398 BLoop->getLoopPreheader() ==
A->getParent() &&
7400 A->getParent()->end()) &&
7408 SCEVPoisonCollector PC(
true);
7410 return PC.MaybePoison.
empty();
7413bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7423bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7440 for (
const Use &
Op :
I->operands()) {
7446 auto *DefI = getDefiningScopeBound(SCEVOps);
7447 return isGuaranteedToTransferExecutionTo(DefI,
I);
7450bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7452 if (isSCEVExprNeverPoison(
I))
7463 auto *ExitingBB =
L->getExitingBlock();
7467 SmallPtrSet<const Value *, 16> KnownPoison;
7476 while (!Worklist.
empty()) {
7479 for (
const Use &U :
Poison->uses()) {
7482 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7486 if (KnownPoison.
insert(PoisonUser).second)
7494ScalarEvolution::LoopProperties
7495ScalarEvolution::getLoopProperties(
const Loop *L) {
7496 using LoopProperties = ScalarEvolution::LoopProperties;
7498 auto Itr = LoopPropertiesCache.find(L);
7499 if (Itr == LoopPropertiesCache.end()) {
7502 return !
SI->isSimple();
7512 return I->mayWriteToMemory();
7515 LoopProperties LP = {
true,
7518 for (
auto *BB :
L->getBlocks())
7519 for (
auto &
I : *BB) {
7521 LP.HasNoAbnormalExits =
false;
7522 if (HasSideEffects(&
I))
7523 LP.HasNoSideEffects =
false;
7524 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7528 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7529 assert(InsertPair.second &&
"We just checked!");
7530 Itr = InsertPair.first;
7543const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7549 Stack.emplace_back(V,
false);
7550 while (!Stack.empty()) {
7551 auto E = Stack.back();
7552 Value *CurV = E.getPointer();
7560 const SCEV *CreatedSCEV =
nullptr;
7563 CreatedSCEV = createSCEV(CurV);
7568 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7572 insertValueToMap(CurV, CreatedSCEV);
7575 Stack.back().setInt(
true);
7578 Stack.emplace_back(
Op,
false);
7595 if (!DT.isReachableFromEntry(
I->getParent()))
7608 switch (BO->Opcode) {
7609 case Instruction::Add:
7610 case Instruction::Mul: {
7617 Ops.push_back(BO->
Op);
7621 Ops.push_back(BO->RHS);
7625 (BO->Opcode == Instruction::Add &&
7626 (NewBO->Opcode != Instruction::Add &&
7627 NewBO->Opcode != Instruction::Sub)) ||
7628 (BO->Opcode == Instruction::Mul &&
7629 NewBO->Opcode != Instruction::Mul)) {
7630 Ops.push_back(BO->LHS);
7635 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7638 Ops.push_back(BO->LHS);
7646 case Instruction::Sub:
7647 case Instruction::UDiv:
7648 case Instruction::URem:
7650 case Instruction::AShr:
7651 case Instruction::Shl:
7652 case Instruction::Xor:
7656 case Instruction::And:
7657 case Instruction::Or:
7661 case Instruction::LShr:
7668 Ops.push_back(BO->LHS);
7669 Ops.push_back(BO->RHS);
7673 switch (
U->getOpcode()) {
7674 case Instruction::Trunc:
7675 case Instruction::ZExt:
7676 case Instruction::SExt:
7677 case Instruction::PtrToAddr:
7678 case Instruction::PtrToInt:
7679 Ops.push_back(
U->getOperand(0));
7682 case Instruction::BitCast:
7684 Ops.push_back(
U->getOperand(0));
7689 case Instruction::SDiv:
7690 case Instruction::SRem:
7691 Ops.push_back(
U->getOperand(0));
7692 Ops.push_back(
U->getOperand(1));
7695 case Instruction::GetElementPtr:
7697 "GEP source element type must be sized");
7701 case Instruction::IntToPtr:
7704 case Instruction::PHI:
7735 Ops.push_back(CondICmp->getOperand(0));
7736 Ops.push_back(CondICmp->getOperand(1));
7756 case Instruction::Select: {
7758 auto CanSimplifyToUnknown = [
this,
U]() {
7776 if (CanSimplifyToUnknown())
7783 case Instruction::Call:
7784 case Instruction::Invoke:
7791 switch (
II->getIntrinsicID()) {
7792 case Intrinsic::abs:
7793 Ops.push_back(
II->getArgOperand(0));
7795 case Intrinsic::umax:
7796 case Intrinsic::umin:
7797 case Intrinsic::smax:
7798 case Intrinsic::smin:
7799 case Intrinsic::usub_sat:
7800 case Intrinsic::uadd_sat:
7801 Ops.push_back(
II->getArgOperand(0));
7802 Ops.push_back(
II->getArgOperand(1));
7804 case Intrinsic::start_loop_iterations:
7805 case Intrinsic::annotation:
7806 case Intrinsic::ptr_annotation:
7807 Ops.push_back(
II->getArgOperand(0));
7819const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7828 if (!DT.isReachableFromEntry(
I->getParent()))
7843 switch (BO->Opcode) {
7844 case Instruction::Add: {
7870 if (BO->Opcode == Instruction::Sub)
7878 if (BO->Opcode == Instruction::Sub)
7885 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7886 NewBO->Opcode != Instruction::Sub)) {
7896 case Instruction::Mul: {
7917 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7926 case Instruction::UDiv:
7930 case Instruction::URem:
7934 case Instruction::Sub: {
7937 Flags = getNoWrapFlagsFromUB(BO->
Op);
7942 Value *PtrLHS =
nullptr, *PtrRHS =
nullptr;
7945 if (HasPtrLHS || HasPtrRHS) {
7950 auto GetOp = [&](
bool HasPtr,
Value *PtrOp,
Value *OrigOp,
7951 bool BothPtr) ->
const SCEV * {
7954 const SCEV *PtrSCEV =
getSCEV(PtrOp);
7964 const SCEV *
L = GetOp(HasPtrLHS, PtrLHS, BO->LHS, HasPtrRHS);
7965 const SCEV *
R = GetOp(HasPtrRHS, PtrRHS, BO->RHS, HasPtrLHS);
7973 case Instruction::And:
7979 if (CI->isMinusOne())
7981 const APInt &
A = CI->getValue();
7987 unsigned LZ =
A.countl_zero();
7988 unsigned TZ =
A.countr_zero();
7993 APInt EffectiveMask =
7995 if ((LZ != 0 || TZ != 0) && !((~
A & ~
Known.Zero) & EffectiveMask)) {
7998 const SCEV *ShiftedLHS =
nullptr;
8002 unsigned MulZeros = OpC->getAPInt().countr_zero();
8003 unsigned GCD = std::min(MulZeros, TZ);
8008 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
8030 case Instruction::Or:
8039 case Instruction::Xor:
8042 if (CI->isMinusOne())
8051 if (LBO->getOpcode() == Instruction::And &&
8052 LCI->getValue() == CI->getValue())
8053 if (
const SCEVZeroExtendExpr *Z =
8056 const SCEV *Z0 =
Z->getOperand();
8063 if (CI->getValue().isMask(Z0TySize))
8069 APInt Trunc = CI->getValue().trunc(Z0TySize);
8078 case Instruction::Shl:
8096 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8105 ConstantInt *
X = ConstantInt::get(
8111 case Instruction::AShr:
8133 const SCEV *AddTruncateExpr =
nullptr;
8134 ConstantInt *ShlAmtCI =
nullptr;
8135 const SCEV *AddConstant =
nullptr;
8137 if (L &&
L->getOpcode() == Instruction::Add) {
8145 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8152 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8160 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8165 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8170 if (AddTruncateExpr && ShlAmtCI) {
8182 const APInt &ShlAmt = ShlAmtCI->
getValue();
8186 const SCEV *CompositeExpr =
8188 if (
L->getOpcode() != Instruction::Shl)
8189 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8198 switch (
U->getOpcode()) {
8199 case Instruction::Trunc:
8202 case Instruction::ZExt:
8205 case Instruction::SExt:
8215 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8216 Type *Ty =
U->getType();
8224 case Instruction::BitCast:
8230 case Instruction::PtrToAddr: {
8237 case Instruction::PtrToInt:
8241 case Instruction::IntToPtr:
8245 case Instruction::SDiv:
8252 case Instruction::SRem:
8259 case Instruction::GetElementPtr:
8262 case Instruction::PHI:
8265 case Instruction::Select:
8266 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8269 case Instruction::Call:
8270 case Instruction::Invoke:
8275 switch (
II->getIntrinsicID()) {
8276 case Intrinsic::abs:
8280 case Intrinsic::umax:
8284 case Intrinsic::umin:
8288 case Intrinsic::smax:
8292 case Intrinsic::smin:
8296 case Intrinsic::usub_sat: {
8297 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8298 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8302 case Intrinsic::uadd_sat: {
8303 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8304 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8308 case Intrinsic::start_loop_iterations:
8309 case Intrinsic::annotation:
8310 case Intrinsic::ptr_annotation:
8314 case Intrinsic::vscale:
8334 auto *ExitCountType = ExitCount->
getType();
8335 assert(ExitCountType->isIntegerTy());
8337 1 + ExitCountType->getScalarSizeInBits());
8350 auto CanAddOneWithoutOverflow = [&]() {
8352 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8363 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8393 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8394 assert(L->isLoopExiting(ExitingBlock) &&
8395 "Exiting block must actually branch out of the loop!");
8404 const auto *MaxExitCount =
8412 L->getExitingBlocks(ExitingBlocks);
8414 std::optional<unsigned> Res;
8415 for (
auto *ExitingBB : ExitingBlocks) {
8419 Res = std::gcd(*Res, Multiple);
8421 return Res.value_or(1);
8425 const SCEV *ExitCount) {
8455 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8456 assert(L->isLoopExiting(ExitingBlock) &&
8457 "Exiting block must actually branch out of the loop!");
8467 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8469 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8471 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8481 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8484 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8487 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8495 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8502 return getBackedgeTakenInfo(L).getExact(L,
this);
8504 return getBackedgeTakenInfo(L).getConstantMax(
this);
8506 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8513 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8518 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8522 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8532 for (
PHINode &PN : Header->phis())
8533 if (Visited.
insert(&PN).second)
8537ScalarEvolution::BackedgeTakenInfo &
8538ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8539 auto &BTI = getBackedgeTakenInfo(L);
8540 if (BTI.hasFullInfo())
8543 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8546 return Pair.first->second;
8548 BackedgeTakenInfo
Result =
8549 computeBackedgeTakenCount(L,
true);
8551 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8554ScalarEvolution::BackedgeTakenInfo &
8555ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8561 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8562 BackedgeTakenCounts.try_emplace(L);
8564 return Pair.first->second;
8569 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8576 if (
Result.hasAnyInfo()) {
8579 auto LoopUsersIt = LoopUsers.find(L);
8580 if (LoopUsersIt != LoopUsers.end())
8582 forgetMemoizedResults(ToForget);
8585 for (PHINode &PN :
L->getHeader()->phis())
8586 ConstantEvolutionLoopExitValue.erase(&PN);
8594 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8603 BackedgeTakenCounts.clear();
8604 PredicatedBackedgeTakenCounts.clear();
8605 BECountUsers.clear();
8606 LoopPropertiesCache.clear();
8607 ConstantEvolutionLoopExitValue.clear();
8608 ValueExprMap.clear();
8609 ValuesAtScopes.clear();
8610 ValuesAtScopesUsers.clear();
8611 LoopDispositions.clear();
8612 BlockDispositions.clear();
8613 UnsignedRanges.clear();
8614 SignedRanges.clear();
8615 ExprValueMap.clear();
8617 ConstantMultipleCache.clear();
8618 PredicatedSCEVRewrites.clear();
8620 FoldCacheUser.clear();
8622void ScalarEvolution::visitAndClearUsers(
8626 while (!Worklist.
empty()) {
8633 if (It != ValueExprMap.
end()) {
8635 eraseValueFromMap(It->first);
8637 ConstantEvolutionLoopExitValue.erase(PN);
8651 while (!LoopWorklist.
empty()) {
8655 forgetBackedgeTakenCounts(CurrL,
false);
8656 forgetBackedgeTakenCounts(CurrL,
true);
8659 PredicatedSCEVRewrites.remove_if(
8660 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8662 auto LoopUsersItr = LoopUsers.find(CurrL);
8663 if (LoopUsersItr != LoopUsers.end())
8668 visitAndClearUsers(Worklist, Visited, ToForget);
8670 LoopPropertiesCache.erase(CurrL);
8673 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8675 forgetMemoizedResults(ToForget);
8692 visitAndClearUsers(Worklist, Visited, ToForget);
8694 forgetMemoizedResults(ToForget);
8702 auto InvalidateValue = [&](
Value *Val) {
8706 struct InvalidationRootCollector {
8710 InvalidationRootCollector(
Loop *L) : L(L) {}
8712 bool follow(
const SCEV *S) {
8718 if (L->contains(AddRec->
getLoop()))
8723 bool isDone()
const {
return false; }
8726 InvalidationRootCollector
C(L);
8728 forgetMemoizedResults(
C.Roots);
8738 return isa<WithOverflowInst>(Inc);
8752 BlockDispositions.clear();
8753 LoopDispositions.clear();
8770 while (!Worklist.
empty()) {
8772 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8773 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8774 if (!LoopDispoRemoved && !BlockDispoRemoved)
8776 auto Users = SCEVUsers.find(Curr);
8777 if (
Users != SCEVUsers.end())
8790const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8794 if (!isComplete() || ExitNotTaken.
empty())
8805 for (
const auto &ENT : ExitNotTaken) {
8806 const SCEV *BECount = ENT.ExactNotTaken;
8809 "We should only have known counts for exiting blocks that dominate "
8812 Ops.push_back(BECount);
8817 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8818 "Predicate should be always true!");
8827const ScalarEvolution::ExitNotTakenInfo *
8828ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8829 const BasicBlock *ExitingBlock,
8830 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8831 for (
const auto &ENT : ExitNotTaken)
8832 if (ENT.ExitingBlock == ExitingBlock) {
8833 if (ENT.hasAlwaysTruePredicate())
8835 else if (Predicates) {
8845const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8847 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8848 if (!getConstantMax())
8851 for (
const auto &ENT : ExitNotTaken)
8852 if (!ENT.hasAlwaysTruePredicate()) {
8860 "No point in having a non-constant max backedge taken count!");
8861 return getConstantMax();
8864const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8866 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8874 for (
const auto &ENT : ExitNotTaken) {
8875 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8878 "We should only have known counts for exiting blocks that "
8884 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8885 "Predicate should be always true!");
8888 if (ExitCounts.
empty())
8897bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8899 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8900 return !ENT.hasAlwaysTruePredicate();
8902 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8918 this->ExactNotTaken = E = ConstantMaxNotTaken;
8919 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8924 "Exact is not allowed to be less precise than Constant Max");
8927 "Exact is not allowed to be less precise than Symbolic Max");
8930 "Symbolic Max is not allowed to be less precise than Constant Max");
8933 "No point in having a non-constant max backedge taken count!");
8935 for (
const auto PredList : PredLists)
8936 for (
const auto *
P : PredList) {
8944 "Backedge count should be int");
8947 "Max backedge count should be int");
8960ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
8962 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
8963 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
8964 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8966 ExitNotTaken.reserve(ExitCounts.
size());
8967 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
8968 std::back_inserter(ExitNotTaken),
8969 [&](
const EdgeExitInfo &EEI) {
8970 BasicBlock *ExitBB = EEI.first;
8971 const ExitLimit &EL = EEI.second;
8972 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
8973 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
8978 "No point in having a non-constant max backedge taken count!");
8982ScalarEvolution::BackedgeTakenInfo
8983ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
8984 bool AllowPredicates) {
8986 L->getExitingBlocks(ExitingBlocks);
8988 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8991 bool CouldComputeBECount =
true;
8993 const SCEV *MustExitMaxBECount =
nullptr;
8994 const SCEV *MayExitMaxBECount =
nullptr;
8995 bool MustExitMaxOrZero =
false;
8996 bool IsOnlyExit = ExitingBlocks.
size() == 1;
9007 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
9008 if (ExitIfTrue == CI->
isZero())
9012 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
9014 assert((AllowPredicates || EL.Predicates.empty()) &&
9015 "Predicated exit limit when predicates are not allowed!");
9020 ++NumExitCountsComputed;
9024 CouldComputeBECount =
false;
9031 "Exact is known but symbolic isn't?");
9032 ++NumExitCountsNotComputed;
9047 DT.dominates(ExitBB, Latch)) {
9048 if (!MustExitMaxBECount) {
9049 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9050 MustExitMaxOrZero = EL.MaxOrZero;
9053 EL.ConstantMaxNotTaken);
9057 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9060 EL.ConstantMaxNotTaken);
9064 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9068 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9074 for (
const auto &Pair : ExitCounts) {
9076 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9078 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9079 {
L, AllowPredicates});
9081 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9082 MaxBECount, MaxOrZero);
9085ScalarEvolution::ExitLimit
9086ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9087 bool IsOnlyExit,
bool AllowPredicates) {
9088 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9092 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9097 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9098 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9099 "It should have one successor in loop and one exit block!");
9110 if (!
L->contains(SBB)) {
9115 assert(Exit &&
"Exiting block must have at least one exit");
9116 return computeExitLimitFromSingleExitSwitch(
9117 L, SI, Exit, IsOnlyExit);
9124 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9125 bool AllowPredicates) {
9126 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9127 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9128 ControlsOnlyExit, AllowPredicates);
9131std::optional<ScalarEvolution::ExitLimit>
9132ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9133 bool ExitIfTrue,
bool ControlsOnlyExit,
9134 bool AllowPredicates) {
9136 (void)this->ExitIfTrue;
9137 (void)this->AllowPredicates;
9139 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9140 this->AllowPredicates == AllowPredicates &&
9141 "Variance in assumed invariant key components!");
9142 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9143 if (Itr == TripCountMap.end())
9144 return std::nullopt;
9148void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9150 bool ControlsOnlyExit,
9151 bool AllowPredicates,
9153 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9154 this->AllowPredicates == AllowPredicates &&
9155 "Variance in assumed invariant key components!");
9157 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9158 assert(InsertResult.second &&
"Expected successful insertion!");
9163ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9164 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9165 bool ControlsOnlyExit,
bool AllowPredicates) {
9167 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9171 ExitLimit EL = computeExitLimitFromCondImpl(
9172 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9173 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9177ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9178 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9179 bool ControlsOnlyExit,
bool AllowPredicates) {
9181 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9182 Cache, L, ExitCond, ExitIfTrue, AllowPredicates))
9183 return *LimitFromBinOp;
9189 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9190 if (EL.hasFullInfo() || !AllowPredicates)
9194 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9214 const WithOverflowInst *WO;
9229 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9230 ControlsOnlyExit, AllowPredicates);
9231 if (EL.hasAnyInfo())
9236 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9239std::optional<ScalarEvolution::ExitLimit>
9240ScalarEvolution::computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache,
9244 bool AllowPredicates) {
9253 return std::nullopt;
9257 ExitLimit EL0 = computeExitLimitFromCondCached(
9258 Cache, L, Op0, ExitIfTrue,
false, AllowPredicates);
9259 ExitLimit EL1 = computeExitLimitFromCondCached(
9260 Cache, L, Op1, ExitIfTrue,
false, AllowPredicates);
9265 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9270 if (EitherMayExit) {
9280 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9282 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9285 EL1.ConstantMaxNotTaken);
9287 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9289 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9292 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9296 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9297 BECount = EL0.ExactNotTaken;
9310 SymbolicMaxBECount =
9312 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9316ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9317 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9318 bool AllowPredicates) {
9330 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9332 if (EL.hasAnyInfo())
9335 auto *ExhaustiveCount =
9336 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9339 return ExhaustiveCount;
9341 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9344ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9346 bool ControlsOnlyExit,
bool AllowPredicates) {
9371 ConstantRange CompRange =
9389 InnerLHS = ZExt->getOperand();
9436 if (EL.hasAnyInfo())
9453 if (EL.hasAnyInfo())
return EL;
9485 ExitLimit EL = howManyLessThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9487 if (EL.hasAnyInfo())
9503 ExitLimit EL = howManyGreaterThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9505 if (EL.hasAnyInfo())
9516ScalarEvolution::ExitLimit
9517ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9519 BasicBlock *ExitingBlock,
9520 bool ControlsOnlyExit) {
9521 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9524 if (
Switch->getDefaultDest() == ExitingBlock)
9528 "Default case must not exit the loop!");
9534 if (EL.hasAnyInfo())
9546 "Evaluation of SCEV at constant didn't fold correctly?");
9550ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9560 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9567 auto MatchPositiveShift = [](
Value *
V,
Value *&OutLHS,
9569 unsigned &OutShiftAmt) {
9570 using namespace PatternMatch;
9572 ConstantInt *ShiftAmt;
9574 OutOpCode = Instruction::LShr;
9576 OutOpCode = Instruction::AShr;
9578 OutOpCode = Instruction::Shl;
9583 if (Amt == 0 || Amt >= OutLHS->getType()->getScalarSizeInBits())
9598 auto MatchShiftRecurrence = [&](
Value *
V, PHINode *&PNOut,
9600 unsigned &ShiftAmtOut) {
9601 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9617 if (MatchPositiveShift(
LHS, V, OpC, Amt)) {
9618 PostShiftOpCode = OpC;
9624 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9627 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9633 MatchPositiveShift(BEValue, OpLHS, OpCodeOut, ShiftAmtOut) &&
9640 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9646 if (!MatchShiftRecurrence(
LHS, PN, OpCode, ShiftAmt))
9658 ConstantInt *StableValue =
nullptr;
9663 case Instruction::AShr: {
9670 if (
Known.isNonNegative())
9671 StableValue = ConstantInt::get(Ty, 0);
9672 else if (
Known.isNegative())
9673 StableValue = ConstantInt::get(Ty, -1,
true);
9679 case Instruction::LShr:
9680 case Instruction::Shl:
9690 "Otherwise cannot be an operand to a branch instruction");
9692 if (
Result->isNullValue()) {
9701 if (OpCode == Instruction::LShr || OpCode == Instruction::AShr) {
9703 const SCEV *StartSCEV =
getSCEV(StartValue);
9707 unsigned RangeBTC =
divideCeil(ActiveBits, ShiftAmt);
9708 MaxBTC = std::min(MaxBTC, RangeBTC);
9712 const SCEV *UpperBound =
9729 if (
const Function *
F = CI->getCalledFunction())
9738 if (!L->contains(
I))
return false;
9743 return L->getHeader() ==
I->getParent();
9819 if (!
I)
return nullptr;
9832 std::vector<Constant*>
Operands(
I->getNumOperands());
9834 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9843 if (!
C)
return nullptr;
9865 if (IncomingVal != CurrentVal) {
9868 IncomingVal = CurrentVal;
9880ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9883 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9892 DenseMap<Instruction *, Constant *> CurrentIterVals;
9894 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9900 for (PHINode &
PHI : Header->phis()) {
9902 CurrentIterVals[&
PHI] = StartCST;
9904 if (!CurrentIterVals.
count(PN))
9905 return RetVal =
nullptr;
9911 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
9914 unsigned IterationNum = 0;
9916 for (; ; ++IterationNum) {
9917 if (IterationNum == NumIterations)
9918 return RetVal = CurrentIterVals[PN];
9922 DenseMap<Instruction *, Constant *> NextIterVals;
9927 NextIterVals[PN] = NextPHI;
9929 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
9935 for (
const auto &
I : CurrentIterVals) {
9937 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
9942 for (
const auto &
I : PHIsToCompute) {
9943 PHINode *
PHI =
I.first;
9946 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9949 if (NextPHI !=
I.second)
9950 StoppedEvolving =
false;
9955 if (StoppedEvolving)
9956 return RetVal = CurrentIterVals[PN];
9958 CurrentIterVals.swap(NextIterVals);
9962const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
9972 DenseMap<Instruction *, Constant *> CurrentIterVals;
9974 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9977 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
9979 for (PHINode &
PHI : Header->phis()) {
9981 CurrentIterVals[&
PHI] = StartCST;
9983 if (!CurrentIterVals.
count(PN))
9991 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
9998 if (CondVal->getValue() ==
uint64_t(ExitWhen)) {
9999 ++NumBruteForceTripCountsComputed;
10004 DenseMap<Instruction *, Constant *> NextIterVals;
10010 for (
const auto &
I : CurrentIterVals) {
10012 if (!
PHI ||
PHI->getParent() != Header)
continue;
10015 for (PHINode *
PHI : PHIsToCompute) {
10017 if (NextPHI)
continue;
10019 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10022 CurrentIterVals.
swap(NextIterVals);
10035 return LS.second ? LS.second : V;
10037 Values.emplace_back(L,
nullptr);
10040 const SCEV *
C = computeSCEVAtScope(V, L);
10041 for (
auto &LS :
reverse(ValuesAtScopes[V]))
10042 if (LS.first == L) {
10045 ValuesAtScopesUsers[
C].push_back({L, V});
10056 switch (V->getSCEVType()) {
10089 assert(!
C->getType()->isPointerTy() &&
10090 "Can only have one pointer, and it must be last");
10115const SCEV *ScalarEvolution::getWithOperands(
const SCEV *S,
10116 SmallVectorImpl<SCEVUse> &NewOps) {
10150const SCEV *ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10151 switch (
V->getSCEVType()) {
10162 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10173 for (++i; i !=
e; ++i)
10217 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10227 for (++i; i !=
e; ++i) {
10232 return getWithOperands(V, NewOps);
10247 const Loop *CurrLoop = this->LI[
I->getParent()];
10258 if (BackedgeTakenCount->
isZero()) {
10259 Value *InitValue =
nullptr;
10260 bool MultipleInitValues =
false;
10266 MultipleInitValues =
true;
10271 if (!MultipleInitValues && InitValue)
10280 unsigned InLoopPred =
10291 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10305 SmallVector<Constant *, 4>
Operands;
10307 bool MadeImprovement =
false;
10322 MadeImprovement |= OrigV != OpV;
10327 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10332 if (!MadeImprovement)
10353const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10355 return stripInjectiveFunctions(ZExt->getOperand());
10357 return stripInjectiveFunctions(SExt->getOperand());
10375 assert(
A != 0 &&
"A must be non-zero.");
10391 if (MinTZ < Mult2 && L->getLoopPredecessor())
10393 if (MinTZ < Mult2) {
10416 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10436static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10442 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10443 << *AddRec <<
'\n');
10446 if (!LC || !MC || !
NC) {
10447 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10448 return std::nullopt;
10454 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10462 N =
N.sext(NewWidth);
10463 M = M.sext(NewWidth);
10464 L = L.sext(NewWidth);
10481 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10482 <<
", multiplied by " <<
T <<
'\n');
10491 std::optional<APInt>
Y) {
10493 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10496 return XW.
slt(YW) ? *
X : *
Y;
10499 return std::nullopt;
10500 return X ? *
X : *
Y;
10517 return std::nullopt;
10518 unsigned W =
X->getBitWidth();
10538static std::optional<APInt>
10544 return std::nullopt;
10547 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10548 std::optional<APInt>
X =
10551 return std::nullopt;
10556 return std::nullopt;
10571static std::optional<APInt>
10575 "Starting value of addrec should be 0");
10576 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10577 <<
Range <<
", addrec " << *AddRec <<
'\n');
10581 "Addrec's initial value should be in range");
10587 return std::nullopt;
10597 auto SolveForBoundary =
10598 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10601 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10602 << Bound <<
" (before multiplying by " << M <<
")\n");
10605 std::optional<APInt> SO;
10608 "signed overflow\n");
10612 "unsigned overflow\n");
10613 std::optional<APInt> UO =
10616 auto LeavesRange = [&] (
const APInt &
X) {
10624 if (
Range.contains(
V1->getValue()))
10633 return {std::nullopt,
false};
10638 if (LeavesRange(*Min))
10639 return { Min,
true };
10640 std::optional<APInt> Max = Min == SO ? UO : SO;
10641 if (LeavesRange(*Max))
10642 return { Max,
true };
10645 return {std::nullopt,
true};
10652 auto SL = SolveForBoundary(
Lower);
10653 auto SU = SolveForBoundary(
Upper);
10656 if (!SL.second || !SU.second)
10657 return std::nullopt;
10700ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10702 bool ControlsOnlyExit,
10703 bool AllowPredicates) {
10714 if (
C->getValue()->isZero())
return C;
10718 const SCEVAddRecExpr *AddRec =
10721 if (!AddRec && AllowPredicates)
10727 if (!AddRec || AddRec->
getLoop() != L)
10738 return ExitLimit(R, R, R,
false, Predicates);
10796 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10822 const SCEV *
Exact =
10830 const SCEV *SymbolicMax =
10832 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10841 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10849 return ExitLimit(
E, M, S,
false, Predicates);
10852ScalarEvolution::ExitLimit
10853ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10861 if (!
C->getValue()->isZero())
10871std::pair<const BasicBlock *, const BasicBlock *>
10872ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10883 if (
const Loop *L = LI.getLoopFor(BB))
10884 return {
L->getLoopPredecessor(),
L->getHeader()};
10886 return {
nullptr, BB};
10895 if (
A ==
B)
return true;
10910 if (ComputesEqualValues(AI, BI))
10918 const SCEV *Op0, *Op1;
10937 auto TrivialCase = [&](
bool TriviallyTrue) {
10946 const SCEV *NewLHS, *NewRHS;
10970 return TrivialCase(
false);
10971 return TrivialCase(
true);
10990 RAdd->hasNoSignedWrap()) ||
10992 RAdd->hasNoUnsignedWrap())) {
11012 bool BothNUW = LMul->hasNoUnsignedWrap() && RMul->hasNoUnsignedWrap();
11013 bool BothNSW = LMul->hasNoSignedWrap() && RMul->hasNoSignedWrap();
11016 C->getAPInt().isStrictlyPositive()) ||
11040 const APInt &
RA = RC->getAPInt();
11042 bool SimplifiedByConstantRange =
false;
11047 return TrivialCase(
true);
11049 return TrivialCase(
false);
11058 Changed = SimplifiedByConstantRange =
true;
11062 if (!SimplifiedByConstantRange) {
11079 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
11085 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
11091 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
11097 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11109 return TrivialCase(
true);
11111 return TrivialCase(
false);
11216 auto NonRecursive = [OrNegative](
const SCEV *S) {
11218 return C->getAPInt().isPowerOf2() ||
11219 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11225 if (NonRecursive(S))
11235 const SCEV *S, uint64_t M,
11251 APInt C = Cst->getAPInt();
11252 return C.urem(M) == 0;
11260 const SCEV *SmodM =
11275 for (
auto *
A : Assumptions)
11276 if (
A->implies(
P, *
this))
11289std::pair<const SCEV *, const SCEV *>
11292 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11294 return { Start, Start };
11296 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11305 getUsedLoops(LHS, LoopsUsed);
11306 getUsedLoops(RHS, LoopsUsed);
11308 if (LoopsUsed.
empty())
11313 for (
const auto *L1 : LoopsUsed)
11314 for (
const auto *L2 : LoopsUsed)
11315 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11316 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11317 "Domination relationship is not a linear order");
11347 SplitRHS.second) &&
11359 if (isKnownPredicateViaSplitting(Pred, LHS, RHS))
11363 return isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11373 return std::nullopt;
11388 if (KnownWithoutContext)
11389 return KnownWithoutContext;
11396 return std::nullopt;
11402 const Loop *L = LHS->getLoop();
11407std::optional<ScalarEvolution::MonotonicPredicateType>
11410 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11416 auto ResultSwapped =
11419 assert(*ResultSwapped != *Result &&
11420 "monotonicity should flip as we flip the predicate");
11427std::optional<ScalarEvolution::MonotonicPredicateType>
11428ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11442 return std::nullopt;
11446 "Should be greater or less!");
11450 if (!LHS->hasNoUnsignedWrap())
11451 return std::nullopt;
11455 "Relational predicate is either signed or unsigned!");
11456 if (!
LHS->hasNoSignedWrap())
11457 return std::nullopt;
11459 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11467 return std::nullopt;
11470std::optional<ScalarEvolution::LoopInvariantPredicate>
11477 return std::nullopt;
11484 if (!ArLHS || ArLHS->
getLoop() != L)
11485 return std::nullopt;
11489 return std::nullopt;
11515 return std::nullopt;
11552 return std::nullopt;
11555std::optional<ScalarEvolution::LoopInvariantPredicate>
11560 Pred, LHS, RHS, L, CtxI, MaxIter))
11570 Pred, LHS, RHS, L, CtxI,
Op))
11572 return std::nullopt;
11575std::optional<ScalarEvolution::LoopInvariantPredicate>
11590 return std::nullopt;
11597 if (!AR || AR->
getLoop() != L)
11598 return std::nullopt;
11603 Pred = Pred.dropSameSign();
11607 return std::nullopt;
11613 if (Step != One && Step != MinusOne)
11614 return std::nullopt;
11620 return std::nullopt;
11626 return std::nullopt;
11634 if (Step == MinusOne)
11638 return std::nullopt;
11644bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11650 auto CheckRange = [&](
bool IsSigned) {
11653 return RangeLHS.
icmp(Pred, RangeRHS);
11662 if (CheckRange(
true) || CheckRange(
false))
11671bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11680 SCEVUse XNonConstOp, XConstOp;
11681 SCEVUse YNonConstOp, YConstOp;
11685 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11688 XFlagsPresent = ExpectedFlags;
11693 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11696 YFlagsPresent = ExpectedFlags;
11699 if (YNonConstOp != XNonConstOp)
11707 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11710 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11770bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11791bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11792 const SCEV *
LHS,
const SCEV *
RHS) {
11797 return any_of(*BB, [&](
const Instruction &
I) {
11798 using namespace llvm::PatternMatch;
11803 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11817 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11822 "This cannot be done on broken IR!");
11825 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11834 if (LoopContinuePredicate &&
11835 isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->
getCondition(),
11836 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11841 if (WalkingBEDominatingConds)
11847 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11848 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11855 const SCEV *LoopCounter =
11863 for (
auto &AssumeVH : AC.assumptions()) {
11870 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11874 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11877 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11878 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11879 assert(DTN &&
"should reach the loop header before reaching the root!");
11882 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11900 if (isImpliedCond(Pred, LHS, RHS, ContBr->
getCondition(),
11913 if (!DT.isReachableFromEntry(BB))
11917 "This cannot be done on broken IR!");
11925 const bool ProvingStrictComparison =
11927 bool ProvedNonStrictComparison =
false;
11928 bool ProvedNonEquality =
false;
11931 if (!ProvedNonStrictComparison)
11932 ProvedNonStrictComparison = Fn(NonStrictPredicate);
11933 if (!ProvedNonEquality)
11935 if (ProvedNonStrictComparison && ProvedNonEquality)
11940 if (ProvingStrictComparison) {
11942 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
11944 if (SplitAndProve(ProofFn))
11949 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
11951 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
11953 if (ProvingStrictComparison) {
11955 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
11957 if (SplitAndProve(ProofFn))
11966 const Loop *ContainingLoop = LI.getLoopFor(BB);
11968 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
11972 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
11973 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
11976 if (!BlockEntryPredicate)
11985 for (
auto &AssumeVH : AC.assumptions()) {
11989 if (!DT.dominates(CI, BB))
11992 if (ProveViaCond(CI->getArgOperand(0),
false))
11998 F.getParent(), Intrinsic::experimental_guard);
12000 for (
const auto *GU : GuardDecl->users())
12002 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
12003 if (ProveViaCond(Guard->getArgOperand(0),
false))
12018 "LHS is not available at Loop Entry");
12020 "RHS is not available at Loop Entry");
12022 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
12033 if (FoundCondValue ==
12037 if (!PendingLoopPredicates.insert(FoundCondValue).second)
12041 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
12044 const Value *Op0, *Op1;
12047 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
12051 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
12052 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
12056 if (!ICI)
return false;
12060 CmpPredicate FoundPred;
12069 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
12072bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
12073 const SCEV *
RHS, CmpPredicate FoundPred,
12074 const SCEV *FoundLHS,
const SCEV *FoundRHS,
12075 const Instruction *CtxI) {
12085 auto *WideType = FoundLHS->
getType();
12097 TruncFoundLHS, TruncFoundRHS, CtxI))
12123 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
12127bool ScalarEvolution::isImpliedCondBalancedTypes(
12132 "Types should be balanced!");
12139 if (FoundLHS == FoundRHS)
12143 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12155 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12172 LHS, FoundLHS, FoundRHS, CtxI);
12174 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12196 assert(P1 != P2 &&
"Handled earlier!");
12200 if (IsSignFlippedPredicate(Pred, FoundPred)) {
12204 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12207 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
12208 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
12209 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12214 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12225 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12226 CanonicalRHS, CanonicalFoundLHS,
12227 CanonicalFoundRHS);
12232 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12233 CanonicalRHS, CanonicalFoundLHS,
12234 CanonicalFoundRHS);
12241 const SCEVConstant *
C =
nullptr;
12242 const SCEV *
V =
nullptr;
12260 if (Min ==
C->getAPInt()) {
12265 APInt SharperMin = Min + 1;
12268 case ICmpInst::ICMP_SGE:
12269 case ICmpInst::ICMP_UGE:
12272 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12277 case ICmpInst::ICMP_SGT:
12278 case ICmpInst::ICMP_UGT:
12288 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12293 case ICmpInst::ICMP_SLE:
12294 case ICmpInst::ICMP_ULE:
12295 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12296 LHS, V, getConstant(SharperMin), CtxI))
12300 case ICmpInst::ICMP_SLT:
12301 case ICmpInst::ICMP_ULT:
12302 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12303 LHS, V, getConstant(Min), CtxI))
12317 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12321 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12324 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12340std::optional<APInt>
12347 APInt DiffMul(BW, 1);
12350 for (
unsigned I = 0;
I < 8; ++
I) {
12359 if (LAR->getLoop() != MAR->getLoop())
12360 return std::nullopt;
12364 if (!LAR->isAffine() || !MAR->isAffine())
12365 return std::nullopt;
12367 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12368 return std::nullopt;
12370 Less = LAR->getStart();
12371 More = MAR->getStart();
12376 auto MatchConstMul =
12377 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12382 return std::nullopt;
12384 if (
auto MatchedMore = MatchConstMul(More)) {
12385 if (
auto MatchedLess = MatchConstMul(
Less)) {
12386 if (MatchedMore->second == MatchedLess->second) {
12387 More = MatchedMore->first;
12388 Less = MatchedLess->first;
12389 DiffMul *= MatchedMore->second;
12400 Diff +=
C->getAPInt() * DiffMul;
12403 Diff -=
C->getAPInt() * DiffMul;
12406 Multiplicity[S] +=
Mul;
12408 auto Decompose = [&](
const SCEV *S,
int Mul) {
12415 Decompose(More, 1);
12416 Decompose(
Less, -1);
12420 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12421 for (
const auto &[S,
Mul] : Multiplicity) {
12426 return std::nullopt;
12428 }
else if (
Mul == -1) {
12430 return std::nullopt;
12433 return std::nullopt;
12437 if (NewMore == More || NewLess ==
Less)
12438 return std::nullopt;
12444 if (!More && !
Less)
12448 if (!More || !
Less)
12449 return std::nullopt;
12453 return std::nullopt;
12456bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12478 const auto *Latch = L->getLoopLatch();
12481 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12490 const auto *Latch = L->getLoopLatch();
12493 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12503bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12506 const SCEV *FoundLHS,
12507 const SCEV *FoundRHS) {
12516 if (!AddRecFoundLHS)
12523 const Loop *
L = AddRecFoundLHS->getLoop();
12524 if (L != AddRecLHS->getLoop())
12563 if (!RDiff || *LDiff != *RDiff)
12566 if (LDiff->isMinValue())
12569 APInt FoundRHSLimit;
12572 FoundRHSLimit = -(*RDiff);
12584bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12585 const SCEV *
RHS,
const SCEV *FoundLHS,
12586 const SCEV *FoundRHS,
unsigned Depth) {
12587 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12591 bool Erased = PendingMerges.erase(LPhi);
12592 assert(Erased &&
"Failed to erase LPhi!");
12596 bool Erased = PendingMerges.erase(RPhi);
12597 assert(Erased &&
"Failed to erase RPhi!");
12605 if (!PendingMerges.insert(Phi).second)
12619 if (!PendingMerges.insert(Phi).second)
12625 if (!LPhi && !RPhi)
12636 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12640 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12641 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12642 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12643 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12646 if (RPhi && RPhi->getParent() == LBB) {
12653 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12654 if (!ProvedEasily(L, R))
12665 auto *RLoop = RAR->
getLoop();
12666 auto *Predecessor = RLoop->getLoopPredecessor();
12667 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12669 if (!ProvedEasily(L1, RAR->
getStart()))
12671 auto *Latch = RLoop->getLoopLatch();
12672 assert(Latch &&
"Loop with AddRec with no latch?");
12693 if (
auto *
Loop = LI.getLoopFor(LBB))
12696 if (!ProvedEasily(L,
RHS))
12703bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12706 const SCEV *FoundLHS,
12707 const SCEV *FoundRHS) {
12710 if (
RHS == FoundRHS) {
12715 if (
LHS != FoundLHS)
12722 Value *Shiftee, *ShiftValue;
12724 using namespace PatternMatch;
12725 if (
match(SUFoundRHS->getValue(),
12727 auto *ShifteeS =
getSCEV(Shiftee);
12745bool ScalarEvolution::isImpliedCondOperandsViaMatchingDiff(
12746 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12747 const SCEV *FoundRHS) {
12779 const SCEV *FoundDiff =
getMinusSCEV(FoundLHS, FoundRHS);
12787 return Diff == FoundDiff;
12790bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12792 const SCEV *FoundLHS,
12793 const SCEV *FoundRHS,
12794 const Instruction *CtxI) {
12795 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12797 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12799 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12800 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12802 isImpliedCondOperandsViaMatchingDiff(Pred,
LHS,
RHS, FoundLHS,
12804 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12808template <
typename MinMaxExprType>
12810 const SCEV *Candidate) {
12815 return is_contained(MinMaxExpr->operands(), Candidate);
12828 const SCEV *LStart, *RStart, *Step;
12901bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
12903 const SCEV *FoundLHS,
12904 const SCEV *FoundRHS,
12908 "LHS and RHS have different sizes?");
12911 "FoundLHS and FoundRHS have different sizes?");
12945 auto GetOpFromSExt = [&](
const SCEV *S) ->
const SCEV * {
12947 return Ext->getOperand();
12954 auto *OrigLHS =
LHS;
12955 auto *OrigFoundLHS = FoundLHS;
12956 LHS = GetOpFromSExt(
LHS);
12957 FoundLHS = GetOpFromSExt(FoundLHS);
12960 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
12963 FoundRHS,
Depth + 1);
12976 if (!LHSAddExpr->hasNoSignedWrap())
12979 SCEVUse LL = LHSAddExpr->getOperand(0);
12980 SCEVUse LR = LHSAddExpr->getOperand(1);
12984 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
12985 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
12990 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
12996 using namespace llvm::PatternMatch;
13015 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
13023 auto *DTy = Denominator->getType();
13024 auto *FRHSTy = FoundRHS->
getType();
13025 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
13044 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
13055 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
13057 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
13065 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
13098bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
13102 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
13105 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
13108bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
13111 const SCEV *FoundLHS,
13112 const SCEV *FoundRHS) {
13148 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
13154bool ScalarEvolution::isImpliedCondOperandsViaRanges(
13155 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
13156 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13170 ConstantRange FoundLHSRange =
13174 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13181 return LHSRange.
icmp(Pred, ConstRHS);
13184bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13197 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13205 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13208bool ScalarEvolution::canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
13220 return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
13228 return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
13240const SCEV *ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
13241 const SCEV *Stride,
13272 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13283 :
APIntOps::umax(MaxEnd, MinStart);
13290ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13291 const Loop *L,
bool IsSigned,
13292 bool ControlsOnlyExit,
bool AllowPredicates) {
13296 bool PredicatedIV =
false;
13301 auto canProveNUW = [&]() {
13304 if (!ControlsOnlyExit)
13325 Limit = Limit.
zext(OuterBitWidth);
13337 Type *Ty = ZExt->getType();
13348 if (!
IV && AllowPredicates) {
13353 PredicatedIV =
true;
13357 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13371 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13374 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13379 bool IVMayOverflow =
true;
13382 if (!PositiveStride) {
13434 auto wouldZeroStrideBeUB = [&]() {
13446 if (!wouldZeroStrideBeUB()) {
13453 IVMayOverflow = canIVOverflowOnLT(
RHS, Stride, IsSigned);
13454 if (IVMayOverflow && !NoWrap)
13467 const SCEV *
Start =
IV->getStart();
13473 const SCEV *OrigStart =
Start;
13474 const SCEV *OrigRHS =
RHS;
13475 if (
Start->getType()->isPointerTy()) {
13486 const SCEV *End =
nullptr, *BECount =
nullptr,
13487 *BECountIfBackedgeTaken =
nullptr;
13490 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13491 any(RHSAddRec->getNoWrapFlags())) {
13504 const SCEV *RHSStart = RHSAddRec->getStart();
13505 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13517 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13526 BECountIfBackedgeTaken =
13531 if (BECount ==
nullptr) {
13536 const SCEV *MaxBECount = computeMaxBECountForLT(
13539 MaxBECount,
false , Predicates);
13546 auto *OrigStartMinusStride =
getMinusSCEV(OrigStart, Stride);
13573 const SCEV *Numerator =
13579 auto canProveRHSGreaterThanEqualStart = [&]() {
13598 auto *StartMinusOne =
13605 if (canProveRHSGreaterThanEqualStart()) {
13620 BECountIfBackedgeTaken =
13640 bool MayAddOverflow = IVMayOverflow && [&] {
13686 if (Start == Stride || Start ==
getMinusSCEV(Stride, One)) {
13700 if (!MayAddOverflow) {
13712 const SCEV *ConstantMaxBECount;
13713 bool MaxOrZero =
false;
13715 ConstantMaxBECount = BECount;
13716 }
else if (BECountIfBackedgeTaken &&
13721 ConstantMaxBECount = BECountIfBackedgeTaken;
13724 ConstantMaxBECount = computeMaxBECountForLT(
13732 const SCEV *SymbolicMaxBECount =
13734 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13738ScalarEvolution::ExitLimit ScalarEvolution::howManyGreaterThans(
13739 const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
bool IsSigned,
13740 bool ControlsOnlyExit,
bool AllowPredicates) {
13747 if (!
IV && AllowPredicates)
13754 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13758 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13771 bool MayAddOverflow =
false;
13772 const SCEV *
Start =
IV->getStart();
13773 const SCEV *End =
RHS;
13774 if (!Stride->
isOne() && canIVOverflowOnGT(
RHS, Stride, IsSigned)) {
13777 MayAddOverflow =
true;
13790 if (
Start->getType()->isPointerTy()) {
13802 const SCEV *BECount;
13803 if (MayAddOverflow) {
13834 const SCEV *ConstantMaxBECount =
13841 ConstantMaxBECount = BECount;
13842 const SCEV *SymbolicMaxBECount =
13845 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
13851 if (
Range.isFullSet())
13856 if (!SC->getValue()->isZero()) {
13862 return ShiftedAddRec->getNumIterationsInRange(
13863 Range.subtract(SC->getAPInt()), SE);
13894 APInt ExitVal = (End +
A).udiv(
A);
13907 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
13908 "Linear scev computation is off in a bad way!");
13939 assert(!
Last->isZero() &&
"Recurrency with zero step?");
13965 Ty =
Store->getValueOperand()->getType();
13966 PtrTy =
Store->getPointerOperandType();
13968 Ty =
Load->getType();
13969 PtrTy =
Load->getPointerOperandType();
13983 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13985 SE->ConstantEvolutionLoopExitValue.erase(PN);
13986 SE->eraseValueFromMap(getValPtr());
13990void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
13991 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14001 : CallbackVH(
V), SE(se) {}
14010 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
14012 LoopDispositions(64), BlockDispositions(64) {
14024 F.getParent(), Intrinsic::experimental_guard);
14025 HasGuards = GuardDecl && !GuardDecl->use_empty();
14029 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
14030 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
14031 ValueExprMap(
std::
move(Arg.ValueExprMap)),
14032 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
14033 PendingMerges(
std::
move(Arg.PendingMerges)),
14034 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
14035 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
14036 PredicatedBackedgeTakenCounts(
14037 std::
move(Arg.PredicatedBackedgeTakenCounts)),
14038 BECountUsers(
std::
move(Arg.BECountUsers)),
14039 ConstantEvolutionLoopExitValue(
14040 std::
move(Arg.ConstantEvolutionLoopExitValue)),
14041 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
14042 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
14043 LoopDispositions(
std::
move(Arg.LoopDispositions)),
14044 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
14045 BlockDispositions(
std::
move(Arg.BlockDispositions)),
14046 SCEVUsers(
std::
move(Arg.SCEVUsers)),
14047 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
14048 SignedRanges(
std::
move(Arg.SignedRanges)),
14049 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
14050 UniquePreds(
std::
move(Arg.UniquePreds)),
14051 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
14052 ConstantSCEVs(
std::
move(Arg.ConstantSCEVs)),
14053 LoopUsers(
std::
move(Arg.LoopUsers)),
14054 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
14055 FirstUnknown(Arg.FirstUnknown) {
14056 Arg.FirstUnknown =
nullptr;
14065 Tmp->~SCEVUnknown();
14067 FirstUnknown =
nullptr;
14069 ExprValueMap.clear();
14070 ValueExprMap.clear();
14072 BackedgeTakenCounts.clear();
14073 PredicatedBackedgeTakenCounts.clear();
14075 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
14076 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
14077 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
14078 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
14100 L->getHeader()->printAsOperand(OS,
false);
14104 L->getExitingBlocks(ExitingBlocks);
14105 if (ExitingBlocks.
size() != 1)
14106 OS <<
"<multiple exits> ";
14110 OS <<
"backedge-taken count is ";
14113 OS <<
"Unpredictable backedge-taken count.";
14116 if (ExitingBlocks.
size() > 1)
14117 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14118 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
14126 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
14129 OS <<
"\n Predicates:\n";
14130 for (
const auto *
P : Predicates)
14138 L->getHeader()->printAsOperand(OS,
false);
14143 OS <<
"constant max backedge-taken count is ";
14146 OS <<
", actual taken count either this or zero.";
14148 OS <<
"Unpredictable constant max backedge-taken count. ";
14153 L->getHeader()->printAsOperand(OS,
false);
14158 OS <<
"symbolic max backedge-taken count is ";
14161 OS <<
", actual taken count either this or zero.";
14163 OS <<
"Unpredictable symbolic max backedge-taken count. ";
14167 if (ExitingBlocks.
size() > 1)
14168 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14169 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
14179 OS <<
"\n predicated symbolic max exit count for "
14180 << ExitingBlock->
getName() <<
": ";
14182 OS <<
"\n Predicates:\n";
14183 for (
const auto *
P : Predicates)
14194 L->getHeader()->printAsOperand(OS,
false);
14197 OS <<
"Predicated backedge-taken count is ";
14200 OS <<
"Unpredictable predicated backedge-taken count.";
14202 OS <<
" Predicates:\n";
14203 for (
const auto *
P : Preds)
14208 auto *PredConstantMax =
14210 if (PredConstantMax != ConstantBTC) {
14212 L->getHeader()->printAsOperand(OS,
false);
14215 OS <<
"Predicated constant max backedge-taken count is ";
14218 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14220 OS <<
" Predicates:\n";
14221 for (
const auto *
P : Preds)
14226 auto *PredSymbolicMax =
14228 if (SymbolicBTC != PredSymbolicMax) {
14230 L->getHeader()->printAsOperand(OS,
false);
14233 OS <<
"Predicated symbolic max backedge-taken count is ";
14236 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14238 OS <<
" Predicates:\n";
14239 for (
const auto *
P : Preds)
14245 L->getHeader()->printAsOperand(OS,
false);
14272 OS <<
"Computable";
14282 OS <<
"DoesNotDominate";
14288 OS <<
"ProperlyDominates";
14305 OS <<
"Classifying expressions for: ";
14306 F.printAsOperand(OS,
false);
14321 const Loop *L = LI.getLoopFor(
I.getParent());
14336 OS <<
"\t\t" "Exits: ";
14339 OS <<
"<<Unknown>>";
14345 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14347 Iter->getHeader()->printAsOperand(OS,
false);
14355 InnerL->getHeader()->printAsOperand(OS,
false);
14366 OS <<
"Determining loop execution counts for: ";
14367 F.printAsOperand(OS,
false);
14375 auto &
Values = LoopDispositions[S];
14376 for (
auto &V :
Values) {
14377 if (V.getPointer() == L)
14382 auto &Values2 = LoopDispositions[S];
14384 if (V.getPointer() == L) {
14393ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14411 if (L->contains(AR->
getLoop()) &&
14413 [&](
const SCEV *
Op) { return isLoopUniform(Op, L); }))
14418 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14419 " dominate the contained loop's header?");
14446 bool HasVarying =
false;
14447 bool HasUniform =
false;
14489 auto &
Values = BlockDispositions[S];
14490 for (
auto &V :
Values) {
14491 if (V.getPointer() == BB)
14496 auto &Values2 = BlockDispositions[S];
14498 if (V.getPointer() == BB) {
14507ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14536 bool Proper =
true;
14547 if (Instruction *
I =
14549 if (
I->getParent() == BB)
14551 if (DT.properlyDominates(
I->getParent(), BB))
14574void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14577 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14578 auto It = BECounts.find(L);
14579 if (It != BECounts.end()) {
14580 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14581 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14583 auto UserIt = BECountUsers.find(S);
14584 assert(UserIt != BECountUsers.end());
14589 BECounts.erase(It);
14597 while (!Worklist.
empty()) {
14599 auto Users = SCEVUsers.find(Curr);
14600 if (
Users != SCEVUsers.end())
14601 for (
const auto *User :
Users->second)
14602 if (ToForget.
insert(User).second)
14606 for (
const auto *S : ToForget)
14607 forgetMemoizedResultsImpl(S);
14609 PredicatedSCEVRewrites.remove_if(
14610 [&](
const auto &Entry) {
return ToForget.count(
Entry.first.first); });
14613void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14614 LoopDispositions.erase(S);
14615 BlockDispositions.erase(S);
14616 UnsignedRanges.erase(S);
14617 SignedRanges.erase(S);
14618 HasRecMap.erase(S);
14619 ConstantMultipleCache.erase(S);
14622 UnsignedWrapViaInductionTried.erase(AR);
14623 SignedWrapViaInductionTried.erase(AR);
14626 auto ExprIt = ExprValueMap.find(S);
14627 if (ExprIt != ExprValueMap.end()) {
14628 for (
Value *V : ExprIt->second) {
14629 auto ValueIt = ValueExprMap.find_as(V);
14630 if (ValueIt != ValueExprMap.end())
14631 ValueExprMap.erase(ValueIt);
14633 ExprValueMap.erase(ExprIt);
14636 auto ScopeIt = ValuesAtScopes.find(S);
14637 if (ScopeIt != ValuesAtScopes.end()) {
14638 for (
const auto &Pair : ScopeIt->second)
14641 std::make_pair(Pair.first, S));
14642 ValuesAtScopes.erase(ScopeIt);
14645 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14646 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14647 for (
const auto &Pair : ScopeUserIt->second)
14648 llvm::erase(ValuesAtScopes[Pair.second], std::make_pair(Pair.first, S));
14649 ValuesAtScopesUsers.erase(ScopeUserIt);
14652 auto BEUsersIt = BECountUsers.find(S);
14653 if (BEUsersIt != BECountUsers.end()) {
14655 auto Copy = BEUsersIt->second;
14656 for (
const auto &Pair : Copy)
14657 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14658 BECountUsers.erase(BEUsersIt);
14661 auto FoldUser = FoldCacheUser.find(S);
14662 if (FoldUser != FoldCacheUser.end())
14663 for (
auto &KV : FoldUser->second)
14664 FoldCache.erase(KV);
14665 FoldCacheUser.erase(S);
14669ScalarEvolution::getUsedLoops(
const SCEV *S,
14671 struct FindUsedLoops {
14672 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14673 : LoopsUsed(LoopsUsed) {}
14674 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14675 bool follow(
const SCEV *S) {
14681 bool isDone()
const {
return false; }
14684 FindUsedLoops
F(LoopsUsed);
14685 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14688void ScalarEvolution::getReachableBlocks(
14691 Worklist.
push_back(&F.getEntryBlock());
14692 while (!Worklist.
empty()) {
14694 if (!Reachable.
insert(BB).second)
14702 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14709 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14713 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14748 SCEVMapper SCM(SE2);
14750 SE2.getReachableBlocks(ReachableBlocks, F);
14752 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14770 while (!LoopStack.
empty()) {
14776 if (!ReachableBlocks.
contains(L->getHeader()))
14781 auto It = BackedgeTakenCounts.find(L);
14782 if (It == BackedgeTakenCounts.end())
14786 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14806 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14807 if (Delta && !Delta->
isZero()) {
14808 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14809 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14810 dbgs() <<
"New: " << *NewBECount <<
"\n";
14811 dbgs() <<
"Delta: " << *Delta <<
"\n";
14819 while (!Worklist.
empty()) {
14821 if (ValidLoops.
insert(L).second)
14822 Worklist.
append(L->begin(), L->end());
14824 for (
const auto &KV : ValueExprMap) {
14829 "AddRec references invalid loop");
14834 auto It = ExprValueMap.find(KV.second);
14835 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14836 dbgs() <<
"Value " << *KV.first
14837 <<
" is in ValueExprMap but not in ExprValueMap\n";
14842 if (!ReachableBlocks.
contains(
I->getParent()))
14844 const SCEV *OldSCEV = SCM.visit(KV.second);
14846 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14847 if (Delta && !Delta->
isZero()) {
14848 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14849 <<
"Old: " << *OldSCEV <<
"\n"
14850 <<
"New: " << *NewSCEV <<
"\n"
14851 <<
"Delta: " << *Delta <<
"\n";
14857 for (
const auto &KV : ExprValueMap) {
14858 for (
Value *V : KV.second) {
14859 const SCEV *S = ValueExprMap.lookup(V);
14861 dbgs() <<
"Value " << *V
14862 <<
" is in ExprValueMap but not in ValueExprMap\n";
14865 if (S != KV.first) {
14866 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14867 << *KV.first <<
"\n";
14874 for (
const auto &S : UniqueSCEVs) {
14879 auto It = SCEVUsers.find(
Op);
14880 if (It != SCEVUsers.end() && It->second.count(&S))
14882 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14883 <<
" is not being tracked!\n";
14889 for (
const auto &ValueAndVec : ValuesAtScopes) {
14891 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14892 const Loop *L = LoopAndValueAtScope.first;
14893 const SCEV *ValueAtScope = LoopAndValueAtScope.second;
14895 auto It = ValuesAtScopesUsers.find(ValueAtScope);
14896 if (It != ValuesAtScopesUsers.end() &&
14899 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14900 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14906 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14907 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14908 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14909 const Loop *L = LoopAndValue.first;
14910 const SCEV *
Value = LoopAndValue.second;
14912 auto It = ValuesAtScopes.find(
Value);
14913 if (It != ValuesAtScopes.end() &&
14914 is_contained(It->second, std::make_pair(L, ValueAtScope)))
14916 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14917 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14923 auto VerifyBECountUsers = [&](
bool Predicated) {
14925 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14926 for (
const auto &LoopAndBEInfo : BECounts) {
14927 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
14928 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14930 auto UserIt = BECountUsers.find(S);
14931 if (UserIt != BECountUsers.end() &&
14932 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
14934 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
14935 <<
" missing from BECountUsers\n";
14942 VerifyBECountUsers(
false);
14943 VerifyBECountUsers(
true);
14946 for (
auto &[S,
Values] : LoopDispositions) {
14947 for (
auto [
Loop, CachedDisposition] :
Values) {
14949 if (CachedDisposition != RecomputedDisposition) {
14950 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
14951 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
14952 << RecomputedDisposition <<
"\n";
14959 for (
auto &[S,
Values] : BlockDispositions) {
14960 for (
auto [BB, CachedDisposition] :
Values) {
14962 if (CachedDisposition != RecomputedDisposition) {
14963 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
14964 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
14965 <<
", actual " << RecomputedDisposition <<
"\n";
14972 for (
auto [
FoldID, Expr] : FoldCache) {
14973 auto I = FoldCacheUser.find(Expr);
14974 if (
I == FoldCacheUser.end()) {
14975 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
14980 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
14984 for (
auto [Expr, IDs] : FoldCacheUser) {
14985 for (
auto &
FoldID : IDs) {
14988 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
14993 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
14994 <<
" != " << *Expr <<
"!\n";
15005 for (
auto [S, Multiple] : ConstantMultipleCache) {
15007 if ((Multiple != 0 && RecomputedMultiple != 0 &&
15008 Multiple.
urem(RecomputedMultiple) != 0 &&
15009 RecomputedMultiple.
urem(Multiple) != 0)) {
15010 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
15011 << *S <<
" : Computed " << RecomputedMultiple
15012 <<
" but cache contains " << Multiple <<
"!\n";
15020 FunctionAnalysisManager::Invalidator &Inv) {
15052 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
15053 <<
F.getName() <<
"':\n";
15059 "Scalar Evolution Analysis",
false,
true)
15108 const SCEV *LHS,
const SCEV *RHS) {
15110 assert(LHS->getType() == RHS->getType() &&
15111 "Type mismatch between LHS and RHS");
15114 ID.AddInteger(Pred);
15115 ID.AddPointer(LHS);
15116 ID.AddPointer(RHS);
15117 void *IP =
nullptr;
15118 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(ID, IP))
15122 UniquePreds.InsertNode(Eq, IP);
15133 ID.AddInteger(AddedFlags);
15134 void *IP =
nullptr;
15135 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(ID, IP))
15137 auto *OF =
new (SCEVAllocator)
15139 UniquePreds.InsertNode(OF, IP);
15159 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
15160 return Rewriter.visit(S);
15166 for (
const auto *Pred : U->getPredicates())
15168 if (IPred->getLHS() == Expr &&
15170 return IPred->getRHS();
15172 if (IPred->getLHS() == Expr &&
15173 IPred->getPredicate() == ICmpInst::ICMP_EQ)
15174 return IPred->getRHS();
15177 return convertToAddRecWithPreds(Expr);
15180 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15196 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15213 explicit SCEVPredicateRewriter(
15214 const Loop *L, ScalarEvolution &SE,
15215 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15216 const SCEVPredicate *Pred)
15217 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
15219 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15222 return Pred && Pred->
implies(
P, SE);
15228 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15231 return addOverflowAssumption(
A);
15240 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15244 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15246 if (!PredicatedRewrite)
15248 for (
const auto *
P : PredicatedRewrite->second){
15251 if (L != WP->getExpr()->getLoop())
15254 if (!addOverflowAssumption(
P))
15257 return PredicatedRewrite->first;
15260 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15261 const SCEVPredicate *Pred;
15270 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15277 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15297 if (!Step->
isOne())
15322 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15323 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15336 return Op->LHS == LHS &&
Op->RHS == RHS;
15343 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15345 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15370 const SCEV *Start = AR->getStart();
15371 const SCEV *OpStart =
Op->AR->getStart();
15376 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15385 const SCEV *Step = AR->getStepRecurrence(SE);
15386 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15439 if (Step->getValue()->getValue().isNonNegative())
15443 return ImpliedFlags;
15450 for (
const auto *
P : Preds)
15463 return this->implies(I, SE);
15475 const Loop *L = NWrap->getExpr()->getLoop();
15482 return RewrittenAR &&
15488 for (
const auto *Pred : Preds)
15489 Pred->print(OS,
Depth);
15494 for (
const auto *Pred : Set->Preds)
15502 bool CheckImplies = Preds.
size() < 16;
15505 if (CheckImplies &&
implies(
N, SE))
15511 for (
auto *
P : Preds) {
15512 if (CheckImplies &&
N->implies(
P, SE))
15516 Preds = std::move(PrunedPreds);
15517 Preds.push_back(
N);
15524 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15529 for (
const auto *
Op :
Ops)
15534 SCEVUsers[
Op].insert(
User);
15543 SCEVUsers[
Op].insert(
User);
15547 const SCEV *Expr = SE.getSCEV(V);
15552 RewriteEntry &Entry = RewriteMap[Expr];
15555 if (Entry.second && Generation == Entry.first)
15556 return Entry.second;
15561 Expr = Entry.second;
15563 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15564 Entry = {Generation, NewSCEV};
15570 if (!BackedgeCount) {
15572 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15573 for (
const auto *
P : Preds)
15576 return BackedgeCount;
15580 if (!SymbolicMaxBackedgeCount) {
15582 SymbolicMaxBackedgeCount =
15583 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15584 for (
const auto *
P : Preds)
15587 return SymbolicMaxBackedgeCount;
15591 if (!SmallConstantMaxTripCount) {
15593 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15594 for (
const auto *
P : Preds)
15597 return *SmallConstantMaxTripCount;
15601 if (Preds->implies(&Pred, SE))
15606 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15607 updateGeneration();
15620void PredicatedScalarEvolution::updateGeneration() {
15622 if (++Generation == 0) {
15623 for (
auto &
II : RewriteMap) {
15624 const SCEV *Rewritten =
II.second.second;
15646 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15652 ExtraPreds->
append(NewPreds);
15658 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15664 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15667 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {}
15671 for (
auto *BB : L.getBlocks())
15672 for (
auto &
I : *BB) {
15673 if (!SE.isSCEVable(
I.getType()))
15676 auto *Expr = SE.getSCEV(&
I);
15677 auto II = RewriteMap.find(Expr);
15679 if (
II == RewriteMap.end())
15683 if (
II->second.second == Expr)
15688 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15696 LoopGuards Guards(SE);
15704void ScalarEvolution::LoopGuards::collectFromPHI(
15712 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15713 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15727 auto &RewriteMap =
G->second.RewriteMap;
15728 if (RewriteMap.empty())
15730 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15731 if (S == RewriteMap.end())
15737 return {C0, SM->getSCEVType()};
15740 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15741 MinMaxPattern
P2) -> MinMaxPattern {
15742 auto [C1,
T1] =
P1;
15743 auto [C2, T2] =
P2;
15744 if (!C1 || !C2 ||
T1 != T2)
15748 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15750 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15752 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15754 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15759 auto P = GetMinMaxConst(0);
15760 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15763 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15766 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15769 Guards.RewriteMap.insert({
LHS,
RHS});
15777 const APInt &DivisorVal,
15779 const APInt *ExprVal;
15792 const APInt &DivisorVal,
15794 const APInt *ExprVal;
15802 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15816 const SCEV *URemRHS =
nullptr;
15820 const SCEV *Multiple =
15822 DivInfo[URemLHS] = Multiple;
15824 Multiples[URemLHS] =
C->getAPInt();
15844 auto IsMinMaxSCEVWithNonNegativeConstant =
15848 if (
MinMax->getNumOperands() != 2)
15851 if (
C->getAPInt().isNegative())
15853 SCTy =
MinMax->getSCEVType();
15862 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15864 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15869 auto *DivisibleExpr =
15877void ScalarEvolution::LoopGuards::collectFromBlock(
15879 const BasicBlock *
Block,
const BasicBlock *Pred,
15887 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
15898 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15900 if (From == FromRewritten)
15902 RewriteMap[From] = To;
15908 auto GetMaybeRewritten = [&](
const SCEV *S) {
15909 return RewriteMap.lookup_or(S, S);
15916 const SCEV *MatchLHS,
15917 const SCEV *MatchRHS) {
15918 const SCEVConstant *C1;
15921 if (!
match(MatchLHS,
15933 const SCEV *RewrittenLHS = GetMaybeRewritten(LHSUnknown);
15934 ExactRegion = ExactRegion.intersectWith(SE.
getUnsignedRange(RewrittenLHS),
15939 if (ExactRegion.isEmptySet() || ExactRegion.isWrappedSet() ||
15940 ExactRegion.isFullSet())
15943 const SCEV *RegionMin = SE.
getConstant(ExactRegion.getUnsignedMin());
15944 const SCEV *RegionMax = SE.
getConstant(ExactRegion.getUnsignedMax());
15945 const SCEV *ClampedLHS =
15947 AddRewrite(LHSUnknown, RewrittenLHS, ClampedLHS);
15950 if (MatchRangeCheckIdiom(Predicate,
LHS,
RHS))
15963 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
15965 const APInt &DividesBy =
15980 switch (Predicate) {
16009 SmallPtrSet<const SCEV *, 16> Visited;
16011 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
16015 while (!Worklist.
empty()) {
16019 if (!Visited.
insert(From).second)
16021 const SCEV *FromRewritten = GetMaybeRewritten(From);
16022 const SCEV *To =
nullptr;
16024 switch (Predicate) {
16029 EnqueueOperands(
UMax);
16035 EnqueueOperands(
SMax);
16041 EnqueueOperands(
UMin);
16047 EnqueueOperands(
SMin);
16055 const SCEV *OneAlignedUp =
16057 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
16069 const SCEVConstant *
C;
16078 Guards.NotEqual.insert({
LHS,
RHS});
16087 AddRewrite(From, FromRewritten, To);
16104 SE.F.
getParent(), Intrinsic::experimental_guard);
16106 for (
const auto *GU : GuardDecl->users())
16108 if (Guard->getFunction() ==
Block->getParent() &&
16117 unsigned NumCollectedConditions = 0;
16119 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
16121 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
16123 const CondBrInst *LoopEntryPredicate =
16125 if (!LoopEntryPredicate)
16130 NumCollectedConditions++;
16134 if (
Depth > 0 && NumCollectedConditions == 2)
16142 if (Pair.second->hasNPredecessorsOrMore(2) &&
16144 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
16145 for (
auto &Phi : Pair.second->phis())
16156 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
16157 SmallVector<Value *, 8> Worklist;
16158 SmallPtrSet<Value *, 8> Visited;
16160 while (!Worklist.
empty()) {
16167 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
16191 DenseMap<const SCEV *, APInt> Multiples;
16193 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
16200 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
16201 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
16205 for (
const auto &[K, Divisor] : Multiples) {
16206 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
16207 Guards.RewriteMap[
K] =
16209 Guards.
rewrite(K), Divisor, SE),
16218 Guards.PreserveNUW =
true;
16219 Guards.PreserveNSW =
true;
16220 for (
const SCEV *Expr : ExprsToRewrite) {
16221 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16222 Guards.PreserveNUW &=
16224 Guards.PreserveNSW &=
16231 if (ExprsToRewrite.size() > 1) {
16232 for (
const SCEV *Expr : ExprsToRewrite) {
16233 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16234 Guards.RewriteMap.erase(Expr);
16235 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
16244 class SCEVLoopGuardRewriter
16255 NotEqual(Guards.NotEqual) {
16256 if (Guards.PreserveNUW)
16258 if (Guards.PreserveNSW)
16265 return Map.lookup_or(Expr, Expr);
16269 if (
const SCEV *S = Map.lookup(Expr))
16276 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16277 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16278 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16280 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16281 if (
const SCEV *S = Map.lookup(NarrowExt))
16282 return SE.getZeroExtendExpr(S, Ty);
16283 Bitwidth = Bitwidth / 2;
16291 if (
const SCEV *S = Map.lookup(Expr))
16298 if (
const SCEV *S = Map.lookup(Expr))
16304 if (
const SCEV *S = Map.lookup(Expr))
16310 if (
const SCEV *S = Map.lookup(Expr))
16315 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16320 if (NotEqual.contains({LHS, RHS})) {
16322 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16323 return SE.getUMaxExpr(OneAlignedUp, S);
16330 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16341 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16342 return SE.getAddExpr(
16345 if (
const SCEV *S = Map.lookup(
Add))
16346 return SE.getAddExpr(Expr->
getOperand(0), S);
16354 const SCEV *S =
nullptr;
16361 S = Map.lookup(SE.getAddExpr(NewC, Expr->
getOperand(1)));
16364 return SE.getAddExpr(S, SE.getMinusOne(Expr->
getType()));
16399 if (RewriteMap.empty() && NotEqual.empty())
16402 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16403 return Rewriter.visit(Expr);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Expand Atomic instructions
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
SmallPtrSet< const BasicBlock *, 8 > VisitedBlocks
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
static bool isSigned(unsigned Opcode)
This file defines a hash set that can be used to remove duplication of nodes in a graph.
Value * getPointer(Value *Ptr)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
This defines the Use class.
iv Induction Variable Users
static constexpr Value * getValue(Ty &ValueOrUse)
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
PowerPC Reduce CR logical Operation
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
const SmallVectorImpl< MachineOperand > & Cond
static DominatorTree getDomTree(Function &F)
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
SI optimize exec mask operations pre RA
static void visit(BasicBlock &Start, std::function< bool(BasicBlock *)> op)
This file provides utility classes that use RAII to save and restore values.
bool SCEVMinMaxExprContains(const SCEV *Root, const SCEV *OperandToFind, SCEVTypes RootKind)
static cl::opt< unsigned > MaxAddRecSize("scalar-evolution-max-add-rec-size", cl::Hidden, cl::desc("Max coefficients in AddRec during evolving"), cl::init(8))
static cl::opt< unsigned > RangeIterThreshold("scev-range-iter-threshold", cl::Hidden, cl::desc("Threshold for switching to iteratively computing SCEV ranges"), cl::init(32))
static const Loop * isIntegerLoopHeaderPHI(const PHINode *PN, LoopInfo &LI)
static unsigned getConstantTripCount(const SCEVConstant *ExitCount)
static int CompareValueComplexity(const LoopInfo *const LI, Value *LV, Value *RV, unsigned Depth)
Compare the two values LV and RV in terms of their "complexity" where "complexity" is a partial (and ...
static const SCEV * getNextSCEVDivisibleByDivisor(const SCEV *Expr, const APInt &DivisorVal, ScalarEvolution &SE)
static void PushLoopPHIs(const Loop *L, SmallVectorImpl< Instruction * > &Worklist, SmallPtrSetImpl< Instruction * > &Visited)
Push PHI nodes in the header of the given loop onto the given Worklist.
static void insertFoldCacheEntry(const ScalarEvolution::FoldID &ID, const SCEV *S, DenseMap< ScalarEvolution::FoldID, const SCEV * > &FoldCache, DenseMap< const SCEV *, SmallVector< ScalarEvolution::FoldID, 2 > > &FoldCacheUser)
static cl::opt< bool > ClassifyExpressions("scalar-evolution-classify-expressions", cl::Hidden, cl::init(true), cl::desc("When printing analysis, include information on every instruction"))
static bool hasHugeExpression(ArrayRef< SCEVUse > Ops)
Returns true if Ops contains a huge SCEV (the subtree of S contains at least HugeExprThreshold nodes)...
static bool CanConstantFold(const Instruction *I)
Return true if we can constant fold an instruction of the specified type, assuming that all operands ...
static cl::opt< unsigned > AddOpsInlineThreshold("scev-addops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining addition operands into a SCEV"), cl::init(500))
static cl::opt< unsigned > MaxLoopGuardCollectionDepth("scalar-evolution-max-loop-guard-collection-depth", cl::Hidden, cl::desc("Maximum depth for recursive loop guard collection"), cl::init(1))
static cl::opt< bool > VerifyIR("scev-verify-ir", cl::Hidden, cl::desc("Verify IR correctness when making sensitive SCEV queries (slow)"), cl::init(false))
static bool RangeRefPHIAllowedOperands(DominatorTree &DT, PHINode *PHI)
static std::optional< APInt > MinOptional(std::optional< APInt > X, std::optional< APInt > Y)
Helper function to compare optional APInts: (a) if X and Y both exist, return min(X,...
static cl::opt< unsigned > MulOpsInlineThreshold("scev-mulops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining multiplication operands into a SCEV"), cl::init(32))
static BinaryOperator * getCommonInstForPHI(PHINode *PN)
static bool isDivisibilityGuard(const SCEV *LHS, const SCEV *RHS, ScalarEvolution &SE)
static std::optional< const SCEV * > createNodeForSelectViaUMinSeq(ScalarEvolution *SE, const SCEV *CondExpr, const SCEV *TrueExpr, const SCEV *FalseExpr)
static Constant * BuildConstantFromSCEV(const SCEV *V)
This builds up a Constant using the ConstantExpr interface.
static ConstantInt * EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C, ScalarEvolution &SE)
static const SCEV * BinomialCoefficient(const SCEV *It, unsigned K, ScalarEvolution &SE, Type *ResultTy)
Compute BC(It, K). The result has width W. Assume, K > 0.
static cl::opt< unsigned > MaxCastDepth("scalar-evolution-max-cast-depth", cl::Hidden, cl::desc("Maximum depth of recursive SExt/ZExt/Trunc"), cl::init(8))
static bool IsMinMaxConsistingOf(const SCEV *MaybeMinMaxExpr, const SCEV *Candidate)
Is MaybeMinMaxExpr an (U|S)(Min|Max) of Candidate and some other values?
static PHINode * getConstantEvolvingPHI(Value *V, const Loop *L)
getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node in the loop that V is deri...
static const SCEV * SolveLinEquationWithOverflow(const APInt &A, const SCEV *B, SmallVectorImpl< const SCEVPredicate * > *Predicates, ScalarEvolution &SE, const Loop *L)
Finds the minimum unsigned root of the following equation:
static cl::opt< unsigned > MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden, cl::desc("Maximum number of iterations SCEV will " "symbolically execute a constant " "derived loop"), cl::init(100))
static uint64_t umul_ov(uint64_t i, uint64_t j, bool &Overflow)
static void PrintSCEVWithTypeHint(raw_ostream &OS, const SCEV *S)
When printing a top-level SCEV for trip counts, it's helpful to include a type for constants which ar...
static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE, const Loop *L)
static SCEV::NoWrapFlags StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type, ArrayRef< SCEVUse > Ops, SCEV::NoWrapFlags Flags)
static bool containsConstantInAddMulChain(const SCEV *StartExpr)
Determine if any of the operands in this SCEV are a constant or if any of the add or multiply express...
static const SCEV * getExtendAddRecStart(const SCEVAddRecExpr *AR, Type *Ty, ScalarEvolution *SE, unsigned Depth)
static bool CollectAddOperandsWithScales(SmallDenseMap< SCEVUse, APInt, 16 > &M, SmallVectorImpl< SCEVUse > &NewOps, APInt &AccumulatedConstant, ArrayRef< SCEVUse > Ops, const APInt &Scale, ScalarEvolution &SE)
Process the given Ops list, which is a list of operands to be added under the given scale,...
static const SCEV * constantFoldAndGroupOps(ScalarEvolution &SE, LoopInfo &LI, DominatorTree &DT, SmallVectorImpl< SCEVUse > &Ops, FoldT Fold, IsIdentityT IsIdentity, IsAbsorberT IsAbsorber)
Performs a number of common optimizations on the passed Ops.
static bool IsKnownPredicateViaAddRecStart(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
static const SCEV * getPreStartForExtend(const SCEVAddRecExpr *AR, ScalarEvolution *SE, unsigned Depth)
static void GroupByComplexity(SmallVectorImpl< SCEVUse > &Ops, LoopInfo *LI, DominatorTree &DT)
Given a list of SCEV objects, order them by their complexity, and group objects of the same complexit...
static bool collectDivisibilityInformation(ICmpInst::Predicate Predicate, const SCEV *LHS, const SCEV *RHS, DenseMap< const SCEV *, const SCEV * > &DivInfo, DenseMap< const SCEV *, APInt > &Multiples, ScalarEvolution &SE)
static cl::opt< unsigned > MaxSCEVOperationsImplicationDepth("scalar-evolution-max-scev-operations-implication-depth", cl::Hidden, cl::desc("Maximum depth of recursive SCEV operations implication analysis"), cl::init(2))
static void PushDefUseChildren(Instruction *I, SmallVectorImpl< Instruction * > &Worklist, SmallPtrSetImpl< Instruction * > &Visited)
Push users of the given Instruction onto the given Worklist.
static std::optional< APInt > SolveQuadraticAddRecRange(const SCEVAddRecExpr *AddRec, const ConstantRange &Range, ScalarEvolution &SE)
Let c(n) be the value of the quadratic chrec {0,+,M,+,N} after n iterations.
static cl::opt< bool > UseContextForNoWrapFlagInference("scalar-evolution-use-context-for-no-wrap-flag-strenghening", cl::Hidden, cl::desc("Infer nuw/nsw flags using context where suitable"), cl::init(true))
static cl::opt< bool > EnableFiniteLoopControl("scalar-evolution-finite-loop", cl::Hidden, cl::desc("Handle <= and >= in finite loops"), cl::init(true))
static bool getOperandsForSelectLikePHI(DominatorTree &DT, PHINode *PN, Value *&Cond, Value *&LHS, Value *&RHS)
static std::optional< std::tuple< APInt, APInt, APInt, APInt, unsigned > > GetQuadraticEquation(const SCEVAddRecExpr *AddRec)
For a given quadratic addrec, generate coefficients of the corresponding quadratic equation,...
static bool isKnownPredicateExtendIdiom(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
static std::optional< BinaryOp > MatchBinaryOp(Value *V, const DataLayout &DL, AssumptionCache &AC, const DominatorTree &DT, const Instruction *CxtI)
Try to map V into a BinaryOp, and return std::nullopt on failure.
static std::optional< APInt > SolveQuadraticAddRecExact(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE)
Let c(n) be the value of the quadratic chrec {L,+,M,+,N} after n iterations.
static std::optional< APInt > TruncIfPossible(std::optional< APInt > X, unsigned BitWidth)
Helper function to truncate an optional APInt to a given BitWidth.
static cl::opt< unsigned > MaxSCEVCompareDepth("scalar-evolution-max-scev-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive SCEV complexity comparisons"), cl::init(32))
static APInt extractConstantWithoutWrapping(ScalarEvolution &SE, const SCEVConstant *ConstantTerm, const SCEVAddExpr *WholeAddExpr)
static cl::opt< unsigned > MaxConstantEvolvingDepth("scalar-evolution-max-constant-evolving-depth", cl::Hidden, cl::desc("Maximum depth of recursive constant evolving"), cl::init(32))
static bool MatchBinarySub(const SCEV *S, SCEVUse &LHS, SCEVUse &RHS)
static std::optional< ConstantRange > GetRangeFromMetadata(Value *V)
Helper method to assign a range to V from metadata present in the IR.
static cl::opt< unsigned > HugeExprThreshold("scalar-evolution-huge-expr-threshold", cl::Hidden, cl::desc("Size of the expression which is considered huge"), cl::init(4096))
static Type * isSimpleCastedPHI(const SCEV *Op, const SCEVUnknown *SymbolicPHI, bool &Signed, ScalarEvolution &SE)
Helper function to createAddRecFromPHIWithCasts.
static Constant * EvaluateExpression(Value *V, const Loop *L, DenseMap< Instruction *, Constant * > &Vals, const DataLayout &DL, const TargetLibraryInfo *TLI)
EvaluateExpression - Given an expression that passes the getConstantEvolvingPHI predicate,...
static const SCEV * getPreviousSCEVDivisibleByDivisor(const SCEV *Expr, const APInt &DivisorVal, ScalarEvolution &SE)
static const SCEV * MatchNotExpr(const SCEV *Expr)
If Expr computes ~A, return A else return nullptr.
static std::pair< ConstantRange, bool > getRangeForAffineARHelper(APInt Step, const ConstantRange &StartRange, const APInt &MaxBECount, bool Signed)
static cl::opt< unsigned > MaxValueCompareDepth("scalar-evolution-max-value-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive value complexity comparisons"), cl::init(2))
static const SCEV * applyDivisibilityOnMinMaxExpr(const SCEV *MinMaxExpr, APInt Divisor, ScalarEvolution &SE)
static cl::opt< bool, true > VerifySCEVOpt("verify-scev", cl::Hidden, cl::location(VerifySCEV), cl::desc("Verify ScalarEvolution's backedge taken counts (slow)"))
static const SCEV * getSignedOverflowLimitForStep(const SCEV *Step, ICmpInst::Predicate *Pred, ScalarEvolution *SE)
static cl::opt< unsigned > MaxArithDepth("scalar-evolution-max-arith-depth", cl::Hidden, cl::desc("Maximum depth of recursive arithmetics"), cl::init(32))
static bool HasSameValue(const SCEV *A, const SCEV *B)
SCEV structural equivalence is usually sufficient for testing whether two expressions are equal,...
static uint64_t Choose(uint64_t n, uint64_t k, bool &Overflow)
Compute the result of "n choose k", the binomial coefficient.
static std::optional< int > CompareSCEVComplexity(const LoopInfo *const LI, const SCEV *LHS, const SCEV *RHS, DominatorTree &DT, unsigned Depth=0)
static bool canConstantEvolve(Instruction *I, const Loop *L)
Determine whether this instruction can constant evolve within this loop assuming its operands can all...
static PHINode * getConstantEvolvingPHIOperands(Instruction *UseInst, const Loop *L, DenseMap< Instruction *, PHINode * > &PHIMap, unsigned Depth)
getConstantEvolvingPHIOperands - Implement getConstantEvolvingPHI by recursing through each instructi...
static bool scevUnconditionallyPropagatesPoisonFromOperands(SCEVTypes Kind)
static cl::opt< bool > VerifySCEVStrict("verify-scev-strict", cl::Hidden, cl::desc("Enable stricter verification with -verify-scev is passed"))
static Constant * getOtherIncomingValue(PHINode *PN, BasicBlock *BB)
static cl::opt< bool > UseExpensiveRangeSharpening("scalar-evolution-use-expensive-range-sharpening", cl::Hidden, cl::init(false), cl::desc("Use more powerful methods of sharpening expression ranges. May " "be costly in terms of compile time"))
static const SCEV * getUnsignedOverflowLimitForStep(const SCEV *Step, ICmpInst::Predicate *Pred, ScalarEvolution *SE)
static bool IsKnownPredicateViaMinOrMax(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Is LHS Pred RHS true on the virtue of LHS or RHS being a Min or Max expression?
static bool BrPHIToSelect(DominatorTree &DT, CondBrInst *BI, PHINode *Merge, Value *&C, Value *&LHS, Value *&RHS)
This file defines the scope_exit class, which executes user-defined cleanup logic at scope exit.
static bool InBlock(const Value *V, const BasicBlock *BB)
Provides some synthesis utilities to produce sequences of values.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
static SymbolRef::Type getType(const Symbol *Sym)
LocallyHashedType DenseMapInfo< LocallyHashedType >::Empty
static std::optional< bool > isImpliedCondOperands(CmpInst::Predicate Pred, const Value *ALHS, const Value *ARHS, const Value *BLHS, const Value *BRHS)
Return true if "icmp Pred BLHS BRHS" is true whenever "icmp PredALHS ARHS" is true.
Virtual Register Rewriter
static const uint32_t IV[8]
SCEVCastSinkingRewriter(ScalarEvolution &SE, Type *TargetTy, ConversionFn CreatePtrCast)
static const SCEV * rewrite(const SCEV *Scev, ScalarEvolution &SE, Type *TargetTy, ConversionFn CreatePtrCast)
const SCEV * visitUnknown(const SCEVUnknown *Expr)
const SCEV * visitAddExpr(const SCEVAddExpr *Expr)
const SCEV * visit(const SCEV *S)
Class for arbitrary precision integers.
LLVM_ABI APInt umul_ov(const APInt &RHS, bool &Overflow) const
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
bool isMinSignedValue() const
Determine if this is the smallest signed value.
uint64_t getZExtValue() const
Get zero extended value.
unsigned getActiveBits() const
Compute the number of active bits in the value.
LLVM_ABI APInt trunc(unsigned width) const
Truncate to new width.
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
APInt abs() const
Get the absolute value.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool isSignMask() const
Check if the APInt's value is returned by getSignMask.
LLVM_ABI APInt urem(const APInt &RHS) const
Unsigned remainder operation.
unsigned getBitWidth() const
Return the number of bits in the APInt.
bool ult(const APInt &RHS) const
Unsigned less than comparison.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
bool isNegative() const
Determine sign of this APInt.
bool sle(const APInt &RHS) const
Signed less or equal comparison.
LLVM_ABI APInt uadd_ov(const APInt &RHS, bool &Overflow) const
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
bool isNonPositive() const
Determine if this APInt Value is non-positive (<= 0).
unsigned countTrailingZeros() const
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
unsigned logBase2() const
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
LLVM_ABI APInt multiplicativeInverse() const
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
LLVM_ABI APInt sext(unsigned width) const
Sign extend to a new width.
APInt shl(unsigned shiftAmt) const
Left-shift function.
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
bool isSignBitSet() const
Determine if sign bit of this APInt is set.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
bool isIntN(unsigned N) const
Check if this APInt has an N-bits unsigned integer value.
bool sge(const APInt &RHS) const
Signed greater or equal comparison.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
This templated class represents "all analyses that operate over <aparticular IR unit>" (e....
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
AnalysisUsage & addRequiredTransitive()
Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
Get the array size.
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
MutableArrayRef< WeakVH > assumptions()
Access the list of assumption handles currently tracked for this function.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
const Function * getParent() const
Return the enclosing method, or null if none.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
LLVM_ABI unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
LLVM_ABI Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
BinaryOps getOpcode() const
This class represents a function call, abstracting a target machine's calling convention.
virtual void deleted()
Callback for Value destruction.
bool isFalseWhenEqual() const
This is just a convenience.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ ICMP_SLE
signed less or equal
@ ICMP_UGE
unsigned greater or equal
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
@ ICMP_SGE
signed greater or equal
@ ICMP_ULE
unsigned less or equal
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
bool isTrueWhenEqual() const
This is just a convenience.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
static LLVM_ABI std::optional< CmpPredicate > getMatching(CmpPredicate A, CmpPredicate B)
Compares two CmpPredicates taking samesign into account and returns the canonicalized CmpPredicate if...
LLVM_ABI CmpInst::Predicate getPreferredSignedPredicate() const
Attempts to return a signed CmpInst::Predicate from the CmpPredicate.
CmpInst::Predicate dropSameSign() const
Drops samesign information.
Conditional Branch instruction.
Value * getCondition() const
BasicBlock * getSuccessor(unsigned i) const
static LLVM_ABI Constant * getNot(Constant *C)
static Constant * getPtrAdd(Constant *Ptr, Constant *Offset, GEPNoWrapFlags NW=GEPNoWrapFlags::none(), std::optional< ConstantRange > InRange=std::nullopt, Type *OnlyIfReduced=nullptr)
Create a getelementptr i8, ptr, offset constant expression.
static LLVM_ABI Constant * getPtrToAddr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static LLVM_ABI Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
static LLVM_ABI Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
This is the shared class of boolean and integer constants.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
static LLVM_ABI ConstantInt * getBool(LLVMContext &Context, bool V)
This class represents a range of values.
LLVM_ABI ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
LLVM_ABI ConstantRange zextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
PreferredRangeType
If represented precisely, the result of some range operations may consist of multiple disjoint ranges...
LLVM_ABI bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
const APInt & getLower() const
Return the lower value for this range.
LLVM_ABI ConstantRange urem(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned remainder operation of...
LLVM_ABI bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type.
LLVM_ABI bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const
Does the predicate Pred hold between ranges this and Other?
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI ConstantRange zeroExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
LLVM_ABI bool isSignWrappedSet() const
Return true if this set wraps around the signed domain.
LLVM_ABI APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
LLVM_ABI bool isWrappedSet() const
Return true if this set wraps around the unsigned domain.
LLVM_ABI void print(raw_ostream &OS) const
Print out the bounds to a stream.
LLVM_ABI ConstantRange truncate(uint32_t BitWidth, unsigned NoWrapKind=0) const
Return a new range in the specified integer type, which must be strictly smaller than the current typ...
LLVM_ABI ConstantRange signExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
const APInt & getUpper() const
Return the upper value for this range.
LLVM_ABI ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
static LLVM_ABI ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
LLVM_ABI bool contains(const APInt &Val) const
Return true if the specified value is in the set.
LLVM_ABI APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
LLVM_ABI ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
LLVM_ABI APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
static LLVM_ABI ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind)
Produce the largest range containing all X such that "X BinOp Y" is guaranteed not to wrap (overflow)...
LLVM_ABI unsigned getMinSignedBits() const
Compute the maximal number of bits needed to represent every value in this signed range.
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
LLVM_ABI ConstantRange sub(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a subtraction of a value in this r...
LLVM_ABI ConstantRange sextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
static LLVM_ABI ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp, const APInt &Other, unsigned NoWrapKind)
Produce the range that contains X if and only if "X BinOp Other" does not wrap.
This is an important base class in LLVM.
A parsed version of the target data layout string in and methods for querying it.
LLVM_ABI const StructLayout * getStructLayout(StructType *Ty) const
Returns a StructLayout object, indicating the alignment of the struct, its size, and the offsets of i...
LLVM_ABI unsigned getIndexTypeSizeInBits(Type *Ty) const
The size in bits of the index used in GEP calculation for this type.
LLVM_ABI IntegerType * getIndexType(LLVMContext &C, unsigned AddressSpace) const
Returns the type of a GEP index in AddressSpace.
TypeSize getTypeSizeInBits(Type *Ty) const
Size examples:
ValueT lookup(const_arg_type_t< KeyT > Val) const
Return the entry for the specified key, or a default constructed value if no such entry exists.
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
iterator find_as(const LookupKeyT &Val)
Alternate version of find() which allows a different, and possibly less expensive,...
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Analysis pass which computes a DominatorTree.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
LLVM_ABI bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
This class describes a reference to an interned FoldingSetNodeID, which can be a useful to store node...
This class is used to gather all the unique data bits of a node.
void AddInteger(signed I)
Represents flags for the getelementptr instruction/expression.
bool hasNoUnsignedSignedWrap() const
bool hasNoUnsignedWrap() const
static GEPNoWrapFlags none()
static LLVM_ABI Type * getTypeAtIndex(Type *Ty, Value *Idx)
Return the type of the element at the given index of an indexable type.
Module * getParent()
Get the module that this global value is contained inside of...
static bool isPrivateLinkage(LinkageTypes Linkage)
static bool isInternalLinkage(LinkageTypes Linkage)
This instruction compares its operands according to the predicate given to the constructor.
CmpPredicate getCmpPredicate() const
static bool isGE(Predicate P)
Return true if the predicate is SGE or UGE.
CmpPredicate getSwappedCmpPredicate() const
static LLVM_ABI bool compare(const APInt &LHS, const APInt &RHS, ICmpInst::Predicate Pred)
Return result of LHS Pred RHS comparison.
static bool isLT(Predicate P)
Return true if the predicate is SLT or ULT.
CmpPredicate getInverseCmpPredicate() const
Predicate getNonStrictCmpPredicate() const
For example, SGT -> SGE, SLT -> SLE, ULT -> ULE, UGT -> UGE.
static bool isGT(Predicate P)
Return true if the predicate is SGT or UGT.
Predicate getFlippedSignednessPredicate() const
For example, SLT->ULT, ULT->SLT, SLE->ULE, ULE->SLE, EQ->EQ.
static CmpPredicate getInverseCmpPredicate(CmpPredicate Pred)
bool isEquality() const
Return true if this predicate is either EQ or NE.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
static bool isLE(Predicate P)
Return true if the predicate is SLE or ULE.
LLVM_ABI bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
LLVM_ABI bool hasNoSignedWrap() const LLVM_READONLY
Determine whether the no signed wrap flag is set.
LLVM_ABI bool isIdenticalToWhenDefined(const Instruction *I, bool IntersectAttrs=false) const LLVM_READONLY
This is like isIdenticalTo, except that it ignores the SubclassOptionalData flags,...
Class to represent integer types.
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
A helper class to return the specified delimiter string after the first invocation of operator String...
An instruction for reading from memory.
Analysis pass that exposes the LoopInfo for a function.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within this loop.
BlockT * getHeader() const
unsigned getLoopDepth() const
Return the nesting level of this loop.
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
Represents a single loop in the control flow graph.
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
A Module instance is used to store all the information related to an LLVM module.
unsigned getOpcode() const
Return the opcode for this Instruction or ConstantExpr.
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
bool hasNoSignedWrap() const
Test whether this operation is known to never undergo signed overflow, aka the nsw property.
bool hasNoUnsignedWrap() const
Test whether this operation is known to never undergo unsigned overflow, aka the nuw property.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
PointerIntPair - This class implements a pair of a pointer and small integer.
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
LLVM_ABI void addPredicate(const SCEVPredicate &Pred)
Adds a new predicate.
LLVM_ABI const SCEVPredicate & getPredicate() const
LLVM_ABI const SCEV * getPredicatedSCEV(const SCEV *Expr)
Returns the rewritten SCEV for Expr in the context of the current SCEV predicate.
LLVM_ABI bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2, ArrayRef< const SCEVPredicate * > ExtraPreds={}) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds and ExtraPreds.
LLVM_ABI bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Returns true if we've statically proved that V doesn't wrap.
LLVM_ABI const SCEVAddRecExpr * getAsAddRec(Value *V, SmallVectorImpl< const SCEVPredicate * > *WrapPredsAdded=nullptr)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
LLVM_ABI void print(raw_ostream &OS, unsigned Depth) const
Print the SCEV mappings done by the Predicated Scalar Evolution.
LLVM_ABI PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L)
LLVM_ABI unsigned getSmallConstantMaxTripCount()
Returns the upper bound of the loop trip count as a normal unsigned value, or 0 if the trip count is ...
LLVM_ABI void addPredicates(ArrayRef< const SCEVPredicate * > Preds)
Adds all predicates in Preds.
LLVM_ABI const SCEV * getBackedgeTakenCount()
Get the (predicated) backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSymbolicMaxBackedgeTakenCount()
Get the (predicated) symbolic max backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
constexpr bool isValid() const
This node represents an addition of some number of SCEVs.
This node represents a polynomial recurrence on the trip count of the specified loop.
friend class ScalarEvolution
LLVM_ABI const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
void setNoWrapFlags(NoWrapFlags Flags)
Set flags for a recurrence without clearing any previously set flags.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
bool isQuadratic() const
Return true if this represents an expression A + B*x + C*x^2 where A, B and C are loop invariant valu...
LLVM_ABI const SCEV * getNumIterationsInRange(const ConstantRange &Range, ScalarEvolution &SE) const
Return the number of iterations of this loop that produce values in the specified constant range.
LLVM_ABI const SCEVAddRecExpr * getPostIncExpr(ScalarEvolution &SE) const
Return an expression representing the value of this expression one iteration of the loop ahead.
const Loop * getLoop() const
SCEVUse getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
This is the base class for unary cast operator classes.
SCEVUse getOperand() const
LLVM_ABI SCEVCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, SCEVUse op, Type *ty)
void setNoWrapFlags(NoWrapFlags Flags)
Set flags for a non-recurrence without clearing previously set flags.
This class represents an assumption that the expression LHS Pred RHS evaluates to true,...
SCEVComparePredicate(const FoldingSetNodeIDRef ID, const ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Implementation of the SCEVPredicate interface.
This class represents a constant integer value.
ConstantInt * getValue() const
const APInt & getAPInt() const
This is the base class for unary integral cast operator classes.
LLVM_ABI SCEVIntegralCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, SCEVUse op, Type *ty)
This node is the base class min/max selections.
static enum SCEVTypes negate(enum SCEVTypes T)
This node represents multiplication of some number of SCEVs.
This node is a base class providing common functionality for n'ary operators.
bool hasNoUnsignedWrap() const
ArrayRef< SCEVUse > operands() const
bool hasNoSelfWrap() const
size_t getNumOperands() const
bool hasNoSignedWrap() const
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
SCEVUse getOperand(unsigned i) const
This class represents an assumption made using SCEV expressions which can be checked at run-time.
SCEVPredicate(const SCEVPredicate &)=default
virtual bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const =0
Returns true if this predicate implies N.
This class represents a cast from a pointer to a pointer-sized integer value, without capturing the p...
This visitor recursively visits a SCEV expression and re-writes it.
const SCEV * visitSignExtendExpr(const SCEVSignExtendExpr *Expr)
const SCEV * visit(const SCEV *S)
const SCEV * visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr)
const SCEV * visitSMinExpr(const SCEVSMinExpr *Expr)
SCEVRewriteVisitor(ScalarEvolution &SE)
const SCEV * visitUMinExpr(const SCEVUMinExpr *Expr)
This class represents a signed minimum selection.
This node is the base class for sequential/in-order min/max selections.
static SCEVTypes getEquivalentNonSequentialSCEVType(SCEVTypes Ty)
This class represents a sign extension of a small integer value to a larger integer value.
Visit all nodes in the expression tree using worklist traversal.
This class represents a truncation of an integer value to a smaller integer value.
This class represents a binary unsigned division operation.
This class represents an unsigned minimum selection.
This class represents a composition of other SCEV predicates, and is the class that most clients will...
void print(raw_ostream &OS, unsigned Depth) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Returns true if this predicate implies N.
SCEVUnionPredicate(ArrayRef< const SCEVPredicate * > Preds, ScalarEvolution &SE)
Union predicates don't get cached so create a dummy set ID for it.
bool isAlwaysTrue() const override
Implementation of the SCEVPredicate interface.
SCEVUnionPredicate getUnionWith(const SCEVPredicate *N, ScalarEvolution &SE) const
Returns a new SCEVUnionPredicate that is the union of this predicate and the given predicate N.
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents the value of vscale, as used when defining the length of a scalable vector or r...
This class represents an assumption made on an AddRec expression.
IncrementWrapFlags
Similar to SCEV::NoWrapFlags, but with slightly different semantics for FlagNUSW.
SCEVWrapPredicate(const FoldingSetNodeIDRef ID, const SCEVAddRecExpr *AR, IncrementWrapFlags Flags)
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Returns true if this predicate implies N.
static SCEVWrapPredicate::IncrementWrapFlags setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OnFlags)
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
const SCEVAddRecExpr * getExpr() const
Implementation of the SCEVPredicate interface.
static SCEVWrapPredicate::IncrementWrapFlags clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OffFlags)
Convenient IncrementWrapFlags manipulation methods.
static SCEVWrapPredicate::IncrementWrapFlags getImpliedFlags(const SCEVAddRecExpr *AR, ScalarEvolution &SE)
Returns the set of SCEVWrapPredicate no wrap flags implied by a SCEVAddRecExpr.
IncrementWrapFlags getFlags() const
Returns the set assumed no overflow flags.
This class represents a zero extension of a small integer value to a larger integer value.
This class represents an analyzed expression in the program.
unsigned short getExpressionSize() const
SCEVNoWrapFlags NoWrapFlags
LLVM_ABI bool isOne() const
Return true if the expression is a constant one.
SCEV(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, unsigned short ExpressionSize, Type *Ty)
static constexpr auto FlagNUW
LLVM_ABI void computeAndSetCanonical(ScalarEvolution &SE)
Compute and set the canonical SCEV, by constructing a SCEV with the same operands,...
LLVM_ABI bool isZero() const
Return true if the expression is a constant zero.
const SCEV * CanonicalSCEV
Pointer to the canonical version of the SCEV, i.e.
static constexpr auto FlagAnyWrap
LLVM_ABI void dump() const
This method is used for debugging.
LLVM_ABI bool isAllOnesValue() const
Return true if the expression is a constant all-ones value.
LLVM_ABI bool isNonConstantNegative() const
Return true if the specified scev is negated, but not a constant.
static constexpr auto FlagNSW
LLVM_ABI ArrayRef< SCEVUse > operands() const
Return operands of this SCEV expression.
Type * getType() const
Return the LLVM type of this SCEV expression.
LLVM_ABI void print(raw_ostream &OS) const
Print out the internal representation of this scalar to the specified stream.
SCEVTypes getSCEVType() const
static constexpr auto FlagNW
Analysis pass that exposes the ScalarEvolution for a function.
LLVM_ABI ScalarEvolution run(Function &F, FunctionAnalysisManager &AM)
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
void print(raw_ostream &OS, const Module *=nullptr) const override
print - Print out the internal state of the pass.
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
ScalarEvolutionWrapperPass()
static LLVM_ABI LoopGuards collect(const Loop *L, ScalarEvolution &SE)
Collect rewrite map for loop guards for loop L, together with flags indicating if NUW and NSW can be ...
LLVM_ABI const SCEV * rewrite(const SCEV *Expr) const
Try to apply the collected loop guards to Expr.
The main scalar evolution driver.
LLVM_ABI const SCEV * getUDivExpr(SCEVUse LHS, SCEVUse RHS)
Get a canonical unsigned division expression, or something simpler if possible.
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
static bool hasFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags TestFlags)
const DataLayout & getDataLayout() const
Return the DataLayout associated with the module this SCEV instance is operating on.
LLVM_ABI bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
LLVM_ABI bool isKnownOnEveryIteration(CmpPredicate Pred, const SCEVAddRecExpr *LHS, const SCEV *RHS)
Test if the condition described by Pred, LHS, RHS is known to be true on every iteration of the loop ...
LLVM_ABI const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterationsImpl(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
LLVM_ABI const SCEV * getZeroExtendExpr(SCEVUse Op, Type *Ty, unsigned Depth=0)
LLVM_ABI const SCEV * getUDivCeilSCEV(const SCEV *N, const SCEV *D)
Compute ceil(N / D).
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterations(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L at given Context duri...
LLVM_ABI Type * getWiderType(Type *Ty1, Type *Ty2) const
LLVM_ABI const SCEV * getAbsExpr(const SCEV *Op, bool IsNSW)
LLVM_ABI bool isKnownNonPositive(const SCEV *S)
Test if the given expression is known to be non-positive.
LLVM_ABI bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
LLVM_ABI const SCEV * getPredicatedConstantMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getConstantMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
LLVM_ABI const SCEV * removePointerBase(const SCEV *S)
Compute an expression equivalent to S - getPointerBase(S).
LLVM_ABI bool isLoopEntryGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS.
LLVM_ABI bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
LLVM_ABI const SCEV * getURemExpr(SCEVUse LHS, SCEVUse RHS)
Represents an unsigned remainder expression based on unsigned division.
LLVM_ABI const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
LLVM_ABI const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
LLVM_ABI const SCEV * getSMinExpr(SCEVUse LHS, SCEVUse RHS)
LLVM_ABI void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags)
Update no-wrap flags of an AddRec.
LLVM_ABI const SCEV * getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS)
Promote the operands to the wider of the types using zero-extension, and then perform a umax operatio...
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
LLVM_ABI bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI=nullptr)
Is operation BinOp between LHS and RHS provably does not have a signed/unsigned overflow (Signed)?
LLVM_ABI ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond, bool ExitIfTrue, bool ControlsOnlyExit, bool AllowPredicates=false)
Compute the number of times the backedge of the specified loop will execute if its exit condition wer...
LLVM_ABI const SCEV * getMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< SCEVUse > &Operands)
LLVM_ABI const SCEVPredicate * getEqualPredicate(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
LLVM_ABI uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
LLVM_ABI const SCEV * getConstant(ConstantInt *V)
LLVM_ABI const SCEV * getPredicatedBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getBackedgeTakenCount, except it will add a set of SCEV predicates to Predicates that are ...
LLVM_ABI const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
LLVM_ABI const SCEV * getMinusSCEV(SCEVUse LHS, SCEVUse RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
LLVM_ABI const SCEV * getAddRecExpr(SCEVUse Start, SCEVUse Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
LLVM_ABI const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
static LLVM_ABI bool isGuaranteedNotToBePoison(const SCEV *Op)
Returns true if Op is guaranteed to not be poison.
bool loopHasNoAbnormalExits(const Loop *L)
Return true if the loop has no abnormal exits.
LLVM_ABI const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)
A version of getTripCountFromExitCount below which always picks an evaluation type which can not resu...
LLVM_ABI ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI)
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
LLVM_ABI const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI const SCEV * getSequentialMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< SCEVUse > &Operands)
LLVM_ABI const SCEV * getCastExpr(SCEVTypes Kind, SCEVUse Op, Type *Ty)
LLVM_ABI std::optional< bool > evaluatePredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Check whether the condition described by Pred, LHS, and RHS is true or false in the given Context.
LLVM_ABI unsigned getSmallConstantMaxTripCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Returns the upper bound of the loop trip count as a normal unsigned value.
LLVM_ABI bool isBackedgeTakenCountMaxOrZero(const Loop *L)
Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCo...
LLVM_ABI void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
LLVM_ABI bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
LLVM_ABI bool isKnownPositive(const SCEV *S)
Test if the given expression is known to be positive.
LLVM_ABI bool SimplifyICmpOperands(CmpPredicate &Pred, SCEVUse &LHS, SCEVUse &RHS, unsigned Depth=0)
Simplify LHS and RHS in a comparison with predicate Pred.
APInt getUnsignedRangeMin(const SCEV *S)
Determine the min of the unsigned range for a particular SCEV.
LLVM_ABI const SCEV * getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo)
Return an expression for offsetof on the given field with type IntTy.
LLVM_ABI LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
LLVM_ABI bool containsAddRecurrence(const SCEV *S)
Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr.
LLVM_ABI const SCEV * getTruncateExpr(SCEVUse Op, Type *Ty, unsigned Depth=0)
LLVM_ABI bool hasOperand(const SCEV *S, const SCEV *Op) const
Test whether the given SCEV has Op as a direct or indirect operand.
LLVM_ABI const SCEV * getZeroExtendExprImpl(SCEVUse Op, Type *Ty, unsigned Depth=0)
LLVM_ABI bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
LLVM_ABI Type * getEffectiveSCEVType(Type *Ty) const
Return a type with the same bitwidth as the given type and which represents how SCEV will treat the g...
LLVM_ABI const SCEVPredicate * getComparePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
LLVM_ABI bool haveSameSign(const SCEV *S1, const SCEV *S2)
Return true if we know that S1 and S2 must have the same sign.
LLVM_ABI const SCEV * getNotSCEV(const SCEV *V)
Return the SCEV object corresponding to ~V.
LLVM_ABI const SCEV * getElementCount(Type *Ty, ElementCount EC, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
LLVM_ABI bool instructionCouldExistWithOperands(const SCEV *A, const SCEV *B)
Return true if there exists a point in the program at which both A and B could be operands to the sam...
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
LLVM_ABI void print(raw_ostream &OS) const
LLVM_ABI const SCEV * getAnyExtendExpr(SCEVUse Op, Type *Ty)
getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the give...
LLVM_ABI const SCEV * getPredicatedExitCount(const Loop *L, const BasicBlock *ExitingBlock, SmallVectorImpl< const SCEVPredicate * > *Predicates, ExitCountKind Kind=Exact)
Same as above except this uses the predicated backedge taken info and may require predicates.
static SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags)
LLVM_ABI void forgetTopmostLoop(const Loop *L)
LLVM_ABI void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
APInt getSignedRangeMin(const SCEV *S)
Determine the min of the signed range for a particular SCEV.
LLVM_ABI bool isLoopUniform(const SCEV *S, const Loop *L)
Returns true if the given SCEV is loop-uniform with respect to the specified loop L.
LLVM_ABI const SCEV * getNoopOrAnyExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
LLVM_ABI const SCEV * getSignExtendExpr(SCEVUse Op, Type *Ty, unsigned Depth=0)
LLVM_ABI const SCEV * getUMaxExpr(SCEVUse LHS, SCEVUse RHS)
static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags Mask)
Convenient NoWrapFlags manipulation.
@ MonotonicallyDecreasing
@ MonotonicallyIncreasing
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI=nullptr)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L, return a LoopInvaria...
LLVM_ABI const SCEV * getStoreSizeOfExpr(Type *IntTy, Type *StoreTy)
Return an expression for the store size of StoreTy that is type IntTy.
LLVM_ABI const SCEVPredicate * getWrapPredicate(const SCEVAddRecExpr *AR, SCEVWrapPredicate::IncrementWrapFlags AddedFlags)
LLVM_ABI bool isLoopBackedgeGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether the backedge of the loop is protected by a conditional between LHS and RHS.
LLVM_ABI APInt getNonZeroConstantMultiple(const SCEV *S)
const SCEV * getMinusOne(Type *Ty)
Return a SCEV for the constant -1 of a specific type.
static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
LLVM_ABI bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
LLVM_ABI BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB)
Return the "disposition" of the given SCEV with respect to the given block.
LLVM_ABI const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
LLVM_ABI const SCEV * getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
Promote the operands to the wider of the types using zero-extension, and then perform a umin operatio...
LLVM_ABI bool loopIsFiniteByAssumption(const Loop *L)
Return true if this loop is finite by assumption.
LLVM_ABI const SCEV * getExistingSCEV(Value *V)
Return an existing SCEV for V if there is one, otherwise return nullptr.
LLVM_ABI APInt getConstantMultiple(const SCEV *S, const Instruction *CtxI=nullptr)
Returns the max constant multiple of S.
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
@ LoopComputable
The SCEV varies predictably with the loop.
@ LoopVariant
The SCEV is loop-variant (unknown).
@ LoopInvariant
The SCEV is loop-invariant.
@ LoopUniform
The SCEV is loop-uniform.
friend class SCEVCallbackVH
LLVM_ABI bool isKnownMultipleOf(const SCEV *S, uint64_t M, SmallVectorImpl< const SCEVPredicate * > &Assumptions)
Check that S is a multiple of M.
LLVM_ABI bool isKnownToBeAPowerOfTwo(const SCEV *S, bool OrZero=false, bool OrNegative=false)
Test if the given expression is known to be a power of 2.
LLVM_ABI std::optional< SCEV::NoWrapFlags > getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO)
Parse NSW/NUW flags from add/sub/mul IR binary operation Op into SCEV no-wrap flags,...
LLVM_ABI void forgetLcssaPhiWithNewPredecessor(Loop *L, PHINode *V)
Forget LCSSA phi node V of loop L to which a new predecessor was added, such that it may no longer be...
LLVM_ABI bool containsUndefs(const SCEV *S) const
Return true if the SCEV expression contains an undef value.
LLVM_ABI std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...
LLVM_ABI const SCEV * getCouldNotCompute()
LLVM_ABI const SCEV * getMulExpr(SmallVectorImpl< SCEVUse > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
LLVM_ABI bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
LLVM_ABI uint32_t getMinTrailingZeros(const SCEV *S, const Instruction *CtxI=nullptr)
Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration).
BlockDisposition
An enum describing the relationship between a SCEV and a basic block.
@ DominatesBlock
The SCEV dominates the block.
@ ProperlyDominatesBlock
The SCEV properly dominates the block.
@ DoesNotDominateBlock
The SCEV does not dominate the block.
LLVM_ABI const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
LLVM_ABI void getPoisonGeneratingValues(SmallPtrSetImpl< const Value * > &Result, const SCEV *S)
Return the set of Values that, if poison, will definitively result in S being poison as well.
LLVM_ABI void forgetLoopDispositions()
Called when the client has changed the disposition of values in this loop.
LLVM_ABI const SCEV * getVScale(Type *Ty)
LLVM_ABI unsigned getSmallConstantTripCount(const Loop *L)
Returns the exact trip count of the loop if we can compute it, and the result is a small constant.
LLVM_ABI bool hasComputableLoopEvolution(const SCEV *S, const Loop *L)
Return true if the given SCEV changes value in a known way in the specified loop.
LLVM_ABI const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
LLVM_ABI void forgetAllLoops()
LLVM_ABI const SCEV * getSignExtendExprImpl(SCEVUse Op, Type *Ty, unsigned Depth=0)
LLVM_ABI bool dominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV dominate the specified basic block.
APInt getUnsignedRangeMax(const SCEV *S)
Determine the max of the unsigned range for a particular SCEV.
LLVM_ABI const SCEV * getAddExpr(SmallVectorImpl< SCEVUse > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
ExitCountKind
The terms "backedge taken count" and "exit count" are used interchangeably to refer to the number of ...
@ SymbolicMaximum
An expression which provides an upper bound on the exact trip count.
@ ConstantMaximum
A constant which provides an upper bound on the exact trip count.
@ Exact
An expression exactly describing the number of times the backedge has executed when a loop is exited.
LLVM_ABI bool isKnownPredicate(CmpPredicate Pred, SCEVUse LHS, SCEVUse RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)
Try to apply information from loop guards for L to Expr.
LLVM_ABI const SCEV * getPtrToAddrExpr(const SCEV *Op)
LLVM_ABI const SCEVAddRecExpr * convertSCEVToAddRecWithPredicates(const SCEV *S, const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Preds)
Tries to convert the S expression to an AddRec expression, adding additional predicates to Preds as r...
LLVM_ABI const SCEV * getSMaxExpr(SCEVUse LHS, SCEVUse RHS)
LLVM_ABI const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
LLVM_ABI const SCEV * getSizeOfExpr(Type *IntTy, TypeSize Size)
Return an expression for a TypeSize.
LLVM_ABI std::optional< bool > evaluatePredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Check whether the condition described by Pred, LHS, and RHS is true or false.
LLVM_ABI const SCEV * getUnknown(Value *V)
LLVM_ABI std::optional< std::pair< const SCEV *, SmallVector< const SCEVPredicate *, 3 > > > createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI)
Checks if SymbolicPHI can be rewritten as an AddRecExpr under some Predicates.
LLVM_ABI const SCEV * getTruncateOrZeroExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool isKnownViaInduction(CmpPredicate Pred, SCEVUse LHS, SCEVUse RHS)
We'd like to check the predicate on every iteration of the most dominated loop between loops used in ...
LLVM_ABI std::optional< APInt > computeConstantDifference(const SCEV *LHS, const SCEV *RHS)
Compute LHS - RHS and returns the result as an APInt if it is a constant, and std::nullopt if it isn'...
LLVM_ABI bool properlyDominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
LLVM_ABI const SCEV * getUDivExactExpr(SCEVUse LHS, SCEVUse RHS)
Get a canonical unsigned division expression, or something simpler if possible.
LLVM_ABI const SCEV * rewriteUsingPredicate(const SCEV *S, const Loop *L, const SCEVPredicate &A)
Re-writes the SCEV according to the Predicates in A.
LLVM_ABI std::pair< const SCEV *, const SCEV * > SplitIntoInitAndPostInc(const Loop *L, const SCEV *S)
Splits SCEV expression S into two SCEVs.
LLVM_ABI bool canReuseInstruction(const SCEV *S, Instruction *I, SmallVectorImpl< Instruction * > &DropPoisonGeneratingInsts)
Check whether it is poison-safe to represent the expression S using the instruction I.
LLVM_ABI bool isKnownPredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI const SCEV * getPredicatedSymbolicMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getSymbolicMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
LLVM_ABI ~ScalarEvolution()
LLVM_ABI const SCEV * getGEPExpr(GEPOperator *GEP, ArrayRef< SCEVUse > IndexExprs)
Returns an expression for a GEP.
LLVM_ABI const SCEV * getUMinExpr(SCEVUse LHS, SCEVUse RHS, bool Sequential=false)
LLVM_ABI void registerUser(const SCEV *User, ArrayRef< const SCEV * > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
LLVM_ABI bool isBasicBlockEntryGuardedByCond(const BasicBlock *BB, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the basic block is protected by a conditional between LHS and RHS.
LLVM_ABI const SCEV * getTruncateOrSignExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool containsErasedValue(const SCEV *S) const
Return true if the SCEV expression contains a Value that has been optimised out and is now a nullptr.
const SCEV * getSymbolicMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEV that is greater than or equal to (i.e.
APInt getSignedRangeMax(const SCEV *S)
Determine the max of the signed range for a particular SCEV.
LLVM_ABI void verify() const
LLVMContext & getContext() const
Implements a dense probed hash-table based set with some number of buckets stored inline.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
iterator insert(iterator I, T &&Elt)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
TypeSize getElementOffset(unsigned Idx) const
TypeSize getSizeInBits() const
Class to represent struct types.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
static LLVM_ABI IntegerType * getInt32Ty(LLVMContext &C)
bool isPointerTy() const
True if this is an instance of PointerType.
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
static LLVM_ABI IntegerType * getIntNTy(LLVMContext &C, unsigned N)
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< user_iterator > users()
unsigned getValueID() const
Return an ID for the concrete type of this object.
LLVM_ABI void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
An efficient, type-erasing, non-owning reference to a callable.
const ParentTy * getParent() const
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be unsigned.
LLVM_ABI std::optional< APInt > SolveQuadraticEquationWrap(APInt A, APInt B, APInt C, unsigned RangeWidth)
Let q(n) = An^2 + Bn + C, and BW = bit width of the value range (e.g.
LLVM_ABI APInt GreatestCommonDivisor(APInt A, APInt B, bool IsSigned=false)
Compute GCD of two APInt values.
const APInt & umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
constexpr bool any(E Val)
int getMinValue(MCInstrInfo const &MCII, MCInst const &MCI)
Return the minimum value of an extendable operand.
@ BasicBlock
Various leaf nodes.
LLVM_ABI Function * getDeclarationIfExists(const Module *M, ID id)
Look up the Function declaration of the intrinsic id in the Module M and return it if it exists.
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
match_combine_or< Ty... > m_CombineOr(const Ty &...Ps)
Combine pattern matchers matching any of Ps patterns.
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
bool match(Val *V, const Pattern &P)
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
auto m_BasicBlock()
Match an arbitrary basic block value and ignore it.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
auto m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
match_bind< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
auto m_Intrinsic(const Ts &...Ops)
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
brc_match< Cond_t, match_bind< BasicBlock >, match_bind< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
CastOperator_match< OpTy, Instruction::PtrToInt > m_PtrToInt(const OpTy &Op)
Matches PtrToInt.
auto m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
bind_cst_ty m_scev_APInt(const APInt *&C)
Match an SCEV constant and bind it to an APInt.
cst_pred_ty< is_all_ones > m_scev_AllOnes()
Match an integer with all bits set.
SCEVUnaryExpr_match< SCEVZeroExtendExpr, Op0_t > m_scev_ZExt(const Op0_t &Op0)
is_undef_or_poison m_scev_UndefOrPoison()
Match an SCEVUnknown wrapping undef or poison.
cst_pred_ty< is_one > m_scev_One()
Match an integer 1.
specificloop_ty m_SpecificLoop(const Loop *L)
SCEVUnaryExpr_match< SCEVSignExtendExpr, Op0_t > m_scev_SExt(const Op0_t &Op0)
match_bind< const SCEVMulExpr > m_scev_Mul(const SCEVMulExpr *&V)
cst_pred_ty< is_zero > m_scev_Zero()
Match an integer 0.
SCEVUnaryExpr_match< SCEVTruncateExpr, Op0_t > m_scev_Trunc(const Op0_t &Op0)
bool match(const SCEV *S, const Pattern &P)
SCEVBinaryExpr_match< SCEVUDivExpr, Op0_t, Op1_t > m_scev_UDiv(const Op0_t &Op0, const Op1_t &Op1)
specificscev_ty m_scev_Specific(const SCEV *S)
Match if we have a specific specified SCEV.
SCEVAffineAddRec_match< Op0_t, Op1_t, match_isa< const Loop > > m_scev_AffineAddRec(const Op0_t &Op0, const Op1_t &Op1)
match_bind< const SCEVUnknown > m_SCEVUnknown(const SCEVUnknown *&V)
SCEVBinaryExpr_match< SCEVMulExpr, Op0_t, Op1_t, SCEV::FlagNUW, true > m_scev_c_NUWMul(const Op0_t &Op0, const Op1_t &Op1)
match_bind< const SCEVAddExpr > m_scev_Add(const SCEVAddExpr *&V)
SCEVBinaryExpr_match< SCEVSMaxExpr, Op0_t, Op1_t, SCEV::FlagAnyWrap, true > m_scev_SMax(const Op0_t &Op0, const Op1_t &Op1)
SCEVBinaryExpr_match< SCEVMulExpr, Op0_t, Op1_t, SCEV::FlagAnyWrap, true > m_scev_c_Mul(const Op0_t &Op0, const Op1_t &Op1)
SCEVURem_match< Op0_t, Op1_t > m_scev_URem(Op0_t LHS, Op1_t RHS, ScalarEvolution &SE)
Match the mathematical pattern A - (A / B) * B, where A and B can be arbitrary expressions.
@ Valid
The data is already valid.
initializer< Ty > init(const Ty &Val)
LocationClass< Ty > location(Ty &L)
@ Switch
The "resume-switch" lowering, where there are separate resume and destroy functions that are shared b...
NodeAddr< PhiNode * > Phi
friend class Instruction
Iterator for Instructions in a `BasicBlock.
unsigned getOpcode(const VPValue *V)
Return the instruction opcode for the recipe defining V or 0 for unsupported recipes and VPValues not...
This is an optimization pass for GlobalISel generic memory operations.
void visitAll(const SCEV *Root, SV &Visitor)
Use SCEVTraversal to visit all nodes in the given expression tree.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
void stable_sort(R &&Range)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
SaveAndRestore(T &) -> SaveAndRestore< T >
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)
LLVM_ABI bool canCreatePoison(const Operator *Op, bool ConsiderFlagsAndMetadata=true)
LLVM_ABI bool mustTriggerUB(const Instruction *I, const SmallPtrSetImpl< const Value * > &KnownPoison)
Return true if the given instruction must trigger undefined behavior when I is executed with any oper...
RelativeUniformCounterPtr Values
@ Known
Known to have no common set bits.
LLVM_ABI bool canConstantFoldCallTo(const CallBase *Call, const Function *F)
canConstantFoldCallTo - Return true if its even possible to fold a call to the specified function.
InterleavedRange< Range > interleaved(const Range &R, StringRef Separator=", ", StringRef Prefix="", StringRef Suffix="")
Output range R as a sequence of interleaved elements.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
auto successors(const MachineBasicBlock *BB)
scope_exit(Callable) -> scope_exit< Callable >
@ BinaryOp
One of the operands is a binary op.
@ Load
The value being inserted comes from a load (InsertElement only).
@ Store
The extracted value is stored (ExtractElement only).
constexpr from_range_t from_range
auto dyn_cast_if_present(const Y &Val)
dyn_cast_if_present<X> - Functionally identical to dyn_cast, except that a null (or none in the case ...
bool set_is_subset(const S1Ty &S1, const S2Ty &S2)
set_is_subset(A, B) - Return true iff A in B
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
auto uninitialized_copy(R &&Src, IterTy Dst)
bool isa_and_nonnull(const Y &Val)
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
LLVM_ABI bool isOverflowIntrinsicNoWrap(const WithOverflowInst *WO, const DominatorTree &DT)
Returns true if the arithmetic part of the WO 's result is used only along the paths control dependen...
DomTreeNodeBase< BasicBlock > DomTreeNode
LLVM_ABI bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, Value *&Start, Value *&Step)
Attempt to match a simple first order recurrence cycle of the form: iv = phi Ty [Start,...
auto dyn_cast_or_null(const Y &Val)
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
auto reverse(ContainerTy &&C)
LLVM_ABI bool isMustProgress(const Loop *L)
Return true if this loop can be assumed to make progress.
LLVM_ABI bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
LLVM_ABI bool isFinite(const Loop *L)
Return true if this loop can be assumed to run for a finite number of iterations.
LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
unsigned short computeExpressionSize(ArrayRef< SCEVUse > Args)
LLVM_ABI bool programUndefinedIfPoison(const Instruction *Inst)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isPointerTy(const Type *T)
LLVM_ABI ConstantRange getVScaleRange(const Function *F, unsigned BitWidth)
Determine the possible constant range of vscale with the given bit width, based on the vscale_range f...
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
LLVM_ABI bool isKnownNonZero(const Value *V, const SimplifyQuery &Q, unsigned Depth=0)
Return true if the given value is known to be non-zero when defined.
constexpr T divideCeil(U Numerator, V Denominator)
Returns the integer ceil(Numerator / Denominator).
LLVM_ABI bool propagatesPoison(const Use &PoisonOp)
Return true if PoisonOp's user yields poison or raises UB if its operand PoisonOp is poison.
@ UMin
Unsigned integer min implemented in terms of select(cmp()).
@ Mul
Product of integers.
@ SMax
Signed integer max implemented in terms of select(cmp()).
@ SMin
Signed integer min implemented in terms of select(cmp()).
@ UMax
Unsigned integer max implemented in terms of select(cmp()).
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
DWARFExpression::Operation Op
auto max_element(R &&Range)
Provide wrappers to std::max_element which take ranges instead of having to pass begin/end explicitly...
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
ArrayRef(const T &OneElt) -> ArrayRef< T >
LLVM_ABI unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Return the number of times the sign bit of the register is replicated into the other bits.
constexpr unsigned BitWidth
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
constexpr auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
constexpr bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
iterator_range< df_iterator< T > > depth_first(const T &G)
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Returns true if V cannot be poison, but may be undef.
LLVM_ABI Constant * ConstantFoldInstOperands(const Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
SCEVUseT< const SCEV * > SCEVUse
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
Implement std::hash so that hash_code can be used in STL containers.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
A special type used by analysis passes to provide an address that identifies that particular analysis...
static KnownBits makeConstant(const APInt &C)
Create known bits from a known constant.
static LLVM_ABI KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for ashr(LHS, RHS).
static LLVM_ABI KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for lshr(LHS, RHS).
static LLVM_ABI KnownBits shl(const KnownBits &LHS, const KnownBits &RHS, bool NUW=false, bool NSW=false, bool ShAmtNonZero=false)
Compute known bits for shl(LHS, RHS).
An object of this class is returned by queries that could not be answered.
LLVM_ABI SCEVCouldNotCompute()
static LLVM_ABI bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This class defines a simple visitor class that may be used for various SCEV analysis purposes.
A utility class that uses RAII to save and restore the value of a variable.
Information about the number of loop iterations for which a loop exit's branch condition evaluates to...
LLVM_ABI ExitLimit(const SCEV *E)
Construct either an exact exit limit from a constant, or an unknown one from a SCEVCouldNotCompute.
const SCEV * ExactNotTaken
const SCEV * SymbolicMaxNotTaken
SmallVector< const SCEVPredicate *, 4 > Predicates
A vector of predicate guards for this ExitLimit.
const SCEV * ConstantMaxNotTaken