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 DPV.getDebugLoc().get());
640 if (!DeadDebugSet.
insert(Key).second)
643 DPV.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(DPV, 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:
1039 if (
auto VTy = dyn_cast<VectorType>(
Left->getType()))
1050 (RK == RecurKind::FMinimum || RK == RecurKind::FMaximum)) {
1065 unsigned VF = cast<FixedVectorType>(Src->getType())->getNumElements();
1069 Value *Result = Acc;
1070 for (
unsigned ExtractIdx = 0; ExtractIdx != VF; ++ExtractIdx) {
1074 if (
Op != Instruction::ICmp &&
Op != Instruction::FCmp) {
1090 unsigned VF = cast<FixedVectorType>(Src->getType())->getNumElements();
1095 "Reduction emission only supported for pow2 vectors!");
1103 Value *TmpVec = Src;
1105 for (
unsigned i = VF; i != 1; i >>= 1) {
1107 for (
unsigned j = 0; j != i / 2; ++j)
1108 ShuffleMask[j] = i / 2 + j;
1111 std::fill(&ShuffleMask[i / 2], ShuffleMask.
end(), -1);
1115 if (
Op != Instruction::ICmp &&
Op != Instruction::FCmp) {
1133 "Unexpected reduction kind");
1134 Value *InitVal =
Desc.getRecurrenceStartValue();
1135 Value *NewVal =
nullptr;
1140 for (
auto *U : OrigPhi->
users()) {
1141 if ((SI = dyn_cast<SelectInst>(U)))
1144 assert(SI &&
"One user of the original phi should be a select");
1146 if (SI->getTrueValue() == OrigPhi)
1147 NewVal = SI->getFalseValue();
1149 assert(SI->getFalseValue() == OrigPhi &&
1150 "At least one input to the select should be the original Phi");
1151 NewVal = SI->getTrueValue();
1156 ElementCount EC = cast<VectorType>(Src->getType())->getElementCount();
1163 return Builder.
CreateSelect(Cmp, NewVal, InitVal,
"rdx.select");
1168 auto *SrcVecEltTy = cast<VectorType>(Src->getType())->getElementType();
1170 case RecurKind::Add:
1172 case RecurKind::Mul:
1174 case RecurKind::And:
1178 case RecurKind::Xor:
1180 case RecurKind::FMulAdd:
1181 case RecurKind::FAdd:
1184 case RecurKind::FMul:
1186 case RecurKind::SMax:
1188 case RecurKind::SMin:
1190 case RecurKind::UMax:
1192 case RecurKind::UMin:
1194 case RecurKind::FMax:
1196 case RecurKind::FMin:
1198 case RecurKind::FMinimum:
1200 case RecurKind::FMaximum:
1214 B.setFastMathFlags(
Desc.getFastMathFlags());
1226 assert((
Desc.getRecurrenceKind() == RecurKind::FAdd ||
1227 Desc.getRecurrenceKind() == RecurKind::FMulAdd) &&
1228 "Unexpected reduction kind");
1229 assert(Src->getType()->isVectorTy() &&
"Expected a vector type");
1230 assert(!Start->getType()->isVectorTy() &&
"Expected a scalar type");
1232 return B.CreateFAddReduce(Start, Src);
1236 bool IncludeWrapFlags) {
1237 auto *VecOp = dyn_cast<Instruction>(
I);
1240 auto *Intersection = (OpValue ==
nullptr) ? dyn_cast<Instruction>(VL[0])
1241 : dyn_cast<Instruction>(OpValue);
1244 const unsigned Opcode = Intersection->getOpcode();
1245 VecOp->copyIRFlags(Intersection, IncludeWrapFlags);
1246 for (
auto *V : VL) {
1247 auto *Instr = dyn_cast<Instruction>(V);
1250 if (OpValue ==
nullptr || Opcode == Instr->getOpcode())
1251 VecOp->andIRFlags(V);
1288 auto Predicate =
Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
1299 auto Predicate =
Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
1315 while (!WorkList.
empty()) {
1318 if (!L->contains(Curr))
1324 for (
const auto *U : Curr->
users()) {
1325 auto *UI = cast<Instruction>(U);
1326 if (Visited.
insert(UI).second)
1352 BasicBlock *Preheader = L->getLoopPreheader();
1362 L->getExitingBlocks(ExitingBlocks);
1364 L->getUniqueExitBlocks(ExitBlocks);
1365 if (ExitBlocks.
size() != 1 || ExitingBlocks.
size() != 1)
1370 while (
PHINode *
P = dyn_cast<PHINode>(BI)) {
1377 for (
const RewritePhi &Phi : RewritePhiSet) {
1378 unsigned i = Phi.Ith;
1379 if (Phi.PN ==
P && (Phi.PN)->getIncomingValue(i) ==
Incoming) {
1386 if (!found && (
I = dyn_cast<Instruction>(
Incoming)))
1387 if (!L->hasLoopInvariantOperands(
I))
1393 for (
auto *BB : L->blocks())
1395 return I.mayHaveSideEffects();
1409 if (!L->getLoopPreheader())
1411 if (Phi->getParent() != L->getHeader())
1423 assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
1424 "Indvars did not preserve LCSSA!");
1427 L->getUniqueExitBlocks(ExitBlocks);
1436 PHINode *PN = dyn_cast<PHINode>(ExitBB->begin());
1443 while ((PN = dyn_cast<PHINode>(BBI++))) {
1451 for (
unsigned i = 0; i != NumPreds; ++i) {
1455 if (!isa<Instruction>(InVal))
1464 if (!L->contains(Inst))
1474 PHINode *IndPhi = dyn_cast<PHINode>(Inst);
1481 if (!isa<PHINode>(U) && !isa<BinaryOperator>(U))
1483 BinaryOperator *B = dyn_cast<BinaryOperator>(U);
1484 if (B && B != ID.getInductionBinOp())
1496 PHINode *Phi = dyn_cast<PHINode>(U);
1497 if (Phi != PN && !checkIsIndPhi(Phi, L, SE, ID))
1502 if (
B !=
ID.getInductionBinOp())
1514 if (isa<SCEVCouldNotCompute>(ExitValue) ||
1516 !
Rewriter.isSafeToExpand(ExitValue)) {
1522 if (isa<SCEVCouldNotCompute>(ExitCount))
1524 if (
auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE->
getSCEV(Inst)))
1525 if (AddRec->getLoop() == L)
1526 ExitValue = AddRec->evaluateAtIteration(ExitCount, *SE);
1527 if (isa<SCEVCouldNotCompute>(ExitValue) ||
1529 !
Rewriter.isSafeToExpand(ExitValue))
1543 bool HighCost =
Rewriter.isHighCostExpansion(
1554 (isa<PHINode>(Inst) || isa<LandingPadInst>(Inst)) ?
1556 RewritePhiSet.
emplace_back(PN, i, ExitValue, InsertPt, HighCost);
1567 int NumReplaced = 0;
1570 for (
const RewritePhi &Phi : RewritePhiSet) {
1577 !LoopCanBeDel && Phi.HighCost)
1581 Phi.ExpansionSCEV, Phi.PN->getType(), Phi.ExpansionPoint);
1583 LLVM_DEBUG(
dbgs() <<
"rewriteLoopExitValues: AfterLoopVal = " << *ExitVal
1585 <<
" LoopVal = " << *(Phi.ExpansionPoint) <<
"\n");
1591 if (
auto *ExitInsn = dyn_cast<Instruction>(ExitVal))
1592 if (
auto *EVL = LI->
getLoopFor(ExitInsn->getParent()))
1594 assert(EVL->contains(L) &&
"LCSSA breach detected!");
1630 assert(UF > 0 &&
"Zero unrolled factor is not supported");
1631 assert(UnrolledLoop != RemainderLoop &&
1632 "Unrolled and Remainder loops are expected to distinct");
1635 unsigned OrigLoopInvocationWeight = 0;
1636 std::optional<unsigned> OrigAverageTripCount =
1638 if (!OrigAverageTripCount)
1642 unsigned UnrolledAverageTripCount = *OrigAverageTripCount / UF;
1644 unsigned RemainderAverageTripCount = *OrigAverageTripCount % UF;
1647 OrigLoopInvocationWeight);
1649 OrigLoopInvocationWeight);
1655template <
typename RangeT>
1665 assert(PreOrderLoops.
empty() &&
"Must start with an empty preorder walk.");
1667 "Must start with an empty preorder walk worklist.");
1671 PreOrderWorklist.
append(L->begin(), L->end());
1673 }
while (!PreOrderWorklist.
empty());
1675 Worklist.
insert(std::move(PreOrderLoops));
1676 PreOrderLoops.
clear();
1680template <
typename RangeT>
1686template void llvm::appendLoopsToWorklist<ArrayRef<Loop *> &>(
1690llvm::appendLoopsToWorklist<Loop &>(
Loop &L,
1702 PL->addChildLoop(&New);
1712 New.addBasicBlockToLoop(cast<BasicBlock>(VM[BB]), *LI);
1739 Value *Start =
nullptr, *
End =
nullptr;
1754 isa<SCEVAddRecExpr>(
High) && isa<SCEVAddRecExpr>(
Low)) {
1755 auto *HighAR = cast<SCEVAddRecExpr>(
High);
1756 auto *LowAR = cast<SCEVAddRecExpr>(
Low);
1758 const SCEV *Recur = LowAR->getStepRecurrence(*Exp.getSE());
1759 if (Recur == HighAR->getStepRecurrence(*Exp.getSE()) &&
1760 HighAR->getLoop() == OuterLoop && LowAR->getLoop() == OuterLoop) {
1762 const SCEV *OuterExitCount =
1763 Exp.getSE()->getExitCount(OuterLoop, OuterLoopLatch);
1764 if (!isa<SCEVCouldNotCompute>(OuterExitCount) &&
1766 const SCEV *NewHigh = cast<SCEVAddRecExpr>(
High)->evaluateAtIteration(
1767 OuterExitCount, *Exp.getSE());
1768 if (!isa<SCEVCouldNotCompute>(NewHigh)) {
1769 LLVM_DEBUG(
dbgs() <<
"LAA: Expanded RT check for range to include "
1770 "outer loop in order to permit hoisting\n");
1772 Low = cast<SCEVAddRecExpr>(
Low)->getStart();
1775 if (!Exp.getSE()->isKnownNonNegative(Recur)) {
1779 << *Stride <<
'\n');
1786 Start = Exp.expandCodeFor(
Low, PtrArithTy, Loc);
1787 End = Exp.expandCodeFor(
High, PtrArithTy, Loc);
1790 Start = Builder.
CreateFreeze(Start, Start->getName() +
".fr");
1794 Stride ? Exp.expandCodeFor(Stride, Stride->getType(), Loc) :
nullptr;
1796 return {Start,
End, StrideVal};
1808 transform(PointerChecks, std::back_inserter(ChecksWithBounds),
1814 return std::make_pair(
First, Second);
1817 return ChecksWithBounds;
1826 auto ExpandedChecks =
1834 Value *MemoryRuntimeCheck =
nullptr;
1836 for (
const auto &
Check : ExpandedChecks) {
1841 assert((
A.Start->getType()->getPointerAddressSpace() ==
1842 B.End->getType()->getPointerAddressSpace()) &&
1843 (
B.Start->getType()->getPointerAddressSpace() ==
1844 A.End->getType()->getPointerAddressSpace()) &&
1845 "Trying to bounds check pointers with different address spaces");
1857 Value *IsConflict = ChkBuilder.
CreateAnd(Cmp0, Cmp1,
"found.conflict");
1858 if (
A.StrideToCheck) {
1860 A.StrideToCheck, ConstantInt::get(
A.StrideToCheck->getType(), 0),
1862 IsConflict = ChkBuilder.
CreateOr(IsConflict, IsNegativeStride);
1864 if (
B.StrideToCheck) {
1866 B.StrideToCheck, ConstantInt::get(
B.StrideToCheck->getType(), 0),
1868 IsConflict = ChkBuilder.
CreateOr(IsConflict, IsNegativeStride);
1870 if (MemoryRuntimeCheck) {
1872 ChkBuilder.
CreateOr(MemoryRuntimeCheck, IsConflict,
"conflict.rdx");
1874 MemoryRuntimeCheck = IsConflict;
1877 return MemoryRuntimeCheck;
1889 Value *MemoryRuntimeCheck =
nullptr;
1891 auto &SE = *Expander.
getSE();
1895 for (
const auto &
C : Checks) {
1896 Type *Ty =
C.SinkStart->getType();
1898 auto *VFTimesUFTimesSize =
1900 ConstantInt::get(Ty, IC *
C.AccessSize));
1902 SE.getMinusSCEV(
C.SinkStart,
C.SrcStart), Ty, Loc);
1906 Value *IsConflict = SeenCompares.
lookup({Diff, VFTimesUFTimesSize});
1911 ChkBuilder.
CreateICmpULT(Diff, VFTimesUFTimesSize,
"diff.check");
1912 SeenCompares.
insert({{Diff, VFTimesUFTimesSize}, IsConflict});
1916 if (MemoryRuntimeCheck) {
1918 ChkBuilder.
CreateOr(MemoryRuntimeCheck, IsConflict,
"conflict.rdx");
1920 MemoryRuntimeCheck = IsConflict;
1923 return MemoryRuntimeCheck;
1926std::optional<IVConditionInfo>
1929 auto *TI = dyn_cast<BranchInst>(L.getHeader()->getTerminator());
1930 if (!TI || !TI->isConditional())
1933 auto *CondI = dyn_cast<CmpInst>(TI->getCondition());
1936 if (!CondI || !L.contains(CondI))
1943 WorkList.
append(CondI->op_begin(), CondI->op_end());
1947 while (!WorkList.
empty()) {
1949 if (!
I || !L.contains(
I))
1953 if (!isa<LoadInst>(
I) && !isa<GetElementPtrInst>(
I))
1957 if (
auto *LI = dyn_cast<LoadInst>(
I))
1958 if (LI->isVolatile() || LI->isAtomic())
1963 if (
auto *MemUse = dyn_cast_or_null<MemoryUse>(MA)) {
1965 AccessesToCheck.
push_back(MemUse->getDefiningAccess());
1973 WorkList.
append(
I->op_begin(),
I->op_end());
1976 if (InstToDuplicate.
empty())
1980 L.getExitingBlocks(ExitingBlocks);
1981 auto HasNoClobbersOnPath =
1982 [&L, &AA, &AccessedLocs, &ExitingBlocks, &InstToDuplicate,
1985 -> std::optional<IVConditionInfo> {
1997 while (!WorkList.
empty()) {
1999 if (!L.contains(Current))
2001 const auto &SeenIns = Seen.
insert(Current);
2002 if (!SeenIns.second)
2006 *Current, [](
Instruction &
I) {
return !
I.mayHaveSideEffects(); });
2012 if (Seen.
size() < 2)
2020 while (!AccessesToCheck.
empty()) {
2022 auto SeenI = SeenAccesses.
insert(Current);
2031 if (isa<MemoryUse>(Current))
2036 if (
auto *CurrentDef = dyn_cast<MemoryDef>(Current)) {
2044 for (
Use &U : Current->
uses())
2045 AccessesToCheck.
push_back(cast<MemoryAccess>(U.getUser()));
2055 if (
Info.PathIsNoop) {
2056 for (
auto *Exiting : ExitingBlocks) {
2060 if (L.contains(Succ))
2063 Info.PathIsNoop &= Succ->phis().empty() &&
2064 (!
Info.ExitForPath ||
Info.ExitForPath == Succ);
2065 if (!
Info.PathIsNoop)
2068 "cannot have multiple exit blocks");
2069 Info.ExitForPath = Succ;
2073 if (!
Info.ExitForPath)
2074 Info.PathIsNoop =
false;
2076 Info.InstToDuplicate = InstToDuplicate;
2082 if (TI->getSuccessor(0) == TI->getSuccessor(1))
2085 if (
auto Info = HasNoClobbersOnPath(TI->getSuccessor(0), L.getHeader(),
2090 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.
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 * 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 ...
Record of a variable value-assignment, aka a non instruction representation of the dbg....
This class represents an Operation in the Expression.
uint64_t getNumOperands() const
Identifies a unique instance of a variable.
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
static constexpr ElementCount get(ScalarTy MinVal, bool Scalable)
Legacy wrapper pass to provide the GlobalsAAResult object.
Common base class shared among various IRBuilders.
CallInst * CreateMulReduce(Value *Src)
Create a vector int mul reduction intrinsic of the source vector.
CallInst * CreateFAddReduce(Value *Acc, Value *Src)
Create a sequential vector fadd reduction intrinsic of the source vector.
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
UnreachableInst * CreateUnreachable()
CallInst * CreateAndReduce(Value *Src)
Create a vector int AND reduction intrinsic of the source vector.
Value * CreateVectorSplat(unsigned NumElts, Value *V, const Twine &Name="")
Return a vector value that contains.
CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with Args, mangled using Types.
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
CallInst * CreateAddReduce(Value *Src)
Create a vector int add reduction intrinsic of the source vector.
Value * CreateFreeze(Value *V, const Twine &Name="")
CallInst * CreateXorReduce(Value *Src)
Create a vector int XOR reduction intrinsic of the source vector.
CallInst * CreateOrReduce(Value *Src)
Create a vector int OR reduction intrinsic of the source vector.
CallInst * CreateFPMinReduce(Value *Src)
Create a vector float min reduction intrinsic of the source vector.
CallInst * CreateFPMaximumReduce(Value *Src)
Create a vector float maximum reduction intrinsic of the source vector.
CallInst * CreateFPMaxReduce(Value *Src)
Create a vector float max reduction intrinsic of the source vector.
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Value * CreateCmp(CmpInst::Predicate Pred, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
Value * CreateShuffleVector(Value *V1, Value *V2, Value *Mask, const Twine &Name="")
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
CallInst * CreateIntMaxReduce(Value *Src, bool IsSigned=false)
Create a vector integer max reduction intrinsic of the source vector.
ConstantInt * getFalse()
Get the constant value for i1 false.
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Value * CreateICmpSLT(Value *LHS, Value *RHS, const Twine &Name="")
CallInst * CreateIntMinReduce(Value *Src, bool IsSigned=false)
Create a vector integer min reduction intrinsic of the source vector.
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
CallInst * CreateFMulReduce(Value *Acc, Value *Src)
Create a sequential vector fmul reduction intrinsic of the source vector.
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
CallInst * CreateFPMinimumReduce(Value *Src)
Create a vector float minimum reduction intrinsic of the source vector.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
A struct for saving information about induction variables.
static bool isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D, const SCEV *Expr=nullptr, SmallVectorImpl< Instruction * > *CastsToIgnore=nullptr)
Returns true if Phi is an induction in the loop L.
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
const BasicBlock * getParent() const
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
This is an important class for using LLVM in a threaded context.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
BlockT * getHeader() const
std::vector< Loop * >::const_iterator iterator
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
void removeBlock(BlockT *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
LoopT * AllocateLoop(ArgsTy &&...Args)
LoopT * removeLoop(iterator I)
This removes the specified top-level loop from this loop info object.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
void destroy(LoopT *L)
Destroy a loop that has been removed from the LoopInfo nest.
The legacy pass manager's analysis pass to compute loop information.
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Represents a single loop in the control flow graph.
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight)
Return metadata containing two branch weights.
void replaceOperandWith(unsigned I, Metadata *New)
Replace a specific operand.
const MDOperand & getOperand(unsigned I) const
ArrayRef< MDOperand > operands() const
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
unsigned getNumOperands() const
Return number of MDNode operands.
LLVMContext & getContext() const
Tracking metadata reference owned by Metadata.
StringRef getString() const
static MDString * get(LLVMContext &Context, StringRef Str)
BasicBlock * getBlock() const
Representation for a specific memory location.
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
Legacy analysis pass which computes MemorySSA.
Encapsulates MemorySSA, including all data associated with memory accesses.
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
void setIncomingValue(unsigned i, Value *V)
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
bool insert(const T &X)
Insert a new element into the PriorityWorklist.
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
static bool isAnyOfRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...
static bool isMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is any min/max kind.
A global registry used in conjunction with static constructors to make pluggable components (like tar...
Legacy wrapper pass to provide the SCEVAAResult object.
This class uses information about analyze scalars to rewrite expressions in canonical form.
ScalarEvolution * getSE()
Value * expandCodeFor(const SCEV *SH, Type *Ty, BasicBlock::iterator I)
Insert code to directly compute the specified SCEV expression into the program.
This class represents an analyzed expression in the program.
Type * getType() const
Return the LLVM type of this SCEV expression.
The main scalar evolution driver.
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
const SCEV * getConstant(ConstantInt *V)
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
@ LoopInvariant
The SCEV is loop-invariant.
bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS.
This class represents the LLVM 'select' instruction.
Implements a dense probed hash-table based set with some number of buckets stored inline.
A version of PriorityWorklist that selects small size optimized data structures for the vector and ma...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
bool starts_with(StringRef Prefix) const
Check if this string starts with the given Prefix.
bool equals(StringRef RHS) const
equals - Check for string equality, this is more efficient than compare() when the relative ordering ...
Provides information about what library functions are available for the current target.
Value handle that tracks a Value across RAUW.
The instances of the Type class are immutable: once they are created, they are never changed.
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
static IntegerType * getInt32Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< use_iterator > uses()
StringRef getName() const
Return a constant reference to the value's name.
std::pair< iterator, bool > insert(const ValueT &V)
An efficient, type-erasing, non-owning reference to a callable.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
std::optional< ElementCount > getOptionalElementCountLoopAttribute(const Loop *TheLoop)
Find a combination of metadata ("llvm.loop.vectorize.width" and "llvm.loop.vectorize....
@ Low
Lower the current thread's priority such that it does not affect foreground tasks significantly.
SmallVector< DomTreeNode *, 16 > collectChildrenInLoop(DomTreeNode *N, const Loop *CurLoop)
Does a BFS from a given node to all of its children inside a given loop.
Interval::succ_iterator succ_end(Interval *I)
Value * addRuntimeChecks(Instruction *Loc, Loop *TheLoop, const SmallVectorImpl< RuntimePointerCheck > &PointerChecks, SCEVExpander &Expander, bool HoistRuntimeChecks=false)
Add code that checks at runtime if the accessed arrays in PointerChecks overlap.
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
std::optional< unsigned > getLoopEstimatedTripCount(Loop *L, unsigned *EstimatedLoopInvocationWeight=nullptr)
Returns a loop's estimated trip count based on branch weight metadata.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
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.
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...
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.
TransformationMode hasVectorizeTransformation(const Loop *L)
OutputIt transform(R &&Range, OutputIt d_first, UnaryFunction F)
Wrapper function around std::transform to apply a function to a range and store the result elsewhere.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
uint64_t divideNearest(uint64_t Numerator, uint64_t Denominator)
Returns the integer nearest(Numerator / Denominator).
SmallVector< Instruction *, 8 > findDefsUsedOutsideOfLoop(Loop *L)
Returns the instructions that use values defined in the loop.
auto reverse(ContainerTy &&C)
bool isMustProgress(const Loop *L)
Return true if this loop can be assumed to make progress.
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
bool isModSet(const ModRefInfo MRI)
TransformationMode hasUnrollAndJamTransformation(const Loop *L)
void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI, MemorySSA *MSSA=nullptr)
This function deletes dead loops.
Value * getShuffleReduction(IRBuilderBase &Builder, Value *Src, unsigned Op, RecurKind MinMaxKind=RecurKind::None)
Generates a vector reduction using shufflevectors to reduce the value.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool hasDisableAllTransformsHint(const Loop *L)
Look for the loop attribute that disables all transformation heuristic.
Value * createOrderedReduction(IRBuilderBase &B, const RecurrenceDescriptor &Desc, Value *Src, Value *Start)
Create an ordered reduction intrinsic using the given recurrence descriptor Desc.
cl::opt< unsigned > SCEVCheapExpansionBudget
TransformationMode hasUnrollTransformation(const Loop *L)
TransformationMode hasDistributeTransformation(const Loop *L)
void breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA)
Remove the backedge of the specified loop.
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
void propagateIRFlags(Value *I, ArrayRef< Value * > VL, Value *OpValue=nullptr, bool IncludeWrapFlags=true)
Get the intersection (logical and) of all of the potential IR flags of each scalar operation (VL) tha...
bool isKnownPositiveInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)
Returns true if we can prove that S is defined and always positive in loop L.
unsigned changeToUnreachable(Instruction *I, bool PreserveLCSSA=false, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...
std::optional< int > getOptionalIntLoopAttribute(const Loop *TheLoop, StringRef Name)
Find named metadata for a loop with an integer value.
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
CmpInst::Predicate getMinMaxReductionPredicate(RecurKind RK)
Returns the comparison predicate used when expanding a min/max reduction.
TransformationMode hasLICMVersioningTransformation(const Loop *L)
bool VerifyMemorySSA
Enables verification of MemorySSA.
TransformationMode
The mode sets how eager a transformation should be applied.
@ TM_Unspecified
The pass can use heuristics to determine whether a transformation should be applied.
@ TM_SuppressedByUser
The transformation must not be applied.
@ TM_ForcedByUser
The transformation was directed by the user, e.g.
@ TM_Disable
The transformation should not be applied.
@ TM_Enable
The transformation should be applied without considering a cost model.
bool hasDisableLICMTransformsHint(const Loop *L)
Look for the loop attribute that disables the LICM transformation heuristics.
RecurKind
These are the kinds of recurrences that we support.
bool setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount, unsigned EstimatedLoopInvocationWeight)
Set a loop's branch weight metadata to reflect that loop has EstimatedTripCount iterations and Estima...
Value * createAnyOfOp(IRBuilderBase &Builder, Value *StartVal, RecurKind RK, Value *Left, Value *Right)
See RecurrenceDescriptor::isAnyOfPattern for a description of the pattern we are trying to match.
void setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop, Loop *RemainderLoop, uint64_t UF)
Set weights for UnrolledLoop and RemainderLoop based on weights for OrigLoop and the following distri...
bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Ensure that all exit blocks of the loop are dedicated exits.
DWARFExpression::Operation Op
void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
bool isKnownNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)
Returns true if we can prove that S is defined and always negative in loop L.
constexpr unsigned BitWidth
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
bool hasIterationCountInvariantInParent(Loop *L, ScalarEvolution &SE)
Check inner loop (L) backedge count is known to be invariant on all iterations of its outer loop.
bool isAlmostDeadIV(PHINode *IV, BasicBlock *LatchBlock, Value *Cond)
Return true if the induction variable IV in a Loop whose latch is LatchBlock would become dead if the...
auto predecessors(const MachineBasicBlock *BB)
int rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI, ScalarEvolution *SE, const TargetTransformInfo *TTI, SCEVExpander &Rewriter, DominatorTree *DT, ReplaceExitVal ReplaceExitValue, SmallVector< WeakTrackingVH, 16 > &DeadInsts)
If the final value of any expressions that are recurrent in the loop can be computed,...
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Value * addDiffRuntimeChecks(Instruction *Loc, ArrayRef< PointerDiffInfo > Checks, SCEVExpander &Expander, function_ref< Value *(IRBuilderBase &, unsigned)> GetVF, unsigned IC)
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 DPValue 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.