84#include "llvm/Config/llvm-config.h"
139#define DEBUG_TYPE "scalar-evolution"
142 "Number of loop exits with predictable exit counts");
144 "Number of loop exits without predictable exit counts");
146 "Number of loops with trip counts computed by force");
148#ifdef EXPENSIVE_CHECKS
156 cl::desc(
"Verify ScalarEvolution's backedge taken counts (slow)"));
192#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
210 OS <<
"(ptrtoaddr " << *
Op->getType() <<
" " <<
Op <<
" to "
217 OS <<
"(trunc " << *
Op->getType() <<
" " <<
Op <<
" to "
224 OS <<
"(zext " << *
Op->getType() <<
" " <<
Op <<
" to " << *ZExt->
getType()
231 OS <<
"(sext " << *
Op->getType() <<
" " <<
Op <<
" to " << *SExt->
getType()
260 const char *OpStr =
nullptr;
273 OpStr =
" umin_seq ";
295 OS <<
"(" << UDiv->
getLHS() <<
" /u " << UDiv->
getRHS() <<
")";
302 OS <<
"***COULDNOTCOMPUTE***";
344 if (!
Mul)
return false;
348 if (!SC)
return false;
362 auto &Entry = ConstantSCEVs[V];
371 static_cast<SCEVConstant *
>(UniqueSCEVs.lookup(ID, Token)))
374 new (SCEVAllocator)
SCEVConstant(ID.Intern(SCEVAllocator), V);
375 UniqueSCEVs.insert(S, Token);
390 ConstantInt::get(ITy, V,
isSigned,
true));
398 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
400 SCEV *S =
new (SCEVAllocator)
SCEVVScale(ID.Intern(SCEVAllocator), Ty);
401 UniqueSCEVs.insert(S, Token);
422 "Must be a non-bit-width-changing pointer-to-integer cast!");
434 "Cannot truncate non-integer value!");
441 "Cannot zero extend non-integer value!");
448 "Cannot sign extend non-integer value!");
453 SE->forgetMemoizedResults({
this});
456 SE->UniqueSCEVs.erase(
this);
462void SCEVUnknown::allUsesReplacedWith(
Value *New) {
464 SE->forgetMemoizedResults({
this});
467 SE->UniqueSCEVs.erase(
this);
483 if (
Depth > Opts.scalar_evolution_max_value_compare_depth)
490 if (LIsPointer != RIsPointer)
491 return (
int)LIsPointer - (int)RIsPointer;
496 return (
int)LID - (int)RID;
501 unsigned LArgNo = LA->getArgNo(), RArgNo =
RA->getArgNo();
502 return (
int)LArgNo - (int)RArgNo;
508 if (
auto L = LGV->getLinkage() - RGV->getLinkage())
511 const auto IsGVNameSemantic = [&](
const GlobalValue *GV) {
512 auto LT = GV->getLinkage();
519 if (IsGVNameSemantic(LGV) && IsGVNameSemantic(RGV))
520 return LGV->getName().compare(RGV->getName());
531 if (LParent != RParent) {
534 if (LDepth != RDepth)
535 return (
int)LDepth - (int)RDepth;
539 unsigned LNumOps = LInst->getNumOperands(),
540 RNumOps = RInst->getNumOperands();
541 if (LNumOps != RNumOps)
542 return (
int)LNumOps - (int)RNumOps;
544 for (
unsigned Idx :
seq(LNumOps)) {
546 RInst->getOperand(Idx),
Depth + 1);
565 if (
LHS.getPointer() ==
RHS.getPointer())
566 return (
int)
LHS.getUseNoWrapFlags() - (int)
RHS.getUseNoWrapFlags();
571 return (
int)LType - (int)RType;
594 unsigned LBitWidth = LA.
getBitWidth(), RBitWidth =
RA.getBitWidth();
595 if (LBitWidth != RBitWidth)
596 return (
int)LBitWidth - (int)RBitWidth;
597 return LA.
ult(
RA) ? -1 : 1;
603 return LTy->getBitWidth() - RTy->getBitWidth();
614 if (LLoop != RLoop) {
616 assert(LHead != RHead &&
"Two loops share the same header?");
620 "No dominance between recurrences used by one SCEV?");
643 unsigned LNumOps = LOps.
size(), RNumOps = ROps.
size();
644 if (LNumOps != RNumOps)
645 return (
int)LNumOps - (int)RNumOps;
647 for (
unsigned i = 0; i != LNumOps; ++i) {
656 assert(LBitWidth != RBitWidth &&
"distinct SCEVs compare equal");
657 return (
int)LBitWidth - (int)RBitWidth;
678 if (
Ops.size() < 2)
return;
684 if (
Ops.size() == 2) {
688 if (IsLessComplex(
RHS,
LHS))
713template <
typename FoldT,
typename IsIdentityT,
typename IsAbsorberT>
718 IsIdentityT IsIdentity, IsAbsorberT IsAbsorber) {
720 for (
unsigned Idx = 0; Idx <
Ops.size();) {
728 Ops.erase(
Ops.begin() + Idx);
746 return Ops.size() == 1 ?
Ops[0] :
nullptr;
821 APInt OddFactorial(W, 1);
823 for (
unsigned i = 3; i <=
K; ++i) {
826 OddFactorial *= (i >> TwoFactors);
830 unsigned CalculationBits = W +
T;
844 for (
unsigned i = 1; i !=
K; ++i) {
877 "use-specific flags only supported for affine AddRecs");
879 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
920 ConversionFn CreatePtrCast;
924 ConversionFn CreatePtrCast)
925 : Base(
SE), TargetTy(TargetTy), CreatePtrCast(
std::
move(CreatePtrCast)) {}
928 Type *TargetTy, ConversionFn CreatePtrCast) {
930 return Rewriter.visit(Scev);
956 "Should only reach pointer-typed SCEVUnknown's.");
961 return SE.getZero(TargetTy);
962 return CreatePtrCast(Expr);
967 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
971 if (DL.hasUnstableRepresentation(
Op->getType()))
974 Type *Ty = DL.getAddressType(
Op->getType());
985 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
987 SCEV *S =
new (SCEVAllocator)
989 UniqueSCEVs.insert(S, Token);
992 return static_cast<const SCEV *
>(S);
995 "We must have succeeded in sinking the cast, "
996 "and ending up with an integer-typed expression!");
1003 "This is not a truncating conversion!");
1005 "This is not a conversion to a SCEVable type!");
1006 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1011 ID.AddPointer(
Op.getOpaqueValue());
1014 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1034 if (
Depth > Opts.scalar_evolution_max_cast_depth) {
1037 UniqueSCEVs.insert(S, Token);
1050 unsigned numTruncs = 0;
1051 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1059 if (numTruncs < 2) {
1069 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1076 for (
const SCEV *
Op : AddRec->operands())
1091 UniqueSCEVs.insert(S, Token);
1132struct ExtendOpTraitsBase {
1133 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(
SCEVUse,
Type *,
1138template <
typename ExtendOp>
struct ExtendOpTraits {
1154 static const GetExtendExprTy GetExtendExpr;
1156 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1157 ICmpInst::Predicate *
Pred,
1158 ScalarEvolution *SE) {
1163const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1170 static const GetExtendExprTy GetExtendExpr;
1172 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1173 ICmpInst::Predicate *
Pred,
1174 ScalarEvolution *SE) {
1179const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1191template <
typename ExtendOpTy>
1194 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1195 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1211 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1224 auto PreStartFlags =
1242 const SCEV *OperandExtendedStart =
1244 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1245 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1257 const SCEV *OverflowLimit =
1258 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &
Pred, SE);
1260 if (OverflowLimit &&
1268template <
typename ExtendOpTy>
1272 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1280 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1315template <
typename ExtendOpTy>
1316bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1319 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1329 APInt StartAI = StartC->
getAPInt();
1331 for (
unsigned Delta : {-2, -1, 1, 2}) {
1332 const SCEV *PreStart =
getConstant(StartAI - Delta);
1333 const auto *PreAR =
static_cast<SCEVAddRecExpr *
>(
1334 findExistingSCEVInCache(
scAddRecExpr, {PreStart, Step},
L));
1338 if (PreAR &&
any(PreAR->getNoWrapFlags(WrapType))) {
1341 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1342 DeltaS, &
Pred,
this);
1360 const unsigned BitWidth =
C.getBitWidth();
1378 const APInt &ConstantStart,
1393 auto I = FoldCache.
insert({ID, S});
1397 auto &UserIDs = FoldCacheUser[
I.first->second];
1398 assert(
count(UserIDs, ID) == 1 &&
"unexpected duplicates in UserIDs");
1399 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1400 if (UserIDs[
I] == ID) {
1405 I.first->second = S;
1407 FoldCacheUser[S].push_back(ID);
1413 "This is not an extending conversion!");
1415 "This is not a conversion to a SCEVable type!");
1416 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1420 if (
const SCEV *S = FoldCache.lookup(ID))
1432 "This is not an extending conversion!");
1434 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1446 const SCEV *Start, *Step;
1448 if (
Depth <= Opts.scalar_evolution_max_cast_depth &&
1451 if (AR->hasNoUnsignedWrap()) {
1462 ID.AddPointer(
Op.getOpaqueValue());
1465 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1467 if (
Depth > Opts.scalar_evolution_max_cast_depth) {
1470 UniqueSCEVs.insert(S, Token);
1480 const SCEV *
X = ST->getOperand();
1513 const SCEV *CastedMaxBECount =
1517 if (MaxBECount == RecastedMaxBECount) {
1526 const SCEV *WideMaxBECount =
1528 const SCEV *OperandExtendedAdd =
1534 if (ZAdd == OperandExtendedAdd) {
1545 OperandExtendedAdd =
1551 if (ZAdd == OperandExtendedAdd) {
1572 !AC.assumptions().empty()) {
1574 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1576 if (AR->hasNoUnsignedWrap()) {
1611 const APInt &
C = SC->getAPInt();
1615 const SCEV *SResidual =
1623 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1647 if (SA->hasNoUnsignedWrap()) {
1660 if (SA->hasNoSignedWrap() &&
1663 C->isNegative() && !
C->isMinSignedValue() && C2->
sge(
C->abs())) {
1682 const SCEV *SResidual =
1693 if (SM->hasNoUnsignedWrap()) {
1715 const SCEV *TruncRHS;
1752 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1756 UniqueSCEVs.insert(S, Token);
1765 "This is not an extending conversion!");
1767 "This is not a conversion to a SCEVable type!");
1768 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1772 if (
const SCEV *S = FoldCache.lookup(ID))
1784 "This is not an extending conversion!");
1786 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1803 const SCEV *Start, *Step;
1805 if (
Depth <= Opts.scalar_evolution_max_cast_depth &&
1808 if (AR->hasNoSignedWrap()) {
1819 ID.AddPointer(
Op.getOpaqueValue());
1822 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
1825 if (
Depth > Opts.scalar_evolution_max_cast_depth) {
1828 UniqueSCEVs.insert(S, Token);
1838 const SCEV *
X = ST->getOperand();
1849 if (SA->hasNoSignedWrap()) {
1871 const SCEV *SResidual =
1904 const SCEV *CastedMaxBECount =
1908 if (MaxBECount == RecastedMaxBECount) {
1917 const SCEV *WideMaxBECount =
1919 const SCEV *OperandExtendedAdd =
1925 if (SAdd == OperandExtendedAdd) {
1936 OperandExtendedAdd =
1942 if (SAdd == OperandExtendedAdd) {
1962 auto NewFlags = proveNoSignedWrapViaInduction(AR);
1964 if (AR->hasNoSignedWrap()) {
1978 const APInt &
C = SC->getAPInt();
1982 const SCEV *SResidual =
1990 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2017 if (
const SCEV *S = UniqueSCEVs.lookup(ID, Token))
2021 UniqueSCEVs.insert(S, Token);
2037 assert(Expr->
getType() == Ty &&
"requested type must match");
2049 "This is not an extending conversion!");
2051 "This is not a conversion to a SCEVable type!");
2056 if (SC->getAPInt().isNegative())
2061 const SCEV *NewOp =
T->getOperand();
2080 for (
const SCEV *
Op : AR->operands())
2121 bool Interesting =
false;
2128 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2130 AccumulatedConstant += Scale *
C->getAPInt();
2135 for (; i !=
Ops.size(); ++i) {
2144 M, NewOps, AccumulatedConstant,
Add->operands(), NewScale, SE);
2150 auto Pair = M.insert({
Key, NewScale});
2154 Pair.first->second += NewScale;
2162 auto Pair = M.insert({
Ops[i]->getCanonical(), Scale});
2166 Pair.first->second += Scale;
2184 case Instruction::Add:
2186 case Instruction::Sub:
2188 case Instruction::Mul:
2202 const SCEV *
A = (this->*Extension)(
Operation(LHS, RHS), WideTy, 0);
2203 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2204 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2212 if (BinOp == Instruction::Mul)
2218 APInt C = RHSC->getAPInt();
2219 unsigned NumBits =
C.getBitWidth();
2220 bool IsSub = (BinOp == Instruction::Sub);
2221 bool IsNegativeConst = (
Signed &&
C.isNegative());
2223 bool OverflowDown = IsSub ^ IsNegativeConst;
2225 if (IsNegativeConst) {
2238 APInt Limit = Min + Magnitude;
2244 APInt Limit = Max - Magnitude;
2253 return std::nullopt;
2262 bool Deduced =
false;
2268 bool CanUseNSW =
true;
2269 const APInt *ShiftAmt;
2274 return std::nullopt;
2278 Opcode = Instruction::Mul;
2280 }
else if (Opcode != Instruction::Add && Opcode != Instruction::Sub &&
2281 Opcode != Instruction::Mul) {
2282 return std::nullopt;
2286 Opts.scalar_evolution_use_context_for_no_wrap_flag_strenghening
2303 return std::nullopt;
2311 using namespace std::placeholders;
2318 assert(CanAnalyze &&
"don't call from other places!");
2325 auto IsKnownNonNegative = [&](
SCEVUse U) {
2334 if (SignOrUnsignWrap != SignOrUnsignMask &&
2341 return Instruction::Add;
2343 return Instruction::Mul;
2372 Ops[0]->isZero() && IsKnownNonNegative(
Ops[1]))
2379 if (UDiv->getOperand(1) ==
Ops[1])
2382 if (UDiv->getOperand(1) ==
Ops[0])
2399 "only nuw or nsw allowed");
2401 "only nuw or nsw allowed");
2402 assert(!
Ops.empty() &&
"Cannot get empty add!");
2403 if (
Ops.size() == 1)
return Ops[0];
2406 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
2408 "SCEVAddExpr operand types don't match!");
2410 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2411 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2415 Opts, *
this, LI, DT,
Ops,
2417 [](
const APInt &
C) {
return C.isZero(); },
2418 [](
const APInt &
C) {
return false; });
2436 if (
Depth > Opts.scalar_evolution_max_arith_depth ||
2438 return {getOrCreateAddExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
2443 if (
Add->getNoWrapFlags(ExprFlags) != ExprFlags)
2444 Add->setNoWrapFlags(ComputeFlags(
Ops));
2445 return {S, UseFlags};
2452 bool FoundMatch =
false;
2453 for (
unsigned i = 0, e =
Ops.size(); i != e-1; ++i)
2471 --i; e -=
Count - 1;
2481 auto FindTruncSrcType = [&]() ->
Type * {
2487 return T->getOperand()->getType();
2489 SCEVUse LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2491 return T->getOperand()->getType();
2495 if (
auto *SrcType = FindTruncSrcType()) {
2502 if (
T->getOperand()->getType() != SrcType) {
2511 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2514 if (
T->getOperand()->getType() != SrcType) {
2543 if (
Ops.size() == 2) {
2553 auto C2 =
C->getAPInt();
2557 auto AddFlags = AddExpr->getNoWrapFlags();
2598 if (
Ops.size() == 2 &&
2609 if (Idx <
Ops.size()) {
2610 bool DeletedAdd =
false;
2616 if (
Ops.size() > Opts.scev_addops_inline_threshold ||
2617 Add->getNumOperands() > Opts.scev_addops_inline_threshold)
2621 Ops.erase(
Ops.begin()+Idx);
2624 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2647 struct APIntCompare {
2648 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2649 return LHS.ult(RHS);
2656 std::map<APInt, SmallVector<SCEVUse, 4>, APIntCompare> MulOpLists;
2658 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2661 if (AccumulatedConstant != 0)
2663 for (
auto &MulOp : MulOpLists) {
2664 if (MulOp.first == 1) {
2666 }
else if (MulOp.first != 0) {
2675 if (
Ops.size() == 1)
2684 if (M->getNumOperands() == 2)
2685 return M->getOperand(OpIdx == 0);
2687 append_range(Remaining, M->operands().drop_front(OpIdx + 1));
2696 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2708 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp) {
2721 for (
unsigned OMulOp = 0, OE = OtherMul->
getNumOperands(); OMulOp != OE;
2727 Cofactors.
push_back(StripFactor(OtherMul, OMulOp));
2736 if (!Cofactors.
empty()) {
2744 if (
Ops.size() == DeadIndices.
size() + 1)
2751 Ops.erase(
Ops.begin() + Idx);
2755 Ops.push_back(OuterMul);
2774 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
2777 Ops.erase(
Ops.begin()+i);
2782 if (!LIOps.
empty()) {
2807 auto *DefI = getDefiningScopeBound(LIOps);
2809 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
2821 if (
Ops.size() == 1)
return NewRec;
2824 for (
unsigned i = 0;; ++i)
2825 if (
Ops[i] == AddRec) {
2835 for (
unsigned OtherIdx = Idx+1;
2843 "AddRecExprs are not sorted in reverse dominance order?");
2850 if (OtherAddRec->getLoop() == AddRecLoop) {
2851 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
2853 if (i >= AddRecOps.
size()) {
2854 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
2858 getAddExpr(AddRecOps[i], OtherAddRec->getOperand(i),
2861 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
2877 "Tried to add SCEVUse flags after operands changed");
2878 return {getOrCreateAddExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
2886 ID.AddPointer(
Op.getOpaqueValue());
2892 S =
new (SCEVAllocator)
2894 UniqueSCEVs.insert(S, Token);
2905 FoldingSetNodeID
ID;
2908 ID.AddPointer(
Op.getOpaqueValue());
2910 FoldingSetInsertToken Token;
2912 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.lookup(ID, Token));
2916 S =
new (SCEVAllocator)
2917 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
2918 UniqueSCEVs.insert(S, Token);
2920 LoopUsers[
L].push_back(S);
2929 FoldingSetNodeID
ID;
2932 ID.AddPointer(
Op.getOpaqueValue());
2933 FoldingSetInsertToken Token;
2934 SCEVMulExpr *S =
static_cast<SCEVMulExpr *
>(UniqueSCEVs.lookup(ID, Token));
2938 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
2940 UniqueSCEVs.insert(S, Token);
2949 FoldingSetNodeID
ID;
2951 ID.AddPointer(
LHS.getOpaqueValue());
2952 ID.AddPointer(
RHS.getOpaqueValue());
2953 FoldingSetInsertToken Token;
2954 SCEV *S = UniqueSCEVs.lookup(ID, Token);
2956 S =
new (SCEVAllocator) SCEVUDivExpr(
ID.Intern(SCEVAllocator),
LHS,
RHS);
2957 UniqueSCEVs.insert(S, Token);
2966 if (j > 1 && k / j != i) Overflow =
true;
2982 if (n == 0 || n == k)
return 1;
2983 if (k > n)
return 0;
2989 for (
uint64_t i = 1; i <= k; ++i) {
2990 r =
umul_ov(r, n-(i-1), Overflow);
2999 struct FindConstantInAddMulChain {
3000 bool FoundConstant =
false;
3002 bool follow(
const SCEV *S) {
3007 bool isDone()
const {
3008 return FoundConstant;
3012 FindConstantInAddMulChain
F;
3014 ST.visitAll(StartExpr);
3015 return F.FoundConstant;
3024 "only nuw or nsw allowed");
3026 "only nuw or nsw allowed");
3027 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3028 if (
Ops.size() == 1)
return Ops[0];
3030 Type *ETy =
Ops[0]->getType();
3032 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3034 "SCEVMulExpr operand types don't match!");
3038 Opts, *
this, LI, DT,
Ops,
3040 [](
const APInt &
C) {
return C.isOne(); },
3041 [](
const APInt &
C) {
return C.isZero(); });
3057 if (
Depth > Opts.scalar_evolution_max_arith_depth ||
3059 return {getOrCreateMulExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
3064 if (
Mul->getNoWrapFlags(ExprFlags) != ExprFlags)
3065 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3066 return {S, UseFlags};
3070 if (
Ops.size() == 2) {
3078 const SCEV *Op0, *Op1;
3086 if (
Ops[0]->isAllOnesValue()) {
3091 bool AnyFolded =
false;
3092 for (
const SCEV *AddOp :
Add->operands()) {
3112 if (AddRec->hasNoSignedWrap()) {
3143 APInt C1V = LHSC->getAPInt();
3153 const SCEV *NewMul =
nullptr;
3157 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3172 if (Idx <
Ops.size()) {
3173 bool DeletedMul =
false;
3175 if (
Ops.size() > Opts.scev_mulops_inline_threshold)
3179 Ops.erase(
Ops.begin()+Idx);
3203 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3206 Ops.erase(
Ops.begin()+i);
3211 if (!LIOps.
empty()) {
3223 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3239 if (
Ops.size() == 1)
return NewRec;
3242 for (
unsigned i = 0;; ++i)
3243 if (
Ops[i] == AddRec) {
3264 bool OpsModified =
false;
3265 for (
unsigned OtherIdx = Idx+1;
3276 Opts.scalar_evolution_max_add_rec_size ||
3280 bool Overflow =
false;
3287 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3288 uint64_t Coeff1 =
Choose(x, 2*x - y, Overflow);
3291 z < ze && !Overflow; ++z) {
3292 uint64_t Coeff2 =
Choose(2*x - y, x-z, Overflow);
3294 if (LargerThan64Bits)
3295 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3297 Coeff = Coeff1*Coeff2;
3310 const SCEV *NewAddRec =
3312 if (
Ops.size() == 2)
return NewAddRec;
3313 Ops[Idx] = NewAddRec;
3314 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3331 "Tried to add SCEVUse flags after operands changed");
3332 return {getOrCreateMulExpr(
Ops, ComputeFlags(
Ops)), UseFlags};
3339 "SCEVURemExpr operand types don't match!");
3344 if (RHSC->getValue()->isOne())
3345 return getZero(LHS->getType());
3348 if (RHSC->getAPInt().isPowerOf2()) {
3349 Type *FullTy = LHS->getType();
3365 assert(!LHS->getType()->isPointerTy() &&
3366 "SCEVUDivExpr operand can't be pointer!");
3367 assert(LHS->getType() == RHS->getType() &&
3368 "SCEVUDivExpr operand types don't match!");
3378 if (RHSC->getValue()->isOne())
3383 if (!RHSC->getValue()->isZero()) {
3387 Type *Ty = LHS->getType();
3388 unsigned LZ = RHSC->getAPInt().countl_zero();
3392 if (!RHSC->getAPInt().isPowerOf2())
3400 const APInt &StepInt = Step->getAPInt();
3401 const APInt &DivInt = RHSC->getAPInt();
3402 if (!StepInt.
urem(DivInt) &&
3408 for (
const SCEV *
Op : AR->operands())
3414 const APInt *StartRem;
3427 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3431 const SCEV *NewStart =
3433 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3435 const SCEV *NewLHS =
3445 if (M->hasNoUnsignedWrap()) {
3447 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3448 const SCEV *
Op = M->getOperand(i);
3475 if (
auto *DivisorConstant =
3477 bool Overflow =
false;
3479 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3490 if (
A->hasNoUnsignedWrap()) {
3492 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3499 if (
Operands.size() ==
A->getNumOperands())
3511 const APInt &
N = RHSC->getAPInt();
3512 const APInt *NMinusM, *M;
3516 if (
N.isPowerOf2() && M->isPowerOf2() && M->ult(
N) &&
3517 *NMinusM ==
N - *M) {
3526 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3536 return getZero(LHS->getType());
3540 if (
Mul &&
Mul->hasNoUnsignedWrap()) {
3541 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3542 if (
Mul->getOperand(i) == RHS) {
3553 const SCEV *NewLHS, *NewRHS;
3558 return getOrCreateUDivExpr(LHS, RHS);
3577 if (StepChrec->getLoop() == L) {
3596 "only nuw or nsw allowed");
3602 "SCEVAddRecExpr operand types don't match!");
3603 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3607 "SCEVAddRecExpr operand is not available at loop entry!");
3623 return {getOrCreateAddRecExpr(
Operands, L, ExprFlags), UseFlags};
3640 if (!GEPI || !isSCEVExprNeverPoison(GEPI)) {
3642 }
else if (
any_of(IndexExprs, [&](
const SCEVUse &IndexExpr) {
3643 const SCEV *Idx = IndexExpr;
3645 !isGuaranteedToTransferExecutionTo(
3646 getDefiningScopeBound({Idx}), GEPI);
3656 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), BaseNW,
3673 bool FirstIter =
true;
3675 for (
SCEVUse IndexExpr : IndexExprs) {
3682 Offsets.push_back(FieldOffset);
3685 CurTy = STy->getTypeAtIndex(Index);
3690 "The first index of a GEP indexes a pointer");
3691 CurTy = SrcElementTy;
3702 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3703 Offsets.push_back(LocalOffset);
3708 if (Offsets.empty())
3721 "GEP should not change type mid-flight.");
3725SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3729 "L must be passed to find existing AddRecs");
3733 ID.AddPointer(
Op.getOpaqueValue());
3737 return UniqueSCEVs.lookup(ID, Token);
3747 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3748 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3749 if (
Ops.size() == 1)
return Ops[0];
3752 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
3754 "Operand types don't match!");
3757 "min/max should be consistently pointerish");
3765 Opts, *
this, LI, DT,
Ops,
3783 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3785 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3790 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3792 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3798 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
3804 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
3809 if (Idx <
Ops.size()) {
3810 bool DeletedAny =
false;
3811 while (
Ops[Idx]->getSCEVType() == Kind) {
3813 Ops.erase(
Ops.begin()+Idx);
3831 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
3833 Ops[i] =
Ops[i + 1] = Common;
3834 if (
Ops[i] ==
Ops[i + 1] ||
3835 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
3838 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
3841 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
3844 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
3850 if (
Ops.size() == 1)
return Ops[0];
3852 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
3859 ID.AddPointer(
Op.getOpaqueValue());
3861 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
3863 return ExistingSCEV;
3866 SCEV *S =
new (SCEVAllocator)
3869 UniqueSCEVs.insert(S, Token);
3877class SCEVSequentialMinMaxDeduplicatingVisitor final
3878 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
3879 std::optional<const SCEV *>> {
3880 using RetVal = std::optional<const SCEV *>;
3887 bool canRecurseInto(
SCEVTypes Kind)
const {
3890 return RootKind == Kind || NonSequentialRootKind == Kind;
3895 if (!SeenOps.
insert(S).second)
3896 return std::nullopt;
3900 if (!canRecurseInto(Kind))
3910 return std::nullopt;
3920 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
3922 : SE(SE), RootKind(RootKind),
3923 NonSequentialRootKind(
3924 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
3928 SmallVectorImpl<SCEVUse> &NewOps) {
3933 for (
const SCEV *
Op : OrigOps) {
3938 Ops.emplace_back(*NewOp);
3942 NewOps = std::move(
Ops);
3986struct SCEVPoisonCollector {
3987 bool LookThroughMaybePoisonBlocking;
3988 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
3989 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
3990 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
3992 bool follow(
const SCEV *S) {
3993 if (!LookThroughMaybePoisonBlocking &&
4003 bool isDone()
const {
return false; }
4013 SCEVPoisonCollector PC1(
true);
4018 if (PC1.MaybePoison.
empty())
4024 SCEVPoisonCollector PC2(
false);
4034 SCEVPoisonCollector PC(
false);
4057 unsigned NumVisitedInsts = 0;
4059 while (!Worklist.
empty()) {
4061 if (!Visited.
insert(V).second)
4070 if (++NumVisitedInsts > InstLimit)
4081 if (PDI->isDisjoint())
4088 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4095 if (
I->hasPoisonGeneratingAnnotations())
4106 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4107 "Not a SCEVSequentialMinMaxExpr!");
4108 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4109 if (
Ops.size() == 1)
4113 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4115 "Operand types don't match!");
4118 "min/max should be consistently pointerish");
4126 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4133 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4143 bool DeletedAny =
false;
4144 while (Idx <
Ops.size()) {
4145 if (
Ops[Idx]->getSCEVType() != Kind) {
4150 Ops.erase(
Ops.begin() + Idx);
4151 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4152 SMME->operands().end());
4160 const SCEV *SaturationPoint;
4171 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4184 Ops.erase(
Ops.begin() + i);
4189 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4190 Ops.erase(
Ops.begin() + i);
4200 ID.AddPointer(
Op.getOpaqueValue());
4202 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
4204 return ExistingSCEV;
4208 SCEV *S =
new (SCEVAllocator)
4211 UniqueSCEVs.insert(S, Token);
4259 if (
Size.isScalable())
4280 "Cannot get offset for structure containing scalable vector types");
4294 if (
SCEV *S = UniqueSCEVs.lookup(ID, Token)) {
4296 "Stale SCEVUnknown in uniquing map!");
4299 SCEV *S =
new (SCEVAllocator)
SCEVUnknown(ID.Intern(SCEVAllocator), V,
this,
4300 FirstUnknown, NextUnknownOrderID++);
4302 UniqueSCEVs.insert(S, Token);
4317 return Ty->isIntOrPtrTy();
4324 if (Ty->isPointerTy())
4335 if (Ty->isIntegerTy())
4339 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4351 bool PreciseA, PreciseB;
4352 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4353 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4354 if (!PreciseA || !PreciseB)
4357 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4358 DT.dominates(ScopeB, ScopeA);
4362 return CouldNotCompute.get();
4365bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4368 return SU && SU->getValue() ==
nullptr;
4371 return !ContainsNulls;
4376 if (
I != HasRecMap.end())
4381 HasRecMap.insert({S, FoundAddRec});
4388 ExprValueMapType::iterator
SI = ExprValueMap.find_as(S);
4389 if (
SI == ExprValueMap.end())
4397void ScalarEvolution::eraseValueFromMap(
Value *
V) {
4399 if (
I != ValueExprMap.end()) {
4400 auto EVIt = ExprValueMap.find(
I->second);
4403 ValueExprMap.erase(
I);
4407void ScalarEvolution::insertValueToMap(
Value *
V,
const SCEV *S) {
4411 if (ValueExprMap.insert({SCEVCallbackVH(V, this), S}).second)
4412 ExprValueMap[S].push_back(
V);
4422 return createSCEVIter(V);
4429 if (
I != ValueExprMap.end()) {
4430 const SCEV *S =
I->second;
4431 assert(checkValidity(S) &&
4432 "existing SCEV has not been properly invalidated");
4444 Type *Ty = V->getType();
4460 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4473 return (
const SCEV *)
nullptr;
4479 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4483 Type *Ty = V->getType();
4489 assert(
P->getType()->isPointerTy());
4504 if (AddOp->getType()->isPointerTy()) {
4505 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4522 return getZero(LHS->getType());
4527 if (RHS->getType()->isPointerTy()) {
4528 if (!LHS->getType()->isPointerTy() ||
4538 const bool RHSIsNotMinSigned =
4569 Type *SrcTy = V->getType();
4570 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4571 "Cannot truncate or zero extend with non-integer arguments!");
4581 Type *SrcTy = V->getType();
4582 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4583 "Cannot truncate or zero extend with non-integer arguments!");
4592 Type *SrcTy = V->getType();
4593 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4594 "Cannot noop or zero extend with non-integer arguments!");
4596 "getNoopOrZeroExtend cannot truncate!");
4603 Type *SrcTy = V->getType();
4604 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4605 "Cannot noop or sign extend with non-integer arguments!");
4607 "getNoopOrSignExtend cannot truncate!");
4614 Type *SrcTy = V->getType();
4615 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4616 "Cannot noop or any extend with non-integer arguments!");
4618 "getNoopOrAnyExtend cannot truncate!");
4625 Type *SrcTy = V->getType();
4626 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4627 "Cannot truncate or noop with non-integer arguments!");
4629 "getTruncateOrNoop cannot extend!");
4637 const SCEV *PromotedLHS = LHS;
4638 const SCEV *PromotedRHS = RHS;
4658 assert(!
Ops.empty() &&
"At least one operand must be!");
4660 if (
Ops.size() == 1)
4664 Type *MaxType =
nullptr;
4670 assert(MaxType &&
"Failed to find maximum type!");
4683 if (!V->getType()->isPointerTy())
4688 V = AddRec->getStart();
4690 const SCEV *PtrOp =
nullptr;
4691 for (
const SCEV *AddOp :
Add->operands()) {
4692 if (AddOp->getType()->isPointerTy()) {
4693 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4697 assert(PtrOp &&
"Must have pointer op");
4709 for (
User *U :
I->users()) {
4711 if (Visited.
insert(UserInsn).second)
4725 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4726 bool IgnoreOtherLoops =
true) {
4729 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4731 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4736 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4738 SeenLoopVariantSCEVUnknown =
true;
4742 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4746 SeenOtherLoops =
true;
4750 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4752 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4755 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
4756 : SCEVRewriteVisitor(SE),
L(
L) {}
4759 bool SeenLoopVariantSCEVUnknown =
false;
4760 bool SeenOtherLoops =
false;
4769 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
4770 SCEVPostIncRewriter
Rewriter(L, SE);
4772 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4777 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4779 SeenLoopVariantSCEVUnknown =
true;
4783 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4787 SeenOtherLoops =
true;
4791 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4793 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4796 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
4797 : SCEVRewriteVisitor(SE),
L(
L) {}
4800 bool SeenLoopVariantSCEVUnknown =
false;
4801 bool SeenOtherLoops =
false;
4807class SCEVBackedgeConditionFolder
4810 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4811 ScalarEvolution &SE) {
4812 bool IsPosBECond =
false;
4813 Value *BECond =
nullptr;
4814 if (BasicBlock *Latch =
L->getLoopLatch()) {
4816 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
4817 "Both outgoing branches should not target same header!");
4818 BECond = BI->getCondition();
4819 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
4824 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
4828 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4829 const SCEV *
Result = Expr;
4834 switch (
I->getOpcode()) {
4835 case Instruction::Select: {
4837 std::optional<const SCEV *> Res =
4838 compareWithBackedgeCondition(
SI->getCondition());
4846 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
4857 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
4858 bool IsPosBECond, ScalarEvolution &SE)
4859 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
4860 IsPositiveBECond(IsPosBECond) {}
4862 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
4866 Value *BackedgeCond =
nullptr;
4868 bool IsPositiveBECond;
4871std::optional<const SCEV *>
4872SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
4877 if (BackedgeCond == IC)
4880 return std::nullopt;
4885 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4886 ScalarEvolution &SE) {
4892 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4899 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4909 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
4910 : SCEVRewriteVisitor(SE),
L(
L) {}
4918void ScalarEvolution::inferNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
4934 const APInt &BECountAP = BECountMax->getAPInt();
4935 unsigned NoOverflowBitWidth =
4944ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
4954 if (!SignedWrapViaInductionTried.insert(AR).second)
4979 AC.assumptions().empty())
4987 const SCEV *OverflowLimit =
4989 if (OverflowLimit &&
4997ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5007 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5032 AC.assumptions().empty())
5041 const SCEV *OverflowLimit =
5070 IsNSW = OBO->hasNoSignedWrap();
5071 IsNUW = OBO->hasNoUnsignedWrap();
5077 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5087 return std::nullopt;
5093 switch (
Op->getOpcode()) {
5094 case Instruction::Add:
5095 case Instruction::Sub:
5096 case Instruction::Mul:
5097 case Instruction::UDiv:
5098 case Instruction::URem:
5099 case Instruction::And:
5100 case Instruction::AShr:
5101 case Instruction::Shl:
5104 case Instruction::Or: {
5107 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5117 case Instruction::Xor:
5121 if (RHSC->getValue().isSignMask())
5122 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5124 if (
V->getType()->isIntegerTy(1))
5125 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5128 case Instruction::LShr:
5137 if (SA->getValue().ult(
BitWidth)) {
5139 ConstantInt::get(SA->getContext(),
5141 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5146 case Instruction::ExtractValue: {
5148 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5156 bool Signed = WO->isSigned();
5159 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5164 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5175 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5176 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5178 return std::nullopt;
5204 if (
Op == SymbolicPHI)
5209 if (SourceBits != NewBits)
5227 if (!L || L->getHeader() != PN->
getParent())
5285std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5286ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5294 assert(L &&
"Expecting an integer loop header phi");
5299 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5300 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5301 Value *
V = PN->getIncomingValue(i);
5302 if (
L->contains(PN->getIncomingBlock(i))) {
5305 }
else if (BEValueV !=
V) {
5309 }
else if (!StartValueV) {
5311 }
else if (StartValueV !=
V) {
5312 StartValueV =
nullptr;
5316 if (!BEValueV || !StartValueV)
5317 return std::nullopt;
5319 const SCEV *BEValue =
getSCEV(BEValueV);
5326 return std::nullopt;
5330 unsigned FoundIndex =
Add->getNumOperands();
5331 Type *TruncTy =
nullptr;
5333 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5336 if (FoundIndex == e) {
5341 if (FoundIndex ==
Add->getNumOperands())
5342 return std::nullopt;
5346 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5347 if (i != FoundIndex)
5348 Ops.push_back(
Add->getOperand(i));
5354 return std::nullopt;
5407 const SCEV *StartVal =
getSCEV(StartValueV);
5408 const SCEV *PHISCEV =
5435 auto getExtendedExpr = [&](
const SCEV *Expr,
5436 bool CreateSignExtend) ->
const SCEV * {
5439 const SCEV *ExtendedExpr =
5442 return ExtendedExpr;
5450 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5451 const SCEV *ExtendedExpr) ->
bool {
5452 return Expr != ExtendedExpr &&
5456 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5457 if (PredIsKnownFalse(StartVal, StartExtended)) {
5459 return std::nullopt;
5464 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5465 if (PredIsKnownFalse(Accum, AccumExtended)) {
5467 return std::nullopt;
5470 auto AppendPredicate = [&](
const SCEV *Expr,
5471 const SCEV *ExtendedExpr) ->
void {
5472 if (Expr != ExtendedExpr &&
5480 AppendPredicate(StartVal, StartExtended);
5481 AppendPredicate(Accum, AccumExtended);
5489 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5490 std::make_pair(NewAR, Predicates);
5492 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5496std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5501 return std::nullopt;
5504 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5505 if (
I != PredicatedSCEVRewrites.end()) {
5506 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5509 if (Rewrite.first == SymbolicPHI)
5510 return std::nullopt;
5514 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5518 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5519 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5524 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5525 return std::nullopt;
5545 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5546 if (Expr1 != Expr2 &&
5547 !AllPreds.
implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5548 !AllPreds.
implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5583const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5585 Value *StartValueV) {
5588 assert(BEValueV && StartValueV);
5590 const SCEV *Accum =
nullptr;
5593 if (BO->Opcode != Instruction::Add)
5596 if (BO->LHS == PN &&
L->isLoopInvariant(BO->RHS))
5598 else if (BO->RHS == PN &&
L->isLoopInvariant(BO->LHS))
5612 if (!
GEP ||
GEP->getPointerOperand() != PN ||
GEP->getNumIndices() != 1)
5615 if (!
L->isLoopInvariant(Idx))
5624 const SCEV *StartVal =
getSCEV(StartValueV);
5625 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5626 insertValueToMap(PN, PHISCEV);
5629 inferNoWrapViaConstantRanges(AR);
5636 "Accum is defined outside L, but is not invariant?");
5637 if (isAddRecNeverPoison(BEInst, L))
5644const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5652 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5658 }
else if (BEValueV !=
V) {
5662 }
else if (!StartValueV) {
5664 }
else if (StartValueV !=
V) {
5665 StartValueV =
nullptr;
5669 if (!BEValueV || !StartValueV)
5672 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5673 "PHI node already processed?");
5677 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5682 insertValueToMap(PN, SymbolicName);
5686 const SCEV *BEValue =
getSCEV(BEValueV);
5696 unsigned FoundIndex =
Add->getNumOperands();
5697 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5698 if (
Add->getOperand(i) == SymbolicName)
5699 if (FoundIndex == e) {
5704 if (FoundIndex !=
Add->getNumOperands()) {
5707 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5708 if (i != FoundIndex)
5709 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5721 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5728 if (
GEP->getOperand(0) == PN)
5736 const SCEV *StartVal =
getSCEV(StartValueV);
5737 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5742 forgetMemoizedResults({SymbolicName});
5743 insertValueToMap(PN, PHISCEV);
5746 inferNoWrapViaConstantRanges(AR);
5770 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5771 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5774 const SCEV *StartVal =
getSCEV(StartValueV);
5775 if (Start == StartVal) {
5779 forgetMemoizedResults({SymbolicName});
5780 insertValueToMap(PN, Shifted);
5790 eraseValueFromMap(PN);
5805 Use &LeftUse =
Merge->getOperandUse(0);
5806 Use &RightUse =
Merge->getOperandUse(1);
5842 assert(IDom &&
"At least the entry block should dominate PN");
5850const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
5855 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
5872 CommonInst = IncomingInst;
5888ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
5894 const SCEV *CommonSCEV =
getSCEV(CommonInst);
5895 bool SCEVExprsIdentical =
5897 [
this, CommonSCEV](
Value *
V) { return CommonSCEV == getSCEV(V); });
5898 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
5901const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
5902 if (
const SCEV *S = createAddRecFromPHI(PN))
5912 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
5915 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
5924 struct FindClosure {
5925 const SCEV *OperandToFind;
5931 bool canRecurseInto(
SCEVTypes Kind)
const {
5934 return RootKind == Kind || NonSequentialRootKind == Kind ||
5939 : OperandToFind(OperandToFind), RootKind(RootKind),
5940 NonSequentialRootKind(
5944 bool follow(
const SCEV *S) {
5945 Found = S == OperandToFind;
5947 return !isDone() && canRecurseInto(S->
getSCEVType());
5950 bool isDone()
const {
return Found; }
5953 FindClosure FC(OperandToFind, RootKind);
5958std::optional<const SCEV *>
5959ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
5969 switch (ICI->getPredicate()) {
5983 bool Signed = ICI->isSigned();
5984 const SCEV *LA =
getSCEV(TrueVal);
5992 if (LA == LS &&
RA == RS)
5994 if (LA == RS &&
RA == LS)
5997 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
5998 if (
Op->getType()->isPointerTy()) {
6009 LS = CoerceOperand(LS);
6010 RS = CoerceOperand(RS);
6034 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6035 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6049 X = ZExt->getOperand();
6051 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6062 return std::nullopt;
6065static std::optional<const SCEV *>
6067 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6071 "Unexpected operands of a select.");
6083 return std::nullopt;
6098static std::optional<const SCEV *>
6102 return std::nullopt;
6105 const auto *SETrue = SE->
getSCEV(TrueVal);
6106 const auto *SEFalse = SE->
getSCEV(FalseVal);
6110const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6112 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6114 V->getType() ==
TrueVal->getType() &&
6115 "Types of select hands and of the result must match.");
6118 if (!
V->getType()->isIntegerTy(1))
6121 if (std::optional<const SCEV *> S =
6134 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6138 if (std::optional<const SCEV *> S =
6139 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6145 return createNodeForSelectOrPHIViaUMinSeq(
V,
Cond, TrueVal, FalseVal);
6151 assert(
GEP->getSourceElementType()->isSized() &&
6152 "GEP source element type must be sized");
6155 for (
Value *Index :
GEP->indices())
6160APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6163 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6166 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6168 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6171 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6189 return GetShiftedByZeros(TZ);
6199 return GetShiftedByZeros(TZ);
6203 if (
M->hasNoUnsignedWrap()) {
6206 for (
const SCEV *Operand :
M->operands().drop_front())
6214 for (
const SCEV *Operand :
M->operands())
6216 return GetShiftedByZeros(TZ);
6221 if (
N->hasNoUnsignedWrap())
6222 return GetGCDMultiple(
N);
6225 for (
const SCEV *Operand :
N->operands().drop_front())
6227 return GetShiftedByZeros(TZ);
6244 CtxI = &*F.getEntryBlock().begin();
6251 .allowEphemerals(
true))
6252 .countMinTrailingZeros();
6253 return GetShiftedByZeros(
Known);
6266 return getConstantMultipleImpl(S, CtxI);
6268 auto I = ConstantMultipleCache.find(S);
6269 if (
I != ConstantMultipleCache.end())
6272 APInt Result = getConstantMultipleImpl(S, CtxI);
6273 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6274 assert(InsertPair.second &&
"Should insert a new key");
6275 return InsertPair.first->second;
6292 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6295 if (std::optional<ConstantRange>
Range = CB->getRange())
6299 if (std::optional<ConstantRange>
Range =
A->getRange())
6302 return std::nullopt;
6309 UnsignedRanges.erase(AddRec);
6310 SignedRanges.erase(AddRec);
6311 ConstantMultipleCache.erase(AddRec);
6316getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6342 Value *Start, *Step;
6349 assert(L && L->getHeader() ==
P->getParent());
6362 case Instruction::AShr:
6363 case Instruction::LShr:
6364 case Instruction::Shl:
6379 KnownStep.getBitWidth() ==
BitWidth);
6382 auto MaxShiftAmt = KnownStep.getMaxValue();
6384 bool Overflow =
false;
6385 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6392 case Instruction::AShr: {
6400 if (KnownStart.isNonNegative())
6403 KnownStart.getMaxValue() + 1);
6404 if (KnownStart.isNegative())
6407 KnownEnd.getMaxValue() + 1);
6410 case Instruction::LShr: {
6419 KnownStart.getMaxValue() + 1);
6421 case Instruction::Shl: {
6425 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6426 return ConstantRange(KnownStart.getMinValue(),
6427 KnownEnd.getMaxValue() + 1);
6452 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6459ScalarEvolution::getRangeRefIter(
const SCEV *S,
6460 ScalarEvolution::RangeSignHint SignHint) {
6461 DenseMap<const SCEV *, ConstantRange> &Cache =
6462 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6465 SmallPtrSet<const SCEV *, 8> Seen;
6469 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6470 if (!Seen.
insert(Expr).second)
6503 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6504 const SCEV *
P = WorkList[
I];
6508 for (
const SCEV *
Op :
P->operands())
6521 if (!WorkList.
empty()) {
6526 getRangeRef(
P, SignHint);
6530 return getRangeRef(S, SignHint, 0);
6533const APInt *ScalarEvolution::getConstantAPIntOrNull(
const SCEV *S) {
6535 return &
C->getAPInt();
6543 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6544 DenseMap<const SCEV *, ConstantRange> &Cache =
6545 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6552 auto I = Cache.
find(S);
6553 if (
I != Cache.
end())
6557 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6561 if (
Depth > Opts.scev_range_iter_threshold)
6562 return getRangeRefIter(S, SignHint);
6565 ConstantRange ConservativeResult(
BitWidth,
true);
6566 using OBO = OverflowingBinaryOperator;
6570 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6574 ConservativeResult =
6581 ConservativeResult = ConstantRange(
6597 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6604 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6611 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6616 return setRange(Cast, SignHint,
X);
6621 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6622 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6624 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6625 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6626 ConservativeResult =
6627 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6629 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6630 unsigned WrapType = OBO::AnyWrap;
6631 if (
Add->hasNoSignedWrap())
6632 WrapType |= OBO::NoSignedWrap;
6633 if (
Add->hasNoUnsignedWrap())
6634 WrapType |= OBO::NoUnsignedWrap;
6636 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6638 return setRange(
Add, SignHint,
6639 ConservativeResult.intersectWith(
X, RangeType));
6643 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6645 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6646 return setRange(
Mul, SignHint,
6647 ConservativeResult.intersectWith(
X, RangeType));
6651 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6652 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6653 return setRange(UDiv, SignHint,
6654 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6662 if (!UnsignedMinValue.
isZero())
6663 ConservativeResult = ConservativeResult.intersectWith(
6664 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6673 bool AllNonNeg =
true;
6674 bool AllNonPos =
true;
6675 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6682 ConservativeResult = ConservativeResult.intersectWith(
6687 ConservativeResult = ConservativeResult.intersectWith(
6696 const SCEV *MaxBEScev =
6710 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
6712 ConservativeResult =
6713 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6716 auto RangeFromFactoring = getRangeViaFactoring(
6718 ConservativeResult =
6719 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6724 if (Opts.scalar_evolution_use_expensive_range_sharpening) {
6725 const SCEV *SymbolicMaxBECount =
6730 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6731 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6732 ConservativeResult =
6733 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6738 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6748 ID = Intrinsic::umax;
6751 ID = Intrinsic::smax;
6755 ID = Intrinsic::umin;
6758 ID = Intrinsic::smin;
6765 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6766 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6768 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6769 return setRange(S, SignHint,
6770 ConservativeResult.intersectWith(
X, RangeType));
6779 ConservativeResult =
6780 ConservativeResult.intersectWith(*MDRange, RangeType);
6785 auto CR = getRangeForUnknownRecurrence(U);
6786 ConservativeResult = ConservativeResult.intersectWith(CR);
6797 if (
U->getType()->isPointerTy()) {
6800 unsigned PtrIdxDiff =
6801 DL.getPointerTypeSizeInBits(
U->getType()) -
BitWidth;
6802 NS = NS > PtrIdxDiff ? NS - PtrIdxDiff : 1;
6807 if (!
Known.Zero.getHiBits(NS).isZero())
6808 Known.Zero.setHighBits(NS);
6809 if (!
Known.One.getHiBits(NS).isZero())
6810 Known.One.setHighBits(NS);
6813 if (
Known.getMinValue() !=
Known.getMaxValue() + 1)
6814 ConservativeResult = ConservativeResult.intersectWith(
6815 ConstantRange(
Known.getMinValue(),
Known.getMaxValue() + 1),
6818 ConservativeResult = ConservativeResult.intersectWith(
6823 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6827 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
6828 DL, CanBeNull,
nullptr);
6844 ConservativeResult = ConservativeResult.intersectWith(
6854 return getRangeRef(AR, SignHint,
Depth + 1);
6858 ConstantRange RangeFromOps(
BitWidth,
false);
6860 for (
const auto &
Op :
Phi->operands()) {
6862 RangeFromOps = RangeFromOps.unionWith(OpRange);
6864 if (RangeFromOps.isFullSet())
6867 ConservativeResult =
6868 ConservativeResult.intersectWith(RangeFromOps, RangeType);
6874 if (
II->getIntrinsicID() == Intrinsic::vscale) {
6876 ConservativeResult = ConservativeResult.difference(Disallowed);
6879 return setRange(U, SignHint, std::move(ConservativeResult));
6885 return setRange(S, SignHint, std::move(ConservativeResult));
6893static std::pair<ConstantRange, bool>
6901 if (Step == 0 || MaxBECount == 0)
6902 return {StartRange,
true};
6908 return {ConstantRange::getFull(
BitWidth),
false};
6924 return {ConstantRange::getFull(
BitWidth),
false};
6937 APInt MovedBoundary;
6942 MovedBoundary = StartLower - std::move(
Offset);
6945 MovedBoundary = StartUpper + std::move(
Offset);
6949 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
6956 if (StartRange.
contains(MovedBoundary))
6957 return {ConstantRange::getFull(
BitWidth),
false};
6960 Descending ? std::move(MovedBoundary) : std::move(StartLower);
6962 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
6970std::pair<ConstantRange, SCEVFlags>
6971ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
6972 const APInt &MaxBECount) {
6976 "mismatched bit widths");
6985 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
6990 StepSRange.
getSignedMax(), StartSRange, MaxBECount,
true);
6991 SR = SR.unionWith(SRMax);
7010ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7012 ScalarEvolution::RangeSignHint SignHint) {
7013 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7015 "This only works for non-self-wrapping AddRecs!");
7016 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7020 return ConstantRange::getFull(
BitWidth);
7028 return ConstantRange::getFull(
BitWidth);
7032 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7034 MaxItersWithoutWrap))
7035 return ConstantRange::getFull(
BitWidth);
7056 ConstantRange StartRange = getRangeRef(Start, SignHint);
7057 ConstantRange EndRange = getRangeRef(
End, SignHint);
7058 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7062 return RangeBetween;
7067 return ConstantRange::getFull(
BitWidth);
7070 isKnownPredicateViaConstantRanges(LEPred, Start,
End))
7071 return RangeBetween;
7073 isKnownPredicateViaConstantRanges(GEPred, Start,
End))
7074 return RangeBetween;
7075 return ConstantRange::getFull(
BitWidth);
7080 const APInt &MaxBECount) {
7087 "mismatched bit widths");
7089 struct SelectPattern {
7090 Value *Condition =
nullptr;
7094 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7096 std::optional<unsigned> CastOp;
7110 CastOp = SCast->getSCEVType();
7111 S = SCast->getOperand();
7114 using namespace llvm::PatternMatch;
7121 Condition =
nullptr;
7153 bool isRecognized() {
return Condition !=
nullptr; }
7156 SelectPattern StartPattern(*
this,
BitWidth, Start);
7157 if (!StartPattern.isRecognized())
7158 return ConstantRange::getFull(
BitWidth);
7160 SelectPattern StepPattern(*
this,
BitWidth, Step);
7161 if (!StepPattern.isRecognized())
7162 return ConstantRange::getFull(
BitWidth);
7164 if (StartPattern.Condition != StepPattern.Condition) {
7168 return ConstantRange::getFull(
BitWidth);
7179 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7180 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7181 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7182 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7184 ConstantRange TrueRange =
7185 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7186 ConstantRange FalseRange =
7187 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7200 PDI && PDI->isDisjoint()) {
7215ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7228 SmallPtrSet<const SCEV *, 16> Visited;
7230 auto pushOp = [&](
const SCEV *S) {
7231 if (!Visited.
insert(S).second)
7234 if (Visited.
size() > 30) {
7245 while (!Worklist.
empty()) {
7247 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7248 if (!Bound || DT.dominates(Bound, DefI))
7255 return Bound ? Bound : &*F.getEntryBlock().begin();
7261 return getDefiningScopeBound(
Ops, Discard);
7264bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7266 if (
A->getParent() ==
B->getParent() &&
7271 auto *BLoop = LI.getLoopFor(
B->getParent());
7272 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7273 BLoop->getLoopPreheader() ==
A->getParent() &&
7275 A->getParent()->end()) &&
7283 SCEVPoisonCollector PC(
true);
7285 return PC.MaybePoison.
empty();
7298bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7315 for (
const Use &
Op :
I->operands()) {
7321 auto *DefI = getDefiningScopeBound(SCEVOps);
7322 return isGuaranteedToTransferExecutionTo(DefI,
I);
7325bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7327 if (isSCEVExprNeverPoison(
I))
7338 auto *ExitingBB =
L->getExitingBlock();
7342 SmallPtrSet<const Value *, 16> KnownPoison;
7351 while (!Worklist.
empty()) {
7354 for (
const Use &U :
Poison->uses()) {
7357 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7361 if (KnownPoison.
insert(PoisonUser).second)
7369ScalarEvolution::LoopProperties
7370ScalarEvolution::getLoopProperties(
const Loop *L) {
7371 using LoopProperties = ScalarEvolution::LoopProperties;
7373 auto Itr = LoopPropertiesCache.find(L);
7374 if (Itr == LoopPropertiesCache.end()) {
7377 return !
SI->isSimple();
7385 if (!
MI->isVolatile())
7389 if (
I->isDroppable())
7392 return I->mayWriteToMemory();
7395 LoopProperties LP = {
true,
7398 for (
auto *BB :
L->getBlocks())
7399 for (
auto &
I : *BB) {
7401 LP.HasNoAbnormalExits =
false;
7402 if (HasSideEffects(&
I))
7403 LP.HasNoSideEffects =
false;
7404 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7408 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7409 assert(InsertPair.second &&
"We just checked!");
7410 Itr = InsertPair.first;
7423const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7429 Stack.emplace_back(V,
false);
7430 while (!Stack.empty()) {
7431 auto E = Stack.back();
7432 Value *CurV = E.getPointer();
7440 const SCEV *CreatedSCEV =
nullptr;
7443 CreatedSCEV = createSCEV(CurV);
7448 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7452 insertValueToMap(CurV, CreatedSCEV);
7455 Stack.back().setInt(
true);
7458 Stack.emplace_back(
Op,
false);
7475 if (!DT.isReachableFromEntry(
I->getParent()))
7487 switch (BO->Opcode) {
7488 case Instruction::Add:
7489 case Instruction::Mul: {
7496 Ops.push_back(BO->
Op);
7500 Ops.push_back(BO->RHS);
7503 (BO->Opcode == Instruction::Add &&
7504 (NewBO->Opcode != Instruction::Add &&
7505 NewBO->Opcode != Instruction::Sub)) ||
7506 (BO->Opcode == Instruction::Mul &&
7507 NewBO->Opcode != Instruction::Mul)) {
7508 Ops.push_back(BO->LHS);
7513 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7516 Ops.push_back(BO->LHS);
7524 case Instruction::Sub:
7525 case Instruction::UDiv:
7526 case Instruction::URem:
7528 case Instruction::AShr:
7529 case Instruction::Shl:
7530 case Instruction::Xor:
7534 case Instruction::And:
7535 case Instruction::Or:
7539 case Instruction::LShr:
7546 Ops.push_back(BO->LHS);
7547 Ops.push_back(BO->RHS);
7551 switch (
U->getOpcode()) {
7552 case Instruction::Trunc:
7553 case Instruction::ZExt:
7554 case Instruction::SExt:
7555 case Instruction::PtrToAddr:
7556 case Instruction::PtrToInt:
7557 Ops.push_back(
U->getOperand(0));
7560 case Instruction::BitCast:
7562 Ops.push_back(
U->getOperand(0));
7567 case Instruction::SDiv:
7568 case Instruction::SRem:
7569 Ops.push_back(
U->getOperand(0));
7570 Ops.push_back(
U->getOperand(1));
7573 case Instruction::GetElementPtr:
7575 "GEP source element type must be sized");
7579 case Instruction::IntToPtr:
7582 case Instruction::PHI:
7613 Ops.push_back(CondICmp->getOperand(0));
7614 Ops.push_back(CondICmp->getOperand(1));
7634 case Instruction::Select: {
7636 auto CanSimplifyToUnknown = [
this,
U]() {
7654 if (CanSimplifyToUnknown())
7661 case Instruction::Call:
7662 case Instruction::Invoke:
7669 switch (
II->getIntrinsicID()) {
7670 case Intrinsic::abs:
7671 Ops.push_back(
II->getArgOperand(0));
7673 case Intrinsic::umax:
7674 case Intrinsic::umin:
7675 case Intrinsic::smax:
7676 case Intrinsic::smin:
7677 case Intrinsic::usub_sat:
7678 case Intrinsic::uadd_sat:
7679 Ops.push_back(
II->getArgOperand(0));
7680 Ops.push_back(
II->getArgOperand(1));
7682 case Intrinsic::start_loop_iterations:
7683 case Intrinsic::annotation:
7684 case Intrinsic::ptr_annotation:
7685 Ops.push_back(
II->getArgOperand(0));
7697const SCEV *ScalarEvolution::createSCEV(
Value *
V) {
7706 if (!DT.isReachableFromEntry(
I->getParent()))
7720 switch (BO->Opcode) {
7721 case Instruction::Add: {
7747 if (BO->Opcode == Instruction::Sub)
7755 if (BO->Opcode == Instruction::Sub)
7761 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7762 NewBO->Opcode != Instruction::Sub)) {
7772 case Instruction::Mul: {
7792 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7801 case Instruction::UDiv:
7805 case Instruction::URem:
7809 case Instruction::Sub: {
7812 Flags = getNoWrapFlagsFromUB(BO->
Op);
7817 Value *PtrLHS =
nullptr, *PtrRHS =
nullptr;
7820 if (HasPtrLHS || HasPtrRHS) {
7825 auto GetOp = [&](
bool HasPtr,
Value *PtrOp,
Value *OrigOp,
7826 bool BothPtr) ->
const SCEV * {
7829 const SCEV *PtrSCEV =
getSCEV(PtrOp);
7839 const SCEV *
L = GetOp(HasPtrLHS, PtrLHS, BO->LHS, HasPtrRHS);
7840 const SCEV *
R = GetOp(HasPtrRHS, PtrRHS, BO->RHS, HasPtrLHS);
7848 case Instruction::And:
7854 if (CI->isMinusOne())
7856 const APInt &
A = CI->getValue();
7862 unsigned LZ =
A.countl_zero();
7863 unsigned TZ =
A.countr_zero();
7868 APInt EffectiveMask =
7870 if ((LZ != 0 || TZ != 0) && !((~
A & ~
Known.Zero) & EffectiveMask)) {
7873 const SCEV *ShiftedLHS =
nullptr;
7877 unsigned MulZeros = OpC->getAPInt().countr_zero();
7878 unsigned GCD = std::min(MulZeros, TZ);
7883 const SCEV *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
7905 case Instruction::Or:
7914 case Instruction::Xor:
7917 if (CI->isMinusOne())
7926 if (LBO->getOpcode() == Instruction::And &&
7927 LCI->getValue() == CI->getValue())
7928 if (
const SCEVZeroExtendExpr *Z =
7931 const SCEV *Z0 =
Z->getOperand();
7938 if (CI->getValue().isMask(Z0TySize))
7944 APInt Trunc = CI->getValue().trunc(Z0TySize);
7953 case Instruction::Shl:
7971 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
7980 ConstantInt *
X = ConstantInt::get(
7986 case Instruction::AShr:
8008 const SCEV *AddTruncateExpr =
nullptr;
8009 ConstantInt *ShlAmtCI =
nullptr;
8010 const SCEV *AddConstant =
nullptr;
8012 if (L &&
L->getOpcode() == Instruction::Add) {
8020 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8027 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8035 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8040 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8045 if (AddTruncateExpr && ShlAmtCI) {
8057 const APInt &ShlAmt = ShlAmtCI->
getValue();
8061 const SCEV *CompositeExpr =
8063 if (
L->getOpcode() != Instruction::Shl)
8064 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8073 switch (
U->getOpcode()) {
8074 case Instruction::Trunc:
8077 case Instruction::ZExt:
8080 case Instruction::SExt:
8089 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8090 Type *Ty =
U->getType();
8098 case Instruction::BitCast:
8104 case Instruction::PtrToAddr: {
8111 case Instruction::PtrToInt:
8115 case Instruction::IntToPtr:
8119 case Instruction::SDiv:
8126 case Instruction::SRem:
8133 case Instruction::GetElementPtr:
8136 case Instruction::PHI:
8139 case Instruction::Select:
8140 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8143 case Instruction::Call:
8144 case Instruction::Invoke:
8149 switch (
II->getIntrinsicID()) {
8150 case Intrinsic::abs:
8154 case Intrinsic::umax:
8158 case Intrinsic::umin:
8162 case Intrinsic::smax:
8166 case Intrinsic::smin:
8170 case Intrinsic::usub_sat: {
8171 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8172 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8176 case Intrinsic::uadd_sat: {
8177 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8178 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8182 case Intrinsic::start_loop_iterations:
8183 case Intrinsic::annotation:
8184 case Intrinsic::ptr_annotation:
8188 case Intrinsic::vscale:
8208 auto *ExitCountType = ExitCount->
getType();
8209 assert(ExitCountType->isIntegerTy());
8211 1 + ExitCountType->getScalarSizeInBits());
8224 auto CanAddOneWithoutOverflow = [&]() {
8226 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8237 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8267 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8268 assert(L->isLoopExiting(ExitingBlock) &&
8269 "Exiting block must actually branch out of the loop!");
8278 const auto *MaxExitCount =
8286 L->getExitingBlocks(ExitingBlocks);
8289 if (ExitingBlocks.
empty() ||
8304 LoopGuards &Guards) {
8308 const SCEV *TCExpr =
8316 : (
unsigned)Multiple.getZExtValue();
8320 const SCEV *ExitCount) {
8343 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8344 assert(L->isLoopExiting(ExitingBlock) &&
8345 "Exiting block must actually branch out of the loop!");
8355 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8357 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8359 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8369 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8372 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8375 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8383 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8390 return getBackedgeTakenInfo(L).getExact(L,
this);
8392 return getBackedgeTakenInfo(L).getConstantMax(
this);
8394 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8401 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8406 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8410 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8420 for (
PHINode &PN : Header->phis())
8421 if (Visited.
insert(&PN).second)
8425ScalarEvolution::BackedgeTakenInfo &
8426ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8427 auto &BTI = getBackedgeTakenInfo(L);
8428 if (BTI.hasFullInfo())
8431 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8434 return Pair.first->second;
8436 BackedgeTakenInfo
Result =
8437 computeBackedgeTakenCount(L,
true);
8439 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8442ScalarEvolution::BackedgeTakenInfo &
8443ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8449 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8450 BackedgeTakenCounts.try_emplace(L);
8452 return Pair.first->second;
8457 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8464 if (
Result.hasAnyInfo()) {
8467 auto LoopUsersIt = LoopUsers.find(L);
8468 if (LoopUsersIt != LoopUsers.end())
8470 forgetMemoizedResults(ToForget);
8473 for (PHINode &PN :
L->getHeader()->phis())
8474 ConstantEvolutionLoopExitValue.erase(&PN);
8482 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8491 BackedgeTakenCounts.clear();
8492 PredicatedBackedgeTakenCounts.clear();
8493 BECountUsers.clear();
8494 LoopPropertiesCache.clear();
8495 ConstantEvolutionLoopExitValue.clear();
8496 ValueExprMap.clear();
8497 ValuesAtScopes.clear();
8498 ValuesAtScopesUsers.clear();
8499 LoopDispositions.clear();
8500 BlockDispositions.clear();
8501 UnsignedRanges.clear();
8502 SignedRanges.clear();
8503 ExprValueMap.clear();
8505 ConstantMultipleCache.clear();
8506 PredicatedSCEVRewrites.clear();
8508 FoldCacheUser.clear();
8510void ScalarEvolution::visitAndClearUsers(
8515 if (ValueExprMap.
empty()) {
8519 while (!Worklist.
empty()) {
8526 if (It != ValueExprMap.
end()) {
8528 eraseValueFromMap(It->first);
8530 ConstantEvolutionLoopExitValue.erase(PN);
8544 while (!LoopWorklist.
empty()) {
8548 forgetBackedgeTakenCounts(CurrL,
false);
8549 forgetBackedgeTakenCounts(CurrL,
true);
8552 PredicatedSCEVRewrites.remove_if(
8553 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8555 auto LoopUsersItr = LoopUsers.find(CurrL);
8556 if (LoopUsersItr != LoopUsers.end())
8561 visitAndClearUsers(Worklist, Visited, ToForget);
8563 LoopPropertiesCache.erase(CurrL);
8566 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8568 forgetMemoizedResults(ToForget);
8585 visitAndClearUsers(Worklist, Visited, ToForget);
8587 forgetMemoizedResults(ToForget);
8598 visitAndClearUsers(Worklist, Visited, ToForget);
8600 forgetMemoizedResults(ToForget);
8608 auto InvalidateValue = [&](
Value *Val) {
8612 struct InvalidationRootCollector {
8616 InvalidationRootCollector(
Loop *L) : L(L) {}
8618 bool follow(
const SCEV *S) {
8624 if (L->contains(AddRec->
getLoop()))
8629 bool isDone()
const {
return false; }
8632 InvalidationRootCollector
C(L);
8634 forgetMemoizedResults(
C.Roots);
8657 BlockDispositions.clear();
8658 LoopDispositions.clear();
8675 while (!Worklist.
empty()) {
8677 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8678 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8679 if (!LoopDispoRemoved && !BlockDispoRemoved)
8681 auto Users = SCEVUsers.find(Curr);
8682 if (
Users != SCEVUsers.end())
8695const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8699 if (!isComplete() || ExitNotTaken.
empty())
8710 for (
const auto &ENT : ExitNotTaken) {
8711 const SCEV *BECount = ENT.ExactNotTaken;
8714 "We should only have known counts for exiting blocks that dominate "
8717 Ops.push_back(BECount);
8722 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8723 "Predicate should be always true!");
8732const ScalarEvolution::ExitNotTakenInfo *
8733ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8734 const BasicBlock *ExitingBlock,
8735 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8736 for (
const auto &ENT : ExitNotTaken)
8737 if (ENT.ExitingBlock == ExitingBlock) {
8738 if (ENT.hasAlwaysTruePredicate())
8740 else if (Predicates) {
8750const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8752 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8753 if (!getConstantMax())
8756 for (
const auto &ENT : ExitNotTaken)
8757 if (!ENT.hasAlwaysTruePredicate()) {
8765 "No point in having a non-constant max backedge taken count!");
8766 return getConstantMax();
8769const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8771 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8779 for (
const auto &ENT : ExitNotTaken) {
8780 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8783 "We should only have known counts for exiting blocks that "
8789 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8790 "Predicate should be always true!");
8793 if (ExitCounts.
empty())
8802bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8804 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8805 return !ENT.hasAlwaysTruePredicate();
8807 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8823 this->ExactNotTaken = E = ConstantMaxNotTaken;
8824 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8829 "Exact is not allowed to be less precise than Constant Max");
8832 "Exact is not allowed to be less precise than Symbolic Max");
8835 "Symbolic Max is not allowed to be less precise than Constant Max");
8838 "No point in having a non-constant max backedge taken count!");
8840 for (
const auto PredList : PredLists)
8841 for (
const auto *
P : PredList) {
8849 "Backedge count should be int");
8852 "Max backedge count should be int");
8865ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
8867 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
8868 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
8869 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8871 ExitNotTaken.reserve(ExitCounts.
size());
8872 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
8873 std::back_inserter(ExitNotTaken),
8874 [&](
const EdgeExitInfo &EEI) {
8875 BasicBlock *ExitBB = EEI.first;
8876 const ExitLimit &EL = EEI.second;
8877 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
8878 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
8883 "No point in having a non-constant max backedge taken count!");
8887ScalarEvolution::BackedgeTakenInfo
8888ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
8889 bool AllowPredicates) {
8891 L->getExitingBlocks(ExitingBlocks);
8893 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8896 bool CouldComputeBECount =
true;
8898 const SCEV *MustExitMaxBECount =
nullptr;
8899 const SCEV *MayExitMaxBECount =
nullptr;
8900 bool MustExitMaxOrZero =
false;
8901 bool IsOnlyExit = ExitingBlocks.
size() == 1;
8912 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
8913 if (ExitIfTrue == CI->
isZero())
8917 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
8919 assert((AllowPredicates || EL.Predicates.empty()) &&
8920 "Predicated exit limit when predicates are not allowed!");
8925 ++NumExitCountsComputed;
8929 CouldComputeBECount =
false;
8936 "Exact is known but symbolic isn't?");
8937 ++NumExitCountsNotComputed;
8952 DT.dominates(ExitBB, Latch)) {
8953 if (!MustExitMaxBECount) {
8954 MustExitMaxBECount = EL.ConstantMaxNotTaken;
8955 MustExitMaxOrZero = EL.MaxOrZero;
8958 EL.ConstantMaxNotTaken);
8962 MayExitMaxBECount = EL.ConstantMaxNotTaken;
8965 EL.ConstantMaxNotTaken);
8969 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
8973 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
8979 for (
const auto &Pair : ExitCounts) {
8981 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
8983 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
8984 {
L, AllowPredicates});
8986 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
8987 MaxBECount, MaxOrZero);
8990ScalarEvolution::ExitLimit
8991ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
8992 bool IsOnlyExit,
bool AllowPredicates) {
8993 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
8997 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9002 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9003 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9004 "It should have one successor in loop and one exit block!");
9015 if (!
L->contains(SBB)) {
9020 assert(Exit &&
"Exiting block must have at least one exit");
9021 return computeExitLimitFromSingleExitSwitch(
9022 L, SI, Exit, IsOnlyExit);
9029 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9030 bool AllowPredicates) {
9031 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9032 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9033 ControlsOnlyExit, AllowPredicates);
9036std::optional<ScalarEvolution::ExitLimit>
9037ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9038 bool ExitIfTrue,
bool ControlsOnlyExit,
9039 bool AllowPredicates) {
9041 (void)this->ExitIfTrue;
9042 (void)this->AllowPredicates;
9044 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9045 this->AllowPredicates == AllowPredicates &&
9046 "Variance in assumed invariant key components!");
9047 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9048 if (Itr == TripCountMap.end())
9049 return std::nullopt;
9053void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9055 bool ControlsOnlyExit,
9056 bool AllowPredicates,
9058 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9059 this->AllowPredicates == AllowPredicates &&
9060 "Variance in assumed invariant key components!");
9062 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9063 assert(InsertResult.second &&
"Expected successful insertion!");
9068ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9069 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9070 bool ControlsOnlyExit,
bool AllowPredicates) {
9072 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9076 ExitLimit EL = computeExitLimitFromCondImpl(
9077 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9078 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9082ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9083 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9084 bool ControlsOnlyExit,
bool AllowPredicates) {
9086 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9087 Cache, L, ExitCond, ExitIfTrue, AllowPredicates))
9088 return *LimitFromBinOp;
9094 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9095 if (EL.hasFullInfo() || !AllowPredicates)
9099 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9119 const WithOverflowInst *WO;
9135 ControlsOnlyExit, AllowPredicates);
9136 if (EL.hasAnyInfo())
9141 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9144std::optional<ScalarEvolution::ExitLimit>
9145ScalarEvolution::computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache,
9149 bool AllowPredicates) {
9158 return std::nullopt;
9162 ExitLimit EL0 = computeExitLimitFromCondCached(
9163 Cache, L, Op0, ExitIfTrue,
false, AllowPredicates);
9164 ExitLimit EL1 = computeExitLimitFromCondCached(
9165 Cache, L, Op1, ExitIfTrue,
false, AllowPredicates);
9170 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9175 if (EitherMayExit) {
9185 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9187 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9190 EL1.ConstantMaxNotTaken);
9192 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9194 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9197 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9201 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9202 BECount = EL0.ExactNotTaken;
9215 SymbolicMaxBECount =
9217 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9221ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9222 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9223 bool AllowPredicates) {
9237 if (EL.hasAnyInfo())
9240 auto *ExhaustiveCount =
9241 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9244 return ExhaustiveCount;
9246 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9249ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9251 bool ControlsOnlyExit,
bool AllowPredicates) {
9276 ConstantRange CompRange =
9294 InnerLHS = ZExt->getOperand();
9341 if (EL.hasAnyInfo())
9358 if (EL.hasAnyInfo())
return EL;
9365 if (!Opts.scalar_evolution_finite_loop || !ControllingFiniteLoop ||
9391 ControlsOnlyExit, AllowPredicates);
9392 if (EL.hasAnyInfo())
9400 if (!Opts.scalar_evolution_finite_loop || !ControllingFiniteLoop ||
9410 ControlsOnlyExit, AllowPredicates);
9411 if (EL.hasAnyInfo())
9422ScalarEvolution::ExitLimit
9423ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9425 BasicBlock *ExitingBlock,
9426 bool ControlsOnlyExit) {
9427 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9430 if (
Switch->getDefaultDest() == ExitingBlock)
9434 "Default case must not exit the loop!");
9440 if (EL.hasAnyInfo())
9452 "Evaluation of SCEV at constant didn't fold correctly?");
9456ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9466 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9473 auto MatchPositiveShift = [](
Value *
V,
Value *&OutLHS,
9475 unsigned &OutShiftAmt) {
9476 using namespace PatternMatch;
9478 ConstantInt *ShiftAmt;
9480 OutOpCode = Instruction::LShr;
9482 OutOpCode = Instruction::AShr;
9484 OutOpCode = Instruction::Shl;
9489 if (Amt == 0 || Amt >= OutLHS->getType()->getScalarSizeInBits())
9504 auto MatchShiftRecurrence = [&](
Value *
V, PHINode *&PNOut,
9506 unsigned &ShiftAmtOut) {
9507 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9523 if (MatchPositiveShift(
LHS,
V, OpC, Amt)) {
9524 PostShiftOpCode = OpC;
9530 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9533 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9539 MatchPositiveShift(BEValue, OpLHS, OpCodeOut, ShiftAmtOut) &&
9546 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9552 if (!MatchShiftRecurrence(
LHS, PN, OpCode, ShiftAmt))
9564 ConstantInt *StableValue =
nullptr;
9569 case Instruction::AShr: {
9576 if (
Known.isNonNegative())
9577 StableValue = ConstantInt::get(Ty, 0);
9578 else if (
Known.isNegative())
9579 StableValue = ConstantInt::get(Ty, -1,
true);
9585 case Instruction::LShr:
9586 case Instruction::Shl:
9596 "Otherwise cannot be an operand to a branch instruction");
9598 if (
Result->isNullValue()) {
9607 if (OpCode == Instruction::LShr || OpCode == Instruction::AShr) {
9609 const SCEV *StartSCEV =
getSCEV(StartValue);
9613 unsigned RangeBTC =
divideCeil(ActiveBits, ShiftAmt);
9614 MaxBTC = std::min(MaxBTC, RangeBTC);
9618 const SCEV *UpperBound =
9636 if (
const Function *
F = CI->getCalledFunction())
9646 if (!L->contains(
I))
return false;
9651 return L->getHeader() ==
I->getParent();
9666 if (
Depth > Opts.scalar_evolution_max_constant_evolving_depth)
9733 if (!
I)
return nullptr;
9747 std::vector<Constant*>
Operands(
I->getNumOperands());
9749 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9758 if (!
C)
return nullptr;
9780 if (IncomingVal != CurrentVal) {
9783 IncomingVal = CurrentVal;
9795ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9798 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9802 if (BEs.
ugt(Opts.scalar_evolution_max_iterations))
9807 DenseMap<Instruction *, Constant *> CurrentIterVals;
9809 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9815 for (PHINode &
PHI : Header->phis()) {
9817 CurrentIterVals[&
PHI] = StartCST;
9819 if (!CurrentIterVals.
count(PN))
9820 return RetVal =
nullptr;
9826 "BEs is <= -scalar-evolution-max-iterations which is an 'unsigned'!");
9829 unsigned IterationNum = 0;
9831 for (; ; ++IterationNum) {
9832 if (IterationNum == NumIterations)
9833 return RetVal = CurrentIterVals[PN];
9837 DenseMap<Instruction *, Constant *> NextIterVals;
9842 NextIterVals[PN] = NextPHI;
9844 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
9850 for (
const auto &
I : CurrentIterVals) {
9852 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
9857 for (
const auto &
I : PHIsToCompute) {
9858 PHINode *
PHI =
I.first;
9861 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9864 if (NextPHI !=
I.second)
9865 StoppedEvolving =
false;
9870 if (StoppedEvolving)
9871 return RetVal = CurrentIterVals[PN];
9873 CurrentIterVals.swap(NextIterVals);
9877const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
9887 DenseMap<Instruction *, Constant *> CurrentIterVals;
9889 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9892 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
9894 for (PHINode &
PHI : Header->phis()) {
9896 CurrentIterVals[&
PHI] = StartCST;
9898 if (!CurrentIterVals.
count(PN))
9904 unsigned MaxIterations =
9905 Opts.scalar_evolution_max_iterations;
9907 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
9914 if (CondVal->getValue() ==
uint64_t(ExitWhen)) {
9915 ++NumBruteForceTripCountsComputed;
9920 DenseMap<Instruction *, Constant *> NextIterVals;
9926 for (
const auto &
I : CurrentIterVals) {
9928 if (!
PHI ||
PHI->getParent() != Header)
continue;
9931 for (PHINode *
PHI : PHIsToCompute) {
9933 if (NextPHI)
continue;
9935 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9938 CurrentIterVals.
swap(NextIterVals);
9949 auto &
Values = ValuesAtScopes[V];
9953 return LS.second ? LS.second :
SCEVUse(V);
9955 Values.emplace_back(L,
nullptr);
9958 SCEVUse C = computeSCEVAtScope(V, L);
9959 for (
auto &LS :
reverse(ValuesAtScopes[V]))
9960 if (LS.first == L) {
9966 ValuesAtScopesUsers[
C.getPointer()].push_back({L, V});
9993 switch (
V->getSCEVType()) {
10026 assert(!
C->getType()->isPointerTy() &&
10027 "Can only have one pointer, and it must be last");
10052const SCEV *ScalarEvolution::getWithOperands(
const SCEV *S,
10053 SmallVectorImpl<SCEVUse> &NewOps) {
10087SCEVUse ScalarEvolution::computeSCEVAtScope(
const SCEV *
V,
const Loop *L) {
10088 switch (
V->getSCEVType()) {
10099 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10110 for (++i; i !=
e; ++i)
10150 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10160 for (++i; i !=
e; ++i) {
10165 return getWithOperands(
V, NewOps);
10180 const Loop *CurrLoop = this->LI[
I->getParent()];
10191 if (BackedgeTakenCount->
isZero()) {
10192 Value *InitValue =
nullptr;
10193 bool MultipleInitValues =
false;
10199 MultipleInitValues =
true;
10204 if (!MultipleInitValues && InitValue)
10213 unsigned InLoopPred =
10224 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10238 SmallVector<Constant *, 4>
Operands;
10240 bool MadeImprovement =
false;
10255 MadeImprovement |= OrigV != OpV;
10260 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10265 if (!MadeImprovement)
10286const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10288 return stripInjectiveFunctions(ZExt->getOperand());
10290 return stripInjectiveFunctions(SExt->getOperand());
10308 assert(
A != 0 &&
"A must be non-zero.");
10324 if (MinTZ < Mult2 && L->getLoopPredecessor())
10326 if (MinTZ < Mult2) {
10349 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10369static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10375 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10376 << *AddRec <<
'\n');
10379 if (!LC || !MC || !
NC) {
10380 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10381 return std::nullopt;
10387 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10395 N =
N.sext(NewWidth);
10396 M = M.sext(NewWidth);
10397 L = L.sext(NewWidth);
10414 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10415 <<
", multiplied by " <<
T <<
'\n');
10424 std::optional<APInt>
Y) {
10426 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10429 return XW.
slt(YW) ? *
X : *
Y;
10432 return std::nullopt;
10433 return X ? *
X : *
Y;
10450 return std::nullopt;
10451 unsigned W =
X->getBitWidth();
10471static std::optional<APInt>
10477 return std::nullopt;
10480 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10481 std::optional<APInt>
X =
10484 return std::nullopt;
10489 return std::nullopt;
10504static std::optional<APInt>
10508 "Starting value of addrec should be 0");
10509 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10510 <<
Range <<
", addrec " << *AddRec <<
'\n');
10514 "Addrec's initial value should be in range");
10520 return std::nullopt;
10530 auto SolveForBoundary =
10531 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10534 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10535 << Bound <<
" (before multiplying by " << M <<
")\n");
10538 std::optional<APInt> SO;
10541 "signed overflow\n");
10545 "unsigned overflow\n");
10546 std::optional<APInt> UO =
10549 auto LeavesRange = [&] (
const APInt &
X) {
10552 if (
Range.contains(V0->getValue()))
10557 if (
Range.contains(
V1->getValue()))
10566 return {std::nullopt,
false};
10571 if (LeavesRange(*Min))
10572 return { Min,
true };
10573 std::optional<APInt> Max = Min == SO ? UO : SO;
10574 if (LeavesRange(*Max))
10575 return { Max,
true };
10578 return {std::nullopt,
true};
10585 auto SL = SolveForBoundary(
Lower);
10586 auto SU = SolveForBoundary(
Upper);
10589 if (!SL.second || !SU.second)
10590 return std::nullopt;
10633ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *
V,
10635 bool ControlsOnlyExit,
10636 bool AllowPredicates) {
10647 if (
C->getValue()->isZero())
return C;
10651 const SCEVAddRecExpr *AddRec =
10654 if (!AddRec && AllowPredicates)
10660 if (!AddRec || AddRec->
getLoop() != L)
10671 return ExitLimit(R, R, R,
false, Predicates);
10729 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10759 const SCEV *
Exact =
10767 const SCEV *SymbolicMax =
10769 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10778 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10786 return ExitLimit(
E, M, S,
false, Predicates);
10789ScalarEvolution::ExitLimit
10790ScalarEvolution::howFarToNonZero(
const SCEV *
V,
const Loop *L) {
10798 if (!
C->getValue()->isZero())
10808std::pair<const BasicBlock *, const BasicBlock *>
10809ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10820 if (
const Loop *L = LI.getLoopFor(BB))
10821 return {
L->getLoopPredecessor(),
L->getHeader()};
10823 return {
nullptr, BB};
10832 if (
A ==
B)
return true;
10847 if (ComputesEqualValues(AI, BI))
10855 const SCEV *Op0, *Op1;
10874 auto TrivialCase = [&](
bool TriviallyTrue) {
10883 const SCEV *NewLHS, *NewRHS;
10907 return TrivialCase(
false);
10908 return TrivialCase(
true);
10927 RAdd->hasNoSignedWrap()) ||
10929 RAdd->hasNoUnsignedWrap())) {
10949 bool BothNUW = LMul->hasNoUnsignedWrap() && RMul->hasNoUnsignedWrap();
10950 bool BothNSW = LMul->hasNoSignedWrap() && RMul->hasNoSignedWrap();
10953 C->getAPInt().isStrictlyPositive()) ||
10977 const APInt &
RA = RC->getAPInt();
10979 bool SimplifiedByConstantRange =
false;
10984 return TrivialCase(
true);
10986 return TrivialCase(
false);
10995 Changed = SimplifiedByConstantRange =
true;
10999 if (!SimplifiedByConstantRange) {
11016 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
11022 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
11028 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
11034 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11054 return TrivialCase(
true);
11056 return TrivialCase(
false);
11161 auto NonRecursive = [OrNegative](
const SCEV *S) {
11163 return C->getAPInt().isPowerOf2() ||
11164 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11170 if (NonRecursive(S))
11180 const SCEV *S, uint64_t M,
11189 APInt C = Cst->getAPInt();
11190 return C.urem(M) == 0;
11196 const SCEV *SmodM =
11217 [&](
SCEVUse Op) { return isKnownMultipleOf(Op, M, Predicates); }))
11224 return isKnownMultipleOf(Op, M, Predicates);
11230 return isKnownMultipleOf(Op, M, Predicates);
11237 for (
auto *
A : *Predicates)
11238 if (
A->implies(
P, *
this))
11251std::pair<const SCEV *, const SCEV *>
11254 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11256 return { Start, Start };
11258 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11267 getUsedLoops(LHS, LoopsUsed);
11268 getUsedLoops(RHS, LoopsUsed);
11270 if (LoopsUsed.
empty())
11275 for (
const auto *L1 : LoopsUsed)
11276 for (
const auto *L2 : LoopsUsed)
11277 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11278 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11279 "Domination relationship is not a linear order");
11309 SplitRHS.second) &&
11319 isKnownPredicateViaSplitting(Pred, LHS, RHS) ||
11320 isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11330 return std::nullopt;
11345 if (KnownWithoutContext)
11346 return KnownWithoutContext;
11353 return std::nullopt;
11359 const Loop *L = LHS->getLoop();
11364std::optional<ScalarEvolution::MonotonicPredicateType>
11367 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11373 auto ResultSwapped =
11376 assert(*ResultSwapped != *Result &&
11377 "monotonicity should flip as we flip the predicate");
11384std::optional<ScalarEvolution::MonotonicPredicateType>
11385ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11399 return std::nullopt;
11403 "Should be greater or less!");
11407 if (!LHS->hasNoUnsignedWrap())
11408 return std::nullopt;
11412 "Relational predicate is either signed or unsigned!");
11413 if (!
LHS->hasNoSignedWrap())
11414 return std::nullopt;
11416 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11424 return std::nullopt;
11427std::optional<ScalarEvolution::LoopInvariantPredicate>
11434 return std::nullopt;
11441 if (!ArLHS || ArLHS->
getLoop() != L)
11442 return std::nullopt;
11447 Pred = Pred.dropSameSign();
11450 return std::nullopt;
11476 return std::nullopt;
11513 return std::nullopt;
11516std::optional<ScalarEvolution::LoopInvariantPredicate>
11521 Pred, LHS, RHS, L, CtxI, MaxIter))
11531 Pred, LHS, RHS, L, CtxI,
Op))
11533 return std::nullopt;
11536std::optional<ScalarEvolution::LoopInvariantPredicate>
11551 return std::nullopt;
11558 if (!AR || AR->
getLoop() != L)
11559 return std::nullopt;
11564 Pred = Pred.dropSameSign();
11568 return std::nullopt;
11574 if (Step != One && Step != MinusOne)
11575 return std::nullopt;
11581 return std::nullopt;
11587 return std::nullopt;
11595 if (Step == MinusOne)
11599 return std::nullopt;
11605bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11611 auto CheckRange = [&](
bool IsSigned) {
11614 return RangeLHS.
icmp(Pred, RangeRHS);
11623 if (CheckRange(
true) || CheckRange(
false))
11632bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate
Pred,
11640 SCEVUse XNonConstOp, XConstOp;
11641 SCEVUse YNonConstOp, YConstOp;
11646 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11647 XConstOp =
nullptr;
11654 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11655 YConstOp =
nullptr;
11660 if (YNonConstOp != XNonConstOp)
11733bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate
Pred,
11754bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate
Pred,
11755 const SCEV *
LHS,
const SCEV *
RHS) {
11760 return any_of(*BB, [&](
const Instruction &
I) {
11761 using namespace llvm::PatternMatch;
11766 isImpliedCond(
Pred,
LHS,
RHS, Condition,
false);
11780 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11783 if (Opts.scev_verify_ir)
11785 "This cannot be done on broken IR!");
11788 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11797 if (LoopContinuePredicate &&
11798 isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->
getCondition(),
11799 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11804 if (WalkingBEDominatingConds)
11810 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11811 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11818 const SCEV *LoopCounter =
11826 for (
auto &AssumeVH : AC.assumptions()) {
11833 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11837 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11840 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11841 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11842 assert(DTN &&
"should reach the loop header before reaching the root!");
11845 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11863 if (isImpliedCond(Pred, LHS, RHS, ContBr->
getCondition(),
11876 if (!DT.isReachableFromEntry(BB))
11878 if (Opts.scev_verify_ir)
11880 "This cannot be done on broken IR!");
11888 const bool ProvingStrictComparison =
11894 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
11896 return isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI);
11902 const Loop *ContainingLoop = LI.getLoopFor(BB);
11904 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
11908 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
11909 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
11912 if (!BlockEntryPredicate)
11921 for (
auto &AssumeVH : AC.assumptions()) {
11925 if (!DT.dominates(CI, BB))
11928 if (ProveViaCond(CI->getArgOperand(0),
false))
11934 F.getParent(), Intrinsic::experimental_guard);
11936 for (
const auto *GU : GuardDecl->users())
11938 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
11939 if (ProveViaCond(Guard->getArgOperand(0),
false))
11944 if (!ProvingStrictComparison)
11947 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS) ||
11948 any_of(Conds, [&](
const auto &
C) {
11949 return isImpliedCond(
P, LHS, RHS,
C.first,
C.second, CtxI);
11965 "LHS is not available at Loop Entry");
11967 "RHS is not available at Loop Entry");
11969 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11980 if (FoundCondValue ==
11984 if (!PendingLoopPredicates.insert(FoundCondValue).second)
11988 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
11991 const Value *Op0, *Op1;
11998 return isImpliedCond(
Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
11999 isImpliedCond(
Pred,
LHS,
RHS, Op1, Inverse, CtxI);
12003 if (!ICI)
return false;
12007 CmpPredicate FoundPred;
12016 return isImpliedCond(
Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
12019bool ScalarEvolution::isImpliedCond(CmpPredicate
Pred,
const SCEV *
LHS,
12020 const SCEV *
RHS, CmpPredicate FoundPred,
12021 const SCEV *FoundLHS,
const SCEV *FoundRHS,
12022 const Instruction *CtxI) {
12032 auto *WideType = FoundLHS->
getType();
12044 TruncFoundLHS, TruncFoundRHS, CtxI))
12070 return isImpliedCondBalancedTypes(
Pred,
LHS,
RHS, FoundPred, FoundLHS,
12074bool ScalarEvolution::isImpliedCondBalancedTypes(
12079 "Types should be balanced!");
12086 if (FoundLHS == FoundRHS)
12090 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12102 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12117 LHS, FoundLHS, FoundRHS, CtxI);
12119 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12131 if (IsSignFlippedPredicate(
Pred, FoundPred) &&
12132 isImpliedCondViaSignFlippedPred(
Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12135 if (IsSignFlippedPredicate(SwappedPred, FoundPred) &&
12136 isImpliedCondViaSignFlippedPred(SwappedPred,
RHS,
LHS, FoundLHS, FoundRHS,
12144 const SCEVConstant *
C =
nullptr;
12145 const SCEV *
V =
nullptr;
12163 if (Min ==
C->getAPInt()) {
12168 APInt SharperMin = Min + 1;
12171 case ICmpInst::ICMP_SGE:
12172 case ICmpInst::ICMP_UGE:
12175 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12180 case ICmpInst::ICMP_SGT:
12181 case ICmpInst::ICMP_UGT:
12191 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12196 case ICmpInst::ICMP_SLE:
12197 case ICmpInst::ICMP_ULE:
12198 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12199 LHS, V, getConstant(SharperMin), CtxI))
12203 case ICmpInst::ICMP_SLT:
12204 case ICmpInst::ICMP_ULT:
12205 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12206 LHS, V, getConstant(Min), CtxI))
12220 if (isImpliedCondOperands(
Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12224 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12227 if (isImpliedCondOperandsViaRanges(
Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12234bool ScalarEvolution::isImpliedCondViaSignFlippedPred(
12235 CmpPredicate
Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12236 const SCEV *FoundRHS,
const Instruction *CtxI) {
12241 return isImpliedCondOperands(
Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12264 CmpPredicate BoundPred =
12266 if (isKnownViaNonRecursiveReasoning(BoundPred, FoundRHS, SignedMin)) {
12269 if (isImpliedCondOperands(
Pred,
LHS,
RHS, Bound, FoundLHS, CtxI))
12277 return isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS);
12283 return isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS);
12297std::optional<APInt>
12304 APInt DiffMul(BW, 1);
12307 for (
unsigned I = 0;
I < 8; ++
I) {
12316 if (LAR->getLoop() != MAR->getLoop())
12317 return std::nullopt;
12321 if (!LAR->isAffine() || !MAR->isAffine())
12322 return std::nullopt;
12324 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12325 return std::nullopt;
12327 Less = LAR->getStart();
12328 More = MAR->getStart();
12333 auto MatchConstMul =
12334 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12339 return std::nullopt;
12341 if (
auto MatchedMore = MatchConstMul(More)) {
12342 if (
auto MatchedLess = MatchConstMul(
Less)) {
12343 if (MatchedMore->second == MatchedLess->second) {
12344 More = MatchedMore->first;
12345 Less = MatchedLess->first;
12346 DiffMul *= MatchedMore->second;
12357 Diff +=
C->getAPInt() * DiffMul;
12360 Diff -=
C->getAPInt() * DiffMul;
12363 Multiplicity[S] +=
Mul;
12365 auto Decompose = [&](
const SCEV *S,
int Mul) {
12372 Decompose(More, 1);
12373 Decompose(
Less, -1);
12377 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12378 for (
const auto &[S,
Mul] : Multiplicity) {
12383 return std::nullopt;
12385 }
else if (
Mul == -1) {
12387 return std::nullopt;
12390 return std::nullopt;
12394 if (NewMore == More || NewLess ==
Less)
12395 return std::nullopt;
12401 if (!More && !
Less)
12405 if (!More || !
Less)
12406 return std::nullopt;
12410 return std::nullopt;
12413bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12435 const auto *Latch = L->getLoopLatch();
12438 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12447 const auto *Latch = L->getLoopLatch();
12450 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12460bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate
Pred,
12463 const SCEV *FoundLHS,
12464 const SCEV *FoundRHS) {
12473 if (!AddRecFoundLHS)
12480 const Loop *
L = AddRecFoundLHS->getLoop();
12481 if (L != AddRecLHS->getLoop())
12520 if (!RDiff || *LDiff != *RDiff)
12523 if (LDiff->isMinValue())
12526 APInt FoundRHSLimit;
12529 FoundRHSLimit = -(*RDiff);
12541bool ScalarEvolution::isImpliedViaMerge(CmpPredicate
Pred,
const SCEV *
LHS,
12542 const SCEV *
RHS,
const SCEV *FoundLHS,
12543 const SCEV *FoundRHS,
unsigned Depth) {
12544 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12548 bool Erased = PendingMerges.erase(LPhi);
12549 assert(Erased &&
"Failed to erase LPhi!");
12553 bool Erased = PendingMerges.erase(RPhi);
12554 assert(Erased &&
"Failed to erase RPhi!");
12562 if (!PendingMerges.insert(Phi).second)
12576 if (!PendingMerges.insert(Phi).second)
12582 if (!LPhi && !RPhi)
12593 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12597 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12598 return isKnownViaNonRecursiveReasoning(
Pred,
S1, S2) ||
12599 isImpliedCondOperandsViaRanges(
Pred,
S1, S2,
Pred, FoundLHS, FoundRHS) ||
12600 isImpliedViaOperations(
Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12603 if (RPhi && RPhi->getParent() == LBB) {
12610 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12611 if (!ProvedEasily(L, R))
12622 auto *RLoop = RAR->
getLoop();
12623 auto *Predecessor = RLoop->getLoopPredecessor();
12624 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12626 if (!ProvedEasily(L1, RAR->
getStart()))
12628 auto *Latch = RLoop->getLoopLatch();
12629 assert(Latch &&
"Loop with AddRec with no latch?");
12650 if (
auto *
Loop = LI.getLoopFor(LBB))
12653 if (!ProvedEasily(L,
RHS))
12660bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate
Pred,
12663 const SCEV *FoundLHS,
12664 const SCEV *FoundRHS) {
12667 if (
RHS == FoundRHS) {
12672 if (
LHS != FoundLHS)
12679 Value *Shiftee, *ShiftValue;
12681 using namespace PatternMatch;
12682 if (
match(SUFoundRHS->getValue(),
12684 auto *ShifteeS =
getSCEV(Shiftee);
12702bool ScalarEvolution::isImpliedCondOperandsViaMatchingDiff(
12703 CmpPredicate
Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12704 const SCEV *FoundRHS) {
12736 const SCEV *FoundDiff =
getMinusSCEV(FoundLHS, FoundRHS);
12744 return Diff == FoundDiff;
12747bool ScalarEvolution::isImpliedCondOperands(CmpPredicate
Pred,
const SCEV *
LHS,
12749 const SCEV *FoundLHS,
12750 const SCEV *FoundRHS,
12751 const Instruction *CtxI) {
12752 return isImpliedCondOperandsViaRanges(
Pred,
LHS,
RHS,
Pred, FoundLHS,
12754 isImpliedCondOperandsViaNoOverflow(
Pred,
LHS,
RHS, FoundLHS,
12756 isImpliedCondOperandsViaShift(
Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12757 isImpliedCondOperandsViaAddRecStart(
Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12759 isImpliedCondOperandsViaMatchingDiff(
Pred,
LHS,
RHS, FoundLHS,
12761 isImpliedCondOperandsHelper(
Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12765template <
typename MinMaxExprType>
12767 const SCEV *Candidate) {
12772 return is_contained(MinMaxExpr->operands(), Candidate);
12785 const SCEV *LStart, *RStart, *Step;
12882bool ScalarEvolution::isImpliedViaOperations(CmpPredicate
Pred,
const SCEV *
LHS,
12884 const SCEV *FoundLHS,
12885 const SCEV *FoundRHS,
12889 "LHS and RHS have different sizes?");
12892 "FoundLHS and FoundRHS have different sizes?");
12894 if (
Depth > Opts.scalar_evolution_max_scev_operations_implication_depth)
12926 auto GetOpFromSExt = [&](
const SCEV *S) ->
const SCEV * {
12928 return Ext->getOperand();
12935 auto *OrigLHS =
LHS;
12936 auto *OrigFoundLHS = FoundLHS;
12937 LHS = GetOpFromSExt(
LHS);
12938 FoundLHS = GetOpFromSExt(FoundLHS);
12941 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
12944 FoundRHS,
Depth + 1);
12961 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
12962 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
12967 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
12973 using namespace llvm::PatternMatch;
12992 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
13000 auto *DTy = Denominator->getType();
13001 auto *FRHSTy = FoundRHS->
getType();
13002 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
13021 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
13032 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
13034 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
13042 if (isImpliedViaMerge(
Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
13075bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate
Pred,
13079 isKnownPredicateViaConstantRanges(
Pred,
LHS,
RHS) ||
13083 isKnownPredicateViaNoOverflow(
Pred,
LHS,
RHS);
13086bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate
Pred,
13089 const SCEV *FoundLHS,
13090 const SCEV *FoundRHS) {
13096 if (isKnownViaNonRecursiveReasoning(NonStrictPred,
LHS, FoundLHS) &&
13097 isKnownViaNonRecursiveReasoning(
13103 return isImpliedViaOperations(
Pred,
LHS,
RHS, FoundLHS, FoundRHS);
13106bool ScalarEvolution::isImpliedCondOperandsViaRanges(
13107 CmpPredicate
Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
13108 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13122 ConstantRange FoundLHSRange =
13126 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13133 return LHSRange.
icmp(
Pred, ConstRHS);
13136bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13137 bool IsSigned,
bool Invert) {
13144 APInt MaxRHS = getRangeMax(
RHS,
true, Invert);
13149 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13152 APInt MaxRHS = getRangeMax(
RHS,
false, Invert);
13157 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13170ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
const SCEV *Stride,
13172 bool IsSigned,
bool Invert) {
13187 APInt MinStart = getRangeMin(Start, IsSigned, Invert);
13200 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13206 APInt MaxEnd = getRangeMax(
End, IsSigned, Invert);
13212 :
APIntOps::umax(MaxEnd, MinStart);
13214 APInt Delta = MaxEnd - MinStart;
13218 const SCEV *DeltaExpr =
13226ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13227 const Loop *L,
bool IsSigned,
bool Invert,
13228 bool ControlsOnlyExit,
bool AllowPredicates) {
13238 bool PredicatedIV =
false;
13240 if (!
IV && !Invert) {
13244 auto canProveNUW = [&]() {
13247 if (!ControlsOnlyExit)
13268 Limit = Limit.
zext(OuterBitWidth);
13280 Type *Ty = ZExt->getType();
13290 if (!
IV && AllowPredicates) {
13295 PredicatedIV =
true;
13299 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13313 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13320 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13323 const SCEV *GuardedStride = Stride;
13327 bool IVMayOverflow =
true;
13331 if (!PositiveStride) {
13334 GuardedStride = LoopGuardedStride;
13335 PositiveStride =
true;
13342 if (!PositiveStride) {
13391 const SCEVPredicate *
P =
13412 auto wouldZeroStrideBeUB = [&]() {
13424 if (!wouldZeroStrideBeUB()) {
13431 IVMayOverflow = canIVOverflowOnLT(
RHS, GuardedStride, IsSigned, Invert) &&
13433 GuardedStride, IsSigned, Invert);
13434 if (IVMayOverflow && !NoWrap)
13447 const SCEV *
Start =
IV->getStart();
13453 const SCEV *OrigStart =
Start;
13454 const SCEV *OrigRHS =
RHS;
13455 if (
Start->getType()->isPointerTy()) {
13469 assert(!Invert &&
"RHS must be loop-invariant for Invert");
13471 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13472 any(RHSAddRec->getNoWrapFlags())) {
13485 const SCEV *RHSStart = RHSAddRec->getStart();
13486 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13498 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13507 BECountIfBackedgeTaken =
13534 bool AddingStrideMinusOneMayOverflow = IVMayOverflow && [&] {
13581 if (!Invert && (Start == Stride || Start ==
getMinusSCEV(Stride, One))) {
13598 auto StepBack = [&](
const SCEV *
V,
const SCEV *
Offset) ->
const SCEV * {
13603 auto Distance = [&](
const SCEV *From,
const SCEV *To) {
13607 const SCEV *OrigPrevStart = StepBack(OrigStart, Stride);
13614 if ((!AddingStrideMinusOneMayOverflow ||
13646 const SCEV *Numerator =
13652 auto canProveRHSIsAtOrBeyondStart = [&]() {
13657 auto SwapIfInverted = [&](
const SCEV *
A,
const SCEV *
B) {
13658 return Invert ? std::pair(
B,
A) : std::pair(
A,
B);
13667 auto [GELHS, GERHS] = SwapIfInverted(OrigRHS, OrigStart);
13672 if ((GuardedRHS != GELHS || GuardedStart != GERHS) &&
13686 auto [GTLHS, GTRHS] = SwapIfInverted(OrigRHS, StepBack(OrigStart, One));
13692 if (canProveRHSIsAtOrBeyondStart()) {
13715 const SCEV *Delta = Distance(Start,
End);
13716 if (!AddingStrideMinusOneMayOverflow) {
13728 const SCEV *ConstantMaxBECount;
13729 bool MaxOrZero =
false;
13731 ConstantMaxBECount = BECount;
13733 ConstantMaxBECount = computeMaxBECountForLT(
13740 const APInt *IfTaken, *RangeMax;
13743 IfTaken->
ugt(*RangeMax)) {
13744 ConstantMaxBECount =
getZero(BECountIfBackedgeTaken->getType());
13746 ConstantMaxBECount = BECountIfBackedgeTaken;
13756 const SCEV *SymbolicMaxBECount =
13758 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13764 if (
Range.isFullSet())
13769 if (!SC->getValue()->isZero()) {
13775 return ShiftedAddRec->getNumIterationsInRange(
13776 Range.subtract(SC->getAPInt()), SE);
13820 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
13821 "Linear scev computation is off in a bad way!");
13852 assert(!
Last->isZero() &&
"Recurrency with zero step?");
13885 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13887 SE->ConstantEvolutionLoopExitValue.erase(PN);
13888 SE->eraseValueFromMap(getValPtr());
13892void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *
V) {
13893 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13903 : CallbackVH(
V), SE(se) {}
13914 ValuesAtScopes(64), LoopDispositions(64), BlockDispositions(64) {
13926 F.getParent(), Intrinsic::experimental_guard);
13927 HasGuards = GuardDecl && !GuardDecl->use_empty();
13931 : Opts(Arg.Opts), F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards),
13932 TLI(Arg.TLI), AC(Arg.AC), DT(Arg.DT), LI(Arg.LI),
13933 CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
13934 ValueExprMap(
std::
move(Arg.ValueExprMap)),
13935 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
13936 PendingMerges(
std::
move(Arg.PendingMerges)),
13937 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
13938 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
13939 PredicatedBackedgeTakenCounts(
13940 std::
move(Arg.PredicatedBackedgeTakenCounts)),
13941 BECountUsers(
std::
move(Arg.BECountUsers)),
13942 ConstantEvolutionLoopExitValue(
13943 std::
move(Arg.ConstantEvolutionLoopExitValue)),
13944 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
13945 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
13946 LoopDispositions(
std::
move(Arg.LoopDispositions)),
13947 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
13948 BlockDispositions(
std::
move(Arg.BlockDispositions)),
13949 SCEVUsers(
std::
move(Arg.SCEVUsers)),
13950 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
13951 SignedRanges(
std::
move(Arg.SignedRanges)),
13952 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
13953 UniquePreds(
std::
move(Arg.UniquePreds)),
13954 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
13955 ConstantSCEVs(
std::
move(Arg.ConstantSCEVs)),
13956 LoopUsers(
std::
move(Arg.LoopUsers)),
13957 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
13958 FirstUnknown(Arg.FirstUnknown),
13959 NextUnknownOrderID(Arg.NextUnknownOrderID) {
13960 Arg.FirstUnknown =
nullptr;
13969 Tmp->~SCEVUnknown();
13971 FirstUnknown =
nullptr;
13973 ExprValueMap.clear();
13974 ValueExprMap.clear();
13976 BackedgeTakenCounts.clear();
13977 PredicatedBackedgeTakenCounts.clear();
13979 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
13980 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
13981 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
13982 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
14004 L->getHeader()->printAsOperand(OS,
false);
14008 L->getExitingBlocks(ExitingBlocks);
14009 if (ExitingBlocks.
size() != 1)
14010 OS <<
"<multiple exits> ";
14014 OS <<
"backedge-taken count is ";
14017 OS <<
"Unpredictable backedge-taken count.";
14020 if (ExitingBlocks.
size() > 1)
14021 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14022 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
14030 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
14033 OS <<
"\n Predicates:\n";
14034 for (
const auto *
P : Predicates)
14042 L->getHeader()->printAsOperand(OS,
false);
14047 OS <<
"constant max backedge-taken count is ";
14050 OS <<
", actual taken count either this or zero.";
14052 OS <<
"Unpredictable constant max backedge-taken count. ";
14057 L->getHeader()->printAsOperand(OS,
false);
14062 OS <<
"symbolic max backedge-taken count is ";
14065 OS <<
", actual taken count either this or zero.";
14067 OS <<
"Unpredictable symbolic max backedge-taken count. ";
14071 if (ExitingBlocks.
size() > 1)
14072 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14073 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
14083 OS <<
"\n predicated symbolic max exit count for "
14084 << ExitingBlock->
getName() <<
": ";
14086 OS <<
"\n Predicates:\n";
14087 for (
const auto *
P : Predicates)
14098 L->getHeader()->printAsOperand(OS,
false);
14101 OS <<
"Predicated backedge-taken count is ";
14104 OS <<
"Unpredictable predicated backedge-taken count.";
14106 OS <<
" Predicates:\n";
14107 for (
const auto *
P : Preds)
14112 auto *PredConstantMax =
14114 if (PredConstantMax != ConstantBTC) {
14116 L->getHeader()->printAsOperand(OS,
false);
14119 OS <<
"Predicated constant max backedge-taken count is ";
14122 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14124 OS <<
" Predicates:\n";
14125 for (
const auto *
P : Preds)
14130 auto *PredSymbolicMax =
14132 if (SymbolicBTC != PredSymbolicMax) {
14134 L->getHeader()->printAsOperand(OS,
false);
14137 OS <<
"Predicated symbolic max backedge-taken count is ";
14140 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14142 OS <<
" Predicates:\n";
14143 for (
const auto *
P : Preds)
14149 L->getHeader()->printAsOperand(OS,
false);
14176 OS <<
"Computable";
14186 OS <<
"DoesNotDominate";
14192 OS <<
"ProperlyDominates";
14208 if (Opts.scalar_evolution_classify_expressions) {
14209 OS <<
"Classifying expressions for: ";
14210 F.printAsOperand(OS,
false);
14225 const Loop *L = LI.getLoopFor(
I.getParent());
14240 OS <<
"\t\t" "Exits: ";
14243 OS <<
"<<Unknown>>";
14249 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14251 Iter->getHeader()->printAsOperand(OS,
false);
14259 InnerL->getHeader()->printAsOperand(OS,
false);
14270 OS <<
"Determining loop execution counts for: ";
14271 F.printAsOperand(OS,
false);
14282 auto &
Values = LoopDispositions[S];
14283 for (
auto &V :
Values) {
14284 if (V.getPointer() == L)
14289 auto &Values2 = LoopDispositions[S];
14291 if (V.getPointer() == L) {
14300ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14318 if (L->contains(AR->
getLoop()) &&
14320 [&](
const SCEV *
Op) { return isLoopUniform(Op, L); }))
14325 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14326 " dominate the contained loop's header?");
14353 bool HasVarying =
false;
14354 bool HasUniform =
false;
14399 auto &
Values = BlockDispositions[S];
14400 for (
auto &V :
Values) {
14401 if (V.getPointer() == BB)
14406 auto &Values2 = BlockDispositions[S];
14408 if (V.getPointer() == BB) {
14417ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14446 bool Proper =
true;
14457 if (Instruction *
I =
14459 if (
I->getParent() == BB)
14461 if (DT.properlyDominates(
I->getParent(), BB))
14480void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14483 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14484 auto It = BECounts.find(L);
14485 if (It != BECounts.end()) {
14486 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14487 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14489 auto UserIt = BECountUsers.find(S);
14490 assert(UserIt != BECountUsers.end());
14495 BECounts.erase(It);
14503 while (!Worklist.
empty()) {
14505 auto Users = SCEVUsers.find(Curr);
14506 if (
Users != SCEVUsers.end())
14507 for (
const auto *User :
Users->second)
14508 if (ToForget.
insert(User).second)
14512 for (
const auto *S : ToForget)
14513 forgetMemoizedResultsImpl(S);
14515 PredicatedSCEVRewrites.remove_if(
14516 [&](
const auto &Entry) {
return ToForget.count(
Entry.first.first); });
14519void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14520 LoopDispositions.erase(S);
14521 BlockDispositions.erase(S);
14522 UnsignedRanges.erase(S);
14523 SignedRanges.erase(S);
14524 HasRecMap.erase(S);
14525 ConstantMultipleCache.erase(S);
14528 UnsignedWrapViaInductionTried.erase(AR);
14529 SignedWrapViaInductionTried.erase(AR);
14532 auto ExprIt = ExprValueMap.find(S);
14533 if (ExprIt != ExprValueMap.end()) {
14534 for (
Value *
V : ExprIt->second) {
14535 auto ValueIt = ValueExprMap.find_as(
V);
14536 if (ValueIt != ValueExprMap.end())
14537 ValueExprMap.erase(ValueIt);
14539 ExprValueMap.erase(ExprIt);
14542 auto ScopeIt = ValuesAtScopes.find(S);
14543 if (ScopeIt != ValuesAtScopes.end()) {
14544 for (
const auto &Pair : ScopeIt->second)
14546 llvm::erase(ValuesAtScopesUsers[Pair.second.getPointer()],
14547 std::make_pair(Pair.first, S));
14548 ValuesAtScopes.erase(ScopeIt);
14551 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14552 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14553 for (
const auto &Pair : ScopeUserIt->second)
14556 llvm::erase_if(ValuesAtScopes[Pair.second], [&](
const auto &LS) {
14557 return LS.first == Pair.first && LS.second.getPointer() == S;
14559 ValuesAtScopesUsers.erase(ScopeUserIt);
14562 auto BEUsersIt = BECountUsers.find(S);
14563 if (BEUsersIt != BECountUsers.end()) {
14565 auto Copy = BEUsersIt->second;
14566 for (
const auto &Pair : Copy)
14567 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14568 BECountUsers.erase(BEUsersIt);
14571 auto FoldUser = FoldCacheUser.find(S);
14572 if (FoldUser != FoldCacheUser.end())
14573 for (
auto &KV : FoldUser->second)
14574 FoldCache.erase(KV);
14575 FoldCacheUser.erase(S);
14579ScalarEvolution::getUsedLoops(
const SCEV *S,
14581 struct FindUsedLoops {
14582 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14583 : LoopsUsed(LoopsUsed) {}
14584 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14585 bool follow(
const SCEV *S) {
14591 bool isDone()
const {
return false; }
14594 FindUsedLoops
F(LoopsUsed);
14595 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14598void ScalarEvolution::getReachableBlocks(
14601 Worklist.
push_back(&F.getEntryBlock());
14602 while (!Worklist.
empty()) {
14604 if (!Reachable.
insert(BB).second)
14612 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14619 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14623 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14658 SCEVMapper SCM(SE2);
14660 SE2.getReachableBlocks(ReachableBlocks, F);
14662 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14680 while (!LoopStack.
empty()) {
14686 if (!ReachableBlocks.
contains(L->getHeader()))
14691 auto It = BackedgeTakenCounts.find(L);
14692 if (It == BackedgeTakenCounts.end())
14696 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14716 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14717 if (Delta && !Delta->
isZero()) {
14718 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14719 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14720 dbgs() <<
"New: " << *NewBECount <<
"\n";
14721 dbgs() <<
"Delta: " << *Delta <<
"\n";
14729 while (!Worklist.
empty()) {
14731 if (ValidLoops.
insert(L).second)
14732 Worklist.
append(L->begin(), L->end());
14734 for (
const auto &KV : ValueExprMap) {
14739 "AddRec references invalid loop");
14744 auto It = ExprValueMap.find(KV.second);
14745 if (It == ExprValueMap.end() || !
is_contained(It->second, KV.first)) {
14746 dbgs() <<
"Value " << *KV.first
14747 <<
" is in ValueExprMap but not in ExprValueMap\n";
14752 if (!ReachableBlocks.
contains(
I->getParent()))
14754 const SCEV *OldSCEV = SCM.visit(KV.second);
14756 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14757 if (Delta && !Delta->
isZero()) {
14758 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14759 <<
"Old: " << *OldSCEV <<
"\n"
14760 <<
"New: " << *NewSCEV <<
"\n"
14761 <<
"Delta: " << *Delta <<
"\n";
14767 for (
const auto &KV : ExprValueMap) {
14768 for (
Value *V : KV.second) {
14769 const SCEV *S = ValueExprMap.lookup(V);
14771 dbgs() <<
"Value " << *V
14772 <<
" is in ExprValueMap but not in ValueExprMap\n";
14775 if (S != KV.first) {
14776 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14777 << *KV.first <<
"\n";
14784 for (
const auto &S : UniqueSCEVs) {
14789 auto It = SCEVUsers.find(
Op);
14790 if (It != SCEVUsers.end() && It->second.count(&S))
14792 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14793 <<
" is not being tracked!\n";
14799 for (
const auto &ValueAndVec : ValuesAtScopes) {
14801 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14802 const Loop *L = LoopAndValueAtScope.first;
14803 SCEVUse ValueAtScope = LoopAndValueAtScope.second;
14805 auto It = ValuesAtScopesUsers.find(ValueAtScope.
getPointer());
14806 if (It != ValuesAtScopesUsers.end() &&
14809 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14810 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14816 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14817 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14818 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14819 const Loop *L = LoopAndValue.first;
14820 const SCEV *
Value = LoopAndValue.second;
14822 auto It = ValuesAtScopes.find(
Value);
14825 if (It != ValuesAtScopes.end() &&
any_of(It->second, [&](
const auto &LS) {
14826 return LS.first == L && LS.second.getPointer() == ValueAtScope;
14829 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14830 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14836 auto VerifyBECountUsers = [&](
bool Predicated) {
14838 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14839 for (
const auto &LoopAndBEInfo : BECounts) {
14840 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
14841 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14843 auto UserIt = BECountUsers.find(S);
14844 if (UserIt != BECountUsers.end() &&
14845 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
14847 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
14848 <<
" missing from BECountUsers\n";
14855 VerifyBECountUsers(
false);
14856 VerifyBECountUsers(
true);
14859 for (
auto &[S,
Values] : LoopDispositions) {
14860 for (
auto [
Loop, CachedDisposition] :
Values) {
14862 if (CachedDisposition != RecomputedDisposition) {
14863 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
14864 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
14865 << RecomputedDisposition <<
"\n";
14872 for (
auto &[S,
Values] : BlockDispositions) {
14873 for (
auto [BB, CachedDisposition] :
Values) {
14875 if (CachedDisposition != RecomputedDisposition) {
14876 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
14877 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
14878 <<
", actual " << RecomputedDisposition <<
"\n";
14885 for (
auto [
FoldID, Expr] : FoldCache) {
14886 auto I = FoldCacheUser.find(Expr);
14887 if (
I == FoldCacheUser.end()) {
14888 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
14893 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
14897 for (
auto [Expr, IDs] : FoldCacheUser) {
14898 for (
auto &
FoldID : IDs) {
14901 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
14906 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
14907 <<
" != " << *Expr <<
"!\n";
14918 for (
auto [S, Multiple] : ConstantMultipleCache) {
14920 if ((Multiple != 0 && RecomputedMultiple != 0 &&
14921 Multiple.
urem(RecomputedMultiple) != 0 &&
14922 RecomputedMultiple.
urem(Multiple) != 0)) {
14923 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
14924 << *S <<
" : Computed " << RecomputedMultiple
14925 <<
" but cache contains " << Multiple <<
"!\n";
14933 FunctionAnalysisManager::Invalidator &Inv) {
14965 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
14966 <<
F.getName() <<
"':\n";
14972 "Scalar Evolution Analysis",
false,
true)
15021 const SCEV *LHS,
const SCEV *RHS) {
15023 assert(LHS->getType() == RHS->getType() &&
15024 "Type mismatch between LHS and RHS");
15027 ID.AddInteger(Pred);
15028 ID.AddPointer(LHS);
15029 ID.AddPointer(RHS);
15031 if (
const auto *S = UniquePreds.lookup(ID, Token))
15035 UniquePreds.insert(Eq, Token);
15046 ID.AddInteger(AddedFlags);
15048 if (
const auto *S = UniquePreds.lookup(ID, Token))
15050 auto *OF =
new (SCEVAllocator)
15052 UniquePreds.insert(OF, Token);
15072 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
15073 return Rewriter.visit(S);
15079 for (
const auto *
Pred : U->getPredicates())
15081 if (IPred->getLHS() == Expr &&
15083 return IPred->getRHS();
15085 if (IPred->getLHS() == Expr &&
15086 IPred->getPredicate() == ICmpInst::ICMP_EQ)
15087 return IPred->getRHS();
15090 return convertToAddRecWithPreds(Expr);
15093 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15109 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15126 explicit SCEVPredicateRewriter(
15127 const Loop *L, ScalarEvolution &SE,
15128 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15129 const SCEVPredicate *
Pred)
15130 : SCEVRewriteVisitor(SE), NewPreds(NewPreds),
Pred(
Pred),
L(
L) {}
15132 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15141 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15144 return addOverflowAssumption(
A);
15153 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15157 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15159 if (!PredicatedRewrite)
15161 for (
const auto *
P : PredicatedRewrite->second){
15164 if (L != WP->getExpr()->getLoop())
15167 if (!addOverflowAssumption(
P))
15170 return PredicatedRewrite->first;
15173 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15174 const SCEVPredicate *
Pred;
15183 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15190 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15210 if (!Step->
isOne())
15235 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15236 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15246 if (
Op->LHS != LHS ||
Op->RHS != RHS)
15256 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15258 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15283 const SCEV *Start = AR->getStart();
15284 const SCEV *OpStart =
Op->AR->getStart();
15289 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15298 const SCEV *Step = AR->getStepRecurrence(SE);
15299 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15320 SCEVFlags ScevFlags = AR->getNoWrapFlags();
15342 for (
const auto *
P : Preds)
15355 return this->implies(I, SE);
15367 const Loop *L = NWrap->getExpr()->getLoop();
15374 return RewrittenAR &&
15380 for (
const auto *Pred : Preds)
15381 Pred->print(OS,
Depth);
15386 for (
const auto *Pred : Set->Preds)
15394 bool CheckImplies = Preds.
size() < 16;
15397 if (CheckImplies &&
implies(
N, SE))
15403 for (
auto *
P : Preds) {
15404 if (CheckImplies &&
N->implies(
P, SE))
15408 Preds = std::move(PrunedPreds);
15409 Preds.push_back(
N);
15416 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15425 SCEVUsers[
Op].insert(
User);
15429 const SCEV *Expr = SE.getSCEV(V);
15434 RewriteEntry &Entry = RewriteMap[Expr];
15437 if (Entry.second && Generation == Entry.first)
15438 return Entry.second;
15443 Expr = Entry.second;
15445 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15446 Entry = {Generation, NewSCEV};
15452 if (!BackedgeCount) {
15454 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15455 for (
const auto *
P : Preds)
15458 return BackedgeCount;
15462 if (!SymbolicMaxBackedgeCount) {
15464 SymbolicMaxBackedgeCount =
15465 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15466 for (
const auto *
P : Preds)
15469 return SymbolicMaxBackedgeCount;
15473 if (!SmallConstantMaxTripCount) {
15475 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15476 for (
const auto *
P : Preds)
15479 return *SmallConstantMaxTripCount;
15483 if (Preds->implies(&Pred, SE))
15486 Preds = std::make_unique<SCEVUnionPredicate>(Preds->getUnionWith(&Pred, SE));
15487 updateGeneration();
15500void PredicatedScalarEvolution::updateGeneration() {
15502 if (++Generation == 0) {
15503 for (
auto &
II : RewriteMap) {
15504 const SCEV *Rewritten =
II.second.second;
15514 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15520 ExtraPreds->
append(NewPreds);
15526 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15532 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15534 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {}
15538 for (
auto *BB : L.getBlocks())
15539 for (
auto &
I : *BB) {
15540 if (!SE.isSCEVable(
I.getType()))
15543 auto *Expr = SE.getSCEV(&
I);
15544 auto II = RewriteMap.find(Expr);
15546 if (
II == RewriteMap.end())
15550 if (
II->second.second == Expr)
15555 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15559void ScalarEvolution::LoopGuards::collectPending() {
15560 const Loop *L = PendingLoop;
15563 PendingLoop =
nullptr;
15568 collectFromBlock(SE, *
this, L->getHeader(), Pred,
VisitedBlocks);
15571void ScalarEvolution::LoopGuards::collectFromPHI(
15579 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15580 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15594 auto &RewriteMap =
G->second.RewriteMap;
15595 if (RewriteMap.empty())
15597 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15598 if (S == RewriteMap.end())
15604 return {
C0, SM->getSCEVType()};
15607 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15608 MinMaxPattern
P2) -> MinMaxPattern {
15610 auto [C2, T2] =
P2;
15611 if (!
C1 || !C2 ||
T1 != T2)
15615 return {
C1->getAPInt().ult(C2->getAPInt()) ?
C1 : C2,
T1};
15617 return {
C1->getAPInt().slt(C2->getAPInt()) ?
C1 : C2,
T1};
15619 return {
C1->getAPInt().ugt(C2->getAPInt()) ?
C1 : C2,
T1};
15621 return {
C1->getAPInt().sgt(C2->getAPInt()) ?
C1 : C2,
T1};
15626 auto P = GetMinMaxConst(0);
15627 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15630 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15633 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15636 Guards.RewriteMap.insert({
LHS,
RHS});
15644 const APInt &DivisorVal,
15646 const APInt *ExprVal;
15659 const APInt &DivisorVal,
15661 const APInt *ExprVal;
15669 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15683 const SCEV *URemRHS =
nullptr;
15687 const SCEV *Multiple =
15689 DivInfo[URemLHS] = Multiple;
15691 Multiples[URemLHS] =
C->getAPInt();
15711 auto IsMinMaxSCEVWithNonNegativeConstant =
15715 if (
MinMax->getNumOperands() != 2)
15718 if (
C->getAPInt().isNegative())
15720 SCTy =
MinMax->getSCEVType();
15729 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15731 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15736 auto *DivisibleExpr =
15744void ScalarEvolution::LoopGuards::collectFromBlock(
15746 const BasicBlock *
Block,
const BasicBlock *
Pred,
15754 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
15765 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15767 if (From == FromRewritten)
15769 RewriteMap[From] = To;
15775 auto GetMaybeRewritten = [&](
const SCEV *S) {
15776 return RewriteMap.lookup_or(S, S);
15783 const SCEV *MatchLHS,
15784 const SCEV *MatchRHS) {
15785 const SCEVConstant *
C1;
15788 if (!
match(MatchLHS,
15795 .
sub(
C1->getAPInt());
15800 const SCEV *RewrittenLHS = GetMaybeRewritten(LHSUnknown);
15801 ExactRegion = ExactRegion.intersectWith(SE.
getUnsignedRange(RewrittenLHS),
15806 if (ExactRegion.isEmptySet() || ExactRegion.isWrappedSet() ||
15807 ExactRegion.isFullSet())
15810 const SCEV *RegionMin = SE.
getConstant(ExactRegion.getUnsignedMin());
15811 const SCEV *RegionMax = SE.
getConstant(ExactRegion.getUnsignedMax());
15812 const SCEV *ClampedLHS =
15814 AddRewrite(LHSUnknown, RewrittenLHS, ClampedLHS);
15817 if (MatchRangeCheckIdiom(Predicate,
LHS,
RHS))
15830 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
15832 const APInt &DividesBy =
15847 switch (Predicate) {
15876 SmallPtrSet<const SCEV *, 16> Visited;
15878 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
15882 while (!Worklist.
empty()) {
15886 if (!Visited.
insert(From).second)
15888 const SCEV *FromRewritten = GetMaybeRewritten(From);
15889 const SCEV *To =
nullptr;
15891 switch (Predicate) {
15896 EnqueueOperands(
UMax);
15902 EnqueueOperands(
SMax);
15908 EnqueueOperands(
UMin);
15915 const APInt *
C, *RHSC;
15917 match(FromRewritten,
15920 FromRewritten = From;
15923 EnqueueOperands(
SMin);
15932 const SCEV *OneAlignedUp =
15934 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
15946 const SCEVConstant *
C;
15955 Guards.NotEqual.insert({
LHS,
RHS});
15964 AddRewrite(From, FromRewritten, To);
15981 SE.F.
getParent(), Intrinsic::experimental_guard);
15983 for (
const auto *GU : GuardDecl->users())
15985 if (Guard->getFunction() ==
Block->getParent() &&
15995 unsigned NumCollectedConditions = 0;
15996 unsigned NumDomTreeSteps = 0;
15998 std::pair<const BasicBlock *, const BasicBlock *> Pair(
Pred,
Block);
15999 for (;; Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
16003 if (!NumDomTreeSteps &&
16004 Depth < SE.Opts.scalar_evolution_max_loop_guard_collection_depth) {
16005 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
16006 for (
auto &Phi : Pair.second->phis())
16011 ++NumDomTreeSteps > SE.Opts.scalar_evolution_max_guard_dom_tree_steps)
16017 const CondBrInst *LoopEntryPredicate =
16019 if (!LoopEntryPredicate)
16024 NumCollectedConditions++;
16028 if (
Depth > 0 && NumCollectedConditions == 2)
16039 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
16040 SmallVector<Value *, 8> Worklist;
16041 SmallPtrSet<Value *, 8> Visited;
16043 while (!Worklist.
empty()) {
16050 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
16074 DenseMap<const SCEV *, APInt> Multiples;
16076 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
16083 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
16084 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
16088 for (
const auto &[K, Divisor] : Multiples) {
16089 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
16090 Guards.RewriteMap[
K] =
16092 Guards.rewrite(K), Divisor, SE),
16101 Guards.PreserveNUW =
true;
16102 Guards.PreserveNSW =
true;
16103 for (
const SCEV *Expr : ExprsToRewrite) {
16104 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16105 Guards.PreserveNUW &=
16107 Guards.PreserveNSW &=
16116 if (ExprsToRewrite.size() > 1) {
16117 constexpr unsigned MaxDepth = 16;
16118 unsigned Depth = 0;
16119 SmallPtrSet<const SCEV *, 16> ToRewrite(
llvm::from_range, ExprsToRewrite);
16120 std::function<
const SCEV *(
const SCEV *)>
Lookup = [&](
const SCEV *Expr) {
16121 if (
Depth < MaxDepth && ToRewrite.erase(Expr)) {
16122 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16123 Guards.RewriteMap.erase(Expr);
16125 Guards.RewriteMap[Expr] = Guards.rewrite(RewriteTo,
Lookup);
16127 return Guards.RewriteMap.lookup(Expr);
16129 for (
const SCEV *Expr : ExprsToRewrite)
16134const SCEV *ScalarEvolution::LoopGuards::rewrite(
const SCEV *Expr)
const {
16135 return rewrite(Expr,
nullptr);
16138const SCEV *ScalarEvolution::LoopGuards::rewrite(
16143 class SCEVLoopGuardRewriter
16161 if (Guards.PreserveNUW)
16163 if (Guards.PreserveNSW)
16169 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
16170 if (
const SCEV *S =
lookup(Expr))
16175 const SCEV *visitPtrToAddrExpr(
const SCEVPtrToAddrExpr *Expr) {
16176 if (
const SCEV *S =
lookup(Expr))
16182 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
16183 if (
const SCEV *S =
lookup(Expr))
16191 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16192 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16195 if (
const SCEV *S =
lookup(NarrowExt))
16197 Bitwidth = Bitwidth / 2;
16204 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
16205 if (
const SCEV *S =
lookup(Expr))
16211 const SCEV *visitUMinExpr(
const SCEVUMinExpr *Expr) {
16212 if (
const SCEV *S =
lookup(Expr))
16217 const SCEV *visitSMinExpr(
const SCEVSMinExpr *Expr) {
16218 if (
const SCEV *S =
lookup(Expr))
16223 const SCEV *visitAddExpr(
const SCEVAddExpr *Expr) {
16224 if (
const SCEV *S =
lookup(Expr))
16229 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16234 if (NotEqual.
contains({LHS, RHS})) {
16244 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16255 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16268 const SCEV *S =
nullptr;
16296 const SCEV *visitMulExpr(
const SCEVMulExpr *Expr) {
16313 if (RewriteMap.empty() && NotEqual.
empty())
16331 if (Guards.PendingLoop)
16332 Guards.collectPending();
16333 return Guards.rewrite(Expr);
const TargetLowering & TLI
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
bpf unwind BPF Unwind Lower
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 lookup(const GsymReader &GR, GsymDataExtractor &Data, uint64_t &Offset, uint64_t BaseAddr, uint64_t Addr, SourceLocations &SrcLocs, llvm::Error &Err)
A Lookup helper functions.
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)
MachineBasicBlock * Folded
SmallVector< MachineOperand, 4 > 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 const Loop * isIntegerLoopHeaderPHI(const PHINode *PN, LoopInfo &LI)
static unsigned getConstantTripCount(const SCEVConstant *ExitCount)
static const SCEV * getNextSCEVDivisibleByDivisor(const SCEV *Expr, const APInt &DivisorVal, ScalarEvolution &SE)
static PHINode * getConstantEvolvingPHIOperands(const AnalysisOptions &Opts, Instruction *UseInst, const Loop *L, DenseMap< Instruction *, PHINode * > &PHIMap, const TargetLibraryInfo *TLI, unsigned Depth)
getConstantEvolvingPHIOperands - Implement getConstantEvolvingPHI by recursing through each instructi...
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 bool hasHugeExpression(const AnalysisOptions &Opts, ArrayRef< SCEVUse > Ops)
Returns true if Ops contains a huge SCEV (the subtree of S contains at least -scalar-evolution-huge-e...
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 std::optional< BinaryOp > MatchBinaryOp(Value *V, const DominatorTree &DT)
Try to map V into a BinaryOp, and return std::nullopt on failure.
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 BinaryOperator * getCommonInstForPHI(PHINode *PN)
static PHINode * getConstantEvolvingPHI(const AnalysisOptions &Opts, 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 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 bool IsMinMaxConsistingOf(const SCEV *MaybeMinMaxExpr, const SCEV *Candidate)
Is MaybeMinMaxExpr an (U|S)(Min|Max) of Candidate and some other values?
static SCEVFlags getNoWrapFlagsForGEP(GEPOperator *GEP, const SCEV *Accum, ScalarEvolution &SE)
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 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 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 const SCEV * constantFoldAndGroupOps(const AnalysisOptions &Opts, 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 int compareValueComplexity(const AnalysisOptions &Opts, 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 bool IsKnownPredicateViaAddRecStart(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
static const SCEV * getPreStartForExtend(const SCEVAddRecExpr *AR, ScalarEvolution *SE, unsigned Depth)
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 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 int compareSCEVComplexity(const AnalysisOptions &Opts, const LoopInfo *const LI, SCEVUse LHS, SCEVUse RHS, DominatorTree &DT)
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 CollectAddOperandsWithScales(SmallDenseMap< const SCEV *, 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 bool isKnownPredicateExtendIdiom(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
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 SCEVFlags StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type, ArrayRef< SCEVUse > Ops, SCEVFlags Flags)
static void groupByComplexity(const AnalysisOptions &Opts, 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 APInt extractConstantWithoutWrapping(ScalarEvolution &SE, const SCEVConstant *ConstantTerm, const SCEVAddExpr *WholeAddExpr)
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 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 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 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 bool scevUnconditionallyPropagatesPoisonFromOperands(SCEVTypes Kind)
static Constant * getOtherIncomingValue(PHINode *PN, BasicBlock *BB)
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.
virt reg Virtual Register Rewriter
static int Lookup(ArrayRef< TableEntry > Table, unsigned Opcode)
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.
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 isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
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 getNonStrictPredicate() const
For example, SGT -> SGE, SLT -> SLE, ULT -> ULE, UGT -> UGE.
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...
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.
bool isSingleElement() const
Return true if this set contains exactly one member.
LLVM_ABI ConstantRange truncate(uint32_t BitWidth, unsigned NoWrapKind=0) const
Return a new range in the specified integer type, which must be strictly smaller than the current typ...
LLVM_ABI ConstantRange signExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
const APInt & getUpper() const
Return the upper value for this range.
LLVM_ABI ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
static LLVM_ABI ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
LLVM_ABI bool contains(const APInt &Val) const
Return true if the specified value is in the set.
LLVM_ABI APInt 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:
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
iterator find(const_arg_type_t< KeyT > Val)
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
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_as(const LookupKeyT &Val)
Alternate version of find() which allows a different, and possibly less expensive,...
void swap(DenseMapBase &RHS)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
DomTreeNodeBase * getIDom() const
Analysis pass which computes a DominatorTree.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
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.
static LLVM_ABI std::optional< bool > isImpliedByMatchingCmp(CmpPredicate Pred1, CmpPredicate Pred2)
Determine if Pred1 implies Pred2 is true, false, or if nothing can be inferred about the implication,...
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
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.
LLVM_ABI 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(SCEVFlags 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(SCEVFlags 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
SCEVFlags getNoWrapFlags(SCEVFlags Mask=FlagsNoWrapMask) 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 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 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...
unsigned getOrderID() const
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 SCEVFlags, 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
static constexpr auto FlagsNoWrapMask
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 * getCanonical() const
Return the canonical SCEV.
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 LoopGuards collectOnDemand(const Loop *L, ScalarEvolution &SE)
Return loop guards for loop L, which are collected on first use.
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.
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 ...
static bool hasFlags(SCEVFlags Flags, SCEVFlags TestFlags)
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 const SCEV * getElementCount(Type *Ty, ElementCount EC, SCEVFlags Flags=SCEV::FlagNone)
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 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 const SCEV * getMinusSCEV(SCEVUse LHS, SCEVUse RHS, SCEVFlags Flags=SCEV::FlagNone, unsigned Depth=0)
Return LHS-RHS.
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 SCEVFlags setFlags(SCEVFlags Flags, SCEVFlags OnFlags)
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 SCEVUse getAddRecExpr(SCEVUse Start, SCEVUse Step, const Loop *L, SCEVFlagsPair Flags)
Get an add recurrence expression for the specified loop.
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.
static SCEVFlags clearFlags(SCEVFlags Flags, SCEVFlags OffFlags)
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.
static SCEVFlags maskFlags(SCEVFlags Flags, SCEVFlags Mask)
Convenient SCEVFlags manipulation.
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 SCEVUse getAddExpr(SmallVectorImpl< SCEVUse > &Ops, SCEVFlagsPair Flags={}, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
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...
LLVM_ABI std::optional< SCEVFlags > getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO)
Parse NSW/NUW flags from add/sub/mul IR binary operation Op into SCEV no-wrap flags,...
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.
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)
@ 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.
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.
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 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 void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEVFlags Flags)
Update no-wrap flags of an AddRec.
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 SCEVUse getMulExpr(SmallVectorImpl< SCEVUse > &Ops, SCEVFlagsPair Flags={}, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
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 bool isGuaranteedNotToCauseUB(const SCEV *Op)
Returns true if Op is guaranteed not to cause immediate UB.
LLVM_ABI const SCEV * getSizeOfExpr(Type *IntTy, TypeSize Size)
Return an expression for a TypeSize.
LLVM_ABI std::optional< bool > evaluatePredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Check whether the condition described by Pred, LHS, and RHS is true or false.
LLVM_ABI const SCEV * getUnknown(Value *V)
LLVM_ABI std::optional< std::pair< const SCEV *, SmallVector< const SCEVPredicate *, 3 > > > createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI)
Checks if SymbolicPHI can be rewritten as an AddRecExpr under some Predicates.
LLVM_ABI const SCEV * getTruncateOrZeroExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool isKnownViaInduction(CmpPredicate Pred, SCEVUse LHS, SCEVUse RHS)
We'd like to check the predicate on every iteration of the most dominated loop between loops used in ...
LLVM_ABI std::optional< APInt > computeConstantDifference(const SCEV *LHS, const SCEV *RHS)
Compute LHS - RHS and returns the result as an APInt if it is a constant, and std::nullopt if it isn'...
LLVM_ABI bool properlyDominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
LLVM_ABI const SCEV * getNegativeSCEV(const SCEV *V, SCEVFlags Flags=SCEV::FlagNone)
Return the SCEV object corresponding to -V.
LLVM_ABI const SCEV * getUDivExactExpr(SCEVUse LHS, SCEVUse RHS)
Get a canonical unsigned division expression, or something simpler if possible.
LLVM_ABI const SCEV * rewriteUsingPredicate(const SCEV *S, const Loop *L, const SCEVPredicate &A)
Re-writes the SCEV according to the Predicates in A.
LLVM_ABI std::pair< const SCEV *, const SCEV * > SplitIntoInitAndPostInc(const Loop *L, const SCEV *S)
Splits SCEV expression S into two SCEVs.
LLVM_ABI bool canReuseInstruction(const SCEV *S, Instruction *I, SmallVectorImpl< Instruction * > &DropPoisonGeneratingInsts)
Check whether it is poison-safe to represent the expression S using the instruction I.
LLVM_ABI bool isKnownPredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI const SCEV * getPredicatedSymbolicMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getSymbolicMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
LLVM_ABI ~ScalarEvolution()
LLVM_ABI const SCEV * getGEPExpr(GEPOperator *GEP, ArrayRef< SCEVUse > IndexExprs)
Returns an expression for a GEP.
LLVM_ABI const SCEV * getUMinExpr(SCEVUse LHS, SCEVUse RHS, bool Sequential=false)
LLVM_ABI bool isBasicBlockEntryGuardedByCond(const BasicBlock *BB, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the basic block is protected by a conditional between LHS and RHS.
LLVM_ABI const SCEV * getTruncateOrSignExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool containsErasedValue(const SCEV *S) const
Return true if the SCEV expression contains a Value that has been optimised out and is now a nullptr.
const SCEV * getSymbolicMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEV that is greater than or equal to (i.e.
APInt getSignedRangeMax(const SCEV *S)
Determine the max of the signed range for a particular SCEV.
LLVM_ABI void verify() const
LLVMContext & getContext() const
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.
LLVM_ABI unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element 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.
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
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)
SCEVBinaryExpr_match< SCEVAddExpr, Op0_t, Op1_t, SCEV::FlagNSW > m_scev_NSWAdd(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< SCEVUMaxExpr, Op0_t, Op1_t, SCEV::FlagNone, true > m_scev_UMax(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.
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.
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.
LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CtxI=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...
auto uninitialized_copy(R &&Src, IterTy Dst)
bool isa_and_nonnull(const Y &Val)
LLVM_ABI unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CtxI=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.
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
auto map_range(ContainerTy &&C, FuncTy F)
Return a range that applies F to the elements of C.
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,...
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Function *CtxF=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
const AnalysisOptions & getAnalysisOptions(const LLVMContext &C)
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.
void sort(IteratorTy Start, IteratorTy End)
LLVM_ABI bool isFinite(const Loop *L)
Return true if this loop can be assumed to run for a finite number of iterations.
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)
SCEVFlags
SCEVFlags are bitfield indices into SCEV's SubclassData.
ArrayRef(const T &OneElt) -> ArrayRef< T >
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.
@ End
Run the machine verifier once, at the end of the pipeline.
constexpr detail::IsaCheckPredicate< Types... > IsaPred
Function object wrapper for the llvm::isa type check.
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.
SCEVFlags ExprFlags
Flags applied directly to a SCEV expression, must be valid wherever the expression is valid.
SCEVFlags UseFlags
Flags only applied to a SCEVUse.
static SCEVUseT getCommon(SCEVUseT A, SCEVUseT B)
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