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);
471 assert(LatchIdx != -1 &&
"LatchBlock is not a case in this PHINode");
475 if (U !=
Cond && U != IncV)
return false;
478 if (U !=
Cond && U != PN)
return false;
485 assert((!DT || L->isLCSSAForm(*DT)) &&
"Expected LCSSA!");
486 auto *Preheader = L->getLoopPreheader();
487 assert(Preheader &&
"Preheader should exist!");
489 std::unique_ptr<MemorySSAUpdater> MSSAU;
491 MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
509 "Preheader must end with a side-effect-free terminator");
511 "Preheader must have a single successor");
539 auto *ExitBlock = L->getUniqueExitBlock();
542 assert(ExitBlock &&
"Should have a unique exit block!");
543 assert(L->hasDedicatedExits() &&
"Loop should have dedicated exits!");
551 for (
PHINode &
P : ExitBlock->phis()) {
556 P.setIncomingBlock(PredIndex, Preheader);
560 P.removeIncomingValueIf([](
unsigned Idx) {
return Idx != 0; },
563 assert((
P.getNumIncomingValues() == 1 &&
564 P.getIncomingBlock(PredIndex) == Preheader) &&
565 "Should have exactly one value and that's from the preheader!");
569 DTU.
applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}});
571 MSSAU->applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}},
584 assert(L->hasNoExitBlocks() &&
585 "Loop should have either zero or one exit blocks.");
593 DTU.
applyUpdates({{DominatorTree::Delete, Preheader, L->getHeader()}});
595 MSSAU->applyUpdates({{DominatorTree::Delete, Preheader, L->getHeader()}},
599 MSSAU->removeBlocks(DeadBlockSet);
619 for (
auto *
Block : L->blocks())
623 if (
auto *Usr = dyn_cast<Instruction>(U.getUser()))
624 if (L->contains(Usr->getParent()))
630 "Unexpected user in reachable block");
635 if (
Block->IsNewDbgInfoFormat) {
639 DVR.getDebugLoc().get());
640 if (!DeadDebugSet.
insert(Key).second)
643 DVR.removeFromParent();
651 auto *DVI = dyn_cast<DbgVariableIntrinsic>(&
I);
667 ExitBlock->getFirstInsertionPt();
668 assert(InsertDbgValueBefore != ExitBlock->end() &&
669 "There should be a non-PHI instruction in exit block, else these "
670 "instructions will have no parent.");
672 for (
auto *DVI : DeadDebugInst)
673 DVI->moveBefore(*ExitBlock, InsertDbgValueBefore);
680 ExitBlock->insertDbgRecordBefore(DVR, InsertDbgValueBefore);
685 for (
auto *
Block : L->blocks())
686 Block->dropAllReferences();
697 BB->eraseFromParent();
703 blocks.insert(L->block_begin(), L->block_end());
711 if (
Loop *ParentLoop = L->getParentLoop()) {
713 assert(
I != ParentLoop->end() &&
"Couldn't find loop");
714 ParentLoop->removeChildLoop(
I);
717 assert(
I != LI->
end() &&
"Couldn't find loop");
726 auto *Latch = L->getLoopLatch();
727 assert(Latch &&
"multiple latches not yet supported");
728 auto *Header = L->getHeader();
729 Loop *OutermostLoop = L->getOutermostLoop();
734 std::unique_ptr<MemorySSAUpdater> MSSAU;
736 MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
741 if (
auto *BI = dyn_cast<BranchInst>(Latch->getTerminator())) {
742 if (!BI->isConditional()) {
751 if (L->isLoopExiting(Latch)) {
756 const unsigned ExitIdx = L->contains(BI->getSuccessor(0)) ? 1 : 0;
757 BasicBlock *ExitBB = BI->getSuccessor(ExitIdx);
760 Header->removePredecessor(Latch,
true);
763 auto *NewBI = Builder.
CreateBr(ExitBB);
767 LLVMContext::MD_annotation});
769 BI->eraseFromParent();
770 DTU.
applyUpdates({{DominatorTree::Delete, Latch, Header}});
772 MSSAU->applyUpdates({{DominatorTree::Delete, Latch, Header}}, DT);
780 auto *BackedgeBB =
SplitEdge(Latch, Header, &DT, &LI, MSSAU.get());
784 true, &DTU, MSSAU.get());
796 if (OutermostLoop != L)
810 if (!LatchBR || LatchBR->
getNumSuccessors() != 2 || !L->isLoopExiting(Latch))
815 "At least one edge out of the latch must go to the header");
839 OrigExitWeight = ExitWeight;
845 return ExitCount + 1;
848std::optional<unsigned>
850 unsigned *EstimatedLoopInvocationWeight) {
857 if (std::optional<uint64_t> EstTripCount =
859 if (EstimatedLoopInvocationWeight)
860 *EstimatedLoopInvocationWeight = ExitWeight;
861 return *EstTripCount;
868 unsigned EstimatedloopInvocationWeight) {
877 unsigned LatchExitWeight = 0;
878 unsigned BackedgeTakenWeight = 0;
880 if (EstimatedTripCount > 0) {
881 LatchExitWeight = EstimatedloopInvocationWeight;
882 BackedgeTakenWeight = (EstimatedTripCount - 1) * LatchExitWeight;
887 std::swap(BackedgeTakenWeight, LatchExitWeight);
893 LLVMContext::MD_prof,
907 const SCEV *InnerLoopBECountSC = SE.
getExitCount(InnerLoop, InnerLoopLatch);
908 if (isa<SCEVCouldNotCompute>(InnerLoopBECountSC) ||
923 case Intrinsic::vector_reduce_fadd:
924 return Instruction::FAdd;
925 case Intrinsic::vector_reduce_fmul:
926 return Instruction::FMul;
927 case Intrinsic::vector_reduce_add:
928 return Instruction::Add;
929 case Intrinsic::vector_reduce_mul:
930 return Instruction::Mul;
931 case Intrinsic::vector_reduce_and:
932 return Instruction::And;
933 case Intrinsic::vector_reduce_or:
934 return Instruction::Or;
935 case Intrinsic::vector_reduce_xor:
936 return Instruction::Xor;
937 case Intrinsic::vector_reduce_smax:
938 case Intrinsic::vector_reduce_smin:
939 case Intrinsic::vector_reduce_umax:
940 case Intrinsic::vector_reduce_umin:
941 return Instruction::ICmp;
942 case Intrinsic::vector_reduce_fmax:
943 case Intrinsic::vector_reduce_fmin:
944 return Instruction::FCmp;
954 case Intrinsic::vector_reduce_umin:
955 return Intrinsic::umin;
956 case Intrinsic::vector_reduce_umax:
957 return Intrinsic::umax;
958 case Intrinsic::vector_reduce_smin:
959 return Intrinsic::smin;
960 case Intrinsic::vector_reduce_smax:
961 return Intrinsic::smax;
962 case Intrinsic::vector_reduce_fmin:
963 return Intrinsic::minnum;
964 case Intrinsic::vector_reduce_fmax:
965 return Intrinsic::maxnum;
966 case Intrinsic::vector_reduce_fminimum:
967 return Intrinsic::minimum;
968 case Intrinsic::vector_reduce_fmaximum:
969 return Intrinsic::maximum;
977 case RecurKind::UMin:
978 return Intrinsic::umin;
979 case RecurKind::UMax:
980 return Intrinsic::umax;
981 case RecurKind::SMin:
982 return Intrinsic::smin;
983 case RecurKind::SMax:
984 return Intrinsic::smax;
985 case RecurKind::FMin:
986 return Intrinsic::minnum;
987 case RecurKind::FMax:
988 return Intrinsic::maxnum;
989 case RecurKind::FMinimum:
990 return Intrinsic::minimum;
991 case RecurKind::FMaximum:
992 return Intrinsic::maximum;
998 case Intrinsic::vector_reduce_smax:
999 return RecurKind::SMax;
1000 case Intrinsic::vector_reduce_smin:
1001 return RecurKind::SMin;
1002 case Intrinsic::vector_reduce_umax:
1003 return RecurKind::UMax;
1004 case Intrinsic::vector_reduce_umin:
1005 return RecurKind::UMin;
1006 case Intrinsic::vector_reduce_fmax:
1007 return RecurKind::FMax;
1008 case Intrinsic::vector_reduce_fmin:
1009 return RecurKind::FMin;
1011 return RecurKind::None;
1019 case RecurKind::UMin:
1021 case RecurKind::UMax:
1023 case RecurKind::SMin:
1025 case RecurKind::SMax:
1027 case RecurKind::FMin:
1029 case RecurKind::FMax:
1041 (RK == RecurKind::FMinimum || RK == RecurKind::FMaximum)) {
1056 unsigned VF = cast<FixedVectorType>(Src->getType())->getNumElements();
1060 Value *Result = Acc;
1061 for (
unsigned ExtractIdx = 0; ExtractIdx != VF; ++ExtractIdx) {
1065 if (
Op != Instruction::ICmp &&
Op != Instruction::FCmp) {
1083 unsigned VF = cast<FixedVectorType>(Src->getType())->getNumElements();
1088 "Reduction emission only supported for pow2 vectors!");
1096 auto BuildShuffledOp = [&Builder, &
Op,
1098 Value *&TmpVec) ->
void {
1100 if (
Op != Instruction::ICmp &&
Op != Instruction::FCmp) {
1110 Value *TmpVec = Src;
1111 if (TargetTransformInfo::ReductionShuffle::Pairwise == RS) {
1113 for (
unsigned stride = 1; stride < VF; stride <<= 1) {
1115 std::fill(ShuffleMask.
begin(), ShuffleMask.
end(), -1);
1116 for (
unsigned j = 0; j < VF; j += stride << 1) {
1117 ShuffleMask[j] = j + stride;
1119 BuildShuffledOp(ShuffleMask, TmpVec);
1123 for (
unsigned i = VF; i != 1; i >>= 1) {
1125 for (
unsigned j = 0; j != i / 2; ++j)
1126 ShuffleMask[j] = i / 2 + j;
1129 std::fill(&ShuffleMask[i / 2], ShuffleMask.
end(), -1);
1130 BuildShuffledOp(ShuffleMask, TmpVec);
1142 "Unexpected reduction kind");
1143 Value *InitVal =
Desc.getRecurrenceStartValue();
1144 Value *NewVal =
nullptr;
1149 for (
auto *U : OrigPhi->
users()) {
1150 if ((SI = dyn_cast<SelectInst>(U)))
1153 assert(SI &&
"One user of the original phi should be a select");
1155 if (SI->getTrueValue() == OrigPhi)
1156 NewVal = SI->getFalseValue();
1158 assert(SI->getFalseValue() == OrigPhi &&
1159 "At least one input to the select should be the original Phi");
1160 NewVal = SI->getTrueValue();
1165 Src->getType()->isVectorTy() ? Builder.
CreateOrReduce(Src) : Src;
1169 return Builder.
CreateSelect(AnyOf, NewVal, InitVal,
"rdx.select");
1174 auto *SrcVecEltTy = cast<VectorType>(Src->getType())->getElementType();
1176 case RecurKind::Add:
1178 case RecurKind::Mul:
1180 case RecurKind::And:
1184 case RecurKind::Xor:
1186 case RecurKind::FMulAdd:
1187 case RecurKind::FAdd:
1190 case RecurKind::FMul:
1192 case RecurKind::SMax:
1194 case RecurKind::SMin:
1196 case RecurKind::UMax:
1198 case RecurKind::UMin:
1200 case RecurKind::FMax:
1202 case RecurKind::FMin:
1204 case RecurKind::FMinimum:
1206 case RecurKind::FMaximum:
1217 "AnyOf reduction is not supported.");
1218 auto *SrcTy = cast<VectorType>(Src->getType());
1219 Type *SrcEltTy = SrcTy->getElementType();
1221 Desc.getRecurrenceIdentity(Kind, SrcEltTy,
Desc.getFastMathFlags());
1222 Value *Ops[] = {Iden, Src};
1233 B.setFastMathFlags(
Desc.getFastMathFlags());
1245 assert((
Desc.getRecurrenceKind() == RecurKind::FAdd ||
1246 Desc.getRecurrenceKind() == RecurKind::FMulAdd) &&
1247 "Unexpected reduction kind");
1248 assert(Src->getType()->isVectorTy() &&
"Expected a vector type");
1249 assert(!Start->getType()->isVectorTy() &&
"Expected a scalar type");
1251 return B.CreateFAddReduce(Start, Src);
1257 assert((
Desc.getRecurrenceKind() == RecurKind::FAdd ||
1258 Desc.getRecurrenceKind() == RecurKind::FMulAdd) &&
1259 "Unexpected reduction kind");
1260 assert(Src->getType()->isVectorTy() &&
"Expected a vector type");
1261 assert(!Start->getType()->isVectorTy() &&
"Expected a scalar type");
1263 auto *SrcTy = cast<VectorType>(Src->getType());
1264 Value *Ops[] = {Start, Src};
1269 bool IncludeWrapFlags) {
1270 auto *VecOp = dyn_cast<Instruction>(
I);
1273 auto *Intersection = (OpValue ==
nullptr) ? dyn_cast<Instruction>(VL[0])
1274 : dyn_cast<Instruction>(OpValue);
1277 const unsigned Opcode = Intersection->getOpcode();
1278 VecOp->copyIRFlags(Intersection, IncludeWrapFlags);
1279 for (
auto *V : VL) {
1280 auto *Instr = dyn_cast<Instruction>(V);
1283 if (OpValue ==
nullptr || Opcode == Instr->getOpcode())
1284 VecOp->andIRFlags(V);
1321 auto Predicate =
Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
1332 auto Predicate =
Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
1348 while (!WorkList.
empty()) {
1351 if (!L->contains(Curr))
1357 for (
const auto *U : Curr->
users()) {
1358 auto *UI = cast<Instruction>(U);
1359 if (Visited.
insert(UI).second)
1385 BasicBlock *Preheader = L->getLoopPreheader();
1395 L->getExitingBlocks(ExitingBlocks);
1397 L->getUniqueExitBlocks(ExitBlocks);
1398 if (ExitBlocks.
size() != 1 || ExitingBlocks.
size() != 1)
1403 while (
PHINode *
P = dyn_cast<PHINode>(BI)) {
1410 for (
const RewritePhi &Phi : RewritePhiSet) {
1411 unsigned i = Phi.Ith;
1412 if (Phi.PN ==
P && (Phi.PN)->getIncomingValue(i) ==
Incoming) {
1419 if (!found && (
I = dyn_cast<Instruction>(
Incoming)))
1420 if (!L->hasLoopInvariantOperands(
I))
1426 for (
auto *BB : L->blocks())
1428 return I.mayHaveSideEffects();
1442 if (!L->getLoopPreheader())
1444 if (Phi->getParent() != L->getHeader())
1456 assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
1457 "Indvars did not preserve LCSSA!");
1460 L->getUniqueExitBlocks(ExitBlocks);
1469 PHINode *PN = dyn_cast<PHINode>(ExitBB->begin());
1476 while ((PN = dyn_cast<PHINode>(BBI++))) {
1484 for (
unsigned i = 0; i != NumPreds; ++i) {
1488 if (!isa<Instruction>(InVal))
1497 if (!L->contains(Inst))
1507 PHINode *IndPhi = dyn_cast<PHINode>(Inst);
1514 if (!isa<PHINode>(U) && !isa<BinaryOperator>(U))
1516 BinaryOperator *B = dyn_cast<BinaryOperator>(U);
1517 if (B && B != ID.getInductionBinOp())
1529 PHINode *Phi = dyn_cast<PHINode>(U);
1530 if (Phi != PN && !checkIsIndPhi(Phi, L, SE, ID))
1535 if (
B !=
ID.getInductionBinOp())
1547 if (isa<SCEVCouldNotCompute>(ExitValue) ||
1549 !
Rewriter.isSafeToExpand(ExitValue)) {
1555 if (isa<SCEVCouldNotCompute>(ExitCount))
1557 if (
auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE->
getSCEV(Inst)))
1558 if (AddRec->getLoop() == L)
1559 ExitValue = AddRec->evaluateAtIteration(ExitCount, *SE);
1560 if (isa<SCEVCouldNotCompute>(ExitValue) ||
1562 !
Rewriter.isSafeToExpand(ExitValue))
1576 bool HighCost =
Rewriter.isHighCostExpansion(
1587 (isa<PHINode>(Inst) || isa<LandingPadInst>(Inst)) ?
1588 &*Inst->
getParent()->getFirstInsertionPt() : Inst;
1589 RewritePhiSet.
emplace_back(PN, i, ExitValue, InsertPt, HighCost);
1600 int NumReplaced = 0;
1603 for (
const RewritePhi &Phi : RewritePhiSet) {
1610 !LoopCanBeDel && Phi.HighCost)
1614 Phi.ExpansionSCEV, Phi.PN->getType(), Phi.ExpansionPoint);
1616 LLVM_DEBUG(
dbgs() <<
"rewriteLoopExitValues: AfterLoopVal = " << *ExitVal
1618 <<
" LoopVal = " << *(Phi.ExpansionPoint) <<
"\n");
1624 if (
auto *ExitInsn = dyn_cast<Instruction>(ExitVal))
1625 if (
auto *EVL = LI->
getLoopFor(ExitInsn->getParent()))
1627 assert(EVL->contains(L) &&
"LCSSA breach detected!");
1663 assert(UF > 0 &&
"Zero unrolled factor is not supported");
1664 assert(UnrolledLoop != RemainderLoop &&
1665 "Unrolled and Remainder loops are expected to distinct");
1668 unsigned OrigLoopInvocationWeight = 0;
1669 std::optional<unsigned> OrigAverageTripCount =
1671 if (!OrigAverageTripCount)
1675 unsigned UnrolledAverageTripCount = *OrigAverageTripCount / UF;
1677 unsigned RemainderAverageTripCount = *OrigAverageTripCount % UF;
1680 OrigLoopInvocationWeight);
1682 OrigLoopInvocationWeight);
1688template <
typename RangeT>
1698 assert(PreOrderLoops.
empty() &&
"Must start with an empty preorder walk.");
1700 "Must start with an empty preorder walk worklist.");
1704 PreOrderWorklist.
append(L->begin(), L->end());
1706 }
while (!PreOrderWorklist.
empty());
1708 Worklist.
insert(std::move(PreOrderLoops));
1709 PreOrderLoops.
clear();
1713template <
typename RangeT>
1719template void llvm::appendLoopsToWorklist<ArrayRef<Loop *> &>(
1723llvm::appendLoopsToWorklist<Loop &>(
Loop &L,
1735 PL->addChildLoop(&New);
1745 New.addBasicBlockToLoop(cast<BasicBlock>(VM[BB]), *LI);
1772 Value *Start =
nullptr, *
End =
nullptr;
1787 isa<SCEVAddRecExpr>(
High) && isa<SCEVAddRecExpr>(
Low)) {
1788 auto *HighAR = cast<SCEVAddRecExpr>(
High);
1789 auto *LowAR = cast<SCEVAddRecExpr>(
Low);
1792 const SCEV *Recur = LowAR->getStepRecurrence(SE);
1793 if (Recur == HighAR->getStepRecurrence(SE) &&
1794 HighAR->getLoop() == OuterLoop && LowAR->getLoop() == OuterLoop) {
1797 if (!isa<SCEVCouldNotCompute>(OuterExitCount) &&
1799 const SCEV *NewHigh =
1800 cast<SCEVAddRecExpr>(
High)->evaluateAtIteration(OuterExitCount, SE);
1801 if (!isa<SCEVCouldNotCompute>(NewHigh)) {
1802 LLVM_DEBUG(
dbgs() <<
"LAA: Expanded RT check for range to include "
1803 "outer loop in order to permit hoisting\n");
1805 Low = cast<SCEVAddRecExpr>(
Low)->getStart();
1813 << *Stride <<
'\n');
1820 Start = Exp.expandCodeFor(
Low, PtrArithTy, Loc);
1821 End = Exp.expandCodeFor(
High, PtrArithTy, Loc);
1824 Start = Builder.
CreateFreeze(Start, Start->getName() +
".fr");
1828 Stride ? Exp.expandCodeFor(Stride, Stride->getType(), Loc) :
nullptr;
1830 return {Start,
End, StrideVal};
1842 transform(PointerChecks, std::back_inserter(ChecksWithBounds),
1848 return std::make_pair(
First, Second);
1851 return ChecksWithBounds;
1860 auto ExpandedChecks =
1868 Value *MemoryRuntimeCheck =
nullptr;
1870 for (
const auto &[
A,
B] : ExpandedChecks) {
1874 assert((
A.Start->getType()->getPointerAddressSpace() ==
1875 B.End->getType()->getPointerAddressSpace()) &&
1876 (
B.Start->getType()->getPointerAddressSpace() ==
1877 A.End->getType()->getPointerAddressSpace()) &&
1878 "Trying to bounds check pointers with different address spaces");
1890 Value *IsConflict = ChkBuilder.
CreateAnd(Cmp0, Cmp1,
"found.conflict");
1891 if (
A.StrideToCheck) {
1893 A.StrideToCheck, ConstantInt::get(
A.StrideToCheck->getType(), 0),
1895 IsConflict = ChkBuilder.
CreateOr(IsConflict, IsNegativeStride);
1897 if (
B.StrideToCheck) {
1899 B.StrideToCheck, ConstantInt::get(
B.StrideToCheck->getType(), 0),
1901 IsConflict = ChkBuilder.
CreateOr(IsConflict, IsNegativeStride);
1903 if (MemoryRuntimeCheck) {
1905 ChkBuilder.
CreateOr(MemoryRuntimeCheck, IsConflict,
"conflict.rdx");
1907 MemoryRuntimeCheck = IsConflict;
1910 return MemoryRuntimeCheck;
1922 Value *MemoryRuntimeCheck =
nullptr;
1924 auto &SE = *Expander.
getSE();
1928 for (
const auto &[SrcStart, SinkStart, AccessSize, NeedsFreeze] : Checks) {
1929 Type *Ty = SinkStart->getType();
1931 auto *VFTimesUFTimesSize =
1933 ConstantInt::get(Ty, IC * AccessSize));
1935 Expander.
expandCodeFor(SE.getMinusSCEV(SinkStart, SrcStart), Ty, Loc);
1939 Value *IsConflict = SeenCompares.
lookup({Diff, VFTimesUFTimesSize});
1944 ChkBuilder.
CreateICmpULT(Diff, VFTimesUFTimesSize,
"diff.check");
1945 SeenCompares.
insert({{Diff, VFTimesUFTimesSize}, IsConflict});
1949 if (MemoryRuntimeCheck) {
1951 ChkBuilder.
CreateOr(MemoryRuntimeCheck, IsConflict,
"conflict.rdx");
1953 MemoryRuntimeCheck = IsConflict;
1956 return MemoryRuntimeCheck;
1959std::optional<IVConditionInfo>
1962 auto *TI = dyn_cast<BranchInst>(L.getHeader()->getTerminator());
1963 if (!TI || !TI->isConditional())
1966 auto *CondI = dyn_cast<Instruction>(TI->getCondition());
1971 if (!CondI || !isa<CmpInst, TruncInst>(CondI) || !L.contains(CondI))
1978 WorkList.
append(CondI->op_begin(), CondI->op_end());
1982 while (!WorkList.
empty()) {
1984 if (!
I || !L.contains(
I))
1988 if (!isa<LoadInst>(
I) && !isa<GetElementPtrInst>(
I))
1992 if (
auto *LI = dyn_cast<LoadInst>(
I))
1993 if (LI->isVolatile() || LI->isAtomic())
1998 if (
auto *MemUse = dyn_cast_or_null<MemoryUse>(MA)) {
2000 AccessesToCheck.
push_back(MemUse->getDefiningAccess());
2008 WorkList.
append(
I->op_begin(),
I->op_end());
2011 if (InstToDuplicate.
empty())
2015 L.getExitingBlocks(ExitingBlocks);
2016 auto HasNoClobbersOnPath =
2017 [&L, &AA, &AccessedLocs, &ExitingBlocks, &InstToDuplicate,
2020 -> std::optional<IVConditionInfo> {
2032 while (!WorkList.
empty()) {
2034 if (!L.contains(Current))
2036 const auto &SeenIns = Seen.
insert(Current);
2037 if (!SeenIns.second)
2041 *Current, [](
Instruction &
I) {
return !
I.mayHaveSideEffects(); });
2047 if (Seen.
size() < 2)
2055 while (!AccessesToCheck.
empty()) {
2057 auto SeenI = SeenAccesses.
insert(Current);
2066 if (isa<MemoryUse>(Current))
2071 if (
auto *CurrentDef = dyn_cast<MemoryDef>(Current)) {
2079 for (
Use &U : Current->
uses())
2080 AccessesToCheck.
push_back(cast<MemoryAccess>(U.getUser()));
2090 if (
Info.PathIsNoop) {
2091 for (
auto *Exiting : ExitingBlocks) {
2095 if (L.contains(Succ))
2098 Info.PathIsNoop &= Succ->phis().empty() &&
2099 (!
Info.ExitForPath ||
Info.ExitForPath == Succ);
2100 if (!
Info.PathIsNoop)
2103 "cannot have multiple exit blocks");
2104 Info.ExitForPath = Succ;
2108 if (!
Info.ExitForPath)
2109 Info.PathIsNoop =
false;
2111 Info.InstToDuplicate = InstToDuplicate;
2117 if (TI->getSuccessor(0) == TI->getSuccessor(1))
2120 if (
auto Info = HasNoClobbersOnPath(TI->getSuccessor(0), L.getHeader(),
2125 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(true))
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
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.
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 * getNegativeZero(Type *Ty)
This is the shared class of boolean and integer constants.
static ConstantInt * getTrue(LLVMContext &Context)
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 ...
This class represents an Operation in the Expression.
uint64_t getNumOperands() const
Record of a variable value-assignment, aka a non instruction representation of the dbg....
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)
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)
void applyUpdates(ArrayRef< typename DomTreeT::UpdateType > Updates)
Submit updates to all available trees.
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.
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.
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.
const DataLayout & getDataLayout() const
Get the data layout of the module this instruction belongs to.
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, bool IsExpected=false)
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.
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.
bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
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...
const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)
Try to apply information from loop guards for L to Expr.
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.
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.
Value * createSimpleTargetReduction(RecurKind Kind, Type *ValTy, ArrayRef< Value * > VecOpArray, const Twine &Name=Twine())
Emit a VP reduction intrinsic call for recurrence kind.
std::pair< iterator, bool > insert(const ValueT &V)
An efficient, type-erasing, non-owning reference to a callable.
const ParentTy * getParent() const
#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.
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.
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.
Intrinsic::ID getMinMaxReductionIntrinsicOp(Intrinsic::ID RdxID)
Returns the min/max intrinsic used when expanding a min/max reduction.
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.
unsigned getArithmeticReductionInstruction(Intrinsic::ID RdxID)
Returns the arithmetic instruction opcode used when expanding a reduction.
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...
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.
constexpr T divideNearest(U Numerator, V Denominator)
Returns (Numerator / Denominator) rounded by round-half-up.
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.
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.
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
Value * getShuffleReduction(IRBuilderBase &Builder, Value *Src, unsigned Op, TargetTransformInfo::ReductionShuffle RS, RecurKind MinMaxKind=RecurKind::None)
Generates a vector reduction using shufflevectors to reduce the value.
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...
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
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.
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
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...
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)
RecurKind getMinMaxReductionRecurKind(Intrinsic::ID RdxID)
Returns the recurence kind used when expanding a min/max reduction.
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...
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
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.
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...
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.