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;
4375 auto [
I, Inserted] = HasRecMap.try_emplace(S);
4385 ExprValueMapType::iterator
SI = ExprValueMap.find_as(S);
4386 if (
SI == ExprValueMap.end())
4394void ScalarEvolution::eraseValueFromMap(
Value *
V) {
4396 if (
I != ValueExprMap.end()) {
4397 auto EVIt = ExprValueMap.find(
I->second);
4400 ValueExprMap.erase(
I);
4404void ScalarEvolution::insertValueToMap(
Value *
V,
const SCEV *S) {
4408 if (ValueExprMap.insert({SCEVCallbackVH(V, this), S}).second)
4409 ExprValueMap[S].push_back(
V);
4419 return createSCEVIter(V);
4426 if (
I != ValueExprMap.end()) {
4427 const SCEV *S =
I->second;
4428 assert(checkValidity(S) &&
4429 "existing SCEV has not been properly invalidated");
4441 Type *Ty = V->getType();
4457 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4470 return (
const SCEV *)
nullptr;
4476 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4480 Type *Ty = V->getType();
4486 assert(
P->getType()->isPointerTy());
4501 if (AddOp->getType()->isPointerTy()) {
4502 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4519 return getZero(LHS->getType());
4524 if (RHS->getType()->isPointerTy()) {
4525 if (!LHS->getType()->isPointerTy() ||
4535 const bool RHSIsNotMinSigned =
4566 Type *SrcTy = V->getType();
4567 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4568 "Cannot truncate or zero extend with non-integer arguments!");
4578 Type *SrcTy = V->getType();
4579 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4580 "Cannot truncate or zero extend with non-integer arguments!");
4589 Type *SrcTy = V->getType();
4590 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4591 "Cannot noop or zero extend with non-integer arguments!");
4593 "getNoopOrZeroExtend cannot truncate!");
4600 Type *SrcTy = V->getType();
4601 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4602 "Cannot noop or sign extend with non-integer arguments!");
4604 "getNoopOrSignExtend cannot truncate!");
4611 Type *SrcTy = V->getType();
4612 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4613 "Cannot noop or any extend with non-integer arguments!");
4615 "getNoopOrAnyExtend cannot truncate!");
4622 Type *SrcTy = V->getType();
4623 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4624 "Cannot truncate or noop with non-integer arguments!");
4626 "getTruncateOrNoop cannot extend!");
4634 const SCEV *PromotedLHS = LHS;
4635 const SCEV *PromotedRHS = RHS;
4655 assert(!
Ops.empty() &&
"At least one operand must be!");
4657 if (
Ops.size() == 1)
4661 Type *MaxType =
nullptr;
4667 assert(MaxType &&
"Failed to find maximum type!");
4680 if (!V->getType()->isPointerTy())
4685 V = AddRec->getStart();
4687 const SCEV *PtrOp =
nullptr;
4688 for (
const SCEV *AddOp :
Add->operands()) {
4689 if (AddOp->getType()->isPointerTy()) {
4690 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4694 assert(PtrOp &&
"Must have pointer op");
4706 for (
User *U :
I->users()) {
4708 if (Visited.
insert(UserInsn).second)
4722 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4723 bool IgnoreOtherLoops =
true) {
4726 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4728 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4733 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4735 SeenLoopVariantSCEVUnknown =
true;
4739 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4743 SeenOtherLoops =
true;
4747 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4749 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4752 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
4753 : SCEVRewriteVisitor(SE),
L(
L) {}
4756 bool SeenLoopVariantSCEVUnknown =
false;
4757 bool SeenOtherLoops =
false;
4766 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
4767 SCEVPostIncRewriter
Rewriter(L, SE);
4769 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4774 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4776 SeenLoopVariantSCEVUnknown =
true;
4780 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4784 SeenOtherLoops =
true;
4788 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4790 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4793 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
4794 : SCEVRewriteVisitor(SE),
L(
L) {}
4797 bool SeenLoopVariantSCEVUnknown =
false;
4798 bool SeenOtherLoops =
false;
4804class SCEVBackedgeConditionFolder
4807 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4808 ScalarEvolution &SE) {
4809 bool IsPosBECond =
false;
4810 Value *BECond =
nullptr;
4811 if (BasicBlock *Latch =
L->getLoopLatch()) {
4813 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
4814 "Both outgoing branches should not target same header!");
4815 BECond = BI->getCondition();
4816 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
4821 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
4825 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4826 const SCEV *
Result = Expr;
4831 switch (
I->getOpcode()) {
4832 case Instruction::Select: {
4834 std::optional<const SCEV *> Res =
4835 compareWithBackedgeCondition(
SI->getCondition());
4843 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
4854 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
4855 bool IsPosBECond, ScalarEvolution &SE)
4856 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
4857 IsPositiveBECond(IsPosBECond) {}
4859 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
4863 Value *BackedgeCond =
nullptr;
4865 bool IsPositiveBECond;
4868std::optional<const SCEV *>
4869SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
4874 if (BackedgeCond == IC)
4877 return std::nullopt;
4882 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4883 ScalarEvolution &SE) {
4889 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4896 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4906 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
4907 : SCEVRewriteVisitor(SE),
L(
L) {}
4915void ScalarEvolution::inferNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
4931 const APInt &BECountAP = BECountMax->getAPInt();
4932 unsigned NoOverflowBitWidth =
4941ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
4951 if (!SignedWrapViaInductionTried.insert(AR).second)
4976 AC.assumptions().empty())
4984 const SCEV *OverflowLimit =
4986 if (OverflowLimit &&
4994ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5004 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5029 AC.assumptions().empty())
5038 const SCEV *OverflowLimit =
5067 IsNSW = OBO->hasNoSignedWrap();
5068 IsNUW = OBO->hasNoUnsignedWrap();
5074 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5084 return std::nullopt;
5090 switch (
Op->getOpcode()) {
5091 case Instruction::Add:
5092 case Instruction::Sub:
5093 case Instruction::Mul:
5094 case Instruction::UDiv:
5095 case Instruction::URem:
5096 case Instruction::And:
5097 case Instruction::AShr:
5098 case Instruction::Shl:
5101 case Instruction::Or: {
5104 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5114 case Instruction::Xor:
5118 if (RHSC->getValue().isSignMask())
5119 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5121 if (
V->getType()->isIntegerTy(1))
5122 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5125 case Instruction::LShr:
5134 if (SA->getValue().ult(
BitWidth)) {
5136 ConstantInt::get(SA->getContext(),
5138 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5143 case Instruction::ExtractValue: {
5145 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5153 bool Signed = WO->isSigned();
5156 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5161 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5172 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5173 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5175 return std::nullopt;
5201 if (
Op == SymbolicPHI)
5206 if (SourceBits != NewBits)
5224 if (!L || L->getHeader() != PN->
getParent())
5282std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5283ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5291 assert(L &&
"Expecting an integer loop header phi");
5296 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5297 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5298 Value *
V = PN->getIncomingValue(i);
5299 if (
L->contains(PN->getIncomingBlock(i))) {
5302 }
else if (BEValueV !=
V) {
5306 }
else if (!StartValueV) {
5308 }
else if (StartValueV !=
V) {
5309 StartValueV =
nullptr;
5313 if (!BEValueV || !StartValueV)
5314 return std::nullopt;
5316 const SCEV *BEValue =
getSCEV(BEValueV);
5323 return std::nullopt;
5327 unsigned FoundIndex =
Add->getNumOperands();
5328 Type *TruncTy =
nullptr;
5330 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5333 if (FoundIndex == e) {
5338 if (FoundIndex ==
Add->getNumOperands())
5339 return std::nullopt;
5343 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5344 if (i != FoundIndex)
5345 Ops.push_back(
Add->getOperand(i));
5351 return std::nullopt;
5404 const SCEV *StartVal =
getSCEV(StartValueV);
5405 const SCEV *PHISCEV =
5432 auto getExtendedExpr = [&](
const SCEV *Expr,
5433 bool CreateSignExtend) ->
const SCEV * {
5436 const SCEV *ExtendedExpr =
5439 return ExtendedExpr;
5447 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5448 const SCEV *ExtendedExpr) ->
bool {
5449 return Expr != ExtendedExpr &&
5453 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5454 if (PredIsKnownFalse(StartVal, StartExtended)) {
5456 return std::nullopt;
5461 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5462 if (PredIsKnownFalse(Accum, AccumExtended)) {
5464 return std::nullopt;
5467 auto AppendPredicate = [&](
const SCEV *Expr,
5468 const SCEV *ExtendedExpr) ->
void {
5469 if (Expr != ExtendedExpr &&
5477 AppendPredicate(StartVal, StartExtended);
5478 AppendPredicate(Accum, AccumExtended);
5486 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5487 std::make_pair(NewAR, Predicates);
5489 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5493std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5498 return std::nullopt;
5501 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5502 if (
I != PredicatedSCEVRewrites.end()) {
5503 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5506 if (Rewrite.first == SymbolicPHI)
5507 return std::nullopt;
5511 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5515 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5516 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5521 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5522 return std::nullopt;
5542 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5543 if (Expr1 != Expr2 &&
5544 !AllPreds.
implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5545 !AllPreds.
implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5580const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5582 Value *StartValueV) {
5585 assert(BEValueV && StartValueV);
5587 const SCEV *Accum =
nullptr;
5590 if (BO->Opcode != Instruction::Add)
5593 if (BO->LHS == PN &&
L->isLoopInvariant(BO->RHS))
5595 else if (BO->RHS == PN &&
L->isLoopInvariant(BO->LHS))
5609 if (!
GEP ||
GEP->getPointerOperand() != PN ||
GEP->getNumIndices() != 1)
5612 if (!
L->isLoopInvariant(Idx))
5621 const SCEV *StartVal =
getSCEV(StartValueV);
5622 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5623 insertValueToMap(PN, PHISCEV);
5626 inferNoWrapViaConstantRanges(AR);
5633 "Accum is defined outside L, but is not invariant?");
5634 if (isAddRecNeverPoison(BEInst, L))
5641const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5649 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5655 }
else if (BEValueV !=
V) {
5659 }
else if (!StartValueV) {
5661 }
else if (StartValueV !=
V) {
5662 StartValueV =
nullptr;
5666 if (!BEValueV || !StartValueV)
5669 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5670 "PHI node already processed?");
5674 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5679 insertValueToMap(PN, SymbolicName);
5683 const SCEV *BEValue =
getSCEV(BEValueV);
5693 unsigned FoundIndex =
Add->getNumOperands();
5694 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5695 if (
Add->getOperand(i) == SymbolicName)
5696 if (FoundIndex == e) {
5701 if (FoundIndex !=
Add->getNumOperands()) {
5704 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5705 if (i != FoundIndex)
5706 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5718 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5725 if (
GEP->getOperand(0) == PN)
5733 const SCEV *StartVal =
getSCEV(StartValueV);
5734 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5739 forgetMemoizedResults({SymbolicName});
5740 insertValueToMap(PN, PHISCEV);
5743 inferNoWrapViaConstantRanges(AR);
5767 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5768 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5771 const SCEV *StartVal =
getSCEV(StartValueV);
5772 if (Start == StartVal) {
5776 forgetMemoizedResults({SymbolicName});
5777 insertValueToMap(PN, Shifted);
5787 eraseValueFromMap(PN);
5802 Use &LeftUse =
Merge->getOperandUse(0);
5803 Use &RightUse =
Merge->getOperandUse(1);
5839 assert(IDom &&
"At least the entry block should dominate PN");
5847const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
5852 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
5869 CommonInst = IncomingInst;
5885ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
5891 const SCEV *CommonSCEV =
getSCEV(CommonInst);
5892 bool SCEVExprsIdentical =
5894 [
this, CommonSCEV](
Value *
V) { return CommonSCEV == getSCEV(V); });
5895 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
5898const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
5899 if (
const SCEV *S = createAddRecFromPHI(PN))
5909 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
5912 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
5921 struct FindClosure {
5922 const SCEV *OperandToFind;
5928 bool canRecurseInto(
SCEVTypes Kind)
const {
5931 return RootKind == Kind || NonSequentialRootKind == Kind ||
5936 : OperandToFind(OperandToFind), RootKind(RootKind),
5937 NonSequentialRootKind(
5941 bool follow(
const SCEV *S) {
5942 Found = S == OperandToFind;
5944 return !isDone() && canRecurseInto(S->
getSCEVType());
5947 bool isDone()
const {
return Found; }
5950 FindClosure FC(OperandToFind, RootKind);
5955std::optional<const SCEV *>
5956ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
5966 switch (ICI->getPredicate()) {
5980 bool Signed = ICI->isSigned();
5981 const SCEV *LA =
getSCEV(TrueVal);
5989 if (LA == LS &&
RA == RS)
5991 if (LA == RS &&
RA == LS)
5994 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
5995 if (
Op->getType()->isPointerTy()) {
6006 LS = CoerceOperand(LS);
6007 RS = CoerceOperand(RS);
6031 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6032 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6046 X = ZExt->getOperand();
6048 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6059 return std::nullopt;
6062static std::optional<const SCEV *>
6064 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6068 "Unexpected operands of a select.");
6080 return std::nullopt;
6095static std::optional<const SCEV *>
6099 return std::nullopt;
6102 const auto *SETrue = SE->
getSCEV(TrueVal);
6103 const auto *SEFalse = SE->
getSCEV(FalseVal);
6107const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6109 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6111 V->getType() ==
TrueVal->getType() &&
6112 "Types of select hands and of the result must match.");
6115 if (!
V->getType()->isIntegerTy(1))
6118 if (std::optional<const SCEV *> S =
6131 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6135 if (std::optional<const SCEV *> S =
6136 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6142 return createNodeForSelectOrPHIViaUMinSeq(
V,
Cond, TrueVal, FalseVal);
6148 assert(
GEP->getSourceElementType()->isSized() &&
6149 "GEP source element type must be sized");
6152 for (
Value *Index :
GEP->indices())
6157APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6160 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6163 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6165 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6168 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6186 return GetShiftedByZeros(TZ);
6196 return GetShiftedByZeros(TZ);
6200 if (
M->hasNoUnsignedWrap()) {
6203 for (
const SCEV *Operand :
M->operands().drop_front())
6211 for (
const SCEV *Operand :
M->operands())
6213 return GetShiftedByZeros(TZ);
6218 if (
N->hasNoUnsignedWrap())
6219 return GetGCDMultiple(
N);
6222 for (
const SCEV *Operand :
N->operands().drop_front())
6224 return GetShiftedByZeros(TZ);
6241 CtxI = &*F.getEntryBlock().begin();
6248 .allowEphemerals(
true))
6249 .countMinTrailingZeros();
6250 return GetShiftedByZeros(
Known);
6263 return getConstantMultipleImpl(S, CtxI);
6265 auto I = ConstantMultipleCache.find(S);
6266 if (
I != ConstantMultipleCache.end())
6269 APInt Result = getConstantMultipleImpl(S, CtxI);
6270 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6271 assert(InsertPair.second &&
"Should insert a new key");
6272 return InsertPair.first->second;
6289 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6292 if (std::optional<ConstantRange>
Range = CB->getRange())
6296 if (std::optional<ConstantRange>
Range =
A->getRange())
6299 return std::nullopt;
6306 UnsignedRanges.erase(AddRec);
6307 SignedRanges.erase(AddRec);
6308 ConstantMultipleCache.erase(AddRec);
6313getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6339 Value *Start, *Step;
6346 assert(L && L->getHeader() ==
P->getParent());
6359 case Instruction::AShr:
6360 case Instruction::LShr:
6361 case Instruction::Shl:
6376 KnownStep.getBitWidth() ==
BitWidth);
6379 auto MaxShiftAmt = KnownStep.getMaxValue();
6381 bool Overflow =
false;
6382 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6389 case Instruction::AShr: {
6397 if (KnownStart.isNonNegative())
6400 KnownStart.getMaxValue() + 1);
6401 if (KnownStart.isNegative())
6404 KnownEnd.getMaxValue() + 1);
6407 case Instruction::LShr: {
6416 KnownStart.getMaxValue() + 1);
6418 case Instruction::Shl: {
6422 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6423 return ConstantRange(KnownStart.getMinValue(),
6424 KnownEnd.getMaxValue() + 1);
6449 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6456ScalarEvolution::getRangeRefIter(
const SCEV *S,
6457 ScalarEvolution::RangeSignHint SignHint) {
6458 DenseMap<const SCEV *, ConstantRange> &Cache =
6459 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6462 SmallPtrSet<const SCEV *, 8> Seen;
6466 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6467 if (!Seen.
insert(Expr).second)
6500 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6501 const SCEV *
P = WorkList[
I];
6505 for (
const SCEV *
Op :
P->operands())
6518 if (!WorkList.
empty()) {
6523 getRangeRef(
P, SignHint);
6527 return getRangeRef(S, SignHint, 0);
6530const APInt *ScalarEvolution::getConstantAPIntOrNull(
const SCEV *S) {
6532 return &
C->getAPInt();
6540 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6541 DenseMap<const SCEV *, ConstantRange> &Cache =
6542 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6549 auto I = Cache.
find(S);
6550 if (
I != Cache.
end())
6554 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6558 if (
Depth > Opts.scev_range_iter_threshold)
6559 return getRangeRefIter(S, SignHint);
6562 ConstantRange ConservativeResult(
BitWidth,
true);
6563 using OBO = OverflowingBinaryOperator;
6567 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6571 ConservativeResult =
6578 ConservativeResult = ConstantRange(
6594 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6601 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6608 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6613 return setRange(Cast, SignHint,
X);
6618 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6619 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6621 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6622 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6623 ConservativeResult =
6624 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6626 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6627 unsigned WrapType = OBO::AnyWrap;
6628 if (
Add->hasNoSignedWrap())
6629 WrapType |= OBO::NoSignedWrap;
6630 if (
Add->hasNoUnsignedWrap())
6631 WrapType |= OBO::NoUnsignedWrap;
6633 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6635 return setRange(
Add, SignHint,
6636 ConservativeResult.intersectWith(
X, RangeType));
6640 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6642 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6643 return setRange(
Mul, SignHint,
6644 ConservativeResult.intersectWith(
X, RangeType));
6648 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6649 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6650 return setRange(UDiv, SignHint,
6651 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6659 if (!UnsignedMinValue.
isZero())
6660 ConservativeResult = ConservativeResult.intersectWith(
6661 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6670 bool AllNonNeg =
true;
6671 bool AllNonPos =
true;
6672 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6679 ConservativeResult = ConservativeResult.intersectWith(
6684 ConservativeResult = ConservativeResult.intersectWith(
6693 const SCEV *MaxBEScev =
6707 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
6709 ConservativeResult =
6710 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6713 auto RangeFromFactoring = getRangeViaFactoring(
6715 ConservativeResult =
6716 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6721 if (Opts.scalar_evolution_use_expensive_range_sharpening) {
6722 const SCEV *SymbolicMaxBECount =
6727 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6728 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6729 ConservativeResult =
6730 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6735 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6745 ID = Intrinsic::umax;
6748 ID = Intrinsic::smax;
6752 ID = Intrinsic::umin;
6755 ID = Intrinsic::smin;
6762 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6763 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6765 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6766 return setRange(S, SignHint,
6767 ConservativeResult.intersectWith(
X, RangeType));
6776 ConservativeResult =
6777 ConservativeResult.intersectWith(*MDRange, RangeType);
6782 auto CR = getRangeForUnknownRecurrence(U);
6783 ConservativeResult = ConservativeResult.intersectWith(CR);
6794 if (
U->getType()->isPointerTy()) {
6797 unsigned PtrIdxDiff =
6798 DL.getPointerTypeSizeInBits(
U->getType()) -
BitWidth;
6799 NS = NS > PtrIdxDiff ? NS - PtrIdxDiff : 1;
6804 if (!
Known.Zero.getHiBits(NS).isZero())
6805 Known.Zero.setHighBits(NS);
6806 if (!
Known.One.getHiBits(NS).isZero())
6807 Known.One.setHighBits(NS);
6810 if (
Known.getMinValue() !=
Known.getMaxValue() + 1)
6811 ConservativeResult = ConservativeResult.intersectWith(
6812 ConstantRange(
Known.getMinValue(),
Known.getMaxValue() + 1),
6815 ConservativeResult = ConservativeResult.intersectWith(
6820 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6824 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
6825 DL, CanBeNull,
nullptr);
6841 ConservativeResult = ConservativeResult.intersectWith(
6851 return getRangeRef(AR, SignHint,
Depth + 1);
6855 ConstantRange RangeFromOps(
BitWidth,
false);
6857 for (
const auto &
Op :
Phi->operands()) {
6859 RangeFromOps = RangeFromOps.unionWith(OpRange, RangeType);
6861 if (RangeFromOps.isFullSet())
6864 ConservativeResult =
6865 ConservativeResult.intersectWith(RangeFromOps, RangeType);
6869 const APInt *TrueC, *FalseC;
6871 ConservativeResult = ConservativeResult.intersectWith(
6872 ConstantRange(*TrueC).unionWith(*FalseC, RangeType), RangeType);
6876 if (
II->getIntrinsicID() == Intrinsic::vscale) {
6878 ConservativeResult = ConservativeResult.difference(Disallowed);
6881 return setRange(U, SignHint, std::move(ConservativeResult));
6887 return setRange(S, SignHint, std::move(ConservativeResult));
6895static std::pair<ConstantRange, bool>
6903 if (Step == 0 || MaxBECount == 0)
6904 return {StartRange,
true};
6910 return {ConstantRange::getFull(
BitWidth),
false};
6926 return {ConstantRange::getFull(
BitWidth),
false};
6939 APInt MovedBoundary;
6944 MovedBoundary = StartLower - std::move(
Offset);
6947 MovedBoundary = StartUpper + std::move(
Offset);
6951 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
6958 if (StartRange.
contains(MovedBoundary))
6959 return {ConstantRange::getFull(
BitWidth),
false};
6962 Descending ? std::move(MovedBoundary) : std::move(StartLower);
6964 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
6972std::pair<ConstantRange, SCEVFlags>
6973ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
6974 const APInt &MaxBECount) {
6978 "mismatched bit widths");
6987 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
6992 StepSRange.
getSignedMax(), StartSRange, MaxBECount,
true);
6993 SR = SR.unionWith(SRMax);
7012ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7014 ScalarEvolution::RangeSignHint SignHint) {
7015 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7017 "This only works for non-self-wrapping AddRecs!");
7018 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7022 return ConstantRange::getFull(
BitWidth);
7030 return ConstantRange::getFull(
BitWidth);
7034 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7036 MaxItersWithoutWrap))
7037 return ConstantRange::getFull(
BitWidth);
7058 ConstantRange StartRange = getRangeRef(Start, SignHint);
7059 ConstantRange EndRange = getRangeRef(
End, SignHint);
7060 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7064 return RangeBetween;
7069 return ConstantRange::getFull(
BitWidth);
7072 isKnownPredicateViaConstantRanges(LEPred, Start,
End))
7073 return RangeBetween;
7075 isKnownPredicateViaConstantRanges(GEPred, Start,
End))
7076 return RangeBetween;
7077 return ConstantRange::getFull(
BitWidth);
7082 const APInt &MaxBECount) {
7089 "mismatched bit widths");
7091 struct SelectPattern {
7092 Value *Condition =
nullptr;
7096 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7098 std::optional<unsigned> CastOp;
7112 CastOp = SCast->getSCEVType();
7113 S = SCast->getOperand();
7116 using namespace llvm::PatternMatch;
7123 Condition =
nullptr;
7155 bool isRecognized() {
return Condition !=
nullptr; }
7158 SelectPattern StartPattern(*
this,
BitWidth, Start);
7159 if (!StartPattern.isRecognized())
7160 return ConstantRange::getFull(
BitWidth);
7162 SelectPattern StepPattern(*
this,
BitWidth, Step);
7163 if (!StepPattern.isRecognized())
7164 return ConstantRange::getFull(
BitWidth);
7166 if (StartPattern.Condition != StepPattern.Condition) {
7170 return ConstantRange::getFull(
BitWidth);
7181 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7182 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7183 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7184 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7186 ConstantRange TrueRange =
7187 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7188 ConstantRange FalseRange =
7189 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7202 PDI && PDI->isDisjoint()) {
7217ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7230 SmallPtrSet<const SCEV *, 16> Visited;
7232 auto pushOp = [&](
const SCEV *S) {
7233 if (!Visited.
insert(S).second)
7236 if (Visited.
size() > 30) {
7247 while (!Worklist.
empty()) {
7249 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7250 if (!Bound || DT.dominates(Bound, DefI))
7257 return Bound ? Bound : &*F.getEntryBlock().begin();
7263 return getDefiningScopeBound(
Ops, Discard);
7266bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7268 if (
A->getParent() ==
B->getParent() &&
7273 auto *BLoop = LI.getLoopFor(
B->getParent());
7274 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7275 BLoop->getLoopPreheader() ==
A->getParent() &&
7277 A->getParent()->end()) &&
7285 SCEVPoisonCollector PC(
true);
7287 return PC.MaybePoison.
empty();
7300bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7317 for (
const Use &
Op :
I->operands()) {
7323 auto *DefI = getDefiningScopeBound(SCEVOps);
7324 return isGuaranteedToTransferExecutionTo(DefI,
I);
7327bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7329 if (isSCEVExprNeverPoison(
I))
7340 auto *ExitingBB =
L->getExitingBlock();
7344 SmallPtrSet<const Value *, 16> KnownPoison;
7353 while (!Worklist.
empty()) {
7356 for (
const Use &U :
Poison->uses()) {
7359 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7363 if (KnownPoison.
insert(PoisonUser).second)
7371ScalarEvolution::LoopProperties
7372ScalarEvolution::getLoopProperties(
const Loop *L) {
7373 using LoopProperties = ScalarEvolution::LoopProperties;
7375 auto Itr = LoopPropertiesCache.find(L);
7376 if (Itr == LoopPropertiesCache.end()) {
7379 return !
SI->isSimple();
7387 if (!
MI->isVolatile())
7391 if (
I->isDroppable())
7394 return I->mayWriteToMemory();
7397 LoopProperties LP = {
true,
7400 for (
auto *BB :
L->getBlocks())
7401 for (
auto &
I : *BB) {
7403 LP.HasNoAbnormalExits =
false;
7404 if (HasSideEffects(&
I))
7405 LP.HasNoSideEffects =
false;
7406 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7410 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7411 assert(InsertPair.second &&
"We just checked!");
7412 Itr = InsertPair.first;
7425const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7431 Stack.emplace_back(V,
false);
7432 while (!Stack.empty()) {
7433 auto E = Stack.back();
7434 Value *CurV = E.getPointer();
7442 const SCEV *CreatedSCEV =
nullptr;
7445 CreatedSCEV = createSCEV(CurV);
7450 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7454 insertValueToMap(CurV, CreatedSCEV);
7457 Stack.back().setInt(
true);
7460 Stack.emplace_back(
Op,
false);
7477 if (!DT.isReachableFromEntry(
I->getParent()))
7489 switch (BO->Opcode) {
7490 case Instruction::Add:
7491 case Instruction::Mul: {
7498 Ops.push_back(BO->
Op);
7502 Ops.push_back(BO->RHS);
7505 (BO->Opcode == Instruction::Add &&
7506 (NewBO->Opcode != Instruction::Add &&
7507 NewBO->Opcode != Instruction::Sub)) ||
7508 (BO->Opcode == Instruction::Mul &&
7509 NewBO->Opcode != Instruction::Mul)) {
7510 Ops.push_back(BO->LHS);
7515 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7518 Ops.push_back(BO->LHS);
7526 case Instruction::Sub:
7527 case Instruction::UDiv:
7528 case Instruction::URem:
7530 case Instruction::AShr:
7531 case Instruction::Shl:
7532 case Instruction::Xor:
7536 case Instruction::And:
7537 case Instruction::Or:
7541 case Instruction::LShr:
7548 Ops.push_back(BO->LHS);
7549 Ops.push_back(BO->RHS);
7553 switch (
U->getOpcode()) {
7554 case Instruction::Trunc:
7555 case Instruction::ZExt:
7556 case Instruction::SExt:
7557 case Instruction::PtrToAddr:
7558 case Instruction::PtrToInt:
7559 Ops.push_back(
U->getOperand(0));
7562 case Instruction::BitCast:
7564 Ops.push_back(
U->getOperand(0));
7569 case Instruction::SDiv:
7570 case Instruction::SRem:
7571 Ops.push_back(
U->getOperand(0));
7572 Ops.push_back(
U->getOperand(1));
7575 case Instruction::GetElementPtr:
7577 "GEP source element type must be sized");
7581 case Instruction::IntToPtr:
7584 case Instruction::PHI:
7615 Ops.push_back(CondICmp->getOperand(0));
7616 Ops.push_back(CondICmp->getOperand(1));
7636 case Instruction::Select: {
7638 auto CanSimplifyToUnknown = [
this,
U]() {
7656 if (CanSimplifyToUnknown())
7663 case Instruction::Call:
7664 case Instruction::Invoke:
7671 switch (
II->getIntrinsicID()) {
7672 case Intrinsic::abs:
7673 Ops.push_back(
II->getArgOperand(0));
7675 case Intrinsic::umax:
7676 case Intrinsic::umin:
7677 case Intrinsic::smax:
7678 case Intrinsic::smin:
7679 case Intrinsic::usub_sat:
7680 case Intrinsic::uadd_sat:
7681 Ops.push_back(
II->getArgOperand(0));
7682 Ops.push_back(
II->getArgOperand(1));
7684 case Intrinsic::start_loop_iterations:
7685 case Intrinsic::annotation:
7686 case Intrinsic::ptr_annotation:
7687 Ops.push_back(
II->getArgOperand(0));
7699const SCEV *ScalarEvolution::createSCEV(
Value *
V) {
7708 if (!DT.isReachableFromEntry(
I->getParent()))
7722 switch (BO->Opcode) {
7723 case Instruction::Add: {
7749 if (BO->Opcode == Instruction::Sub)
7757 if (BO->Opcode == Instruction::Sub)
7763 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7764 NewBO->Opcode != Instruction::Sub)) {
7774 case Instruction::Mul: {
7794 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7803 case Instruction::UDiv:
7807 case Instruction::URem:
7811 case Instruction::Sub: {
7814 Flags = getNoWrapFlagsFromUB(BO->
Op);
7819 Value *PtrLHS =
nullptr, *PtrRHS =
nullptr;
7822 if (HasPtrLHS || HasPtrRHS) {
7827 auto GetOp = [&](
bool HasPtr,
Value *PtrOp,
Value *OrigOp,
7828 bool BothPtr) ->
const SCEV * {
7831 const SCEV *PtrSCEV =
getSCEV(PtrOp);
7841 const SCEV *
L = GetOp(HasPtrLHS, PtrLHS, BO->LHS, HasPtrRHS);
7842 const SCEV *
R = GetOp(HasPtrRHS, PtrRHS, BO->RHS, HasPtrLHS);
7850 case Instruction::And:
7856 if (CI->isMinusOne())
7858 const APInt &
A = CI->getValue();
7864 unsigned LZ =
A.countl_zero();
7865 unsigned TZ =
A.countr_zero();
7870 APInt EffectiveMask =
7872 if ((LZ != 0 || TZ != 0) && !((~
A & ~
Known.Zero) & EffectiveMask)) {
7875 const SCEV *ShiftedLHS =
nullptr;
7879 unsigned MulZeros = OpC->getAPInt().countr_zero();
7880 unsigned GCD = std::min(MulZeros, TZ);
7885 const SCEV *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
7907 case Instruction::Or:
7916 case Instruction::Xor:
7919 if (CI->isMinusOne())
7928 if (LBO->getOpcode() == Instruction::And &&
7929 LCI->getValue() == CI->getValue())
7930 if (
const SCEVZeroExtendExpr *Z =
7933 const SCEV *Z0 =
Z->getOperand();
7940 if (CI->getValue().isMask(Z0TySize))
7946 APInt Trunc = CI->getValue().trunc(Z0TySize);
7955 case Instruction::Shl:
7973 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
7982 ConstantInt *
X = ConstantInt::get(
7988 case Instruction::AShr:
8010 const SCEV *AddTruncateExpr =
nullptr;
8011 ConstantInt *ShlAmtCI =
nullptr;
8012 const SCEV *AddConstant =
nullptr;
8014 if (L &&
L->getOpcode() == Instruction::Add) {
8022 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8029 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8037 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8042 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8047 if (AddTruncateExpr && ShlAmtCI) {
8059 const APInt &ShlAmt = ShlAmtCI->
getValue();
8063 const SCEV *CompositeExpr =
8065 if (
L->getOpcode() != Instruction::Shl)
8066 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8075 switch (
U->getOpcode()) {
8076 case Instruction::Trunc:
8079 case Instruction::ZExt:
8082 case Instruction::SExt:
8091 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8092 Type *Ty =
U->getType();
8100 case Instruction::BitCast:
8106 case Instruction::PtrToAddr: {
8113 case Instruction::PtrToInt:
8117 case Instruction::IntToPtr:
8121 case Instruction::SDiv:
8128 case Instruction::SRem:
8135 case Instruction::GetElementPtr:
8138 case Instruction::PHI:
8141 case Instruction::Select:
8142 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8145 case Instruction::Call:
8146 case Instruction::Invoke:
8151 switch (
II->getIntrinsicID()) {
8152 case Intrinsic::abs:
8156 case Intrinsic::umax:
8160 case Intrinsic::umin:
8164 case Intrinsic::smax:
8168 case Intrinsic::smin:
8172 case Intrinsic::usub_sat: {
8173 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8174 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8178 case Intrinsic::uadd_sat: {
8179 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8180 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8184 case Intrinsic::start_loop_iterations:
8185 case Intrinsic::annotation:
8186 case Intrinsic::ptr_annotation:
8190 case Intrinsic::vscale:
8210 auto *ExitCountType = ExitCount->
getType();
8211 assert(ExitCountType->isIntegerTy());
8213 1 + ExitCountType->getScalarSizeInBits());
8226 auto CanAddOneWithoutOverflow = [&]() {
8228 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8239 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8269 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8270 assert(L->isLoopExiting(ExitingBlock) &&
8271 "Exiting block must actually branch out of the loop!");
8280 const auto *MaxExitCount =
8288 L->getExitingBlocks(ExitingBlocks);
8291 if (ExitingBlocks.
empty() ||
8306 LoopGuards &Guards) {
8310 const SCEV *TCExpr =
8318 : (
unsigned)Multiple.getZExtValue();
8322 const SCEV *ExitCount) {
8345 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8346 assert(L->isLoopExiting(ExitingBlock) &&
8347 "Exiting block must actually branch out of the loop!");
8357 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8359 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8361 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8371 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8374 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8377 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8385 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8392 return getBackedgeTakenInfo(L).getExact(L,
this);
8394 return getBackedgeTakenInfo(L).getConstantMax(
this);
8396 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8403 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8408 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8412 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8422 for (
PHINode &PN : Header->phis())
8423 if (Visited.
insert(&PN).second)
8427ScalarEvolution::BackedgeTakenInfo &
8428ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8429 auto &BTI = getBackedgeTakenInfo(L);
8430 if (BTI.hasFullInfo())
8433 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8436 return Pair.first->second;
8438 BackedgeTakenInfo
Result =
8439 computeBackedgeTakenCount(L,
true);
8441 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8444ScalarEvolution::BackedgeTakenInfo &
8445ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8451 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8452 BackedgeTakenCounts.try_emplace(L);
8454 return Pair.first->second;
8459 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8466 if (
Result.hasAnyInfo()) {
8469 auto LoopUsersIt = LoopUsers.find(L);
8470 if (LoopUsersIt != LoopUsers.end())
8472 forgetMemoizedResults(ToForget);
8475 for (PHINode &PN :
L->getHeader()->phis())
8476 ConstantEvolutionLoopExitValue.erase(&PN);
8484 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8493 BackedgeTakenCounts.clear();
8494 PredicatedBackedgeTakenCounts.clear();
8495 BECountUsers.clear();
8496 LoopPropertiesCache.clear();
8497 ConstantEvolutionLoopExitValue.clear();
8498 ValueExprMap.clear();
8499 ValuesAtScopes.clear();
8500 ValuesAtScopesUsers.clear();
8501 LoopDispositions.clear();
8502 BlockDispositions.clear();
8503 UnsignedRanges.clear();
8504 SignedRanges.clear();
8505 ExprValueMap.clear();
8507 ConstantMultipleCache.clear();
8508 PredicatedSCEVRewrites.clear();
8510 FoldCacheUser.clear();
8512void ScalarEvolution::visitAndClearUsers(
8517 if (ValueExprMap.
empty()) {
8521 while (!Worklist.
empty()) {
8528 if (It != ValueExprMap.
end()) {
8530 eraseValueFromMap(It->first);
8532 ConstantEvolutionLoopExitValue.erase(PN);
8546 while (!LoopWorklist.
empty()) {
8550 forgetBackedgeTakenCounts(CurrL,
false);
8551 forgetBackedgeTakenCounts(CurrL,
true);
8554 PredicatedSCEVRewrites.remove_if(
8555 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8557 auto LoopUsersItr = LoopUsers.find(CurrL);
8558 if (LoopUsersItr != LoopUsers.end())
8563 visitAndClearUsers(Worklist, Visited, ToForget);
8565 LoopPropertiesCache.erase(CurrL);
8568 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8570 forgetMemoizedResults(ToForget);
8587 visitAndClearUsers(Worklist, Visited, ToForget);
8589 forgetMemoizedResults(ToForget);
8600 visitAndClearUsers(Worklist, Visited, ToForget);
8602 forgetMemoizedResults(ToForget);
8610 auto InvalidateValue = [&](
Value *Val) {
8614 struct InvalidationRootCollector {
8618 InvalidationRootCollector(
Loop *L) : L(L) {}
8620 bool follow(
const SCEV *S) {
8626 if (L->contains(AddRec->
getLoop()))
8631 bool isDone()
const {
return false; }
8634 InvalidationRootCollector
C(L);
8636 forgetMemoizedResults(
C.Roots);
8659 BlockDispositions.clear();
8660 LoopDispositions.clear();
8677 while (!Worklist.
empty()) {
8679 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8680 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8681 if (!LoopDispoRemoved && !BlockDispoRemoved)
8683 auto Users = SCEVUsers.find(Curr);
8684 if (
Users != SCEVUsers.end())
8697const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8701 if (!isComplete() || ExitNotTaken.
empty())
8712 for (
const auto &ENT : ExitNotTaken) {
8713 const SCEV *BECount = ENT.ExactNotTaken;
8716 "We should only have known counts for exiting blocks that dominate "
8719 Ops.push_back(BECount);
8724 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8725 "Predicate should be always true!");
8734const ScalarEvolution::ExitNotTakenInfo *
8735ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8736 const BasicBlock *ExitingBlock,
8737 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8738 for (
const auto &ENT : ExitNotTaken)
8739 if (ENT.ExitingBlock == ExitingBlock) {
8740 if (ENT.hasAlwaysTruePredicate())
8742 else if (Predicates) {
8752const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8754 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8755 if (!getConstantMax())
8758 for (
const auto &ENT : ExitNotTaken)
8759 if (!ENT.hasAlwaysTruePredicate()) {
8767 "No point in having a non-constant max backedge taken count!");
8768 return getConstantMax();
8771const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8773 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8781 for (
const auto &ENT : ExitNotTaken) {
8782 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8785 "We should only have known counts for exiting blocks that "
8791 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8792 "Predicate should be always true!");
8795 if (ExitCounts.
empty())
8804bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8806 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8807 return !ENT.hasAlwaysTruePredicate();
8809 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8825 this->ExactNotTaken = E = ConstantMaxNotTaken;
8826 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8831 "Exact is not allowed to be less precise than Constant Max");
8834 "Exact is not allowed to be less precise than Symbolic Max");
8837 "Symbolic Max is not allowed to be less precise than Constant Max");
8840 "No point in having a non-constant max backedge taken count!");
8842 for (
const auto PredList : PredLists)
8843 for (
const auto *
P : PredList) {
8851 "Backedge count should be int");
8854 "Max backedge count should be int");
8867ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
8869 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
8870 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
8871 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8873 ExitNotTaken.reserve(ExitCounts.
size());
8874 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
8875 std::back_inserter(ExitNotTaken),
8876 [&](
const EdgeExitInfo &EEI) {
8877 BasicBlock *ExitBB = EEI.first;
8878 const ExitLimit &EL = EEI.second;
8879 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
8880 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
8885 "No point in having a non-constant max backedge taken count!");
8889ScalarEvolution::BackedgeTakenInfo
8890ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
8891 bool AllowPredicates) {
8893 L->getExitingBlocks(ExitingBlocks);
8895 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8898 bool CouldComputeBECount =
true;
8900 const SCEV *MustExitMaxBECount =
nullptr;
8901 const SCEV *MayExitMaxBECount =
nullptr;
8902 bool MustExitMaxOrZero =
false;
8903 bool IsOnlyExit = ExitingBlocks.
size() == 1;
8914 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
8915 if (ExitIfTrue == CI->
isZero())
8919 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
8921 assert((AllowPredicates || EL.Predicates.empty()) &&
8922 "Predicated exit limit when predicates are not allowed!");
8927 ++NumExitCountsComputed;
8931 CouldComputeBECount =
false;
8938 "Exact is known but symbolic isn't?");
8939 ++NumExitCountsNotComputed;
8954 DT.dominates(ExitBB, Latch)) {
8955 if (!MustExitMaxBECount) {
8956 MustExitMaxBECount = EL.ConstantMaxNotTaken;
8957 MustExitMaxOrZero = EL.MaxOrZero;
8960 EL.ConstantMaxNotTaken);
8964 MayExitMaxBECount = EL.ConstantMaxNotTaken;
8967 EL.ConstantMaxNotTaken);
8971 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
8975 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
8981 for (
const auto &Pair : ExitCounts) {
8983 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
8985 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
8986 {
L, AllowPredicates});
8988 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
8989 MaxBECount, MaxOrZero);
8992ScalarEvolution::ExitLimit
8993ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
8994 bool IsOnlyExit,
bool AllowPredicates) {
8995 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
8999 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9004 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9005 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9006 "It should have one successor in loop and one exit block!");
9017 if (!
L->contains(SBB)) {
9022 assert(Exit &&
"Exiting block must have at least one exit");
9023 return computeExitLimitFromSingleExitSwitch(
9024 L, SI, Exit, IsOnlyExit);
9031 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9032 bool AllowPredicates) {
9033 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9034 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9035 ControlsOnlyExit, AllowPredicates);
9038std::optional<ScalarEvolution::ExitLimit>
9039ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9040 bool ExitIfTrue,
bool ControlsOnlyExit,
9041 bool AllowPredicates) {
9043 (void)this->ExitIfTrue;
9044 (void)this->AllowPredicates;
9046 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9047 this->AllowPredicates == AllowPredicates &&
9048 "Variance in assumed invariant key components!");
9049 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9050 if (Itr == TripCountMap.end())
9051 return std::nullopt;
9055void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9057 bool ControlsOnlyExit,
9058 bool AllowPredicates,
9060 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9061 this->AllowPredicates == AllowPredicates &&
9062 "Variance in assumed invariant key components!");
9064 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9065 assert(InsertResult.second &&
"Expected successful insertion!");
9070ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9071 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9072 bool ControlsOnlyExit,
bool AllowPredicates) {
9074 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9078 ExitLimit EL = computeExitLimitFromCondImpl(
9079 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9080 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9084ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9085 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9086 bool ControlsOnlyExit,
bool AllowPredicates) {
9088 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9089 Cache, L, ExitCond, ExitIfTrue, AllowPredicates))
9090 return *LimitFromBinOp;
9096 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9097 if (EL.hasFullInfo() || !AllowPredicates)
9101 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9121 const WithOverflowInst *WO;
9137 ControlsOnlyExit, AllowPredicates);
9138 if (EL.hasAnyInfo())
9143 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9146std::optional<ScalarEvolution::ExitLimit>
9147ScalarEvolution::computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache,
9151 bool AllowPredicates) {
9160 return std::nullopt;
9164 ExitLimit EL0 = computeExitLimitFromCondCached(
9165 Cache, L, Op0, ExitIfTrue,
false, AllowPredicates);
9166 ExitLimit EL1 = computeExitLimitFromCondCached(
9167 Cache, L, Op1, ExitIfTrue,
false, AllowPredicates);
9172 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9177 if (EitherMayExit) {
9187 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9189 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9192 EL1.ConstantMaxNotTaken);
9194 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9196 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9199 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9203 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9204 BECount = EL0.ExactNotTaken;
9217 SymbolicMaxBECount =
9219 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9223ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9224 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9225 bool AllowPredicates) {
9239 if (EL.hasAnyInfo())
9242 auto *ExhaustiveCount =
9243 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9246 return ExhaustiveCount;
9248 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9251ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9253 bool ControlsOnlyExit,
bool AllowPredicates) {
9278 ConstantRange CompRange =
9296 InnerLHS = ZExt->getOperand();
9343 if (EL.hasAnyInfo())
9360 if (EL.hasAnyInfo())
return EL;
9367 if (!Opts.scalar_evolution_finite_loop || !ControllingFiniteLoop ||
9393 ControlsOnlyExit, AllowPredicates);
9394 if (EL.hasAnyInfo())
9402 if (!Opts.scalar_evolution_finite_loop || !ControllingFiniteLoop ||
9412 ControlsOnlyExit, AllowPredicates);
9413 if (EL.hasAnyInfo())
9424ScalarEvolution::ExitLimit
9425ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9427 BasicBlock *ExitingBlock,
9428 bool ControlsOnlyExit) {
9429 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9432 if (
Switch->getDefaultDest() == ExitingBlock)
9436 "Default case must not exit the loop!");
9442 if (EL.hasAnyInfo())
9454 "Evaluation of SCEV at constant didn't fold correctly?");
9458ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9468 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9475 auto MatchPositiveShift = [](
Value *
V,
Value *&OutLHS,
9477 unsigned &OutShiftAmt) {
9478 using namespace PatternMatch;
9480 ConstantInt *ShiftAmt;
9482 OutOpCode = Instruction::LShr;
9484 OutOpCode = Instruction::AShr;
9486 OutOpCode = Instruction::Shl;
9491 if (Amt == 0 || Amt >= OutLHS->getType()->getScalarSizeInBits())
9506 auto MatchShiftRecurrence = [&](
Value *
V, PHINode *&PNOut,
9508 unsigned &ShiftAmtOut) {
9509 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9525 if (MatchPositiveShift(
LHS,
V, OpC, Amt)) {
9526 PostShiftOpCode = OpC;
9532 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9535 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9541 MatchPositiveShift(BEValue, OpLHS, OpCodeOut, ShiftAmtOut) &&
9548 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9554 if (!MatchShiftRecurrence(
LHS, PN, OpCode, ShiftAmt))
9566 ConstantInt *StableValue =
nullptr;
9571 case Instruction::AShr: {
9578 if (
Known.isNonNegative())
9579 StableValue = ConstantInt::get(Ty, 0);
9580 else if (
Known.isNegative())
9581 StableValue = ConstantInt::get(Ty, -1,
true);
9587 case Instruction::LShr:
9588 case Instruction::Shl:
9598 "Otherwise cannot be an operand to a branch instruction");
9600 if (
Result->isNullValue()) {
9609 if (OpCode == Instruction::LShr || OpCode == Instruction::AShr) {
9611 const SCEV *StartSCEV =
getSCEV(StartValue);
9615 unsigned RangeBTC =
divideCeil(ActiveBits, ShiftAmt);
9616 MaxBTC = std::min(MaxBTC, RangeBTC);
9620 const SCEV *UpperBound =
9638 if (
const Function *
F = CI->getCalledFunction())
9648 if (!L->contains(
I))
return false;
9653 return L->getHeader() ==
I->getParent();
9668 if (
Depth > Opts.scalar_evolution_max_constant_evolving_depth)
9735 if (!
I)
return nullptr;
9749 std::vector<Constant*>
Operands(
I->getNumOperands());
9751 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9760 if (!
C)
return nullptr;
9782 if (IncomingVal != CurrentVal) {
9785 IncomingVal = CurrentVal;
9797ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9800 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9804 if (BEs.
ugt(Opts.scalar_evolution_max_iterations))
9809 DenseMap<Instruction *, Constant *> CurrentIterVals;
9811 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9817 for (PHINode &
PHI : Header->phis()) {
9819 CurrentIterVals[&
PHI] = StartCST;
9821 if (!CurrentIterVals.
count(PN))
9822 return RetVal =
nullptr;
9828 "BEs is <= -scalar-evolution-max-iterations which is an 'unsigned'!");
9831 unsigned IterationNum = 0;
9833 for (; ; ++IterationNum) {
9834 if (IterationNum == NumIterations)
9835 return RetVal = CurrentIterVals[PN];
9839 DenseMap<Instruction *, Constant *> NextIterVals;
9844 NextIterVals[PN] = NextPHI;
9846 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
9852 for (
const auto &
I : CurrentIterVals) {
9854 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
9859 for (
const auto &
I : PHIsToCompute) {
9860 PHINode *
PHI =
I.first;
9863 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9866 if (NextPHI !=
I.second)
9867 StoppedEvolving =
false;
9872 if (StoppedEvolving)
9873 return RetVal = CurrentIterVals[PN];
9875 CurrentIterVals.swap(NextIterVals);
9879const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
9889 DenseMap<Instruction *, Constant *> CurrentIterVals;
9891 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9894 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
9896 for (PHINode &
PHI : Header->phis()) {
9898 CurrentIterVals[&
PHI] = StartCST;
9900 if (!CurrentIterVals.
count(PN))
9906 unsigned MaxIterations =
9907 Opts.scalar_evolution_max_iterations;
9909 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
9916 if (CondVal->getValue() ==
uint64_t(ExitWhen)) {
9917 ++NumBruteForceTripCountsComputed;
9922 DenseMap<Instruction *, Constant *> NextIterVals;
9928 for (
const auto &
I : CurrentIterVals) {
9930 if (!
PHI ||
PHI->getParent() != Header)
continue;
9933 for (PHINode *
PHI : PHIsToCompute) {
9935 if (NextPHI)
continue;
9937 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9940 CurrentIterVals.
swap(NextIterVals);
9951 auto &
Values = ValuesAtScopes[V];
9955 return LS.second ? LS.second :
SCEVUse(V);
9957 Values.emplace_back(L,
nullptr);
9960 SCEVUse C = computeSCEVAtScope(V, L);
9961 for (
auto &LS :
reverse(ValuesAtScopes[V]))
9962 if (LS.first == L) {
9968 ValuesAtScopesUsers[
C.getPointer()].push_back({L, V});
9995 switch (
V->getSCEVType()) {
10028 assert(!
C->getType()->isPointerTy() &&
10029 "Can only have one pointer, and it must be last");
10054const SCEV *ScalarEvolution::getWithOperands(
const SCEV *S,
10055 SmallVectorImpl<SCEVUse> &NewOps) {
10089SCEVUse ScalarEvolution::computeSCEVAtScope(
const SCEV *
V,
const Loop *L) {
10090 switch (
V->getSCEVType()) {
10101 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10112 for (++i; i !=
e; ++i)
10152 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10162 for (++i; i !=
e; ++i) {
10167 return getWithOperands(
V, NewOps);
10182 const Loop *CurrLoop = this->LI[
I->getParent()];
10193 if (BackedgeTakenCount->
isZero()) {
10194 Value *InitValue =
nullptr;
10195 bool MultipleInitValues =
false;
10201 MultipleInitValues =
true;
10206 if (!MultipleInitValues && InitValue)
10215 unsigned InLoopPred =
10226 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10240 SmallVector<Constant *, 4>
Operands;
10242 bool MadeImprovement =
false;
10257 MadeImprovement |= OrigV != OpV;
10262 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10267 if (!MadeImprovement)
10288const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10290 return stripInjectiveFunctions(ZExt->getOperand());
10292 return stripInjectiveFunctions(SExt->getOperand());
10310 assert(
A != 0 &&
"A must be non-zero.");
10326 if (MinTZ < Mult2 && L->getLoopPredecessor())
10328 if (MinTZ < Mult2) {
10351 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10371static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10377 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10378 << *AddRec <<
'\n');
10381 if (!LC || !MC || !
NC) {
10382 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10383 return std::nullopt;
10389 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10397 N =
N.sext(NewWidth);
10398 M = M.sext(NewWidth);
10399 L = L.sext(NewWidth);
10416 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10417 <<
", multiplied by " <<
T <<
'\n');
10426 std::optional<APInt>
Y) {
10428 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10431 return XW.
slt(YW) ? *
X : *
Y;
10434 return std::nullopt;
10435 return X ? *
X : *
Y;
10452 return std::nullopt;
10453 unsigned W =
X->getBitWidth();
10473static std::optional<APInt>
10479 return std::nullopt;
10482 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10483 std::optional<APInt>
X =
10486 return std::nullopt;
10491 return std::nullopt;
10506static std::optional<APInt>
10510 "Starting value of addrec should be 0");
10511 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10512 <<
Range <<
", addrec " << *AddRec <<
'\n');
10516 "Addrec's initial value should be in range");
10522 return std::nullopt;
10532 auto SolveForBoundary =
10533 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10536 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10537 << Bound <<
" (before multiplying by " << M <<
")\n");
10540 std::optional<APInt> SO;
10543 "signed overflow\n");
10547 "unsigned overflow\n");
10548 std::optional<APInt> UO =
10551 auto LeavesRange = [&] (
const APInt &
X) {
10554 if (
Range.contains(V0->getValue()))
10559 if (
Range.contains(
V1->getValue()))
10568 return {std::nullopt,
false};
10573 if (LeavesRange(*Min))
10574 return { Min,
true };
10575 std::optional<APInt> Max = Min == SO ? UO : SO;
10576 if (LeavesRange(*Max))
10577 return { Max,
true };
10580 return {std::nullopt,
true};
10587 auto SL = SolveForBoundary(
Lower);
10588 auto SU = SolveForBoundary(
Upper);
10591 if (!SL.second || !SU.second)
10592 return std::nullopt;
10635ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *
V,
10637 bool ControlsOnlyExit,
10638 bool AllowPredicates) {
10649 if (
C->getValue()->isZero())
return C;
10653 const SCEVAddRecExpr *AddRec =
10656 if (!AddRec && AllowPredicates)
10662 if (!AddRec || AddRec->
getLoop() != L)
10673 return ExitLimit(R, R, R,
false, Predicates);
10731 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10761 const SCEV *
Exact =
10769 const SCEV *SymbolicMax =
10771 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10780 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10788 return ExitLimit(
E, M, S,
false, Predicates);
10791ScalarEvolution::ExitLimit
10792ScalarEvolution::howFarToNonZero(
const SCEV *
V,
const Loop *L) {
10800 if (!
C->getValue()->isZero())
10810std::pair<const BasicBlock *, const BasicBlock *>
10811ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10822 if (
const Loop *L = LI.getLoopFor(BB))
10823 return {
L->getLoopPredecessor(),
L->getHeader()};
10825 return {
nullptr, BB};
10834 if (
A ==
B)
return true;
10849 if (ComputesEqualValues(AI, BI))
10857 const SCEV *Op0, *Op1;
10876 auto TrivialCase = [&](
bool TriviallyTrue) {
10885 const SCEV *NewLHS, *NewRHS;
10909 return TrivialCase(
false);
10910 return TrivialCase(
true);
10929 RAdd->hasNoSignedWrap()) ||
10931 RAdd->hasNoUnsignedWrap())) {
10951 bool BothNUW = LMul->hasNoUnsignedWrap() && RMul->hasNoUnsignedWrap();
10952 bool BothNSW = LMul->hasNoSignedWrap() && RMul->hasNoSignedWrap();
10955 C->getAPInt().isStrictlyPositive()) ||
10979 const APInt &
RA = RC->getAPInt();
10981 bool SimplifiedByConstantRange =
false;
10986 return TrivialCase(
true);
10988 return TrivialCase(
false);
10997 Changed = SimplifiedByConstantRange =
true;
11001 if (!SimplifiedByConstantRange) {
11018 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
11024 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
11030 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
11036 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11056 return TrivialCase(
true);
11058 return TrivialCase(
false);
11163 auto NonRecursive = [OrNegative](
const SCEV *S) {
11165 return C->getAPInt().isPowerOf2() ||
11166 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11172 if (NonRecursive(S))
11182 const SCEV *S, uint64_t M,
11191 APInt C = Cst->getAPInt();
11192 return C.urem(M) == 0;
11198 const SCEV *SmodM =
11219 [&](
SCEVUse Op) { return isKnownMultipleOf(Op, M, Predicates); }))
11226 return isKnownMultipleOf(Op, M, Predicates);
11232 return isKnownMultipleOf(Op, M, Predicates);
11239 for (
auto *
A : *Predicates)
11240 if (
A->implies(
P, *
this))
11253std::pair<const SCEV *, const SCEV *>
11256 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11258 return { Start, Start };
11260 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11269 getUsedLoops(LHS, LoopsUsed);
11270 getUsedLoops(RHS, LoopsUsed);
11272 if (LoopsUsed.
empty())
11277 for (
const auto *L1 : LoopsUsed)
11278 for (
const auto *L2 : LoopsUsed)
11279 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11280 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11281 "Domination relationship is not a linear order");
11311 SplitRHS.second) &&
11321 isKnownPredicateViaSplitting(Pred, LHS, RHS) ||
11322 isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11332 return std::nullopt;
11347 if (KnownWithoutContext)
11348 return KnownWithoutContext;
11355 return std::nullopt;
11361 const Loop *L = LHS->getLoop();
11366std::optional<ScalarEvolution::MonotonicPredicateType>
11369 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11375 auto ResultSwapped =
11378 assert(*ResultSwapped != *Result &&
11379 "monotonicity should flip as we flip the predicate");
11386std::optional<ScalarEvolution::MonotonicPredicateType>
11387ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11401 return std::nullopt;
11405 "Should be greater or less!");
11409 if (!LHS->hasNoUnsignedWrap())
11410 return std::nullopt;
11414 "Relational predicate is either signed or unsigned!");
11415 if (!
LHS->hasNoSignedWrap())
11416 return std::nullopt;
11418 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11426 return std::nullopt;
11429std::optional<ScalarEvolution::LoopInvariantPredicate>
11436 return std::nullopt;
11443 if (!ArLHS || ArLHS->
getLoop() != L)
11444 return std::nullopt;
11449 Pred = Pred.dropSameSign();
11452 return std::nullopt;
11478 return std::nullopt;
11515 return std::nullopt;
11518std::optional<ScalarEvolution::LoopInvariantPredicate>
11523 Pred, LHS, RHS, L, CtxI, MaxIter))
11533 Pred, LHS, RHS, L, CtxI,
Op))
11535 return std::nullopt;
11538std::optional<ScalarEvolution::LoopInvariantPredicate>
11553 return std::nullopt;
11560 if (!AR || AR->
getLoop() != L)
11561 return std::nullopt;
11566 Pred = Pred.dropSameSign();
11570 return std::nullopt;
11576 if (Step != One && Step != MinusOne)
11577 return std::nullopt;
11583 return std::nullopt;
11589 return std::nullopt;
11597 if (Step == MinusOne)
11601 return std::nullopt;
11607bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11613 auto CheckRange = [&](
bool IsSigned) {
11616 return RangeLHS.
icmp(Pred, RangeRHS);
11625 if (CheckRange(
true) || CheckRange(
false))
11634bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate
Pred,
11642 SCEVUse XNonConstOp, XConstOp;
11643 SCEVUse YNonConstOp, YConstOp;
11648 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11649 XConstOp =
nullptr;
11656 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11657 YConstOp =
nullptr;
11662 if (YNonConstOp != XNonConstOp)
11735bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate
Pred,
11756bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate
Pred,
11757 const SCEV *
LHS,
const SCEV *
RHS) {
11762 return any_of(*BB, [&](
const Instruction &
I) {
11763 using namespace llvm::PatternMatch;
11768 isImpliedCond(
Pred,
LHS,
RHS, Condition,
false);
11782 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11785 if (Opts.scev_verify_ir)
11787 "This cannot be done on broken IR!");
11790 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11799 if (LoopContinuePredicate &&
11800 isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->
getCondition(),
11801 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11806 if (WalkingBEDominatingConds)
11812 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11813 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11820 const SCEV *LoopCounter =
11828 for (
auto &AssumeVH : AC.assumptions()) {
11835 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11839 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11842 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11843 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11844 assert(DTN &&
"should reach the loop header before reaching the root!");
11847 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11865 if (isImpliedCond(Pred, LHS, RHS, ContBr->
getCondition(),
11878 if (!DT.isReachableFromEntry(BB))
11880 if (Opts.scev_verify_ir)
11882 "This cannot be done on broken IR!");
11890 const bool ProvingStrictComparison =
11896 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
11898 return isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI);
11904 const Loop *ContainingLoop = LI.getLoopFor(BB);
11906 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
11910 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
11911 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
11914 if (!BlockEntryPredicate)
11923 for (
auto &AssumeVH : AC.assumptions()) {
11927 if (!DT.dominates(CI, BB))
11930 if (ProveViaCond(CI->getArgOperand(0),
false))
11936 F.getParent(), Intrinsic::experimental_guard);
11938 for (
const auto *GU : GuardDecl->users())
11940 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
11941 if (ProveViaCond(Guard->getArgOperand(0),
false))
11946 if (!ProvingStrictComparison)
11949 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS) ||
11950 any_of(Conds, [&](
const auto &
C) {
11951 return isImpliedCond(
P, LHS, RHS,
C.first,
C.second, CtxI);
11967 "LHS is not available at Loop Entry");
11969 "RHS is not available at Loop Entry");
11971 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11982 if (FoundCondValue ==
11986 if (!PendingLoopPredicates.insert(FoundCondValue).second)
11990 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
11993 const Value *Op0, *Op1;
12000 return isImpliedCond(
Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
12001 isImpliedCond(
Pred,
LHS,
RHS, Op1, Inverse, CtxI);
12005 if (!ICI)
return false;
12009 CmpPredicate FoundPred;
12018 return isImpliedCond(
Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
12021bool ScalarEvolution::isImpliedCond(CmpPredicate
Pred,
const SCEV *
LHS,
12022 const SCEV *
RHS, CmpPredicate FoundPred,
12023 const SCEV *FoundLHS,
const SCEV *FoundRHS,
12024 const Instruction *CtxI) {
12034 auto *WideType = FoundLHS->
getType();
12046 TruncFoundLHS, TruncFoundRHS, CtxI))
12072 return isImpliedCondBalancedTypes(
Pred,
LHS,
RHS, FoundPred, FoundLHS,
12076bool ScalarEvolution::isImpliedCondBalancedTypes(
12081 "Types should be balanced!");
12088 if (FoundLHS == FoundRHS)
12092 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12104 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12119 LHS, FoundLHS, FoundRHS, CtxI);
12121 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12133 if (IsSignFlippedPredicate(
Pred, FoundPred) &&
12134 isImpliedCondViaSignFlippedPred(
Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12137 if (IsSignFlippedPredicate(SwappedPred, FoundPred) &&
12138 isImpliedCondViaSignFlippedPred(SwappedPred,
RHS,
LHS, FoundLHS, FoundRHS,
12146 const SCEVConstant *
C =
nullptr;
12147 const SCEV *
V =
nullptr;
12165 if (Min ==
C->getAPInt()) {
12170 APInt SharperMin = Min + 1;
12173 case ICmpInst::ICMP_SGE:
12174 case ICmpInst::ICMP_UGE:
12177 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12182 case ICmpInst::ICMP_SGT:
12183 case ICmpInst::ICMP_UGT:
12193 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12198 case ICmpInst::ICMP_SLE:
12199 case ICmpInst::ICMP_ULE:
12200 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12201 LHS, V, getConstant(SharperMin), CtxI))
12205 case ICmpInst::ICMP_SLT:
12206 case ICmpInst::ICMP_ULT:
12207 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12208 LHS, V, getConstant(Min), CtxI))
12222 if (isImpliedCondOperands(
Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12226 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12229 if (isImpliedCondOperandsViaRanges(
Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12236bool ScalarEvolution::isImpliedCondViaSignFlippedPred(
12237 CmpPredicate
Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12238 const SCEV *FoundRHS,
const Instruction *CtxI) {
12243 return isImpliedCondOperands(
Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12266 CmpPredicate BoundPred =
12268 if (isKnownViaNonRecursiveReasoning(BoundPred, FoundRHS, SignedMin)) {
12271 if (isImpliedCondOperands(
Pred,
LHS,
RHS, Bound, FoundLHS, CtxI))
12279 return isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS);
12285 return isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS);
12299std::optional<APInt>
12306 APInt DiffMul(BW, 1);
12309 for (
unsigned I = 0;
I < 8; ++
I) {
12318 if (LAR->getLoop() != MAR->getLoop())
12319 return std::nullopt;
12323 if (!LAR->isAffine() || !MAR->isAffine())
12324 return std::nullopt;
12326 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12327 return std::nullopt;
12329 Less = LAR->getStart();
12330 More = MAR->getStart();
12335 auto MatchConstMul =
12336 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12341 return std::nullopt;
12343 if (
auto MatchedMore = MatchConstMul(More)) {
12344 if (
auto MatchedLess = MatchConstMul(
Less)) {
12345 if (MatchedMore->second == MatchedLess->second) {
12346 More = MatchedMore->first;
12347 Less = MatchedLess->first;
12348 DiffMul *= MatchedMore->second;
12359 Diff +=
C->getAPInt() * DiffMul;
12362 Diff -=
C->getAPInt() * DiffMul;
12365 Multiplicity[S] +=
Mul;
12367 auto Decompose = [&](
const SCEV *S,
int Mul) {
12374 Decompose(More, 1);
12375 Decompose(
Less, -1);
12379 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12380 for (
const auto &[S,
Mul] : Multiplicity) {
12385 return std::nullopt;
12387 }
else if (
Mul == -1) {
12389 return std::nullopt;
12392 return std::nullopt;
12396 if (NewMore == More || NewLess ==
Less)
12397 return std::nullopt;
12403 if (!More && !
Less)
12407 if (!More || !
Less)
12408 return std::nullopt;
12412 return std::nullopt;
12415bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12437 const auto *Latch = L->getLoopLatch();
12440 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12449 const auto *Latch = L->getLoopLatch();
12452 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12462bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate
Pred,
12465 const SCEV *FoundLHS,
12466 const SCEV *FoundRHS) {
12475 if (!AddRecFoundLHS)
12482 const Loop *
L = AddRecFoundLHS->getLoop();
12483 if (L != AddRecLHS->getLoop())
12522 if (!RDiff || *LDiff != *RDiff)
12525 if (LDiff->isMinValue())
12528 APInt FoundRHSLimit;
12531 FoundRHSLimit = -(*RDiff);
12543bool ScalarEvolution::isImpliedViaMerge(CmpPredicate
Pred,
const SCEV *
LHS,
12544 const SCEV *
RHS,
const SCEV *FoundLHS,
12545 const SCEV *FoundRHS,
unsigned Depth) {
12546 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12550 bool Erased = PendingMerges.erase(LPhi);
12551 assert(Erased &&
"Failed to erase LPhi!");
12555 bool Erased = PendingMerges.erase(RPhi);
12556 assert(Erased &&
"Failed to erase RPhi!");
12564 if (!PendingMerges.insert(Phi).second)
12578 if (!PendingMerges.insert(Phi).second)
12584 if (!LPhi && !RPhi)
12595 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12599 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12600 return isKnownViaNonRecursiveReasoning(
Pred,
S1, S2) ||
12601 isImpliedCondOperandsViaRanges(
Pred,
S1, S2,
Pred, FoundLHS, FoundRHS) ||
12602 isImpliedViaOperations(
Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12605 if (RPhi && RPhi->getParent() == LBB) {
12612 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12613 if (!ProvedEasily(L, R))
12624 auto *RLoop = RAR->
getLoop();
12625 auto *Predecessor = RLoop->getLoopPredecessor();
12626 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12628 if (!ProvedEasily(L1, RAR->
getStart()))
12630 auto *Latch = RLoop->getLoopLatch();
12631 assert(Latch &&
"Loop with AddRec with no latch?");
12652 if (
auto *
Loop = LI.getLoopFor(LBB))
12655 if (!ProvedEasily(L,
RHS))
12662bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate
Pred,
12665 const SCEV *FoundLHS,
12666 const SCEV *FoundRHS) {
12669 if (
RHS == FoundRHS) {
12674 if (
LHS != FoundLHS)
12681 Value *Shiftee, *ShiftValue;
12683 using namespace PatternMatch;
12684 if (
match(SUFoundRHS->getValue(),
12686 auto *ShifteeS =
getSCEV(Shiftee);
12704bool ScalarEvolution::isImpliedCondOperandsViaMatchingDiff(
12705 CmpPredicate
Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12706 const SCEV *FoundRHS) {
12738 const SCEV *FoundDiff =
getMinusSCEV(FoundLHS, FoundRHS);
12746 return Diff == FoundDiff;
12749bool ScalarEvolution::isImpliedCondOperands(CmpPredicate
Pred,
const SCEV *
LHS,
12751 const SCEV *FoundLHS,
12752 const SCEV *FoundRHS,
12753 const Instruction *CtxI) {
12754 return isImpliedCondOperandsViaRanges(
Pred,
LHS,
RHS,
Pred, FoundLHS,
12756 isImpliedCondOperandsViaNoOverflow(
Pred,
LHS,
RHS, FoundLHS,
12758 isImpliedCondOperandsViaShift(
Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12759 isImpliedCondOperandsViaAddRecStart(
Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12761 isImpliedCondOperandsViaMatchingDiff(
Pred,
LHS,
RHS, FoundLHS,
12763 isImpliedCondOperandsHelper(
Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12767template <
typename MinMaxExprType>
12769 const SCEV *Candidate) {
12774 return is_contained(MinMaxExpr->operands(), Candidate);
12787 const SCEV *LStart, *RStart, *Step;
12884bool ScalarEvolution::isImpliedViaOperations(CmpPredicate
Pred,
const SCEV *
LHS,
12886 const SCEV *FoundLHS,
12887 const SCEV *FoundRHS,
12891 "LHS and RHS have different sizes?");
12894 "FoundLHS and FoundRHS have different sizes?");
12896 if (
Depth > Opts.scalar_evolution_max_scev_operations_implication_depth)
12928 auto GetOpFromSExt = [&](
const SCEV *S) ->
const SCEV * {
12930 return Ext->getOperand();
12937 auto *OrigLHS =
LHS;
12938 auto *OrigFoundLHS = FoundLHS;
12939 LHS = GetOpFromSExt(
LHS);
12940 FoundLHS = GetOpFromSExt(FoundLHS);
12943 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
12946 FoundRHS,
Depth + 1);
12963 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
12964 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
12969 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
12975 using namespace llvm::PatternMatch;
12994 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
13002 auto *DTy = Denominator->getType();
13003 auto *FRHSTy = FoundRHS->
getType();
13004 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
13023 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
13034 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
13036 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
13044 if (isImpliedViaMerge(
Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
13077bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate
Pred,
13081 isKnownPredicateViaConstantRanges(
Pred,
LHS,
RHS) ||
13085 isKnownPredicateViaNoOverflow(
Pred,
LHS,
RHS);
13088bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate
Pred,
13091 const SCEV *FoundLHS,
13092 const SCEV *FoundRHS) {
13098 if (isKnownViaNonRecursiveReasoning(NonStrictPred,
LHS, FoundLHS) &&
13099 isKnownViaNonRecursiveReasoning(
13105 return isImpliedViaOperations(
Pred,
LHS,
RHS, FoundLHS, FoundRHS);
13108bool ScalarEvolution::isImpliedCondOperandsViaRanges(
13109 CmpPredicate
Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
13110 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13124 ConstantRange FoundLHSRange =
13128 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13135 return LHSRange.
icmp(
Pred, ConstRHS);
13138bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13139 bool IsSigned,
bool Invert) {
13146 APInt MaxRHS = getRangeMax(
RHS,
true, Invert);
13151 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13154 APInt MaxRHS = getRangeMax(
RHS,
false, Invert);
13159 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13172ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
const SCEV *Stride,
13174 bool IsSigned,
bool Invert) {
13189 APInt MinStart = getRangeMin(Start, IsSigned, Invert);
13202 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13208 APInt MaxEnd = getRangeMax(
End, IsSigned, Invert);
13214 :
APIntOps::umax(MaxEnd, MinStart);
13216 APInt Delta = MaxEnd - MinStart;
13220 const SCEV *DeltaExpr =
13228ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13229 const Loop *L,
bool IsSigned,
bool Invert,
13230 bool ControlsOnlyExit,
bool AllowPredicates) {
13240 bool PredicatedIV =
false;
13242 if (!
IV && !Invert) {
13246 auto canProveNUW = [&]() {
13249 if (!ControlsOnlyExit)
13270 Limit = Limit.
zext(OuterBitWidth);
13282 Type *Ty = ZExt->getType();
13292 if (!
IV && AllowPredicates) {
13297 PredicatedIV =
true;
13301 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13315 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13322 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13325 const SCEV *GuardedStride = Stride;
13329 bool IVMayOverflow =
true;
13333 if (!PositiveStride) {
13336 GuardedStride = LoopGuardedStride;
13337 PositiveStride =
true;
13344 if (!PositiveStride) {
13393 const SCEVPredicate *
P =
13414 auto wouldZeroStrideBeUB = [&]() {
13426 if (!wouldZeroStrideBeUB()) {
13433 IVMayOverflow = canIVOverflowOnLT(
RHS, GuardedStride, IsSigned, Invert) &&
13435 GuardedStride, IsSigned, Invert);
13436 if (IVMayOverflow && !NoWrap)
13449 const SCEV *
Start =
IV->getStart();
13455 const SCEV *OrigStart =
Start;
13456 const SCEV *OrigRHS =
RHS;
13457 if (
Start->getType()->isPointerTy()) {
13471 assert(!Invert &&
"RHS must be loop-invariant for Invert");
13473 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13474 any(RHSAddRec->getNoWrapFlags())) {
13487 const SCEV *RHSStart = RHSAddRec->getStart();
13488 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13500 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13509 BECountIfBackedgeTaken =
13536 bool AddingStrideMinusOneMayOverflow = IVMayOverflow && [&] {
13583 if (!Invert && (Start == Stride || Start ==
getMinusSCEV(Stride, One))) {
13600 auto StepBack = [&](
const SCEV *
V,
const SCEV *
Offset) ->
const SCEV * {
13605 auto Distance = [&](
const SCEV *From,
const SCEV *To) {
13609 const SCEV *OrigPrevStart = StepBack(OrigStart, Stride);
13616 if ((!AddingStrideMinusOneMayOverflow ||
13648 const SCEV *Numerator =
13654 auto canProveRHSIsAtOrBeyondStart = [&]() {
13659 auto SwapIfInverted = [&](
const SCEV *
A,
const SCEV *
B) {
13660 return Invert ? std::pair(
B,
A) : std::pair(
A,
B);
13669 auto [GELHS, GERHS] = SwapIfInverted(OrigRHS, OrigStart);
13674 if ((GuardedRHS != GELHS || GuardedStart != GERHS) &&
13688 auto [GTLHS, GTRHS] = SwapIfInverted(OrigRHS, StepBack(OrigStart, One));
13694 if (canProveRHSIsAtOrBeyondStart()) {
13717 const SCEV *Delta = Distance(Start,
End);
13718 if (!AddingStrideMinusOneMayOverflow) {
13730 const SCEV *ConstantMaxBECount;
13731 bool MaxOrZero =
false;
13733 ConstantMaxBECount = BECount;
13735 ConstantMaxBECount = computeMaxBECountForLT(
13742 const APInt *IfTaken, *RangeMax;
13745 IfTaken->
ugt(*RangeMax)) {
13746 ConstantMaxBECount =
getZero(BECountIfBackedgeTaken->getType());
13748 ConstantMaxBECount = BECountIfBackedgeTaken;
13758 const SCEV *SymbolicMaxBECount =
13760 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13766 if (
Range.isFullSet())
13771 if (!SC->getValue()->isZero()) {
13777 return ShiftedAddRec->getNumIterationsInRange(
13778 Range.subtract(SC->getAPInt()), SE);
13822 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
13823 "Linear scev computation is off in a bad way!");
13854 assert(!
Last->isZero() &&
"Recurrency with zero step?");
13887 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13889 SE->ConstantEvolutionLoopExitValue.erase(PN);
13890 SE->eraseValueFromMap(getValPtr());
13894void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *
V) {
13895 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13905 : CallbackVH(
V), SE(se) {}
13916 ValuesAtScopes(64), LoopDispositions(64), BlockDispositions(64) {
13928 F.getParent(), Intrinsic::experimental_guard);
13929 HasGuards = GuardDecl && !GuardDecl->use_empty();
13933 : Opts(Arg.Opts), F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards),
13934 TLI(Arg.TLI), AC(Arg.AC), DT(Arg.DT), LI(Arg.LI),
13935 CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
13936 ValueExprMap(
std::
move(Arg.ValueExprMap)),
13937 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
13938 PendingMerges(
std::
move(Arg.PendingMerges)),
13939 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
13940 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
13941 PredicatedBackedgeTakenCounts(
13942 std::
move(Arg.PredicatedBackedgeTakenCounts)),
13943 BECountUsers(
std::
move(Arg.BECountUsers)),
13944 ConstantEvolutionLoopExitValue(
13945 std::
move(Arg.ConstantEvolutionLoopExitValue)),
13946 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
13947 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
13948 LoopDispositions(
std::
move(Arg.LoopDispositions)),
13949 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
13950 BlockDispositions(
std::
move(Arg.BlockDispositions)),
13951 SCEVUsers(
std::
move(Arg.SCEVUsers)),
13952 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
13953 SignedRanges(
std::
move(Arg.SignedRanges)),
13954 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
13955 UniquePreds(
std::
move(Arg.UniquePreds)),
13956 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
13957 ConstantSCEVs(
std::
move(Arg.ConstantSCEVs)),
13958 LoopUsers(
std::
move(Arg.LoopUsers)),
13959 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
13960 FirstUnknown(Arg.FirstUnknown),
13961 NextUnknownOrderID(Arg.NextUnknownOrderID) {
13962 Arg.FirstUnknown =
nullptr;
13971 Tmp->~SCEVUnknown();
13973 FirstUnknown =
nullptr;
13975 ExprValueMap.clear();
13976 ValueExprMap.clear();
13978 BackedgeTakenCounts.clear();
13979 PredicatedBackedgeTakenCounts.clear();
13981 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
13982 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
13983 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
13984 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
14006 L->getHeader()->printAsOperand(OS,
false);
14010 L->getExitingBlocks(ExitingBlocks);
14011 if (ExitingBlocks.
size() != 1)
14012 OS <<
"<multiple exits> ";
14016 OS <<
"backedge-taken count is ";
14019 OS <<
"Unpredictable backedge-taken count.";
14022 if (ExitingBlocks.
size() > 1)
14023 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14024 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
14032 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
14035 OS <<
"\n Predicates:\n";
14036 for (
const auto *
P : Predicates)
14044 L->getHeader()->printAsOperand(OS,
false);
14049 OS <<
"constant max backedge-taken count is ";
14052 OS <<
", actual taken count either this or zero.";
14054 OS <<
"Unpredictable constant max backedge-taken count. ";
14059 L->getHeader()->printAsOperand(OS,
false);
14064 OS <<
"symbolic max backedge-taken count is ";
14067 OS <<
", actual taken count either this or zero.";
14069 OS <<
"Unpredictable symbolic max backedge-taken count. ";
14073 if (ExitingBlocks.
size() > 1)
14074 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14075 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
14085 OS <<
"\n predicated symbolic max exit count for "
14086 << ExitingBlock->
getName() <<
": ";
14088 OS <<
"\n Predicates:\n";
14089 for (
const auto *
P : Predicates)
14100 L->getHeader()->printAsOperand(OS,
false);
14103 OS <<
"Predicated backedge-taken count is ";
14106 OS <<
"Unpredictable predicated backedge-taken count.";
14108 OS <<
" Predicates:\n";
14109 for (
const auto *
P : Preds)
14114 auto *PredConstantMax =
14116 if (PredConstantMax != ConstantBTC) {
14118 L->getHeader()->printAsOperand(OS,
false);
14121 OS <<
"Predicated constant max backedge-taken count is ";
14124 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14126 OS <<
" Predicates:\n";
14127 for (
const auto *
P : Preds)
14132 auto *PredSymbolicMax =
14134 if (SymbolicBTC != PredSymbolicMax) {
14136 L->getHeader()->printAsOperand(OS,
false);
14139 OS <<
"Predicated symbolic max backedge-taken count is ";
14142 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14144 OS <<
" Predicates:\n";
14145 for (
const auto *
P : Preds)
14151 L->getHeader()->printAsOperand(OS,
false);
14178 OS <<
"Computable";
14188 OS <<
"DoesNotDominate";
14194 OS <<
"ProperlyDominates";
14210 if (Opts.scalar_evolution_classify_expressions) {
14211 OS <<
"Classifying expressions for: ";
14212 F.printAsOperand(OS,
false);
14227 const Loop *L = LI.getLoopFor(
I.getParent());
14242 OS <<
"\t\t" "Exits: ";
14245 OS <<
"<<Unknown>>";
14251 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14253 Iter->getHeader()->printAsOperand(OS,
false);
14261 InnerL->getHeader()->printAsOperand(OS,
false);
14272 OS <<
"Determining loop execution counts for: ";
14273 F.printAsOperand(OS,
false);
14284 auto &
Values = LoopDispositions[S];
14285 for (
auto &V :
Values) {
14286 if (V.getPointer() == L)
14291 auto &Values2 = LoopDispositions[S];
14293 if (V.getPointer() == L) {
14302ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14320 if (L->contains(AR->
getLoop()) &&
14322 [&](
const SCEV *
Op) { return isLoopUniform(Op, L); }))
14327 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14328 " dominate the contained loop's header?");
14355 bool HasVarying =
false;
14356 bool HasUniform =
false;
14401 auto &
Values = BlockDispositions[S];
14402 for (
auto &V :
Values) {
14403 if (V.getPointer() == BB)
14408 auto &Values2 = BlockDispositions[S];
14410 if (V.getPointer() == BB) {
14419ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14448 bool Proper =
true;
14459 if (Instruction *
I =
14461 if (
I->getParent() == BB)
14463 if (DT.properlyDominates(
I->getParent(), BB))
14482void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14485 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14486 auto It = BECounts.find(L);
14487 if (It != BECounts.end()) {
14488 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14489 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14491 auto UserIt = BECountUsers.find(S);
14492 assert(UserIt != BECountUsers.end());
14497 BECounts.erase(It);
14505 while (!Worklist.
empty()) {
14507 auto Users = SCEVUsers.find(Curr);
14508 if (
Users != SCEVUsers.end())
14509 for (
const auto *User :
Users->second)
14510 if (ToForget.
insert(User).second)
14514 for (
const auto *S : ToForget)
14515 forgetMemoizedResultsImpl(S);
14517 PredicatedSCEVRewrites.remove_if(
14518 [&](
const auto &Entry) {
return ToForget.count(
Entry.first.first); });
14521void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14522 LoopDispositions.erase(S);
14523 BlockDispositions.erase(S);
14524 UnsignedRanges.erase(S);
14525 SignedRanges.erase(S);
14526 HasRecMap.erase(S);
14527 ConstantMultipleCache.erase(S);
14530 UnsignedWrapViaInductionTried.erase(AR);
14531 SignedWrapViaInductionTried.erase(AR);
14534 auto ExprIt = ExprValueMap.find(S);
14535 if (ExprIt != ExprValueMap.end()) {
14536 for (
Value *
V : ExprIt->second) {
14537 auto ValueIt = ValueExprMap.find_as(
V);
14538 if (ValueIt != ValueExprMap.end())
14539 ValueExprMap.erase(ValueIt);
14541 ExprValueMap.erase(ExprIt);
14544 auto ScopeIt = ValuesAtScopes.find(S);
14545 if (ScopeIt != ValuesAtScopes.end()) {
14546 for (
const auto &Pair : ScopeIt->second)
14548 llvm::erase(ValuesAtScopesUsers[Pair.second.getPointer()],
14549 std::make_pair(Pair.first, S));
14550 ValuesAtScopes.erase(ScopeIt);
14553 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14554 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14555 for (
const auto &Pair : ScopeUserIt->second)
14558 llvm::erase_if(ValuesAtScopes[Pair.second], [&](
const auto &LS) {
14559 return LS.first == Pair.first && LS.second.getPointer() == S;
14561 ValuesAtScopesUsers.erase(ScopeUserIt);
14564 auto BEUsersIt = BECountUsers.find(S);
14565 if (BEUsersIt != BECountUsers.end()) {
14567 auto Copy = BEUsersIt->second;
14568 for (
const auto &Pair : Copy)
14569 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14570 BECountUsers.erase(BEUsersIt);
14573 auto FoldUser = FoldCacheUser.find(S);
14574 if (FoldUser != FoldCacheUser.end()) {
14575 for (
auto &KV : FoldUser->second)
14576 FoldCache.erase(KV);
14577 FoldCacheUser.erase(FoldUser);
14582ScalarEvolution::getUsedLoops(
const SCEV *S,
14584 struct FindUsedLoops {
14585 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14586 : LoopsUsed(LoopsUsed) {}
14587 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14588 bool follow(
const SCEV *S) {
14594 bool isDone()
const {
return false; }
14597 FindUsedLoops
F(LoopsUsed);
14598 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14601void ScalarEvolution::getReachableBlocks(
14604 Worklist.
push_back(&F.getEntryBlock());
14605 while (!Worklist.
empty()) {
14607 if (!Reachable.
insert(BB).second)
14615 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14622 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14626 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14661 SCEVMapper SCM(SE2);
14663 SE2.getReachableBlocks(ReachableBlocks, F);
14665 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14683 while (!LoopStack.
empty()) {
14689 if (!ReachableBlocks.
contains(L->getHeader()))
14694 auto It = BackedgeTakenCounts.find(L);
14695 if (It == BackedgeTakenCounts.end())
14699 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14719 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14720 if (Delta && !Delta->
isZero()) {
14721 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14722 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14723 dbgs() <<
"New: " << *NewBECount <<
"\n";
14724 dbgs() <<
"Delta: " << *Delta <<
"\n";
14732 while (!Worklist.
empty()) {
14734 if (ValidLoops.
insert(L).second)
14735 Worklist.
append(L->begin(), L->end());
14737 for (
const auto &KV : ValueExprMap) {
14742 "AddRec references invalid loop");
14747 auto It = ExprValueMap.find(KV.second);
14748 if (It == ExprValueMap.end() || !
is_contained(It->second, KV.first)) {
14749 dbgs() <<
"Value " << *KV.first
14750 <<
" is in ValueExprMap but not in ExprValueMap\n";
14755 if (!ReachableBlocks.
contains(
I->getParent()))
14757 const SCEV *OldSCEV = SCM.visit(KV.second);
14759 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14760 if (Delta && !Delta->
isZero()) {
14761 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14762 <<
"Old: " << *OldSCEV <<
"\n"
14763 <<
"New: " << *NewSCEV <<
"\n"
14764 <<
"Delta: " << *Delta <<
"\n";
14770 for (
const auto &KV : ExprValueMap) {
14771 for (
Value *V : KV.second) {
14772 const SCEV *S = ValueExprMap.lookup(V);
14774 dbgs() <<
"Value " << *V
14775 <<
" is in ExprValueMap but not in ValueExprMap\n";
14778 if (S != KV.first) {
14779 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14780 << *KV.first <<
"\n";
14787 for (
const auto &S : UniqueSCEVs) {
14792 auto It = SCEVUsers.find(
Op);
14793 if (It != SCEVUsers.end() && It->second.count(&S))
14795 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14796 <<
" is not being tracked!\n";
14802 for (
const auto &ValueAndVec : ValuesAtScopes) {
14804 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14805 const Loop *L = LoopAndValueAtScope.first;
14806 SCEVUse ValueAtScope = LoopAndValueAtScope.second;
14808 auto It = ValuesAtScopesUsers.find(ValueAtScope.
getPointer());
14809 if (It != ValuesAtScopesUsers.end() &&
14812 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14813 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14819 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14820 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14821 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14822 const Loop *L = LoopAndValue.first;
14823 const SCEV *
Value = LoopAndValue.second;
14825 auto It = ValuesAtScopes.find(
Value);
14828 if (It != ValuesAtScopes.end() &&
any_of(It->second, [&](
const auto &LS) {
14829 return LS.first == L && LS.second.getPointer() == ValueAtScope;
14832 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14833 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14839 auto VerifyBECountUsers = [&](
bool Predicated) {
14841 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14842 for (
const auto &LoopAndBEInfo : BECounts) {
14843 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
14844 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14846 auto UserIt = BECountUsers.find(S);
14847 if (UserIt != BECountUsers.end() &&
14848 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
14850 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
14851 <<
" missing from BECountUsers\n";
14858 VerifyBECountUsers(
false);
14859 VerifyBECountUsers(
true);
14862 for (
auto &[S,
Values] : LoopDispositions) {
14863 for (
auto [
Loop, CachedDisposition] :
Values) {
14865 if (CachedDisposition != RecomputedDisposition) {
14866 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
14867 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
14868 << RecomputedDisposition <<
"\n";
14875 for (
auto &[S,
Values] : BlockDispositions) {
14876 for (
auto [BB, CachedDisposition] :
Values) {
14878 if (CachedDisposition != RecomputedDisposition) {
14879 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
14880 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
14881 <<
", actual " << RecomputedDisposition <<
"\n";
14888 for (
auto [
FoldID, Expr] : FoldCache) {
14889 auto I = FoldCacheUser.find(Expr);
14890 if (
I == FoldCacheUser.end()) {
14891 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
14896 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
14900 for (
auto [Expr, IDs] : FoldCacheUser) {
14901 for (
auto &
FoldID : IDs) {
14904 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
14909 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
14910 <<
" != " << *Expr <<
"!\n";
14921 for (
auto [S, Multiple] : ConstantMultipleCache) {
14923 if ((Multiple != 0 && RecomputedMultiple != 0 &&
14924 Multiple.
urem(RecomputedMultiple) != 0 &&
14925 RecomputedMultiple.
urem(Multiple) != 0)) {
14926 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
14927 << *S <<
" : Computed " << RecomputedMultiple
14928 <<
" but cache contains " << Multiple <<
"!\n";
14936 FunctionAnalysisManager::Invalidator &Inv) {
14968 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
14969 <<
F.getName() <<
"':\n";
14975 "Scalar Evolution Analysis",
false,
true)
15024 const SCEV *LHS,
const SCEV *RHS) {
15026 assert(LHS->getType() == RHS->getType() &&
15027 "Type mismatch between LHS and RHS");
15030 ID.AddInteger(Pred);
15031 ID.AddPointer(LHS);
15032 ID.AddPointer(RHS);
15034 if (
const auto *S = UniquePreds.lookup(ID, Token))
15038 UniquePreds.insert(Eq, Token);
15049 ID.AddInteger(AddedFlags);
15051 if (
const auto *S = UniquePreds.lookup(ID, Token))
15053 auto *OF =
new (SCEVAllocator)
15055 UniquePreds.insert(OF, Token);
15075 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
15076 return Rewriter.visit(S);
15082 for (
const auto *
Pred : U->getPredicates())
15084 if (IPred->getLHS() == Expr &&
15086 return IPred->getRHS();
15088 if (IPred->getLHS() == Expr &&
15089 IPred->getPredicate() == ICmpInst::ICMP_EQ)
15090 return IPred->getRHS();
15093 return convertToAddRecWithPreds(Expr);
15096 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15112 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15129 explicit SCEVPredicateRewriter(
15130 const Loop *L, ScalarEvolution &SE,
15131 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15132 const SCEVPredicate *
Pred)
15133 : SCEVRewriteVisitor(SE), NewPreds(NewPreds),
Pred(
Pred),
L(
L) {}
15135 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15144 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15147 return addOverflowAssumption(
A);
15156 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15160 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15162 if (!PredicatedRewrite)
15164 for (
const auto *
P : PredicatedRewrite->second){
15167 if (L != WP->getExpr()->getLoop())
15170 if (!addOverflowAssumption(
P))
15173 return PredicatedRewrite->first;
15176 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15177 const SCEVPredicate *
Pred;
15186 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15193 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15213 if (!Step->
isOne())
15238 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15239 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15249 if (
Op->LHS != LHS ||
Op->RHS != RHS)
15259 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15261 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15286 const SCEV *Start = AR->getStart();
15287 const SCEV *OpStart =
Op->AR->getStart();
15292 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15301 const SCEV *Step = AR->getStepRecurrence(SE);
15302 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15323 SCEVFlags ScevFlags = AR->getNoWrapFlags();
15345 for (
const auto *
P : Preds)
15358 return this->implies(I, SE);
15370 const Loop *L = NWrap->getExpr()->getLoop();
15377 return RewrittenAR &&
15383 for (
const auto *Pred : Preds)
15384 Pred->print(OS,
Depth);
15389 for (
const auto *Pred : Set->Preds)
15397 bool CheckImplies = Preds.
size() < 16;
15400 if (CheckImplies &&
implies(
N, SE))
15406 for (
auto *
P : Preds) {
15407 if (CheckImplies &&
N->implies(
P, SE))
15411 Preds = std::move(PrunedPreds);
15412 Preds.push_back(
N);
15419 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15428 SCEVUsers[
Op].insert(
User);
15432 const SCEV *Expr = SE.getSCEV(V);
15437 RewriteEntry &Entry = RewriteMap[Expr];
15440 if (Entry.second && Generation == Entry.first)
15441 return Entry.second;
15446 Expr = Entry.second;
15448 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15449 Entry = {Generation, NewSCEV};
15455 if (!BackedgeCount) {
15457 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15458 for (
const auto *
P : Preds)
15461 return BackedgeCount;
15465 if (!SymbolicMaxBackedgeCount) {
15467 SymbolicMaxBackedgeCount =
15468 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15469 for (
const auto *
P : Preds)
15472 return SymbolicMaxBackedgeCount;
15476 if (!SmallConstantMaxTripCount) {
15478 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15479 for (
const auto *
P : Preds)
15482 return *SmallConstantMaxTripCount;
15486 if (Preds->implies(&Pred, SE))
15489 Preds = std::make_unique<SCEVUnionPredicate>(Preds->getUnionWith(&Pred, SE));
15490 updateGeneration();
15503void PredicatedScalarEvolution::updateGeneration() {
15505 if (++Generation == 0) {
15506 for (
auto &
II : RewriteMap) {
15507 const SCEV *Rewritten =
II.second.second;
15517 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15523 ExtraPreds->
append(NewPreds);
15529 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15535 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15537 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {}
15541 for (
auto *BB : L.getBlocks())
15542 for (
auto &
I : *BB) {
15543 if (!SE.isSCEVable(
I.getType()))
15546 auto *Expr = SE.getSCEV(&
I);
15547 auto II = RewriteMap.find(Expr);
15549 if (
II == RewriteMap.end())
15553 if (
II->second.second == Expr)
15558 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15562void ScalarEvolution::LoopGuards::collectPending() {
15563 const Loop *L = PendingLoop;
15566 PendingLoop =
nullptr;
15571 collectFromBlock(SE, *
this, L->getHeader(), Pred,
VisitedBlocks);
15574void ScalarEvolution::LoopGuards::collectFromPHI(
15582 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15583 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15597 auto &RewriteMap =
G->second.RewriteMap;
15598 if (RewriteMap.empty())
15600 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15601 if (S == RewriteMap.end())
15607 return {
C0, SM->getSCEVType()};
15610 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15611 MinMaxPattern
P2) -> MinMaxPattern {
15613 auto [C2, T2] =
P2;
15614 if (!
C1 || !C2 ||
T1 != T2)
15618 return {
C1->getAPInt().ult(C2->getAPInt()) ?
C1 : C2,
T1};
15620 return {
C1->getAPInt().slt(C2->getAPInt()) ?
C1 : C2,
T1};
15622 return {
C1->getAPInt().ugt(C2->getAPInt()) ?
C1 : C2,
T1};
15624 return {
C1->getAPInt().sgt(C2->getAPInt()) ?
C1 : C2,
T1};
15629 auto P = GetMinMaxConst(0);
15630 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15633 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15636 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15639 Guards.RewriteMap.insert({
LHS,
RHS});
15647 const APInt &DivisorVal,
15649 const APInt *ExprVal;
15662 const APInt &DivisorVal,
15664 const APInt *ExprVal;
15672 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15686 const SCEV *URemRHS =
nullptr;
15690 const SCEV *Multiple =
15692 DivInfo[URemLHS] = Multiple;
15694 Multiples[URemLHS] =
C->getAPInt();
15709 const APInt &Divisor,
15716 C->getAPInt().isNegative())
15726void ScalarEvolution::LoopGuards::collectFromBlock(
15728 const BasicBlock *
Block,
const BasicBlock *
Pred,
15736 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
15747 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15749 if (From == FromRewritten)
15751 RewriteMap[From] = To;
15757 auto GetMaybeRewritten = [&](
const SCEV *S) {
15758 return RewriteMap.lookup_or(S, S);
15765 const SCEV *MatchLHS,
15766 const SCEV *MatchRHS) {
15767 const SCEVConstant *
C1;
15770 if (!
match(MatchLHS,
15777 .
sub(
C1->getAPInt());
15782 const SCEV *RewrittenLHS = GetMaybeRewritten(LHSUnknown);
15783 ExactRegion = ExactRegion.intersectWith(SE.
getUnsignedRange(RewrittenLHS),
15788 if (ExactRegion.isEmptySet() || ExactRegion.isWrappedSet() ||
15789 ExactRegion.isFullSet())
15792 const SCEV *RegionMin = SE.
getConstant(ExactRegion.getUnsignedMin());
15793 const SCEV *RegionMax = SE.
getConstant(ExactRegion.getUnsignedMax());
15794 const SCEV *ClampedLHS =
15796 AddRewrite(LHSUnknown, RewrittenLHS, ClampedLHS);
15799 if (MatchRangeCheckIdiom(Predicate,
LHS,
RHS))
15812 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
15814 const APInt &DividesBy =
15829 switch (Predicate) {
15858 SmallPtrSet<const SCEV *, 16> Visited;
15860 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
15864 while (!Worklist.
empty()) {
15868 if (!Visited.
insert(From).second)
15870 const SCEV *FromRewritten = GetMaybeRewritten(From);
15871 const SCEV *To =
nullptr;
15873 switch (Predicate) {
15878 EnqueueOperands(
UMax);
15884 EnqueueOperands(
SMax);
15890 EnqueueOperands(
UMin);
15897 const APInt *
C, *RHSC;
15899 match(FromRewritten,
15902 FromRewritten = From;
15905 EnqueueOperands(
SMin);
15914 const SCEV *OneAlignedUp =
15916 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
15928 const SCEVConstant *
C;
15937 Guards.NotEqual.insert({
LHS,
RHS});
15946 AddRewrite(From, FromRewritten, To);
15963 SE.F.
getParent(), Intrinsic::experimental_guard);
15965 for (
const auto *GU : GuardDecl->users())
15967 if (Guard->getFunction() ==
Block->getParent() &&
15977 unsigned NumCollectedConditions = 0;
15978 unsigned NumDomTreeSteps = 0;
15980 std::pair<const BasicBlock *, const BasicBlock *> Pair(
Pred,
Block);
15981 for (;; Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
15985 if (!NumDomTreeSteps &&
15986 Depth < SE.Opts.scalar_evolution_max_loop_guard_collection_depth) {
15987 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
15988 for (
auto &Phi : Pair.second->phis())
15993 ++NumDomTreeSteps > SE.Opts.scalar_evolution_max_guard_dom_tree_steps)
15999 const CondBrInst *LoopEntryPredicate =
16001 if (!LoopEntryPredicate)
16006 NumCollectedConditions++;
16010 if (
Depth > 0 && NumCollectedConditions == 2)
16021 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
16022 SmallVector<Value *, 8> Worklist;
16023 SmallPtrSet<Value *, 8> Visited;
16025 while (!Worklist.
empty()) {
16032 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
16056 DenseMap<const SCEV *, APInt> Multiples;
16058 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
16065 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
16066 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
16070 for (
const auto &[K, Divisor] : Multiples) {
16071 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
16072 Guards.RewriteMap[
K] =
16074 Guards.rewrite(K), Divisor, SE),
16083 Guards.PreserveNUW =
true;
16084 Guards.PreserveNSW =
true;
16085 for (
const SCEV *Expr : ExprsToRewrite) {
16086 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16087 Guards.PreserveNUW &=
16089 Guards.PreserveNSW &=
16098 if (ExprsToRewrite.size() > 1) {
16099 constexpr unsigned MaxDepth = 16;
16100 unsigned Depth = 0;
16101 SmallPtrSet<const SCEV *, 16> ToRewrite(
llvm::from_range, ExprsToRewrite);
16102 std::function<
const SCEV *(
const SCEV *)>
Lookup = [&](
const SCEV *Expr) {
16103 if (
Depth < MaxDepth && ToRewrite.erase(Expr)) {
16104 auto It = Guards.RewriteMap.find(Expr);
16105 assert(It != Guards.RewriteMap.end() &&
"Expected rewrite entry");
16106 const SCEV *RewriteTo = It->second;
16107 Guards.RewriteMap.erase(It);
16109 const SCEV *Rewritten = Guards.rewrite(RewriteTo,
Lookup);
16110 Guards.RewriteMap[Expr] = Rewritten;
16113 return Guards.RewriteMap.lookup(Expr);
16115 for (
const SCEV *Expr : ExprsToRewrite)
16120const SCEV *ScalarEvolution::LoopGuards::rewrite(
const SCEV *Expr)
const {
16121 return rewrite(Expr,
nullptr);
16124const SCEV *ScalarEvolution::LoopGuards::rewrite(
16129 class SCEVLoopGuardRewriter
16147 if (Guards.PreserveNUW)
16149 if (Guards.PreserveNSW)
16162 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
return Expr; }
16164 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
16170 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16171 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16174 if (
const SCEV *S =
lookup(NarrowExt))
16176 Bitwidth = Bitwidth / 2;
16182 const SCEV *visitAddExpr(
const SCEVAddExpr *Expr) {
16185 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16190 if (NotEqual.
contains({LHS, RHS})) {
16200 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16211 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16224 const SCEV *S =
nullptr;
16251 const SCEV *visitMulExpr(
const SCEVMulExpr *Expr) {
16267 if (RewriteMap.empty() && NotEqual.
empty())
16285 if (Guards.PendingLoop)
16286 Guards.collectPending();
16287 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 * applyDivisibilityOnMinMaxExpr(const SCEV *MinMaxExpr, const APInt &Divisor, ScalarEvolution &SE)
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 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 * visit(const SCEV *S)
const SCEV * visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr)
SCEVRewriteVisitor(ScalarEvolution &SE)
This class represents a signed minimum selection.
This node is the base class for sequential/in-order min/max selections.
static SCEVTypes getEquivalentNonSequentialSCEVType(SCEVTypes Ty)
This class represents a sign extension of a small integer value to a larger integer value.
Visit all nodes in the expression tree using worklist traversal.
This class represents a truncation of an integer value to a smaller integer value.
This class represents a binary unsigned division operation.
This class represents an unsigned minimum selection.
This class represents a composition of other SCEV predicates, and is the class that most clients will...
void print(raw_ostream &OS, unsigned Depth) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Returns true if this predicate implies N.
SCEVUnionPredicate(ArrayRef< const SCEVPredicate * > Preds, ScalarEvolution &SE)
Union predicates don't get cached so create a dummy set ID for it.
bool isAlwaysTrue() const override
Implementation of the SCEVPredicate interface.
SCEVUnionPredicate getUnionWith(const SCEVPredicate *N, ScalarEvolution &SE) const
Returns a new SCEVUnionPredicate that is the union of this predicate and the given predicate N.
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
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.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
static LLVM_ABI IntegerType * getIntNTy(LLVMContext &C, unsigned N)
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< user_iterator > users()
unsigned getValueID() const
Return an ID for the concrete type of this object.
LLVM_ABI void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
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.
SCEVBinaryExpr_match< SCEVMinMaxExpr, Op0_t, Op1_t > m_scev_MinMax(const Op0_t &Op0, const Op1_t &Op1)
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