31#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
32#define SCEV_DEBUG_WITH_TYPE(TYPE, X) DEBUG_WITH_TYPE(TYPE, X)
34#define SCEV_DEBUG_WITH_TYPE(TYPE, X)
41 cl::desc(
"When performing SCEV expansion only if it is cheap to do, this "
42 "controls the budget that is considered cheap (default = 4)"));
44using namespace PatternMatch;
52 if (
auto *OBO = dyn_cast<OverflowingBinaryOperator>(
I)) {
53 NUW = OBO->hasNoUnsignedWrap();
54 NSW = OBO->hasNoSignedWrap();
56 if (
auto *PEO = dyn_cast<PossiblyExactOperator>(
I))
57 Exact = PEO->isExact();
58 if (
auto *PDI = dyn_cast<PossiblyDisjointInst>(
I))
60 if (
auto *PNI = dyn_cast<PossiblyNonNegInst>(
I))
61 NNeg = PNI->hasNonNeg();
62 if (
auto *TI = dyn_cast<TruncInst>(
I)) {
63 NUW = TI->hasNoUnsignedWrap();
64 NSW = TI->hasNoSignedWrap();
69 if (isa<OverflowingBinaryOperator>(
I)) {
70 I->setHasNoUnsignedWrap(
NUW);
71 I->setHasNoSignedWrap(
NSW);
73 if (isa<PossiblyExactOperator>(
I))
75 if (
auto *PDI = dyn_cast<PossiblyDisjointInst>(
I))
77 if (
auto *PNI = dyn_cast<PossiblyNonNegInst>(
I))
79 if (isa<TruncInst>(
I)) {
80 I->setHasNoUnsignedWrap(
NUW);
81 I->setHasNoSignedWrap(
NSW);
102 Value *Ret =
nullptr;
105 for (
User *U : V->users()) {
106 if (U->getType() != Ty)
108 CastInst *CI = dyn_cast<CastInst>(U);
114 if (IP->getParent() == CI->
getParent() && &*BIP != CI &&
123 SCEVInsertPointGuard Guard(Builder,
this);
131 assert(!isa<Instruction>(Ret) ||
132 SE.DT.
dominates(cast<Instruction>(Ret), &*BIP));
141 if (
auto *II = dyn_cast<InvokeInst>(
I))
142 IP = II->getNormalDest()->begin();
144 while (isa<PHINode>(IP))
147 if (isa<FuncletPadInst>(IP) || isa<LandingPadInst>(IP)) {
149 }
else if (isa<CatchSwitchInst>(IP)) {
152 assert(!IP->isEHPad() &&
"unexpected eh pad!");
165SCEVExpander::GetOptimalInsertionPointForCastOf(
Value *V)
const {
168 if (
Argument *
A = dyn_cast<Argument>(V)) {
170 while ((isa<BitCastInst>(IP) &&
171 isa<Argument>(cast<BitCastInst>(IP)->getOperand(0)) &&
172 cast<BitCastInst>(IP)->getOperand(0) !=
A) ||
173 isa<DbgInfoIntrinsic>(IP))
184 assert(isa<Constant>(V) &&
185 "Expected the cast argument to be a global/constant");
197 assert((
Op == Instruction::BitCast ||
198 Op == Instruction::PtrToInt ||
199 Op == Instruction::IntToPtr) &&
200 "InsertNoopCastOfTo cannot perform non-noop casts!");
202 "InsertNoopCastOfTo cannot change sizes!");
209 if (
Op == Instruction::IntToPtr) {
210 auto *PtrTy = cast<PointerType>(Ty);
215 if (
Op == Instruction::BitCast) {
216 if (
V->getType() == Ty)
218 if (
CastInst *CI = dyn_cast<CastInst>(V)) {
224 if ((
Op == Instruction::PtrToInt ||
Op == Instruction::IntToPtr) &&
226 if (
CastInst *CI = dyn_cast<CastInst>(V))
227 if ((CI->
getOpcode() == Instruction::PtrToInt ||
228 CI->
getOpcode() == Instruction::IntToPtr) &&
233 if ((
CE->getOpcode() == Instruction::PtrToInt ||
234 CE->getOpcode() == Instruction::IntToPtr) &&
237 return CE->getOperand(0);
245 return ReuseOrCreateCast(V, Ty,
Op, GetOptimalInsertionPointForCastOf(V));
255 if (
Constant *CLHS = dyn_cast<Constant>(LHS))
256 if (
Constant *CRHS = dyn_cast<Constant>(RHS))
261 unsigned ScanLimit = 6;
265 if (IP != BlockBegin) {
267 for (; ScanLimit; --IP, --ScanLimit) {
270 if (isa<DbgInfoIntrinsic>(IP))
275 if (isa<OverflowingBinaryOperator>(
I)) {
283 if (isa<PossiblyExactOperator>(
I) &&
I->isExact())
287 if (IP->getOpcode() == (
unsigned)Opcode && IP->getOperand(0) ==
LHS &&
288 IP->getOperand(1) ==
RHS && !canGenerateIncompatiblePoison(&*IP))
290 if (IP == BlockBegin)
break;
296 SCEVInsertPointGuard Guard(Builder,
this);
301 if (!
L->isLoopInvariant(LHS) || !
L->isLoopInvariant(RHS))
break;
303 if (!Preheader)
break;
351 assert(!isa<Instruction>(V) ||
357 if (
Constant *CLHS = dyn_cast<Constant>(V))
362 unsigned ScanLimit = 6;
366 if (IP != BlockBegin) {
368 for (; ScanLimit; --IP, --ScanLimit) {
371 if (isa<DbgInfoIntrinsic>(IP))
373 if (IP->getOpcode() == Instruction::GetElementPtr &&
374 IP->getOperand(0) == V && IP->getOperand(1) ==
Idx &&
375 cast<GEPOperator>(&*IP)->getSourceElementType() ==
378 if (IP == BlockBegin)
break;
383 SCEVInsertPointGuard Guard(Builder,
this);
387 if (!
L->isLoopInvariant(V) || !
L->isLoopInvariant(
Idx))
break;
389 if (!Preheader)
break;
406 if (
A->contains(
B))
return B;
407 if (
B->contains(
A))
return A;
408 if (DT.
dominates(
A->getHeader(),
B->getHeader()))
return B;
409 if (DT.
dominates(
B->getHeader(),
A->getHeader()))
return A;
415const Loop *SCEVExpander::getRelevantLoop(
const SCEV *S) {
417 auto Pair = RelevantLoops.insert(std::make_pair(S,
nullptr));
419 return Pair.first->second;
438 const Loop *
L =
nullptr;
443 return RelevantLoops[S] =
L;
447 if (
const Instruction *
I = dyn_cast<Instruction>(
U->getValue()))
448 return Pair.first->second = SE.LI.
getLoopFor(
I->getParent());
466 bool operator()(std::pair<const Loop *, const SCEV *>
LHS,
467 std::pair<const Loop *, const SCEV *>
RHS)
const {
474 if (
LHS.first !=
RHS.first)
480 if (
LHS.second->isNonConstantNegative()) {
481 if (!
RHS.second->isNonConstantNegative())
483 }
else if (
RHS.second->isNonConstantNegative())
500 OpsAndLoops.
push_back(std::make_pair(getRelevantLoop(
Op),
Op));
508 Value *Sum =
nullptr;
509 for (
auto I = OpsAndLoops.
begin(), E = OpsAndLoops.
end();
I != E;) {
510 const Loop *CurLoop =
I->first;
519 assert(!
Op->getType()->isPointerTy() &&
"Only first op can be pointer");
520 if (isa<PointerType>(Sum->
getType())) {
524 for (;
I != E &&
I->first == CurLoop; ++
I) {
527 const SCEV *
X =
I->second;
529 if (!isa<Instruction>(
U->getValue()))
533 Sum = expandAddToGEP(SE.
getAddExpr(NewOps), Sum);
534 }
else if (
Op->isNonConstantNegative()) {
544 if (isa<Constant>(Sum))
562 OpsAndLoops.
push_back(std::make_pair(getRelevantLoop(
Op),
Op));
569 Value *Prod =
nullptr;
570 auto I = OpsAndLoops.
begin();
575 const auto ExpandOpBinPowN = [
this, &
I, &OpsAndLoops]() {
585 while (E != OpsAndLoops.
end() && *
I == *E &&
Exponent != MaxExponent) {
589 assert(
Exponent > 0 &&
"Trying to calculate a zeroth exponent of operand?");
608 assert(Result &&
"Nothing was expanded?");
612 while (
I != OpsAndLoops.
end()) {
615 Prod = ExpandOpBinPowN();
616 }
else if (
I->second->isAllOnesValue()) {
623 Value *
W = ExpandOpBinPowN();
625 if (isa<Constant>(Prod))
std::swap(Prod, W);
632 if (
RHS->logBase2() ==
RHS->getBitWidth() - 1)
634 Prod = InsertBinop(Instruction::Shl, Prod,
635 ConstantInt::get(Ty,
RHS->logBase2()), NWFlags,
638 Prod = InsertBinop(Instruction::Mul, Prod, W, S->
getNoWrapFlags(),
651 if (
RHS.isPowerOf2())
652 return InsertBinop(Instruction::LShr, LHS,
653 ConstantInt::get(
SC->getType(),
RHS.logBase2()),
667 (isa<CastInst>(IncV) && !isa<BitCastInst>(IncV)))
672 if (L == IVIncInsertLoop) {
675 if (!SE.DT.
dominates(OInst, IVIncInsertPos))
679 IncV = dyn_cast<Instruction>(IncV->
getOperand(0));
689 return isNormalAddRecExprPHI(PN, IncV, L);
704 if (IncV == InsertPos)
711 case Instruction::Add:
712 case Instruction::Sub: {
714 if (!OInst || SE.DT.
dominates(OInst, InsertPos))
715 return dyn_cast<Instruction>(IncV->
getOperand(0));
718 case Instruction::BitCast:
719 return dyn_cast<Instruction>(IncV->
getOperand(0));
720 case Instruction::GetElementPtr:
722 if (isa<Constant>(U))
724 if (
Instruction *OInst = dyn_cast<Instruction>(U)) {
733 if (!cast<GEPOperator>(IncV)->getSourceElementType()->isIntegerTy(8))
737 return dyn_cast<Instruction>(IncV->
getOperand(0));
753 for (
auto *InsertPtGuard : InsertPointGuards)
754 if (InsertPtGuard->GetInsertPoint() == It)
755 InsertPtGuard->SetInsertPoint(NewInsertPt);
762 bool RecomputePoisonFlags) {
767 I->dropPoisonGeneratingFlags();
768 if (
auto *OBO = dyn_cast<OverflowingBinaryOperator>(
I))
770 auto *BO = cast<BinaryOperator>(
I);
779 if (RecomputePoisonFlags)
780 FixupPoisonFlags(IncV);
786 if (isa<PHINode>(InsertPos) ||
806 fixupInsertPoints(
I);
807 I->moveBefore(InsertPos);
808 if (RecomputePoisonFlags)
831 (IVOper =
getIVIncOperand(IVOper, L->getLoopPreheader()->getTerminator(),
864 Type *PhiTy = Phi->getType();
878 if (Phi == Requested) {
893 if (!isa<IntegerType>(AR->
getType()))
901 const SCEV *ExtendAfterOp =
903 return ExtendAfterOp == OpAfterExtend;
907 if (!isa<IntegerType>(AR->
getType()))
915 const SCEV *ExtendAfterOp =
917 return ExtendAfterOp == OpAfterExtend;
924SCEVExpander::getAddRecExprPHILiterally(
const SCEVAddRecExpr *Normalized,
927 assert((!IVIncInsertLoop || IVIncInsertPos) &&
928 "Uninitialized insert position");
933 PHINode *AddRecPhiMatch =
nullptr;
940 bool TryNonMatchingSCEV =
944 for (
PHINode &PN :
L->getHeader()->phis()) {
952 DebugType,
dbgs() <<
"One incomplete PHI is found: " << PN <<
"\n");
960 bool IsMatchingSCEV = PhiSCEV == Normalized;
964 if (!IsMatchingSCEV && !TryNonMatchingSCEV)
975 if (!isExpandedAddRecExprPHI(&PN, TempIncV, L))
978 if (!isNormalAddRecExprPHI(&PN, TempIncV, L))
983 if (IsMatchingSCEV) {
987 AddRecPhiMatch = &PN;
993 if ((!TruncTy || InvertStep) &&
997 AddRecPhiMatch = &PN;
999 TruncTy = Normalized->
getType();
1003 if (AddRecPhiMatch) {
1006 InsertedValues.insert(AddRecPhiMatch);
1008 rememberInstruction(IncV);
1010 ReusedValues.
insert(AddRecPhiMatch);
1011 ReusedValues.
insert(IncV);
1012 return AddRecPhiMatch;
1017 SCEVInsertPointGuard Guard(Builder,
this);
1027 PostIncLoops.
clear();
1030 assert(
L->getLoopPreheader() &&
1031 "Can't expand add recurrences without a loop preheader!");
1033 expand(Normalized->
getStart(),
L->getLoopPreheader()->getTerminator());
1037 assert(!isa<Instruction>(StartV) ||
1052 Value *StepV = expand(Step,
L->getHeader()->getFirstInsertionPt());
1057 bool IncrementIsNUW = !useSubtract &&
IsIncrementNUW(SE, Normalized);
1058 bool IncrementIsNSW = !useSubtract &&
IsIncrementNSW(SE, Normalized);
1069 if (!
L->contains(Pred)) {
1078 IVIncInsertPos : Pred->getTerminator();
1080 Value *IncV = expandIVInc(PN, StepV, L, useSubtract);
1082 if (isa<OverflowingBinaryOperator>(IncV)) {
1084 cast<BinaryOperator>(IncV)->setHasNoUnsignedWrap();
1086 cast<BinaryOperator>(IncV)->setHasNoSignedWrap();
1093 PostIncLoops = SavedPostIncLoops;
1097 InsertedValues.insert(PN);
1098 InsertedIVs.push_back(PN);
1108 if (PostIncLoops.
count(L)) {
1111 Normalized = cast<SCEVAddRecExpr>(
1115 [[maybe_unused]]
const SCEV *Start = Normalized->
getStart();
1118 "Start does not properly dominate loop header");
1119 assert(SE.
dominates(Step,
L->getHeader()) &&
"Step not dominate loop header");
1123 Type *TruncTy =
nullptr;
1124 bool InvertStep =
false;
1125 PHINode *PN = getAddRecExprPHILiterally(Normalized, L, TruncTy, InvertStep);
1129 if (!PostIncLoops.
count(L))
1134 assert(LatchBlock &&
"PostInc mode requires a unique loop latch!");
1140 if (isa<OverflowingBinaryOperator>(Result)) {
1141 auto *
I = cast<Instruction>(Result);
1143 I->setHasNoUnsignedWrap(
false);
1145 I->setHasNoSignedWrap(
false);
1151 if (isa<Instruction>(Result) &&
1152 !SE.DT.
dominates(cast<Instruction>(Result),
1170 SCEVInsertPointGuard Guard(Builder,
this);
1171 StepV = expand(Step,
L->getHeader()->getFirstInsertionPt());
1173 Result = expandIVInc(PN, StepV, L, useSubtract);
1181 if (TruncTy !=
Result->getType())
1204 return expandAddRecExprLiterally(S);
1210 PHINode *CanonicalIV =
nullptr;
1211 if (
PHINode *PN =
L->getCanonicalInductionVariable())
1233 if (isa<PointerType>(S->
getType())) {
1249 return expand(SE.
getAddExpr(AddExprLHS, AddExprRHS));
1260 rememberInstruction(CanonicalIV);
1263 Constant *One = ConstantInt::get(Ty, 1);
1266 if (!PredSeen.
insert(HP).second) {
1273 if (
L->contains(HP)) {
1280 rememberInstruction(
Add);
1291 "IVs with types different from the canonical IV should "
1292 "already have been handled!");
1314 const SCEV *NewS = S;
1316 if (isa<SCEVAddRecExpr>(Ext))
1319 const SCEV *
V = cast<SCEVAddRecExpr>(NewS)->evaluateAtIteration(IH, SE);
1328 return ReuseOrCreateCast(V, S->
getType(), CastInst::PtrToInt,
1329 GetOptimalInsertionPointForCastOf(V));
1350 bool IsSequential) {
1357 if (IsSequential && i != 0)
1374 return expandMinMaxExpr(S, Intrinsic::smax,
"smax");
1378 return expandMinMaxExpr(S, Intrinsic::umax,
"umax");
1382 return expandMinMaxExpr(S, Intrinsic::smin,
"smin");
1386 return expandMinMaxExpr(S, Intrinsic::umin,
"umin");
1390 return expandMinMaxExpr(S, Intrinsic::umin,
"umin",
true);
1406 Value *V = expand(SH);
1410 "non-trivial casts should be done with the SCEVs directly!");
1411 V = InsertNoopCastOfTo(V, Ty);
1416Value *SCEVExpander::FindValueInExprValueMap(
1425 if (isa<SCEVConstant>(S))
1428 for (
Value *V : SE.getSCEVValues(S)) {
1445 DropPoisonGeneratingInsts.
clear();
1456Value *SCEVExpander::expand(
const SCEV *S) {
1463 auto SafeToHoist = [](
const SCEV *S) {
1465 if (
const auto *
D = dyn_cast<SCEVUDivExpr>(S)) {
1466 if (
const auto *SC = dyn_cast<SCEVConstant>(
D->getRHS()))
1468 return SC->getValue()->isZero();
1478 if (SafeToHoist(S)) {
1480 L =
L->getParentLoop()) {
1483 if (
BasicBlock *Preheader =
L->getLoopPreheader()) {
1489 InsertPt =
L->getHeader()->getFirstInsertionPt();
1496 InsertPt =
L->getHeader()->getFirstInsertionPt();
1500 isa<DbgInfoIntrinsic>(&*InsertPt))) {
1501 InsertPt = std::next(InsertPt);
1509 auto I = InsertedExpressions.find(std::make_pair(S, &*InsertPt));
1510 if (
I != InsertedExpressions.end())
1513 SCEVInsertPointGuard Guard(Builder,
this);
1518 Value *
V = FindValueInExprValueMap(S, &*InsertPt, DropPoisonGeneratingInsts);
1521 V = fixupLCSSAFormFor(V);
1525 I->dropPoisonGeneratingAnnotations();
1528 if (
auto *OBO = dyn_cast<OverflowingBinaryOperator>(
I))
1530 auto *BO = cast<BinaryOperator>(
I);
1536 if (
auto *NNI = dyn_cast<PossiblyNonNegInst>(
I)) {
1537 auto *Src = NNI->getOperand(0);
1540 DL).value_or(
false))
1541 NNI->setNonNeg(
true);
1551 InsertedExpressions[std::make_pair(S, &*InsertPt)] =
V;
1555void SCEVExpander::rememberInstruction(
Value *
I) {
1556 auto DoInsert = [
this](
Value *
V) {
1557 if (!PostIncLoops.
empty())
1558 InsertedPostIncValues.insert(V);
1560 InsertedValues.insert(V);
1570void SCEVExpander::replaceCongruentIVInc(
1580 dyn_cast<Instruction>(
Phi->getIncomingValueForBlock(LatchBlock));
1581 if (!OrigInc || !IsomorphicInc)
1588 !(ChainedPhis.count(Phi) ||
1589 isExpandedAddRecExprPHI(OrigPhi, OrigInc, L)) &&
1590 (ChainedPhis.count(Phi) ||
1591 isExpandedAddRecExprPHI(Phi, IsomorphicInc, L))) {
1605 const SCEV *TruncExpr =
1607 if (OrigInc == IsomorphicInc || TruncExpr != SE.
getSCEV(IsomorphicInc) ||
1611 bool BothHaveNUW =
false;
1612 bool BothHaveNSW =
false;
1613 auto *OBOIncV = dyn_cast<OverflowingBinaryOperator>(OrigInc);
1614 auto *OBOIsomorphic = dyn_cast<OverflowingBinaryOperator>(IsomorphicInc);
1615 if (OBOIncV && OBOIsomorphic) {
1617 OBOIncV->hasNoUnsignedWrap() && OBOIsomorphic->hasNoUnsignedWrap();
1619 OBOIncV->hasNoSignedWrap() && OBOIsomorphic->hasNoSignedWrap();
1632 "Should only replace an increment with a wider one.");
1633 if (BothHaveNUW || BothHaveNSW) {
1639 dbgs() <<
"INDVARS: Eliminated congruent iv.inc: "
1640 << *IsomorphicInc <<
'\n');
1641 Value *NewInc = OrigInc;
1644 if (
PHINode *PN = dyn_cast<PHINode>(OrigInc))
1670 for (
PHINode &PN : L->getHeader()->phis())
1684 unsigned NumElim = 0;
1694 auto *Const = dyn_cast<SCEVConstant>(SE.
getSCEV(PN));
1697 return Const->getValue();
1702 if (
Value *V = SimplifyPHINode(Phi)) {
1703 if (V->getType() != Phi->getType())
1706 Phi->replaceAllUsesWith(V);
1710 dbgs() <<
"INDVARS: Eliminated constant iv: " << *Phi
1721 if (Phi->getType()->isIntegerTy() &&
TTI &&
1727 if (isa<SCEVAddRecExpr>(PhiExpr)) {
1730 const SCEV *TruncExpr =
1732 ExprToIVMap[TruncExpr] = Phi;
1743 replaceCongruentIVInc(Phi, OrigPhiRef, L, DT, DeadInsts);
1745 dbgs() <<
"INDVARS: Eliminated congruent iv: " << *Phi
1748 DebugType,
dbgs() <<
"INDVARS: Original iv: " << *OrigPhiRef <<
'\n');
1750 Value *NewIV = OrigPhiRef;
1751 if (OrigPhiRef->
getType() != Phi->getType()) {
1753 L->getHeader()->getFirstInsertionPt());
1757 Phi->replaceAllUsesWith(NewIV);
1769 L->getExitingBlocks(ExitingBlocks);
1776 if (!
match(BB->getTerminator(),
1793 return FindValueInExprValueMap(S, At, DropPoisonGeneratingInsts) !=
nullptr;
1804 struct OperationIndices {
1805 OperationIndices(
unsigned Opc,
size_t min,
size_t max) :
1806 Opcode(Opc), MinIdx(min), MaxIdx(
max) { }
1820 S->getOperand(0)->getType(),
1824 auto ArithCost = [&](
unsigned Opcode,
unsigned NumRequired,
1825 unsigned MinIdx = 0,
1828 return NumRequired *
1832 auto CmpSelCost = [&](
unsigned Opcode,
unsigned NumRequired,
unsigned MinIdx,
1835 Type *OpType = S->getType();
1841 switch (S->getSCEVType()) {
1849 Cost = CastCost(Instruction::PtrToInt);
1852 Cost = CastCost(Instruction::Trunc);
1855 Cost = CastCost(Instruction::ZExt);
1858 Cost = CastCost(Instruction::SExt);
1861 unsigned Opcode = Instruction::UDiv;
1862 if (
auto *SC = dyn_cast<SCEVConstant>(S->getOperand(1)))
1863 if (SC->getAPInt().isPowerOf2())
1864 Opcode = Instruction::LShr;
1865 Cost = ArithCost(Opcode, 1);
1869 Cost = ArithCost(Instruction::Add, S->getNumOperands() - 1);
1875 Cost = ArithCost(Instruction::Mul, S->getNumOperands() - 1);
1884 Cost += CmpSelCost(Instruction::ICmp, S->getNumOperands() - 1, 0, 1);
1885 Cost += CmpSelCost(Instruction::Select, S->getNumOperands() - 1, 0, 2);
1886 switch (S->getSCEVType()) {
1890 Cost += CmpSelCost(Instruction::ICmp, S->getNumOperands() - 1, 0, 0);
1891 Cost += ArithCost(Instruction::Or,
1892 S->getNumOperands() > 2 ? S->getNumOperands() - 2 : 0);
1893 Cost += CmpSelCost(Instruction::Select, 1, 0, 1);
1897 assert(!isa<SCEVSequentialMinMaxExpr>(S) &&
1898 "Unhandled SCEV expression type?");
1907 return !Op->isZero();
1910 assert(NumTerms >= 1 &&
"Polynominal should have at least one term.");
1911 assert(!(*std::prev(S->operands().end()))->isZero() &&
1912 "Last operand should not be zero");
1915 int NumNonZeroDegreeNonOneTerms =
1917 auto *SConst = dyn_cast<SCEVConstant>(Op);
1918 return !SConst || SConst->getAPInt().ugt(1);
1927 ArithCost(Instruction::Mul, NumNonZeroDegreeNonOneTerms);
1928 Cost = AddCost + MulCost;
1931 int PolyDegree = S->getNumOperands() - 1;
1932 assert(PolyDegree >= 1 &&
"Should be at least affine.");
1940 Cost += MulCost * (PolyDegree - 1);
1945 for (
auto &CostOp : Operations) {
1946 for (
auto SCEVOp :
enumerate(S->operands())) {
1948 size_t MinIdx = std::max(SCEVOp.index(), CostOp.MinIdx);
1949 size_t OpIdx = std::min(MinIdx, CostOp.MaxIdx);
1950 Worklist.
emplace_back(CostOp.Opcode, OpIdx, SCEVOp.value());
1956bool SCEVExpander::isHighCostExpansionHelper(
1966 if (!isa<SCEVConstant>(S) && !Processed.
insert(S).second)
1975 L->getHeader()->getParent()->hasMinSize()
1990 const APInt &
Imm = cast<SCEVConstant>(S)->getAPInt();
1994 return Cost > Budget;
2028 assert(cast<SCEVNAryExpr>(S)->getNumOperands() > 1 &&
2029 "Nary expr should have more than 1 operand.");
2034 return Cost > Budget;
2037 assert(cast<SCEVAddRecExpr>(S)->getNumOperands() >= 2 &&
2038 "Polynomial should be at least linear");
2039 Cost += costAndCollectOperands<SCEVAddRecExpr>(
2041 return Cost > Budget;
2056 auto *AddRecPred = cast<SCEVWrapPredicate>(Pred);
2070 auto *
I = Builder.
CreateICmp(InvPred, Expr0, Expr1,
"ident.check");
2077 "non-affine expression");
2081 const SCEV *ExitCount =
2084 assert(!isa<SCEVCouldNotCompute>(ExitCount) &&
"Invalid loop count");
2099 Value *TripCountVal = expand(ExitCount, Loc);
2104 Value *StepValue = expand(Step, Loc);
2106 Value *StartValue = expand(Start, Loc);
2124 auto ComputeEndCheck = [&]() ->
Value * {
2132 Value *MulV, *OfMul;
2133 if (Step->
isOne()) {
2137 MulV = TruncTripCount;
2141 Intrinsic::umul_with_overflow, Ty);
2143 Builder.
CreateCall(MulF, {AbsStep, TruncTripCount},
"mul");
2148 Value *
Add =
nullptr, *Sub =
nullptr;
2152 if (isa<PointerType>(ARTy)) {
2162 Sub = Builder.
CreateSub(StartValue, MulV);
2165 Value *EndCompareLT =
nullptr;
2166 Value *EndCompareGT =
nullptr;
2167 Value *EndCheck =
nullptr;
2169 EndCheck = EndCompareLT = Builder.
CreateICmp(
2172 EndCheck = EndCompareGT = Builder.
CreateICmp(
2174 if (NeedPosCheck && NeedNegCheck) {
2176 EndCheck = Builder.
CreateSelect(StepCompare, EndCompareGT, EndCompareLT);
2178 return Builder.
CreateOr(EndCheck, OfMul);
2180 Value *EndCheck = ComputeEndCheck();
2185 if (SrcBits > DstBits) {
2187 auto *BackedgeCheck =
2189 ConstantInt::get(Loc->
getContext(), MaxVal));
2193 EndCheck = Builder.
CreateOr(EndCheck, BackedgeCheck);
2201 const auto *
A = cast<SCEVAddRecExpr>(Pred->
getExpr());
2202 Value *NSSWCheck =
nullptr, *NUSWCheck =
nullptr;
2212 if (NUSWCheck && NSSWCheck)
2213 return Builder.
CreateOr(NUSWCheck, NSSWCheck);
2228 for (
const auto *Pred : Union->getPredicates()) {
2238Value *SCEVExpander::fixupLCSSAFormFor(
Value *V) {
2239 auto *DefI = dyn_cast<Instruction>(V);
2240 if (!PreserveLCSSA || !DefI)
2246 if (!DefLoop || UseLoop == DefLoop || DefLoop->
contains(UseLoop))
2257 if (DefI->getType()->isIntegerTy())
2263 auto RemoveUserOnExit =
2272 for (
PHINode *PN : InsertedPHIs)
2273 rememberInstruction(PN);
2274 for (
PHINode *PN : PHIsToRemove) {
2277 InsertedValues.erase(PN);
2278 InsertedPostIncValues.erase(PN);
2304struct SCEVFindUnsafe {
2307 bool IsUnsafe =
false;
2310 : SE(SE), CanonicalMode(CanonicalMode) {}
2312 bool follow(
const SCEV *S) {
2322 if (!AR->getLoop()->getLoopPreheader() &&
2323 (!CanonicalMode || !AR->isAffine())) {
2330 bool isDone()
const {
return IsUnsafe; }
2335 SCEVFindUnsafe Search(SE, CanonicalMode);
2337 return !Search.IsUnsafe;
2355 if (
const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S))
2368 for (
auto [
I, Flags] : Expander.OrigFlags)
2374 InsertedInstructions.end());
2384 [&InsertedSet](
Value *U) {
2385 return InsertedSet.contains(cast<Instruction>(U));
2387 "removed instruction should only be used by instructions inserted "
2388 "during expansion");
2390 assert(!
I->getType()->isVoidTy() &&
2391 "inserted instruction should have non-void types");
2393 I->eraseFromParent();
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static cl::opt< TargetTransformInfo::TargetCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(TargetTransformInfo::TCK_RecipThroughput), cl::values(clEnumValN(TargetTransformInfo::TCK_RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(TargetTransformInfo::TCK_Latency, "latency", "Instruction latency"), clEnumValN(TargetTransformInfo::TCK_CodeSize, "code-size", "Code size"), clEnumValN(TargetTransformInfo::TCK_SizeAndLatency, "size-latency", "Code size and latency")))
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool IsIncrementNUW(ScalarEvolution &SE, const SCEVAddRecExpr *AR)
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 IsIncrementNSW(ScalarEvolution &SE, const SCEVAddRecExpr *AR)
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)
This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...
This file defines the SmallSet class.
Class for arbitrary precision integers.
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.
This class represents an incoming formal argument to a Function.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Function * getParent() const
Return the enclosing method, or null if none.
InstListType::iterator iterator
Instruction iterators...
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name, BasicBlock::iterator InsertBefore)
Construct a binary instruction, given the opcode and the two operands.
This class represents a function call, abstracting a target machine's calling convention.
This is the base class for all instructions that perform data casts.
static 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 CastInst * CreateBitOrPointerCast(Value *S, Type *Ty, const Twine &Name, BasicBlock::iterator InsertBefore)
Create a BitCast, a PtrToInt, or an IntToPTr cast instruction.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ 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,...
A constant value that is initialized with an expression using other constant values.
static 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 ConstantInt * getFalse(LLVMContext &Context)
This is an important base class in LLVM.
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
This class represents an Operation in the Expression.
bool isNonIntegralPointerType(PointerType *PT) const
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
const BasicBlock & getEntryBlock() const
Value * CreateVScale(Constant *Scaling, const Twine &Name="")
Create a call to llvm.vscale, multiplied by Scaling.
Value * CreatePtrAdd(Value *Ptr, Value *Offset, const Twine &Name="", bool IsInBounds=false)
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
Value * CreateExtractValue(Value *Agg, ArrayRef< unsigned > Idxs, const Twine &Name="")
CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with Args, mangled using Types.
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
BasicBlock::iterator GetInsertPoint() const
Value * CreateSExt(Value *V, Type *DestTy, const Twine &Name="")
Value * CreateFreeze(Value *V, const Twine &Name="")
BasicBlock * GetInsertBlock() const
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Value * CreateNeg(Value *V, const Twine &Name="", bool HasNSW=false)
PHINode * CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name="")
InstTy * Insert(InstTy *I, const Twine &Name="") const
Insert and return the specified instruction.
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateCast(Instruction::CastOps Op, Value *V, Type *DestTy, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
CallInst * CreateCall(FunctionType *FTy, Value *Callee, ArrayRef< Value * > Args=std::nullopt, const Twine &Name="", MDNode *FPMathTag=nullptr)
Value * CreateTruncOrBitCast(Value *V, Type *DestTy, const Twine &Name="")
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
IntegerType * getInt8Ty()
Fetch the type representing an 8-bit integer.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
void setHasNoUnsignedWrap(bool b=true)
Set or clear the nuw flag on this instruction, which must be an operator which supports this flag.
void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
const BasicBlock * getParent() const
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
const Function * getFunction() const
Return the function this instruction belongs to.
bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
const Instruction * getNextNonDebugInstruction(bool SkipPseudoOp=false) const
Return a pointer to the next non-debug instruction in the same basic block as 'this',...
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Class to represent integer types.
static 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 in this loop.
BlockT * getHeader() const
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.
bool movementPreservesLCSSAForm(Instruction *Inst, Instruction *NewLoc)
Checks if moving a specific instruction can break LCSSA in any loop.
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 ...
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr, BasicBlock::iterator InsertBefore)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
Value * getIncomingValueForBlock(const BasicBlock *BB) const
static PointerType * get(Type *ElementType, unsigned AddressSpace)
This constructs a pointer to an object of the specified type in a numbered address space.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
This node represents an addition of some number of SCEVs.
This node represents a polynomial recurrence on the trip count of the specified loop.
const SCEV * getStart() const
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
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
const SCEV * getOperand() const
This class represents an assumption that the expression LHS Pred RHS evaluates to true,...
const SCEV * getRHS() const
Returns the right hand side of the predicate.
ICmpInst::Predicate getPredicate() const
const SCEV * getLHS() const
Returns the left hand side of the predicate.
This class represents a constant integer value.
Value * generateOverflowCheck(const SCEVAddRecExpr *AR, Instruction *Loc, bool Signed)
Generates code that evaluates if the AR expression will overflow.
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.
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...
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...
unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT, SmallVectorImpl< WeakTrackingVH > &DeadInsts, const TargetTransformInfo *TTI=nullptr)
replace congruent phis with their most canonical representative.
Value * expandUnionPredicate(const SCEVUnionPredicate *Pred, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
bool hoistIVInc(Instruction *IncV, Instruction *InsertPos, bool RecomputePoisonFlags=false)
Utility for hoisting IncV (with all subexpressions requried for its computation) before InsertPos.
void clear()
Erase the contents of the InsertedExpressions map so that users trying to expand the same expression ...
bool isInsertedInstruction(Instruction *I) const
Return true if the specified instruction was inserted by the code rewriter.
Value * expandCodeForPredicate(const SCEVPredicate *Pred, Instruction *Loc)
Generates a code sequence that evaluates this predicate.
static 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...
Value * expandComparePredicate(const SCEVComparePredicate *Pred, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
Value * expandCodeFor(const SCEV *SH, Type *Ty, BasicBlock::iterator I)
Insert code to directly compute the specified SCEV expression into the program.
Value * expandWrapPredicate(const SCEVWrapPredicate *P, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
Instruction * getIVIncOperand(Instruction *IncV, Instruction *InsertPos, bool allowScale)
Return the induction variable increment's IV operand.
BasicBlock::iterator findInsertPointAfter(Instruction *I, Instruction *MustDominate) const
Returns a suitable insert point after I, that dominates MustDominate.
void setInsertPoint(Instruction *IP)
Set the current insertion point.
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
size_t getNumOperands() const
bool hasNoSignedWrap() const
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
const SCEV * getOperand(unsigned i) const
ArrayRef< const SCEV * > operands() const
This class represents an assumption made using SCEV expressions which can be checked at run-time.
SCEVPredicateKind getKind() const
This class represents a cast from a pointer to a pointer-sized integer value.
This class represents a signed maximum selection.
This class represents a signed minimum selection.
This class represents a sequential/in-order unsigned minimum selection.
This class represents a sign extension of a small integer value to a larger integer value.
This class represents a truncation of an integer value to a smaller integer value.
This class represents a binary unsigned division operation.
const SCEV * getLHS() const
const SCEV * getRHS() const
This class represents an unsigned maximum selection.
This class represents an unsigned minimum selection.
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 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.
const SCEVAddRecExpr * getExpr() const
Implementation of the SCEVPredicate interface.
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.
ArrayRef< const SCEV * > operands() const
Return operands of this SCEV expression.
bool isOne() const
Return true if the expression is a constant one.
bool isZero() const
Return true if the expression is a constant zero.
bool isNonConstantNegative() const
Return true if the specified scev is negated, but not a constant.
SCEVTypes getSCEVType() const
Type * getType() const
Return the LLVM type of this SCEV expression.
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
The main scalar evolution driver.
bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
const SCEV * removePointerBase(const SCEV *S)
Compute an expression equivalent to S - getPointerBase(S).
bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
const SCEV * getConstant(ConstantInt *V)
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
bool isKnownPositive(const SCEV *S)
Test if the given expression is known to be positive.
bool containsAddRecurrence(const SCEV *S)
Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr.
const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
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...
const SCEV * getPredicatedBackedgeTakenCount(const Loop *L, SmallVector< const SCEVPredicate *, 4 > &Predicates)
Similar to getBackedgeTakenCount, except it will add a set of SCEV predicates to Predicates that are ...
static SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags)
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...
const SCEV * getNoopOrAnyExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
const SCEV * getAnyExtendExpr(const SCEV *Op, Type *Ty)
getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the give...
std::optional< SCEV::NoWrapFlags > getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO)
Parse NSW/NUW flags from add/sub/mul IR binary operation Op into SCEV no-wrap flags,...
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
bool hasComputableLoopEvolution(const SCEV *S, const Loop *L)
Return true if the given SCEV changes value in a known way in the specified loop.
const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
bool dominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV dominate the specified basic block.
const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
const SCEV * getUnknown(Value *V)
static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, int Mask)
Convenient NoWrapFlags manipulation that hides enum casts and is visible in the ScalarEvolution name ...
bool properlyDominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
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.
const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
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)
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.
unsigned getIntegerBitWidth() const
bool isVectorTy() const
True if this is an instance of VectorType.
bool isPointerTy() const
True if this is an instance of PointerType.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
static IntegerType * getInt32Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
iterator_range< value_op_iterator > operand_values()
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
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.
constexpr ScalarTy getFixedValue() const
self_iterator getIterator()
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
@ SC
CHAIN = SC CHAIN, Imm128 - System call.
cst_pred_ty< is_power2 > m_Power2()
Match an integer or vector power-of-2.
bool match(Val *V, const Pattern &P)
bind_ty< 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.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
class_match< Value > 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.
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
@ CE
Windows NT (Windows on ARM)
initializer< Ty > init(const Ty &Val)
NodeAddr< PhiNode * > Phi
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.
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
pred_iterator pred_end(BasicBlock *BB)
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.
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are are tuples (A,...
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
pred_iterator pred_begin(BasicBlock *BB)
auto reverse(ContainerTy &&C)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
cl::opt< unsigned > SCEVCheapExpansionBudget
Constant * ConstantFoldBinaryOpOperands(unsigned Opcode, Constant *LHS, Constant *RHS, const DataLayout &DL)
Attempt to constant fold a binary operation with the specified operands.
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.
@ Mul
Product of integers.
constexpr unsigned BitWidth
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 count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
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...
unsigned pred_size(const MachineBasicBlock *BB)
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.
void apply(Instruction *I)
PoisonFlags(const Instruction *I)
struct for holding enough information to help calculate the cost of the given SCEV when expanded into...
Value * visit(const SCEV *S)