52#define DEBUG_TYPE "loop-utils"
67 "Must start with an empty predecessors list!");
72 bool IsDedicatedExit =
true;
74 if (L->contains(PredBB)) {
75 if (isa<IndirectBrInst>(PredBB->getTerminator()))
81 IsDedicatedExit =
false;
84 assert(!InLoopPredecessors.
empty() &&
"Must have *some* loop predecessor!");
91 BB, InLoopPredecessors,
".loopexit", DT, LI, MSSAU, PreserveLCSSA);
95 dbgs() <<
"WARNING: Can't create a dedicated exit block for loop: "
98 LLVM_DEBUG(
dbgs() <<
"LoopSimplify: Creating dedicated exit block "
99 << NewExitBB->getName() <<
"\n");
106 for (
auto *BB : L->blocks())
109 if (L->contains(SuccBB))
113 if (!Visited.
insert(SuccBB).second)
116 Changed |= RewriteExit(SuccBB);
126 for (
auto *
Block : L->getBlocks())
129 for (
auto &Inst : *
Block) {
130 auto Users = Inst.users();
132 auto *
Use = cast<Instruction>(U);
133 return !L->contains(
Use->getParent());
220 for (
unsigned i = 1, ie = LoopID->
getNumOperands(); i < ie; ++i) {
223 if (Node->getNumOperands() == 2) {
224 MDString *S = dyn_cast<MDString>(Node->getOperand(0));
227 mdconst::extract_or_null<ConstantInt>(Node->getOperand(1));
249std::optional<ElementCount>
251 std::optional<int> Width =
256 TheLoop,
"llvm.loop.vectorize.scalable.enable");
265 const char *InheritOptionsExceptPrefix,
bool AlwaysNew) {
274 bool InheritAllAttrs = !InheritOptionsExceptPrefix;
275 bool InheritSomeAttrs =
276 InheritOptionsExceptPrefix && InheritOptionsExceptPrefix[0] !=
'\0';
280 bool Changed =
false;
281 if (InheritAllAttrs || InheritSomeAttrs) {
283 MDNode *
Op = cast<MDNode>(Existing.get());
285 auto InheritThisAttribute = [InheritSomeAttrs,
286 InheritOptionsExceptPrefix](
MDNode *
Op) {
287 if (!InheritSomeAttrs)
294 if (!isa<MDString>(NameMD))
296 StringRef AttrName = cast<MDString>(NameMD)->getString();
299 return !AttrName.
starts_with(InheritOptionsExceptPrefix);
302 if (InheritThisAttribute(
Op))
312 bool HasAnyFollowup =
false;
313 for (
StringRef OptionName : FollowupOptions) {
318 HasAnyFollowup =
true;
327 if (!AlwaysNew && !HasAnyFollowup)
331 if (!AlwaysNew && !Changed)
341 return FollowupLoopID;
356 std::optional<int> Count =
377 std::optional<int> Count =
392 std::optional<bool>
Enable =
398 std::optional<ElementCount> VectorizeWidth =
400 std::optional<int> InterleaveCount =
405 if (
Enable ==
true && VectorizeWidth && VectorizeWidth->isScalar() &&
406 InterleaveCount == 1)
415 if ((VectorizeWidth && VectorizeWidth->isScalar()) && InterleaveCount == 1)
418 if ((VectorizeWidth && VectorizeWidth->isVector()) || InterleaveCount > 1)
459 AddRegionToWorklist(
N);
461 for (
size_t I = 0;
I < Worklist.
size();
I++) {
463 AddRegionToWorklist(Child);
474 if (U !=
Cond && U != IncV)
return false;
477 if (U !=
Cond && U != PN)
return false;
484 assert((!DT || L->isLCSSAForm(*DT)) &&
"Expected LCSSA!");
485 auto *Preheader = L->getLoopPreheader();
486 assert(Preheader &&
"Preheader should exist!");
488 std::unique_ptr<MemorySSAUpdater> MSSAU;
490 MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
508 "Preheader must end with a side-effect-free terminator");
510 "Preheader must have a single successor");
538 auto *ExitBlock = L->getUniqueExitBlock();
541 assert(ExitBlock &&
"Should have a unique exit block!");
542 assert(L->hasDedicatedExits() &&
"Loop should have dedicated exits!");
550 for (
PHINode &
P : ExitBlock->phis()) {
555 P.setIncomingBlock(PredIndex, Preheader);
559 P.removeIncomingValueIf([](
unsigned Idx) {
return Idx != 0; },
562 assert((
P.getNumIncomingValues() == 1 &&
563 P.getIncomingBlock(PredIndex) == Preheader) &&
564 "Should have exactly one value and that's from the preheader!");
568 DTU.
applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}});
570 MSSAU->applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}},
583 assert(L->hasNoExitBlocks() &&
584 "Loop should have either zero or one exit blocks.");
592 DTU.
applyUpdates({{DominatorTree::Delete, Preheader, L->getHeader()}});
594 MSSAU->applyUpdates({{DominatorTree::Delete, Preheader, L->getHeader()}},
598 MSSAU->removeBlocks(DeadBlockSet);
618 for (
auto *
Block : L->blocks())
622 if (
auto *Usr = dyn_cast<Instruction>(U.getUser()))
623 if (L->contains(Usr->getParent()))
629 "Unexpected user in reachable block");
634 if (
Block->IsNewDbgInfoFormat) {
638 DPV.getDebugLoc().get());
639 if (!DeadDebugSet.
insert(Key).second)
642 DPV.removeFromParent();
650 auto *DVI = dyn_cast<DbgVariableIntrinsic>(&
I);
666 ExitBlock->getFirstInsertionPt();
667 assert(InsertDbgValueBefore != ExitBlock->end() &&
668 "There should be a non-PHI instruction in exit block, else these "
669 "instructions will have no parent.");
671 for (
auto *DVI : DeadDebugInst)
672 DVI->moveBefore(*ExitBlock, InsertDbgValueBefore);
679 ExitBlock->insertDPValueBefore(DPV, InsertDbgValueBefore);
684 for (
auto *
Block : L->blocks())
685 Block->dropAllReferences();
696 BB->eraseFromParent();
702 blocks.insert(L->block_begin(), L->block_end());
710 if (
Loop *ParentLoop = L->getParentLoop()) {
712 assert(
I != ParentLoop->end() &&
"Couldn't find loop");
713 ParentLoop->removeChildLoop(
I);
716 assert(
I != LI->
end() &&
"Couldn't find loop");
725 auto *Latch = L->getLoopLatch();
726 assert(Latch &&
"multiple latches not yet supported");
727 auto *Header = L->getHeader();
728 Loop *OutermostLoop = L->getOutermostLoop();
733 std::unique_ptr<MemorySSAUpdater> MSSAU;
735 MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
740 if (
auto *BI = dyn_cast<BranchInst>(Latch->getTerminator())) {
741 if (!BI->isConditional()) {
750 if (L->isLoopExiting(Latch)) {
755 const unsigned ExitIdx = L->contains(BI->getSuccessor(0)) ? 1 : 0;
756 BasicBlock *ExitBB = BI->getSuccessor(ExitIdx);
759 Header->removePredecessor(Latch,
true);
762 auto *NewBI = Builder.
CreateBr(ExitBB);
766 LLVMContext::MD_annotation});
768 BI->eraseFromParent();
769 DTU.
applyUpdates({{DominatorTree::Delete, Latch, Header}});
771 MSSAU->applyUpdates({{DominatorTree::Delete, Latch, Header}}, DT);
779 auto *BackedgeBB =
SplitEdge(Latch, Header, &DT, &LI, MSSAU.get());
783 true, &DTU, MSSAU.get());
795 if (OutermostLoop != L)
809 if (!LatchBR || LatchBR->
getNumSuccessors() != 2 || !L->isLoopExiting(Latch))
814 "At least one edge out of the latch must go to the header");
838 OrigExitWeight = ExitWeight;
844 return ExitCount + 1;
847std::optional<unsigned>
849 unsigned *EstimatedLoopInvocationWeight) {
856 if (std::optional<uint64_t> EstTripCount =
858 if (EstimatedLoopInvocationWeight)
859 *EstimatedLoopInvocationWeight = ExitWeight;
860 return *EstTripCount;
867 unsigned EstimatedloopInvocationWeight) {
876 unsigned LatchExitWeight = 0;
877 unsigned BackedgeTakenWeight = 0;
879 if (EstimatedTripCount > 0) {
880 LatchExitWeight = EstimatedloopInvocationWeight;
881 BackedgeTakenWeight = (EstimatedTripCount - 1) * LatchExitWeight;
886 std::swap(BackedgeTakenWeight, LatchExitWeight);
892 LLVMContext::MD_prof,
906 const SCEV *InnerLoopBECountSC = SE.
getExitCount(InnerLoop, InnerLoopLatch);
907 if (isa<SCEVCouldNotCompute>(InnerLoopBECountSC) ||
924 case RecurKind::UMin:
925 return Intrinsic::umin;
926 case RecurKind::UMax:
927 return Intrinsic::umax;
928 case RecurKind::SMin:
929 return Intrinsic::smin;
930 case RecurKind::SMax:
931 return Intrinsic::smax;
932 case RecurKind::FMin:
933 return Intrinsic::minnum;
934 case RecurKind::FMax:
935 return Intrinsic::maxnum;
936 case RecurKind::FMinimum:
937 return Intrinsic::minimum;
938 case RecurKind::FMaximum:
939 return Intrinsic::maximum;
947 case RecurKind::UMin:
949 case RecurKind::UMax:
951 case RecurKind::SMin:
953 case RecurKind::SMax:
955 case RecurKind::FMin:
957 case RecurKind::FMax:
967 if (
auto VTy = dyn_cast<VectorType>(
Left->getType()))
978 (RK == RecurKind::FMinimum || RK == RecurKind::FMaximum)) {
993 unsigned VF = cast<FixedVectorType>(Src->getType())->getNumElements();
998 for (
unsigned ExtractIdx = 0; ExtractIdx != VF; ++ExtractIdx) {
1002 if (
Op != Instruction::ICmp &&
Op != Instruction::FCmp) {
1018 unsigned VF = cast<FixedVectorType>(Src->getType())->getNumElements();
1023 "Reduction emission only supported for pow2 vectors!");
1031 Value *TmpVec = Src;
1033 for (
unsigned i = VF; i != 1; i >>= 1) {
1035 for (
unsigned j = 0; j != i / 2; ++j)
1036 ShuffleMask[j] = i / 2 + j;
1039 std::fill(&ShuffleMask[i / 2], ShuffleMask.
end(), -1);
1043 if (
Op != Instruction::ICmp &&
Op != Instruction::FCmp) {
1061 "Unexpected reduction kind");
1062 Value *InitVal =
Desc.getRecurrenceStartValue();
1063 Value *NewVal =
nullptr;
1068 for (
auto *U : OrigPhi->
users()) {
1069 if ((SI = dyn_cast<SelectInst>(U)))
1072 assert(SI &&
"One user of the original phi should be a select");
1074 if (SI->getTrueValue() == OrigPhi)
1075 NewVal = SI->getFalseValue();
1077 assert(SI->getFalseValue() == OrigPhi &&
1078 "At least one input to the select should be the original Phi");
1079 NewVal = SI->getTrueValue();
1084 ElementCount EC = cast<VectorType>(Src->getType())->getElementCount();
1091 return Builder.
CreateSelect(Cmp, NewVal, InitVal,
"rdx.select");
1096 auto *SrcVecEltTy = cast<VectorType>(Src->getType())->getElementType();
1098 case RecurKind::Add:
1100 case RecurKind::Mul:
1102 case RecurKind::And:
1106 case RecurKind::Xor:
1108 case RecurKind::FMulAdd:
1109 case RecurKind::FAdd:
1112 case RecurKind::FMul:
1114 case RecurKind::SMax:
1116 case RecurKind::SMin:
1118 case RecurKind::UMax:
1120 case RecurKind::UMin:
1122 case RecurKind::FMax:
1124 case RecurKind::FMin:
1126 case RecurKind::FMinimum:
1128 case RecurKind::FMaximum:
1142 B.setFastMathFlags(
Desc.getFastMathFlags());
1154 assert((
Desc.getRecurrenceKind() == RecurKind::FAdd ||
1155 Desc.getRecurrenceKind() == RecurKind::FMulAdd) &&
1156 "Unexpected reduction kind");
1157 assert(Src->getType()->isVectorTy() &&
"Expected a vector type");
1158 assert(!Start->getType()->isVectorTy() &&
"Expected a scalar type");
1160 return B.CreateFAddReduce(Start, Src);
1164 bool IncludeWrapFlags) {
1165 auto *VecOp = dyn_cast<Instruction>(
I);
1168 auto *Intersection = (OpValue ==
nullptr) ? dyn_cast<Instruction>(VL[0])
1169 : dyn_cast<Instruction>(OpValue);
1172 const unsigned Opcode = Intersection->getOpcode();
1173 VecOp->copyIRFlags(Intersection, IncludeWrapFlags);
1174 for (
auto *V : VL) {
1175 auto *Instr = dyn_cast<Instruction>(V);
1178 if (OpValue ==
nullptr ||
Opcode == Instr->getOpcode())
1179 VecOp->andIRFlags(V);
1216 auto Predicate =
Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
1227 auto Predicate =
Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
1243 while (!WorkList.
empty()) {
1246 if (!L->contains(Curr))
1252 for (
const auto *U : Curr->
users()) {
1253 auto *UI = cast<Instruction>(U);
1254 if (Visited.
insert(UI).second)
1280 BasicBlock *Preheader = L->getLoopPreheader();
1290 L->getExitingBlocks(ExitingBlocks);
1292 L->getUniqueExitBlocks(ExitBlocks);
1293 if (ExitBlocks.
size() != 1 || ExitingBlocks.
size() != 1)
1298 while (
PHINode *
P = dyn_cast<PHINode>(BI)) {
1299 Value *Incoming =
P->getIncomingValueForBlock(ExitingBlocks[0]);
1305 for (
const RewritePhi &Phi : RewritePhiSet) {
1306 unsigned i = Phi.Ith;
1307 if (Phi.PN ==
P && (Phi.PN)->getIncomingValue(i) == Incoming) {
1314 if (!found && (
I = dyn_cast<Instruction>(Incoming)))
1315 if (!L->hasLoopInvariantOperands(
I))
1321 for (
auto *BB : L->blocks())
1323 return I.mayHaveSideEffects();
1337 if (!L->getLoopPreheader())
1339 if (Phi->getParent() != L->getHeader())
1351 assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
1352 "Indvars did not preserve LCSSA!");
1355 L->getUniqueExitBlocks(ExitBlocks);
1364 PHINode *PN = dyn_cast<PHINode>(ExitBB->begin());
1371 while ((PN = dyn_cast<PHINode>(BBI++))) {
1379 for (
unsigned i = 0; i != NumPreds; ++i) {
1383 if (!isa<Instruction>(InVal))
1392 if (!L->contains(Inst))
1402 PHINode *IndPhi = dyn_cast<PHINode>(Inst);
1409 if (!isa<PHINode>(U) && !isa<BinaryOperator>(U))
1411 BinaryOperator *B = dyn_cast<BinaryOperator>(U);
1412 if (B && B != ID.getInductionBinOp())
1424 PHINode *Phi = dyn_cast<PHINode>(U);
1425 if (Phi != PN && !checkIsIndPhi(Phi, L, SE, ID))
1430 if (
B !=
ID.getInductionBinOp())
1442 if (isa<SCEVCouldNotCompute>(ExitValue) ||
1444 !
Rewriter.isSafeToExpand(ExitValue)) {
1450 if (isa<SCEVCouldNotCompute>(ExitCount))
1452 if (
auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE->
getSCEV(Inst)))
1453 if (AddRec->getLoop() == L)
1454 ExitValue = AddRec->evaluateAtIteration(ExitCount, *SE);
1455 if (isa<SCEVCouldNotCompute>(ExitValue) ||
1457 !
Rewriter.isSafeToExpand(ExitValue))
1471 bool HighCost =
Rewriter.isHighCostExpansion(
1482 (isa<PHINode>(Inst) || isa<LandingPadInst>(Inst)) ?
1484 RewritePhiSet.
emplace_back(PN, i, ExitValue, InsertPt, HighCost);
1495 int NumReplaced = 0;
1498 for (
const RewritePhi &Phi : RewritePhiSet) {
1505 !LoopCanBeDel && Phi.HighCost)
1509 Phi.ExpansionSCEV, Phi.PN->getType(), Phi.ExpansionPoint);
1511 LLVM_DEBUG(
dbgs() <<
"rewriteLoopExitValues: AfterLoopVal = " << *ExitVal
1513 <<
" LoopVal = " << *(Phi.ExpansionPoint) <<
"\n");
1519 if (
auto *ExitInsn = dyn_cast<Instruction>(ExitVal))
1520 if (
auto *EVL = LI->
getLoopFor(ExitInsn->getParent()))
1522 assert(EVL->contains(L) &&
"LCSSA breach detected!");
1558 assert(UF > 0 &&
"Zero unrolled factor is not supported");
1559 assert(UnrolledLoop != RemainderLoop &&
1560 "Unrolled and Remainder loops are expected to distinct");
1563 unsigned OrigLoopInvocationWeight = 0;
1564 std::optional<unsigned> OrigAverageTripCount =
1566 if (!OrigAverageTripCount)
1570 unsigned UnrolledAverageTripCount = *OrigAverageTripCount / UF;
1572 unsigned RemainderAverageTripCount = *OrigAverageTripCount % UF;
1575 OrigLoopInvocationWeight);
1577 OrigLoopInvocationWeight);
1583template <
typename RangeT>
1593 assert(PreOrderLoops.
empty() &&
"Must start with an empty preorder walk.");
1595 "Must start with an empty preorder walk worklist.");
1599 PreOrderWorklist.
append(L->begin(), L->end());
1601 }
while (!PreOrderWorklist.
empty());
1603 Worklist.
insert(std::move(PreOrderLoops));
1604 PreOrderLoops.
clear();
1608template <
typename RangeT>
1614template void llvm::appendLoopsToWorklist<ArrayRef<Loop *> &>(
1618llvm::appendLoopsToWorklist<Loop &>(
Loop &L,
1630 PL->addChildLoop(&New);
1640 New.addBasicBlockToLoop(cast<BasicBlock>(VM[BB]), *LI);
1667 Value *Start =
nullptr, *
End =
nullptr;
1682 isa<SCEVAddRecExpr>(
High) && isa<SCEVAddRecExpr>(
Low)) {
1683 auto *HighAR = cast<SCEVAddRecExpr>(
High);
1684 auto *LowAR = cast<SCEVAddRecExpr>(
Low);
1686 const SCEV *Recur = LowAR->getStepRecurrence(*Exp.getSE());
1687 if (Recur == HighAR->getStepRecurrence(*Exp.getSE()) &&
1688 HighAR->getLoop() == OuterLoop && LowAR->getLoop() == OuterLoop) {
1690 const SCEV *OuterExitCount =
1691 Exp.getSE()->getExitCount(OuterLoop, OuterLoopLatch);
1692 if (!isa<SCEVCouldNotCompute>(OuterExitCount) &&
1694 const SCEV *NewHigh = cast<SCEVAddRecExpr>(
High)->evaluateAtIteration(
1695 OuterExitCount, *Exp.getSE());
1696 if (!isa<SCEVCouldNotCompute>(NewHigh)) {
1697 LLVM_DEBUG(
dbgs() <<
"LAA: Expanded RT check for range to include "
1698 "outer loop in order to permit hoisting\n");
1700 Low = cast<SCEVAddRecExpr>(
Low)->getStart();
1703 if (!Exp.getSE()->isKnownNonNegative(Recur)) {
1707 << *Stride <<
'\n');
1714 Start = Exp.expandCodeFor(
Low, PtrArithTy, Loc);
1715 End = Exp.expandCodeFor(
High, PtrArithTy, Loc);
1718 Start = Builder.
CreateFreeze(Start, Start->getName() +
".fr");
1722 Stride ? Exp.expandCodeFor(Stride, Stride->getType(), Loc) :
nullptr;
1724 return {Start,
End, StrideVal};
1736 transform(PointerChecks, std::back_inserter(ChecksWithBounds),
1742 return std::make_pair(
First, Second);
1745 return ChecksWithBounds;
1754 auto ExpandedChecks =
1762 Value *MemoryRuntimeCheck =
nullptr;
1764 for (
const auto &
Check : ExpandedChecks) {
1769 assert((
A.Start->getType()->getPointerAddressSpace() ==
1770 B.End->getType()->getPointerAddressSpace()) &&
1771 (
B.Start->getType()->getPointerAddressSpace() ==
1772 A.End->getType()->getPointerAddressSpace()) &&
1773 "Trying to bounds check pointers with different address spaces");
1785 Value *IsConflict = ChkBuilder.
CreateAnd(Cmp0, Cmp1,
"found.conflict");
1786 if (
A.StrideToCheck) {
1790 IsConflict = ChkBuilder.
CreateOr(IsConflict, IsNegativeStride);
1792 if (
B.StrideToCheck) {
1796 IsConflict = ChkBuilder.
CreateOr(IsConflict, IsNegativeStride);
1798 if (MemoryRuntimeCheck) {
1800 ChkBuilder.
CreateOr(MemoryRuntimeCheck, IsConflict,
"conflict.rdx");
1802 MemoryRuntimeCheck = IsConflict;
1805 return MemoryRuntimeCheck;
1817 Value *MemoryRuntimeCheck =
nullptr;
1819 auto &SE = *Expander.
getSE();
1823 for (
const auto &
C : Checks) {
1824 Type *Ty =
C.SinkStart->getType();
1826 auto *VFTimesUFTimesSize =
1830 SE.getMinusSCEV(
C.SinkStart,
C.SrcStart), Ty, Loc);
1834 Value *IsConflict = SeenCompares.
lookup({Diff, VFTimesUFTimesSize});
1839 ChkBuilder.
CreateICmpULT(Diff, VFTimesUFTimesSize,
"diff.check");
1840 SeenCompares.
insert({{Diff, VFTimesUFTimesSize}, IsConflict});
1844 if (MemoryRuntimeCheck) {
1846 ChkBuilder.
CreateOr(MemoryRuntimeCheck, IsConflict,
"conflict.rdx");
1848 MemoryRuntimeCheck = IsConflict;
1851 return MemoryRuntimeCheck;
1854std::optional<IVConditionInfo>
1857 auto *TI = dyn_cast<BranchInst>(L.getHeader()->getTerminator());
1858 if (!TI || !TI->isConditional())
1861 auto *CondI = dyn_cast<CmpInst>(TI->getCondition());
1864 if (!CondI || !L.contains(CondI))
1871 WorkList.
append(CondI->op_begin(), CondI->op_end());
1875 while (!WorkList.
empty()) {
1877 if (!
I || !L.contains(
I))
1881 if (!isa<LoadInst>(
I) && !isa<GetElementPtrInst>(
I))
1885 if (
auto *LI = dyn_cast<LoadInst>(
I))
1886 if (LI->isVolatile() || LI->isAtomic())
1891 if (
auto *MemUse = dyn_cast_or_null<MemoryUse>(MA)) {
1893 AccessesToCheck.
push_back(MemUse->getDefiningAccess());
1901 WorkList.
append(
I->op_begin(),
I->op_end());
1904 if (InstToDuplicate.
empty())
1908 L.getExitingBlocks(ExitingBlocks);
1909 auto HasNoClobbersOnPath =
1910 [&L, &AA, &AccessedLocs, &ExitingBlocks, &InstToDuplicate,
1913 -> std::optional<IVConditionInfo> {
1925 while (!WorkList.
empty()) {
1927 if (!L.contains(Current))
1929 const auto &SeenIns = Seen.
insert(Current);
1930 if (!SeenIns.second)
1934 *Current, [](
Instruction &
I) {
return !
I.mayHaveSideEffects(); });
1940 if (Seen.
size() < 2)
1948 while (!AccessesToCheck.
empty()) {
1950 auto SeenI = SeenAccesses.
insert(Current);
1959 if (isa<MemoryUse>(Current))
1964 if (
auto *CurrentDef = dyn_cast<MemoryDef>(Current)) {
1972 for (
Use &U : Current->
uses())
1973 AccessesToCheck.
push_back(cast<MemoryAccess>(U.getUser()));
1983 if (
Info.PathIsNoop) {
1984 for (
auto *Exiting : ExitingBlocks) {
1988 if (L.contains(Succ))
1991 Info.PathIsNoop &= Succ->phis().empty() &&
1992 (!
Info.ExitForPath ||
Info.ExitForPath == Succ);
1993 if (!
Info.PathIsNoop)
1996 "cannot have multiple exit blocks");
1997 Info.ExitForPath = Succ;
2001 if (!
Info.ExitForPath)
2002 Info.PathIsNoop =
false;
2004 Info.InstToDuplicate = InstToDuplicate;
2010 if (TI->getSuccessor(0) == TI->getSuccessor(1))
2013 if (
auto Info = HasNoClobbersOnPath(TI->getSuccessor(0), L.getHeader(),
2018 if (
auto Info = HasNoClobbersOnPath(TI->getSuccessor(1), L.getHeader(),
amdgpu AMDGPU Register Bank Select
This is the interface for LLVM's primary stateless and local alias analysis.
bbsections Prepares for basic block by splitting functions into clusters of basic blocks
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
Analysis containing CSE Info
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
This file defines the DenseSet and SmallDenseSet classes.
This is the interface for a simple mod/ref and alias analysis over globals.
static const HTTPClientCleanup Cleanup
iv Induction Variable Users
static cl::opt< ReplaceExitVal > ReplaceExitValue("replexitval", cl::Hidden, cl::init(OnlyCheapRepl), cl::desc("Choose the strategy to replace exit value in IndVarSimplify"), cl::values(clEnumValN(NeverRepl, "never", "never replace exit value"), clEnumValN(OnlyCheapRepl, "cheap", "only replace exit value when the cost is cheap"), clEnumValN(UnusedIndVarInLoop, "unusedindvarinloop", "only replace exit value when it is an unused " "induction variable in the loop and has cheap replacement cost"), clEnumValN(NoHardUse, "noharduse", "only replace exit values when loop def likely dead"), clEnumValN(AlwaysRepl, "always", "always replace exit value whenever possible")))
static cl::opt< bool, true > HoistRuntimeChecks("hoist-runtime-checks", cl::Hidden, cl::desc("Hoist inner loop runtime memory checks to outer loop if possible"), cl::location(VectorizerParams::HoistRuntimeChecks), cl::init(false))
static std::optional< uint64_t > getEstimatedTripCount(BranchInst *ExitingBranch, Loop *L, uint64_t &OrigExitWeight)
Return the estimated trip count for any exiting branch which dominates the loop latch.
static bool hasHardUserWithinLoop(const Loop *L, const Instruction *I)
static const char * LLVMLoopDisableLICM
static PointerBounds expandBounds(const RuntimeCheckingPtrGroup *CG, Loop *TheLoop, Instruction *Loc, SCEVExpander &Exp, bool HoistRuntimeChecks)
Expand code for the lower and upper bound of the pointer group CG in TheLoop.
static bool canLoopBeDeleted(Loop *L, SmallVector< RewritePhi, 8 > &RewritePhiSet)
static const char * LLVMLoopDisableNonforced
static MDNode * createStringMetadata(Loop *TheLoop, StringRef Name, unsigned V)
Create MDNode for input string.
static BranchInst * getExpectedExitLoopLatchBranch(Loop *L)
Checks if L has an exiting latch branch.
static bool checkIsIndPhi(PHINode *Phi, Loop *L, ScalarEvolution *SE, InductionDescriptor &ID)
Checks if it is safe to call InductionDescriptor::isInductionPHI for Phi, and returns true if this Ph...
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
Module.h This file contains the declarations for the Module class.
#define INITIALIZE_PASS_DEPENDENCY(depName)
This file provides a priority worklist.
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This is the interface for a SCEV-based alias analysis.
This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...
This file implements a set that has insertion order iteration characteristics.
static cl::opt< unsigned > MSSAThreshold("simple-loop-unswitch-memoryssa-threshold", cl::desc("Max number of memory uses to explore during " "partial unswitching analysis"), cl::init(100), cl::Hidden)
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
Virtual Register Rewriter
static constexpr uint32_t Opcode
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
Check whether or not an instruction may read or write the optionally specified memory location.
Class for arbitrary precision integers.
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequiredID(const void *ID)
AnalysisUsage & addPreservedID(const void *ID)
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Legacy wrapper pass to provide the BasicAAResult object.
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...
InstListType::iterator iterator
Instruction iterators...
LLVMContext & getContext() const
Get the context in which this basic block lives.
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...
Conditional or Unconditional Branch instruction.
unsigned getNumSuccessors() const
BasicBlock * getSuccessor(unsigned i) const
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ FCMP_OLT
0 1 0 0 True if ordered and less than
@ FCMP_OGT
0 0 1 0 True if ordered and greater than
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
static Constant * get(Type *Ty, double V)
This returns a ConstantFP, or a vector containing a splat of a ConstantFP, for the specified value in...
static Constant * getNegativeZero(Type *Ty)
This is the shared class of boolean and integer constants.
static ConstantInt * getTrue(LLVMContext &Context)
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
static ConstantInt * getFalse(LLVMContext &Context)
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
Record of a variable value-assignment, aka a non instruction representation of the dbg....
This class represents an Operation in the Expression.
uint64_t getNumOperands() const
Identifies a unique instance of a variable.
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
static constexpr ElementCount get(ScalarTy MinVal, bool Scalable)
Legacy wrapper pass to provide the GlobalsAAResult object.
Common base class shared among various IRBuilders.
CallInst * CreateMulReduce(Value *Src)
Create a vector int mul reduction intrinsic of the source vector.
CallInst * CreateFAddReduce(Value *Acc, Value *Src)
Create a sequential vector fadd reduction intrinsic of the source vector.
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
UnreachableInst * CreateUnreachable()
CallInst * CreateAndReduce(Value *Src)
Create a vector int AND reduction intrinsic of the source vector.
Value * CreateVectorSplat(unsigned NumElts, Value *V, const Twine &Name="")
Return a vector value that contains.
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)
CallInst * CreateAddReduce(Value *Src)
Create a vector int add reduction intrinsic of the source vector.
Value * CreateFreeze(Value *V, const Twine &Name="")
CallInst * CreateXorReduce(Value *Src)
Create a vector int XOR reduction intrinsic of the source vector.
CallInst * CreateOrReduce(Value *Src)
Create a vector int OR reduction intrinsic of the source vector.
CallInst * CreateFPMinReduce(Value *Src)
Create a vector float min reduction intrinsic of the source vector.
CallInst * CreateFPMaximumReduce(Value *Src)
Create a vector float maximum reduction intrinsic of the source vector.
CallInst * CreateFPMaxReduce(Value *Src)
Create a vector float max reduction intrinsic of the source vector.
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Value * CreateCmp(CmpInst::Predicate Pred, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
Value * CreateShuffleVector(Value *V1, Value *V2, Value *Mask, const Twine &Name="")
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
CallInst * CreateIntMaxReduce(Value *Src, bool IsSigned=false)
Create a vector integer max reduction intrinsic of the source vector.
ConstantInt * getFalse()
Get the constant value for i1 false.
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Value * CreateICmpSLT(Value *LHS, Value *RHS, const Twine &Name="")
CallInst * CreateIntMinReduce(Value *Src, bool IsSigned=false)
Create a vector integer min reduction intrinsic of the source vector.
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
CallInst * CreateFMulReduce(Value *Acc, Value *Src)
Create a sequential vector fmul reduction intrinsic of the source vector.
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
CallInst * CreateFPMinimumReduce(Value *Src)
Create a vector float minimum reduction intrinsic of the source vector.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
A struct for saving information about induction variables.
static bool isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D, const SCEV *Expr=nullptr, SmallVectorImpl< Instruction * > *CastsToIgnore=nullptr)
Returns true if Phi is an induction in the loop L.
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
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.
bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
This is an important class for using LLVM in a threaded context.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
BlockT * getHeader() const
std::vector< Loop * >::const_iterator iterator
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
void removeBlock(BlockT *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
LoopT * AllocateLoop(ArgsTy &&...Args)
LoopT * removeLoop(iterator I)
This removes the specified top-level loop from this loop info object.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
void destroy(LoopT *L)
Destroy a loop that has been removed from the LoopInfo nest.
The legacy pass manager's analysis pass to compute loop information.
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Represents a single loop in the control flow graph.
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight)
Return metadata containing two branch weights.
void replaceOperandWith(unsigned I, Metadata *New)
Replace a specific operand.
const MDOperand & getOperand(unsigned I) const
ArrayRef< MDOperand > operands() const
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
unsigned getNumOperands() const
Return number of MDNode operands.
LLVMContext & getContext() const
Tracking metadata reference owned by Metadata.
StringRef getString() const
static MDString * get(LLVMContext &Context, StringRef Str)
BasicBlock * getBlock() const
Representation for a specific memory location.
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
Legacy analysis pass which computes MemorySSA.
Encapsulates MemorySSA, including all data associated with memory accesses.
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
void setIncomingValue(unsigned i, Value *V)
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
bool insert(const T &X)
Insert a new element into the PriorityWorklist.
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
static bool isAnyOfRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...
static bool isMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is any min/max kind.
A global registry used in conjunction with static constructors to make pluggable components (like tar...
Legacy wrapper pass to provide the SCEVAAResult object.
This class uses information about analyze scalars to rewrite expressions in canonical form.
ScalarEvolution * getSE()
Value * expandCodeFor(const SCEV *SH, Type *Ty, BasicBlock::iterator I)
Insert code to directly compute the specified SCEV expression into the program.
This class represents an analyzed expression in the program.
Type * getType() const
Return the LLVM type of this SCEV expression.
The main scalar evolution driver.
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
const SCEV * getConstant(ConstantInt *V)
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
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...
void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
@ LoopInvariant
The SCEV is loop-invariant.
bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS.
This class represents the LLVM 'select' instruction.
Implements a dense probed hash-table based set with some number of buckets stored inline.
A version of PriorityWorklist that selects small size optimized data structures for the vector and ma...
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.
A SetVector that performs no allocations if smaller than a certain size.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
bool starts_with(StringRef Prefix) const
Check if this string starts with the given Prefix.
bool equals(StringRef RHS) const
equals - Check for string equality, this is more efficient than compare() when the relative ordering ...
Provides information about what library functions are available for the current target.
Value handle that tracks a Value across RAUW.
The instances of the Type class are immutable: once they are created, they are never changed.
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
static IntegerType * getInt32Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
A Use represents the edge between a Value definition and its users.
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.
iterator_range< user_iterator > users()
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< use_iterator > uses()
StringRef getName() const
Return a constant reference to the value's name.
std::pair< iterator, bool > insert(const ValueT &V)
An efficient, type-erasing, non-owning reference to a callable.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
std::optional< ElementCount > getOptionalElementCountLoopAttribute(const Loop *TheLoop)
Find a combination of metadata ("llvm.loop.vectorize.width" and "llvm.loop.vectorize....
@ Low
Lower the current thread's priority such that it does not affect foreground tasks significantly.
SmallVector< DomTreeNode *, 16 > collectChildrenInLoop(DomTreeNode *N, const Loop *CurLoop)
Does a BFS from a given node to all of its children inside a given loop.
Interval::succ_iterator succ_end(Interval *I)
Value * addRuntimeChecks(Instruction *Loc, Loop *TheLoop, const SmallVectorImpl< RuntimePointerCheck > &PointerChecks, SCEVExpander &Expander, bool HoistRuntimeChecks=false)
Add code that checks at runtime if the accessed arrays in PointerChecks overlap.
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
std::optional< unsigned > getLoopEstimatedTripCount(Loop *L, unsigned *EstimatedLoopInvocationWeight=nullptr)
Returns a loop's estimated trip count based on branch weight metadata.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
bool getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name)
Returns true if Name is applied to TheLoop and enabled.
std::pair< const RuntimeCheckingPtrGroup *, const RuntimeCheckingPtrGroup * > RuntimePointerCheck
A memcheck which made up of a pair of grouped pointers.
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
bool isKnownNonPositiveInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)
Returns true if we can prove that S is defined and always non-positive in loop L.
Value * createSimpleTargetReduction(IRBuilderBase &B, Value *Src, RecurKind RdxKind)
Create a target reduction of the given vector.
std::optional< bool > getOptionalBoolLoopAttribute(const Loop *TheLoop, StringRef Name)
void appendReversedLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
auto successors(const MachineBasicBlock *BB)
void initializeLoopPassPass(PassRegistry &)
Manually defined generic "LoopPass" dependency initialization.
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
std::optional< MDNode * > makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef< StringRef > FollowupAttrs, const char *InheritOptionsAttrsPrefix="", bool AlwaysNew=false)
Create a new loop identifier for a loop created from a loop transformation.
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Intrinsic::ID getMinMaxReductionIntrinsicOp(RecurKind RK)
Returns the min/max intrinsic used when expanding a min/max reduction.
Value * createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left, Value *Right)
Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, unsigned V=0)
Set input string into loop metadata by keeping other values intact.
bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, bool Signed)
Returns true if S is defined and never is equal to signed/unsigned max.
TransformationMode hasVectorizeTransformation(const Loop *L)
OutputIt transform(R &&Range, OutputIt d_first, UnaryFunction F)
Wrapper function around std::transform to apply a function to a range and store the result elsewhere.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
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.
uint64_t divideNearest(uint64_t Numerator, uint64_t Denominator)
Returns the integer nearest(Numerator / Denominator).
SmallVector< Instruction *, 8 > findDefsUsedOutsideOfLoop(Loop *L)
Returns the instructions that use values defined in the loop.
auto reverse(ContainerTy &&C)
bool isMustProgress(const Loop *L)
Return true if this loop can be assumed to make progress.
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
bool isModSet(const ModRefInfo MRI)
TransformationMode hasUnrollAndJamTransformation(const Loop *L)
void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI, MemorySSA *MSSA=nullptr)
This function deletes dead loops.
Value * getShuffleReduction(IRBuilderBase &Builder, Value *Src, unsigned Op, RecurKind MinMaxKind=RecurKind::None)
Generates a vector reduction using shufflevectors to reduce the value.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool hasDisableAllTransformsHint(const Loop *L)
Look for the loop attribute that disables all transformation heuristic.
Value * createOrderedReduction(IRBuilderBase &B, const RecurrenceDescriptor &Desc, Value *Src, Value *Start)
Create an ordered reduction intrinsic using the given recurrence descriptor Desc.
cl::opt< unsigned > SCEVCheapExpansionBudget
TransformationMode hasUnrollTransformation(const Loop *L)
TransformationMode hasDistributeTransformation(const Loop *L)
void breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA)
Remove the backedge of the specified loop.
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
void propagateIRFlags(Value *I, ArrayRef< Value * > VL, Value *OpValue=nullptr, bool IncludeWrapFlags=true)
Get the intersection (logical and) of all of the potential IR flags of each scalar operation (VL) tha...
bool isKnownPositiveInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)
Returns true if we can prove that S is defined and always positive in loop L.
unsigned changeToUnreachable(Instruction *I, bool PreserveLCSSA=false, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...
std::optional< int > getOptionalIntLoopAttribute(const Loop *TheLoop, StringRef Name)
Find named metadata for a loop with an integer value.
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
CmpInst::Predicate getMinMaxReductionPredicate(RecurKind RK)
Returns the comparison predicate used when expanding a min/max reduction.
TransformationMode hasLICMVersioningTransformation(const Loop *L)
bool VerifyMemorySSA
Enables verification of MemorySSA.
TransformationMode
The mode sets how eager a transformation should be applied.
@ TM_Unspecified
The pass can use heuristics to determine whether a transformation should be applied.
@ TM_SuppressedByUser
The transformation must not be applied.
@ TM_ForcedByUser
The transformation was directed by the user, e.g.
@ TM_Disable
The transformation should not be applied.
@ TM_Enable
The transformation should be applied without considering a cost model.
bool hasDisableLICMTransformsHint(const Loop *L)
Look for the loop attribute that disables the LICM transformation heuristics.
RecurKind
These are the kinds of recurrences that we support.
bool setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount, unsigned EstimatedLoopInvocationWeight)
Set a loop's branch weight metadata to reflect that loop has EstimatedTripCount iterations and Estima...
Value * createAnyOfOp(IRBuilderBase &Builder, Value *StartVal, RecurKind RK, Value *Left, Value *Right)
See RecurrenceDescriptor::isAnyOfPattern for a description of the pattern we are trying to match.
void setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop, Loop *RemainderLoop, uint64_t UF)
Set weights for UnrolledLoop and RemainderLoop based on weights for OrigLoop and the following distri...
bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Ensure that all exit blocks of the loop are dedicated exits.
DWARFExpression::Operation Op
void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
bool isKnownNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)
Returns true if we can prove that S is defined and always negative in loop L.
constexpr unsigned BitWidth
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
bool hasIterationCountInvariantInParent(Loop *L, ScalarEvolution &SE)
Check inner loop (L) backedge count is known to be invariant on all iterations of its outer loop.
bool isAlmostDeadIV(PHINode *IV, BasicBlock *LatchBlock, Value *Cond)
Return true if the induction variable IV in a Loop whose latch is LatchBlock would become dead if the...
auto predecessors(const MachineBasicBlock *BB)
int rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI, ScalarEvolution *SE, const TargetTransformInfo *TTI, SCEVExpander &Rewriter, DominatorTree *DT, ReplaceExitVal ReplaceExitValue, SmallVector< WeakTrackingVH, 16 > &DeadInsts)
If the final value of any expressions that are recurrent in the loop can be computed,...
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Value * addDiffRuntimeChecks(Instruction *Loc, ArrayRef< PointerDiffInfo > Checks, SCEVExpander &Expander, function_ref< Value *(IRBuilderBase &, unsigned)> GetVF, unsigned IC)
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
std::optional< IVConditionInfo > hasPartialIVCondition(const Loop &L, unsigned MSSAThreshold, const MemorySSA &MSSA, AAResults &AA)
Check if the loop header has a conditional branch that is not loop-invariant, because it involves loa...
bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, bool Signed)
Returns true if S is defined and never is equal to signed/unsigned min.
bool isKnownNonNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)
Returns true if we can prove that S is defined and always non-negative in loop L.
Value * getOrderedReduction(IRBuilderBase &Builder, Value *Acc, Value *Src, unsigned Op, RecurKind MinMaxKind=RecurKind::None)
Generates an ordered vector reduction using extracts to reduce the value.
MDNode * findOptionMDForLoopID(MDNode *LoopID, StringRef Name)
Find and return the loop attribute node for the attribute Name in LoopID.
Value * createTargetReduction(IRBuilderBase &B, const RecurrenceDescriptor &Desc, Value *Src, PHINode *OrigPhi=nullptr)
Create a generic target reduction using a recurrence descriptor Desc The target is queried to determi...
Loop * cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, LoopInfo *LI, LPPassManager *LPM)
Recursively clone the specified loop and all of its children, mapping the blocks with the specified m...
Value * createAnyOfTargetReduction(IRBuilderBase &B, Value *Src, const RecurrenceDescriptor &Desc, PHINode *OrigPhi)
Create a target reduction of the given vector Src for a reduction of the kind RecurKind::IAnyOf or Re...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
IR Values for the lower and upper bounds of a pointer evolution.
TrackingVH< Value > Start
RewritePhi(PHINode *P, unsigned I, const SCEV *Val, Instruction *ExpansionPt, bool H)
const SCEV * ExpansionSCEV
Instruction * ExpansionPoint
Description of the encoding of one expression Op.
Struct to hold information about a partially invariant condition.
unsigned AddressSpace
Address space of the involved pointers.
bool NeedsFreeze
Whether the pointer needs to be frozen after expansion, e.g.
const SCEV * High
The SCEV expression which represents the upper bound of all the pointers in this group.
const SCEV * Low
The SCEV expression which represents the lower bound of all the pointers in this group.