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.lookup(ID, Token)))
472 new (SCEVAllocator)
SCEVConstant(ID.Intern(SCEVAllocator), V);
473 UniqueSCEVs.insert(S, Token);
488 ConstantInt::get(ITy, V,
isSigned,
true));
496 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
498 SCEV *S =
new (SCEVAllocator)
SCEVVScale(ID.Intern(SCEVAllocator), Ty);
499 UniqueSCEVs.insert(S, Token);
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.erase(
this);
560void SCEVUnknown::allUsesReplacedWith(
Value *New) {
562 SE->forgetMemoizedResults({
this});
565 SE->UniqueSCEVs.erase(
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 "use-specific flags only supported for affine AddRecs");
993 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
1034 ConversionFn CreatePtrCast;
1038 ConversionFn CreatePtrCast)
1039 : Base(
SE), TargetTy(TargetTy), CreatePtrCast(
std::
move(CreatePtrCast)) {}
1042 Type *TargetTy, ConversionFn CreatePtrCast) {
1044 return Rewriter.visit(Scev);
1070 "Should only reach pointer-typed SCEVUnknown's.");
1075 return SE.getZero(TargetTy);
1076 return CreatePtrCast(Expr);
1081 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
1085 if (DL.hasUnstableRepresentation(
Op->getType()))
1088 Type *Ty = DL.getAddressType(
Op->getType());
1099 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1101 SCEV *S =
new (SCEVAllocator)
1103 UniqueSCEVs.insert(S, Token);
1106 return static_cast<const SCEV *
>(S);
1109 "We must have succeeded in sinking the cast, "
1110 "and ending up with an integer-typed expression!");
1117 "This is not a truncating conversion!");
1119 "This is not a conversion to a SCEVable type!");
1120 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1125 ID.AddPointer(
Op.getOpaqueValue());
1128 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1151 UniqueSCEVs.insert(S, Token);
1164 unsigned numTruncs = 0;
1165 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1173 if (numTruncs < 2) {
1183 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1190 for (
const SCEV *
Op : AddRec->operands())
1205 UniqueSCEVs.insert(S, Token);
1246struct ExtendOpTraitsBase {
1247 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(
SCEVUse,
Type *,
1252template <
typename ExtendOp>
struct ExtendOpTraits {
1268 static const GetExtendExprTy GetExtendExpr;
1270 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1271 ICmpInst::Predicate *Pred,
1272 ScalarEvolution *SE) {
1277const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1284 static const GetExtendExprTy GetExtendExpr;
1286 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1287 ICmpInst::Predicate *Pred,
1288 ScalarEvolution *SE) {
1293const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1305template <
typename ExtendOpTy>
1308 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1309 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1325 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1338 auto PreStartFlags =
1356 const SCEV *OperandExtendedStart =
1358 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1359 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1371 const SCEV *OverflowLimit =
1372 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1374 if (OverflowLimit &&
1382template <
typename ExtendOpTy>
1386 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1394 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1429template <
typename ExtendOpTy>
1430bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1433 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1443 APInt StartAI = StartC->
getAPInt();
1445 for (
unsigned Delta : {-2, -1, 1, 2}) {
1446 const SCEV *PreStart =
getConstant(StartAI - Delta);
1448 FoldingSetNodeID
ID;
1450 ID.AddPointer(PreStart);
1451 ID.AddPointer(Step);
1453 FoldingSetInsertToken Token;
1455 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.lookup(ID, Token));
1459 if (PreAR &&
any(PreAR->getNoWrapFlags(WrapType))) {
1462 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1463 DeltaS, &Pred,
this);
1481 const unsigned BitWidth =
C.getBitWidth();
1499 const APInt &ConstantStart,
1514 auto I = FoldCache.
insert({ID, S});
1518 auto &UserIDs = FoldCacheUser[
I.first->second];
1519 assert(
count(UserIDs, ID) == 1 &&
"unexpected duplicates in UserIDs");
1520 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1521 if (UserIDs[
I] == ID) {
1526 I.first->second = S;
1528 FoldCacheUser[S].push_back(ID);
1534 "This is not an extending conversion!");
1536 "This is not a conversion to a SCEVable type!");
1537 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1541 if (
const SCEV *S = FoldCache.lookup(ID))
1553 "This is not an extending conversion!");
1555 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1567 const SCEV *Start, *Step;
1572 if (AR->hasNoUnsignedWrap()) {
1583 ID.AddPointer(
Op.getOpaqueValue());
1586 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1591 UniqueSCEVs.insert(S, Token);
1601 const SCEV *
X = ST->getOperand();
1634 const SCEV *CastedMaxBECount =
1638 if (MaxBECount == RecastedMaxBECount) {
1647 const SCEV *WideMaxBECount =
1649 const SCEV *OperandExtendedAdd =
1655 if (ZAdd == OperandExtendedAdd) {
1666 OperandExtendedAdd =
1672 if (ZAdd == OperandExtendedAdd) {
1693 !AC.assumptions().empty()) {
1695 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1697 if (AR->hasNoUnsignedWrap()) {
1732 const APInt &
C = SC->getAPInt();
1736 const SCEV *SResidual =
1744 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1768 if (SA->hasNoUnsignedWrap()) {
1781 if (SA->hasNoSignedWrap() &&
1784 C->isNegative() && !
C->isMinSignedValue() && C2->
sge(
C->abs())) {
1803 const SCEV *SResidual =
1814 if (SM->hasNoUnsignedWrap()) {
1836 const SCEV *TruncRHS;
1873 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1877 UniqueSCEVs.insert(S, Token);
1886 "This is not an extending conversion!");
1888 "This is not a conversion to a SCEVable type!");
1889 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1893 if (
const SCEV *S = FoldCache.lookup(ID))
1905 "This is not an extending conversion!");
1907 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1924 const SCEV *Start, *Step;
1929 if (AR->hasNoSignedWrap()) {
1940 ID.AddPointer(
Op.getOpaqueValue());
1943 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1949 UniqueSCEVs.insert(S, Token);
1959 const SCEV *
X = ST->getOperand();
1970 if (SA->hasNoSignedWrap()) {
1992 const SCEV *SResidual =
2025 const SCEV *CastedMaxBECount =
2029 if (MaxBECount == RecastedMaxBECount) {
2038 const SCEV *WideMaxBECount =
2040 const SCEV *OperandExtendedAdd =
2046 if (SAdd == OperandExtendedAdd) {
2057 OperandExtendedAdd =
2063 if (SAdd == OperandExtendedAdd) {
2083 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2085 if (AR->hasNoSignedWrap()) {
2099 const APInt &
C = SC->getAPInt();
2103 const SCEV *SResidual =
2111 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2138 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
2142 UniqueSCEVs.insert(S, Token);
2158 assert(Expr->
getType() == Ty &&
"requested type must match");
2170 "This is not an extending conversion!");
2172 "This is not a conversion to a SCEVable type!");
2177 if (SC->getAPInt().isNegative())
2182 const SCEV *NewOp =
T->getOperand();
2201 for (
const SCEV *
Op : AR->operands())
2239 APInt &AccumulatedConstant,
2243 bool Interesting =
false;
2250 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2252 AccumulatedConstant += Scale *
C->getAPInt();
2257 for (; i !=
Ops.size(); ++i) {
2266 M, NewOps, AccumulatedConstant,
Add->operands(), NewScale, SE);
2272 auto Pair = M.insert({
Key, NewScale});
2276 Pair.first->second += NewScale;
2284 auto Pair = M.insert({
Ops[i], Scale});
2288 Pair.first->second += Scale;
2306 case Instruction::Add:
2308 case Instruction::Sub:
2310 case Instruction::Mul:
2324 const SCEV *
A = (this->*Extension)(
Operation(LHS, RHS), WideTy, 0);
2325 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2326 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2334 if (BinOp == Instruction::Mul)
2340 APInt C = RHSC->getAPInt();
2341 unsigned NumBits =
C.getBitWidth();
2342 bool IsSub = (BinOp == Instruction::Sub);
2343 bool IsNegativeConst = (
Signed &&
C.isNegative());
2345 bool OverflowDown = IsSub ^ IsNegativeConst;
2347 if (IsNegativeConst) {
2360 APInt Limit = Min + Magnitude;
2366 APInt Limit = Max - Magnitude;
2371std::optional<SCEV::NoWrapFlags>
2376 return std::nullopt;
2385 bool Deduced =
false;
2391 bool CanUseNSW =
true;
2392 const APInt *ShiftAmt;
2397 return std::nullopt;
2401 Opcode = Instruction::Mul;
2403 }
else if (Opcode != Instruction::Add && Opcode != Instruction::Sub &&
2404 Opcode != Instruction::Mul) {
2405 return std::nullopt;
2424 return std::nullopt;
2434 using namespace std::placeholders;
2441 assert(CanAnalyze &&
"don't call from other places!");
2448 auto IsKnownNonNegative = [&](
SCEVUse U) {
2457 if (SignOrUnsignWrap != SignOrUnsignMask &&
2464 return Instruction::Add;
2466 return Instruction::Mul;
2477 Opcode,
C, OBO::NoSignedWrap);
2485 Opcode,
C, OBO::NoUnsignedWrap);
2495 Ops[0]->isZero() && IsKnownNonNegative(
Ops[1]))
2502 if (UDiv->getOperand(1) ==
Ops[1])
2505 if (UDiv->getOperand(1) ==
Ops[0])
2522 "only nuw or nsw allowed");
2524 "only nuw or nsw allowed");
2525 assert(!
Ops.empty() &&
"Cannot get empty add!");
2526 if (
Ops.size() == 1)
return Ops[0];
2529 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
2531 "SCEVAddExpr operand types don't match!");
2533 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2534 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2539 [](
const APInt &C1,
const APInt &C2) {
return C1 + C2; },
2540 [](
const APInt &
C) {
return C.isZero(); },
2541 [](
const APInt &
C) {
return false; });
2560 return {getOrCreateAddExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
2565 if (
Add->getNoWrapFlags(OrigFlags) != OrigFlags)
2566 Add->setNoWrapFlags(ComputeFlags(
Ops));
2567 return {S, UseFlags};
2574 bool FoundMatch =
false;
2575 for (
unsigned i = 0, e =
Ops.size(); i != e-1; ++i)
2576 if (
Ops[i] ==
Ops[i+1]) {
2588 --i; e -=
Count - 1;
2598 auto FindTruncSrcType = [&]() ->
Type * {
2604 return T->getOperand()->getType();
2606 SCEVUse LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2608 return T->getOperand()->getType();
2612 if (
auto *SrcType = FindTruncSrcType()) {
2619 if (
T->getOperand()->getType() != SrcType) {
2628 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2631 if (
T->getOperand()->getType() != SrcType) {
2660 if (
Ops.size() == 2) {
2670 auto C2 =
C->getAPInt();
2673 APInt ConstAdd = C1 + C2;
2674 auto AddFlags = AddExpr->getNoWrapFlags();
2715 if (
Ops.size() == 2 &&
2726 if (Idx <
Ops.size()) {
2727 bool DeletedAdd =
false;
2738 Ops.erase(
Ops.begin()+Idx);
2741 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2764 struct APIntCompare {
2765 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2766 return LHS.ult(RHS);
2773 std::map<APInt, SmallVector<SCEVUse, 4>, APIntCompare> MulOpLists;
2775 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2778 if (AccumulatedConstant != 0)
2780 for (
auto &MulOp : MulOpLists) {
2781 if (MulOp.first == 1) {
2783 }
else if (MulOp.first != 0) {
2792 if (
Ops.size() == 1)
2801 if (M->getNumOperands() == 2)
2802 return M->getOperand(OpIdx == 0);
2804 append_range(Remaining, M->operands().drop_front(OpIdx + 1));
2813 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2817 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2825 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp) {
2826 if (MulOpSCEV ==
Ops[AddOp]) {
2837 for (
unsigned OMulOp = 0, OE = OtherMul->
getNumOperands(); OMulOp != OE;
2839 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2841 Cofactors.
push_back(StripFactor(OtherMul, OMulOp));
2850 if (!Cofactors.
empty()) {
2858 if (
Ops.size() == DeadIndices.
size() + 1)
2865 Ops.erase(
Ops.begin() + Idx);
2869 Ops.push_back(OuterMul);
2888 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
2891 Ops.erase(
Ops.begin()+i);
2896 if (!LIOps.
empty()) {
2921 auto *DefI = getDefiningScopeBound(LIOps);
2923 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
2935 if (
Ops.size() == 1)
return NewRec;
2938 for (
unsigned i = 0;; ++i)
2939 if (
Ops[i] == AddRec) {
2949 for (
unsigned OtherIdx = Idx+1;
2957 "AddRecExprs are not sorted in reverse dominance order?");
2964 if (OtherAddRec->getLoop() == AddRecLoop) {
2965 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
2967 if (i >= AddRecOps.
size()) {
2968 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
2972 getAddExpr(AddRecOps[i], OtherAddRec->getOperand(i),
2975 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
2991 "Tried to add SCEVUse flags after operands changed");
2992 return {getOrCreateAddExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
3000 ID.AddPointer(
Op.getOpaqueValue());
3006 S =
new (SCEVAllocator)
3008 UniqueSCEVs.insert(S, Token);
3019 FoldingSetNodeID
ID;
3022 ID.AddPointer(
Op.getOpaqueValue());
3024 FoldingSetInsertToken Token;
3026 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.lookup(ID, Token));
3030 S =
new (SCEVAllocator)
3031 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
3032 UniqueSCEVs.insert(S, Token);
3034 LoopUsers[
L].push_back(S);
3043 FoldingSetNodeID
ID;
3046 ID.AddPointer(
Op.getOpaqueValue());
3047 FoldingSetInsertToken Token;
3048 SCEVMulExpr *S =
static_cast<SCEVMulExpr *
>(UniqueSCEVs.lookup(ID, Token));
3052 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3054 UniqueSCEVs.insert(S, Token);
3063 FoldingSetNodeID
ID;
3065 ID.AddPointer(
LHS.getOpaqueValue());
3066 ID.AddPointer(
RHS.getOpaqueValue());
3067 FoldingSetInsertToken Token;
3068 SCEV *S = UniqueSCEVs.lookup(ID, Token);
3070 S =
new (SCEVAllocator) SCEVUDivExpr(
ID.Intern(SCEVAllocator),
LHS,
RHS);
3071 UniqueSCEVs.insert(S, Token);
3080 if (j > 1 && k / j != i) Overflow =
true;
3096 if (n == 0 || n == k)
return 1;
3097 if (k > n)
return 0;
3103 for (
uint64_t i = 1; i <= k; ++i) {
3104 r =
umul_ov(r, n-(i-1), Overflow);
3113 struct FindConstantInAddMulChain {
3114 bool FoundConstant =
false;
3116 bool follow(
const SCEV *S) {
3121 bool isDone()
const {
3122 return FoundConstant;
3126 FindConstantInAddMulChain
F;
3128 ST.visitAll(StartExpr);
3129 return F.FoundConstant;
3138 "only nuw or nsw allowed");
3140 "only nuw or nsw allowed");
3141 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3142 if (
Ops.size() == 1)
return Ops[0];
3144 Type *ETy =
Ops[0]->getType();
3146 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3148 "SCEVMulExpr operand types don't match!");
3153 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3154 [](
const APInt &
C) {
return C.isOne(); },
3155 [](
const APInt &
C) {
return C.isZero(); });
3172 return {getOrCreateMulExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
3177 if (
Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3178 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3179 return {S, UseFlags};
3183 if (
Ops.size() == 2) {
3191 const SCEV *Op0, *Op1;
3199 if (
Ops[0]->isAllOnesValue()) {
3204 bool AnyFolded =
false;
3205 for (
const SCEV *AddOp :
Add->operands()) {
3225 if (AddRec->hasNoSignedWrap()) {
3256 APInt C1V = LHSC->getAPInt();
3266 const SCEV *NewMul =
nullptr;
3270 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3285 if (Idx <
Ops.size()) {
3286 bool DeletedMul =
false;
3292 Ops.erase(
Ops.begin()+Idx);
3316 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3319 Ops.erase(
Ops.begin()+i);
3324 if (!LIOps.
empty()) {
3337 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3353 if (
Ops.size() == 1)
return NewRec;
3356 for (
unsigned i = 0;; ++i)
3357 if (
Ops[i] == AddRec) {
3378 bool OpsModified =
false;
3379 for (
unsigned OtherIdx = Idx+1;
3393 bool Overflow =
false;
3400 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3401 uint64_t Coeff1 =
Choose(x, 2*x - y, Overflow);
3404 z < ze && !Overflow; ++z) {
3405 uint64_t Coeff2 =
Choose(2*x - y, x-z, Overflow);
3407 if (LargerThan64Bits)
3408 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3410 Coeff = Coeff1*Coeff2;
3423 const SCEV *NewAddRec =
3425 if (
Ops.size() == 2)
return NewAddRec;
3426 Ops[Idx] = NewAddRec;
3427 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3444 "Tried to add SCEVUse flags after operands changed");
3445 return {getOrCreateMulExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
3452 "SCEVURemExpr operand types don't match!");
3457 if (RHSC->getValue()->isOne())
3458 return getZero(LHS->getType());
3461 if (RHSC->getAPInt().isPowerOf2()) {
3462 Type *FullTy = LHS->getType();
3478 assert(!LHS->getType()->isPointerTy() &&
3479 "SCEVUDivExpr operand can't be pointer!");
3480 assert(LHS->getType() == RHS->getType() &&
3481 "SCEVUDivExpr operand types don't match!");
3491 if (RHSC->getValue()->isOne())
3496 if (!RHSC->getValue()->isZero()) {
3500 Type *Ty = LHS->getType();
3501 unsigned LZ = RHSC->getAPInt().countl_zero();
3505 if (!RHSC->getAPInt().isPowerOf2())
3513 const APInt &StepInt = Step->getAPInt();
3514 const APInt &DivInt = RHSC->getAPInt();
3515 if (!StepInt.
urem(DivInt) &&
3521 for (
const SCEV *
Op : AR->operands())
3527 const APInt *StartRem;
3540 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3544 const SCEV *NewStart =
3546 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3548 const SCEV *NewLHS =
3558 if (M->hasNoUnsignedWrap()) {
3560 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3561 const SCEV *
Op = M->getOperand(i);
3588 if (
auto *DivisorConstant =
3590 bool Overflow =
false;
3592 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3603 if (
A->hasNoUnsignedWrap()) {
3605 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3612 if (
Operands.size() ==
A->getNumOperands())
3624 const APInt &
N = RHSC->getAPInt();
3625 const APInt *NMinusM, *M;
3629 if (
N.isPowerOf2() && M->isPowerOf2() && M->ult(
N) &&
3630 *NMinusM ==
N - *M) {
3639 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3649 return getZero(LHS->getType());
3653 if (
Mul &&
Mul->hasNoUnsignedWrap()) {
3654 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3655 if (
Mul->getOperand(i) == RHS) {
3666 const SCEV *NewLHS, *NewRHS;
3671 return getOrCreateUDivExpr(LHS, RHS);
3690 if (StepChrec->getLoop() == L) {
3709 "only nuw or nsw allowed");
3715 "SCEVAddRecExpr operand types don't match!");
3716 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3720 "SCEVAddRecExpr operand is not available at loop entry!");
3742 const Loop *NestedLoop = NestedAR->getLoop();
3743 if (L->contains(NestedLoop)
3746 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3748 Operands[0] = NestedAR->getStart();
3752 bool AllInvariant =
all_of(
3764 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3775 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3786 "Tried to add SCEVUse flags after operands changed");
3787 return {getOrCreateAddRecExpr(
Operands, L, Flags), UseFlags};
3803 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3807 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3821 bool FirstIter =
true;
3823 for (
SCEVUse IndexExpr : IndexExprs) {
3830 Offsets.push_back(FieldOffset);
3833 CurTy = STy->getTypeAtIndex(Index);
3838 "The first index of a GEP indexes a pointer");
3839 CurTy = SrcElementTy;
3850 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3851 Offsets.push_back(LocalOffset);
3856 if (Offsets.empty())
3869 "GEP should not change type mid-flight.");
3873SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3878 ID.AddPointer(
Op.getOpaqueValue());
3880 return UniqueSCEVs.lookup(ID, Token);
3890 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3891 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3892 if (
Ops.size() == 1)
return Ops[0];
3895 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
3897 "Operand types don't match!");
3900 "min/max should be consistently pointerish");
3926 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3928 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3933 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3935 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3941 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
3947 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
3952 if (Idx <
Ops.size()) {
3953 bool DeletedAny =
false;
3954 while (
Ops[Idx]->getSCEVType() == Kind) {
3956 Ops.erase(
Ops.begin()+Idx);
3974 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
3975 if (
Ops[i] ==
Ops[i + 1] ||
3976 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
3979 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
3982 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
3985 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
3991 if (
Ops.size() == 1)
return Ops[0];
3993 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
4000 ID.AddPointer(
Op.getOpaqueValue());
4002 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
4004 return ExistingSCEV;
4007 SCEV *S =
new (SCEVAllocator)
4010 UniqueSCEVs.insert(S, Token);
4018class SCEVSequentialMinMaxDeduplicatingVisitor final
4019 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
4020 std::optional<const SCEV *>> {
4021 using RetVal = std::optional<const SCEV *>;
4028 bool canRecurseInto(
SCEVTypes Kind)
const {
4031 return RootKind == Kind || NonSequentialRootKind == Kind;
4036 if (!SeenOps.
insert(S).second)
4037 return std::nullopt;
4041 if (!canRecurseInto(Kind))
4051 return std::nullopt;
4061 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4063 : SE(SE), RootKind(RootKind),
4064 NonSequentialRootKind(
4065 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4069 SmallVectorImpl<SCEVUse> &NewOps) {
4074 for (
const SCEV *
Op : OrigOps) {
4079 Ops.emplace_back(*NewOp);
4083 NewOps = std::move(
Ops);
4127struct SCEVPoisonCollector {
4128 bool LookThroughMaybePoisonBlocking;
4129 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4130 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4131 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4133 bool follow(
const SCEV *S) {
4134 if (!LookThroughMaybePoisonBlocking &&
4144 bool isDone()
const {
return false; }
4154 SCEVPoisonCollector PC1(
true);
4159 if (PC1.MaybePoison.
empty())
4165 SCEVPoisonCollector PC2(
false);
4175 SCEVPoisonCollector PC(
false);
4198 while (!Worklist.
empty()) {
4200 if (!Visited.
insert(V).second)
4204 if (Visited.
size() > 16)
4220 if (PDI->isDisjoint())
4227 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4234 if (
I->hasPoisonGeneratingAnnotations())
4245 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4246 "Not a SCEVSequentialMinMaxExpr!");
4247 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4248 if (
Ops.size() == 1)
4252 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4254 "Operand types don't match!");
4257 "min/max should be consistently pointerish");
4265 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4272 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4282 bool DeletedAny =
false;
4283 while (Idx <
Ops.size()) {
4284 if (
Ops[Idx]->getSCEVType() != Kind) {
4289 Ops.erase(
Ops.begin() + Idx);
4290 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4291 SMME->operands().end());
4299 const SCEV *SaturationPoint;
4310 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4311 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4323 Ops.erase(
Ops.begin() + i);
4328 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4329 Ops.erase(
Ops.begin() + i);
4339 ID.AddPointer(
Op.getOpaqueValue());
4341 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
4343 return ExistingSCEV;
4347 SCEV *S =
new (SCEVAllocator)
4350 UniqueSCEVs.insert(S, Token);
4398 if (
Size.isScalable())
4419 "Cannot get offset for structure containing scalable vector types");
4433 if (
SCEV *S = UniqueSCEVs.lookup(ID, Token)) {
4435 "Stale SCEVUnknown in uniquing map!");
4438 SCEV *S =
new (SCEVAllocator)
SCEVUnknown(ID.Intern(SCEVAllocator), V,
this,
4441 UniqueSCEVs.insert(S, Token);
4456 return Ty->isIntOrPtrTy();
4463 if (Ty->isPointerTy())
4474 if (Ty->isIntegerTy())
4478 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4490 bool PreciseA, PreciseB;
4491 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4492 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4493 if (!PreciseA || !PreciseB)
4496 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4497 DT.dominates(ScopeB, ScopeA);
4501 return CouldNotCompute.get();
4504bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4507 return SU && SU->getValue() ==
nullptr;
4510 return !ContainsNulls;
4515 if (
I != HasRecMap.end())
4520 HasRecMap.insert({S, FoundAddRec});
4528 if (
SI == ExprValueMap.
end())
4530 return SI->second.getArrayRef();
4536void ScalarEvolution::eraseValueFromMap(
Value *V) {
4538 if (
I != ValueExprMap.end()) {
4539 auto EVIt = ExprValueMap.find(
I->second);
4540 bool Removed = EVIt->second.remove(V);
4542 assert(Removed &&
"Value not in ExprValueMap?");
4543 ValueExprMap.erase(
I);
4547void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4551 auto It = ValueExprMap.find_as(V);
4552 if (It == ValueExprMap.end()) {
4554 ExprValueMap[S].insert(V);
4565 return createSCEVIter(V);
4572 if (
I != ValueExprMap.end()) {
4573 const SCEV *S =
I->second;
4574 assert(checkValidity(S) &&
4575 "existing SCEV has not been properly invalidated");
4588 Type *Ty = V->getType();
4604 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4617 return (
const SCEV *)
nullptr;
4623 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4627 Type *Ty = V->getType();
4633 assert(
P->getType()->isPointerTy());
4648 if (AddOp->getType()->isPointerTy()) {
4649 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4667 return getZero(LHS->getType());
4672 if (RHS->getType()->isPointerTy()) {
4673 if (!LHS->getType()->isPointerTy() ||
4683 const bool RHSIsNotMinSigned =
4714 Type *SrcTy = V->getType();
4715 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4716 "Cannot truncate or zero extend with non-integer arguments!");
4726 Type *SrcTy = V->getType();
4727 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4728 "Cannot truncate or zero extend with non-integer arguments!");
4737 Type *SrcTy = V->getType();
4738 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4739 "Cannot noop or zero extend with non-integer arguments!");
4741 "getNoopOrZeroExtend cannot truncate!");
4748 Type *SrcTy = V->getType();
4749 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4750 "Cannot noop or sign extend with non-integer arguments!");
4752 "getNoopOrSignExtend cannot truncate!");
4759 Type *SrcTy = V->getType();
4760 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4761 "Cannot noop or any extend with non-integer arguments!");
4763 "getNoopOrAnyExtend cannot truncate!");
4770 Type *SrcTy = V->getType();
4771 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4772 "Cannot truncate or noop with non-integer arguments!");
4774 "getTruncateOrNoop cannot extend!");
4782 const SCEV *PromotedLHS = LHS;
4783 const SCEV *PromotedRHS = RHS;
4803 assert(!
Ops.empty() &&
"At least one operand must be!");
4805 if (
Ops.size() == 1)
4809 Type *MaxType =
nullptr;
4815 assert(MaxType &&
"Failed to find maximum type!");
4828 if (!V->getType()->isPointerTy())
4833 V = AddRec->getStart();
4835 const SCEV *PtrOp =
nullptr;
4836 for (
const SCEV *AddOp :
Add->operands()) {
4837 if (AddOp->getType()->isPointerTy()) {
4838 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4842 assert(PtrOp &&
"Must have pointer op");
4854 for (
User *U :
I->users()) {
4856 if (Visited.
insert(UserInsn).second)
4870 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4871 bool IgnoreOtherLoops =
true) {
4874 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4876 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4881 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4883 SeenLoopVariantSCEVUnknown =
true;
4887 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4891 SeenOtherLoops =
true;
4895 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4897 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4900 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
4901 : SCEVRewriteVisitor(SE),
L(
L) {}
4904 bool SeenLoopVariantSCEVUnknown =
false;
4905 bool SeenOtherLoops =
false;
4914 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
4915 SCEVPostIncRewriter
Rewriter(L, SE);
4917 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4922 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4924 SeenLoopVariantSCEVUnknown =
true;
4928 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4932 SeenOtherLoops =
true;
4936 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4938 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4941 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
4942 : SCEVRewriteVisitor(SE),
L(
L) {}
4945 bool SeenLoopVariantSCEVUnknown =
false;
4946 bool SeenOtherLoops =
false;
4952class SCEVBackedgeConditionFolder
4955 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4956 ScalarEvolution &SE) {
4957 bool IsPosBECond =
false;
4958 Value *BECond =
nullptr;
4959 if (BasicBlock *Latch =
L->getLoopLatch()) {
4961 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
4962 "Both outgoing branches should not target same header!");
4963 BECond = BI->getCondition();
4964 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
4969 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
4973 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4974 const SCEV *
Result = Expr;
4979 switch (
I->getOpcode()) {
4980 case Instruction::Select: {
4982 std::optional<const SCEV *> Res =
4983 compareWithBackedgeCondition(
SI->getCondition());
4991 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
5002 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
5003 bool IsPosBECond, ScalarEvolution &SE)
5004 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
5005 IsPositiveBECond(IsPosBECond) {}
5007 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5011 Value *BackedgeCond =
nullptr;
5013 bool IsPositiveBECond;
5016std::optional<const SCEV *>
5017SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5022 if (BackedgeCond == IC)
5025 return std::nullopt;
5030 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5031 ScalarEvolution &SE) {
5037 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5044 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5054 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5055 : SCEVRewriteVisitor(SE),
L(
L) {}
5063void ScalarEvolution::inferNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5079 const APInt &BECountAP = BECountMax->getAPInt();
5080 unsigned NoOverflowBitWidth =
5089ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5099 if (!SignedWrapViaInductionTried.insert(AR).second)
5124 AC.assumptions().empty())
5132 const SCEV *OverflowLimit =
5134 if (OverflowLimit &&
5142ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5152 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5177 AC.assumptions().empty())
5186 const SCEV *OverflowLimit =
5215 IsNSW = OBO->hasNoSignedWrap();
5216 IsNUW = OBO->hasNoUnsignedWrap();
5222 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5234 return std::nullopt;
5240 switch (
Op->getOpcode()) {
5241 case Instruction::Add:
5242 case Instruction::Sub:
5243 case Instruction::Mul:
5244 case Instruction::UDiv:
5245 case Instruction::URem:
5246 case Instruction::And:
5247 case Instruction::AShr:
5248 case Instruction::Shl:
5251 case Instruction::Or: {
5254 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5264 case Instruction::Xor:
5268 if (RHSC->getValue().isSignMask())
5269 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5271 if (V->getType()->isIntegerTy(1))
5272 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5275 case Instruction::LShr:
5284 if (SA->getValue().ult(
BitWidth)) {
5286 ConstantInt::get(SA->getContext(),
5288 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5293 case Instruction::ExtractValue: {
5295 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5303 bool Signed = WO->isSigned();
5306 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5311 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5322 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5323 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5325 return std::nullopt;
5351 if (
Op == SymbolicPHI)
5356 if (SourceBits != NewBits)
5374 if (!L || L->getHeader() != PN->
getParent())
5432std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5433ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5441 assert(L &&
"Expecting an integer loop header phi");
5446 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5447 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5448 Value *
V = PN->getIncomingValue(i);
5449 if (
L->contains(PN->getIncomingBlock(i))) {
5452 }
else if (BEValueV != V) {
5456 }
else if (!StartValueV) {
5458 }
else if (StartValueV != V) {
5459 StartValueV =
nullptr;
5463 if (!BEValueV || !StartValueV)
5464 return std::nullopt;
5466 const SCEV *BEValue =
getSCEV(BEValueV);
5473 return std::nullopt;
5477 unsigned FoundIndex =
Add->getNumOperands();
5478 Type *TruncTy =
nullptr;
5480 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5483 if (FoundIndex == e) {
5488 if (FoundIndex ==
Add->getNumOperands())
5489 return std::nullopt;
5493 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5494 if (i != FoundIndex)
5495 Ops.push_back(
Add->getOperand(i));
5501 return std::nullopt;
5554 const SCEV *StartVal =
getSCEV(StartValueV);
5555 const SCEV *PHISCEV =
5582 auto getExtendedExpr = [&](
const SCEV *Expr,
5583 bool CreateSignExtend) ->
const SCEV * {
5586 const SCEV *ExtendedExpr =
5589 return ExtendedExpr;
5597 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5598 const SCEV *ExtendedExpr) ->
bool {
5599 return Expr != ExtendedExpr &&
5603 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5604 if (PredIsKnownFalse(StartVal, StartExtended)) {
5606 return std::nullopt;
5611 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5612 if (PredIsKnownFalse(Accum, AccumExtended)) {
5614 return std::nullopt;
5617 auto AppendPredicate = [&](
const SCEV *Expr,
5618 const SCEV *ExtendedExpr) ->
void {
5619 if (Expr != ExtendedExpr &&
5627 AppendPredicate(StartVal, StartExtended);
5628 AppendPredicate(Accum, AccumExtended);
5636 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5637 std::make_pair(NewAR, Predicates);
5639 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5643std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5648 return std::nullopt;
5651 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5652 if (
I != PredicatedSCEVRewrites.end()) {
5653 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5656 if (Rewrite.first == SymbolicPHI)
5657 return std::nullopt;
5661 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5665 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5666 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5671 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5672 return std::nullopt;
5692 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5693 if (Expr1 != Expr2 &&
5694 !AllPreds.
implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5695 !AllPreds.
implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5730const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5732 Value *StartValueV) {
5735 assert(BEValueV && StartValueV);
5737 const SCEV *Accum =
nullptr;
5740 if (BO->Opcode != Instruction::Add)
5743 if (BO->LHS == PN &&
L->isLoopInvariant(BO->RHS))
5745 else if (BO->RHS == PN &&
L->isLoopInvariant(BO->LHS))
5759 if (!
GEP ||
GEP->getPointerOperand() != PN ||
GEP->getNumIndices() != 1)
5762 if (!
L->isLoopInvariant(Idx))
5771 const SCEV *StartVal =
getSCEV(StartValueV);
5772 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5773 insertValueToMap(PN, PHISCEV);
5776 inferNoWrapViaConstantRanges(AR);
5783 "Accum is defined outside L, but is not invariant?");
5784 if (isAddRecNeverPoison(BEInst, L))
5791const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5799 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5805 }
else if (BEValueV != V) {
5809 }
else if (!StartValueV) {
5811 }
else if (StartValueV != V) {
5812 StartValueV =
nullptr;
5816 if (!BEValueV || !StartValueV)
5819 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5820 "PHI node already processed?");
5824 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5829 insertValueToMap(PN, SymbolicName);
5833 const SCEV *BEValue =
getSCEV(BEValueV);
5843 unsigned FoundIndex =
Add->getNumOperands();
5844 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5845 if (
Add->getOperand(i) == SymbolicName)
5846 if (FoundIndex == e) {
5851 if (FoundIndex !=
Add->getNumOperands()) {
5854 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5855 if (i != FoundIndex)
5856 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5868 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5875 if (
GEP->getOperand(0) == PN)
5883 const SCEV *StartVal =
getSCEV(StartValueV);
5884 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5889 forgetMemoizedResults({SymbolicName});
5890 insertValueToMap(PN, PHISCEV);
5893 inferNoWrapViaConstantRanges(AR);
5917 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5918 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5920 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
5921 const SCEV *StartVal =
getSCEV(StartValueV);
5922 if (Start == StartVal) {
5926 forgetMemoizedResults({SymbolicName});
5927 insertValueToMap(PN, Shifted);
5937 eraseValueFromMap(PN);
5952 Use &LeftUse =
Merge->getOperandUse(0);
5953 Use &RightUse =
Merge->getOperandUse(1);
5989 assert(IDom &&
"At least the entry block should dominate PN");
5997const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
6002 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
6019 CommonInst = IncomingInst;
6035ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6041 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6042 bool SCEVExprsIdentical =
6044 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6045 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6048const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6049 if (
const SCEV *S = createAddRecFromPHI(PN))
6059 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6062 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6071 struct FindClosure {
6072 const SCEV *OperandToFind;
6078 bool canRecurseInto(
SCEVTypes Kind)
const {
6081 return RootKind == Kind || NonSequentialRootKind == Kind ||
6086 : OperandToFind(OperandToFind), RootKind(RootKind),
6087 NonSequentialRootKind(
6091 bool follow(
const SCEV *S) {
6092 Found = S == OperandToFind;
6094 return !isDone() && canRecurseInto(S->
getSCEVType());
6097 bool isDone()
const {
return Found; }
6100 FindClosure FC(OperandToFind, RootKind);
6105std::optional<const SCEV *>
6106ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6116 switch (ICI->getPredicate()) {
6130 bool Signed = ICI->isSigned();
6131 const SCEV *LA =
getSCEV(TrueVal);
6139 if (LA == LS &&
RA == RS)
6141 if (LA == RS &&
RA == LS)
6144 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6145 if (
Op->getType()->isPointerTy()) {
6156 LS = CoerceOperand(LS);
6157 RS = CoerceOperand(RS);
6181 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6182 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6196 X = ZExt->getOperand();
6198 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6209 return std::nullopt;
6212static std::optional<const SCEV *>
6214 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6218 "Unexpected operands of a select.");
6230 return std::nullopt;
6245static std::optional<const SCEV *>
6249 return std::nullopt;
6252 const auto *SETrue = SE->
getSCEV(TrueVal);
6253 const auto *SEFalse = SE->
getSCEV(FalseVal);
6257const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6259 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6261 V->getType() ==
TrueVal->getType() &&
6262 "Types of select hands and of the result must match.");
6265 if (!
V->getType()->isIntegerTy(1))
6268 if (std::optional<const SCEV *> S =
6281 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6285 if (std::optional<const SCEV *> S =
6286 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6292 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6298 assert(
GEP->getSourceElementType()->isSized() &&
6299 "GEP source element type must be sized");
6302 for (
Value *Index :
GEP->indices())
6307APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6310 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6313 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6315 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6318 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6336 return GetShiftedByZeros(TZ);
6346 return GetShiftedByZeros(TZ);
6350 if (
M->hasNoUnsignedWrap()) {
6353 for (
const SCEV *Operand :
M->operands().drop_front())
6361 for (
const SCEV *Operand :
M->operands())
6363 return GetShiftedByZeros(TZ);
6368 if (
N->hasNoUnsignedWrap())
6369 return GetGCDMultiple(
N);
6372 for (
const SCEV *Operand :
N->operands().drop_front())
6374 return GetShiftedByZeros(TZ);
6391 CtxI = &*F.getEntryBlock().begin();
6398 .allowEphemerals(
true))
6399 .countMinTrailingZeros();
6400 return GetShiftedByZeros(
Known);
6413 return getConstantMultipleImpl(S, CtxI);
6415 auto I = ConstantMultipleCache.find(S);
6416 if (
I != ConstantMultipleCache.end())
6419 APInt Result = getConstantMultipleImpl(S, CtxI);
6420 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6421 assert(InsertPair.second &&
"Should insert a new key");
6422 return InsertPair.first->second;
6439 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6442 if (std::optional<ConstantRange>
Range = CB->getRange())
6446 if (std::optional<ConstantRange>
Range =
A->getRange())
6449 return std::nullopt;
6456 UnsignedRanges.erase(AddRec);
6457 SignedRanges.erase(AddRec);
6458 ConstantMultipleCache.erase(AddRec);
6463getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6489 Value *Start, *Step;
6496 assert(L && L->getHeader() ==
P->getParent());
6509 case Instruction::AShr:
6510 case Instruction::LShr:
6511 case Instruction::Shl:
6526 KnownStep.getBitWidth() ==
BitWidth);
6529 auto MaxShiftAmt = KnownStep.getMaxValue();
6531 bool Overflow =
false;
6532 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6539 case Instruction::AShr: {
6547 if (KnownStart.isNonNegative())
6550 KnownStart.getMaxValue() + 1);
6551 if (KnownStart.isNegative())
6554 KnownEnd.getMaxValue() + 1);
6557 case Instruction::LShr: {
6566 KnownStart.getMaxValue() + 1);
6568 case Instruction::Shl: {
6572 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6573 return ConstantRange(KnownStart.getMinValue(),
6574 KnownEnd.getMaxValue() + 1);
6599 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6606ScalarEvolution::getRangeRefIter(
const SCEV *S,
6607 ScalarEvolution::RangeSignHint SignHint) {
6608 DenseMap<const SCEV *, ConstantRange> &Cache =
6609 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6612 SmallPtrSet<const SCEV *, 8> Seen;
6616 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6617 if (!Seen.
insert(Expr).second)
6650 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6651 const SCEV *
P = WorkList[
I];
6655 for (
const SCEV *
Op :
P->operands())
6668 if (!WorkList.
empty()) {
6673 getRangeRef(
P, SignHint);
6677 return getRangeRef(S, SignHint, 0);
6680const APInt *ScalarEvolution::getConstantAPIntOrNull(
const SCEV *S) {
6682 return &
C->getAPInt();
6690 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6691 DenseMap<const SCEV *, ConstantRange> &Cache =
6692 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6699 auto I = Cache.
find(S);
6700 if (
I != Cache.
end())
6704 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6709 return getRangeRefIter(S, SignHint);
6712 ConstantRange ConservativeResult(
BitWidth,
true);
6713 using OBO = OverflowingBinaryOperator;
6717 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6721 ConservativeResult =
6728 ConservativeResult = ConstantRange(
6744 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6751 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6758 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6763 return setRange(Cast, SignHint,
X);
6768 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6769 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6771 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6772 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6773 ConservativeResult =
6774 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6776 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6777 unsigned WrapType = OBO::AnyWrap;
6778 if (
Add->hasNoSignedWrap())
6779 WrapType |= OBO::NoSignedWrap;
6780 if (
Add->hasNoUnsignedWrap())
6781 WrapType |= OBO::NoUnsignedWrap;
6783 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6785 return setRange(
Add, SignHint,
6786 ConservativeResult.intersectWith(
X, RangeType));
6790 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6792 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6793 return setRange(
Mul, SignHint,
6794 ConservativeResult.intersectWith(
X, RangeType));
6798 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6799 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6800 return setRange(UDiv, SignHint,
6801 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6809 if (!UnsignedMinValue.
isZero())
6810 ConservativeResult = ConservativeResult.intersectWith(
6811 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6820 bool AllNonNeg =
true;
6821 bool AllNonPos =
true;
6822 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6829 ConservativeResult = ConservativeResult.intersectWith(
6834 ConservativeResult = ConservativeResult.intersectWith(
6843 const SCEV *MaxBEScev =
6857 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
6859 ConservativeResult =
6860 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6863 auto RangeFromFactoring = getRangeViaFactoring(
6865 ConservativeResult =
6866 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6872 const SCEV *SymbolicMaxBECount =
6877 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6878 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6879 ConservativeResult =
6880 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6885 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6895 ID = Intrinsic::umax;
6898 ID = Intrinsic::smax;
6902 ID = Intrinsic::umin;
6905 ID = Intrinsic::smin;
6912 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6913 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6915 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6916 return setRange(S, SignHint,
6917 ConservativeResult.intersectWith(
X, RangeType));
6926 ConservativeResult =
6927 ConservativeResult.intersectWith(*MDRange, RangeType);
6932 auto CR = getRangeForUnknownRecurrence(U);
6933 ConservativeResult = ConservativeResult.intersectWith(CR);
6944 if (
U->getType()->isPointerTy()) {
6947 unsigned PtrIdxDiff =
6948 DL.getPointerTypeSizeInBits(
U->getType()) -
BitWidth;
6949 NS = NS > PtrIdxDiff ? NS - PtrIdxDiff : 1;
6954 if (!
Known.Zero.getHiBits(NS).isZero())
6955 Known.Zero.setHighBits(NS);
6956 if (!
Known.One.getHiBits(NS).isZero())
6957 Known.One.setHighBits(NS);
6960 if (
Known.getMinValue() !=
Known.getMaxValue() + 1)
6961 ConservativeResult = ConservativeResult.intersectWith(
6962 ConstantRange(
Known.getMinValue(),
Known.getMaxValue() + 1),
6965 ConservativeResult = ConservativeResult.intersectWith(
6970 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6974 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
6975 DL, CanBeNull,
nullptr);
6991 ConservativeResult = ConservativeResult.intersectWith(
7001 return getRangeRef(AR, SignHint,
Depth + 1);
7005 ConstantRange RangeFromOps(
BitWidth,
false);
7007 for (
const auto &
Op :
Phi->operands()) {
7009 RangeFromOps = RangeFromOps.unionWith(OpRange);
7011 if (RangeFromOps.isFullSet())
7014 ConservativeResult =
7015 ConservativeResult.intersectWith(RangeFromOps, RangeType);
7021 if (
II->getIntrinsicID() == Intrinsic::vscale) {
7023 ConservativeResult = ConservativeResult.difference(Disallowed);
7026 return setRange(U, SignHint, std::move(ConservativeResult));
7032 return setRange(S, SignHint, std::move(ConservativeResult));
7040static std::pair<ConstantRange, bool>
7048 if (Step == 0 || MaxBECount == 0)
7049 return {StartRange,
true};
7055 return {ConstantRange::getFull(
BitWidth),
false};
7071 return {ConstantRange::getFull(
BitWidth),
false};
7084 APInt MovedBoundary;
7089 MovedBoundary = StartLower - std::move(
Offset);
7092 MovedBoundary = StartUpper + std::move(
Offset);
7096 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
7103 if (StartRange.
contains(MovedBoundary))
7104 return {ConstantRange::getFull(
BitWidth),
false};
7107 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7109 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7117std::pair<ConstantRange, SCEV::NoWrapFlags>
7118ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
7119 const APInt &MaxBECount) {
7123 "mismatched bit widths");
7132 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7134 StartSRange, MaxBECount,
7136 ConstantRange SR = SR1.unionWith(SR2);
7153ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7155 ScalarEvolution::RangeSignHint SignHint) {
7156 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7158 "This only works for non-self-wrapping AddRecs!");
7159 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7163 return ConstantRange::getFull(
BitWidth);
7171 return ConstantRange::getFull(
BitWidth);
7175 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7177 MaxItersWithoutWrap))
7178 return ConstantRange::getFull(
BitWidth);
7199 ConstantRange StartRange = getRangeRef(Start, SignHint);
7200 ConstantRange EndRange = getRangeRef(End, SignHint);
7201 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7205 return RangeBetween;
7210 return ConstantRange::getFull(
BitWidth);
7213 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7214 return RangeBetween;
7216 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7217 return RangeBetween;
7218 return ConstantRange::getFull(
BitWidth);
7223 const APInt &MaxBECount) {
7230 "mismatched bit widths");
7232 struct SelectPattern {
7233 Value *Condition =
nullptr;
7237 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7239 std::optional<unsigned> CastOp;
7253 CastOp = SCast->getSCEVType();
7254 S = SCast->getOperand();
7257 using namespace llvm::PatternMatch;
7264 Condition =
nullptr;
7296 bool isRecognized() {
return Condition !=
nullptr; }
7299 SelectPattern StartPattern(*
this,
BitWidth, Start);
7300 if (!StartPattern.isRecognized())
7301 return ConstantRange::getFull(
BitWidth);
7303 SelectPattern StepPattern(*
this,
BitWidth, Step);
7304 if (!StepPattern.isRecognized())
7305 return ConstantRange::getFull(
BitWidth);
7307 if (StartPattern.Condition != StepPattern.Condition) {
7311 return ConstantRange::getFull(
BitWidth);
7322 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7323 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7324 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7325 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7327 ConstantRange TrueRange =
7328 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7329 ConstantRange FalseRange =
7330 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7343 PDI && PDI->isDisjoint()) {
7358ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7371 SmallPtrSet<const SCEV *, 16> Visited;
7373 auto pushOp = [&](
const SCEV *S) {
7374 if (!Visited.
insert(S).second)
7377 if (Visited.
size() > 30) {
7388 while (!Worklist.
empty()) {
7390 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7391 if (!Bound || DT.dominates(Bound, DefI))
7398 return Bound ? Bound : &*F.getEntryBlock().begin();
7404 return getDefiningScopeBound(
Ops, Discard);
7407bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7409 if (
A->getParent() ==
B->getParent() &&
7414 auto *BLoop = LI.getLoopFor(
B->getParent());
7415 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7416 BLoop->getLoopPreheader() ==
A->getParent() &&
7418 A->getParent()->end()) &&
7426 SCEVPoisonCollector PC(
true);
7428 return PC.MaybePoison.
empty();
7431bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7441bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7458 for (
const Use &
Op :
I->operands()) {
7464 auto *DefI = getDefiningScopeBound(SCEVOps);
7465 return isGuaranteedToTransferExecutionTo(DefI,
I);
7468bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7470 if (isSCEVExprNeverPoison(
I))
7481 auto *ExitingBB =
L->getExitingBlock();
7485 SmallPtrSet<const Value *, 16> KnownPoison;
7494 while (!Worklist.
empty()) {
7497 for (
const Use &U :
Poison->uses()) {
7500 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7504 if (KnownPoison.
insert(PoisonUser).second)
7512ScalarEvolution::LoopProperties
7513ScalarEvolution::getLoopProperties(
const Loop *L) {
7514 using LoopProperties = ScalarEvolution::LoopProperties;
7516 auto Itr = LoopPropertiesCache.find(L);
7517 if (Itr == LoopPropertiesCache.end()) {
7520 return !
SI->isSimple();
7530 return I->mayWriteToMemory();
7533 LoopProperties LP = {
true,
7536 for (
auto *BB :
L->getBlocks())
7537 for (
auto &
I : *BB) {
7539 LP.HasNoAbnormalExits =
false;
7540 if (HasSideEffects(&
I))
7541 LP.HasNoSideEffects =
false;
7542 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7546 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7547 assert(InsertPair.second &&
"We just checked!");
7548 Itr = InsertPair.first;
7561const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7567 Stack.emplace_back(V,
false);
7568 while (!Stack.empty()) {
7569 auto E = Stack.back();
7570 Value *CurV = E.getPointer();
7578 const SCEV *CreatedSCEV =
nullptr;
7581 CreatedSCEV = createSCEV(CurV);
7586 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7590 insertValueToMap(CurV, CreatedSCEV);
7593 Stack.back().setInt(
true);
7596 Stack.emplace_back(
Op,
false);
7613 if (!DT.isReachableFromEntry(
I->getParent()))
7626 switch (BO->Opcode) {
7627 case Instruction::Add:
7628 case Instruction::Mul: {
7635 Ops.push_back(BO->
Op);
7639 Ops.push_back(BO->RHS);
7643 (BO->Opcode == Instruction::Add &&
7644 (NewBO->Opcode != Instruction::Add &&
7645 NewBO->Opcode != Instruction::Sub)) ||
7646 (BO->Opcode == Instruction::Mul &&
7647 NewBO->Opcode != Instruction::Mul)) {
7648 Ops.push_back(BO->LHS);
7653 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7656 Ops.push_back(BO->LHS);
7664 case Instruction::Sub:
7665 case Instruction::UDiv:
7666 case Instruction::URem:
7668 case Instruction::AShr:
7669 case Instruction::Shl:
7670 case Instruction::Xor:
7674 case Instruction::And:
7675 case Instruction::Or:
7679 case Instruction::LShr:
7686 Ops.push_back(BO->LHS);
7687 Ops.push_back(BO->RHS);
7691 switch (
U->getOpcode()) {
7692 case Instruction::Trunc:
7693 case Instruction::ZExt:
7694 case Instruction::SExt:
7695 case Instruction::PtrToAddr:
7696 case Instruction::PtrToInt:
7697 Ops.push_back(
U->getOperand(0));
7700 case Instruction::BitCast:
7702 Ops.push_back(
U->getOperand(0));
7707 case Instruction::SDiv:
7708 case Instruction::SRem:
7709 Ops.push_back(
U->getOperand(0));
7710 Ops.push_back(
U->getOperand(1));
7713 case Instruction::GetElementPtr:
7715 "GEP source element type must be sized");
7719 case Instruction::IntToPtr:
7722 case Instruction::PHI:
7753 Ops.push_back(CondICmp->getOperand(0));
7754 Ops.push_back(CondICmp->getOperand(1));
7774 case Instruction::Select: {
7776 auto CanSimplifyToUnknown = [
this,
U]() {
7794 if (CanSimplifyToUnknown())
7801 case Instruction::Call:
7802 case Instruction::Invoke:
7809 switch (
II->getIntrinsicID()) {
7810 case Intrinsic::abs:
7811 Ops.push_back(
II->getArgOperand(0));
7813 case Intrinsic::umax:
7814 case Intrinsic::umin:
7815 case Intrinsic::smax:
7816 case Intrinsic::smin:
7817 case Intrinsic::usub_sat:
7818 case Intrinsic::uadd_sat:
7819 Ops.push_back(
II->getArgOperand(0));
7820 Ops.push_back(
II->getArgOperand(1));
7822 case Intrinsic::start_loop_iterations:
7823 case Intrinsic::annotation:
7824 case Intrinsic::ptr_annotation:
7825 Ops.push_back(
II->getArgOperand(0));
7837const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7846 if (!DT.isReachableFromEntry(
I->getParent()))
7861 switch (BO->Opcode) {
7862 case Instruction::Add: {
7888 if (BO->Opcode == Instruction::Sub)
7896 if (BO->Opcode == Instruction::Sub)
7903 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7904 NewBO->Opcode != Instruction::Sub)) {
7914 case Instruction::Mul: {
7935 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7944 case Instruction::UDiv:
7948 case Instruction::URem:
7952 case Instruction::Sub: {
7955 Flags = getNoWrapFlagsFromUB(BO->
Op);
7960 Value *PtrLHS =
nullptr, *PtrRHS =
nullptr;
7963 if (HasPtrLHS || HasPtrRHS) {
7968 auto GetOp = [&](
bool HasPtr,
Value *PtrOp,
Value *OrigOp,
7969 bool BothPtr) ->
const SCEV * {
7972 const SCEV *PtrSCEV =
getSCEV(PtrOp);
7982 const SCEV *
L = GetOp(HasPtrLHS, PtrLHS, BO->LHS, HasPtrRHS);
7983 const SCEV *
R = GetOp(HasPtrRHS, PtrRHS, BO->RHS, HasPtrLHS);
7991 case Instruction::And:
7997 if (CI->isMinusOne())
7999 const APInt &
A = CI->getValue();
8005 unsigned LZ =
A.countl_zero();
8006 unsigned TZ =
A.countr_zero();
8011 APInt EffectiveMask =
8013 if ((LZ != 0 || TZ != 0) && !((~
A & ~
Known.Zero) & EffectiveMask)) {
8016 const SCEV *ShiftedLHS =
nullptr;
8020 unsigned MulZeros = OpC->getAPInt().countr_zero();
8021 unsigned GCD = std::min(MulZeros, TZ);
8026 const SCEV *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
8048 case Instruction::Or:
8057 case Instruction::Xor:
8060 if (CI->isMinusOne())
8069 if (LBO->getOpcode() == Instruction::And &&
8070 LCI->getValue() == CI->getValue())
8071 if (
const SCEVZeroExtendExpr *Z =
8074 const SCEV *Z0 =
Z->getOperand();
8081 if (CI->getValue().isMask(Z0TySize))
8087 APInt Trunc = CI->getValue().trunc(Z0TySize);
8096 case Instruction::Shl:
8114 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8123 ConstantInt *
X = ConstantInt::get(
8129 case Instruction::AShr:
8151 const SCEV *AddTruncateExpr =
nullptr;
8152 ConstantInt *ShlAmtCI =
nullptr;
8153 const SCEV *AddConstant =
nullptr;
8155 if (L &&
L->getOpcode() == Instruction::Add) {
8163 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8170 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8178 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8183 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8188 if (AddTruncateExpr && ShlAmtCI) {
8200 const APInt &ShlAmt = ShlAmtCI->
getValue();
8204 const SCEV *CompositeExpr =
8206 if (
L->getOpcode() != Instruction::Shl)
8207 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8216 switch (
U->getOpcode()) {
8217 case Instruction::Trunc:
8220 case Instruction::ZExt:
8223 case Instruction::SExt:
8233 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8234 Type *Ty =
U->getType();
8242 case Instruction::BitCast:
8248 case Instruction::PtrToAddr: {
8255 case Instruction::PtrToInt:
8259 case Instruction::IntToPtr:
8263 case Instruction::SDiv:
8270 case Instruction::SRem:
8277 case Instruction::GetElementPtr:
8280 case Instruction::PHI:
8283 case Instruction::Select:
8284 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8287 case Instruction::Call:
8288 case Instruction::Invoke:
8293 switch (
II->getIntrinsicID()) {
8294 case Intrinsic::abs:
8298 case Intrinsic::umax:
8302 case Intrinsic::umin:
8306 case Intrinsic::smax:
8310 case Intrinsic::smin:
8314 case Intrinsic::usub_sat: {
8315 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8316 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8320 case Intrinsic::uadd_sat: {
8321 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8322 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8326 case Intrinsic::start_loop_iterations:
8327 case Intrinsic::annotation:
8328 case Intrinsic::ptr_annotation:
8332 case Intrinsic::vscale:
8352 auto *ExitCountType = ExitCount->
getType();
8353 assert(ExitCountType->isIntegerTy());
8355 1 + ExitCountType->getScalarSizeInBits());
8368 auto CanAddOneWithoutOverflow = [&]() {
8370 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8381 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8411 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8412 assert(L->isLoopExiting(ExitingBlock) &&
8413 "Exiting block must actually branch out of the loop!");
8422 const auto *MaxExitCount =
8430 L->getExitingBlocks(ExitingBlocks);
8433 if (ExitingBlocks.
empty() ||
8449 const LoopGuards &Guards) {
8453 const SCEV *TCExpr =
8461 : (
unsigned)Multiple.getZExtValue();
8465 const SCEV *ExitCount) {
8487 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8488 assert(L->isLoopExiting(ExitingBlock) &&
8489 "Exiting block must actually branch out of the loop!");
8499 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8501 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8503 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8513 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8516 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8519 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8527 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8534 return getBackedgeTakenInfo(L).getExact(L,
this);
8536 return getBackedgeTakenInfo(L).getConstantMax(
this);
8538 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8545 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8550 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8554 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8564 for (
PHINode &PN : Header->phis())
8565 if (Visited.
insert(&PN).second)
8569ScalarEvolution::BackedgeTakenInfo &
8570ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8571 auto &BTI = getBackedgeTakenInfo(L);
8572 if (BTI.hasFullInfo())
8575 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8578 return Pair.first->second;
8580 BackedgeTakenInfo
Result =
8581 computeBackedgeTakenCount(L,
true);
8583 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8586ScalarEvolution::BackedgeTakenInfo &
8587ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8593 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8594 BackedgeTakenCounts.try_emplace(L);
8596 return Pair.first->second;
8601 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8608 if (
Result.hasAnyInfo()) {
8611 auto LoopUsersIt = LoopUsers.find(L);
8612 if (LoopUsersIt != LoopUsers.end())
8614 forgetMemoizedResults(ToForget);
8617 for (PHINode &PN :
L->getHeader()->phis())
8618 ConstantEvolutionLoopExitValue.erase(&PN);
8626 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8635 BackedgeTakenCounts.clear();
8636 PredicatedBackedgeTakenCounts.clear();
8637 BECountUsers.clear();
8638 LoopPropertiesCache.clear();
8639 ConstantEvolutionLoopExitValue.clear();
8640 ValueExprMap.clear();
8641 ValuesAtScopes.clear();
8642 ValuesAtScopesUsers.clear();
8643 LoopDispositions.clear();
8644 BlockDispositions.clear();
8645 UnsignedRanges.clear();
8646 SignedRanges.clear();
8647 ExprValueMap.clear();
8649 ConstantMultipleCache.clear();
8650 PredicatedSCEVRewrites.clear();
8652 FoldCacheUser.clear();
8654void ScalarEvolution::visitAndClearUsers(
8658 while (!Worklist.
empty()) {
8665 if (It != ValueExprMap.
end()) {
8667 eraseValueFromMap(It->first);
8669 ConstantEvolutionLoopExitValue.erase(PN);
8683 while (!LoopWorklist.
empty()) {
8687 forgetBackedgeTakenCounts(CurrL,
false);
8688 forgetBackedgeTakenCounts(CurrL,
true);
8691 PredicatedSCEVRewrites.remove_if(
8692 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8694 auto LoopUsersItr = LoopUsers.find(CurrL);
8695 if (LoopUsersItr != LoopUsers.end())
8700 visitAndClearUsers(Worklist, Visited, ToForget);
8702 LoopPropertiesCache.erase(CurrL);
8705 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8707 forgetMemoizedResults(ToForget);
8724 visitAndClearUsers(Worklist, Visited, ToForget);
8726 forgetMemoizedResults(ToForget);
8737 visitAndClearUsers(Worklist, Visited, ToForget);
8739 forgetMemoizedResults(ToForget);
8747 auto InvalidateValue = [&](
Value *Val) {
8751 struct InvalidationRootCollector {
8755 InvalidationRootCollector(
Loop *L) : L(L) {}
8757 bool follow(
const SCEV *S) {
8763 if (L->contains(AddRec->
getLoop()))
8768 bool isDone()
const {
return false; }
8771 InvalidationRootCollector
C(L);
8773 forgetMemoizedResults(
C.Roots);
8796 BlockDispositions.clear();
8797 LoopDispositions.clear();
8814 while (!Worklist.
empty()) {
8816 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8817 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8818 if (!LoopDispoRemoved && !BlockDispoRemoved)
8820 auto Users = SCEVUsers.find(Curr);
8821 if (
Users != SCEVUsers.end())
8834const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8838 if (!isComplete() || ExitNotTaken.
empty())
8849 for (
const auto &ENT : ExitNotTaken) {
8850 const SCEV *BECount = ENT.ExactNotTaken;
8853 "We should only have known counts for exiting blocks that dominate "
8856 Ops.push_back(BECount);
8861 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8862 "Predicate should be always true!");
8871const ScalarEvolution::ExitNotTakenInfo *
8872ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8873 const BasicBlock *ExitingBlock,
8874 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8875 for (
const auto &ENT : ExitNotTaken)
8876 if (ENT.ExitingBlock == ExitingBlock) {
8877 if (ENT.hasAlwaysTruePredicate())
8879 else if (Predicates) {
8889const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8891 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8892 if (!getConstantMax())
8895 for (
const auto &ENT : ExitNotTaken)
8896 if (!ENT.hasAlwaysTruePredicate()) {
8904 "No point in having a non-constant max backedge taken count!");
8905 return getConstantMax();
8908const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8910 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8918 for (
const auto &ENT : ExitNotTaken) {
8919 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8922 "We should only have known counts for exiting blocks that "
8928 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8929 "Predicate should be always true!");
8932 if (ExitCounts.
empty())
8941bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8943 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8944 return !ENT.hasAlwaysTruePredicate();
8946 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8962 this->ExactNotTaken = E = ConstantMaxNotTaken;
8963 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8968 "Exact is not allowed to be less precise than Constant Max");
8971 "Exact is not allowed to be less precise than Symbolic Max");
8974 "Symbolic Max is not allowed to be less precise than Constant Max");
8977 "No point in having a non-constant max backedge taken count!");
8979 for (
const auto PredList : PredLists)
8980 for (
const auto *
P : PredList) {
8988 "Backedge count should be int");
8991 "Max backedge count should be int");
9004ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
9006 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
9007 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
9008 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9010 ExitNotTaken.reserve(ExitCounts.
size());
9011 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
9012 std::back_inserter(ExitNotTaken),
9013 [&](
const EdgeExitInfo &EEI) {
9014 BasicBlock *ExitBB = EEI.first;
9015 const ExitLimit &EL = EEI.second;
9016 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
9017 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
9022 "No point in having a non-constant max backedge taken count!");
9026ScalarEvolution::BackedgeTakenInfo
9027ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
9028 bool AllowPredicates) {
9030 L->getExitingBlocks(ExitingBlocks);
9032 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9035 bool CouldComputeBECount =
true;
9037 const SCEV *MustExitMaxBECount =
nullptr;
9038 const SCEV *MayExitMaxBECount =
nullptr;
9039 bool MustExitMaxOrZero =
false;
9040 bool IsOnlyExit = ExitingBlocks.
size() == 1;
9051 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
9052 if (ExitIfTrue == CI->
isZero())
9056 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
9058 assert((AllowPredicates || EL.Predicates.empty()) &&
9059 "Predicated exit limit when predicates are not allowed!");
9064 ++NumExitCountsComputed;
9068 CouldComputeBECount =
false;
9075 "Exact is known but symbolic isn't?");
9076 ++NumExitCountsNotComputed;
9091 DT.dominates(ExitBB, Latch)) {
9092 if (!MustExitMaxBECount) {
9093 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9094 MustExitMaxOrZero = EL.MaxOrZero;
9097 EL.ConstantMaxNotTaken);
9101 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9104 EL.ConstantMaxNotTaken);
9108 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9112 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9118 for (
const auto &Pair : ExitCounts) {
9120 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9122 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9123 {
L, AllowPredicates});
9125 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9126 MaxBECount, MaxOrZero);
9129ScalarEvolution::ExitLimit
9130ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9131 bool IsOnlyExit,
bool AllowPredicates) {
9132 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9136 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9141 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9142 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9143 "It should have one successor in loop and one exit block!");
9154 if (!
L->contains(SBB)) {
9159 assert(Exit &&
"Exiting block must have at least one exit");
9160 return computeExitLimitFromSingleExitSwitch(
9161 L, SI, Exit, IsOnlyExit);
9168 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9169 bool AllowPredicates) {
9170 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9171 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9172 ControlsOnlyExit, AllowPredicates);
9175std::optional<ScalarEvolution::ExitLimit>
9176ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9177 bool ExitIfTrue,
bool ControlsOnlyExit,
9178 bool AllowPredicates) {
9180 (void)this->ExitIfTrue;
9181 (void)this->AllowPredicates;
9183 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9184 this->AllowPredicates == AllowPredicates &&
9185 "Variance in assumed invariant key components!");
9186 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9187 if (Itr == TripCountMap.end())
9188 return std::nullopt;
9192void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9194 bool ControlsOnlyExit,
9195 bool AllowPredicates,
9197 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9198 this->AllowPredicates == AllowPredicates &&
9199 "Variance in assumed invariant key components!");
9201 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9202 assert(InsertResult.second &&
"Expected successful insertion!");
9207ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9208 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9209 bool ControlsOnlyExit,
bool AllowPredicates) {
9211 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9215 ExitLimit EL = computeExitLimitFromCondImpl(
9216 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9217 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9221ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9222 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9223 bool ControlsOnlyExit,
bool AllowPredicates) {
9225 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9226 Cache, L, ExitCond, ExitIfTrue, AllowPredicates))
9227 return *LimitFromBinOp;
9233 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9234 if (EL.hasFullInfo() || !AllowPredicates)
9238 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9258 const WithOverflowInst *WO;
9273 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9274 ControlsOnlyExit, AllowPredicates);
9275 if (EL.hasAnyInfo())
9280 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9283std::optional<ScalarEvolution::ExitLimit>
9284ScalarEvolution::computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache,
9288 bool AllowPredicates) {
9297 return std::nullopt;
9301 ExitLimit EL0 = computeExitLimitFromCondCached(
9302 Cache, L, Op0, ExitIfTrue,
false, AllowPredicates);
9303 ExitLimit EL1 = computeExitLimitFromCondCached(
9304 Cache, L, Op1, ExitIfTrue,
false, AllowPredicates);
9309 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9314 if (EitherMayExit) {
9324 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9326 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9329 EL1.ConstantMaxNotTaken);
9331 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9333 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9336 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9340 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9341 BECount = EL0.ExactNotTaken;
9354 SymbolicMaxBECount =
9356 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9360ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9361 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9362 bool AllowPredicates) {
9374 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9376 if (EL.hasAnyInfo())
9379 auto *ExhaustiveCount =
9380 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9383 return ExhaustiveCount;
9385 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9388ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9390 bool ControlsOnlyExit,
bool AllowPredicates) {
9415 ConstantRange CompRange =
9433 InnerLHS = ZExt->getOperand();
9480 if (EL.hasAnyInfo())
9497 if (EL.hasAnyInfo())
return EL;
9529 ExitLimit EL = howManyLessThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9531 if (EL.hasAnyInfo())
9547 ExitLimit EL = howManyGreaterThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9549 if (EL.hasAnyInfo())
9560ScalarEvolution::ExitLimit
9561ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9563 BasicBlock *ExitingBlock,
9564 bool ControlsOnlyExit) {
9565 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9568 if (
Switch->getDefaultDest() == ExitingBlock)
9572 "Default case must not exit the loop!");
9578 if (EL.hasAnyInfo())
9590 "Evaluation of SCEV at constant didn't fold correctly?");
9594ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9604 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9611 auto MatchPositiveShift = [](
Value *
V,
Value *&OutLHS,
9613 unsigned &OutShiftAmt) {
9614 using namespace PatternMatch;
9616 ConstantInt *ShiftAmt;
9618 OutOpCode = Instruction::LShr;
9620 OutOpCode = Instruction::AShr;
9622 OutOpCode = Instruction::Shl;
9627 if (Amt == 0 || Amt >= OutLHS->getType()->getScalarSizeInBits())
9642 auto MatchShiftRecurrence = [&](
Value *
V, PHINode *&PNOut,
9644 unsigned &ShiftAmtOut) {
9645 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9661 if (MatchPositiveShift(
LHS, V, OpC, Amt)) {
9662 PostShiftOpCode = OpC;
9668 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9671 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9677 MatchPositiveShift(BEValue, OpLHS, OpCodeOut, ShiftAmtOut) &&
9684 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9690 if (!MatchShiftRecurrence(
LHS, PN, OpCode, ShiftAmt))
9702 ConstantInt *StableValue =
nullptr;
9707 case Instruction::AShr: {
9714 if (
Known.isNonNegative())
9715 StableValue = ConstantInt::get(Ty, 0);
9716 else if (
Known.isNegative())
9717 StableValue = ConstantInt::get(Ty, -1,
true);
9723 case Instruction::LShr:
9724 case Instruction::Shl:
9734 "Otherwise cannot be an operand to a branch instruction");
9736 if (
Result->isNullValue()) {
9745 if (OpCode == Instruction::LShr || OpCode == Instruction::AShr) {
9747 const SCEV *StartSCEV =
getSCEV(StartValue);
9751 unsigned RangeBTC =
divideCeil(ActiveBits, ShiftAmt);
9752 MaxBTC = std::min(MaxBTC, RangeBTC);
9756 const SCEV *UpperBound =
9774 if (
const Function *
F = CI->getCalledFunction())
9784 if (!L->contains(
I))
return false;
9789 return L->getHeader() ==
I->getParent();
9868 if (!
I)
return nullptr;
9882 std::vector<Constant*>
Operands(
I->getNumOperands());
9884 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9893 if (!
C)
return nullptr;
9915 if (IncomingVal != CurrentVal) {
9918 IncomingVal = CurrentVal;
9930ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9933 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9942 DenseMap<Instruction *, Constant *> CurrentIterVals;
9944 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9950 for (PHINode &
PHI : Header->phis()) {
9952 CurrentIterVals[&
PHI] = StartCST;
9954 if (!CurrentIterVals.
count(PN))
9955 return RetVal =
nullptr;
9961 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
9964 unsigned IterationNum = 0;
9966 for (; ; ++IterationNum) {
9967 if (IterationNum == NumIterations)
9968 return RetVal = CurrentIterVals[PN];
9972 DenseMap<Instruction *, Constant *> NextIterVals;
9977 NextIterVals[PN] = NextPHI;
9979 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
9985 for (
const auto &
I : CurrentIterVals) {
9987 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
9992 for (
const auto &
I : PHIsToCompute) {
9993 PHINode *
PHI =
I.first;
9996 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9999 if (NextPHI !=
I.second)
10000 StoppedEvolving =
false;
10005 if (StoppedEvolving)
10006 return RetVal = CurrentIterVals[PN];
10008 CurrentIterVals.swap(NextIterVals);
10012const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
10022 DenseMap<Instruction *, Constant *> CurrentIterVals;
10024 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
10027 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
10029 for (PHINode &
PHI : Header->phis()) {
10031 CurrentIterVals[&
PHI] = StartCST;
10033 if (!CurrentIterVals.
count(PN))
10041 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
10048 if (CondVal->getValue() ==
uint64_t(ExitWhen)) {
10049 ++NumBruteForceTripCountsComputed;
10054 DenseMap<Instruction *, Constant *> NextIterVals;
10060 for (
const auto &
I : CurrentIterVals) {
10062 if (!
PHI ||
PHI->getParent() != Header)
continue;
10065 for (PHINode *
PHI : PHIsToCompute) {
10067 if (NextPHI)
continue;
10069 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10072 CurrentIterVals.
swap(NextIterVals);
10080 auto &
Values = ValuesAtScopes[V];
10084 return LS.second ? LS.second :
SCEVUse(V);
10086 Values.emplace_back(L,
nullptr);
10089 SCEVUse C = computeSCEVAtScope(V, L);
10090 for (
auto &LS :
reverse(ValuesAtScopes[V]))
10091 if (LS.first == L) {
10097 ValuesAtScopesUsers[
C.getPointer()].push_back({L, V});
10124 switch (V->getSCEVType()) {
10157 assert(!
C->getType()->isPointerTy() &&
10158 "Can only have one pointer, and it must be last");
10183const SCEV *ScalarEvolution::getWithOperands(
const SCEV *S,
10184 SmallVectorImpl<SCEVUse> &NewOps) {
10218SCEVUse ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10219 switch (
V->getSCEVType()) {
10230 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10241 for (++i; i !=
e; ++i)
10281 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10291 for (++i; i !=
e; ++i) {
10296 return getWithOperands(V, NewOps);
10311 const Loop *CurrLoop = this->LI[
I->getParent()];
10322 if (BackedgeTakenCount->
isZero()) {
10323 Value *InitValue =
nullptr;
10324 bool MultipleInitValues =
false;
10330 MultipleInitValues =
true;
10335 if (!MultipleInitValues && InitValue)
10344 unsigned InLoopPred =
10355 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10369 SmallVector<Constant *, 4>
Operands;
10371 bool MadeImprovement =
false;
10386 MadeImprovement |= OrigV != OpV;
10391 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10396 if (!MadeImprovement)
10417const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10419 return stripInjectiveFunctions(ZExt->getOperand());
10421 return stripInjectiveFunctions(SExt->getOperand());
10439 assert(
A != 0 &&
"A must be non-zero.");
10455 if (MinTZ < Mult2 && L->getLoopPredecessor())
10457 if (MinTZ < Mult2) {
10480 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10500static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10506 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10507 << *AddRec <<
'\n');
10510 if (!LC || !MC || !
NC) {
10511 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10512 return std::nullopt;
10518 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10526 N =
N.sext(NewWidth);
10527 M = M.sext(NewWidth);
10528 L = L.sext(NewWidth);
10545 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10546 <<
", multiplied by " <<
T <<
'\n');
10555 std::optional<APInt>
Y) {
10557 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10560 return XW.
slt(YW) ? *
X : *
Y;
10563 return std::nullopt;
10564 return X ? *
X : *
Y;
10581 return std::nullopt;
10582 unsigned W =
X->getBitWidth();
10602static std::optional<APInt>
10608 return std::nullopt;
10611 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10612 std::optional<APInt>
X =
10615 return std::nullopt;
10620 return std::nullopt;
10635static std::optional<APInt>
10639 "Starting value of addrec should be 0");
10640 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10641 <<
Range <<
", addrec " << *AddRec <<
'\n');
10645 "Addrec's initial value should be in range");
10651 return std::nullopt;
10661 auto SolveForBoundary =
10662 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10665 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10666 << Bound <<
" (before multiplying by " << M <<
")\n");
10669 std::optional<APInt> SO;
10672 "signed overflow\n");
10676 "unsigned overflow\n");
10677 std::optional<APInt> UO =
10680 auto LeavesRange = [&] (
const APInt &
X) {
10683 if (
Range.contains(V0->getValue()))
10688 if (
Range.contains(
V1->getValue()))
10697 return {std::nullopt,
false};
10702 if (LeavesRange(*Min))
10703 return { Min,
true };
10704 std::optional<APInt> Max = Min == SO ? UO : SO;
10705 if (LeavesRange(*Max))
10706 return { Max,
true };
10709 return {std::nullopt,
true};
10716 auto SL = SolveForBoundary(
Lower);
10717 auto SU = SolveForBoundary(
Upper);
10720 if (!SL.second || !SU.second)
10721 return std::nullopt;
10764ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10766 bool ControlsOnlyExit,
10767 bool AllowPredicates) {
10778 if (
C->getValue()->isZero())
return C;
10782 const SCEVAddRecExpr *AddRec =
10785 if (!AddRec && AllowPredicates)
10791 if (!AddRec || AddRec->
getLoop() != L)
10802 return ExitLimit(R, R, R,
false, Predicates);
10860 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10890 const SCEV *
Exact =
10898 const SCEV *SymbolicMax =
10900 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10909 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10917 return ExitLimit(
E, M, S,
false, Predicates);
10920ScalarEvolution::ExitLimit
10921ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10929 if (!
C->getValue()->isZero())
10939std::pair<const BasicBlock *, const BasicBlock *>
10940ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10951 if (
const Loop *L = LI.getLoopFor(BB))
10952 return {
L->getLoopPredecessor(),
L->getHeader()};
10954 return {
nullptr, BB};
10963 if (
A ==
B)
return true;
10978 if (ComputesEqualValues(AI, BI))
10986 const SCEV *Op0, *Op1;
11005 auto TrivialCase = [&](
bool TriviallyTrue) {
11014 const SCEV *NewLHS, *NewRHS;
11038 return TrivialCase(
false);
11039 return TrivialCase(
true);
11058 RAdd->hasNoSignedWrap()) ||
11060 RAdd->hasNoUnsignedWrap())) {
11080 bool BothNUW = LMul->hasNoUnsignedWrap() && RMul->hasNoUnsignedWrap();
11081 bool BothNSW = LMul->hasNoSignedWrap() && RMul->hasNoSignedWrap();
11084 C->getAPInt().isStrictlyPositive()) ||
11108 const APInt &
RA = RC->getAPInt();
11110 bool SimplifiedByConstantRange =
false;
11115 return TrivialCase(
true);
11117 return TrivialCase(
false);
11126 Changed = SimplifiedByConstantRange =
true;
11130 if (!SimplifiedByConstantRange) {
11147 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
11153 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
11159 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
11165 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11185 return TrivialCase(
true);
11187 return TrivialCase(
false);
11292 auto NonRecursive = [OrNegative](
const SCEV *S) {
11294 return C->getAPInt().isPowerOf2() ||
11295 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11301 if (NonRecursive(S))
11311 const SCEV *S, uint64_t M,
11320 APInt C = Cst->getAPInt();
11321 return C.urem(M) == 0;
11327 const SCEV *SmodM =
11348 [&](
SCEVUse Op) { return isKnownMultipleOf(Op, M, Predicates); }))
11355 return isKnownMultipleOf(Op, M, Predicates);
11361 return isKnownMultipleOf(Op, M, Predicates);
11368 for (
auto *
A : *Predicates)
11369 if (
A->implies(
P, *
this))
11382std::pair<const SCEV *, const SCEV *>
11385 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11387 return { Start, Start };
11389 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11398 getUsedLoops(LHS, LoopsUsed);
11399 getUsedLoops(RHS, LoopsUsed);
11401 if (LoopsUsed.
empty())
11406 for (
const auto *L1 : LoopsUsed)
11407 for (
const auto *L2 : LoopsUsed)
11408 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11409 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11410 "Domination relationship is not a linear order");
11440 SplitRHS.second) &&
11450 isKnownPredicateViaSplitting(Pred, LHS, RHS) ||
11451 isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11461 return std::nullopt;
11476 if (KnownWithoutContext)
11477 return KnownWithoutContext;
11484 return std::nullopt;
11490 const Loop *L = LHS->getLoop();
11495std::optional<ScalarEvolution::MonotonicPredicateType>
11498 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11504 auto ResultSwapped =
11507 assert(*ResultSwapped != *Result &&
11508 "monotonicity should flip as we flip the predicate");
11515std::optional<ScalarEvolution::MonotonicPredicateType>
11516ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11530 return std::nullopt;
11534 "Should be greater or less!");
11538 if (!LHS->hasNoUnsignedWrap())
11539 return std::nullopt;
11543 "Relational predicate is either signed or unsigned!");
11544 if (!
LHS->hasNoSignedWrap())
11545 return std::nullopt;
11547 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11555 return std::nullopt;
11558std::optional<ScalarEvolution::LoopInvariantPredicate>
11565 return std::nullopt;
11572 if (!ArLHS || ArLHS->
getLoop() != L)
11573 return std::nullopt;
11577 return std::nullopt;
11603 return std::nullopt;
11640 return std::nullopt;
11643std::optional<ScalarEvolution::LoopInvariantPredicate>
11648 Pred, LHS, RHS, L, CtxI, MaxIter))
11658 Pred, LHS, RHS, L, CtxI,
Op))
11660 return std::nullopt;
11663std::optional<ScalarEvolution::LoopInvariantPredicate>
11678 return std::nullopt;
11685 if (!AR || AR->
getLoop() != L)
11686 return std::nullopt;
11691 Pred = Pred.dropSameSign();
11695 return std::nullopt;
11701 if (Step != One && Step != MinusOne)
11702 return std::nullopt;
11708 return std::nullopt;
11714 return std::nullopt;
11722 if (Step == MinusOne)
11726 return std::nullopt;
11732bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11738 auto CheckRange = [&](
bool IsSigned) {
11741 return RangeLHS.
icmp(Pred, RangeRHS);
11750 if (CheckRange(
true) || CheckRange(
false))
11759bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11768 SCEVUse XNonConstOp, XConstOp;
11769 SCEVUse YNonConstOp, YConstOp;
11773 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11776 XFlagsPresent = ExpectedFlags;
11781 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11784 YFlagsPresent = ExpectedFlags;
11787 if (YNonConstOp != XNonConstOp)
11795 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11798 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11858bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11879bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11880 const SCEV *
LHS,
const SCEV *
RHS) {
11885 return any_of(*BB, [&](
const Instruction &
I) {
11886 using namespace llvm::PatternMatch;
11891 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11905 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11910 "This cannot be done on broken IR!");
11913 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11922 if (LoopContinuePredicate &&
11923 isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->
getCondition(),
11924 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11929 if (WalkingBEDominatingConds)
11935 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11936 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11943 const SCEV *LoopCounter =
11951 for (
auto &AssumeVH : AC.assumptions()) {
11958 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11962 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11965 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11966 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11967 assert(DTN &&
"should reach the loop header before reaching the root!");
11970 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11988 if (isImpliedCond(Pred, LHS, RHS, ContBr->
getCondition(),
12001 if (!DT.isReachableFromEntry(BB))
12005 "This cannot be done on broken IR!");
12013 const bool ProvingStrictComparison =
12015 bool ProvedNonStrictComparison =
false;
12016 bool ProvedNonEquality =
false;
12019 if (!ProvedNonStrictComparison)
12020 ProvedNonStrictComparison = Fn(NonStrictPredicate);
12021 if (!ProvedNonEquality)
12023 if (ProvedNonStrictComparison && ProvedNonEquality)
12028 if (ProvingStrictComparison) {
12030 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
12032 if (SplitAndProve(ProofFn))
12037 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
12039 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
12041 if (ProvingStrictComparison) {
12043 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
12045 if (SplitAndProve(ProofFn))
12054 const Loop *ContainingLoop = LI.getLoopFor(BB);
12056 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
12060 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
12061 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
12064 if (!BlockEntryPredicate)
12073 for (
auto &AssumeVH : AC.assumptions()) {
12077 if (!DT.dominates(CI, BB))
12080 if (ProveViaCond(CI->getArgOperand(0),
false))
12086 F.getParent(), Intrinsic::experimental_guard);
12088 for (
const auto *GU : GuardDecl->users())
12090 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
12091 if (ProveViaCond(Guard->getArgOperand(0),
false))
12106 "LHS is not available at Loop Entry");
12108 "RHS is not available at Loop Entry");
12110 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
12121 if (FoundCondValue ==
12125 if (!PendingLoopPredicates.insert(FoundCondValue).second)
12129 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
12132 const Value *Op0, *Op1;
12135 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
12139 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
12140 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
12144 if (!ICI)
return false;
12148 CmpPredicate FoundPred;
12157 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
12160bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
12161 const SCEV *
RHS, CmpPredicate FoundPred,
12162 const SCEV *FoundLHS,
const SCEV *FoundRHS,
12163 const Instruction *CtxI) {
12173 auto *WideType = FoundLHS->
getType();
12185 TruncFoundLHS, TruncFoundRHS, CtxI))
12211 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
12215bool ScalarEvolution::isImpliedCondBalancedTypes(
12220 "Types should be balanced!");
12227 if (FoundLHS == FoundRHS)
12231 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12243 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12260 LHS, FoundLHS, FoundRHS, CtxI);
12262 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12284 assert(P1 != P2 &&
"Handled earlier!");
12288 if (IsSignFlippedPredicate(Pred, FoundPred)) {
12292 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12295 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
12296 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
12297 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12302 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12313 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12314 CanonicalRHS, CanonicalFoundLHS,
12315 CanonicalFoundRHS);
12320 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12321 CanonicalRHS, CanonicalFoundLHS,
12322 CanonicalFoundRHS);
12329 const SCEVConstant *
C =
nullptr;
12330 const SCEV *
V =
nullptr;
12348 if (Min ==
C->getAPInt()) {
12353 APInt SharperMin = Min + 1;
12356 case ICmpInst::ICMP_SGE:
12357 case ICmpInst::ICMP_UGE:
12360 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12365 case ICmpInst::ICMP_SGT:
12366 case ICmpInst::ICMP_UGT:
12376 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12381 case ICmpInst::ICMP_SLE:
12382 case ICmpInst::ICMP_ULE:
12383 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12384 LHS, V, getConstant(SharperMin), CtxI))
12388 case ICmpInst::ICMP_SLT:
12389 case ICmpInst::ICMP_ULT:
12390 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12391 LHS, V, getConstant(Min), CtxI))
12405 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12409 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12412 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12428std::optional<APInt>
12435 APInt DiffMul(BW, 1);
12438 for (
unsigned I = 0;
I < 8; ++
I) {
12447 if (LAR->getLoop() != MAR->getLoop())
12448 return std::nullopt;
12452 if (!LAR->isAffine() || !MAR->isAffine())
12453 return std::nullopt;
12455 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12456 return std::nullopt;
12458 Less = LAR->getStart();
12459 More = MAR->getStart();
12464 auto MatchConstMul =
12465 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12470 return std::nullopt;
12472 if (
auto MatchedMore = MatchConstMul(More)) {
12473 if (
auto MatchedLess = MatchConstMul(
Less)) {
12474 if (MatchedMore->second == MatchedLess->second) {
12475 More = MatchedMore->first;
12476 Less = MatchedLess->first;
12477 DiffMul *= MatchedMore->second;
12488 Diff +=
C->getAPInt() * DiffMul;
12491 Diff -=
C->getAPInt() * DiffMul;
12494 Multiplicity[S] +=
Mul;
12496 auto Decompose = [&](
const SCEV *S,
int Mul) {
12503 Decompose(More, 1);
12504 Decompose(
Less, -1);
12508 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12509 for (
const auto &[S,
Mul] : Multiplicity) {
12514 return std::nullopt;
12516 }
else if (
Mul == -1) {
12518 return std::nullopt;
12521 return std::nullopt;
12525 if (NewMore == More || NewLess ==
Less)
12526 return std::nullopt;
12532 if (!More && !
Less)
12536 if (!More || !
Less)
12537 return std::nullopt;
12541 return std::nullopt;
12544bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12566 const auto *Latch = L->getLoopLatch();
12569 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12578 const auto *Latch = L->getLoopLatch();
12581 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12591bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12594 const SCEV *FoundLHS,
12595 const SCEV *FoundRHS) {
12604 if (!AddRecFoundLHS)
12611 const Loop *
L = AddRecFoundLHS->getLoop();
12612 if (L != AddRecLHS->getLoop())
12651 if (!RDiff || *LDiff != *RDiff)
12654 if (LDiff->isMinValue())
12657 APInt FoundRHSLimit;
12660 FoundRHSLimit = -(*RDiff);
12672bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12673 const SCEV *
RHS,
const SCEV *FoundLHS,
12674 const SCEV *FoundRHS,
unsigned Depth) {
12675 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12679 bool Erased = PendingMerges.erase(LPhi);
12680 assert(Erased &&
"Failed to erase LPhi!");
12684 bool Erased = PendingMerges.erase(RPhi);
12685 assert(Erased &&
"Failed to erase RPhi!");
12693 if (!PendingMerges.insert(Phi).second)
12707 if (!PendingMerges.insert(Phi).second)
12713 if (!LPhi && !RPhi)
12724 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12728 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12729 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12730 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12731 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12734 if (RPhi && RPhi->getParent() == LBB) {
12741 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12742 if (!ProvedEasily(L, R))
12753 auto *RLoop = RAR->
getLoop();
12754 auto *Predecessor = RLoop->getLoopPredecessor();
12755 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12757 if (!ProvedEasily(L1, RAR->
getStart()))
12759 auto *Latch = RLoop->getLoopLatch();
12760 assert(Latch &&
"Loop with AddRec with no latch?");
12781 if (
auto *
Loop = LI.getLoopFor(LBB))
12784 if (!ProvedEasily(L,
RHS))
12791bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12794 const SCEV *FoundLHS,
12795 const SCEV *FoundRHS) {
12798 if (
RHS == FoundRHS) {
12803 if (
LHS != FoundLHS)
12810 Value *Shiftee, *ShiftValue;
12812 using namespace PatternMatch;
12813 if (
match(SUFoundRHS->getValue(),
12815 auto *ShifteeS =
getSCEV(Shiftee);
12833bool ScalarEvolution::isImpliedCondOperandsViaMatchingDiff(
12834 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12835 const SCEV *FoundRHS) {
12867 const SCEV *FoundDiff =
getMinusSCEV(FoundLHS, FoundRHS);
12875 return Diff == FoundDiff;
12878bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12880 const SCEV *FoundLHS,
12881 const SCEV *FoundRHS,
12882 const Instruction *CtxI) {
12883 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12885 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12887 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12888 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12890 isImpliedCondOperandsViaMatchingDiff(Pred,
LHS,
RHS, FoundLHS,
12892 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12896template <
typename MinMaxExprType>
12898 const SCEV *Candidate) {
12903 return is_contained(MinMaxExpr->operands(), Candidate);
12916 const SCEV *LStart, *RStart, *Step;
13014bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
13016 const SCEV *FoundLHS,
13017 const SCEV *FoundRHS,
13021 "LHS and RHS have different sizes?");
13024 "FoundLHS and FoundRHS have different sizes?");
13058 auto GetOpFromSExt = [&](
const SCEV *S) ->
const SCEV * {
13060 return Ext->getOperand();
13067 auto *OrigLHS =
LHS;
13068 auto *OrigFoundLHS = FoundLHS;
13069 LHS = GetOpFromSExt(
LHS);
13070 FoundLHS = GetOpFromSExt(FoundLHS);
13073 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
13076 FoundRHS,
Depth + 1);
13089 if (!LHSAddExpr->hasNoSignedWrap())
13092 SCEVUse LL = LHSAddExpr->getOperand(0);
13093 SCEVUse LR = LHSAddExpr->getOperand(1);
13097 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
13098 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
13103 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
13109 using namespace llvm::PatternMatch;
13128 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
13136 auto *DTy = Denominator->getType();
13137 auto *FRHSTy = FoundRHS->
getType();
13138 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
13157 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
13168 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
13170 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
13178 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
13211bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
13215 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
13219 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
13222bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
13225 const SCEV *FoundLHS,
13226 const SCEV *FoundRHS) {
13262 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
13268bool ScalarEvolution::isImpliedCondOperandsViaRanges(
13269 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
13270 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13284 ConstantRange FoundLHSRange =
13288 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13295 return LHSRange.
icmp(Pred, ConstRHS);
13298bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13299 bool IsSigned,
bool Invert) {
13306 APInt MaxRHS = getRangeMax(
RHS,
true, Invert);
13311 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13314 APInt MaxRHS = getRangeMax(
RHS,
false, Invert);
13319 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13332ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
const SCEV *Stride,
13334 bool IsSigned,
bool Invert) {
13349 APInt MinStart = getRangeMin(Start, IsSigned, Invert);
13362 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13368 APInt MaxEnd = getRangeMax(End, IsSigned, Invert);
13374 :
APIntOps::umax(MaxEnd, MinStart);
13376 APInt Delta = MaxEnd - MinStart;
13380 const SCEV *DeltaExpr =
13388ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13389 const Loop *L,
bool IsSigned,
13390 bool ControlsOnlyExit,
bool AllowPredicates) {
13394 bool PredicatedIV =
false;
13399 auto canProveNUW = [&]() {
13402 if (!ControlsOnlyExit)
13423 Limit = Limit.
zext(OuterBitWidth);
13435 Type *Ty = ZExt->getType();
13446 if (!
IV && AllowPredicates) {
13451 PredicatedIV =
true;
13455 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13469 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13472 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13473 const SCEV *GuardedStride = Stride;
13476 bool IVMayOverflow =
true;
13480 if (!PositiveStride) {
13483 GuardedStride = LoopGuardedStride;
13484 PositiveStride =
true;
13491 if (!PositiveStride) {
13543 auto wouldZeroStrideBeUB = [&]() {
13555 if (!wouldZeroStrideBeUB()) {
13562 IVMayOverflow = canIVOverflowOnLT(
RHS, GuardedStride, IsSigned);
13563 if (IVMayOverflow && !NoWrap)
13576 const SCEV *
Start =
IV->getStart();
13582 const SCEV *OrigStart =
Start;
13583 const SCEV *OrigRHS =
RHS;
13584 if (
Start->getType()->isPointerTy()) {
13599 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13600 any(RHSAddRec->getNoWrapFlags())) {
13613 const SCEV *RHSStart = RHSAddRec->getStart();
13614 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13626 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13635 BECountIfBackedgeTaken =
13661 bool AddingStrideMinusOneMayOverflow = IVMayOverflow && [&] {
13707 if (Start == Stride || Start ==
getMinusSCEV(Stride, One)) {
13720 auto *OrigStartMinusStride =
getMinusSCEV(OrigStart, Stride);
13727 if ((!AddingStrideMinusOneMayOverflow ||
13759 const SCEV *Numerator =
13765 auto canProveRHSGreaterThanEqualStart = [&]() {
13784 const SCEV *StartMinusOne =
13791 if (canProveRHSGreaterThanEqualStart()) {
13806 BECountIfBackedgeTaken =
13811 if (!AddingStrideMinusOneMayOverflow) {
13823 const SCEV *ConstantMaxBECount;
13824 bool MaxOrZero =
false;
13826 ConstantMaxBECount = BECount;
13831 ConstantMaxBECount = BECountIfBackedgeTaken;
13834 ConstantMaxBECount = computeMaxBECountForLT(
13843 const SCEV *SymbolicMaxBECount =
13845 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13849ScalarEvolution::ExitLimit ScalarEvolution::howManyGreaterThans(
13850 const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
bool IsSigned,
13851 bool ControlsOnlyExit,
bool AllowPredicates) {
13858 if (!
IV && AllowPredicates)
13865 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13869 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13882 bool MayAddOverflow =
false;
13883 const SCEV *
Start =
IV->getStart();
13884 const SCEV *End =
RHS;
13885 if (!Stride->
isOne() &&
13886 canIVOverflowOnLT(
RHS, Stride, IsSigned,
true)) {
13889 MayAddOverflow =
true;
13902 if (
Start->getType()->isPointerTy()) {
13904 "Start, End and RHS all must be pointers");
13919 const SCEV *BECount;
13920 if (MayAddOverflow) {
13936 const SCEV *ConstantMaxBECount =
13939 : computeMaxBECountForLT(Start, Stride,
RHS,
13944 ConstantMaxBECount = BECount;
13945 const SCEV *SymbolicMaxBECount =
13948 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
13954 if (
Range.isFullSet())
13959 if (!SC->getValue()->isZero()) {
13965 return ShiftedAddRec->getNumIterationsInRange(
13966 Range.subtract(SC->getAPInt()), SE);
13997 APInt ExitVal = (End +
A).udiv(
A);
14010 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
14011 "Linear scev computation is off in a bad way!");
14042 assert(!
Last->isZero() &&
"Recurrency with zero step?");
14075 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14077 SE->ConstantEvolutionLoopExitValue.erase(PN);
14078 SE->eraseValueFromMap(getValPtr());
14082void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
14083 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
14093 : CallbackVH(
V), SE(se) {}
14102 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
14104 LoopDispositions(64), BlockDispositions(64) {
14116 F.getParent(), Intrinsic::experimental_guard);
14117 HasGuards = GuardDecl && !GuardDecl->use_empty();
14121 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
14122 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
14123 ValueExprMap(
std::
move(Arg.ValueExprMap)),
14124 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
14125 PendingMerges(
std::
move(Arg.PendingMerges)),
14126 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
14127 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
14128 PredicatedBackedgeTakenCounts(
14129 std::
move(Arg.PredicatedBackedgeTakenCounts)),
14130 BECountUsers(
std::
move(Arg.BECountUsers)),
14131 ConstantEvolutionLoopExitValue(
14132 std::
move(Arg.ConstantEvolutionLoopExitValue)),
14133 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
14134 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
14135 LoopDispositions(
std::
move(Arg.LoopDispositions)),
14136 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
14137 BlockDispositions(
std::
move(Arg.BlockDispositions)),
14138 SCEVUsers(
std::
move(Arg.SCEVUsers)),
14139 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
14140 SignedRanges(
std::
move(Arg.SignedRanges)),
14141 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
14142 UniquePreds(
std::
move(Arg.UniquePreds)),
14143 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
14144 ConstantSCEVs(
std::
move(Arg.ConstantSCEVs)),
14145 LoopUsers(
std::
move(Arg.LoopUsers)),
14146 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
14147 FirstUnknown(Arg.FirstUnknown) {
14148 Arg.FirstUnknown =
nullptr;
14157 Tmp->~SCEVUnknown();
14159 FirstUnknown =
nullptr;
14161 ExprValueMap.clear();
14162 ValueExprMap.clear();
14164 BackedgeTakenCounts.clear();
14165 PredicatedBackedgeTakenCounts.clear();
14167 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
14168 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
14169 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
14170 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
14192 L->getHeader()->printAsOperand(OS,
false);
14196 L->getExitingBlocks(ExitingBlocks);
14197 if (ExitingBlocks.
size() != 1)
14198 OS <<
"<multiple exits> ";
14202 OS <<
"backedge-taken count is ";
14205 OS <<
"Unpredictable backedge-taken count.";
14208 if (ExitingBlocks.
size() > 1)
14209 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14210 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
14218 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
14221 OS <<
"\n Predicates:\n";
14222 for (
const auto *
P : Predicates)
14230 L->getHeader()->printAsOperand(OS,
false);
14235 OS <<
"constant max backedge-taken count is ";
14238 OS <<
", actual taken count either this or zero.";
14240 OS <<
"Unpredictable constant max backedge-taken count. ";
14245 L->getHeader()->printAsOperand(OS,
false);
14250 OS <<
"symbolic max backedge-taken count is ";
14253 OS <<
", actual taken count either this or zero.";
14255 OS <<
"Unpredictable symbolic max backedge-taken count. ";
14259 if (ExitingBlocks.
size() > 1)
14260 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14261 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
14271 OS <<
"\n predicated symbolic max exit count for "
14272 << ExitingBlock->
getName() <<
": ";
14274 OS <<
"\n Predicates:\n";
14275 for (
const auto *
P : Predicates)
14286 L->getHeader()->printAsOperand(OS,
false);
14289 OS <<
"Predicated backedge-taken count is ";
14292 OS <<
"Unpredictable predicated backedge-taken count.";
14294 OS <<
" Predicates:\n";
14295 for (
const auto *
P : Preds)
14300 auto *PredConstantMax =
14302 if (PredConstantMax != ConstantBTC) {
14304 L->getHeader()->printAsOperand(OS,
false);
14307 OS <<
"Predicated constant max backedge-taken count is ";
14310 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14312 OS <<
" Predicates:\n";
14313 for (
const auto *
P : Preds)
14318 auto *PredSymbolicMax =
14320 if (SymbolicBTC != PredSymbolicMax) {
14322 L->getHeader()->printAsOperand(OS,
false);
14325 OS <<
"Predicated symbolic max backedge-taken count is ";
14328 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14330 OS <<
" Predicates:\n";
14331 for (
const auto *
P : Preds)
14337 L->getHeader()->printAsOperand(OS,
false);
14364 OS <<
"Computable";
14374 OS <<
"DoesNotDominate";
14380 OS <<
"ProperlyDominates";
14397 OS <<
"Classifying expressions for: ";
14398 F.printAsOperand(OS,
false);
14413 const Loop *L = LI.getLoopFor(
I.getParent());
14428 OS <<
"\t\t" "Exits: ";
14431 OS <<
"<<Unknown>>";
14437 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14439 Iter->getHeader()->printAsOperand(OS,
false);
14447 InnerL->getHeader()->printAsOperand(OS,
false);
14458 OS <<
"Determining loop execution counts for: ";
14459 F.printAsOperand(OS,
false);
14467 auto &
Values = LoopDispositions[S];
14468 for (
auto &V :
Values) {
14469 if (V.getPointer() == L)
14474 auto &Values2 = LoopDispositions[S];
14476 if (V.getPointer() == L) {
14485ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14503 if (L->contains(AR->
getLoop()) &&
14505 [&](
const SCEV *
Op) { return isLoopUniform(Op, L); }))
14510 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14511 " dominate the contained loop's header?");
14538 bool HasVarying =
false;
14539 bool HasUniform =
false;
14581 auto &
Values = BlockDispositions[S];
14582 for (
auto &V :
Values) {
14583 if (V.getPointer() == BB)
14588 auto &Values2 = BlockDispositions[S];
14590 if (V.getPointer() == BB) {
14599ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14628 bool Proper =
true;
14639 if (Instruction *
I =
14641 if (
I->getParent() == BB)
14643 if (DT.properlyDominates(
I->getParent(), BB))
14666void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14669 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14670 auto It = BECounts.find(L);
14671 if (It != BECounts.end()) {
14672 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14673 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14675 auto UserIt = BECountUsers.find(S);
14676 assert(UserIt != BECountUsers.end());
14681 BECounts.erase(It);
14689 while (!Worklist.
empty()) {
14691 auto Users = SCEVUsers.find(Curr);
14692 if (
Users != SCEVUsers.end())
14693 for (
const auto *User :
Users->second)
14694 if (ToForget.
insert(User).second)
14698 for (
const auto *S : ToForget)
14699 forgetMemoizedResultsImpl(S);
14701 PredicatedSCEVRewrites.remove_if(
14702 [&](
const auto &Entry) {
return ToForget.count(
Entry.first.first); });
14705void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14706 LoopDispositions.erase(S);
14707 BlockDispositions.erase(S);
14708 UnsignedRanges.erase(S);
14709 SignedRanges.erase(S);
14710 HasRecMap.erase(S);
14711 ConstantMultipleCache.erase(S);
14714 UnsignedWrapViaInductionTried.erase(AR);
14715 SignedWrapViaInductionTried.erase(AR);
14718 auto ExprIt = ExprValueMap.find(S);
14719 if (ExprIt != ExprValueMap.end()) {
14720 for (
Value *V : ExprIt->second) {
14721 auto ValueIt = ValueExprMap.find_as(V);
14722 if (ValueIt != ValueExprMap.end())
14723 ValueExprMap.erase(ValueIt);
14725 ExprValueMap.erase(ExprIt);
14728 auto ScopeIt = ValuesAtScopes.find(S);
14729 if (ScopeIt != ValuesAtScopes.end()) {
14730 for (
const auto &Pair : ScopeIt->second)
14732 llvm::erase(ValuesAtScopesUsers[Pair.second.getPointer()],
14733 std::make_pair(Pair.first, S));
14734 ValuesAtScopes.erase(ScopeIt);
14737 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14738 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14739 for (
const auto &Pair : ScopeUserIt->second)
14742 llvm::erase_if(ValuesAtScopes[Pair.second], [&](
const auto &LS) {
14743 return LS.first == Pair.first && LS.second.getPointer() == S;
14745 ValuesAtScopesUsers.erase(ScopeUserIt);
14748 auto BEUsersIt = BECountUsers.find(S);
14749 if (BEUsersIt != BECountUsers.end()) {
14751 auto Copy = BEUsersIt->second;
14752 for (
const auto &Pair : Copy)
14753 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14754 BECountUsers.erase(BEUsersIt);
14757 auto FoldUser = FoldCacheUser.find(S);
14758 if (FoldUser != FoldCacheUser.end())
14759 for (
auto &KV : FoldUser->second)
14760 FoldCache.erase(KV);
14761 FoldCacheUser.erase(S);
14765ScalarEvolution::getUsedLoops(
const SCEV *S,
14767 struct FindUsedLoops {
14768 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14769 : LoopsUsed(LoopsUsed) {}
14770 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14771 bool follow(
const SCEV *S) {
14777 bool isDone()
const {
return false; }
14780 FindUsedLoops
F(LoopsUsed);
14781 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14784void ScalarEvolution::getReachableBlocks(
14787 Worklist.
push_back(&F.getEntryBlock());
14788 while (!Worklist.
empty()) {
14790 if (!Reachable.
insert(BB).second)
14798 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14805 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14809 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14844 SCEVMapper SCM(SE2);
14846 SE2.getReachableBlocks(ReachableBlocks, F);
14848 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14866 while (!LoopStack.
empty()) {
14872 if (!ReachableBlocks.
contains(L->getHeader()))
14877 auto It = BackedgeTakenCounts.find(L);
14878 if (It == BackedgeTakenCounts.end())
14882 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14902 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14903 if (Delta && !Delta->
isZero()) {
14904 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14905 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14906 dbgs() <<
"New: " << *NewBECount <<
"\n";
14907 dbgs() <<
"Delta: " << *Delta <<
"\n";
14915 while (!Worklist.
empty()) {
14917 if (ValidLoops.
insert(L).second)
14918 Worklist.
append(L->begin(), L->end());
14920 for (
const auto &KV : ValueExprMap) {
14925 "AddRec references invalid loop");
14930 auto It = ExprValueMap.find(KV.second);
14931 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14932 dbgs() <<
"Value " << *KV.first
14933 <<
" is in ValueExprMap but not in ExprValueMap\n";
14938 if (!ReachableBlocks.
contains(
I->getParent()))
14940 const SCEV *OldSCEV = SCM.visit(KV.second);
14942 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14943 if (Delta && !Delta->
isZero()) {
14944 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14945 <<
"Old: " << *OldSCEV <<
"\n"
14946 <<
"New: " << *NewSCEV <<
"\n"
14947 <<
"Delta: " << *Delta <<
"\n";
14953 for (
const auto &KV : ExprValueMap) {
14954 for (
Value *V : KV.second) {
14955 const SCEV *S = ValueExprMap.lookup(V);
14957 dbgs() <<
"Value " << *V
14958 <<
" is in ExprValueMap but not in ValueExprMap\n";
14961 if (S != KV.first) {
14962 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14963 << *KV.first <<
"\n";
14970 for (
const auto &S : UniqueSCEVs) {
14975 auto It = SCEVUsers.find(
Op);
14976 if (It != SCEVUsers.end() && It->second.count(&S))
14978 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14979 <<
" is not being tracked!\n";
14985 for (
const auto &ValueAndVec : ValuesAtScopes) {
14987 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14988 const Loop *L = LoopAndValueAtScope.first;
14989 SCEVUse ValueAtScope = LoopAndValueAtScope.second;
14991 auto It = ValuesAtScopesUsers.find(ValueAtScope.
getPointer());
14992 if (It != ValuesAtScopesUsers.end() &&
14995 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14996 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
15002 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
15003 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
15004 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
15005 const Loop *L = LoopAndValue.first;
15006 const SCEV *
Value = LoopAndValue.second;
15008 auto It = ValuesAtScopes.find(
Value);
15011 if (It != ValuesAtScopes.end() &&
any_of(It->second, [&](
const auto &LS) {
15012 return LS.first == L && LS.second.getPointer() == ValueAtScope;
15015 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
15016 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
15022 auto VerifyBECountUsers = [&](
bool Predicated) {
15024 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
15025 for (
const auto &LoopAndBEInfo : BECounts) {
15026 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
15027 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
15029 auto UserIt = BECountUsers.find(S);
15030 if (UserIt != BECountUsers.end() &&
15031 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
15033 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
15034 <<
" missing from BECountUsers\n";
15041 VerifyBECountUsers(
false);
15042 VerifyBECountUsers(
true);
15045 for (
auto &[S,
Values] : LoopDispositions) {
15046 for (
auto [
Loop, CachedDisposition] :
Values) {
15048 if (CachedDisposition != RecomputedDisposition) {
15049 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
15050 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
15051 << RecomputedDisposition <<
"\n";
15058 for (
auto &[S,
Values] : BlockDispositions) {
15059 for (
auto [BB, CachedDisposition] :
Values) {
15061 if (CachedDisposition != RecomputedDisposition) {
15062 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
15063 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
15064 <<
", actual " << RecomputedDisposition <<
"\n";
15071 for (
auto [
FoldID, Expr] : FoldCache) {
15072 auto I = FoldCacheUser.find(Expr);
15073 if (
I == FoldCacheUser.end()) {
15074 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
15079 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
15083 for (
auto [Expr, IDs] : FoldCacheUser) {
15084 for (
auto &
FoldID : IDs) {
15087 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
15092 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
15093 <<
" != " << *Expr <<
"!\n";
15104 for (
auto [S, Multiple] : ConstantMultipleCache) {
15106 if ((Multiple != 0 && RecomputedMultiple != 0 &&
15107 Multiple.
urem(RecomputedMultiple) != 0 &&
15108 RecomputedMultiple.
urem(Multiple) != 0)) {
15109 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
15110 << *S <<
" : Computed " << RecomputedMultiple
15111 <<
" but cache contains " << Multiple <<
"!\n";
15119 FunctionAnalysisManager::Invalidator &Inv) {
15151 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
15152 <<
F.getName() <<
"':\n";
15158 "Scalar Evolution Analysis",
false,
true)
15207 const SCEV *LHS,
const SCEV *RHS) {
15209 assert(LHS->getType() == RHS->getType() &&
15210 "Type mismatch between LHS and RHS");
15213 ID.AddInteger(Pred);
15214 ID.AddPointer(LHS);
15215 ID.AddPointer(RHS);
15217 if (
const auto *S = UniquePreds.lookup(ID, Token))
15221 UniquePreds.insert(Eq, Token);
15232 ID.AddInteger(AddedFlags);
15234 if (
const auto *S = UniquePreds.lookup(ID, Token))
15236 auto *OF =
new (SCEVAllocator)
15238 UniquePreds.insert(OF, Token);
15258 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
15259 return Rewriter.visit(S);
15265 for (
const auto *Pred : U->getPredicates())
15267 if (IPred->getLHS() == Expr &&
15269 return IPred->getRHS();
15271 if (IPred->getLHS() == Expr &&
15272 IPred->getPredicate() == ICmpInst::ICMP_EQ)
15273 return IPred->getRHS();
15276 return convertToAddRecWithPreds(Expr);
15279 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15295 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15312 explicit SCEVPredicateRewriter(
15313 const Loop *L, ScalarEvolution &SE,
15314 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15315 const SCEVPredicate *Pred)
15316 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
15318 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15321 return Pred && Pred->
implies(
P, SE);
15327 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15330 return addOverflowAssumption(
A);
15339 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15343 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15345 if (!PredicatedRewrite)
15347 for (
const auto *
P : PredicatedRewrite->second){
15350 if (L != WP->getExpr()->getLoop())
15353 if (!addOverflowAssumption(
P))
15356 return PredicatedRewrite->first;
15359 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15360 const SCEVPredicate *Pred;
15369 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15376 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15396 if (!Step->
isOne())
15421 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15422 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15435 return Op->LHS == LHS &&
Op->RHS == RHS;
15442 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15444 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15469 const SCEV *Start = AR->getStart();
15470 const SCEV *OpStart =
Op->AR->getStart();
15475 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15484 const SCEV *Step = AR->getStepRecurrence(SE);
15485 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15528 for (
const auto *
P : Preds)
15541 return this->implies(I, SE);
15553 const Loop *L = NWrap->getExpr()->getLoop();
15560 return RewrittenAR &&
15566 for (
const auto *Pred : Preds)
15567 Pred->print(OS,
Depth);
15572 for (
const auto *Pred : Set->Preds)
15580 bool CheckImplies = Preds.
size() < 16;
15583 if (CheckImplies &&
implies(
N, SE))
15589 for (
auto *
P : Preds) {
15590 if (CheckImplies &&
N->implies(
P, SE))
15594 Preds = std::move(PrunedPreds);
15595 Preds.push_back(
N);
15602 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15611 SCEVUsers[
Op].insert(
User);
15615 const SCEV *Expr = SE.getSCEV(V);
15620 RewriteEntry &Entry = RewriteMap[Expr];
15623 if (Entry.second && Generation == Entry.first)
15624 return Entry.second;
15629 Expr = Entry.second;
15631 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15632 Entry = {Generation, NewSCEV};
15638 if (!BackedgeCount) {
15640 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15641 for (
const auto *
P : Preds)
15644 return BackedgeCount;
15648 if (!SymbolicMaxBackedgeCount) {
15650 SymbolicMaxBackedgeCount =
15651 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15652 for (
const auto *
P : Preds)
15655 return SymbolicMaxBackedgeCount;
15659 if (!SmallConstantMaxTripCount) {
15661 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15662 for (
const auto *
P : Preds)
15665 return *SmallConstantMaxTripCount;
15669 if (Preds->implies(&Pred, SE))
15674 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15675 updateGeneration();
15688void PredicatedScalarEvolution::updateGeneration() {
15690 if (++Generation == 0) {
15691 for (
auto &
II : RewriteMap) {
15692 const SCEV *Rewritten =
II.second.second;
15702 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15708 ExtraPreds->
append(NewPreds);
15714 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15720 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15723 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {}
15727 for (
auto *BB : L.getBlocks())
15728 for (
auto &
I : *BB) {
15729 if (!SE.isSCEVable(
I.getType()))
15732 auto *Expr = SE.getSCEV(&
I);
15733 auto II = RewriteMap.find(Expr);
15735 if (
II == RewriteMap.end())
15739 if (
II->second.second == Expr)
15744 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15752 LoopGuards Guards(SE);
15760void ScalarEvolution::LoopGuards::collectFromPHI(
15768 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15769 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15783 auto &RewriteMap =
G->second.RewriteMap;
15784 if (RewriteMap.empty())
15786 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15787 if (S == RewriteMap.end())
15793 return {C0, SM->getSCEVType()};
15796 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15797 MinMaxPattern
P2) -> MinMaxPattern {
15798 auto [C1,
T1] =
P1;
15799 auto [C2, T2] =
P2;
15800 if (!C1 || !C2 ||
T1 != T2)
15804 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15806 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15808 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15810 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15815 auto P = GetMinMaxConst(0);
15816 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15819 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15822 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15825 Guards.RewriteMap.insert({
LHS,
RHS});
15833 const APInt &DivisorVal,
15835 const APInt *ExprVal;
15848 const APInt &DivisorVal,
15850 const APInt *ExprVal;
15858 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15872 const SCEV *URemRHS =
nullptr;
15876 const SCEV *Multiple =
15878 DivInfo[URemLHS] = Multiple;
15880 Multiples[URemLHS] =
C->getAPInt();
15900 auto IsMinMaxSCEVWithNonNegativeConstant =
15904 if (
MinMax->getNumOperands() != 2)
15907 if (
C->getAPInt().isNegative())
15909 SCTy =
MinMax->getSCEVType();
15918 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15920 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15925 auto *DivisibleExpr =
15933void ScalarEvolution::LoopGuards::collectFromBlock(
15935 const BasicBlock *
Block,
const BasicBlock *Pred,
15943 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
15954 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15956 if (From == FromRewritten)
15958 RewriteMap[From] = To;
15964 auto GetMaybeRewritten = [&](
const SCEV *S) {
15965 return RewriteMap.lookup_or(S, S);
15972 const SCEV *MatchLHS,
15973 const SCEV *MatchRHS) {
15974 const SCEVConstant *C1;
15977 if (!
match(MatchLHS,
15989 const SCEV *RewrittenLHS = GetMaybeRewritten(LHSUnknown);
15990 ExactRegion = ExactRegion.intersectWith(SE.
getUnsignedRange(RewrittenLHS),
15995 if (ExactRegion.isEmptySet() || ExactRegion.isWrappedSet() ||
15996 ExactRegion.isFullSet())
15999 const SCEV *RegionMin = SE.
getConstant(ExactRegion.getUnsignedMin());
16000 const SCEV *RegionMax = SE.
getConstant(ExactRegion.getUnsignedMax());
16001 const SCEV *ClampedLHS =
16003 AddRewrite(LHSUnknown, RewrittenLHS, ClampedLHS);
16006 if (MatchRangeCheckIdiom(Predicate,
LHS,
RHS))
16019 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
16021 const APInt &DividesBy =
16036 switch (Predicate) {
16065 SmallPtrSet<const SCEV *, 16> Visited;
16067 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
16071 while (!Worklist.
empty()) {
16075 if (!Visited.
insert(From).second)
16077 const SCEV *FromRewritten = GetMaybeRewritten(From);
16078 const SCEV *To =
nullptr;
16080 switch (Predicate) {
16085 EnqueueOperands(
UMax);
16091 EnqueueOperands(
SMax);
16097 EnqueueOperands(
UMin);
16103 EnqueueOperands(
SMin);
16111 const SCEV *OneAlignedUp =
16113 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
16125 const SCEVConstant *
C;
16134 Guards.NotEqual.insert({
LHS,
RHS});
16143 AddRewrite(From, FromRewritten, To);
16160 SE.F.
getParent(), Intrinsic::experimental_guard);
16162 for (
const auto *GU : GuardDecl->users())
16164 if (Guard->getFunction() ==
Block->getParent() &&
16173 unsigned NumCollectedConditions = 0;
16175 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
16177 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
16179 const CondBrInst *LoopEntryPredicate =
16181 if (!LoopEntryPredicate)
16186 NumCollectedConditions++;
16190 if (
Depth > 0 && NumCollectedConditions == 2)
16198 if (Pair.second->hasNPredecessorsOrMore(2) &&
16200 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
16201 for (
auto &Phi : Pair.second->phis())
16212 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
16213 SmallVector<Value *, 8> Worklist;
16214 SmallPtrSet<Value *, 8> Visited;
16216 while (!Worklist.
empty()) {
16223 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
16247 DenseMap<const SCEV *, APInt> Multiples;
16249 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
16256 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
16257 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
16261 for (
const auto &[K, Divisor] : Multiples) {
16262 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
16263 Guards.RewriteMap[
K] =
16265 Guards.
rewrite(K), Divisor, SE),
16274 Guards.PreserveNUW =
true;
16275 Guards.PreserveNSW =
true;
16276 for (
const SCEV *Expr : ExprsToRewrite) {
16277 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16278 Guards.PreserveNUW &=
16280 Guards.PreserveNSW &=
16287 if (ExprsToRewrite.size() > 1) {
16288 for (
const SCEV *Expr : ExprsToRewrite) {
16289 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16290 Guards.RewriteMap.erase(Expr);
16291 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
16300 class SCEVLoopGuardRewriter
16311 NotEqual(Guards.NotEqual) {
16312 if (Guards.PreserveNUW)
16314 if (Guards.PreserveNSW)
16321 return Map.lookup_or(Expr, Expr);
16325 if (
const SCEV *S = Map.lookup(Expr))
16332 if (
const SCEV *S = Map.lookup(Expr))
16339 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16340 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16341 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16343 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16344 if (
const SCEV *S = Map.lookup(NarrowExt))
16345 return SE.getZeroExtendExpr(S, Ty);
16346 Bitwidth = Bitwidth / 2;
16354 if (
const SCEV *S = Map.lookup(Expr))
16361 if (
const SCEV *S = Map.lookup(Expr))
16367 if (
const SCEV *S = Map.lookup(Expr))
16373 if (
const SCEV *S = Map.lookup(Expr))
16378 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16383 if (NotEqual.contains({LHS, RHS})) {
16385 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16386 return SE.getUMaxExpr(OneAlignedUp, S);
16393 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16404 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16405 return SE.getAddExpr(
16408 if (
const SCEV *S = Map.lookup(
Add))
16409 return SE.getAddExpr(Expr->
getOperand(0), S);
16417 const SCEV *S =
nullptr;
16424 S = Map.lookup(SE.getAddExpr(NewC, Expr->
getOperand(1)));
16427 return SE.getAddExpr(S, SE.getMinusOne(Expr->
getType()));
16462 if (RewriteMap.empty() && NotEqual.empty())
16465 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16466 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 bool hasNoUnsignedWrap(BinaryOperator &I)
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 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 SCEV::NoWrapFlags getNoWrapFlagsForGEP(GEPOperator *GEP, const SCEV *Accum, ScalarEvolution &SE)
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 bool IsKnownPredicateViaAddRecMonotonicity(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Is LHS Pred RHS true because one of them is an AddRec that is known not to go below its own start val...
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 PHINode * getConstantEvolvingPHI(Value *V, const Loop *L, const TargetLibraryInfo *TLI)
getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node in the loop that V is deri...
static bool canConstantFold(const Instruction *I, const TargetLibraryInfo *TLI)
Return true if we can constant fold an instruction of the specified type, assuming that all operands ...
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 PHINode * getConstantEvolvingPHIOperands(Instruction *UseInst, const Loop *L, DenseMap< Instruction *, PHINode * > &PHIMap, const TargetLibraryInfo *TLI, unsigned Depth)
getConstantEvolvingPHIOperands - Implement getConstantEvolvingPHI by recursing through each instructi...
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 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 canConstantEvolve(Instruction *I, const Loop *L, const TargetLibraryInfo *TLI)
Determine whether this instruction can constant evolve within this loop assuming its operands can all...
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 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.
This is the base class for all instructions that perform data casts.
This class is the base class for the comparison instructions.
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 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.
Insertion token: a failed lookup fills it in, the matching insert consumes it.
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)
This class represents a freeze function that returns random concrete value if an operand is either a ...
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.
This instruction inserts a single (scalar) element into a VectorType value.
This instruction inserts a struct field of array element value into an aggregate value.
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 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 SCEVUse getExitValue(ScalarEvolution &SE) const
Return the value of this recurrences when its loop exits, i.e.
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
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=FlagsMask) const
bool hasNoSelfWrap() const
size_t getNumOperands() const
bool hasNoSignedWrap() 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 * visitPtrToAddrExpr(const SCEVPtrToAddrExpr *Expr)
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.
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.
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.
static constexpr auto FlagNone
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 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 * 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 SCEVUse getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
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 void registerUser(const SCEV *User, ArrayRef< SCEVUse > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
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.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
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 void forgetValues(ArrayRef< Value * > Values)
Batched forgetValue: invalidates all Values in one shared def-use walk, avoiding the redundant re-tra...
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 isKnownMultipleOf(const SCEV *S, uint64_t M, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Check that S is a multiple of M.
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 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 SCEVUse getSCEVAtExit(const SCEV *S, const Loop *L, const BasicBlock *ExitingBlock)
Return the SCEV expression at the specified loop exit.
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 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 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 const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagNone)
Return the SCEV object corresponding to -V.
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.
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 const SCEV * getMinusSCEV(SCEVUse LHS, SCEVUse RHS, SCEV::NoWrapFlags Flags=SCEV::FlagNone, unsigned Depth=0)
Return LHS-RHS.
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 * getElementCount(Type *Ty, ElementCount EC, SCEV::NoWrapFlags Flags=SCEV::FlagNone)
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 SCEVUse getMulExpr(SmallVectorImpl< SCEVUse > &Ops, SCEVFlags Flags={}, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
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 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.
LLVM_ABI SCEVUse getAddRecExpr(SCEVUse Start, SCEVUse Step, const Loop *L, SCEVFlags Flags)
Get an add recurrence expression for the specified loop.
LLVM_ABI SCEVUse getAddExpr(SmallVectorImpl< SCEVUse > &Ops, SCEVFlags Flags={}, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
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
This class represents the LLVM 'select' instruction.
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.
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)
@ 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)
SCEVBinaryExpr_match< SCEVSMaxExpr, Op0_t, Op1_t, SCEV::FlagNone, true > m_scev_SMax(const Op0_t &Op0, const Op1_t &Op1)
SCEVBinaryExpr_match< SCEVMulExpr, Op0_t, Op1_t, SCEV::FlagNone, true > m_scev_c_Mul(const Op0_t &Op0, const Op1_t &Op1)
match_bind< const SCEVAddExpr > m_scev_Add(const SCEVAddExpr *&V)
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.
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 >
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
@ BinaryOp
One of the operands is a binary op.
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.
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.
LLVM_ABI bool canConstantFoldCallTo(const CallBase *Call, const Function *F, const TargetLibraryInfo *TLI=nullptr)
canConstantFoldCallTo - Return true if its even possible to fold a call to the specified function.
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.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
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.
Type * getLoadStoreType(const Value *I)
A helper function that returns the type of a load or store instruction.
iterator_range< df_iterator< T > > depth_first(const T &G)
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
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.
constexpr detail::IsaCheckPredicate< Types... > IsaPred
Function object wrapper for the llvm::isa type check.
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Function *CxtF=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) 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:
The no-wrap flags to apply when creating a SCEV expression, to the expression and use respectively.
SCEVNoWrapFlags UseFlags
Flags only applied to a SCEVUse.
SCEVNoWrapFlags ExprFlags
Flags applied directly to a SCEV expression, must be valid wherever the expression is valid.
SCEVPtrT getPointer() const
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