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!");
3629 const Loop *NestedLoop = NestedAR->getLoop();
3630 if (L->contains(NestedLoop)
3633 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3635 Operands[0] = NestedAR->getStart();
3639 bool AllInvariant =
all_of(
3651 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3662 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3673 "Tried to add SCEVUse flags after operands changed");
3674 return {getOrCreateAddRecExpr(
Operands, L, ExprFlags), UseFlags};
3691 if (!GEPI || !isSCEVExprNeverPoison(GEPI)) {
3693 }
else if (
any_of(IndexExprs, [&](
const SCEVUse &IndexExpr) {
3694 const SCEV *Idx = IndexExpr;
3696 !isGuaranteedToTransferExecutionTo(
3697 getDefiningScopeBound({Idx}), GEPI);
3707 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), BaseNW,
3724 bool FirstIter =
true;
3726 for (
SCEVUse IndexExpr : IndexExprs) {
3733 Offsets.push_back(FieldOffset);
3736 CurTy = STy->getTypeAtIndex(Index);
3741 "The first index of a GEP indexes a pointer");
3742 CurTy = SrcElementTy;
3753 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3754 Offsets.push_back(LocalOffset);
3759 if (Offsets.empty())
3772 "GEP should not change type mid-flight.");
3776SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3780 "L must be passed to find existing AddRecs");
3784 ID.AddPointer(
Op.getOpaqueValue());
3788 return UniqueSCEVs.lookup(ID, Token);
3798 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
3799 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3800 if (
Ops.size() == 1)
return Ops[0];
3803 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
3805 "Operand types don't match!");
3808 "min/max should be consistently pointerish");
3816 Opts, *
this, LI, DT,
Ops,
3834 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3836 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3841 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
3843 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
3849 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
3855 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
3860 if (Idx <
Ops.size()) {
3861 bool DeletedAny =
false;
3862 while (
Ops[Idx]->getSCEVType() == Kind) {
3864 Ops.erase(
Ops.begin()+Idx);
3882 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
3884 Ops[i] =
Ops[i + 1] = Common;
3885 if (
Ops[i] ==
Ops[i + 1] ||
3886 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
3889 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
3892 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
3895 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
3901 if (
Ops.size() == 1)
return Ops[0];
3903 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
3910 ID.AddPointer(
Op.getOpaqueValue());
3912 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
3914 return ExistingSCEV;
3917 SCEV *S =
new (SCEVAllocator)
3920 UniqueSCEVs.insert(S, Token);
3928class SCEVSequentialMinMaxDeduplicatingVisitor final
3929 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
3930 std::optional<const SCEV *>> {
3931 using RetVal = std::optional<const SCEV *>;
3938 bool canRecurseInto(
SCEVTypes Kind)
const {
3941 return RootKind == Kind || NonSequentialRootKind == Kind;
3946 if (!SeenOps.
insert(S).second)
3947 return std::nullopt;
3951 if (!canRecurseInto(Kind))
3961 return std::nullopt;
3971 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
3973 : SE(SE), RootKind(RootKind),
3974 NonSequentialRootKind(
3975 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
3979 SmallVectorImpl<SCEVUse> &NewOps) {
3984 for (
const SCEV *
Op : OrigOps) {
3989 Ops.emplace_back(*NewOp);
3993 NewOps = std::move(
Ops);
4037struct SCEVPoisonCollector {
4038 bool LookThroughMaybePoisonBlocking;
4039 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4040 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4041 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4043 bool follow(
const SCEV *S) {
4044 if (!LookThroughMaybePoisonBlocking &&
4054 bool isDone()
const {
return false; }
4064 SCEVPoisonCollector PC1(
true);
4069 if (PC1.MaybePoison.
empty())
4075 SCEVPoisonCollector PC2(
false);
4085 SCEVPoisonCollector PC(
false);
4108 unsigned NumVisitedInsts = 0;
4110 while (!Worklist.
empty()) {
4112 if (!Visited.
insert(V).second)
4121 if (++NumVisitedInsts > InstLimit)
4132 if (PDI->isDisjoint())
4139 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4146 if (
I->hasPoisonGeneratingAnnotations())
4157 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4158 "Not a SCEVSequentialMinMaxExpr!");
4159 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4160 if (
Ops.size() == 1)
4164 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4166 "Operand types don't match!");
4169 "min/max should be consistently pointerish");
4177 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4184 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4194 bool DeletedAny =
false;
4195 while (Idx <
Ops.size()) {
4196 if (
Ops[Idx]->getSCEVType() != Kind) {
4201 Ops.erase(
Ops.begin() + Idx);
4202 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4203 SMME->operands().end());
4211 const SCEV *SaturationPoint;
4222 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4235 Ops.erase(
Ops.begin() + i);
4240 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4241 Ops.erase(
Ops.begin() + i);
4251 ID.AddPointer(
Op.getOpaqueValue());
4253 const SCEV *ExistingSCEV = UniqueSCEVs.lookup(ID, Token);
4255 return ExistingSCEV;
4259 SCEV *S =
new (SCEVAllocator)
4262 UniqueSCEVs.insert(S, Token);
4310 if (
Size.isScalable())
4331 "Cannot get offset for structure containing scalable vector types");
4345 if (
SCEV *S = UniqueSCEVs.lookup(ID, Token)) {
4347 "Stale SCEVUnknown in uniquing map!");
4350 SCEV *S =
new (SCEVAllocator)
SCEVUnknown(ID.Intern(SCEVAllocator), V,
this,
4351 FirstUnknown, NextUnknownOrderID++);
4353 UniqueSCEVs.insert(S, Token);
4368 return Ty->isIntOrPtrTy();
4375 if (Ty->isPointerTy())
4386 if (Ty->isIntegerTy())
4390 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4402 bool PreciseA, PreciseB;
4403 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4404 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4405 if (!PreciseA || !PreciseB)
4408 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4409 DT.dominates(ScopeB, ScopeA);
4413 return CouldNotCompute.get();
4416bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4419 return SU && SU->getValue() ==
nullptr;
4422 return !ContainsNulls;
4427 if (
I != HasRecMap.end())
4432 HasRecMap.insert({S, FoundAddRec});
4439 ExprValueMapType::iterator
SI = ExprValueMap.find_as(S);
4440 if (
SI == ExprValueMap.end())
4448void ScalarEvolution::eraseValueFromMap(
Value *V) {
4450 if (
I != ValueExprMap.end()) {
4451 auto EVIt = ExprValueMap.find(
I->second);
4454 ValueExprMap.erase(
I);
4458void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4462 if (ValueExprMap.insert({SCEVCallbackVH(V, this), S}).second)
4463 ExprValueMap[S].push_back(V);
4473 return createSCEVIter(V);
4480 if (
I != ValueExprMap.end()) {
4481 const SCEV *S =
I->second;
4482 assert(checkValidity(S) &&
4483 "existing SCEV has not been properly invalidated");
4495 Type *Ty = V->getType();
4511 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4524 return (
const SCEV *)
nullptr;
4530 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4534 Type *Ty = V->getType();
4540 assert(
P->getType()->isPointerTy());
4555 if (AddOp->getType()->isPointerTy()) {
4556 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4573 return getZero(LHS->getType());
4578 if (RHS->getType()->isPointerTy()) {
4579 if (!LHS->getType()->isPointerTy() ||
4589 const bool RHSIsNotMinSigned =
4620 Type *SrcTy = V->getType();
4621 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4622 "Cannot truncate or zero extend with non-integer arguments!");
4632 Type *SrcTy = V->getType();
4633 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4634 "Cannot truncate or zero extend with non-integer arguments!");
4643 Type *SrcTy = V->getType();
4644 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4645 "Cannot noop or zero extend with non-integer arguments!");
4647 "getNoopOrZeroExtend cannot truncate!");
4654 Type *SrcTy = V->getType();
4655 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4656 "Cannot noop or sign extend with non-integer arguments!");
4658 "getNoopOrSignExtend cannot truncate!");
4665 Type *SrcTy = V->getType();
4666 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4667 "Cannot noop or any extend with non-integer arguments!");
4669 "getNoopOrAnyExtend cannot truncate!");
4676 Type *SrcTy = V->getType();
4677 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4678 "Cannot truncate or noop with non-integer arguments!");
4680 "getTruncateOrNoop cannot extend!");
4688 const SCEV *PromotedLHS = LHS;
4689 const SCEV *PromotedRHS = RHS;
4709 assert(!
Ops.empty() &&
"At least one operand must be!");
4711 if (
Ops.size() == 1)
4715 Type *MaxType =
nullptr;
4721 assert(MaxType &&
"Failed to find maximum type!");
4734 if (!V->getType()->isPointerTy())
4739 V = AddRec->getStart();
4741 const SCEV *PtrOp =
nullptr;
4742 for (
const SCEV *AddOp :
Add->operands()) {
4743 if (AddOp->getType()->isPointerTy()) {
4744 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4748 assert(PtrOp &&
"Must have pointer op");
4760 for (
User *U :
I->users()) {
4762 if (Visited.
insert(UserInsn).second)
4776 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
4777 bool IgnoreOtherLoops =
true) {
4780 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
4782 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
4787 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4789 SeenLoopVariantSCEVUnknown =
true;
4793 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4797 SeenOtherLoops =
true;
4801 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4803 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4806 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
4807 : SCEVRewriteVisitor(SE),
L(
L) {}
4810 bool SeenLoopVariantSCEVUnknown =
false;
4811 bool SeenOtherLoops =
false;
4820 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
4821 SCEVPostIncRewriter
Rewriter(L, SE);
4823 return Rewriter.hasSeenLoopVariantSCEVUnknown()
4828 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4830 SeenLoopVariantSCEVUnknown =
true;
4834 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4838 SeenOtherLoops =
true;
4842 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
4844 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
4847 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
4848 : SCEVRewriteVisitor(SE),
L(
L) {}
4851 bool SeenLoopVariantSCEVUnknown =
false;
4852 bool SeenOtherLoops =
false;
4858class SCEVBackedgeConditionFolder
4861 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4862 ScalarEvolution &SE) {
4863 bool IsPosBECond =
false;
4864 Value *BECond =
nullptr;
4865 if (BasicBlock *Latch =
L->getLoopLatch()) {
4867 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
4868 "Both outgoing branches should not target same header!");
4869 BECond = BI->getCondition();
4870 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
4875 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
4879 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4880 const SCEV *
Result = Expr;
4885 switch (
I->getOpcode()) {
4886 case Instruction::Select: {
4888 std::optional<const SCEV *> Res =
4889 compareWithBackedgeCondition(
SI->getCondition());
4897 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
4908 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
4909 bool IsPosBECond, ScalarEvolution &SE)
4910 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
4911 IsPositiveBECond(IsPosBECond) {}
4913 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
4917 Value *BackedgeCond =
nullptr;
4919 bool IsPositiveBECond;
4922std::optional<const SCEV *>
4923SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
4928 if (BackedgeCond == IC)
4931 return std::nullopt;
4936 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
4937 ScalarEvolution &SE) {
4943 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
4950 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
4960 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
4961 : SCEVRewriteVisitor(SE),
L(
L) {}
4969void ScalarEvolution::inferNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
4985 const APInt &BECountAP = BECountMax->getAPInt();
4986 unsigned NoOverflowBitWidth =
4995ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5005 if (!SignedWrapViaInductionTried.insert(AR).second)
5030 AC.assumptions().empty())
5038 const SCEV *OverflowLimit =
5040 if (OverflowLimit &&
5048ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5058 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5083 AC.assumptions().empty())
5092 const SCEV *OverflowLimit =
5121 IsNSW = OBO->hasNoSignedWrap();
5122 IsNUW = OBO->hasNoUnsignedWrap();
5128 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5138 return std::nullopt;
5144 switch (
Op->getOpcode()) {
5145 case Instruction::Add:
5146 case Instruction::Sub:
5147 case Instruction::Mul:
5148 case Instruction::UDiv:
5149 case Instruction::URem:
5150 case Instruction::And:
5151 case Instruction::AShr:
5152 case Instruction::Shl:
5155 case Instruction::Or: {
5158 BinaryOp BinOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5168 case Instruction::Xor:
5172 if (RHSC->getValue().isSignMask())
5173 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5175 if (V->getType()->isIntegerTy(1))
5176 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5179 case Instruction::LShr:
5188 if (SA->getValue().ult(
BitWidth)) {
5190 ConstantInt::get(SA->getContext(),
5192 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5197 case Instruction::ExtractValue: {
5199 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5207 bool Signed = WO->isSigned();
5210 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5215 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5226 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5227 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5229 return std::nullopt;
5255 if (
Op == SymbolicPHI)
5260 if (SourceBits != NewBits)
5278 if (!L || L->getHeader() != PN->
getParent())
5336std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5337ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5345 assert(L &&
"Expecting an integer loop header phi");
5350 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5351 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5352 Value *
V = PN->getIncomingValue(i);
5353 if (
L->contains(PN->getIncomingBlock(i))) {
5356 }
else if (BEValueV != V) {
5360 }
else if (!StartValueV) {
5362 }
else if (StartValueV != V) {
5363 StartValueV =
nullptr;
5367 if (!BEValueV || !StartValueV)
5368 return std::nullopt;
5370 const SCEV *BEValue =
getSCEV(BEValueV);
5377 return std::nullopt;
5381 unsigned FoundIndex =
Add->getNumOperands();
5382 Type *TruncTy =
nullptr;
5384 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5387 if (FoundIndex == e) {
5392 if (FoundIndex ==
Add->getNumOperands())
5393 return std::nullopt;
5397 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5398 if (i != FoundIndex)
5399 Ops.push_back(
Add->getOperand(i));
5405 return std::nullopt;
5458 const SCEV *StartVal =
getSCEV(StartValueV);
5459 const SCEV *PHISCEV =
5486 auto getExtendedExpr = [&](
const SCEV *Expr,
5487 bool CreateSignExtend) ->
const SCEV * {
5490 const SCEV *ExtendedExpr =
5493 return ExtendedExpr;
5501 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5502 const SCEV *ExtendedExpr) ->
bool {
5503 return Expr != ExtendedExpr &&
5507 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5508 if (PredIsKnownFalse(StartVal, StartExtended)) {
5510 return std::nullopt;
5515 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5516 if (PredIsKnownFalse(Accum, AccumExtended)) {
5518 return std::nullopt;
5521 auto AppendPredicate = [&](
const SCEV *Expr,
5522 const SCEV *ExtendedExpr) ->
void {
5523 if (Expr != ExtendedExpr &&
5531 AppendPredicate(StartVal, StartExtended);
5532 AppendPredicate(Accum, AccumExtended);
5540 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5541 std::make_pair(NewAR, Predicates);
5543 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5547std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5552 return std::nullopt;
5555 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5556 if (
I != PredicatedSCEVRewrites.end()) {
5557 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5560 if (Rewrite.first == SymbolicPHI)
5561 return std::nullopt;
5565 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5569 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5570 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5575 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5576 return std::nullopt;
5596 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5597 if (Expr1 != Expr2 &&
5598 !AllPreds.
implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5599 !AllPreds.
implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5634const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5636 Value *StartValueV) {
5639 assert(BEValueV && StartValueV);
5641 const SCEV *Accum =
nullptr;
5644 if (BO->Opcode != Instruction::Add)
5647 if (BO->LHS == PN &&
L->isLoopInvariant(BO->RHS))
5649 else if (BO->RHS == PN &&
L->isLoopInvariant(BO->LHS))
5663 if (!
GEP ||
GEP->getPointerOperand() != PN ||
GEP->getNumIndices() != 1)
5666 if (!
L->isLoopInvariant(Idx))
5675 const SCEV *StartVal =
getSCEV(StartValueV);
5676 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5677 insertValueToMap(PN, PHISCEV);
5680 inferNoWrapViaConstantRanges(AR);
5687 "Accum is defined outside L, but is not invariant?");
5688 if (isAddRecNeverPoison(BEInst, L))
5695const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5703 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5709 }
else if (BEValueV != V) {
5713 }
else if (!StartValueV) {
5715 }
else if (StartValueV != V) {
5716 StartValueV =
nullptr;
5720 if (!BEValueV || !StartValueV)
5723 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5724 "PHI node already processed?");
5728 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5733 insertValueToMap(PN, SymbolicName);
5737 const SCEV *BEValue =
getSCEV(BEValueV);
5747 unsigned FoundIndex =
Add->getNumOperands();
5748 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5749 if (
Add->getOperand(i) == SymbolicName)
5750 if (FoundIndex == e) {
5755 if (FoundIndex !=
Add->getNumOperands()) {
5758 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5759 if (i != FoundIndex)
5760 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
5772 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
5779 if (
GEP->getOperand(0) == PN)
5787 const SCEV *StartVal =
getSCEV(StartValueV);
5788 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
5793 forgetMemoizedResults({SymbolicName});
5794 insertValueToMap(PN, PHISCEV);
5797 inferNoWrapViaConstantRanges(AR);
5821 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
5822 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
5825 const SCEV *StartVal =
getSCEV(StartValueV);
5826 if (Start == StartVal) {
5830 forgetMemoizedResults({SymbolicName});
5831 insertValueToMap(PN, Shifted);
5841 eraseValueFromMap(PN);
5856 Use &LeftUse =
Merge->getOperandUse(0);
5857 Use &RightUse =
Merge->getOperandUse(1);
5893 assert(IDom &&
"At least the entry block should dominate PN");
5901const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
5906 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
5923 CommonInst = IncomingInst;
5939ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
5945 const SCEV *CommonSCEV =
getSCEV(CommonInst);
5946 bool SCEVExprsIdentical =
5948 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
5949 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
5952const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
5953 if (
const SCEV *S = createAddRecFromPHI(PN))
5963 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
5966 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
5975 struct FindClosure {
5976 const SCEV *OperandToFind;
5982 bool canRecurseInto(
SCEVTypes Kind)
const {
5985 return RootKind == Kind || NonSequentialRootKind == Kind ||
5990 : OperandToFind(OperandToFind), RootKind(RootKind),
5991 NonSequentialRootKind(
5995 bool follow(
const SCEV *S) {
5996 Found = S == OperandToFind;
5998 return !isDone() && canRecurseInto(S->
getSCEVType());
6001 bool isDone()
const {
return Found; }
6004 FindClosure FC(OperandToFind, RootKind);
6009std::optional<const SCEV *>
6010ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6020 switch (ICI->getPredicate()) {
6034 bool Signed = ICI->isSigned();
6035 const SCEV *LA =
getSCEV(TrueVal);
6043 if (LA == LS &&
RA == RS)
6045 if (LA == RS &&
RA == LS)
6048 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6049 if (
Op->getType()->isPointerTy()) {
6060 LS = CoerceOperand(LS);
6061 RS = CoerceOperand(RS);
6085 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6086 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6100 X = ZExt->getOperand();
6102 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6113 return std::nullopt;
6116static std::optional<const SCEV *>
6118 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6122 "Unexpected operands of a select.");
6134 return std::nullopt;
6149static std::optional<const SCEV *>
6153 return std::nullopt;
6156 const auto *SETrue = SE->
getSCEV(TrueVal);
6157 const auto *SEFalse = SE->
getSCEV(FalseVal);
6161const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6163 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6165 V->getType() ==
TrueVal->getType() &&
6166 "Types of select hands and of the result must match.");
6169 if (!
V->getType()->isIntegerTy(1))
6172 if (std::optional<const SCEV *> S =
6185 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6189 if (std::optional<const SCEV *> S =
6190 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6196 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6202 assert(
GEP->getSourceElementType()->isSized() &&
6203 "GEP source element type must be sized");
6206 for (
Value *Index :
GEP->indices())
6211APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6214 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6217 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6219 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6222 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6240 return GetShiftedByZeros(TZ);
6250 return GetShiftedByZeros(TZ);
6254 if (
M->hasNoUnsignedWrap()) {
6257 for (
const SCEV *Operand :
M->operands().drop_front())
6265 for (
const SCEV *Operand :
M->operands())
6267 return GetShiftedByZeros(TZ);
6272 if (
N->hasNoUnsignedWrap())
6273 return GetGCDMultiple(
N);
6276 for (
const SCEV *Operand :
N->operands().drop_front())
6278 return GetShiftedByZeros(TZ);
6295 CtxI = &*F.getEntryBlock().begin();
6302 .allowEphemerals(
true))
6303 .countMinTrailingZeros();
6304 return GetShiftedByZeros(
Known);
6317 return getConstantMultipleImpl(S, CtxI);
6319 auto I = ConstantMultipleCache.find(S);
6320 if (
I != ConstantMultipleCache.end())
6323 APInt Result = getConstantMultipleImpl(S, CtxI);
6324 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6325 assert(InsertPair.second &&
"Should insert a new key");
6326 return InsertPair.first->second;
6343 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6346 if (std::optional<ConstantRange>
Range = CB->getRange())
6350 if (std::optional<ConstantRange>
Range =
A->getRange())
6353 return std::nullopt;
6360 UnsignedRanges.erase(AddRec);
6361 SignedRanges.erase(AddRec);
6362 ConstantMultipleCache.erase(AddRec);
6367getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6393 Value *Start, *Step;
6400 assert(L && L->getHeader() ==
P->getParent());
6413 case Instruction::AShr:
6414 case Instruction::LShr:
6415 case Instruction::Shl:
6430 KnownStep.getBitWidth() ==
BitWidth);
6433 auto MaxShiftAmt = KnownStep.getMaxValue();
6435 bool Overflow =
false;
6436 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6443 case Instruction::AShr: {
6451 if (KnownStart.isNonNegative())
6454 KnownStart.getMaxValue() + 1);
6455 if (KnownStart.isNegative())
6458 KnownEnd.getMaxValue() + 1);
6461 case Instruction::LShr: {
6470 KnownStart.getMaxValue() + 1);
6472 case Instruction::Shl: {
6476 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6477 return ConstantRange(KnownStart.getMinValue(),
6478 KnownEnd.getMaxValue() + 1);
6503 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6510ScalarEvolution::getRangeRefIter(
const SCEV *S,
6511 ScalarEvolution::RangeSignHint SignHint) {
6512 DenseMap<const SCEV *, ConstantRange> &Cache =
6513 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6516 SmallPtrSet<const SCEV *, 8> Seen;
6520 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6521 if (!Seen.
insert(Expr).second)
6554 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6555 const SCEV *
P = WorkList[
I];
6559 for (
const SCEV *
Op :
P->operands())
6572 if (!WorkList.
empty()) {
6577 getRangeRef(
P, SignHint);
6581 return getRangeRef(S, SignHint, 0);
6584const APInt *ScalarEvolution::getConstantAPIntOrNull(
const SCEV *S) {
6586 return &
C->getAPInt();
6594 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6595 DenseMap<const SCEV *, ConstantRange> &Cache =
6596 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6603 auto I = Cache.
find(S);
6604 if (
I != Cache.
end())
6608 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6612 if (
Depth > Opts.scev_range_iter_threshold)
6613 return getRangeRefIter(S, SignHint);
6616 ConstantRange ConservativeResult(
BitWidth,
true);
6617 using OBO = OverflowingBinaryOperator;
6621 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6625 ConservativeResult =
6632 ConservativeResult = ConstantRange(
6648 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6655 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6662 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6667 return setRange(Cast, SignHint,
X);
6672 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6673 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6675 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6676 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6677 ConservativeResult =
6678 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6680 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6681 unsigned WrapType = OBO::AnyWrap;
6682 if (
Add->hasNoSignedWrap())
6683 WrapType |= OBO::NoSignedWrap;
6684 if (
Add->hasNoUnsignedWrap())
6685 WrapType |= OBO::NoUnsignedWrap;
6687 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6689 return setRange(
Add, SignHint,
6690 ConservativeResult.intersectWith(
X, RangeType));
6694 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6696 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6697 return setRange(
Mul, SignHint,
6698 ConservativeResult.intersectWith(
X, RangeType));
6702 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6703 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6704 return setRange(UDiv, SignHint,
6705 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6713 if (!UnsignedMinValue.
isZero())
6714 ConservativeResult = ConservativeResult.intersectWith(
6715 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6724 bool AllNonNeg =
true;
6725 bool AllNonPos =
true;
6726 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6733 ConservativeResult = ConservativeResult.intersectWith(
6738 ConservativeResult = ConservativeResult.intersectWith(
6747 const SCEV *MaxBEScev =
6761 auto [RangeFromAffine,
Flags] = getRangeForAffineAR(
6763 ConservativeResult =
6764 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
6767 auto RangeFromFactoring = getRangeViaFactoring(
6769 ConservativeResult =
6770 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
6775 if (Opts.scalar_evolution_use_expensive_range_sharpening) {
6776 const SCEV *SymbolicMaxBECount =
6781 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
6782 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
6783 ConservativeResult =
6784 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
6789 return setRange(AddRec, SignHint, std::move(ConservativeResult));
6799 ID = Intrinsic::umax;
6802 ID = Intrinsic::smax;
6806 ID = Intrinsic::umin;
6809 ID = Intrinsic::smin;
6816 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
6817 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
6819 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
6820 return setRange(S, SignHint,
6821 ConservativeResult.intersectWith(
X, RangeType));
6830 ConservativeResult =
6831 ConservativeResult.intersectWith(*MDRange, RangeType);
6836 auto CR = getRangeForUnknownRecurrence(U);
6837 ConservativeResult = ConservativeResult.intersectWith(CR);
6848 if (
U->getType()->isPointerTy()) {
6851 unsigned PtrIdxDiff =
6852 DL.getPointerTypeSizeInBits(
U->getType()) -
BitWidth;
6853 NS = NS > PtrIdxDiff ? NS - PtrIdxDiff : 1;
6858 if (!
Known.Zero.getHiBits(NS).isZero())
6859 Known.Zero.setHighBits(NS);
6860 if (!
Known.One.getHiBits(NS).isZero())
6861 Known.One.setHighBits(NS);
6864 if (
Known.getMinValue() !=
Known.getMaxValue() + 1)
6865 ConservativeResult = ConservativeResult.intersectWith(
6866 ConstantRange(
Known.getMinValue(),
Known.getMaxValue() + 1),
6869 ConservativeResult = ConservativeResult.intersectWith(
6874 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
6878 uint64_t DerefBytes =
V->getPointerDereferenceableBytes(
6879 DL, CanBeNull,
nullptr);
6895 ConservativeResult = ConservativeResult.intersectWith(
6905 return getRangeRef(AR, SignHint,
Depth + 1);
6909 ConstantRange RangeFromOps(
BitWidth,
false);
6911 for (
const auto &
Op :
Phi->operands()) {
6913 RangeFromOps = RangeFromOps.unionWith(OpRange);
6915 if (RangeFromOps.isFullSet())
6918 ConservativeResult =
6919 ConservativeResult.intersectWith(RangeFromOps, RangeType);
6925 if (
II->getIntrinsicID() == Intrinsic::vscale) {
6927 ConservativeResult = ConservativeResult.difference(Disallowed);
6930 return setRange(U, SignHint, std::move(ConservativeResult));
6936 return setRange(S, SignHint, std::move(ConservativeResult));
6944static std::pair<ConstantRange, bool>
6952 if (Step == 0 || MaxBECount == 0)
6953 return {StartRange,
true};
6959 return {ConstantRange::getFull(
BitWidth),
false};
6975 return {ConstantRange::getFull(
BitWidth),
false};
6988 APInt MovedBoundary;
6993 MovedBoundary = StartLower - std::move(
Offset);
6996 MovedBoundary = StartUpper + std::move(
Offset);
7000 MovedBoundary = StartUpper.
uadd_ov(std::move(
Offset), Overflow);
7007 if (StartRange.
contains(MovedBoundary))
7008 return {ConstantRange::getFull(
BitWidth),
false};
7011 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7013 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7021std::pair<ConstantRange, SCEVFlags>
7022ScalarEvolution::getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
7023 const APInt &MaxBECount) {
7027 "mismatched bit widths");
7036 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7041 StepSRange.
getSignedMax(), StartSRange, MaxBECount,
true);
7042 SR = SR.unionWith(SRMax);
7061ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7063 ScalarEvolution::RangeSignHint SignHint) {
7064 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7066 "This only works for non-self-wrapping AddRecs!");
7067 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7071 return ConstantRange::getFull(
BitWidth);
7079 return ConstantRange::getFull(
BitWidth);
7083 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7085 MaxItersWithoutWrap))
7086 return ConstantRange::getFull(
BitWidth);
7107 ConstantRange StartRange = getRangeRef(Start, SignHint);
7108 ConstantRange EndRange = getRangeRef(
End, SignHint);
7109 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7113 return RangeBetween;
7118 return ConstantRange::getFull(
BitWidth);
7121 isKnownPredicateViaConstantRanges(LEPred, Start,
End))
7122 return RangeBetween;
7124 isKnownPredicateViaConstantRanges(GEPred, Start,
End))
7125 return RangeBetween;
7126 return ConstantRange::getFull(
BitWidth);
7131 const APInt &MaxBECount) {
7138 "mismatched bit widths");
7140 struct SelectPattern {
7141 Value *Condition =
nullptr;
7145 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7147 std::optional<unsigned> CastOp;
7161 CastOp = SCast->getSCEVType();
7162 S = SCast->getOperand();
7165 using namespace llvm::PatternMatch;
7172 Condition =
nullptr;
7204 bool isRecognized() {
return Condition !=
nullptr; }
7207 SelectPattern StartPattern(*
this,
BitWidth, Start);
7208 if (!StartPattern.isRecognized())
7209 return ConstantRange::getFull(
BitWidth);
7211 SelectPattern StepPattern(*
this,
BitWidth, Step);
7212 if (!StepPattern.isRecognized())
7213 return ConstantRange::getFull(
BitWidth);
7215 if (StartPattern.Condition != StepPattern.Condition) {
7219 return ConstantRange::getFull(
BitWidth);
7230 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7231 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7232 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7233 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7235 ConstantRange TrueRange =
7236 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount).first;
7237 ConstantRange FalseRange =
7238 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount).first;
7251 PDI && PDI->isDisjoint()) {
7266ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7279 SmallPtrSet<const SCEV *, 16> Visited;
7281 auto pushOp = [&](
const SCEV *S) {
7282 if (!Visited.
insert(S).second)
7285 if (Visited.
size() > 30) {
7296 while (!Worklist.
empty()) {
7298 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7299 if (!Bound || DT.dominates(Bound, DefI))
7306 return Bound ? Bound : &*F.getEntryBlock().begin();
7312 return getDefiningScopeBound(
Ops, Discard);
7315bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7317 if (
A->getParent() ==
B->getParent() &&
7322 auto *BLoop = LI.getLoopFor(
B->getParent());
7323 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7324 BLoop->getLoopPreheader() ==
A->getParent() &&
7326 A->getParent()->end()) &&
7334 SCEVPoisonCollector PC(
true);
7336 return PC.MaybePoison.
empty();
7349bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7366 for (
const Use &
Op :
I->operands()) {
7372 auto *DefI = getDefiningScopeBound(SCEVOps);
7373 return isGuaranteedToTransferExecutionTo(DefI,
I);
7376bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7378 if (isSCEVExprNeverPoison(
I))
7389 auto *ExitingBB =
L->getExitingBlock();
7393 SmallPtrSet<const Value *, 16> KnownPoison;
7402 while (!Worklist.
empty()) {
7405 for (
const Use &U :
Poison->uses()) {
7408 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7412 if (KnownPoison.
insert(PoisonUser).second)
7420ScalarEvolution::LoopProperties
7421ScalarEvolution::getLoopProperties(
const Loop *L) {
7422 using LoopProperties = ScalarEvolution::LoopProperties;
7424 auto Itr = LoopPropertiesCache.find(L);
7425 if (Itr == LoopPropertiesCache.end()) {
7428 return !
SI->isSimple();
7439 if (
I->isDroppable())
7442 return I->mayWriteToMemory();
7445 LoopProperties LP = {
true,
7448 for (
auto *BB :
L->getBlocks())
7449 for (
auto &
I : *BB) {
7451 LP.HasNoAbnormalExits =
false;
7452 if (HasSideEffects(&
I))
7453 LP.HasNoSideEffects =
false;
7454 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7458 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7459 assert(InsertPair.second &&
"We just checked!");
7460 Itr = InsertPair.first;
7473const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7479 Stack.emplace_back(V,
false);
7480 while (!Stack.empty()) {
7481 auto E = Stack.back();
7482 Value *CurV = E.getPointer();
7490 const SCEV *CreatedSCEV =
nullptr;
7493 CreatedSCEV = createSCEV(CurV);
7498 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7502 insertValueToMap(CurV, CreatedSCEV);
7505 Stack.back().setInt(
true);
7508 Stack.emplace_back(
Op,
false);
7525 if (!DT.isReachableFromEntry(
I->getParent()))
7537 switch (BO->Opcode) {
7538 case Instruction::Add:
7539 case Instruction::Mul: {
7546 Ops.push_back(BO->
Op);
7550 Ops.push_back(BO->RHS);
7553 (BO->Opcode == Instruction::Add &&
7554 (NewBO->Opcode != Instruction::Add &&
7555 NewBO->Opcode != Instruction::Sub)) ||
7556 (BO->Opcode == Instruction::Mul &&
7557 NewBO->Opcode != Instruction::Mul)) {
7558 Ops.push_back(BO->LHS);
7563 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7566 Ops.push_back(BO->LHS);
7574 case Instruction::Sub:
7575 case Instruction::UDiv:
7576 case Instruction::URem:
7578 case Instruction::AShr:
7579 case Instruction::Shl:
7580 case Instruction::Xor:
7584 case Instruction::And:
7585 case Instruction::Or:
7589 case Instruction::LShr:
7596 Ops.push_back(BO->LHS);
7597 Ops.push_back(BO->RHS);
7601 switch (
U->getOpcode()) {
7602 case Instruction::Trunc:
7603 case Instruction::ZExt:
7604 case Instruction::SExt:
7605 case Instruction::PtrToAddr:
7606 case Instruction::PtrToInt:
7607 Ops.push_back(
U->getOperand(0));
7610 case Instruction::BitCast:
7612 Ops.push_back(
U->getOperand(0));
7617 case Instruction::SDiv:
7618 case Instruction::SRem:
7619 Ops.push_back(
U->getOperand(0));
7620 Ops.push_back(
U->getOperand(1));
7623 case Instruction::GetElementPtr:
7625 "GEP source element type must be sized");
7629 case Instruction::IntToPtr:
7632 case Instruction::PHI:
7663 Ops.push_back(CondICmp->getOperand(0));
7664 Ops.push_back(CondICmp->getOperand(1));
7684 case Instruction::Select: {
7686 auto CanSimplifyToUnknown = [
this,
U]() {
7704 if (CanSimplifyToUnknown())
7711 case Instruction::Call:
7712 case Instruction::Invoke:
7719 switch (
II->getIntrinsicID()) {
7720 case Intrinsic::abs:
7721 Ops.push_back(
II->getArgOperand(0));
7723 case Intrinsic::umax:
7724 case Intrinsic::umin:
7725 case Intrinsic::smax:
7726 case Intrinsic::smin:
7727 case Intrinsic::usub_sat:
7728 case Intrinsic::uadd_sat:
7729 Ops.push_back(
II->getArgOperand(0));
7730 Ops.push_back(
II->getArgOperand(1));
7732 case Intrinsic::start_loop_iterations:
7733 case Intrinsic::annotation:
7734 case Intrinsic::ptr_annotation:
7735 Ops.push_back(
II->getArgOperand(0));
7747const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7756 if (!DT.isReachableFromEntry(
I->getParent()))
7770 switch (BO->Opcode) {
7771 case Instruction::Add: {
7797 if (BO->Opcode == Instruction::Sub)
7805 if (BO->Opcode == Instruction::Sub)
7811 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
7812 NewBO->Opcode != Instruction::Sub)) {
7822 case Instruction::Mul: {
7842 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
7851 case Instruction::UDiv:
7855 case Instruction::URem:
7859 case Instruction::Sub: {
7862 Flags = getNoWrapFlagsFromUB(BO->
Op);
7867 Value *PtrLHS =
nullptr, *PtrRHS =
nullptr;
7870 if (HasPtrLHS || HasPtrRHS) {
7875 auto GetOp = [&](
bool HasPtr,
Value *PtrOp,
Value *OrigOp,
7876 bool BothPtr) ->
const SCEV * {
7879 const SCEV *PtrSCEV =
getSCEV(PtrOp);
7889 const SCEV *
L = GetOp(HasPtrLHS, PtrLHS, BO->LHS, HasPtrRHS);
7890 const SCEV *
R = GetOp(HasPtrRHS, PtrRHS, BO->RHS, HasPtrLHS);
7898 case Instruction::And:
7904 if (CI->isMinusOne())
7906 const APInt &
A = CI->getValue();
7912 unsigned LZ =
A.countl_zero();
7913 unsigned TZ =
A.countr_zero();
7918 APInt EffectiveMask =
7920 if ((LZ != 0 || TZ != 0) && !((~
A & ~
Known.Zero) & EffectiveMask)) {
7923 const SCEV *ShiftedLHS =
nullptr;
7927 unsigned MulZeros = OpC->getAPInt().countr_zero();
7928 unsigned GCD = std::min(MulZeros, TZ);
7933 const SCEV *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
7955 case Instruction::Or:
7964 case Instruction::Xor:
7967 if (CI->isMinusOne())
7976 if (LBO->getOpcode() == Instruction::And &&
7977 LCI->getValue() == CI->getValue())
7978 if (
const SCEVZeroExtendExpr *Z =
7981 const SCEV *Z0 =
Z->getOperand();
7988 if (CI->getValue().isMask(Z0TySize))
7994 APInt Trunc = CI->getValue().trunc(Z0TySize);
8003 case Instruction::Shl:
8021 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8030 ConstantInt *
X = ConstantInt::get(
8036 case Instruction::AShr:
8058 const SCEV *AddTruncateExpr =
nullptr;
8059 ConstantInt *ShlAmtCI =
nullptr;
8060 const SCEV *AddConstant =
nullptr;
8062 if (L &&
L->getOpcode() == Instruction::Add) {
8070 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8077 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8085 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8090 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8095 if (AddTruncateExpr && ShlAmtCI) {
8107 const APInt &ShlAmt = ShlAmtCI->
getValue();
8111 const SCEV *CompositeExpr =
8113 if (
L->getOpcode() != Instruction::Shl)
8114 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8123 switch (
U->getOpcode()) {
8124 case Instruction::Trunc:
8127 case Instruction::ZExt:
8130 case Instruction::SExt:
8139 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8140 Type *Ty =
U->getType();
8148 case Instruction::BitCast:
8154 case Instruction::PtrToAddr: {
8161 case Instruction::PtrToInt:
8165 case Instruction::IntToPtr:
8169 case Instruction::SDiv:
8176 case Instruction::SRem:
8183 case Instruction::GetElementPtr:
8186 case Instruction::PHI:
8189 case Instruction::Select:
8190 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8193 case Instruction::Call:
8194 case Instruction::Invoke:
8199 switch (
II->getIntrinsicID()) {
8200 case Intrinsic::abs:
8204 case Intrinsic::umax:
8208 case Intrinsic::umin:
8212 case Intrinsic::smax:
8216 case Intrinsic::smin:
8220 case Intrinsic::usub_sat: {
8221 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8222 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8226 case Intrinsic::uadd_sat: {
8227 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8228 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8232 case Intrinsic::start_loop_iterations:
8233 case Intrinsic::annotation:
8234 case Intrinsic::ptr_annotation:
8238 case Intrinsic::vscale:
8258 auto *ExitCountType = ExitCount->
getType();
8259 assert(ExitCountType->isIntegerTy());
8261 1 + ExitCountType->getScalarSizeInBits());
8274 auto CanAddOneWithoutOverflow = [&]() {
8276 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8287 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8317 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8318 assert(L->isLoopExiting(ExitingBlock) &&
8319 "Exiting block must actually branch out of the loop!");
8328 const auto *MaxExitCount =
8336 L->getExitingBlocks(ExitingBlocks);
8339 if (ExitingBlocks.
empty() ||
8354 LoopGuards &Guards) {
8358 const SCEV *TCExpr =
8366 : (
unsigned)Multiple.getZExtValue();
8370 const SCEV *ExitCount) {
8393 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8394 assert(L->isLoopExiting(ExitingBlock) &&
8395 "Exiting block must actually branch out of the loop!");
8405 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8407 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8409 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8419 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8422 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8425 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8433 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8440 return getBackedgeTakenInfo(L).getExact(L,
this);
8442 return getBackedgeTakenInfo(L).getConstantMax(
this);
8444 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8451 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8456 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8460 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8470 for (
PHINode &PN : Header->phis())
8471 if (Visited.
insert(&PN).second)
8475ScalarEvolution::BackedgeTakenInfo &
8476ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8477 auto &BTI = getBackedgeTakenInfo(L);
8478 if (BTI.hasFullInfo())
8481 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8484 return Pair.first->second;
8486 BackedgeTakenInfo
Result =
8487 computeBackedgeTakenCount(L,
true);
8489 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8492ScalarEvolution::BackedgeTakenInfo &
8493ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8499 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8500 BackedgeTakenCounts.try_emplace(L);
8502 return Pair.first->second;
8507 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8514 if (
Result.hasAnyInfo()) {
8517 auto LoopUsersIt = LoopUsers.find(L);
8518 if (LoopUsersIt != LoopUsers.end())
8520 forgetMemoizedResults(ToForget);
8523 for (PHINode &PN :
L->getHeader()->phis())
8524 ConstantEvolutionLoopExitValue.erase(&PN);
8532 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8541 BackedgeTakenCounts.clear();
8542 PredicatedBackedgeTakenCounts.clear();
8543 BECountUsers.clear();
8544 LoopPropertiesCache.clear();
8545 ConstantEvolutionLoopExitValue.clear();
8546 ValueExprMap.clear();
8547 ValuesAtScopes.clear();
8548 ValuesAtScopesUsers.clear();
8549 LoopDispositions.clear();
8550 BlockDispositions.clear();
8551 UnsignedRanges.clear();
8552 SignedRanges.clear();
8553 ExprValueMap.clear();
8555 ConstantMultipleCache.clear();
8556 PredicatedSCEVRewrites.clear();
8558 FoldCacheUser.clear();
8560void ScalarEvolution::visitAndClearUsers(
8565 if (ValueExprMap.
empty()) {
8569 while (!Worklist.
empty()) {
8576 if (It != ValueExprMap.
end()) {
8578 eraseValueFromMap(It->first);
8580 ConstantEvolutionLoopExitValue.erase(PN);
8594 while (!LoopWorklist.
empty()) {
8598 forgetBackedgeTakenCounts(CurrL,
false);
8599 forgetBackedgeTakenCounts(CurrL,
true);
8602 PredicatedSCEVRewrites.remove_if(
8603 [&](
const auto &Entry) {
return Entry.first.second == CurrL; });
8605 auto LoopUsersItr = LoopUsers.find(CurrL);
8606 if (LoopUsersItr != LoopUsers.end())
8611 visitAndClearUsers(Worklist, Visited, ToForget);
8613 LoopPropertiesCache.erase(CurrL);
8616 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8618 forgetMemoizedResults(ToForget);
8635 visitAndClearUsers(Worklist, Visited, ToForget);
8637 forgetMemoizedResults(ToForget);
8648 visitAndClearUsers(Worklist, Visited, ToForget);
8650 forgetMemoizedResults(ToForget);
8658 auto InvalidateValue = [&](
Value *Val) {
8662 struct InvalidationRootCollector {
8666 InvalidationRootCollector(
Loop *L) : L(L) {}
8668 bool follow(
const SCEV *S) {
8674 if (L->contains(AddRec->
getLoop()))
8679 bool isDone()
const {
return false; }
8682 InvalidationRootCollector
C(L);
8684 forgetMemoizedResults(
C.Roots);
8707 BlockDispositions.clear();
8708 LoopDispositions.clear();
8725 while (!Worklist.
empty()) {
8727 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8728 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8729 if (!LoopDispoRemoved && !BlockDispoRemoved)
8731 auto Users = SCEVUsers.find(Curr);
8732 if (
Users != SCEVUsers.end())
8745const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8749 if (!isComplete() || ExitNotTaken.
empty())
8760 for (
const auto &ENT : ExitNotTaken) {
8761 const SCEV *BECount = ENT.ExactNotTaken;
8764 "We should only have known counts for exiting blocks that dominate "
8767 Ops.push_back(BECount);
8772 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8773 "Predicate should be always true!");
8782const ScalarEvolution::ExitNotTakenInfo *
8783ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8784 const BasicBlock *ExitingBlock,
8785 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8786 for (
const auto &ENT : ExitNotTaken)
8787 if (ENT.ExitingBlock == ExitingBlock) {
8788 if (ENT.hasAlwaysTruePredicate())
8790 else if (Predicates) {
8800const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8802 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8803 if (!getConstantMax())
8806 for (
const auto &ENT : ExitNotTaken)
8807 if (!ENT.hasAlwaysTruePredicate()) {
8815 "No point in having a non-constant max backedge taken count!");
8816 return getConstantMax();
8819const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8821 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8829 for (
const auto &ENT : ExitNotTaken) {
8830 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8833 "We should only have known counts for exiting blocks that "
8839 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
8840 "Predicate should be always true!");
8843 if (ExitCounts.
empty())
8852bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
8854 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
8855 return !ENT.hasAlwaysTruePredicate();
8857 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
8873 this->ExactNotTaken = E = ConstantMaxNotTaken;
8874 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
8879 "Exact is not allowed to be less precise than Constant Max");
8882 "Exact is not allowed to be less precise than Symbolic Max");
8885 "Symbolic Max is not allowed to be less precise than Constant Max");
8888 "No point in having a non-constant max backedge taken count!");
8890 for (
const auto PredList : PredLists)
8891 for (
const auto *
P : PredList) {
8899 "Backedge count should be int");
8902 "Max backedge count should be int");
8915ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
8917 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
8918 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
8919 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8921 ExitNotTaken.reserve(ExitCounts.
size());
8922 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
8923 std::back_inserter(ExitNotTaken),
8924 [&](
const EdgeExitInfo &EEI) {
8925 BasicBlock *ExitBB = EEI.first;
8926 const ExitLimit &EL = EEI.second;
8927 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
8928 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
8933 "No point in having a non-constant max backedge taken count!");
8937ScalarEvolution::BackedgeTakenInfo
8938ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
8939 bool AllowPredicates) {
8941 L->getExitingBlocks(ExitingBlocks);
8943 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
8946 bool CouldComputeBECount =
true;
8948 const SCEV *MustExitMaxBECount =
nullptr;
8949 const SCEV *MayExitMaxBECount =
nullptr;
8950 bool MustExitMaxOrZero =
false;
8951 bool IsOnlyExit = ExitingBlocks.
size() == 1;
8962 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
8963 if (ExitIfTrue == CI->
isZero())
8967 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
8969 assert((AllowPredicates || EL.Predicates.empty()) &&
8970 "Predicated exit limit when predicates are not allowed!");
8975 ++NumExitCountsComputed;
8979 CouldComputeBECount =
false;
8986 "Exact is known but symbolic isn't?");
8987 ++NumExitCountsNotComputed;
9002 DT.dominates(ExitBB, Latch)) {
9003 if (!MustExitMaxBECount) {
9004 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9005 MustExitMaxOrZero = EL.MaxOrZero;
9008 EL.ConstantMaxNotTaken);
9012 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9015 EL.ConstantMaxNotTaken);
9019 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9023 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9029 for (
const auto &Pair : ExitCounts) {
9031 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9033 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9034 {
L, AllowPredicates});
9036 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9037 MaxBECount, MaxOrZero);
9040ScalarEvolution::ExitLimit
9041ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9042 bool IsOnlyExit,
bool AllowPredicates) {
9043 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9047 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9052 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9053 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9054 "It should have one successor in loop and one exit block!");
9065 if (!
L->contains(SBB)) {
9070 assert(Exit &&
"Exiting block must have at least one exit");
9071 return computeExitLimitFromSingleExitSwitch(
9072 L, SI, Exit, IsOnlyExit);
9079 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9080 bool AllowPredicates) {
9081 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9082 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9083 ControlsOnlyExit, AllowPredicates);
9086std::optional<ScalarEvolution::ExitLimit>
9087ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9088 bool ExitIfTrue,
bool ControlsOnlyExit,
9089 bool AllowPredicates) {
9091 (void)this->ExitIfTrue;
9092 (void)this->AllowPredicates;
9094 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9095 this->AllowPredicates == AllowPredicates &&
9096 "Variance in assumed invariant key components!");
9097 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9098 if (Itr == TripCountMap.end())
9099 return std::nullopt;
9103void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9105 bool ControlsOnlyExit,
9106 bool AllowPredicates,
9108 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9109 this->AllowPredicates == AllowPredicates &&
9110 "Variance in assumed invariant key components!");
9112 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9113 assert(InsertResult.second &&
"Expected successful insertion!");
9118ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9119 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9120 bool ControlsOnlyExit,
bool AllowPredicates) {
9122 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9126 ExitLimit EL = computeExitLimitFromCondImpl(
9127 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9128 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9132ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9133 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9134 bool ControlsOnlyExit,
bool AllowPredicates) {
9136 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9137 Cache, L, ExitCond, ExitIfTrue, AllowPredicates))
9138 return *LimitFromBinOp;
9144 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9145 if (EL.hasFullInfo() || !AllowPredicates)
9149 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9169 const WithOverflowInst *WO;
9184 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9185 ControlsOnlyExit, AllowPredicates);
9186 if (EL.hasAnyInfo())
9191 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9194std::optional<ScalarEvolution::ExitLimit>
9195ScalarEvolution::computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache,
9199 bool AllowPredicates) {
9208 return std::nullopt;
9212 ExitLimit EL0 = computeExitLimitFromCondCached(
9213 Cache, L, Op0, ExitIfTrue,
false, AllowPredicates);
9214 ExitLimit EL1 = computeExitLimitFromCondCached(
9215 Cache, L, Op1, ExitIfTrue,
false, AllowPredicates);
9220 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9225 if (EitherMayExit) {
9235 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9237 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9240 EL1.ConstantMaxNotTaken);
9242 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9244 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9247 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9251 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9252 BECount = EL0.ExactNotTaken;
9265 SymbolicMaxBECount =
9267 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9271ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9272 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9273 bool AllowPredicates) {
9285 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9287 if (EL.hasAnyInfo())
9290 auto *ExhaustiveCount =
9291 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9294 return ExhaustiveCount;
9296 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9299ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9301 bool ControlsOnlyExit,
bool AllowPredicates) {
9326 ConstantRange CompRange =
9344 InnerLHS = ZExt->getOperand();
9391 if (EL.hasAnyInfo())
9408 if (EL.hasAnyInfo())
return EL;
9415 if (!Opts.scalar_evolution_finite_loop || !ControllingFiniteLoop ||
9441 ControlsOnlyExit, AllowPredicates);
9442 if (EL.hasAnyInfo())
9450 if (!Opts.scalar_evolution_finite_loop || !ControllingFiniteLoop ||
9460 ControlsOnlyExit, AllowPredicates);
9461 if (EL.hasAnyInfo())
9472ScalarEvolution::ExitLimit
9473ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9475 BasicBlock *ExitingBlock,
9476 bool ControlsOnlyExit) {
9477 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9480 if (
Switch->getDefaultDest() == ExitingBlock)
9484 "Default case must not exit the loop!");
9490 if (EL.hasAnyInfo())
9502 "Evaluation of SCEV at constant didn't fold correctly?");
9506ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9516 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9523 auto MatchPositiveShift = [](
Value *
V,
Value *&OutLHS,
9525 unsigned &OutShiftAmt) {
9526 using namespace PatternMatch;
9528 ConstantInt *ShiftAmt;
9530 OutOpCode = Instruction::LShr;
9532 OutOpCode = Instruction::AShr;
9534 OutOpCode = Instruction::Shl;
9539 if (Amt == 0 || Amt >= OutLHS->getType()->getScalarSizeInBits())
9554 auto MatchShiftRecurrence = [&](
Value *
V, PHINode *&PNOut,
9556 unsigned &ShiftAmtOut) {
9557 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9573 if (MatchPositiveShift(
LHS, V, OpC, Amt)) {
9574 PostShiftOpCode = OpC;
9580 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9583 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9589 MatchPositiveShift(BEValue, OpLHS, OpCodeOut, ShiftAmtOut) &&
9596 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9602 if (!MatchShiftRecurrence(
LHS, PN, OpCode, ShiftAmt))
9614 ConstantInt *StableValue =
nullptr;
9619 case Instruction::AShr: {
9626 if (
Known.isNonNegative())
9627 StableValue = ConstantInt::get(Ty, 0);
9628 else if (
Known.isNegative())
9629 StableValue = ConstantInt::get(Ty, -1,
true);
9635 case Instruction::LShr:
9636 case Instruction::Shl:
9646 "Otherwise cannot be an operand to a branch instruction");
9648 if (
Result->isNullValue()) {
9657 if (OpCode == Instruction::LShr || OpCode == Instruction::AShr) {
9659 const SCEV *StartSCEV =
getSCEV(StartValue);
9663 unsigned RangeBTC =
divideCeil(ActiveBits, ShiftAmt);
9664 MaxBTC = std::min(MaxBTC, RangeBTC);
9668 const SCEV *UpperBound =
9686 if (
const Function *
F = CI->getCalledFunction())
9696 if (!L->contains(
I))
return false;
9701 return L->getHeader() ==
I->getParent();
9716 if (
Depth > Opts.scalar_evolution_max_constant_evolving_depth)
9783 if (!
I)
return nullptr;
9797 std::vector<Constant*>
Operands(
I->getNumOperands());
9799 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9808 if (!
C)
return nullptr;
9830 if (IncomingVal != CurrentVal) {
9833 IncomingVal = CurrentVal;
9845ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9848 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9852 if (BEs.
ugt(Opts.scalar_evolution_max_iterations))
9857 DenseMap<Instruction *, Constant *> CurrentIterVals;
9859 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9865 for (PHINode &
PHI : Header->phis()) {
9867 CurrentIterVals[&
PHI] = StartCST;
9869 if (!CurrentIterVals.
count(PN))
9870 return RetVal =
nullptr;
9876 "BEs is <= -scalar-evolution-max-iterations which is an 'unsigned'!");
9879 unsigned IterationNum = 0;
9881 for (; ; ++IterationNum) {
9882 if (IterationNum == NumIterations)
9883 return RetVal = CurrentIterVals[PN];
9887 DenseMap<Instruction *, Constant *> NextIterVals;
9892 NextIterVals[PN] = NextPHI;
9894 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
9900 for (
const auto &
I : CurrentIterVals) {
9902 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
9907 for (
const auto &
I : PHIsToCompute) {
9908 PHINode *
PHI =
I.first;
9911 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9914 if (NextPHI !=
I.second)
9915 StoppedEvolving =
false;
9920 if (StoppedEvolving)
9921 return RetVal = CurrentIterVals[PN];
9923 CurrentIterVals.swap(NextIterVals);
9927const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
9937 DenseMap<Instruction *, Constant *> CurrentIterVals;
9939 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9942 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
9944 for (PHINode &
PHI : Header->phis()) {
9946 CurrentIterVals[&
PHI] = StartCST;
9948 if (!CurrentIterVals.
count(PN))
9954 unsigned MaxIterations =
9955 Opts.scalar_evolution_max_iterations;
9957 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
9964 if (CondVal->getValue() ==
uint64_t(ExitWhen)) {
9965 ++NumBruteForceTripCountsComputed;
9970 DenseMap<Instruction *, Constant *> NextIterVals;
9976 for (
const auto &
I : CurrentIterVals) {
9978 if (!
PHI ||
PHI->getParent() != Header)
continue;
9981 for (PHINode *
PHI : PHIsToCompute) {
9983 if (NextPHI)
continue;
9985 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
9988 CurrentIterVals.
swap(NextIterVals);
9999 auto &
Values = ValuesAtScopes[V];
10003 return LS.second ? LS.second :
SCEVUse(V);
10005 Values.emplace_back(L,
nullptr);
10008 SCEVUse C = computeSCEVAtScope(V, L);
10009 for (
auto &LS :
reverse(ValuesAtScopes[V]))
10010 if (LS.first == L) {
10016 ValuesAtScopesUsers[
C.getPointer()].push_back({L, V});
10043 switch (V->getSCEVType()) {
10076 assert(!
C->getType()->isPointerTy() &&
10077 "Can only have one pointer, and it must be last");
10102const SCEV *ScalarEvolution::getWithOperands(
const SCEV *S,
10103 SmallVectorImpl<SCEVUse> &NewOps) {
10137SCEVUse ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10138 switch (
V->getSCEVType()) {
10149 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10160 for (++i; i !=
e; ++i)
10200 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10210 for (++i; i !=
e; ++i) {
10215 return getWithOperands(V, NewOps);
10230 const Loop *CurrLoop = this->LI[
I->getParent()];
10241 if (BackedgeTakenCount->
isZero()) {
10242 Value *InitValue =
nullptr;
10243 bool MultipleInitValues =
false;
10249 MultipleInitValues =
true;
10254 if (!MultipleInitValues && InitValue)
10263 unsigned InLoopPred =
10274 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10288 SmallVector<Constant *, 4>
Operands;
10290 bool MadeImprovement =
false;
10305 MadeImprovement |= OrigV != OpV;
10310 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10315 if (!MadeImprovement)
10336const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10338 return stripInjectiveFunctions(ZExt->getOperand());
10340 return stripInjectiveFunctions(SExt->getOperand());
10358 assert(
A != 0 &&
"A must be non-zero.");
10374 if (MinTZ < Mult2 && L->getLoopPredecessor())
10376 if (MinTZ < Mult2) {
10399 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10419static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10425 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10426 << *AddRec <<
'\n');
10429 if (!LC || !MC || !
NC) {
10430 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10431 return std::nullopt;
10437 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10445 N =
N.sext(NewWidth);
10446 M = M.sext(NewWidth);
10447 L = L.sext(NewWidth);
10464 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10465 <<
", multiplied by " <<
T <<
'\n');
10474 std::optional<APInt>
Y) {
10476 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10479 return XW.
slt(YW) ? *
X : *
Y;
10482 return std::nullopt;
10483 return X ? *
X : *
Y;
10500 return std::nullopt;
10501 unsigned W =
X->getBitWidth();
10521static std::optional<APInt>
10527 return std::nullopt;
10530 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10531 std::optional<APInt>
X =
10534 return std::nullopt;
10539 return std::nullopt;
10554static std::optional<APInt>
10558 "Starting value of addrec should be 0");
10559 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10560 <<
Range <<
", addrec " << *AddRec <<
'\n');
10564 "Addrec's initial value should be in range");
10570 return std::nullopt;
10580 auto SolveForBoundary =
10581 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10584 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10585 << Bound <<
" (before multiplying by " << M <<
")\n");
10588 std::optional<APInt> SO;
10591 "signed overflow\n");
10595 "unsigned overflow\n");
10596 std::optional<APInt> UO =
10599 auto LeavesRange = [&] (
const APInt &
X) {
10602 if (
Range.contains(V0->getValue()))
10607 if (
Range.contains(
V1->getValue()))
10616 return {std::nullopt,
false};
10621 if (LeavesRange(*Min))
10622 return { Min,
true };
10623 std::optional<APInt> Max = Min == SO ? UO : SO;
10624 if (LeavesRange(*Max))
10625 return { Max,
true };
10628 return {std::nullopt,
true};
10635 auto SL = SolveForBoundary(
Lower);
10636 auto SU = SolveForBoundary(
Upper);
10639 if (!SL.second || !SU.second)
10640 return std::nullopt;
10683ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10685 bool ControlsOnlyExit,
10686 bool AllowPredicates) {
10697 if (
C->getValue()->isZero())
return C;
10701 const SCEVAddRecExpr *AddRec =
10704 if (!AddRec && AllowPredicates)
10710 if (!AddRec || AddRec->
getLoop() != L)
10721 return ExitLimit(R, R, R,
false, Predicates);
10779 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10809 const SCEV *
Exact =
10817 const SCEV *SymbolicMax =
10819 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10828 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10836 return ExitLimit(
E, M, S,
false, Predicates);
10839ScalarEvolution::ExitLimit
10840ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10848 if (!
C->getValue()->isZero())
10858std::pair<const BasicBlock *, const BasicBlock *>
10859ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10870 if (
const Loop *L = LI.getLoopFor(BB))
10871 return {
L->getLoopPredecessor(),
L->getHeader()};
10873 return {
nullptr, BB};
10882 if (
A ==
B)
return true;
10897 if (ComputesEqualValues(AI, BI))
10905 const SCEV *Op0, *Op1;
10924 auto TrivialCase = [&](
bool TriviallyTrue) {
10933 const SCEV *NewLHS, *NewRHS;
10957 return TrivialCase(
false);
10958 return TrivialCase(
true);
10977 RAdd->hasNoSignedWrap()) ||
10979 RAdd->hasNoUnsignedWrap())) {
10999 bool BothNUW = LMul->hasNoUnsignedWrap() && RMul->hasNoUnsignedWrap();
11000 bool BothNSW = LMul->hasNoSignedWrap() && RMul->hasNoSignedWrap();
11003 C->getAPInt().isStrictlyPositive()) ||
11027 const APInt &
RA = RC->getAPInt();
11029 bool SimplifiedByConstantRange =
false;
11034 return TrivialCase(
true);
11036 return TrivialCase(
false);
11045 Changed = SimplifiedByConstantRange =
true;
11049 if (!SimplifiedByConstantRange) {
11066 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
11072 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
11078 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
11084 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11104 return TrivialCase(
true);
11106 return TrivialCase(
false);
11211 auto NonRecursive = [OrNegative](
const SCEV *S) {
11213 return C->getAPInt().isPowerOf2() ||
11214 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11220 if (NonRecursive(S))
11230 const SCEV *S, uint64_t M,
11239 APInt C = Cst->getAPInt();
11240 return C.urem(M) == 0;
11246 const SCEV *SmodM =
11267 [&](
SCEVUse Op) { return isKnownMultipleOf(Op, M, Predicates); }))
11274 return isKnownMultipleOf(Op, M, Predicates);
11280 return isKnownMultipleOf(Op, M, Predicates);
11287 for (
auto *
A : *Predicates)
11288 if (
A->implies(
P, *
this))
11301std::pair<const SCEV *, const SCEV *>
11304 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11306 return { Start, Start };
11308 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11317 getUsedLoops(LHS, LoopsUsed);
11318 getUsedLoops(RHS, LoopsUsed);
11320 if (LoopsUsed.
empty())
11325 for (
const auto *L1 : LoopsUsed)
11326 for (
const auto *L2 : LoopsUsed)
11327 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11328 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11329 "Domination relationship is not a linear order");
11359 SplitRHS.second) &&
11369 isKnownPredicateViaSplitting(Pred, LHS, RHS) ||
11370 isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11380 return std::nullopt;
11395 if (KnownWithoutContext)
11396 return KnownWithoutContext;
11403 return std::nullopt;
11409 const Loop *L = LHS->getLoop();
11414std::optional<ScalarEvolution::MonotonicPredicateType>
11417 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11423 auto ResultSwapped =
11426 assert(*ResultSwapped != *Result &&
11427 "monotonicity should flip as we flip the predicate");
11434std::optional<ScalarEvolution::MonotonicPredicateType>
11435ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11449 return std::nullopt;
11453 "Should be greater or less!");
11457 if (!LHS->hasNoUnsignedWrap())
11458 return std::nullopt;
11462 "Relational predicate is either signed or unsigned!");
11463 if (!
LHS->hasNoSignedWrap())
11464 return std::nullopt;
11466 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11474 return std::nullopt;
11477std::optional<ScalarEvolution::LoopInvariantPredicate>
11484 return std::nullopt;
11491 if (!ArLHS || ArLHS->
getLoop() != L)
11492 return std::nullopt;
11497 Pred = Pred.dropSameSign();
11500 return std::nullopt;
11526 return std::nullopt;
11563 return std::nullopt;
11566std::optional<ScalarEvolution::LoopInvariantPredicate>
11571 Pred, LHS, RHS, L, CtxI, MaxIter))
11581 Pred, LHS, RHS, L, CtxI,
Op))
11583 return std::nullopt;
11586std::optional<ScalarEvolution::LoopInvariantPredicate>
11601 return std::nullopt;
11608 if (!AR || AR->
getLoop() != L)
11609 return std::nullopt;
11614 Pred = Pred.dropSameSign();
11618 return std::nullopt;
11624 if (Step != One && Step != MinusOne)
11625 return std::nullopt;
11631 return std::nullopt;
11637 return std::nullopt;
11645 if (Step == MinusOne)
11649 return std::nullopt;
11655bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11661 auto CheckRange = [&](
bool IsSigned) {
11664 return RangeLHS.
icmp(Pred, RangeRHS);
11673 if (CheckRange(
true) || CheckRange(
false))
11682bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11690 SCEVUse XNonConstOp, XConstOp;
11691 SCEVUse YNonConstOp, YConstOp;
11696 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11697 XConstOp =
nullptr;
11704 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11705 YConstOp =
nullptr;
11710 if (YNonConstOp != XNonConstOp)
11783bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11804bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11805 const SCEV *
LHS,
const SCEV *
RHS) {
11810 return any_of(*BB, [&](
const Instruction &
I) {
11811 using namespace llvm::PatternMatch;
11816 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11830 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11833 if (Opts.scev_verify_ir)
11835 "This cannot be done on broken IR!");
11838 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11847 if (LoopContinuePredicate &&
11848 isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->
getCondition(),
11849 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11854 if (WalkingBEDominatingConds)
11860 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11861 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11868 const SCEV *LoopCounter =
11876 for (
auto &AssumeVH : AC.assumptions()) {
11883 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11887 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11890 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11891 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11892 assert(DTN &&
"should reach the loop header before reaching the root!");
11895 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11913 if (isImpliedCond(Pred, LHS, RHS, ContBr->
getCondition(),
11926 if (!DT.isReachableFromEntry(BB))
11928 if (Opts.scev_verify_ir)
11930 "This cannot be done on broken IR!");
11938 const bool ProvingStrictComparison =
11940 bool ProvedNonStrictComparison =
false;
11941 bool ProvedNonEquality =
false;
11944 if (!ProvedNonStrictComparison)
11945 ProvedNonStrictComparison = Fn(NonStrictPredicate);
11946 if (!ProvedNonEquality)
11948 if (ProvedNonStrictComparison && ProvedNonEquality)
11953 if (ProvingStrictComparison) {
11955 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
11957 if (SplitAndProve(ProofFn))
11962 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
11964 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
11966 if (ProvingStrictComparison) {
11968 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
11970 if (SplitAndProve(ProofFn))
11979 const Loop *ContainingLoop = LI.getLoopFor(BB);
11981 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
11985 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
11986 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
11989 if (!BlockEntryPredicate)
11998 for (
auto &AssumeVH : AC.assumptions()) {
12002 if (!DT.dominates(CI, BB))
12005 if (ProveViaCond(CI->getArgOperand(0),
false))
12011 F.getParent(), Intrinsic::experimental_guard);
12013 for (
const auto *GU : GuardDecl->users())
12015 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
12016 if (ProveViaCond(Guard->getArgOperand(0),
false))
12031 "LHS is not available at Loop Entry");
12033 "RHS is not available at Loop Entry");
12035 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
12046 if (FoundCondValue ==
12050 if (!PendingLoopPredicates.insert(FoundCondValue).second)
12054 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
12057 const Value *Op0, *Op1;
12060 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
12064 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
12065 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
12069 if (!ICI)
return false;
12073 CmpPredicate FoundPred;
12082 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
12085bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
12086 const SCEV *
RHS, CmpPredicate FoundPred,
12087 const SCEV *FoundLHS,
const SCEV *FoundRHS,
12088 const Instruction *CtxI) {
12098 auto *WideType = FoundLHS->
getType();
12110 TruncFoundLHS, TruncFoundRHS, CtxI))
12136 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
12140bool ScalarEvolution::isImpliedCondBalancedTypes(
12145 "Types should be balanced!");
12152 if (FoundLHS == FoundRHS)
12156 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12168 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12183 LHS, FoundLHS, FoundRHS, CtxI);
12185 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12197 if (IsSignFlippedPredicate(Pred, FoundPred) &&
12198 isImpliedCondViaSignFlippedPred(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12201 if (IsSignFlippedPredicate(SwappedPred, FoundPred) &&
12202 isImpliedCondViaSignFlippedPred(SwappedPred,
RHS,
LHS, FoundLHS, FoundRHS,
12210 const SCEVConstant *
C =
nullptr;
12211 const SCEV *
V =
nullptr;
12229 if (Min ==
C->getAPInt()) {
12234 APInt SharperMin = Min + 1;
12237 case ICmpInst::ICMP_SGE:
12238 case ICmpInst::ICMP_UGE:
12241 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12246 case ICmpInst::ICMP_SGT:
12247 case ICmpInst::ICMP_UGT:
12257 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12262 case ICmpInst::ICMP_SLE:
12263 case ICmpInst::ICMP_ULE:
12264 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12265 LHS, V, getConstant(SharperMin), CtxI))
12269 case ICmpInst::ICMP_SLT:
12270 case ICmpInst::ICMP_ULT:
12271 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12272 LHS, V, getConstant(Min), CtxI))
12286 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12290 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12293 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12300bool ScalarEvolution::isImpliedCondViaSignFlippedPred(
12301 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12302 const SCEV *FoundRHS,
const Instruction *CtxI) {
12307 isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12331 CmpPredicate BoundPred =
12333 if (isKnownViaNonRecursiveReasoning(BoundPred, FoundRHS, SignedMin)) {
12336 if (isImpliedCondOperands(Pred,
LHS,
RHS, Bound, FoundLHS, CtxI))
12344 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS))
12351 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS))
12366std::optional<APInt>
12373 APInt DiffMul(BW, 1);
12376 for (
unsigned I = 0;
I < 8; ++
I) {
12385 if (LAR->getLoop() != MAR->getLoop())
12386 return std::nullopt;
12390 if (!LAR->isAffine() || !MAR->isAffine())
12391 return std::nullopt;
12393 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12394 return std::nullopt;
12396 Less = LAR->getStart();
12397 More = MAR->getStart();
12402 auto MatchConstMul =
12403 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12408 return std::nullopt;
12410 if (
auto MatchedMore = MatchConstMul(More)) {
12411 if (
auto MatchedLess = MatchConstMul(
Less)) {
12412 if (MatchedMore->second == MatchedLess->second) {
12413 More = MatchedMore->first;
12414 Less = MatchedLess->first;
12415 DiffMul *= MatchedMore->second;
12426 Diff +=
C->getAPInt() * DiffMul;
12429 Diff -=
C->getAPInt() * DiffMul;
12432 Multiplicity[S] +=
Mul;
12434 auto Decompose = [&](
const SCEV *S,
int Mul) {
12441 Decompose(More, 1);
12442 Decompose(
Less, -1);
12446 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12447 for (
const auto &[S,
Mul] : Multiplicity) {
12452 return std::nullopt;
12454 }
else if (
Mul == -1) {
12456 return std::nullopt;
12459 return std::nullopt;
12463 if (NewMore == More || NewLess ==
Less)
12464 return std::nullopt;
12470 if (!More && !
Less)
12474 if (!More || !
Less)
12475 return std::nullopt;
12479 return std::nullopt;
12482bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12504 const auto *Latch = L->getLoopLatch();
12507 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12516 const auto *Latch = L->getLoopLatch();
12519 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12529bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12532 const SCEV *FoundLHS,
12533 const SCEV *FoundRHS) {
12542 if (!AddRecFoundLHS)
12549 const Loop *
L = AddRecFoundLHS->getLoop();
12550 if (L != AddRecLHS->getLoop())
12589 if (!RDiff || *LDiff != *RDiff)
12592 if (LDiff->isMinValue())
12595 APInt FoundRHSLimit;
12598 FoundRHSLimit = -(*RDiff);
12610bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12611 const SCEV *
RHS,
const SCEV *FoundLHS,
12612 const SCEV *FoundRHS,
unsigned Depth) {
12613 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12617 bool Erased = PendingMerges.erase(LPhi);
12618 assert(Erased &&
"Failed to erase LPhi!");
12622 bool Erased = PendingMerges.erase(RPhi);
12623 assert(Erased &&
"Failed to erase RPhi!");
12631 if (!PendingMerges.insert(Phi).second)
12645 if (!PendingMerges.insert(Phi).second)
12651 if (!LPhi && !RPhi)
12662 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12666 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12667 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12668 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12669 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12672 if (RPhi && RPhi->getParent() == LBB) {
12679 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12680 if (!ProvedEasily(L, R))
12691 auto *RLoop = RAR->
getLoop();
12692 auto *Predecessor = RLoop->getLoopPredecessor();
12693 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12695 if (!ProvedEasily(L1, RAR->
getStart()))
12697 auto *Latch = RLoop->getLoopLatch();
12698 assert(Latch &&
"Loop with AddRec with no latch?");
12719 if (
auto *
Loop = LI.getLoopFor(LBB))
12722 if (!ProvedEasily(L,
RHS))
12729bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12732 const SCEV *FoundLHS,
12733 const SCEV *FoundRHS) {
12736 if (
RHS == FoundRHS) {
12741 if (
LHS != FoundLHS)
12748 Value *Shiftee, *ShiftValue;
12750 using namespace PatternMatch;
12751 if (
match(SUFoundRHS->getValue(),
12753 auto *ShifteeS =
getSCEV(Shiftee);
12771bool ScalarEvolution::isImpliedCondOperandsViaMatchingDiff(
12772 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
const SCEV *FoundLHS,
12773 const SCEV *FoundRHS) {
12805 const SCEV *FoundDiff =
getMinusSCEV(FoundLHS, FoundRHS);
12813 return Diff == FoundDiff;
12816bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12818 const SCEV *FoundLHS,
12819 const SCEV *FoundRHS,
12820 const Instruction *CtxI) {
12821 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12823 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12825 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12826 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12828 isImpliedCondOperandsViaMatchingDiff(Pred,
LHS,
RHS, FoundLHS,
12830 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12834template <
typename MinMaxExprType>
12836 const SCEV *Candidate) {
12841 return is_contained(MinMaxExpr->operands(), Candidate);
12854 const SCEV *LStart, *RStart, *Step;
12951bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
12953 const SCEV *FoundLHS,
12954 const SCEV *FoundRHS,
12958 "LHS and RHS have different sizes?");
12961 "FoundLHS and FoundRHS have different sizes?");
12963 if (
Depth > Opts.scalar_evolution_max_scev_operations_implication_depth)
12995 auto GetOpFromSExt = [&](
const SCEV *S) ->
const SCEV * {
12997 return Ext->getOperand();
13004 auto *OrigLHS =
LHS;
13005 auto *OrigFoundLHS = FoundLHS;
13006 LHS = GetOpFromSExt(
LHS);
13007 FoundLHS = GetOpFromSExt(FoundLHS);
13010 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
13013 FoundRHS,
Depth + 1);
13030 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
13031 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
13036 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
13042 using namespace llvm::PatternMatch;
13061 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
13069 auto *DTy = Denominator->getType();
13070 auto *FRHSTy = FoundRHS->
getType();
13071 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
13090 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
13101 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
13103 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
13111 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
13144bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
13148 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
13152 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
13155bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
13158 const SCEV *FoundLHS,
13159 const SCEV *FoundRHS) {
13165 if (isKnownViaNonRecursiveReasoning(NonStrictPred,
LHS, FoundLHS) &&
13166 isKnownViaNonRecursiveReasoning(
13172 return isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
13175bool ScalarEvolution::isImpliedCondOperandsViaRanges(
13176 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
13177 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13191 ConstantRange FoundLHSRange =
13195 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13202 return LHSRange.
icmp(Pred, ConstRHS);
13205bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13206 bool IsSigned,
bool Invert) {
13213 APInt MaxRHS = getRangeMax(
RHS,
true, Invert);
13218 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13221 APInt MaxRHS = getRangeMax(
RHS,
false, Invert);
13226 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13239ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
const SCEV *Stride,
13241 bool IsSigned,
bool Invert) {
13256 APInt MinStart = getRangeMin(Start, IsSigned, Invert);
13269 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13275 APInt MaxEnd = getRangeMax(
End, IsSigned, Invert);
13281 :
APIntOps::umax(MaxEnd, MinStart);
13283 APInt Delta = MaxEnd - MinStart;
13287 const SCEV *DeltaExpr =
13295ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13296 const Loop *L,
bool IsSigned,
bool Invert,
13297 bool ControlsOnlyExit,
bool AllowPredicates) {
13307 bool PredicatedIV =
false;
13309 if (!
IV && !Invert) {
13313 auto canProveNUW = [&]() {
13316 if (!ControlsOnlyExit)
13337 Limit = Limit.
zext(OuterBitWidth);
13349 Type *Ty = ZExt->getType();
13359 if (!
IV && AllowPredicates) {
13364 PredicatedIV =
true;
13368 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13382 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13389 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13392 const SCEV *GuardedStride = Stride;
13396 bool IVMayOverflow =
true;
13400 if (!PositiveStride) {
13403 GuardedStride = LoopGuardedStride;
13404 PositiveStride =
true;
13411 if (!PositiveStride) {
13460 const SCEVPredicate *
P =
13481 auto wouldZeroStrideBeUB = [&]() {
13493 if (!wouldZeroStrideBeUB()) {
13500 IVMayOverflow = canIVOverflowOnLT(
RHS, GuardedStride, IsSigned, Invert) &&
13502 GuardedStride, IsSigned, Invert);
13503 if (IVMayOverflow && !NoWrap)
13516 const SCEV *
Start =
IV->getStart();
13522 const SCEV *OrigStart =
Start;
13523 const SCEV *OrigRHS =
RHS;
13524 if (
Start->getType()->isPointerTy()) {
13538 assert(!Invert &&
"RHS must be loop-invariant for Invert");
13540 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13541 any(RHSAddRec->getNoWrapFlags())) {
13554 const SCEV *RHSStart = RHSAddRec->getStart();
13555 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13567 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13576 BECountIfBackedgeTaken =
13603 bool AddingStrideMinusOneMayOverflow = IVMayOverflow && [&] {
13650 if (!Invert && (Start == Stride || Start ==
getMinusSCEV(Stride, One))) {
13667 auto StepBack = [&](
const SCEV *
V,
const SCEV *
Offset) ->
const SCEV * {
13672 auto Distance = [&](
const SCEV *From,
const SCEV *To) {
13676 const SCEV *OrigPrevStart = StepBack(OrigStart, Stride);
13683 if ((!AddingStrideMinusOneMayOverflow ||
13715 const SCEV *Numerator =
13721 auto canProveRHSIsAtOrBeyondStart = [&]() {
13726 auto SwapIfInverted = [&](
const SCEV *
A,
const SCEV *
B) {
13727 return Invert ? std::pair(
B,
A) : std::pair(
A,
B);
13736 auto [GELHS, GERHS] = SwapIfInverted(OrigRHS, OrigStart);
13741 if ((GuardedRHS != GELHS || GuardedStart != GERHS) &&
13755 auto [GTLHS, GTRHS] = SwapIfInverted(OrigRHS, StepBack(OrigStart, One));
13761 if (canProveRHSIsAtOrBeyondStart()) {
13784 const SCEV *Delta = Distance(Start,
End);
13785 if (!AddingStrideMinusOneMayOverflow) {
13797 const SCEV *ConstantMaxBECount;
13798 bool MaxOrZero =
false;
13800 ConstantMaxBECount = BECount;
13802 ConstantMaxBECount = computeMaxBECountForLT(
13809 const APInt *IfTaken, *RangeMax;
13812 IfTaken->
ugt(*RangeMax)) {
13813 ConstantMaxBECount =
getZero(BECountIfBackedgeTaken->getType());
13815 ConstantMaxBECount = BECountIfBackedgeTaken;
13825 const SCEV *SymbolicMaxBECount =
13827 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13833 if (
Range.isFullSet())
13838 if (!SC->getValue()->isZero()) {
13844 return ShiftedAddRec->getNumIterationsInRange(
13845 Range.subtract(SC->getAPInt()), SE);
13889 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
13890 "Linear scev computation is off in a bad way!");
13921 assert(!
Last->isZero() &&
"Recurrency with zero step?");
13954 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13956 SE->ConstantEvolutionLoopExitValue.erase(PN);
13957 SE->eraseValueFromMap(getValPtr());
13961void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
13962 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13972 : CallbackVH(
V), SE(se) {}
13983 ValuesAtScopes(64), LoopDispositions(64), BlockDispositions(64) {
13995 F.getParent(), Intrinsic::experimental_guard);
13996 HasGuards = GuardDecl && !GuardDecl->use_empty();
14000 : Opts(Arg.Opts), F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards),
14001 TLI(Arg.TLI), AC(Arg.AC), DT(Arg.DT), LI(Arg.LI),
14002 CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
14003 ValueExprMap(
std::
move(Arg.ValueExprMap)),
14004 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
14005 PendingMerges(
std::
move(Arg.PendingMerges)),
14006 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
14007 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
14008 PredicatedBackedgeTakenCounts(
14009 std::
move(Arg.PredicatedBackedgeTakenCounts)),
14010 BECountUsers(
std::
move(Arg.BECountUsers)),
14011 ConstantEvolutionLoopExitValue(
14012 std::
move(Arg.ConstantEvolutionLoopExitValue)),
14013 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
14014 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
14015 LoopDispositions(
std::
move(Arg.LoopDispositions)),
14016 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
14017 BlockDispositions(
std::
move(Arg.BlockDispositions)),
14018 SCEVUsers(
std::
move(Arg.SCEVUsers)),
14019 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
14020 SignedRanges(
std::
move(Arg.SignedRanges)),
14021 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
14022 UniquePreds(
std::
move(Arg.UniquePreds)),
14023 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
14024 ConstantSCEVs(
std::
move(Arg.ConstantSCEVs)),
14025 LoopUsers(
std::
move(Arg.LoopUsers)),
14026 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
14027 FirstUnknown(Arg.FirstUnknown),
14028 NextUnknownOrderID(Arg.NextUnknownOrderID) {
14029 Arg.FirstUnknown =
nullptr;
14038 Tmp->~SCEVUnknown();
14040 FirstUnknown =
nullptr;
14042 ExprValueMap.clear();
14043 ValueExprMap.clear();
14045 BackedgeTakenCounts.clear();
14046 PredicatedBackedgeTakenCounts.clear();
14048 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
14049 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
14050 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
14051 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
14073 L->getHeader()->printAsOperand(OS,
false);
14077 L->getExitingBlocks(ExitingBlocks);
14078 if (ExitingBlocks.
size() != 1)
14079 OS <<
"<multiple exits> ";
14083 OS <<
"backedge-taken count is ";
14086 OS <<
"Unpredictable backedge-taken count.";
14089 if (ExitingBlocks.
size() > 1)
14090 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14091 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
14099 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
14102 OS <<
"\n Predicates:\n";
14103 for (
const auto *
P : Predicates)
14111 L->getHeader()->printAsOperand(OS,
false);
14116 OS <<
"constant max backedge-taken count is ";
14119 OS <<
", actual taken count either this or zero.";
14121 OS <<
"Unpredictable constant max backedge-taken count. ";
14126 L->getHeader()->printAsOperand(OS,
false);
14131 OS <<
"symbolic max backedge-taken count is ";
14134 OS <<
", actual taken count either this or zero.";
14136 OS <<
"Unpredictable symbolic max backedge-taken count. ";
14140 if (ExitingBlocks.
size() > 1)
14141 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14142 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
14152 OS <<
"\n predicated symbolic max exit count for "
14153 << ExitingBlock->
getName() <<
": ";
14155 OS <<
"\n Predicates:\n";
14156 for (
const auto *
P : Predicates)
14167 L->getHeader()->printAsOperand(OS,
false);
14170 OS <<
"Predicated backedge-taken count is ";
14173 OS <<
"Unpredictable predicated backedge-taken count.";
14175 OS <<
" Predicates:\n";
14176 for (
const auto *
P : Preds)
14181 auto *PredConstantMax =
14183 if (PredConstantMax != ConstantBTC) {
14185 L->getHeader()->printAsOperand(OS,
false);
14188 OS <<
"Predicated constant max backedge-taken count is ";
14191 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14193 OS <<
" Predicates:\n";
14194 for (
const auto *
P : Preds)
14199 auto *PredSymbolicMax =
14201 if (SymbolicBTC != PredSymbolicMax) {
14203 L->getHeader()->printAsOperand(OS,
false);
14206 OS <<
"Predicated symbolic max backedge-taken count is ";
14209 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14211 OS <<
" Predicates:\n";
14212 for (
const auto *
P : Preds)
14218 L->getHeader()->printAsOperand(OS,
false);
14245 OS <<
"Computable";
14255 OS <<
"DoesNotDominate";
14261 OS <<
"ProperlyDominates";
14277 if (Opts.scalar_evolution_classify_expressions) {
14278 OS <<
"Classifying expressions for: ";
14279 F.printAsOperand(OS,
false);
14294 const Loop *L = LI.getLoopFor(
I.getParent());
14309 OS <<
"\t\t" "Exits: ";
14312 OS <<
"<<Unknown>>";
14318 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14320 Iter->getHeader()->printAsOperand(OS,
false);
14328 InnerL->getHeader()->printAsOperand(OS,
false);
14339 OS <<
"Determining loop execution counts for: ";
14340 F.printAsOperand(OS,
false);
14351 auto &
Values = LoopDispositions[S];
14352 for (
auto &V :
Values) {
14353 if (V.getPointer() == L)
14358 auto &Values2 = LoopDispositions[S];
14360 if (V.getPointer() == L) {
14369ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14387 if (L->contains(AR->
getLoop()) &&
14389 [&](
const SCEV *
Op) { return isLoopUniform(Op, L); }))
14394 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14395 " dominate the contained loop's header?");
14422 bool HasVarying =
false;
14423 bool HasUniform =
false;
14468 auto &
Values = BlockDispositions[S];
14469 for (
auto &V :
Values) {
14470 if (V.getPointer() == BB)
14475 auto &Values2 = BlockDispositions[S];
14477 if (V.getPointer() == BB) {
14486ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14515 bool Proper =
true;
14526 if (Instruction *
I =
14528 if (
I->getParent() == BB)
14530 if (DT.properlyDominates(
I->getParent(), BB))
14549void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14552 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14553 auto It = BECounts.find(L);
14554 if (It != BECounts.end()) {
14555 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14556 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14558 auto UserIt = BECountUsers.find(S);
14559 assert(UserIt != BECountUsers.end());
14564 BECounts.erase(It);
14572 while (!Worklist.
empty()) {
14574 auto Users = SCEVUsers.find(Curr);
14575 if (
Users != SCEVUsers.end())
14576 for (
const auto *User :
Users->second)
14577 if (ToForget.
insert(User).second)
14581 for (
const auto *S : ToForget)
14582 forgetMemoizedResultsImpl(S);
14584 PredicatedSCEVRewrites.remove_if(
14585 [&](
const auto &Entry) {
return ToForget.count(
Entry.first.first); });
14588void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14589 LoopDispositions.erase(S);
14590 BlockDispositions.erase(S);
14591 UnsignedRanges.erase(S);
14592 SignedRanges.erase(S);
14593 HasRecMap.erase(S);
14594 ConstantMultipleCache.erase(S);
14597 UnsignedWrapViaInductionTried.erase(AR);
14598 SignedWrapViaInductionTried.erase(AR);
14601 auto ExprIt = ExprValueMap.find(S);
14602 if (ExprIt != ExprValueMap.end()) {
14603 for (
Value *V : ExprIt->second) {
14604 auto ValueIt = ValueExprMap.find_as(V);
14605 if (ValueIt != ValueExprMap.end())
14606 ValueExprMap.erase(ValueIt);
14608 ExprValueMap.erase(ExprIt);
14611 auto ScopeIt = ValuesAtScopes.find(S);
14612 if (ScopeIt != ValuesAtScopes.end()) {
14613 for (
const auto &Pair : ScopeIt->second)
14615 llvm::erase(ValuesAtScopesUsers[Pair.second.getPointer()],
14616 std::make_pair(Pair.first, S));
14617 ValuesAtScopes.erase(ScopeIt);
14620 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14621 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14622 for (
const auto &Pair : ScopeUserIt->second)
14625 llvm::erase_if(ValuesAtScopes[Pair.second], [&](
const auto &LS) {
14626 return LS.first == Pair.first && LS.second.getPointer() == S;
14628 ValuesAtScopesUsers.erase(ScopeUserIt);
14631 auto BEUsersIt = BECountUsers.find(S);
14632 if (BEUsersIt != BECountUsers.end()) {
14634 auto Copy = BEUsersIt->second;
14635 for (
const auto &Pair : Copy)
14636 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14637 BECountUsers.erase(BEUsersIt);
14640 auto FoldUser = FoldCacheUser.find(S);
14641 if (FoldUser != FoldCacheUser.end())
14642 for (
auto &KV : FoldUser->second)
14643 FoldCache.erase(KV);
14644 FoldCacheUser.erase(S);
14648ScalarEvolution::getUsedLoops(
const SCEV *S,
14650 struct FindUsedLoops {
14651 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14652 : LoopsUsed(LoopsUsed) {}
14653 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14654 bool follow(
const SCEV *S) {
14660 bool isDone()
const {
return false; }
14663 FindUsedLoops
F(LoopsUsed);
14664 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14667void ScalarEvolution::getReachableBlocks(
14670 Worklist.
push_back(&F.getEntryBlock());
14671 while (!Worklist.
empty()) {
14673 if (!Reachable.
insert(BB).second)
14681 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14688 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14692 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14727 SCEVMapper SCM(SE2);
14729 SE2.getReachableBlocks(ReachableBlocks, F);
14731 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14749 while (!LoopStack.
empty()) {
14755 if (!ReachableBlocks.
contains(L->getHeader()))
14760 auto It = BackedgeTakenCounts.find(L);
14761 if (It == BackedgeTakenCounts.end())
14765 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14785 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14786 if (Delta && !Delta->
isZero()) {
14787 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14788 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14789 dbgs() <<
"New: " << *NewBECount <<
"\n";
14790 dbgs() <<
"Delta: " << *Delta <<
"\n";
14798 while (!Worklist.
empty()) {
14800 if (ValidLoops.
insert(L).second)
14801 Worklist.
append(L->begin(), L->end());
14803 for (
const auto &KV : ValueExprMap) {
14808 "AddRec references invalid loop");
14813 auto It = ExprValueMap.find(KV.second);
14814 if (It == ExprValueMap.end() || !
is_contained(It->second, KV.first)) {
14815 dbgs() <<
"Value " << *KV.first
14816 <<
" is in ValueExprMap but not in ExprValueMap\n";
14821 if (!ReachableBlocks.
contains(
I->getParent()))
14823 const SCEV *OldSCEV = SCM.visit(KV.second);
14825 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14826 if (Delta && !Delta->
isZero()) {
14827 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14828 <<
"Old: " << *OldSCEV <<
"\n"
14829 <<
"New: " << *NewSCEV <<
"\n"
14830 <<
"Delta: " << *Delta <<
"\n";
14836 for (
const auto &KV : ExprValueMap) {
14837 for (
Value *V : KV.second) {
14838 const SCEV *S = ValueExprMap.lookup(V);
14840 dbgs() <<
"Value " << *V
14841 <<
" is in ExprValueMap but not in ValueExprMap\n";
14844 if (S != KV.first) {
14845 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14846 << *KV.first <<
"\n";
14853 for (
const auto &S : UniqueSCEVs) {
14858 auto It = SCEVUsers.find(
Op);
14859 if (It != SCEVUsers.end() && It->second.count(&S))
14861 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14862 <<
" is not being tracked!\n";
14868 for (
const auto &ValueAndVec : ValuesAtScopes) {
14870 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14871 const Loop *L = LoopAndValueAtScope.first;
14872 SCEVUse ValueAtScope = LoopAndValueAtScope.second;
14874 auto It = ValuesAtScopesUsers.find(ValueAtScope.
getPointer());
14875 if (It != ValuesAtScopesUsers.end() &&
14878 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14879 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14885 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14886 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14887 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14888 const Loop *L = LoopAndValue.first;
14889 const SCEV *
Value = LoopAndValue.second;
14891 auto It = ValuesAtScopes.find(
Value);
14894 if (It != ValuesAtScopes.end() &&
any_of(It->second, [&](
const auto &LS) {
14895 return LS.first == L && LS.second.getPointer() == ValueAtScope;
14898 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14899 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14905 auto VerifyBECountUsers = [&](
bool Predicated) {
14907 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14908 for (
const auto &LoopAndBEInfo : BECounts) {
14909 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
14910 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14912 auto UserIt = BECountUsers.find(S);
14913 if (UserIt != BECountUsers.end() &&
14914 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
14916 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
14917 <<
" missing from BECountUsers\n";
14924 VerifyBECountUsers(
false);
14925 VerifyBECountUsers(
true);
14928 for (
auto &[S,
Values] : LoopDispositions) {
14929 for (
auto [
Loop, CachedDisposition] :
Values) {
14931 if (CachedDisposition != RecomputedDisposition) {
14932 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
14933 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
14934 << RecomputedDisposition <<
"\n";
14941 for (
auto &[S,
Values] : BlockDispositions) {
14942 for (
auto [BB, CachedDisposition] :
Values) {
14944 if (CachedDisposition != RecomputedDisposition) {
14945 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
14946 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
14947 <<
", actual " << RecomputedDisposition <<
"\n";
14954 for (
auto [
FoldID, Expr] : FoldCache) {
14955 auto I = FoldCacheUser.find(Expr);
14956 if (
I == FoldCacheUser.end()) {
14957 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
14962 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
14966 for (
auto [Expr, IDs] : FoldCacheUser) {
14967 for (
auto &
FoldID : IDs) {
14970 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
14975 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
14976 <<
" != " << *Expr <<
"!\n";
14987 for (
auto [S, Multiple] : ConstantMultipleCache) {
14989 if ((Multiple != 0 && RecomputedMultiple != 0 &&
14990 Multiple.
urem(RecomputedMultiple) != 0 &&
14991 RecomputedMultiple.
urem(Multiple) != 0)) {
14992 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
14993 << *S <<
" : Computed " << RecomputedMultiple
14994 <<
" but cache contains " << Multiple <<
"!\n";
15002 FunctionAnalysisManager::Invalidator &Inv) {
15034 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
15035 <<
F.getName() <<
"':\n";
15041 "Scalar Evolution Analysis",
false,
true)
15090 const SCEV *LHS,
const SCEV *RHS) {
15092 assert(LHS->getType() == RHS->getType() &&
15093 "Type mismatch between LHS and RHS");
15096 ID.AddInteger(Pred);
15097 ID.AddPointer(LHS);
15098 ID.AddPointer(RHS);
15100 if (
const auto *S = UniquePreds.lookup(ID, Token))
15104 UniquePreds.insert(Eq, Token);
15115 ID.AddInteger(AddedFlags);
15117 if (
const auto *S = UniquePreds.lookup(ID, Token))
15119 auto *OF =
new (SCEVAllocator)
15121 UniquePreds.insert(OF, Token);
15141 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
15142 return Rewriter.visit(S);
15148 for (
const auto *Pred : U->getPredicates())
15150 if (IPred->getLHS() == Expr &&
15152 return IPred->getRHS();
15154 if (IPred->getLHS() == Expr &&
15155 IPred->getPredicate() == ICmpInst::ICMP_EQ)
15156 return IPred->getRHS();
15159 return convertToAddRecWithPreds(Expr);
15162 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15178 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15195 explicit SCEVPredicateRewriter(
15196 const Loop *L, ScalarEvolution &SE,
15197 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15198 const SCEVPredicate *Pred)
15199 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
15201 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15204 return Pred && Pred->
implies(
P, SE);
15210 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15213 return addOverflowAssumption(
A);
15222 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15226 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15228 if (!PredicatedRewrite)
15230 for (
const auto *
P : PredicatedRewrite->second){
15233 if (L != WP->getExpr()->getLoop())
15236 if (!addOverflowAssumption(
P))
15239 return PredicatedRewrite->first;
15242 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15243 const SCEVPredicate *Pred;
15252 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15259 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15279 if (!Step->
isOne())
15304 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15305 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15318 return Op->LHS == LHS &&
Op->RHS == RHS;
15325 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15327 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15352 const SCEV *Start = AR->getStart();
15353 const SCEV *OpStart =
Op->AR->getStart();
15358 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15367 const SCEV *Step = AR->getStepRecurrence(SE);
15368 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15389 SCEVFlags ScevFlags = AR->getNoWrapFlags();
15411 for (
const auto *
P : Preds)
15424 return this->implies(I, SE);
15436 const Loop *L = NWrap->getExpr()->getLoop();
15443 return RewrittenAR &&
15449 for (
const auto *Pred : Preds)
15450 Pred->print(OS,
Depth);
15455 for (
const auto *Pred : Set->Preds)
15463 bool CheckImplies = Preds.
size() < 16;
15466 if (CheckImplies &&
implies(
N, SE))
15472 for (
auto *
P : Preds) {
15473 if (CheckImplies &&
N->implies(
P, SE))
15477 Preds = std::move(PrunedPreds);
15478 Preds.push_back(
N);
15485 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15494 SCEVUsers[
Op].insert(
User);
15498 const SCEV *Expr = SE.getSCEV(V);
15503 RewriteEntry &Entry = RewriteMap[Expr];
15506 if (Entry.second && Generation == Entry.first)
15507 return Entry.second;
15512 Expr = Entry.second;
15514 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15515 Entry = {Generation, NewSCEV};
15521 if (!BackedgeCount) {
15523 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15524 for (
const auto *
P : Preds)
15527 return BackedgeCount;
15531 if (!SymbolicMaxBackedgeCount) {
15533 SymbolicMaxBackedgeCount =
15534 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15535 for (
const auto *
P : Preds)
15538 return SymbolicMaxBackedgeCount;
15542 if (!SmallConstantMaxTripCount) {
15544 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15545 for (
const auto *
P : Preds)
15548 return *SmallConstantMaxTripCount;
15552 if (Preds->implies(&Pred, SE))
15555 Preds = std::make_unique<SCEVUnionPredicate>(Preds->getUnionWith(&Pred, SE));
15556 updateGeneration();
15569void PredicatedScalarEvolution::updateGeneration() {
15571 if (++Generation == 0) {
15572 for (
auto &
II : RewriteMap) {
15573 const SCEV *Rewritten =
II.second.second;
15583 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15589 ExtraPreds->
append(NewPreds);
15595 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15601 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15603 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {}
15607 for (
auto *BB : L.getBlocks())
15608 for (
auto &
I : *BB) {
15609 if (!SE.isSCEVable(
I.getType()))
15612 auto *Expr = SE.getSCEV(&
I);
15613 auto II = RewriteMap.find(Expr);
15615 if (
II == RewriteMap.end())
15619 if (
II->second.second == Expr)
15624 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15628void ScalarEvolution::LoopGuards::collectPending() {
15629 const Loop *L = PendingLoop;
15632 PendingLoop =
nullptr;
15637 collectFromBlock(SE, *
this, L->getHeader(), Pred,
VisitedBlocks);
15640void ScalarEvolution::LoopGuards::collectFromPHI(
15648 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15649 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15663 auto &RewriteMap =
G->second.RewriteMap;
15664 if (RewriteMap.empty())
15666 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15667 if (S == RewriteMap.end())
15673 return {
C0, SM->getSCEVType()};
15676 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15677 MinMaxPattern
P2) -> MinMaxPattern {
15679 auto [C2, T2] =
P2;
15680 if (!
C1 || !C2 ||
T1 != T2)
15684 return {
C1->getAPInt().ult(C2->getAPInt()) ?
C1 : C2,
T1};
15686 return {
C1->getAPInt().slt(C2->getAPInt()) ?
C1 : C2,
T1};
15688 return {
C1->getAPInt().ugt(C2->getAPInt()) ?
C1 : C2,
T1};
15690 return {
C1->getAPInt().sgt(C2->getAPInt()) ?
C1 : C2,
T1};
15695 auto P = GetMinMaxConst(0);
15696 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15699 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15702 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15705 Guards.RewriteMap.insert({
LHS,
RHS});
15713 const APInt &DivisorVal,
15715 const APInt *ExprVal;
15728 const APInt &DivisorVal,
15730 const APInt *ExprVal;
15738 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15752 const SCEV *URemRHS =
nullptr;
15756 const SCEV *Multiple =
15758 DivInfo[URemLHS] = Multiple;
15760 Multiples[URemLHS] =
C->getAPInt();
15780 auto IsMinMaxSCEVWithNonNegativeConstant =
15784 if (
MinMax->getNumOperands() != 2)
15787 if (
C->getAPInt().isNegative())
15789 SCTy =
MinMax->getSCEVType();
15798 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15800 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15805 auto *DivisibleExpr =
15813void ScalarEvolution::LoopGuards::collectFromBlock(
15815 const BasicBlock *
Block,
const BasicBlock *Pred,
15823 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
15834 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15836 if (From == FromRewritten)
15838 RewriteMap[From] = To;
15844 auto GetMaybeRewritten = [&](
const SCEV *S) {
15845 return RewriteMap.lookup_or(S, S);
15852 const SCEV *MatchLHS,
15853 const SCEV *MatchRHS) {
15854 const SCEVConstant *
C1;
15857 if (!
match(MatchLHS,
15864 .
sub(
C1->getAPInt());
15869 const SCEV *RewrittenLHS = GetMaybeRewritten(LHSUnknown);
15870 ExactRegion = ExactRegion.intersectWith(SE.
getUnsignedRange(RewrittenLHS),
15875 if (ExactRegion.isEmptySet() || ExactRegion.isWrappedSet() ||
15876 ExactRegion.isFullSet())
15879 const SCEV *RegionMin = SE.
getConstant(ExactRegion.getUnsignedMin());
15880 const SCEV *RegionMax = SE.
getConstant(ExactRegion.getUnsignedMax());
15881 const SCEV *ClampedLHS =
15883 AddRewrite(LHSUnknown, RewrittenLHS, ClampedLHS);
15886 if (MatchRangeCheckIdiom(Predicate,
LHS,
RHS))
15899 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
15901 const APInt &DividesBy =
15916 switch (Predicate) {
15945 SmallPtrSet<const SCEV *, 16> Visited;
15947 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
15951 while (!Worklist.
empty()) {
15955 if (!Visited.
insert(From).second)
15957 const SCEV *FromRewritten = GetMaybeRewritten(From);
15958 const SCEV *To =
nullptr;
15960 switch (Predicate) {
15965 EnqueueOperands(
UMax);
15971 EnqueueOperands(
SMax);
15977 EnqueueOperands(
UMin);
15983 EnqueueOperands(
SMin);
15991 const SCEV *OneAlignedUp =
15993 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
16005 const SCEVConstant *
C;
16014 Guards.NotEqual.insert({
LHS,
RHS});
16023 AddRewrite(From, FromRewritten, To);
16040 SE.F.
getParent(), Intrinsic::experimental_guard);
16042 for (
const auto *GU : GuardDecl->users())
16044 if (Guard->getFunction() ==
Block->getParent() &&
16054 unsigned NumCollectedConditions = 0;
16055 unsigned NumDomTreeSteps = 0;
16057 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
16058 for (;; Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
16062 if (!NumDomTreeSteps &&
16063 Depth < SE.Opts.scalar_evolution_max_loop_guard_collection_depth) {
16064 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
16065 for (
auto &Phi : Pair.second->phis())
16070 ++NumDomTreeSteps > SE.Opts.scalar_evolution_max_guard_dom_tree_steps)
16076 const CondBrInst *LoopEntryPredicate =
16078 if (!LoopEntryPredicate)
16083 NumCollectedConditions++;
16087 if (
Depth > 0 && NumCollectedConditions == 2)
16098 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
16099 SmallVector<Value *, 8> Worklist;
16100 SmallPtrSet<Value *, 8> Visited;
16102 while (!Worklist.
empty()) {
16109 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
16133 DenseMap<const SCEV *, APInt> Multiples;
16135 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
16142 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
16143 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
16147 for (
const auto &[K, Divisor] : Multiples) {
16148 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
16149 Guards.RewriteMap[
K] =
16151 Guards.
rewrite(K), Divisor, SE),
16160 Guards.PreserveNUW =
true;
16161 Guards.PreserveNSW =
true;
16162 for (
const SCEV *Expr : ExprsToRewrite) {
16163 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16164 Guards.PreserveNUW &=
16166 Guards.PreserveNSW &=
16173 if (ExprsToRewrite.size() > 1) {
16174 for (
const SCEV *Expr : ExprsToRewrite) {
16175 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16176 Guards.RewriteMap.erase(Expr);
16177 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
16186 class SCEVLoopGuardRewriter
16197 NotEqual(Guards.NotEqual) {
16198 if (Guards.PreserveNUW)
16200 if (Guards.PreserveNSW)
16207 return Map.lookup_or(Expr, Expr);
16211 if (
const SCEV *S = Map.lookup(Expr))
16218 if (
const SCEV *S = Map.lookup(Expr))
16225 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16226 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16227 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16229 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16230 if (
const SCEV *S = Map.lookup(NarrowExt))
16231 return SE.getZeroExtendExpr(S, Ty);
16232 Bitwidth = Bitwidth / 2;
16240 if (
const SCEV *S = Map.lookup(Expr))
16247 if (
const SCEV *S = Map.lookup(Expr))
16253 if (
const SCEV *S = Map.lookup(Expr))
16259 if (
const SCEV *S = Map.lookup(Expr))
16264 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16269 if (NotEqual.contains({LHS, RHS})) {
16271 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16272 return SE.getUMaxExpr(OneAlignedUp, S);
16279 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16290 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16291 return SE.getAddExpr(
16294 if (
const SCEV *S = Map.lookup(
Add))
16295 return SE.getAddExpr(Expr->
getOperand(0), S);
16303 const SCEV *S =
nullptr;
16310 S = Map.lookup(SE.getAddExpr(NewC, Expr->
getOperand(1)));
16313 return SE.getAddExpr(S, SE.getMinusOne(Expr->
getType()));
16348 if (RewriteMap.empty() && NotEqual.empty())
16351 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16352 return Rewriter.visit(Expr);
16366 if (Guards.PendingLoop)
16367 Guards.collectPending();
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Expand Atomic instructions
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
SmallPtrSet< const BasicBlock *, 8 > VisitedBlocks
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
static bool isSigned(unsigned Opcode)
This file defines a hash set that can be used to remove duplication of nodes in a graph.
Value * getPointer(Value *Ptr)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
This defines the Use class.
iv Induction Variable Users
static bool hasNoUnsignedWrap(BinaryOperator &I)
static constexpr Value * getValue(Ty &ValueOrUse)
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
PowerPC Reduce CR logical Operation
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
MachineBasicBlock * Folded
SmallVector< MachineOperand, 4 > Cond
static DominatorTree getDomTree(Function &F)
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
SI optimize exec mask operations pre RA
static void visit(BasicBlock &Start, std::function< bool(BasicBlock *)> op)
This file provides utility classes that use RAII to save and restore values.
bool SCEVMinMaxExprContains(const SCEV *Root, const SCEV *OperandToFind, SCEVTypes RootKind)
static const Loop * isIntegerLoopHeaderPHI(const PHINode *PN, LoopInfo &LI)
static unsigned getConstantTripCount(const SCEVConstant *ExitCount)
static const SCEV * getNextSCEVDivisibleByDivisor(const SCEV *Expr, const APInt &DivisorVal, ScalarEvolution &SE)
static PHINode * getConstantEvolvingPHIOperands(const AnalysisOptions &Opts, Instruction *UseInst, const Loop *L, DenseMap< Instruction *, PHINode * > &PHIMap, const TargetLibraryInfo *TLI, unsigned Depth)
getConstantEvolvingPHIOperands - Implement getConstantEvolvingPHI by recursing through each instructi...
static void PushLoopPHIs(const Loop *L, SmallVectorImpl< Instruction * > &Worklist, SmallPtrSetImpl< Instruction * > &Visited)
Push PHI nodes in the header of the given loop onto the given Worklist.
static void insertFoldCacheEntry(const ScalarEvolution::FoldID &ID, const SCEV *S, DenseMap< ScalarEvolution::FoldID, const SCEV * > &FoldCache, DenseMap< const SCEV *, SmallVector< ScalarEvolution::FoldID, 2 > > &FoldCacheUser)
static bool hasHugeExpression(const AnalysisOptions &Opts, ArrayRef< SCEVUse > Ops)
Returns true if Ops contains a huge SCEV (the subtree of S contains at least -scalar-evolution-huge-e...
static bool RangeRefPHIAllowedOperands(DominatorTree &DT, PHINode *PHI)
static bool IsKnownPredicateViaAddRecMonotonicity(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Is LHS Pred RHS true because one of them is an AddRec that is known not to go below its own start val...
static std::optional< APInt > MinOptional(std::optional< APInt > X, std::optional< APInt > Y)
Helper function to compare optional APInts: (a) if X and Y both exist, return min(X,...
static std::optional< BinaryOp > MatchBinaryOp(Value *V, const DominatorTree &DT)
Try to map V into a BinaryOp, and return std::nullopt on failure.
static bool canConstantFold(const Instruction *I, const TargetLibraryInfo *TLI)
Return true if we can constant fold an instruction of the specified type, assuming that all operands ...
static BinaryOperator * getCommonInstForPHI(PHINode *PN)
static PHINode * getConstantEvolvingPHI(const AnalysisOptions &Opts, Value *V, const Loop *L, const TargetLibraryInfo *TLI)
getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node in the loop that V is deri...
static bool isDivisibilityGuard(const SCEV *LHS, const SCEV *RHS, ScalarEvolution &SE)
static std::optional< const SCEV * > createNodeForSelectViaUMinSeq(ScalarEvolution *SE, const SCEV *CondExpr, const SCEV *TrueExpr, const SCEV *FalseExpr)
static Constant * BuildConstantFromSCEV(const SCEV *V)
This builds up a Constant using the ConstantExpr interface.
static ConstantInt * EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C, ScalarEvolution &SE)
static const SCEV * BinomialCoefficient(const SCEV *It, unsigned K, ScalarEvolution &SE, Type *ResultTy)
Compute BC(It, K). The result has width W. Assume, K > 0.
static bool IsMinMaxConsistingOf(const SCEV *MaybeMinMaxExpr, const SCEV *Candidate)
Is MaybeMinMaxExpr an (U|S)(Min|Max) of Candidate and some other values?
static SCEVFlags getNoWrapFlagsForGEP(GEPOperator *GEP, const SCEV *Accum, ScalarEvolution &SE)
static const SCEV * SolveLinEquationWithOverflow(const APInt &A, const SCEV *B, SmallVectorImpl< const SCEVPredicate * > *Predicates, ScalarEvolution &SE, const Loop *L)
Finds the minimum unsigned root of the following equation:
static uint64_t umul_ov(uint64_t i, uint64_t j, bool &Overflow)
static void PrintSCEVWithTypeHint(raw_ostream &OS, const SCEV *S)
When printing a top-level SCEV for trip counts, it's helpful to include a type for constants which ar...
static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE, const Loop *L)
static bool containsConstantInAddMulChain(const SCEV *StartExpr)
Determine if any of the operands in this SCEV are a constant or if any of the add or multiply express...
static const SCEV * getExtendAddRecStart(const SCEVAddRecExpr *AR, Type *Ty, ScalarEvolution *SE, unsigned Depth)
static const SCEV * constantFoldAndGroupOps(const AnalysisOptions &Opts, ScalarEvolution &SE, LoopInfo &LI, DominatorTree &DT, SmallVectorImpl< SCEVUse > &Ops, FoldT Fold, IsIdentityT IsIdentity, IsAbsorberT IsAbsorber)
Performs a number of common optimizations on the passed Ops.
static int compareValueComplexity(const AnalysisOptions &Opts, const LoopInfo *const LI, Value *LV, Value *RV, unsigned Depth)
Compare the two values LV and RV in terms of their "complexity" where "complexity" is a partial (and ...
static bool IsKnownPredicateViaAddRecStart(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
static const SCEV * getPreStartForExtend(const SCEVAddRecExpr *AR, ScalarEvolution *SE, unsigned Depth)
static bool collectDivisibilityInformation(ICmpInst::Predicate Predicate, const SCEV *LHS, const SCEV *RHS, DenseMap< const SCEV *, const SCEV * > &DivInfo, DenseMap< const SCEV *, APInt > &Multiples, ScalarEvolution &SE)
static void PushDefUseChildren(Instruction *I, SmallVectorImpl< Instruction * > &Worklist, SmallPtrSetImpl< Instruction * > &Visited)
Push users of the given Instruction onto the given Worklist.
static std::optional< APInt > SolveQuadraticAddRecRange(const SCEVAddRecExpr *AddRec, const ConstantRange &Range, ScalarEvolution &SE)
Let c(n) be the value of the quadratic chrec {0,+,M,+,N} after n iterations.
static int compareSCEVComplexity(const AnalysisOptions &Opts, const LoopInfo *const LI, SCEVUse LHS, SCEVUse RHS, DominatorTree &DT)
static bool getOperandsForSelectLikePHI(DominatorTree &DT, PHINode *PN, Value *&Cond, Value *&LHS, Value *&RHS)
static std::optional< std::tuple< APInt, APInt, APInt, APInt, unsigned > > GetQuadraticEquation(const SCEVAddRecExpr *AddRec)
For a given quadratic addrec, generate coefficients of the corresponding quadratic equation,...
static bool CollectAddOperandsWithScales(SmallDenseMap< const SCEV *, APInt, 16 > &M, SmallVectorImpl< SCEVUse > &NewOps, APInt &AccumulatedConstant, ArrayRef< SCEVUse > Ops, const APInt &Scale, ScalarEvolution &SE)
Process the given Ops list, which is a list of operands to be added under the given scale,...
static bool isKnownPredicateExtendIdiom(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
static std::optional< APInt > SolveQuadraticAddRecExact(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE)
Let c(n) be the value of the quadratic chrec {L,+,M,+,N} after n iterations.
static std::optional< APInt > TruncIfPossible(std::optional< APInt > X, unsigned BitWidth)
Helper function to truncate an optional APInt to a given BitWidth.
static SCEVFlags StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type, ArrayRef< SCEVUse > Ops, SCEVFlags Flags)
static void groupByComplexity(const AnalysisOptions &Opts, SmallVectorImpl< SCEVUse > &Ops, LoopInfo *LI, DominatorTree &DT)
Given a list of SCEV objects, order them by their complexity, and group objects of the same complexit...
static APInt extractConstantWithoutWrapping(ScalarEvolution &SE, const SCEVConstant *ConstantTerm, const SCEVAddExpr *WholeAddExpr)
static bool canConstantEvolve(Instruction *I, const Loop *L, const TargetLibraryInfo *TLI)
Determine whether this instruction can constant evolve within this loop assuming its operands can all...
static bool MatchBinarySub(const SCEV *S, SCEVUse &LHS, SCEVUse &RHS)
static std::optional< ConstantRange > GetRangeFromMetadata(Value *V)
Helper method to assign a range to V from metadata present in the IR.
static Type * isSimpleCastedPHI(const SCEV *Op, const SCEVUnknown *SymbolicPHI, bool &Signed, ScalarEvolution &SE)
Helper function to createAddRecFromPHIWithCasts.
static Constant * EvaluateExpression(Value *V, const Loop *L, DenseMap< Instruction *, Constant * > &Vals, const DataLayout &DL, const TargetLibraryInfo *TLI)
EvaluateExpression - Given an expression that passes the getConstantEvolvingPHI predicate,...
static const SCEV * getPreviousSCEVDivisibleByDivisor(const SCEV *Expr, const APInt &DivisorVal, ScalarEvolution &SE)
static const SCEV * MatchNotExpr(const SCEV *Expr)
If Expr computes ~A, return A else return nullptr.
static std::pair< ConstantRange, bool > getRangeForAffineARHelper(APInt Step, const ConstantRange &StartRange, const APInt &MaxBECount, bool Signed)
static const SCEV * applyDivisibilityOnMinMaxExpr(const SCEV *MinMaxExpr, APInt Divisor, ScalarEvolution &SE)
static cl::opt< bool, true > VerifySCEVOpt("verify-scev", cl::Hidden, cl::location(VerifySCEV), cl::desc("Verify ScalarEvolution's backedge taken counts (slow)"))
static const SCEV * getSignedOverflowLimitForStep(const SCEV *Step, ICmpInst::Predicate *Pred, ScalarEvolution *SE)
static bool HasSameValue(const SCEV *A, const SCEV *B)
SCEV structural equivalence is usually sufficient for testing whether two expressions are equal,...
static uint64_t Choose(uint64_t n, uint64_t k, bool &Overflow)
Compute the result of "n choose k", the binomial coefficient.
static bool scevUnconditionallyPropagatesPoisonFromOperands(SCEVTypes Kind)
static Constant * getOtherIncomingValue(PHINode *PN, BasicBlock *BB)
static const SCEV * getUnsignedOverflowLimitForStep(const SCEV *Step, ICmpInst::Predicate *Pred, ScalarEvolution *SE)
static bool IsKnownPredicateViaMinOrMax(ScalarEvolution &SE, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Is LHS Pred RHS true on the virtue of LHS or RHS being a Min or Max expression?
static bool BrPHIToSelect(DominatorTree &DT, CondBrInst *BI, PHINode *Merge, Value *&C, Value *&LHS, Value *&RHS)
This file defines the scope_exit class, which executes user-defined cleanup logic at scope exit.
static bool InBlock(const Value *V, const BasicBlock *BB)
Provides some synthesis utilities to produce sequences of values.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
static SymbolRef::Type getType(const Symbol *Sym)
LocallyHashedType DenseMapInfo< LocallyHashedType >::Empty
static std::optional< bool > isImpliedCondOperands(CmpInst::Predicate Pred, const Value *ALHS, const Value *ARHS, const Value *BLHS, const Value *BRHS)
Return true if "icmp Pred BLHS BRHS" is true whenever "icmp PredALHS ARHS" is true.
virt reg Virtual Register Rewriter
static 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 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...
LLVM_ABI CmpInst::Predicate getPreferredSignedPredicate() const
Attempts to return a signed CmpInst::Predicate from the CmpPredicate.
CmpInst::Predicate dropSameSign() const
Drops samesign information.
Conditional Branch instruction.
Value * getCondition() const
BasicBlock * getSuccessor(unsigned i) const
static LLVM_ABI Constant * getNot(Constant *C)
static Constant * getPtrAdd(Constant *Ptr, Constant *Offset, GEPNoWrapFlags NW=GEPNoWrapFlags::none(), std::optional< ConstantRange > InRange=std::nullopt, Type *OnlyIfReduced=nullptr)
Create a getelementptr i8, ptr, offset constant expression.
static LLVM_ABI Constant * getPtrToAddr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static LLVM_ABI Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
static LLVM_ABI Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
This is the shared class of boolean and integer constants.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
static LLVM_ABI ConstantInt * getBool(LLVMContext &Context, bool V)
This class represents a range of values.
LLVM_ABI ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
LLVM_ABI ConstantRange zextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
PreferredRangeType
If represented precisely, the result of some range operations may consist of multiple disjoint ranges...
LLVM_ABI bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
const APInt & getLower() const
Return the lower value for this range.
LLVM_ABI ConstantRange urem(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned remainder operation of...
LLVM_ABI bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type.
LLVM_ABI bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const
Does the predicate Pred hold between ranges this and Other?
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI ConstantRange zeroExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
LLVM_ABI bool isSignWrappedSet() const
Return true if this set wraps around the signed domain.
LLVM_ABI APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
LLVM_ABI bool isWrappedSet() const
Return true if this set wraps around the unsigned domain.
LLVM_ABI void print(raw_ostream &OS) const
Print out the bounds to a stream.
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.
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
static bool isLE(Predicate P)
Return true if the predicate is SLE or ULE.
This instruction inserts a single (scalar) element into a VectorType value.
This instruction inserts a struct field of array element value into an aggregate value.
LLVM_ABI bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
LLVM_ABI bool hasNoSignedWrap() const LLVM_READONLY
Determine whether the no signed wrap flag is set.
LLVM_ABI bool isIdenticalToWhenDefined(const Instruction *I, bool IntersectAttrs=false) const LLVM_READONLY
This is like isIdenticalTo, except that it ignores the SubclassOptionalData flags,...
Class to represent integer types.
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
A helper class to return the specified delimiter string after the first invocation of operator String...
An instruction for reading from memory.
Analysis pass that exposes the LoopInfo for a function.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within this loop.
BlockT * getHeader() const
unsigned getLoopDepth() const
Return the nesting level of this loop.
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
Represents a single loop in the control flow graph.
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
A Module instance is used to store all the information related to an LLVM module.
unsigned getOpcode() const
Return the opcode for this Instruction or ConstantExpr.
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
bool hasNoSignedWrap() const
Test whether this operation is known to never undergo signed overflow, aka the nsw property.
bool hasNoUnsignedWrap() const
Test whether this operation is known to never undergo unsigned overflow, aka the nuw property.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
PointerIntPair - This class implements a pair of a pointer and small integer.
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
LLVM_ABI void addPredicate(const SCEVPredicate &Pred)
Adds a new predicate.
LLVM_ABI const SCEVPredicate & getPredicate() const
LLVM_ABI const SCEV * getPredicatedSCEV(const SCEV *Expr)
Returns the rewritten SCEV for Expr in the context of the current SCEV predicate.
LLVM_ABI bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2, ArrayRef< const SCEVPredicate * > ExtraPreds={}) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds and ExtraPreds.
LLVM_ABI const SCEVAddRecExpr * getAsAddRec(Value *V, SmallVectorImpl< const SCEVPredicate * > *WrapPredsAdded=nullptr)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
LLVM_ABI void print(raw_ostream &OS, unsigned Depth) const
Print the SCEV mappings done by the Predicated Scalar Evolution.
LLVM_ABI PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L)
LLVM_ABI unsigned getSmallConstantMaxTripCount()
Returns the upper bound of the loop trip count as a normal unsigned value, or 0 if the trip count is ...
LLVM_ABI void addPredicates(ArrayRef< const SCEVPredicate * > Preds)
Adds all predicates in Preds.
LLVM_ABI const SCEV * getBackedgeTakenCount()
Get the (predicated) backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSymbolicMaxBackedgeTakenCount()
Get the (predicated) symbolic max backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
constexpr bool isValid() const
This node represents an addition of some number of SCEVs.
This node represents a polynomial recurrence on the trip count of the specified loop.
friend class ScalarEvolution
LLVM_ABI SCEVUse getExitValue(ScalarEvolution &SE) const
Return the value of this recurrences when its loop exits, i.e.
LLVM_ABI const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
void setNoWrapFlags(SCEVFlags Flags)
Set flags for a recurrence without clearing any previously set flags.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
bool isQuadratic() const
Return true if this represents an expression A + B*x + C*x^2 where A, B and C are loop invariant valu...
LLVM_ABI const SCEV * getNumIterationsInRange(const ConstantRange &Range, ScalarEvolution &SE) const
Return the number of iterations of this loop that produce values in the specified constant range.
LLVM_ABI const SCEVAddRecExpr * getPostIncExpr(ScalarEvolution &SE) const
Return an expression representing the value of this expression one iteration of the loop ahead.
const Loop * getLoop() const
SCEVUse getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
This is the base class for unary cast operator classes.
SCEVUse getOperand() const
LLVM_ABI SCEVCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, SCEVUse op, Type *ty)
void setNoWrapFlags(SCEVFlags Flags)
This class represents an assumption that the expression LHS Pred RHS evaluates to true,...
SCEVComparePredicate(const FoldingSetNodeIDRef ID, const ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Implementation of the SCEVPredicate interface.
This class represents a constant integer value.
ConstantInt * getValue() const
const APInt & getAPInt() const
This is the base class for unary integral cast operator classes.
LLVM_ABI SCEVIntegralCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, SCEVUse op, Type *ty)
This node is the base class min/max selections.
static enum SCEVTypes negate(enum SCEVTypes T)
This node represents multiplication of some number of SCEVs.
This node is a base class providing common functionality for n'ary operators.
bool hasNoUnsignedWrap() const
ArrayRef< SCEVUse > operands() const
SCEVFlags getNoWrapFlags(SCEVFlags Mask=FlagsNoWrapMask) const
bool hasNoSelfWrap() const
size_t getNumOperands() const
bool hasNoSignedWrap() const
SCEVUse getOperand(unsigned i) const
This class represents an assumption made using SCEV expressions which can be checked at run-time.
SCEVPredicate(const SCEVPredicate &)=default
virtual bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const =0
Returns true if this predicate implies N.
This class represents a cast from a pointer to a pointer-sized integer value, without capturing the p...
This visitor recursively visits a SCEV expression and re-writes it.
const SCEV * visitPtrToAddrExpr(const SCEVPtrToAddrExpr *Expr)
const SCEV * visitSignExtendExpr(const SCEVSignExtendExpr *Expr)
const SCEV * visit(const SCEV *S)
const SCEV * visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr)
const SCEV * visitSMinExpr(const SCEVSMinExpr *Expr)
SCEVRewriteVisitor(ScalarEvolution &SE)
const SCEV * visitUMinExpr(const SCEVUMinExpr *Expr)
This 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()
friend class ScalarEvolution
static LoopGuards collectOnDemand(const Loop *L, ScalarEvolution &SE)
Return loop guards for loop L, which are collected on first use.
LLVM_ABI const SCEV * rewrite(const SCEV *Expr) const
Try to apply the collected loop guards to Expr.
The main scalar evolution driver.
LLVM_ABI const SCEV * getUDivExpr(SCEVUse LHS, SCEVUse RHS)
Get a canonical unsigned division expression, or something simpler if possible.
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
const DataLayout & getDataLayout() const
Return the DataLayout associated with the module this SCEV instance is operating on.
LLVM_ABI bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
LLVM_ABI bool isKnownOnEveryIteration(CmpPredicate Pred, const SCEVAddRecExpr *LHS, const SCEV *RHS)
Test if the condition described by Pred, LHS, RHS is known to be true on every iteration of the loop ...
static bool hasFlags(SCEVFlags Flags, SCEVFlags TestFlags)
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterationsImpl(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
LLVM_ABI const SCEV * getZeroExtendExpr(SCEVUse Op, Type *Ty, unsigned Depth=0)
LLVM_ABI const SCEV * getUDivCeilSCEV(const SCEV *N, const SCEV *D)
Compute ceil(N / D).
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterations(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L at given Context duri...
LLVM_ABI Type * getWiderType(Type *Ty1, Type *Ty2) const
LLVM_ABI const SCEV * getAbsExpr(const SCEV *Op, bool IsNSW)
LLVM_ABI bool isKnownNonPositive(const SCEV *S)
Test if the given expression is known to be non-positive.
LLVM_ABI const SCEV * getElementCount(Type *Ty, ElementCount EC, SCEVFlags Flags=SCEV::FlagNone)
LLVM_ABI bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
LLVM_ABI const SCEV * getPredicatedConstantMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getConstantMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
LLVM_ABI const SCEV * removePointerBase(const SCEV *S)
Compute an expression equivalent to S - getPointerBase(S).
LLVM_ABI bool isLoopEntryGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS.
LLVM_ABI bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
LLVM_ABI const SCEV * getURemExpr(SCEVUse LHS, SCEVUse RHS)
Represents an unsigned remainder expression based on unsigned division.
LLVM_ABI const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
LLVM_ABI const SCEV * getSMinExpr(SCEVUse LHS, SCEVUse RHS)
LLVM_ABI const SCEV * getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS)
Promote the operands to the wider of the types using zero-extension, and then perform a umax operatio...
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
LLVM_ABI bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI=nullptr)
Is operation BinOp between LHS and RHS provably does not have a signed/unsigned overflow (Signed)?
LLVM_ABI const SCEV * getMinusSCEV(SCEVUse LHS, SCEVUse RHS, SCEVFlags Flags=SCEV::FlagNone, unsigned Depth=0)
Return LHS-RHS.
LLVM_ABI ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond, bool ExitIfTrue, bool ControlsOnlyExit, bool AllowPredicates=false)
Compute the number of times the backedge of the specified loop will execute if its exit condition wer...
LLVM_ABI const SCEV * getMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< SCEVUse > &Operands)
LLVM_ABI const SCEVPredicate * getEqualPredicate(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
LLVM_ABI SCEVUse getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
LLVM_ABI uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
LLVM_ABI void registerUser(const SCEV *User, ArrayRef< SCEVUse > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
LLVM_ABI const SCEV * getConstant(ConstantInt *V)
LLVM_ABI const SCEV * getPredicatedBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getBackedgeTakenCount, except it will add a set of SCEV predicates to Predicates that are ...
LLVM_ABI const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
LLVM_ABI const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
static SCEVFlags setFlags(SCEVFlags Flags, SCEVFlags OnFlags)
static LLVM_ABI bool isGuaranteedNotToBePoison(const SCEV *Op)
Returns true if Op is guaranteed to not be poison.
bool loopHasNoAbnormalExits(const Loop *L)
Return true if the loop has no abnormal exits.
LLVM_ABI const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)
A version of getTripCountFromExitCount below which always picks an evaluation type which can not resu...
LLVM_ABI ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI)
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
LLVM_ABI const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI void forgetValues(ArrayRef< Value * > Values)
Batched forgetValue: invalidates all Values in one shared def-use walk, avoiding the redundant re-tra...
LLVM_ABI const SCEV * getSequentialMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< SCEVUse > &Operands)
LLVM_ABI const SCEV * getCastExpr(SCEVTypes Kind, SCEVUse Op, Type *Ty)
LLVM_ABI std::optional< bool > evaluatePredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Check whether the condition described by Pred, LHS, and RHS is true or false in the given Context.
LLVM_ABI SCEVUse getAddRecExpr(SCEVUse Start, SCEVUse Step, const Loop *L, SCEVFlagsPair Flags)
Get an add recurrence expression for the specified loop.
LLVM_ABI unsigned getSmallConstantMaxTripCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Returns the upper bound of the loop trip count as a normal unsigned value.
LLVM_ABI bool isKnownMultipleOf(const SCEV *S, uint64_t M, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Check that S is a multiple of M.
LLVM_ABI bool isBackedgeTakenCountMaxOrZero(const Loop *L)
Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCo...
LLVM_ABI void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
LLVM_ABI bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
LLVM_ABI bool isKnownPositive(const SCEV *S)
Test if the given expression is known to be positive.
LLVM_ABI bool SimplifyICmpOperands(CmpPredicate &Pred, SCEVUse &LHS, SCEVUse &RHS, unsigned Depth=0)
Simplify LHS and RHS in a comparison with predicate Pred.
APInt getUnsignedRangeMin(const SCEV *S)
Determine the min of the unsigned range for a particular SCEV.
static SCEVFlags clearFlags(SCEVFlags Flags, SCEVFlags OffFlags)
LLVM_ABI const SCEV * getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo)
Return an expression for offsetof on the given field with type IntTy.
LLVM_ABI LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
static SCEVFlags maskFlags(SCEVFlags Flags, SCEVFlags Mask)
Convenient SCEVFlags manipulation.
LLVM_ABI bool containsAddRecurrence(const SCEV *S)
Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr.
LLVM_ABI const SCEV * getTruncateExpr(SCEVUse Op, Type *Ty, unsigned Depth=0)
LLVM_ABI SCEVUse getAddExpr(SmallVectorImpl< SCEVUse > &Ops, SCEVFlagsPair Flags={}, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
LLVM_ABI const SCEV * getZeroExtendExprImpl(SCEVUse Op, Type *Ty, unsigned Depth=0)
LLVM_ABI bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
LLVM_ABI Type * getEffectiveSCEVType(Type *Ty) const
Return a type with the same bitwidth as the given type and which represents how SCEV will treat the g...
LLVM_ABI const SCEVPredicate * getComparePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
LLVM_ABI bool haveSameSign(const SCEV *S1, const SCEV *S2)
Return true if we know that S1 and S2 must have the same sign.
LLVM_ABI const SCEV * getNotSCEV(const SCEV *V)
Return the SCEV object corresponding to ~V.
LLVM_ABI bool instructionCouldExistWithOperands(const SCEV *A, const SCEV *B)
Return true if there exists a point in the program at which both A and B could be operands to the sam...
LLVM_ABI std::optional< SCEVFlags > getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO)
Parse NSW/NUW flags from add/sub/mul IR binary operation Op into SCEV no-wrap flags,...
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
LLVM_ABI void print(raw_ostream &OS) const
LLVM_ABI const SCEV * getAnyExtendExpr(SCEVUse Op, Type *Ty)
getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the give...
LLVM_ABI const SCEV * getPredicatedExitCount(const Loop *L, const BasicBlock *ExitingBlock, SmallVectorImpl< const SCEVPredicate * > *Predicates, ExitCountKind Kind=Exact)
Same as above except this uses the predicated backedge taken info and may require predicates.
LLVM_ABI void forgetTopmostLoop(const Loop *L)
LLVM_ABI void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
APInt getSignedRangeMin(const SCEV *S)
Determine the min of the signed range for a particular SCEV.
LLVM_ABI bool isLoopUniform(const SCEV *S, const Loop *L)
Returns true if the given SCEV is loop-uniform with respect to the specified loop L.
LLVM_ABI const SCEV * getNoopOrAnyExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
LLVM_ABI const SCEV * getSignExtendExpr(SCEVUse Op, Type *Ty, unsigned Depth=0)
LLVM_ABI const SCEV * getUMaxExpr(SCEVUse LHS, SCEVUse RHS)
@ MonotonicallyDecreasing
@ MonotonicallyIncreasing
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI=nullptr)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L, return a LoopInvaria...
LLVM_ABI const SCEV * getStoreSizeOfExpr(Type *IntTy, Type *StoreTy)
Return an expression for the store size of StoreTy that is type IntTy.
LLVM_ABI const SCEVPredicate * getWrapPredicate(const SCEVAddRecExpr *AR, SCEVWrapPredicate::IncrementWrapFlags AddedFlags)
LLVM_ABI bool isLoopBackedgeGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether the backedge of the loop is protected by a conditional between LHS and RHS.
LLVM_ABI APInt getNonZeroConstantMultiple(const SCEV *S)
const SCEV * getMinusOne(Type *Ty)
Return a SCEV for the constant -1 of a specific type.
LLVM_ABI bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
LLVM_ABI BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB)
Return the "disposition" of the given SCEV with respect to the given block.
LLVM_ABI const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
LLVM_ABI const SCEV * getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
Promote the operands to the wider of the types using zero-extension, and then perform a umin operatio...
LLVM_ABI bool loopIsFiniteByAssumption(const Loop *L)
Return true if this loop is finite by assumption.
LLVM_ABI SCEVUse getSCEVAtExit(const SCEV *S, const Loop *L, const BasicBlock *ExitingBlock)
Return the SCEV expression at the specified loop exit.
LLVM_ABI const SCEV * getExistingSCEV(Value *V)
Return an existing SCEV for V if there is one, otherwise return nullptr.
LLVM_ABI APInt getConstantMultiple(const SCEV *S, const Instruction *CtxI=nullptr)
Returns the max constant multiple of S.
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
@ LoopComputable
The SCEV varies predictably with the loop.
@ LoopVariant
The SCEV is loop-variant (unknown).
@ LoopInvariant
The SCEV is loop-invariant.
@ LoopUniform
The SCEV is loop-uniform.
LLVM_ABI bool isKnownToBeAPowerOfTwo(const SCEV *S, bool OrZero=false, bool OrNegative=false)
Test if the given expression is known to be a power of 2.
LLVM_ABI void forgetLcssaPhiWithNewPredecessor(Loop *L, PHINode *V)
Forget LCSSA phi node V of loop L to which a new predecessor was added, such that it may no longer be...
LLVM_ABI bool containsUndefs(const SCEV *S) const
Return true if the SCEV expression contains an undef value.
LLVM_ABI std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...
LLVM_ABI const SCEV * getCouldNotCompute()
LLVM_ABI bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
LLVM_ABI uint32_t getMinTrailingZeros(const SCEV *S, const Instruction *CtxI=nullptr)
Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration).
BlockDisposition
An enum describing the relationship between a SCEV and a basic block.
@ DominatesBlock
The SCEV dominates the block.
@ ProperlyDominatesBlock
The SCEV properly dominates the block.
@ DoesNotDominateBlock
The SCEV does not dominate the block.
LLVM_ABI const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
LLVM_ABI void getPoisonGeneratingValues(SmallPtrSetImpl< const Value * > &Result, const SCEV *S)
Return the set of Values that, if poison, will definitively result in S being poison as well.
LLVM_ABI void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEVFlags Flags)
Update no-wrap flags of an AddRec.
LLVM_ABI void forgetLoopDispositions()
Called when the client has changed the disposition of values in this loop.
LLVM_ABI const SCEV * getVScale(Type *Ty)
LLVM_ABI SCEVUse getMulExpr(SmallVectorImpl< SCEVUse > &Ops, SCEVFlagsPair Flags={}, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
LLVM_ABI unsigned getSmallConstantTripCount(const Loop *L)
Returns the exact trip count of the loop if we can compute it, and the result is a small constant.
LLVM_ABI bool hasComputableLoopEvolution(const SCEV *S, const Loop *L)
Return true if the given SCEV changes value in a known way in the specified loop.
LLVM_ABI const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
LLVM_ABI void forgetAllLoops()
LLVM_ABI const SCEV * getSignExtendExprImpl(SCEVUse Op, Type *Ty, unsigned Depth=0)
LLVM_ABI bool dominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV dominate the specified basic block.
APInt getUnsignedRangeMax(const SCEV *S)
Determine the max of the unsigned range for a particular SCEV.
ExitCountKind
The terms "backedge taken count" and "exit count" are used interchangeably to refer to the number of ...
@ SymbolicMaximum
An expression which provides an upper bound on the exact trip count.
@ ConstantMaximum
A constant which provides an upper bound on the exact trip count.
@ Exact
An expression exactly describing the number of times the backedge has executed when a loop is exited.
LLVM_ABI bool isKnownPredicate(CmpPredicate Pred, SCEVUse LHS, SCEVUse RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)
Try to apply information from loop guards for L to Expr.
LLVM_ABI const SCEV * getPtrToAddrExpr(const SCEV *Op)
LLVM_ABI const SCEVAddRecExpr * convertSCEVToAddRecWithPredicates(const SCEV *S, const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Preds)
Tries to convert the S expression to an AddRec expression, adding additional predicates to Preds as r...
LLVM_ABI const SCEV * getSMaxExpr(SCEVUse LHS, SCEVUse RHS)
LLVM_ABI const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
LLVM_ABI bool isGuaranteedNotToCauseUB(const SCEV *Op)
Returns true if Op is guaranteed not to cause immediate UB.
LLVM_ABI const SCEV * getSizeOfExpr(Type *IntTy, TypeSize Size)
Return an expression for a TypeSize.
LLVM_ABI std::optional< bool > evaluatePredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Check whether the condition described by Pred, LHS, and RHS is true or false.
LLVM_ABI const SCEV * getUnknown(Value *V)
LLVM_ABI std::optional< std::pair< const SCEV *, SmallVector< const SCEVPredicate *, 3 > > > createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI)
Checks if SymbolicPHI can be rewritten as an AddRecExpr under some Predicates.
LLVM_ABI const SCEV * getTruncateOrZeroExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool isKnownViaInduction(CmpPredicate Pred, SCEVUse LHS, SCEVUse RHS)
We'd like to check the predicate on every iteration of the most dominated loop between loops used in ...
LLVM_ABI std::optional< APInt > computeConstantDifference(const SCEV *LHS, const SCEV *RHS)
Compute LHS - RHS and returns the result as an APInt if it is a constant, and std::nullopt if it isn'...
LLVM_ABI bool properlyDominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
LLVM_ABI const SCEV * getNegativeSCEV(const SCEV *V, SCEVFlags Flags=SCEV::FlagNone)
Return the SCEV object corresponding to -V.
LLVM_ABI const SCEV * getUDivExactExpr(SCEVUse LHS, SCEVUse RHS)
Get a canonical unsigned division expression, or something simpler if possible.
LLVM_ABI const SCEV * rewriteUsingPredicate(const SCEV *S, const Loop *L, const SCEVPredicate &A)
Re-writes the SCEV according to the Predicates in A.
LLVM_ABI std::pair< const SCEV *, const SCEV * > SplitIntoInitAndPostInc(const Loop *L, const SCEV *S)
Splits SCEV expression S into two SCEVs.
LLVM_ABI bool canReuseInstruction(const SCEV *S, Instruction *I, SmallVectorImpl< Instruction * > &DropPoisonGeneratingInsts)
Check whether it is poison-safe to represent the expression S using the instruction I.
LLVM_ABI bool isKnownPredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI const SCEV * getPredicatedSymbolicMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getSymbolicMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
LLVM_ABI ~ScalarEvolution()
LLVM_ABI const SCEV * getGEPExpr(GEPOperator *GEP, ArrayRef< SCEVUse > IndexExprs)
Returns an expression for a GEP.
LLVM_ABI const SCEV * getUMinExpr(SCEVUse LHS, SCEVUse RHS, bool Sequential=false)
LLVM_ABI bool isBasicBlockEntryGuardedByCond(const BasicBlock *BB, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the basic block is protected by a conditional between LHS and RHS.
LLVM_ABI const SCEV * getTruncateOrSignExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool containsErasedValue(const SCEV *S) const
Return true if the SCEV expression contains a Value that has been optimised out and is now a nullptr.
const SCEV * getSymbolicMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEV that is greater than or equal to (i.e.
APInt getSignedRangeMax(const SCEV *S)
Determine the max of the signed range for a particular SCEV.
LLVM_ABI void verify() const
LLVMContext & getContext() const
This class represents the LLVM 'select' instruction.
Implements a dense probed hash-table based set with some number of buckets stored inline.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
iterator insert(iterator I, T &&Elt)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
TypeSize getElementOffset(unsigned Idx) const
TypeSize getSizeInBits() const
Class to represent struct types.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
static LLVM_ABI IntegerType * getInt32Ty(LLVMContext &C)
bool isPointerTy() const
True if this is an instance of PointerType.
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
static LLVM_ABI IntegerType * getIntNTy(LLVMContext &C, unsigned N)
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< user_iterator > users()
unsigned getValueID() const
Return an ID for the concrete type of this object.
LLVM_ABI void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
An efficient, type-erasing, non-owning reference to a callable.
const ParentTy * getParent() const
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be unsigned.
LLVM_ABI std::optional< APInt > SolveQuadraticEquationWrap(APInt A, APInt B, APInt C, unsigned RangeWidth)
Let q(n) = An^2 + Bn + C, and BW = bit width of the value range (e.g.
LLVM_ABI APInt GreatestCommonDivisor(APInt A, APInt B, bool IsSigned=false)
Compute GCD of two APInt values.
const APInt & umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
constexpr bool any(E Val)
@ BasicBlock
Various leaf nodes.
LLVM_ABI Function * getDeclarationIfExists(const Module *M, ID id)
Look up the Function declaration of the intrinsic id in the Module M and return it if it exists.
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
match_combine_or< Ty... > m_CombineOr(const Ty &...Ps)
Combine pattern matchers matching any of Ps patterns.
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
bool match(Val *V, const Pattern &P)
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
auto m_BasicBlock()
Match an arbitrary basic block value and ignore it.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
auto m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
match_bind< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
auto m_Intrinsic(const Ts &...Ops)
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
brc_match< Cond_t, match_bind< BasicBlock >, match_bind< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
CastOperator_match< OpTy, Instruction::PtrToInt > m_PtrToInt(const OpTy &Op)
Matches PtrToInt.
auto m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
bind_cst_ty m_scev_APInt(const APInt *&C)
Match an SCEV constant and bind it to an APInt.
cst_pred_ty< is_all_ones > m_scev_AllOnes()
Match an integer with all bits set.
SCEVUnaryExpr_match< SCEVZeroExtendExpr, Op0_t > m_scev_ZExt(const Op0_t &Op0)
is_undef_or_poison m_scev_UndefOrPoison()
Match an SCEVUnknown wrapping undef or poison.
cst_pred_ty< is_one > m_scev_One()
Match an integer 1.
specificloop_ty m_SpecificLoop(const Loop *L)
SCEVUnaryExpr_match< SCEVSignExtendExpr, Op0_t > m_scev_SExt(const Op0_t &Op0)
match_bind< const SCEVMulExpr > m_scev_Mul(const SCEVMulExpr *&V)
cst_pred_ty< is_zero > m_scev_Zero()
Match an integer 0.
SCEVUnaryExpr_match< SCEVTruncateExpr, Op0_t > m_scev_Trunc(const Op0_t &Op0)
bool match(const SCEV *S, const Pattern &P)
SCEVBinaryExpr_match< SCEVUDivExpr, Op0_t, Op1_t > m_scev_UDiv(const Op0_t &Op0, const Op1_t &Op1)
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< 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