33#if LLVM_ENABLE_ABI_BREAKING_CHECKS
34#define SCEV_DEBUG_WITH_TYPE(TYPE, X) DEBUG_WITH_TYPE(TYPE, X)
36#define SCEV_DEBUG_WITH_TYPE(TYPE, X)
43 cl::desc(
"When performing SCEV expansion only if it is cheap to do, this "
44 "controls the budget that is considered cheap (default = 4)"));
58 NUW = OBO->hasNoUnsignedWrap();
59 NSW = OBO->hasNoSignedWrap();
62 Exact = PEO->isExact();
66 NNeg = PNI->hasNonNeg();
68 NUW = TI->hasNoUnsignedWrap();
69 NSW = TI->hasNoSignedWrap();
79 I->setHasNoUnsignedWrap(
NUW);
80 I->setHasNoSignedWrap(
NSW);
89 I->setHasNoUnsignedWrap(
NUW);
90 I->setHasNoSignedWrap(
NSW);
115 Value *Ret =
nullptr;
120 if (U->getType() != Ty)
129 if (IP->getParent() == CI->
getParent() && &*BIP != CI &&
139 SCEVInsertPointGuard Guard(Builder,
this);
140 Builder.SetInsertPoint(&*IP);
141 Ret = Builder.CreateCast(
Op,
V, Ty,
V->getName());
157 if (
auto MaybeIP =
I->getInsertionPointAfterDef()) {
160 assert(SE.DT.dominates(
I, MustDominate) &&
161 "instruction must dominate the insertion point");
178 while (!WorkList.
empty()) {
187 InsertedValues.erase(
I);
188 InsertedPostIncValues.erase(
I);
190 I->eraseFromParent();
195SCEVExpander::GetOptimalInsertionPointForCastOf(
Value *V)
const {
203 "Expected the cast argument to be a global/constant");
204 return Builder.GetInsertBlock()
207 .getFirstInsertionPt();
215 assert((
Op == Instruction::BitCast ||
216 Op == Instruction::PtrToInt ||
217 Op == Instruction::IntToPtr) &&
218 "InsertNoopCastOfTo cannot perform non-noop casts!");
220 "InsertNoopCastOfTo cannot change sizes!");
227 if (
Op == Instruction::IntToPtr) {
229 if (
DL.isNonIntegralPointerType(PtrTy))
233 if (
Op == Instruction::BitCast) {
234 if (
V->getType() == Ty)
242 if ((
Op == Instruction::PtrToInt ||
Op == Instruction::IntToPtr) &&
243 SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(
V->getType())) {
245 if ((CI->
getOpcode() == Instruction::PtrToInt ||
246 CI->
getOpcode() == Instruction::IntToPtr) &&
247 SE.getTypeSizeInBits(CI->
getType()) ==
251 if ((
CE->getOpcode() == Instruction::PtrToInt ||
252 CE->getOpcode() == Instruction::IntToPtr) &&
253 SE.getTypeSizeInBits(
CE->getType()) ==
254 SE.getTypeSizeInBits(
CE->getOperand(0)->getType()))
255 return CE->getOperand(0);
263 return ReuseOrCreateCast(
V, Ty,
Op, GetOptimalInsertionPointForCastOf(
V));
271 bool IsSafeToHoist) {
279 unsigned ScanLimit = 6;
283 if (IP != BlockBegin) {
285 for (; ScanLimit; --IP, --ScanLimit) {
300 if (IP->getOpcode() == (
unsigned)Opcode && IP->getOperand(0) ==
LHS &&
301 IP->getOperand(1) ==
RHS && !canGenerateIncompatiblePoison(&*IP))
303 if (IP == BlockBegin)
break;
308 DebugLoc Loc = Builder.GetInsertPoint()->getDebugLoc();
309 SCEVInsertPointGuard Guard(Builder,
this);
313 while (
const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
314 if (!
L->isLoopInvariant(
LHS) || !
L->isLoopInvariant(
RHS))
break;
316 if (!Preheader)
break;
324 Builder.SetCurrentDebugLocation(Loc);
329 if (LSRMode && !PostIncLoops.empty() &&
331 return !
L->contains(Builder.GetInsertBlock());
335 BO->setHasNoUnsignedWrap();
337 BO->setHasNoSignedWrap();
338 return Builder.Insert(BO);
340 return Builder.CreateNoWrapBinOp(Opcode,
LHS,
RHS, IsNUW, IsNSW);
377 : GEPNoWrapFlags::
none();
382 return Builder.CreatePtrAdd(CLHS, CRHS,
"", NW);
385 unsigned ScanLimit = 6;
389 if (IP != BlockBegin) {
391 for (; ScanLimit; --IP, --ScanLimit) {
393 if (
GEP->getPointerOperand() ==
V &&
394 GEP->getSourceElementType() == Builder.getInt8Ty() &&
395 GEP->getOperand(1) == Idx) {
397 GEP->setNoWrapFlags(
GEP->getNoWrapFlags() & NW);
401 if (IP == BlockBegin)
break;
406 SCEVInsertPointGuard Guard(Builder,
this);
409 while (
const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
410 if (!
L->isLoopInvariant(
V) || !
L->isLoopInvariant(Idx))
break;
412 if (!Preheader)
break;
419 return Builder.CreatePtrAdd(
V, Idx,
"scevgep", NW);
429 if (
A->contains(
B))
return B;
430 if (
B->contains(
A))
return A;
431 if (DT.
dominates(
A->getHeader(),
B->getHeader()))
return B;
432 if (DT.
dominates(
B->getHeader(),
A->getHeader()))
return A;
438const Loop *SCEVExpander::getRelevantLoop(
const SCEV *S) {
440 auto Pair = RelevantLoops.try_emplace(S);
442 return Pair.first->second;
461 const Loop *
L =
nullptr;
466 return RelevantLoops[S] =
L;
471 return Pair.first->second = SE.LI.getLoopFor(
I->getParent());
487 explicit LoopCompare(DominatorTree &dt) : DT(dt) {}
489 bool operator()(std::pair<const Loop *, SCEVUse>
LHS,
490 std::pair<const Loop *, SCEVUse>
RHS)
const {
497 if (
LHS.first !=
RHS.first)
503 if (
LHS.second->isNonConstantNegative()) {
504 if (!
RHS.second->isNonConstantNegative())
506 }
else if (
RHS.second->isNonConstantNegative())
518 const SCEV *URemLHS =
nullptr;
519 const SCEV *URemRHS =
nullptr;
522 Value *
RHS = expandDivisor(URemRHS);
528 const SCEV *UMaxRHS =
nullptr;
529 const SCEVConstant *
C1, *C2;
535 return Builder.CreateIntrinsic(Intrinsic::usub_sat, {S->getType()},
545 OpsAndLoops.
push_back(std::make_pair(getRelevantLoop(
Op),
Op));
553 Value *Sum =
nullptr;
554 for (
auto I = OpsAndLoops.
begin(),
E = OpsAndLoops.
end();
I !=
E;) {
555 const Loop *CurLoop =
I->first;
564 assert(!
Op->getType()->isPointerTy() &&
"Only first op can be pointer");
569 for (;
I !=
E &&
I->first == CurLoop; ++
I) {
575 X = SE.getSCEV(
U->getValue());
578 Sum = expandAddToGEP(SE.getAddExpr(NewOps), Sum, S.
getNoWrapFlags());
579 }
else if (
Op->isNonConstantNegative()) {
581 Value *
W = expand(SE.getNegativeSCEV(
Op));
601 Type *Ty = S->getType();
603 const SCEVConstant *
C1, *C2;
609 C1 == C2 &&
C1->getAPInt().isPowerOf2()) {
611 unsigned ShAmtC =
C1->getAPInt().logBase2();
614 Value *Res = InsertBinop(Instruction::And,
LHS, ConstantInt::get(Ty, Mask),
622 for (
const SCEV *
Op :
reverse(S->operands()))
623 OpsAndLoops.
push_back(std::make_pair(getRelevantLoop(
Op),
Op));
630 Value *Prod =
nullptr;
631 auto I = OpsAndLoops.
begin();
636 const auto ExpandOpBinPowN = [
this, &
I, &OpsAndLoops]() {
646 while (
E != OpsAndLoops.
end() && *
I == *
E &&
Exponent != MaxExponent) {
650 assert(
Exponent > 0 &&
"Trying to calculate a zeroth exponent of operand?");
669 assert(Result &&
"Nothing was expanded?");
673 while (
I != OpsAndLoops.
end()) {
676 Prod = ExpandOpBinPowN();
677 }
else if (
I->second->isAllOnesValue()) {
684 Value *
W = ExpandOpBinPowN();
693 if (
RHS->logBase2() ==
RHS->getBitWidth() - 1)
695 Prod = InsertBinop(Instruction::Shl, Prod,
696 ConstantInt::get(Ty,
RHS->logBase2()), NWFlags,
711 const APInt &
RHS = SC->getAPInt();
712 if (
RHS.isPowerOf2())
713 return InsertBinop(Instruction::LShr,
LHS,
714 ConstantInt::get(SC->getType(),
RHS.logBase2()),
718 Value *
RHS = expandDivisor(S->getRHS());
720 SE.isKnownNonZero(S->getRHS()));
723Value *SCEVExpander::expandDivisor(
const SCEV *Divisor) {
724 Value *
V = expand(Divisor);
725 if (!SafeDivisorMode)
728 bool GuaranteedNotPoison =
730 if (!GuaranteedNotPoison)
731 V = Builder.CreateFreeze(
V);
736 if (!SE.isKnownNonZero(Divisor) || !GuaranteedNotPoison)
737 V = Builder.CreateIntrinsic(
V->getType(), Intrinsic::umax,
738 {V, ConstantInt::get(V->getType(), 1)});
752 if (L == IVIncInsertLoop) {
755 if (!SE.DT.dominates(OInst, IVIncInsertPos))
769 return isNormalAddRecExprPHI(PN, IncV, L);
784 if (IncV == InsertPos)
791 case Instruction::Add:
792 case Instruction::Sub: {
794 if (!OInst || SE.DT.dominates(OInst, InsertPos))
798 case Instruction::BitCast:
800 case Instruction::GetElementPtr:
805 if (!SE.DT.dominates(OInst, InsertPos))
831 if (Builder.GetInsertPoint() == It)
832 Builder.SetInsertPoint(&*NewInsertPt);
833 for (
auto *InsertPtGuard : InsertPointGuards)
834 if (InsertPtGuard->GetInsertPoint() == It)
835 InsertPtGuard->SetInsertPoint(NewInsertPt);
842 bool RecomputePoisonFlags) {
847 I->dropPoisonGeneratingFlags();
849 if (
auto Flags = SE.getStrengthenedNoWrapFlagsFromBinOp(OBO)) {
851 BO->setHasNoUnsignedWrap(
853 BO->setHasNoSignedWrap(
858 if (SE.DT.dominates(IncV, InsertPos)) {
859 if (RecomputePoisonFlags)
860 FixupPoisonFlags(IncV);
870 if (!SE.LI.movementPreservesLCSSAForm(IncV, InsertPos))
882 if (SE.DT.dominates(IncV, InsertPos))
886 fixupInsertPoints(
I);
888 if (RecomputePoisonFlags)
911 (IVOper =
getIVIncOperand(IVOper, L->getLoopPreheader()->getTerminator(),
928 IncV = Builder.CreatePtrAdd(PN, StepV,
"scevgep");
931 Builder.CreateSub(PN, StepV, Twine(IVName) +
".iv.next") :
932 Builder.CreateAdd(PN, StepV, Twine(IVName) +
".iv.next");
944 Type *PhiTy = Phi->getType();
958 if (Phi == Requested) {
976SCEVExpander::getAddRecExprPHILiterally(
const SCEVAddRecExpr *Normalized,
979 assert((!IVIncInsertLoop || IVIncInsertPos) &&
980 "Uninitialized insert position");
985 PHINode *AddRecPhiMatch =
nullptr;
992 bool TryNonMatchingSCEV =
994 SE.DT.properlyDominates(LatchBlock, IVIncInsertLoop->getHeader());
996 for (PHINode &PN :
L->getHeader()->phis()) {
997 if (!SE.isSCEVable(PN.
getType()))
1004 DebugType,
dbgs() <<
"One incomplete PHI is found: " << PN <<
"\n");
1012 bool IsMatchingSCEV = PhiSCEV == Normalized;
1016 if (!IsMatchingSCEV && !TryNonMatchingSCEV)
1027 if (!isExpandedAddRecExprPHI(&PN, TempIncV, L))
1030 if (!isNormalAddRecExprPHI(&PN, TempIncV, L))
1035 if (IsMatchingSCEV) {
1039 AddRecPhiMatch = &PN;
1045 if ((!TruncTy || InvertStep) &&
1049 AddRecPhiMatch = &PN;
1051 TruncTy = Normalized->
getType();
1055 if (AddRecPhiMatch) {
1058 InsertedValues.insert(AddRecPhiMatch);
1060 rememberInstruction(IncV);
1062 ReusedValues.insert(AddRecPhiMatch);
1063 ReusedValues.insert(IncV);
1064 return AddRecPhiMatch;
1069 SCEVInsertPointGuard Guard(Builder,
this);
1079 PostIncLoops.
clear();
1082 assert(
L->getLoopPreheader() &&
1083 "Can't expand add recurrences without a loop preheader!");
1085 expand(Normalized->
getStart(),
L->getLoopPreheader()->getTerminator());
1102 Step = SE.getNegativeSCEV(Step);
1104 Value *StepV = expand(Step,
L->getHeader()->getFirstInsertionPt());
1108 bool CanHaveNoWrap = !useSubtract && ExpandTy->
isIntegerTy();
1109 bool IncrementIsNUW =
1111 SE.willNotOverflow(Instruction::Add,
false, Normalized, Step);
1112 bool IncrementIsNSW =
1114 SE.willNotOverflow(Instruction::Add,
true, Normalized, Step);
1118 Builder.SetInsertPoint(Header->begin());
1120 Builder.CreatePHI(ExpandTy,
pred_size(Header), Twine(IVName) +
".iv");
1125 if (!
L->contains(
Pred)) {
1134 IVIncInsertPos :
Pred->getTerminator();
1135 Builder.SetInsertPoint(InsertPos);
1136 Value *IncV = expandIVInc(PN, StepV, L, useSubtract);
1149 PostIncLoops = SavedPostIncLoops;
1153 InsertedValues.
insert(PN);
1154 InsertedIVs.push_back(PN);
1160 const Loop *
L = S->getLoop();
1164 const SCEVAddRecExpr *Normalized = S;
1165 if (PostIncLoops.count(L)) {
1172 [[maybe_unused]]
const SCEV *
Start = Normalized->
getStart();
1174 assert(SE.properlyDominates(Start,
L->getHeader()) &&
1175 "Start does not properly dominate loop header");
1176 assert(SE.dominates(Step,
L->getHeader()) &&
"Step not dominate loop header");
1180 Type *TruncTy =
nullptr;
1181 bool InvertStep =
false;
1182 PHINode *PN = getAddRecExprPHILiterally(Normalized, L, TruncTy, InvertStep);
1186 if (!PostIncLoops.count(L))
1191 assert(LatchBlock &&
"PostInc mode requires a unique loop latch!");
1199 if (!S->hasNoUnsignedWrap())
1200 I->setHasNoUnsignedWrap(
false);
1201 if (!S->hasNoSignedWrap())
1202 I->setHasNoSignedWrap(
false);
1210 &*Builder.GetInsertPoint())) {
1223 Step = SE.getNegativeSCEV(Step);
1227 SCEVInsertPointGuard Guard(Builder,
this);
1228 StepV = expand(Step,
L->getHeader()->getFirstInsertionPt());
1230 Result = expandIVInc(PN, StepV, L, useSubtract);
1237 if (TruncTy !=
Result->getType() || InvertStep)
1238 Result = fixupLCSSAFormFor(Result);
1240 if (TruncTy !=
Result->getType())
1241 Result = Builder.CreateTrunc(Result, TruncTy);
1245 Result = Builder.CreateSub(expand(Normalized->
getStart()), Result);
1251std::pair<PHINode *, const SCEV *>
1255 Type *STy = S->getType();
1256 const Loop *L = S->getLoop();
1259 return {
nullptr,
nullptr};
1263 auto CanReuse = [&](
const SCEV *ExitSCEV) ->
const SCEV * {
1266 const SCEV *Diff = SE.getMinusSCEV(S, ExitSCEV);
1276 for (
auto &PN : EB->
phis()) {
1277 if (!SE.isSCEVable(PN.
getType()))
1279 auto *ExitSCEV = SE.getSCEV(&PN);
1283 const SCEV *Diff =
nullptr;
1285 SE.getDataLayout().getAddressType(PhiTy) == STy) {
1286 const SCEV *AddrSCEV = SE.getPtrToAddrExpr(ExitSCEV);
1287 Diff = CanReuse(AddrSCEV);
1288 }
else if (STy == PhiTy) {
1289 Diff = CanReuse(ExitSCEV);
1295 "difference must be of integer type");
1299 return {
nullptr,
nullptr};
1307 Value *BaseV = fixupLCSSAFormFor(PN);
1309 if (S->getType()->isPointerTy())
1310 return Builder.CreatePtrAdd(BaseV, DiffV);
1311 BaseV = Builder.CreatePtrToAddr(BaseV);
1313 return Builder.CreateAdd(BaseV, DiffV);
1326 if (!CanonicalMode || (S->getNumOperands() > 2))
1327 return expandAddRecExprLiterally(S);
1329 Type *Ty = SE.getEffectiveSCEVType(S->getType());
1330 const Loop *
L = S->getLoop();
1333 PHINode *CanonicalIV =
nullptr;
1334 if (PHINode *PN =
L->getCanonicalInductionVariable())
1335 if (SE.getTypeSizeInBits(PN->
getType()) >= SE.getTypeSizeInBits(Ty))
1341 SE.getTypeSizeInBits(CanonicalIV->
getType()) > SE.getTypeSizeInBits(Ty) &&
1342 !S->getType()->isPointerTy()) {
1344 for (
unsigned i = 0, e = S->getNumOperands(); i != e; ++i)
1345 NewOps[i] = SE.getAnyExtendExpr(S->getOperand(i), CanonicalIV->
getType());
1350 &*Builder.GetInsertPoint())
1351 : Builder.GetInsertPoint();
1352 V = expand(SE.getTruncateExpr(SE.getUnknown(
V), Ty), NewInsertPt);
1358 if (
Value *
V = tryToReuseLCSSAPhi(S))
1363 Value *StartV = expand(SE.getPointerBase(S));
1364 return expandAddToGEP(SE.removePointerBase(S), StartV,
1369 if (!S->getStart()->isZero()) {
1370 const SCEV *Rest = SE.getAddRecExpr(SE.getZero(Ty), S->getOperand(1), L,
1377 const SCEV *AddExprLHS = SE.getUnknown(expand(S->getStart()));
1378 const SCEV *AddExprRHS = SE.getUnknown(expand(Rest));
1379 return expand(SE.getAddExpr(AddExprLHS, AddExprRHS));
1390 rememberInstruction(CanonicalIV);
1392 SmallPtrSet<BasicBlock *, 4> PredSeen;
1393 Constant *One = ConstantInt::get(Ty, 1);
1396 if (!PredSeen.
insert(HP).second) {
1403 if (
L->contains(HP)) {
1410 rememberInstruction(
Add);
1419 return expand(SE.getMulExpr(SE.getUnknown(CanonicalIV), S->getOperand(1)));
1428 if (CI->
getOpcode() == CastInst::PtrToAddr)
1430 if (CI->
getOpcode() != CastInst::PtrToInt)
1433 return DL.getPointerSizeInBits(AS) ==
DL.getIndexSizeInBits(AS);
1454 Type *Ty = S->getType();
1460 return &*BIP != CI && SE.DT.
dominates(CI, &*BIP);
1464 return ReuseOrCreateCast(
V, Ty, CastInst::PtrToAddr,
1465 GetOptimalInsertionPointForCastOf(
V));
1469 Type *Ty = S->getType();
1475 Value *PtrOp = expand(PtrToAddr->getOperand());
1478 for (User *U : PtrOp->
users()) {
1480 if (CI && CI->
getType() == Ty &&
1481 CI->
getOpcode() == CastInst::PtrToInt && &*BIP != CI &&
1482 SE.DT.dominates(CI, &*BIP))
1488 Value *
V = expand(S->getOperand());
1489 return Builder.CreateTrunc(
V, S->getType());
1494 Value *
V = expand(S->getOperand());
1495 return Builder.CreateZExt(
V, S->getType(),
"",
1496 SE.isKnownNonNegative(S->getOperand()));
1501 Value *
V = expand(S->getOperand());
1502 return Builder.CreateSExt(
V, S->getType());
1507 bool IsSequential) {
1508 bool PrevSafeMode = SafeDivisorMode;
1509 SafeDivisorMode |= IsSequential;
1510 Value *
LHS = expand(S->getOperand(S->getNumOperands() - 1));
1513 LHS = Builder.CreateFreeze(
LHS);
1514 for (
int i = S->getNumOperands() - 2; i >= 0; --i) {
1515 SafeDivisorMode = (IsSequential && i != 0) || PrevSafeMode;
1516 Value *
RHS = expand(S->getOperand(i));
1517 if (IsSequential && i != 0)
1518 RHS = Builder.CreateFreeze(
RHS);
1521 Sel = Builder.CreateIntrinsic(IntrinID, {Ty}, {
LHS,
RHS},
1526 Sel = Builder.CreateSelectWithUnknownProfile(ICmp,
LHS,
RHS,
1527 "scev-expander", Name);
1531 SafeDivisorMode = PrevSafeMode;
1536 return expandMinMaxExpr(S, Intrinsic::smax,
"smax");
1540 return expandMinMaxExpr(S, Intrinsic::umax,
"umax");
1544 return expandMinMaxExpr(S, Intrinsic::smin,
"smin");
1548 return expandMinMaxExpr(S, Intrinsic::umin,
"umin");
1551Value *SCEVExpander::visitSequentialUMinExpr(
1553 return expandMinMaxExpr(S, Intrinsic::umin,
"umin",
1558 return Builder.CreateVScale(S->getType());
1569 Value *V = expand(SH);
1571 if (Ty && Ty != V->getType()) {
1572 assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->
getType()) &&
1573 "non-trivial casts should be done with the SCEVs directly!");
1574 V = InsertNoopCastOfTo(V, Ty);
1579Value *SCEVExpander::FindValueInExprValueMap(
1591 for (
Value *V : SE.getSCEVValues(S)) {
1608 DropPoisonGeneratingInsts.
clear();
1613Value *SCEVExpander::findExistingExpansionAndDropPoisonFlags(
1615 SmallVector<Instruction *> DropPoisonGeneratingInsts;
1616 Value *
V = FindValueInExprValueMap(S, InsertPt, DropPoisonGeneratingInsts);
1619 for (Instruction *
I : DropPoisonGeneratingInsts) {
1640 auto SafeToHoist = [](
const SCEV *S) {
1645 return SC->getValue()->isZero();
1655 if (SafeToHoist(S)) {
1656 for (
Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock());;
1657 L =
L->getParentLoop()) {
1658 if (SE.isLoopInvariant(S, L)) {
1660 if (BasicBlock *Preheader =
L->getLoopPreheader()) {
1666 InsertPt =
L->getHeader()->getFirstInsertionPt();
1672 if (L && SE.hasComputableLoopEvolution(S, L) && !PostIncLoops.count(L))
1673 InsertPt =
L->getHeader()->getFirstInsertionPt();
1675 while (InsertPt != Builder.GetInsertPoint() &&
1677 InsertPt = std::next(InsertPt);
1685 auto I = InsertedExpressions.find(std::make_pair(S, &*InsertPt));
1686 if (
I != InsertedExpressions.end())
1689 SCEVInsertPointGuard Guard(Builder,
this);
1690 Builder.SetInsertPoint(InsertPt);
1693 Value *
V = findExistingExpansionAndDropPoisonFlags(S, &*InsertPt);
1695 if (!
V && InsertPt != OrigInsertPt && PostIncLoops.empty()) {
1699 V = findExistingExpansionAndDropPoisonFlags(S, &*OrigInsertPt);
1701 CacheAt = OrigInsertPt;
1705 V = fixupLCSSAFormFor(
V);
1713 InsertedExpressions[std::make_pair(S, &*CacheAt)] =
V;
1717void SCEVExpander::rememberInstruction(
Value *
I) {
1718 auto DoInsert = [
this](
Value *
V) {
1719 if (!PostIncLoops.empty())
1720 InsertedPostIncValues.insert(
V);
1722 InsertedValues.insert(
V);
1729 OrigFlags.try_emplace(
I, PoisonFlags(
I));
1734 I->dropPoisonGeneratingAnnotations();
1738 if (SE.isSCEVable(OBO->getType()))
1739 if (
auto Flags = SE.getStrengthenedNoWrapFlagsFromBinOp(OBO)) {
1741 BO->setHasNoUnsignedWrap(
1743 BO->setHasNoSignedWrap(
1747 auto *Src = NNI->getOperand(0);
1752 NNI->setNonNeg(
true);
1756void SCEVExpander::replaceCongruentIVInc(
1767 if (!OrigInc || !IsomorphicInc)
1773 if (OrigPhi->
getType() == Phi->getType()) {
1774 bool Chained = ChainedPhis.contains(Phi);
1775 if (!(Chained || isExpandedAddRecExprPHI(OrigPhi, OrigInc, L)) &&
1776 (Chained || isExpandedAddRecExprPHI(Phi, IsomorphicInc, L))) {
1791 const SCEV *TruncExpr =
1792 SE.getTruncateOrNoop(SE.getSCEV(OrigInc), IsomorphicInc->
getType());
1793 if (OrigInc == IsomorphicInc || TruncExpr != SE.getSCEV(IsomorphicInc) ||
1794 !SE.LI.replacementPreservesLCSSAForm(IsomorphicInc, OrigInc))
1797 bool BothHaveNUW =
false;
1798 bool BothHaveNSW =
false;
1801 if (OBOIncV && OBOIsomorphic) {
1803 OBOIncV->hasNoUnsignedWrap() && OBOIsomorphic->hasNoUnsignedWrap();
1805 OBOIncV->hasNoSignedWrap() && OBOIsomorphic->hasNoSignedWrap();
1818 "Should only replace an increment with a wider one.");
1819 if (BothHaveNUW || BothHaveNSW) {
1825 dbgs() <<
"INDVARS: Eliminated congruent iv.inc: "
1826 << *IsomorphicInc <<
'\n');
1827 Value *NewInc = OrigInc;
1831 IP = PN->
getParent()->getFirstInsertionPt();
1836 Builder.SetCurrentDebugLocation(IsomorphicInc->
getDebugLoc());
1838 Builder.CreateTruncOrBitCast(OrigInc, IsomorphicInc->
getType(), IVName);
1863 if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy())
1864 return RHS->getType()->isIntegerTy() && !LHS->getType()->isIntegerTy();
1865 return RHS->getType()->getPrimitiveSizeInBits().getFixedValue() <
1866 LHS->getType()->getPrimitiveSizeInBits().getFixedValue();
1869 unsigned NumElim = 0;
1877 if (!SE.isSCEVable(PN->
getType()))
1882 return Const->getValue();
1887 if (
Value *V = SimplifyPHINode(Phi)) {
1888 if (V->getType() != Phi->getType())
1890 SE.forgetValue(Phi);
1891 Phi->replaceAllUsesWith(V);
1895 dbgs() <<
"INDVARS: Eliminated constant iv: " << *Phi
1900 if (!SE.isSCEVable(Phi->getType()))
1903 PHINode *&OrigPhiRef = ExprToIVMap[SE.getSCEV(Phi)];
1906 if (Phi->getType()->isIntegerTy() &&
TTI &&
1907 TTI->isTruncateFree(Phi->getType(), Phis.
back()->getType())) {
1911 const SCEV *PhiExpr = SE.getSCEV(Phi);
1915 const SCEV *TruncExpr =
1916 SE.getTruncateExpr(PhiExpr, Phis.
back()->getType());
1917 ExprToIVMap[TruncExpr] = Phi;
1928 replaceCongruentIVInc(Phi, OrigPhiRef, L, DT, DeadInsts);
1930 dbgs() <<
"INDVARS: Eliminated congruent iv: " << *Phi
1933 DebugType,
dbgs() <<
"INDVARS: Original iv: " << *OrigPhiRef <<
'\n');
1935 Value *NewIV = OrigPhiRef;
1936 if (OrigPhiRef->
getType() != Phi->getType()) {
1937 IRBuilder<> Builder(L->getHeader()->getFirstInsertionPt());
1938 Builder.SetCurrentDebugLocation(Phi->getDebugLoc());
1939 NewIV = Builder.CreateTruncOrBitCast(OrigPhiRef, Phi->getType(), IVName);
1941 Phi->replaceAllUsesWith(NewIV);
1953 L->getExitingBlocks(ExitingBlocks);
1960 if (!
match(BB->getTerminator(),
1965 if (SE.getSCEV(LHS) == S && SE.DT.dominates(LHS, At))
1968 if (SE.getSCEV(RHS) == S && SE.DT.dominates(RHS, At))
1977 return FindValueInExprValueMap(S, At, DropPoisonGeneratingInsts) !=
nullptr;
1988 struct OperationIndices {
1989 OperationIndices(
unsigned Opc,
size_t min,
size_t max) :
1990 Opcode(
Opc), MinIdx(
min), MaxIdx(
max) { }
2003 return TTI.getCastInstrCost(Opcode, S->getType(),
2004 S->getOperand(0)->getType(),
2008 auto ArithCost = [&](
unsigned Opcode,
unsigned NumRequired,
2009 unsigned MinIdx = 0,
2012 return NumRequired *
2013 TTI.getArithmeticInstrCost(Opcode, S->getType(), CostKind);
2016 auto CmpSelCost = [&](
unsigned Opcode,
unsigned NumRequired,
unsigned MinIdx,
2019 Type *OpType = S->getType();
2020 return NumRequired *
TTI.getCmpSelInstrCost(
2025 switch (S->getSCEVType()) {
2033 Cost = CastCost(Instruction::PtrToAddr);
2036 Cost = CastCost(Instruction::Trunc);
2039 Cost = CastCost(Instruction::ZExt);
2042 Cost = CastCost(Instruction::SExt);
2045 unsigned Opcode = Instruction::UDiv;
2047 if (SC->getAPInt().isPowerOf2())
2048 Opcode = Instruction::LShr;
2049 Cost = ArithCost(Opcode, 1);
2053 Cost = ArithCost(Instruction::Add, S->getNumOperands() - 1);
2064 unsigned OpCode = Instruction::Mul;
2065 if (S->getNumOperands() == 2)
2067 if (SC->getAPInt().isAllOnes())
2068 OpCode = Instruction::Sub;
2069 else if (SC->getAPInt().isPowerOf2())
2070 OpCode = Instruction::Shl;
2072 Cost = ArithCost(OpCode, S->getNumOperands() - 1);
2082 Cost += CmpSelCost(Instruction::ICmp, S->getNumOperands() - 1, 0, 1);
2083 Cost += CmpSelCost(Instruction::Select, S->getNumOperands() - 1, 0, 2);
2084 switch (S->getSCEVType()) {
2088 Cost += CmpSelCost(Instruction::ICmp, S->getNumOperands() - 1, 0, 0);
2089 Cost += ArithCost(Instruction::Or,
2090 S->getNumOperands() > 2 ? S->getNumOperands() - 2 : 0);
2091 Cost += CmpSelCost(Instruction::Select, 1, 0, 1);
2096 "Unhandled SCEV expression type?");
2103 unsigned NumRecurrences = S->getNumOperands() - 1;
2104 Cost +=
TTI.getCFInstrCost(Instruction::PHI, CostKind) * NumRecurrences;
2106 TTI.getArithmeticInstrCost(Instruction::Add, S->getType(), CostKind) *
2109 Worklist.
emplace_back(Instruction::PHI, 0, S->getOperand(0));
2111 for (
const SCEV *
Op : S->operands().drop_front())
2117 for (
auto &CostOp : Operations) {
2118 for (
auto SCEVOp :
enumerate(S->operands())) {
2120 size_t MinIdx = std::max(SCEVOp.index(), CostOp.MinIdx);
2121 size_t OpIdx = std::min(MinIdx, CostOp.MaxIdx);
2122 Worklist.
emplace_back(CostOp.Opcode, OpIdx, SCEVOp.value());
2128bool SCEVExpander::isHighCostExpansionHelper(
2136 const SCEV *S = WorkItem.
S;
2147 L->getHeader()->getParent()->hasMinSize()
2166 return Cost > Budget;
2186 SE.getAddExpr(S, SE.getConstant(S->
getType(), 1)), &At, L))
2201 "Nary expr should have more than 1 operand.");
2206 return Cost > Budget;
2210 "Polynomial should be at least linear");
2212 WorkItem,
TTI, CostKind, Worklist);
2213 return Cost > Budget;
2222 switch (Pred->getKind()) {
2237 Value *Expr0 = expand(Pred->getLHS(), IP);
2238 Value *Expr1 = expand(Pred->getRHS(), IP);
2240 Builder.SetInsertPoint(IP);
2242 auto *
I = Builder.CreateICmp(InvPred, Expr0, Expr1,
"ident.check");
2249 "non-affine expression");
2253 const SCEV *ExitCount =
2254 SE.getPredicatedSymbolicMaxBackedgeTakenCount(AR->
getLoop(), Pred);
2262 unsigned SrcBits = SE.getTypeSizeInBits(ExitCount->
getType());
2263 unsigned DstBits = SE.getTypeSizeInBits(ARTy);
2270 Builder.SetInsertPoint(
Loc);
2271 Value *TripCountVal = expand(ExitCount,
Loc);
2276 Value *StepValue = expand(Step,
Loc);
2277 Value *NegStepValue = expand(SE.getNegativeSCEV(Step),
Loc);
2278 Value *StartValue = expand(Start,
Loc);
2283 Builder.SetInsertPoint(
Loc);
2286 Value *AbsStep = Builder.CreateSelectWithUnknownProfile(
2287 StepCompare, NegStepValue, StepValue,
"scev-expander");
2297 auto ComputeEndCheck = [&]() ->
Value * {
2299 Value *MulV, *OfMul;
2300 auto Key = std::make_tuple(TripCountVal, AbsStep,
Loc);
2301 auto I = InsertedOverflowChecks.find(
Key);
2302 if (
I != InsertedOverflowChecks.end()) {
2303 MulV =
I->second.first;
2304 OfMul =
I->second.second;
2307 Value *TruncTripCount = Builder.CreateZExtOrTrunc(TripCountVal, Ty);
2308 Value *
Mul = Builder.CreateIntrinsic(Intrinsic::umul_with_overflow, Ty,
2309 {AbsStep, TruncTripCount},
2311 MulV = Builder.CreateExtractValue(
Mul, 0,
"mul.result");
2312 OfMul = Builder.CreateExtractValue(
Mul, 1,
"mul.overflow");
2315 InsertedOverflowChecks[
Key] = {MulV, OfMul};
2319 bool NeedPosCheck = !SE.isKnownNegative(Step);
2320 bool NeedNegCheck = !SE.isKnownPositive(Step);
2323 Value *NegMulV = Builder.CreateNeg(MulV);
2325 Add = Builder.CreatePtrAdd(StartValue, MulV);
2327 Sub = Builder.CreatePtrAdd(StartValue, NegMulV);
2330 Add = Builder.CreateAdd(StartValue, MulV);
2332 Sub = Builder.CreateSub(StartValue, MulV);
2335 Value *EndCompareLT =
nullptr;
2336 Value *EndCompareGT =
nullptr;
2337 Value *EndCheck =
nullptr;
2339 EndCheck = EndCompareLT = Builder.CreateICmp(
2342 EndCheck = EndCompareGT = Builder.CreateICmp(
2344 if (NeedPosCheck && NeedNegCheck) {
2346 EndCheck = Builder.CreateSelectWithUnknownProfile(
2347 StepCompare, EndCompareGT, EndCompareLT,
"scev-expander");
2349 return Builder.CreateOr(EndCheck, OfMul);
2351 Value *EndCheck = ComputeEndCheck();
2356 if (SrcBits > DstBits) {
2358 auto *BackedgeCheck =
2360 ConstantInt::get(
Loc->getContext(), MaxVal));
2361 BackedgeCheck = Builder.CreateAnd(
2364 EndCheck = Builder.CreateOr(EndCheck, BackedgeCheck);
2373 Value *NSSWCheck =
nullptr, *NUSWCheck =
nullptr;
2383 if (NUSWCheck && NSSWCheck)
2384 return Builder.CreateOr(NUSWCheck, NSSWCheck);
2399 for (
const auto *Pred : Union->getPredicates()) {
2401 Builder.SetInsertPoint(IP);
2406 return Builder.CreateOr(Checks);
2409Value *SCEVExpander::fixupLCSSAFormFor(
Value *V) {
2411 if (!PreserveLCSSA || !DefI)
2417 if (!DefLoop || UseLoop == DefLoop || DefLoop->
contains(UseLoop))
2428 if (DefI->getType()->isIntegerTy())
2442 for (
PHINode *PN : InsertedPHIs)
2443 rememberInstruction(PN);
2444 for (
PHINode *PN : PHIsToRemove) {
2447 InsertedValues.erase(PN);
2448 InsertedPostIncValues.erase(PN);
2452 return User->getOperand(0);
2474struct SCEVFindUnsafe {
2475 ScalarEvolution &SE;
2477 bool IsUnsafe =
false;
2479 SCEVFindUnsafe(ScalarEvolution &SE,
bool CanonicalMode)
2480 : SE(SE), CanonicalMode(CanonicalMode) {}
2482 bool follow(
const SCEV *S) {
2493 if (!AR->getLoop()->getLoopPreheader() &&
2494 (!CanonicalMode || !AR->isAffine())) {
2501 bool isDone()
const {
return IsUnsafe; }
2506 SCEVFindUnsafe Search(SE, CanonicalMode);
2508 return !Search.IsUnsafe;
2539 for (
auto [
I, Flags] : Expander.OrigFlags)
2542 auto InsertedInstructions = Expander.getAllInsertedInstructions();
2545 InsertedInstructions);
2555 [&InsertedSet](
Value *U) {
2556 return InsertedSet.contains(cast<Instruction>(U));
2558 "removed instruction should only be used by instructions inserted "
2559 "during expansion");
2561 assert(!
I->getType()->isVoidTy() &&
2562 "inserted instruction should have non-void types");
2564 I->eraseFromParent();
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
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")
static Expected< BitVector > expand(StringRef S, StringRef Original)
This file contains the declarations for profiling metadata utility functions.
static const Loop * PickMostRelevantLoop(const Loop *A, const Loop *B, DominatorTree &DT)
PickMostRelevantLoop - Given two loops pick the one that's most relevant for SCEV expansion.
static InstructionCost costAndCollectOperands(const SCEVOperand &WorkItem, const TargetTransformInfo &TTI, TargetTransformInfo::TargetCostKind CostKind, SmallVectorImpl< SCEVOperand > &Worklist)
static bool canBeCheaplyTransformed(ScalarEvolution &SE, const SCEVAddRecExpr *Phi, const SCEVAddRecExpr *Requested, bool &InvertStep)
Check whether we can cheaply express the requested SCEV in terms of the available PHI SCEV by truncat...
#define SCEV_DEBUG_WITH_TYPE(TYPE, X)
static bool canReuseCastForPtrToAddr(const CastInst *CI, Type *Ty, const DataLayout &DL)
Return true if CI computes the same value as a ptrtoaddr of its pointer operand to Ty.
This file defines the scope_exit class, which executes user-defined cleanup logic at scope exit.
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
static APInt getBitsSetFrom(unsigned numBits, unsigned loBit)
Constructs an APInt value that has a contiguous range of bits set.
LLVM Basic Block Representation.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
InstListType::iterator iterator
Instruction iterators...
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
static LLVM_ABI BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), InsertPosition InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
This is the base class for all instructions that perform data casts.
Type * getSrcTy() const
Return the source type, as a convenience.
static LLVM_ABI Instruction::CastOps getCastOpcode(const Value *Val, bool SrcIsSigned, Type *Ty, bool DstIsSigned)
Returns the opcode necessary to cast Val into Ty using usual casting rules.
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
static LLVM_ABI CastInst * CreateBitOrPointerCast(Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Create a BitCast, a PtrToInt, or an IntToPTr cast instruction.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
@ ICMP_SLT
signed less than
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
@ ICMP_SGE
signed greater or equal
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
static LLVM_ABI Constant * getCast(unsigned ops, Constant *C, Type *Ty, bool OnlyIfReduced=false)
Convenience function for getting a Cast operation.
This is the shared class of boolean and integer constants.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
A parsed version of the target data layout string in and methods for querying it.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
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.
static GEPNoWrapFlags noUnsignedWrap()
static GEPNoWrapFlags none()
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
LLVM_ABI void setHasNoUnsignedWrap(bool b=true)
Set or clear the nuw flag on this instruction, which must be an operator which supports this flag.
LLVM_ABI void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_ABI void insertBefore(InstListType::iterator InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified position.
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
LLVM_ABI const Function * getFunction() const
Return the function this instruction belongs to.
LLVM_ABI bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
LLVM_ABI bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
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.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within this loop.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Represents a single loop in the control flow graph.
ICmpInst::Predicate getPredicate() const
Returns the comparison predicate underlying the intrinsic.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
bool isComplete() const
If the PHI node is complete which means all of its parent's predecessors have incoming value in this ...
Value * getIncomingValueForBlock(const BasicBlock *BB) const
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static LLVM_ABI PointerType * get(LLVMContext &C, unsigned AddressSpace)
This constructs an opaque pointer to an object in a numbered address space.
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
This node represents a polynomial recurrence on the trip count of the specified loop.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
const Loop * getLoop() const
SCEVUse getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
This class represents an assumption that the expression LHS Pred RHS evaluates to true,...
ConstantInt * getValue() const
const APInt & getAPInt() const
LLVM_ABI Value * generateOverflowCheck(const SCEVAddRecExpr *AR, Instruction *Loc, bool Signed)
Generates code that evaluates if the AR expression will overflow.
LLVM_ABI bool hasRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L)
Determine whether there is an existing expansion of S that can be reused.
SmallVector< Instruction *, 32 > getAllInsertedInstructions() const
Return a vector containing all instructions inserted during expansion.
LLVM_ABI bool isSafeToExpand(const SCEV *S) const
Return true if the given expression is safe to expand in the sense that all materialized values are s...
LLVM_ABI bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint) const
Return true if the given expression is safe to expand in the sense that all materialized values are d...
LLVM_ABI unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT, SmallVectorImpl< WeakTrackingVH > &DeadInsts, const TargetTransformInfo *TTI=nullptr)
replace congruent phis with their most canonical representative.
static LLVM_ABI void dropPoisonGeneratingAnnotationsAndReinfer(ScalarEvolution &SE, Instruction *I)
Drop poison-generating flags from I, then try re-infer via SCEV.
LLVM_ABI Value * expandUnionPredicate(const SCEVUnionPredicate *Pred, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
static LLVM_ABI CastInst * findReusableCastForPtrToAddr(Value *PtrOp, Type *Ty, const DataLayout &DL, function_ref< bool(const CastInst *)> Dominates)
Find an existing cast among PtrOp's users that computes the same value as a ptrtoaddr of PtrOp to Ty ...
LLVM_ABI bool hoistIVInc(Instruction *IncV, Instruction *InsertPos, bool RecomputePoisonFlags=false)
Utility for hoisting IncV (with all subexpressions requried for its computation) before InsertPos.
bool isInsertedInstruction(Instruction *I) const
Return true if the specified instruction was inserted by the code rewriter.
LLVM_ABI Value * expandCodeForPredicate(const SCEVPredicate *Pred, Instruction *Loc)
Generates a code sequence that evaluates this predicate.
static LLVM_ABI bool canReuseFlagsFromOriginalIVInc(PHINode *OrigPhi, PHINode *WidePhi, Instruction *OrigInc, Instruction *WideInc)
Return true if both increments directly increment the corresponding IV PHI nodes and have the same op...
LLVM_ABI Value * expandCodeFor(SCEVUse SH, Type *Ty, BasicBlock::iterator I)
Insert code to directly compute the specified SCEV expression into the program.
LLVM_ABI Value * expandComparePredicate(const SCEVComparePredicate *Pred, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
LLVM_ABI Value * expandWrapPredicate(const SCEVWrapPredicate *P, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
LLVM_ABI Instruction * getIVIncOperand(Instruction *IncV, Instruction *InsertPos, bool allowScale)
Return the induction variable increment's IV operand.
LLVM_ABI void eraseDeadInstructions(Value *Root)
Remove inserted instructions that are dead, e.g.
LLVM_ABI BasicBlock::iterator findInsertPointAfter(Instruction *I, Instruction *MustDominate) const
Returns a suitable insert point after I, that dominates MustDominate.
static LLVM_ABI std::pair< PHINode *, const SCEV * > findReusableLCSSAPhi(ScalarEvolution &SE, SCEVUseT< const SCEVAddRecExpr * > S, const BasicBlock *InsertBB)
Find a phi in the exit block of S's loop, which must dominate InsertBB, such that S can be expanded i...
void setInsertPoint(Instruction *IP)
Set the current insertion point.
This class represents an assumption made using SCEV expressions which can be checked at run-time.
This class represents a composition of other SCEV predicates, and is the class that most clients will...
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents an assumption made on an AddRec expression.
This class represents an analyzed expression in the program.
static constexpr auto FlagNUW
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
SCEVTypes getSCEVType() const
static constexpr auto FlagNW
The main scalar evolution driver.
LLVM_ABI bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
LLVM_ABI const SCEV * getMinusSCEV(SCEVUse LHS, SCEVUse RHS, SCEVFlags Flags=SCEV::FlagNone, unsigned Depth=0)
Return LHS-RHS.
LLVM_ABI uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
static LLVM_ABI bool isGuaranteedNotToBePoison(const SCEV *Op)
Returns true if Op is guaranteed to not be poison.
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.
static SCEVFlags clearFlags(SCEVFlags Flags, SCEVFlags OffFlags)
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 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.
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 push_back(const T &Elt)
LLVM_NO_SANITIZE_CFI_UNRELATED_CAST iterator begin()
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
LLVM_ABI unsigned getIntegerBitWidth() const
bool isVectorTy() const
True if this is an instance of VectorType.
static LLVM_ABI IntegerType * getInt32Ty(LLVMContext &C)
bool isPointerTy() const
True if this is an instance of PointerType.
LLVM_ABI unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
bool isIntegerTy() const
True if this is an instance of IntegerType.
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< user_iterator > users()
An efficient, type-erasing, non-owning reference to a callable.
const ParentTy * getParent() const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr bool any(E Val)
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ BasicBlock
Various leaf nodes.
cst_pred_ty< is_power2 > m_Power2()
Match an integer or vector power-of-2.
bool match(Val *V, const Pattern &P)
match_bind< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
auto m_BasicBlock()
Match an arbitrary basic block value and ignore it.
auto m_Value()
Match an arbitrary value and ignore it.
AnyBinaryOp_match< LHS, RHS, true > m_c_BinOp(const LHS &L, const RHS &R)
Matches a BinaryOperator with LHS and RHS in either order.
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
brc_match< Cond_t, match_bind< BasicBlock >, match_bind< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
cst_pred_ty< is_all_ones > m_scev_AllOnes()
Match an integer with all bits set.
SCEVUnaryExpr_match< SCEVPtrToAddrExpr, Op0_t > m_scev_PtrToAddr(const Op0_t &Op0)
match_bind< const SCEVMulExpr > m_scev_Mul(const SCEVMulExpr *&V)
SCEVBinaryExpr_match< SCEVUDivExpr, Op0_t, Op1_t > m_scev_UDiv(const Op0_t &Op0, const Op1_t &Op1)
SCEVBinaryExpr_match< SCEVUMaxExpr, Op0_t, Op1_t, SCEV::FlagNone, true > m_scev_UMax(const Op0_t &Op0, const Op1_t &Op1)
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.
@ CE
Windows NT (Windows on ARM)
initializer< Ty > init(const Ty &Val)
@ User
could "use" a pointer
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
void visitAll(const SCEV *Root, SV &Visitor)
Use SCEVTraversal to visit all nodes in the given expression tree.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
void stable_sort(R &&Range)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are tuples (A, B,...
auto pred_end(const MachineBasicBlock *BB)
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
constexpr from_range_t from_range
constexpr NextUseDistance min(NextUseDistance A, NextUseDistance B)
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
auto pred_size(const MachineBasicBlock *BB)
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
LLVM_ABI bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
auto reverse(ContainerTy &&C)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
IRBuilder(LLVMContext &, FolderTy, InserterTy) -> IRBuilder< FolderTy, InserterTy >
LLVM_ABI cl::opt< unsigned > SCEVCheapExpansionBudget
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 Constant * ConstantFoldBinaryOpOperands(unsigned Opcode, Constant *LHS, Constant *RHS, const DataLayout &DL)
Attempt to constant fold a binary operation with the specified operands.
LLVM_ABI const SCEV * normalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, ScalarEvolution &SE, bool CheckInvertible=true)
Normalize S to be post-increment for all loops present in Loops.
constexpr NextUseDistance max(NextUseDistance A, NextUseDistance B)
@ Mul
Product of integers.
@ Sub
Subtraction of integers.
DWARFExpression::Operation Op
PredIterator< BasicBlock, Value::user_iterator > pred_iterator
SCEVFlags
SCEVFlags are bitfield indices into SCEV's SubclassData.
constexpr unsigned BitWidth
LLVM_ABI bool formLCSSAForInstructions(SmallVectorImpl< Instruction * > &Worklist, const DominatorTree &DT, const LoopInfo &LI, ScalarEvolution *SE, SmallVectorImpl< PHINode * > *PHIsToRemove=nullptr, SmallVectorImpl< PHINode * > *InsertedPHIs=nullptr)
Ensures LCSSA form for every instruction from the Worklist in the scope of innermost containing loop.
auto pred_begin(const MachineBasicBlock *BB)
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
SmallPtrSet< const Loop *, 2 > PostIncLoopSet
auto predecessors(const MachineBasicBlock *BB)
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
LLVM_ABI std::optional< bool > isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL)
Return the boolean condition value in the context of the given instruction if it is known based on do...
SCEVUseT< const SCEV * > SCEVUse
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
LLVM_ABI void apply(Instruction *I)
LLVM_ABI PoisonFlags(const Instruction *I)
struct for holding enough information to help calculate the cost of the given SCEV when expanded into...
const SCEV * S
The SCEV operand to be costed.
unsigned ParentOpcode
LLVM instruction opcode that uses the operand.
int OperandIdx
The use index of an expanded instruction.
SCEVFlags getNoWrapFlags(SCEVFlags Mask=SCEVFlags::FlagsNoWrapMask) const
Return the flags for this SCEVUse, which is the union of the use-specific flags and the underlying SC...