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)
291 if (Op->getNumOperands() == 0)
293 Metadata *NameMD = Op->getOperand(0).get();
294 if (!isa<MDString>(NameMD))
296 StringRef AttrName = cast<MDString>(NameMD)->getString();
299 return !AttrName.
startswith(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!");
544 Builder.CreateCondBr(
Builder.getFalse(), L->getHeader(), ExitBlock);
550 for (
PHINode &
P : ExitBlock->phis()) {
555 P.setIncomingBlock(PredIndex, Preheader);
563 for (
unsigned i = 0, e =
P.getNumIncomingValues() - 1; i != e; ++i)
564 P.removeIncomingValue(e - i,
false);
566 assert((
P.getNumIncomingValues() == 1 &&
567 P.getIncomingBlock(PredIndex) == Preheader) &&
568 "Should have exactly one value and that's from the preheader!");
572 DTU.
applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}});
574 MSSAU->applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}},
582 Builder.SetInsertPoint(Preheader->getTerminator());
585 Preheader->getTerminator()->eraseFromParent();
587 assert(L->hasNoExitBlocks() &&
588 "Loop should have either zero or one exit blocks.");
590 Builder.SetInsertPoint(OldTerm);
592 Preheader->getTerminator()->eraseFromParent();
596 DTU.
applyUpdates({{DominatorTree::Delete, Preheader, L->getHeader()}});
598 MSSAU->applyUpdates({{DominatorTree::Delete, Preheader, L->getHeader()}},
602 MSSAU->removeBlocks(DeadBlockSet);
621 for (
auto *Block : L->blocks())
625 if (
auto *Usr = dyn_cast<Instruction>(U.getUser()))
626 if (L->contains(Usr->getParent()))
632 "Unexpected user in reachable block");
635 auto *DVI = dyn_cast<DbgVariableIntrinsic>(&
I);
648 Instruction *InsertDbgValueBefore = ExitBlock->getFirstNonPHI();
649 assert(InsertDbgValueBefore &&
650 "There should be a non-PHI instruction in exit block, else these "
651 "instructions will have no parent.");
652 for (
auto *DVI : DeadDebugInst) {
653 DVI->setKillLocation();
654 DVI->moveBefore(InsertDbgValueBefore);
660 for (
auto *Block : L->blocks())
661 Block->dropAllReferences();
672 BB->eraseFromParent();
678 blocks.
insert(L->block_begin(), L->block_end());
686 if (
Loop *ParentLoop = L->getParentLoop()) {
688 assert(
I != ParentLoop->end() &&
"Couldn't find loop");
689 ParentLoop->removeChildLoop(
I);
692 assert(
I != LI->
end() &&
"Couldn't find loop");
701 auto *Latch = L->getLoopLatch();
702 assert(Latch &&
"multiple latches not yet supported");
703 auto *Header = L->getHeader();
704 Loop *OutermostLoop = L->getOutermostLoop();
709 std::unique_ptr<MemorySSAUpdater> MSSAU;
711 MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
716 if (
auto *BI = dyn_cast<BranchInst>(Latch->getTerminator())) {
717 if (!BI->isConditional()) {
726 if (L->isLoopExiting(Latch)) {
731 const unsigned ExitIdx = L->contains(BI->getSuccessor(0)) ? 1 : 0;
732 BasicBlock *ExitBB = BI->getSuccessor(ExitIdx);
735 Header->removePredecessor(Latch,
true);
738 auto *NewBI =
Builder.CreateBr(ExitBB);
741 NewBI->copyMetadata(*BI, {LLVMContext::MD_dbg,
742 LLVMContext::MD_annotation});
744 BI->eraseFromParent();
745 DTU.
applyUpdates({{DominatorTree::Delete, Latch, Header}});
747 MSSAU->applyUpdates({{DominatorTree::Delete, Latch, Header}}, DT);
755 auto *BackedgeBB =
SplitEdge(Latch, Header, &DT, &LI, MSSAU.get());
759 true, &DTU, MSSAU.get());
771 if (OutermostLoop != L)
785 if (!LatchBR || LatchBR->
getNumSuccessors() != 2 || !L->isLoopExiting(Latch))
790 "At least one edge out of the latch must go to the header");
814 OrigExitWeight = ExitWeight;
820 return ExitCount + 1;
823std::optional<unsigned>
825 unsigned *EstimatedLoopInvocationWeight) {
832 if (std::optional<uint64_t> EstTripCount =
834 if (EstimatedLoopInvocationWeight)
835 *EstimatedLoopInvocationWeight = ExitWeight;
836 return *EstTripCount;
843 unsigned EstimatedloopInvocationWeight) {
852 unsigned LatchExitWeight = 0;
853 unsigned BackedgeTakenWeight = 0;
855 if (EstimatedTripCount > 0) {
856 LatchExitWeight = EstimatedloopInvocationWeight;
857 BackedgeTakenWeight = (EstimatedTripCount - 1) * LatchExitWeight;
862 std::swap(BackedgeTakenWeight, LatchExitWeight);
868 LLVMContext::MD_prof,
882 const SCEV *InnerLoopBECountSC = SE.
getExitCount(InnerLoop, InnerLoopLatch);
883 if (isa<SCEVCouldNotCompute>(InnerLoopBECountSC) ||
900 case RecurKind::UMin:
901 return Intrinsic::umin;
902 case RecurKind::UMax:
903 return Intrinsic::umax;
904 case RecurKind::SMin:
905 return Intrinsic::smin;
906 case RecurKind::SMax:
907 return Intrinsic::smax;
908 case RecurKind::FMin:
909 return Intrinsic::minnum;
910 case RecurKind::FMax:
911 return Intrinsic::maxnum;
919 case RecurKind::UMin:
921 case RecurKind::UMax:
923 case RecurKind::SMin:
925 case RecurKind::SMax:
927 case RecurKind::FMin:
929 case RecurKind::FMax:
936 if (
auto VTy = dyn_cast<VectorType>(
Left->getType()))
937 StartVal =
Builder.CreateVectorSplat(VTy->getElementCount(), StartVal);
961 unsigned VF = cast<FixedVectorType>(Src->getType())->getNumElements();
966 for (
unsigned ExtractIdx = 0; ExtractIdx != VF; ++ExtractIdx) {
970 if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
986 unsigned VF = cast<FixedVectorType>(Src->getType())->getNumElements();
991 "Reduction emission only supported for pow2 vectors!");
1001 for (
unsigned i = VF; i != 1; i >>= 1) {
1003 for (
unsigned j = 0; j != i / 2; ++j)
1004 ShuffleMask[j] = i / 2 + j;
1007 std::fill(&ShuffleMask[i / 2], ShuffleMask.
end(), -1);
1009 Value *Shuf =
Builder.CreateShuffleVector(TmpVec, ShuffleMask,
"rdx.shuf");
1011 if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
1021 return Builder.CreateExtractElement(TmpVec,
Builder.getInt32(0));
1031 "Unexpected reduction kind");
1033 Value *NewVal =
nullptr;
1038 for (
auto *U : OrigPhi->
users()) {
1039 if ((
SI = dyn_cast<SelectInst>(U)))
1042 assert(
SI &&
"One user of the original phi should be a select");
1044 if (
SI->getTrueValue() == OrigPhi)
1045 NewVal =
SI->getFalseValue();
1047 assert(
SI->getFalseValue() == OrigPhi &&
1048 "At least one input to the select should be the original Phi");
1049 NewVal =
SI->getTrueValue();
1054 ElementCount EC = cast<VectorType>(Src->getType())->getElementCount();
1060 Cmp =
Builder.CreateOrReduce(Cmp);
1061 return Builder.CreateSelect(Cmp, NewVal, InitVal,
"rdx.select");
1067 auto *SrcVecEltTy = cast<VectorType>(Src->getType())->getElementType();
1069 case RecurKind::Add:
1070 return Builder.CreateAddReduce(Src);
1071 case RecurKind::Mul:
1072 return Builder.CreateMulReduce(Src);
1073 case RecurKind::And:
1074 return Builder.CreateAndReduce(Src);
1076 return Builder.CreateOrReduce(Src);
1077 case RecurKind::Xor:
1078 return Builder.CreateXorReduce(Src);
1079 case RecurKind::FMulAdd:
1080 case RecurKind::FAdd:
1083 case RecurKind::FMul:
1085 case RecurKind::SMax:
1086 return Builder.CreateIntMaxReduce(Src,
true);
1087 case RecurKind::SMin:
1088 return Builder.CreateIntMinReduce(Src,
true);
1089 case RecurKind::UMax:
1090 return Builder.CreateIntMaxReduce(Src,
false);
1091 case RecurKind::UMin:
1092 return Builder.CreateIntMinReduce(Src,
false);
1093 case RecurKind::FMax:
1094 return Builder.CreateFPMaxReduce(Src);
1095 case RecurKind::FMin:
1096 return Builder.CreateFPMinReduce(Src);
1124 "Unexpected reduction kind");
1125 assert(Src->getType()->isVectorTy() &&
"Expected a vector type");
1126 assert(!Start->getType()->isVectorTy() &&
"Expected a scalar type");
1128 return B.CreateFAddReduce(Start, Src);
1132 bool IncludeWrapFlags) {
1133 auto *VecOp = dyn_cast<Instruction>(
I);
1136 auto *Intersection = (OpValue ==
nullptr) ? dyn_cast<Instruction>(VL[0])
1137 : dyn_cast<Instruction>(OpValue);
1140 const unsigned Opcode = Intersection->getOpcode();
1141 VecOp->copyIRFlags(Intersection, IncludeWrapFlags);
1142 for (
auto *V : VL) {
1143 auto *Instr = dyn_cast<Instruction>(V);
1146 if (OpValue ==
nullptr || Opcode == Instr->getOpcode())
1147 VecOp->andIRFlags(V);
1184 auto Predicate =
Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
1195 auto Predicate =
Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
1211 while (!WorkList.
empty()) {
1214 if (!L->contains(Curr))
1220 for (
const auto *U : Curr->
users()) {
1221 auto *UI = cast<Instruction>(U);
1222 if (Visited.
insert(UI).second)
1248 BasicBlock *Preheader = L->getLoopPreheader();
1258 L->getExitingBlocks(ExitingBlocks);
1260 L->getUniqueExitBlocks(ExitBlocks);
1261 if (ExitBlocks.
size() != 1 || ExitingBlocks.
size() != 1)
1266 while (
PHINode *
P = dyn_cast<PHINode>(BI)) {
1267 Value *Incoming =
P->getIncomingValueForBlock(ExitingBlocks[0]);
1273 for (
const RewritePhi &Phi : RewritePhiSet) {
1274 unsigned i = Phi.Ith;
1275 if (Phi.PN ==
P && (Phi.PN)->getIncomingValue(i) == Incoming) {
1282 if (!found && (
I = dyn_cast<Instruction>(Incoming)))
1283 if (!L->hasLoopInvariantOperands(
I))
1289 for (
auto *BB : L->blocks())
1291 return I.mayHaveSideEffects();
1305 if (!L->getLoopPreheader())
1319 assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
1320 "Indvars did not preserve LCSSA!");
1323 L->getUniqueExitBlocks(ExitBlocks);
1332 PHINode *PN = dyn_cast<PHINode>(ExitBB->begin());
1339 while ((PN = dyn_cast<PHINode>(BBI++))) {
1347 for (
unsigned i = 0; i != NumPreds; ++i) {
1351 if (!isa<Instruction>(InVal))
1360 if (!L->contains(Inst))
1370 PHINode *IndPhi = dyn_cast<PHINode>(Inst);
1377 if (!isa<PHINode>(U) && !isa<BinaryOperator>(U))
1379 BinaryOperator *B = dyn_cast<BinaryOperator>(U);
1380 if (B && B != ID.getInductionBinOp())
1392 PHINode *Phi = dyn_cast<PHINode>(U);
1393 if (Phi != PN && !checkIsIndPhi(Phi, L, SE, ID))
1398 if (
B !=
ID.getInductionBinOp())
1410 if (isa<SCEVCouldNotCompute>(ExitValue) ||
1412 !
Rewriter.isSafeToExpand(ExitValue)) {
1418 if (isa<SCEVCouldNotCompute>(ExitCount))
1420 if (
auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE->
getSCEV(Inst)))
1421 if (AddRec->getLoop() == L)
1422 ExitValue = AddRec->evaluateAtIteration(ExitCount, *SE);
1423 if (isa<SCEVCouldNotCompute>(ExitValue) ||
1425 !
Rewriter.isSafeToExpand(ExitValue))
1439 bool HighCost =
Rewriter.isHighCostExpansion(
1450 (isa<PHINode>(Inst) || isa<LandingPadInst>(Inst)) ?
1452 RewritePhiSet.
emplace_back(PN, i, ExitValue, InsertPt, HighCost);
1463 int NumReplaced = 0;
1466 for (
const RewritePhi &Phi : RewritePhiSet) {
1473 !LoopCanBeDel && Phi.HighCost)
1477 Phi.ExpansionSCEV, Phi.PN->getType(), Phi.ExpansionPoint);
1479 LLVM_DEBUG(
dbgs() <<
"rewriteLoopExitValues: AfterLoopVal = " << *ExitVal
1481 <<
" LoopVal = " << *(Phi.ExpansionPoint) <<
"\n");
1487 if (
auto *ExitInsn = dyn_cast<Instruction>(ExitVal))
1488 if (
auto *EVL = LI->
getLoopFor(ExitInsn->getParent()))
1490 assert(EVL->contains(L) &&
"LCSSA breach detected!");
1526 assert(UF > 0 &&
"Zero unrolled factor is not supported");
1527 assert(UnrolledLoop != RemainderLoop &&
1528 "Unrolled and Remainder loops are expected to distinct");
1531 unsigned OrigLoopInvocationWeight = 0;
1532 std::optional<unsigned> OrigAverageTripCount =
1534 if (!OrigAverageTripCount)
1538 unsigned UnrolledAverageTripCount = *OrigAverageTripCount / UF;
1540 unsigned RemainderAverageTripCount = *OrigAverageTripCount % UF;
1543 OrigLoopInvocationWeight);
1545 OrigLoopInvocationWeight);
1551template <
typename RangeT>
1561 assert(PreOrderLoops.
empty() &&
"Must start with an empty preorder walk.");
1563 "Must start with an empty preorder walk worklist.");
1567 PreOrderWorklist.
append(L->begin(), L->end());
1569 }
while (!PreOrderWorklist.
empty());
1571 Worklist.
insert(std::move(PreOrderLoops));
1572 PreOrderLoops.
clear();
1576template <
typename RangeT>
1582template void llvm::appendLoopsToWorklist<ArrayRef<Loop *> &>(
1586llvm::appendLoopsToWorklist<Loop &>(
Loop &L,
1598 PL->addChildLoop(&New);
1608 New.addBasicBlockToLoop(cast<BasicBlock>(VM[BB]), *LI);
1634 Value *Start =
nullptr, *
End =
nullptr;
1636 Start = Exp.expandCodeFor(CG->
Low, PtrArithTy, Loc);
1637 End = Exp.expandCodeFor(CG->
High, PtrArithTy, Loc);
1640 Start =
Builder.CreateFreeze(Start, Start->getName() +
".fr");
1644 return {Start,
End};
1656 transform(PointerChecks, std::back_inserter(ChecksWithBounds),
1660 return std::make_pair(First, Second);
1663 return ChecksWithBounds;
1672 auto ExpandedChecks =
expandBounds(PointerChecks, TheLoop, Loc, Exp);
1679 Value *MemoryRuntimeCheck =
nullptr;
1681 for (
const auto &
Check : ExpandedChecks) {
1685 unsigned AS0 =
A.Start->getType()->getPointerAddressSpace();
1686 unsigned AS1 =
B.Start->getType()->getPointerAddressSpace();
1688 assert((AS0 ==
B.End->getType()->getPointerAddressSpace()) &&
1689 (AS1 ==
A.End->getType()->getPointerAddressSpace()) &&
1690 "Trying to bounds check pointers with different address spaces");
1710 Value *IsConflict = ChkBuilder.
CreateAnd(Cmp0, Cmp1,
"found.conflict");
1711 if (MemoryRuntimeCheck) {
1713 ChkBuilder.
CreateOr(MemoryRuntimeCheck, IsConflict,
"conflict.rdx");
1715 MemoryRuntimeCheck = IsConflict;
1718 return MemoryRuntimeCheck;
1730 Value *MemoryRuntimeCheck =
nullptr;
1732 for (
const auto &
C : Checks) {
1733 Type *Ty =
C.SinkStart->getType();
1735 auto *VFTimesUFTimesSize =
1740 if (
C.NeedsFreeze) {
1742 Sink =
Builder.CreateFreeze(Sink, Sink->getName() +
".fr");
1743 Src =
Builder.CreateFreeze(Src, Src->getName() +
".fr");
1747 ChkBuilder.
CreateICmpULT(Diff, VFTimesUFTimesSize,
"diff.check");
1749 if (MemoryRuntimeCheck) {
1751 ChkBuilder.
CreateOr(MemoryRuntimeCheck, IsConflict,
"conflict.rdx");
1753 MemoryRuntimeCheck = IsConflict;
1756 return MemoryRuntimeCheck;
1759std::optional<IVConditionInfo>
1762 auto *TI = dyn_cast<BranchInst>(L.getHeader()->getTerminator());
1763 if (!TI || !TI->isConditional())
1766 auto *CondI = dyn_cast<CmpInst>(TI->getCondition());
1769 if (!CondI || !L.contains(CondI))
1776 WorkList.
append(CondI->op_begin(), CondI->op_end());
1780 while (!WorkList.
empty()) {
1782 if (!
I || !L.contains(
I))
1786 if (!isa<LoadInst>(
I) && !isa<GetElementPtrInst>(
I))
1790 if (
auto *LI = dyn_cast<LoadInst>(
I))
1791 if (LI->isVolatile() || LI->isAtomic())
1796 if (
auto *MemUse = dyn_cast_or_null<MemoryUse>(MA)) {
1798 AccessesToCheck.
push_back(MemUse->getDefiningAccess());
1806 WorkList.
append(
I->op_begin(),
I->op_end());
1809 if (InstToDuplicate.
empty())
1813 L.getExitingBlocks(ExitingBlocks);
1814 auto HasNoClobbersOnPath =
1815 [&L, &AA, &AccessedLocs, &ExitingBlocks, &InstToDuplicate,
1818 -> std::optional<IVConditionInfo> {
1830 while (!WorkList.
empty()) {
1832 if (!L.contains(Current))
1834 const auto &SeenIns = Seen.
insert(Current);
1835 if (!SeenIns.second)
1839 *Current, [](
Instruction &
I) {
return !
I.mayHaveSideEffects(); });
1845 if (Seen.
size() < 2)
1853 while (!AccessesToCheck.
empty()) {
1855 auto SeenI = SeenAccesses.
insert(Current);
1864 if (isa<MemoryUse>(Current))
1869 if (
auto *CurrentDef = dyn_cast<MemoryDef>(Current)) {
1877 for (
Use &U : Current->
uses())
1878 AccessesToCheck.
push_back(cast<MemoryAccess>(U.getUser()));
1888 if (
Info.PathIsNoop) {
1889 for (
auto *Exiting : ExitingBlocks) {
1893 if (L.contains(Succ))
1896 Info.PathIsNoop &= Succ->phis().empty() &&
1897 (!
Info.ExitForPath ||
Info.ExitForPath == Succ);
1898 if (!
Info.PathIsNoop)
1901 "cannot have multiple exit blocks");
1902 Info.ExitForPath = Succ;
1906 if (!
Info.ExitForPath)
1907 Info.PathIsNoop =
false;
1909 Info.InstToDuplicate = InstToDuplicate;
1915 if (TI->getSuccessor(0) == TI->getSuccessor(1))
1918 if (
auto Info = HasNoClobbersOnPath(TI->getSuccessor(0), L.getHeader(),
1923 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.
SmallVector< MachineOperand, 4 > Cond
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
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 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 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...
static PointerBounds expandBounds(const RuntimeCheckingPtrGroup *CG, Loop *TheLoop, Instruction *Loc, SCEVExpander &Exp)
Expand code for the lower and upper bound of the pointer group CG in TheLoop.
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.
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
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 ...
Identifies a unique instance of a variable.
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.
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
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
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.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
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.
FastMathFlags getFastMathFlags() const
TrackingVH< Value > getRecurrenceStartValue() const
RecurKind getRecurrenceKind() const
static bool isMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is any min/max kind.
static bool isSelectCmpRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...
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.
Value * expandCodeFor(const SCEV *SH, Type *Ty, Instruction *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 startswith(StringRef Prefix) const
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 PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
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()
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....
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)
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 * createSelectCmpOp(IRBuilderBase &Builder, Value *StartVal, RecurKind RK, Value *Left, Value *Right)
See RecurrenceDescriptor::isSelectCmpPattern for a description of the pattern we are trying to match.
std::optional< bool > getOptionalBoolLoopAttribute(const Loop *TheLoop, StringRef Name)
Value * createSimpleTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI, Value *Src, RecurKind RdxKind)
Create a target reduction of the given vector.
void appendReversedLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
auto successors(const MachineBasicBlock *BB)
Value * createTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI, const RecurrenceDescriptor &Desc, Value *Src, PHINode *OrigPhi=nullptr)
Create a generic target reduction using a recurrence descriptor Desc The target is queried to determi...
void initializeLoopPassPass(PassRegistry &)
Manually defined generic "LoopPass" dependency initialization.
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...
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI)
Put a loop nest into LCSSA form.
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...
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.
Value * addRuntimeChecks(Instruction *Loc, Loop *TheLoop, const SmallVectorImpl< RuntimePointerCheck > &PointerChecks, SCEVExpander &Expander)
Add code that checks at runtime if the accessed arrays in PointerChecks overlap.
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...
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.
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.
Value * createSelectCmpTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI, Value *Src, const RecurrenceDescriptor &Desc, PHINode *OrigPhi)
Create a target reduction of the given vector Src for a reduction of the kind RecurKind::SelectICmp o...
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.
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...
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
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.