52#define DEBUG_TYPE "loop-utils"
67 "Must start with an empty predecessors list!");
72 bool IsDedicatedExit =
true;
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())
113 if (!Visited.
insert(SuccBB).second)
116 Changed |= RewriteExit(SuccBB);
129 for (
auto &Inst : *Block) {
130 auto Users = Inst.users();
132 auto *
Use = cast<Instruction>(U);
220 for (
unsigned i = 1, ie = LoopID->
getNumOperands(); i < ie; ++i) {
223 if (Node->getNumOperands() == 2) {
224 MDString *S = dyn_cast<MDString>(Node->getOperand(0));
227 mdconst::extract_or_null<ConstantInt>(Node->getOperand(1));
249std::optional<ElementCount>
251 std::optional<int> Width =
256 TheLoop,
"llvm.loop.vectorize.scalable.enable");
265 const char *InheritOptionsExceptPrefix,
bool AlwaysNew) {
274 bool InheritAllAttrs = !InheritOptionsExceptPrefix;
275 bool InheritSomeAttrs =
276 InheritOptionsExceptPrefix && InheritOptionsExceptPrefix[0] !=
'\0';
280 bool Changed =
false;
281 if (InheritAllAttrs || InheritSomeAttrs) {
283 MDNode *Op = cast<MDNode>(Existing.get());
285 auto InheritThisAttribute = [InheritSomeAttrs,
286 InheritOptionsExceptPrefix](
MDNode *Op) {
287 if (!InheritSomeAttrs)
291 if (Op->getNumOperands() == 0)
293 Metadata *NameMD = Op->getOperand(0).get();
294 if (!isa<MDString>(NameMD))
296 StringRef AttrName = cast<MDString>(NameMD)->getString();
299 return !AttrName.
startswith(InheritOptionsExceptPrefix);
302 if (InheritThisAttribute(Op))
312 bool HasAnyFollowup =
false;
313 for (
StringRef OptionName : FollowupOptions) {
318 HasAnyFollowup =
true;
327 if (!AlwaysNew && !HasAnyFollowup)
331 if (!AlwaysNew && !Changed)
341 return FollowupLoopID;
356 std::optional<int> Count =
377 std::optional<int> Count =
392 std::optional<bool>
Enable =
398 std::optional<ElementCount> VectorizeWidth =
400 std::optional<int> InterleaveCount =
405 if (
Enable ==
true && VectorizeWidth && VectorizeWidth->isScalar() &&
406 InterleaveCount == 1)
415 if ((VectorizeWidth && VectorizeWidth->isScalar()) && InterleaveCount == 1)
418 if ((VectorizeWidth && VectorizeWidth->isVector()) || InterleaveCount > 1)
459 AddRegionToWorklist(
N);
461 for (
size_t I = 0;
I < Worklist.
size();
I++) {
463 AddRegionToWorklist(Child);
473 assert(Preheader &&
"Preheader should exist!");
475 std::unique_ptr<MemorySSAUpdater> MSSAU;
477 MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
495 "Preheader must end with a side-effect-free terminator");
497 "Preheader must have a single successor");
528 assert(ExitBlock &&
"Should have a unique exit block!");
537 for (
PHINode &
P : ExitBlock->phis()) {
542 P.setIncomingBlock(PredIndex, Preheader);
550 for (
unsigned i = 0, e =
P.getNumIncomingValues() - 1; i != e; ++i)
551 P.removeIncomingValue(e - i,
false);
553 assert((
P.getNumIncomingValues() == 1 &&
554 P.getIncomingBlock(PredIndex) == Preheader) &&
555 "Should have exactly one value and that's from the preheader!");
559 DTU.
applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}});
561 MSSAU->applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}},
569 Builder.SetInsertPoint(Preheader->getTerminator());
572 Preheader->getTerminator()->eraseFromParent();
575 "Loop should have either zero or one exit blocks.");
577 Builder.SetInsertPoint(OldTerm);
579 Preheader->getTerminator()->eraseFromParent();
585 MSSAU->applyUpdates({{DominatorTree::Delete, Preheader, L->
getHeader()}},
589 MSSAU->removeBlocks(DeadBlockSet);
608 for (
auto *Block : L->
blocks())
612 if (
auto *Usr = dyn_cast<Instruction>(U.getUser()))
619 "Unexpected user in reachable block");
622 auto *DVI = dyn_cast<DbgVariableIntrinsic>(&
I);
635 Instruction *InsertDbgValueBefore = ExitBlock->getFirstNonPHI();
636 assert(InsertDbgValueBefore &&
637 "There should be a non-PHI instruction in exit block, else these "
638 "instructions will have no parent.");
639 for (
auto *DVI : DeadDebugInst) {
640 DVI->setKillLocation();
641 DVI->moveBefore(InsertDbgValueBefore);
647 for (
auto *Block : L->
blocks())
648 Block->dropAllReferences();
659 BB->eraseFromParent();
675 assert(
I != ParentLoop->end() &&
"Couldn't find loop");
676 ParentLoop->removeChildLoop(
I);
679 assert(
I != LI->
end() &&
"Couldn't find loop");
689 assert(Latch &&
"multiple latches not yet supported");
696 std::unique_ptr<MemorySSAUpdater> MSSAU;
698 MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
703 if (
auto *BI = dyn_cast<BranchInst>(Latch->getTerminator())) {
704 if (!BI->isConditional()) {
718 const unsigned ExitIdx = L->
contains(BI->getSuccessor(0)) ? 1 : 0;
719 BasicBlock *ExitBB = BI->getSuccessor(ExitIdx);
722 Header->removePredecessor(Latch,
true);
725 auto *NewBI =
Builder.CreateBr(ExitBB);
728 NewBI->copyMetadata(*BI, {LLVMContext::MD_dbg,
729 LLVMContext::MD_annotation});
731 BI->eraseFromParent();
732 DTU.
applyUpdates({{DominatorTree::Delete, Latch, Header}});
734 MSSAU->applyUpdates({{DominatorTree::Delete, Latch, Header}}, DT);
742 auto *BackedgeBB =
SplitEdge(Latch, Header, &DT, &LI, MSSAU.get());
746 true, &DTU, MSSAU.get());
758 if (OutermostLoop != L)
777 "At least one edge out of the latch must go to the header");
801 OrigExitWeight = ExitWeight;
807 return ExitCount + 1;
810std::optional<unsigned>
812 unsigned *EstimatedLoopInvocationWeight) {
819 if (std::optional<uint64_t> EstTripCount =
821 if (EstimatedLoopInvocationWeight)
822 *EstimatedLoopInvocationWeight = ExitWeight;
823 return *EstTripCount;
830 unsigned EstimatedloopInvocationWeight) {
839 unsigned LatchExitWeight = 0;
840 unsigned BackedgeTakenWeight = 0;
842 if (EstimatedTripCount > 0) {
843 LatchExitWeight = EstimatedloopInvocationWeight;
844 BackedgeTakenWeight = (EstimatedTripCount - 1) * LatchExitWeight;
849 std::swap(BackedgeTakenWeight, LatchExitWeight);
855 LLVMContext::MD_prof,
869 const SCEV *InnerLoopBECountSC = SE.
getExitCount(InnerLoop, InnerLoopLatch);
870 if (isa<SCEVCouldNotCompute>(InnerLoopBECountSC) ||
887 case RecurKind::UMin:
889 case RecurKind::UMax:
891 case RecurKind::SMin:
893 case RecurKind::SMax:
895 case RecurKind::FMin:
897 case RecurKind::FMax:
904 if (
auto VTy = dyn_cast<VectorType>(
Left->getType()))
905 StartVal =
Builder.CreateVectorSplat(VTy->getElementCount(), StartVal);
922 unsigned VF = cast<FixedVectorType>(Src->getType())->getNumElements();
927 for (
unsigned ExtractIdx = 0; ExtractIdx != VF; ++ExtractIdx) {
931 if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
947 unsigned VF = cast<FixedVectorType>(Src->getType())->getNumElements();
952 "Reduction emission only supported for pow2 vectors!");
962 for (
unsigned i = VF; i != 1; i >>= 1) {
964 for (
unsigned j = 0; j != i / 2; ++j)
965 ShuffleMask[j] = i / 2 + j;
968 std::fill(&ShuffleMask[i / 2], ShuffleMask.
end(), -1);
970 Value *Shuf =
Builder.CreateShuffleVector(TmpVec, ShuffleMask,
"rdx.shuf");
972 if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
992 "Unexpected reduction kind");
994 Value *NewVal =
nullptr;
999 for (
auto *U : OrigPhi->
users()) {
1000 if ((
SI = dyn_cast<SelectInst>(U)))
1003 assert(
SI &&
"One user of the original phi should be a select");
1005 if (
SI->getTrueValue() == OrigPhi)
1006 NewVal =
SI->getFalseValue();
1008 assert(
SI->getFalseValue() == OrigPhi &&
1009 "At least one input to the select should be the original Phi");
1010 NewVal =
SI->getTrueValue();
1015 ElementCount EC = cast<VectorType>(Src->getType())->getElementCount();
1021 Cmp =
Builder.CreateOrReduce(Cmp);
1022 return Builder.CreateSelect(Cmp, NewVal, InitVal,
"rdx.select");
1028 auto *SrcVecEltTy = cast<VectorType>(Src->getType())->getElementType();
1030 case RecurKind::Add:
1031 return Builder.CreateAddReduce(Src);
1032 case RecurKind::Mul:
1033 return Builder.CreateMulReduce(Src);
1034 case RecurKind::And:
1035 return Builder.CreateAndReduce(Src);
1037 return Builder.CreateOrReduce(Src);
1038 case RecurKind::Xor:
1039 return Builder.CreateXorReduce(Src);
1040 case RecurKind::FMulAdd:
1041 case RecurKind::FAdd:
1044 case RecurKind::FMul:
1046 case RecurKind::SMax:
1047 return Builder.CreateIntMaxReduce(Src,
true);
1048 case RecurKind::SMin:
1049 return Builder.CreateIntMinReduce(Src,
true);
1050 case RecurKind::UMax:
1051 return Builder.CreateIntMaxReduce(Src,
false);
1052 case RecurKind::UMin:
1053 return Builder.CreateIntMinReduce(Src,
false);
1054 case RecurKind::FMax:
1055 return Builder.CreateFPMaxReduce(Src);
1056 case RecurKind::FMin:
1057 return Builder.CreateFPMinReduce(Src);
1085 "Unexpected reduction kind");
1086 assert(Src->getType()->isVectorTy() &&
"Expected a vector type");
1087 assert(!Start->getType()->isVectorTy() &&
"Expected a scalar type");
1089 return B.CreateFAddReduce(Start, Src);
1093 bool IncludeWrapFlags) {
1094 auto *VecOp = dyn_cast<Instruction>(
I);
1097 auto *Intersection = (OpValue ==
nullptr) ? dyn_cast<Instruction>(VL[0])
1098 : dyn_cast<Instruction>(OpValue);
1101 const unsigned Opcode = Intersection->getOpcode();
1102 VecOp->copyIRFlags(Intersection, IncludeWrapFlags);
1103 for (
auto *V : VL) {
1104 auto *Instr = dyn_cast<Instruction>(V);
1107 if (OpValue ==
nullptr || Opcode == Instr->getOpcode())
1108 VecOp->andIRFlags(V);
1131 auto Predicate =
Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
1142 auto Predicate =
Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
1158 while (!WorkList.
empty()) {
1167 for (
const auto *U : Curr->
users()) {
1168 auto *UI = cast<Instruction>(U);
1169 if (Visited.
insert(UI).second)
1208 if (ExitBlocks.
size() != 1 || ExitingBlocks.
size() != 1)
1213 while (
PHINode *
P = dyn_cast<PHINode>(BI)) {
1214 Value *Incoming =
P->getIncomingValueForBlock(ExitingBlocks[0]);
1220 for (
const RewritePhi &Phi : RewritePhiSet) {
1221 unsigned i = Phi.Ith;
1222 if (Phi.PN ==
P && (Phi.PN)->getIncomingValue(i) == Incoming) {
1229 if (!found && (
I = dyn_cast<Instruction>(Incoming)))
1236 for (
auto *BB : L->
blocks())
1238 return I.mayHaveSideEffects();
1267 "Indvars did not preserve LCSSA!");
1279 PHINode *PN = dyn_cast<PHINode>(ExitBB->begin());
1286 while ((PN = dyn_cast<PHINode>(BBI++))) {
1294 for (
unsigned i = 0; i != NumPreds; ++i) {
1298 if (!isa<Instruction>(InVal))
1317 PHINode *IndPhi = dyn_cast<PHINode>(Inst);
1324 if (!isa<PHINode>(U) && !isa<BinaryOperator>(U))
1326 BinaryOperator *B = dyn_cast<BinaryOperator>(U);
1327 if (B && B != ID.getInductionBinOp())
1339 PHINode *Phi = dyn_cast<PHINode>(U);
1340 if (Phi != PN && !checkIsIndPhi(Phi, L, SE, ID))
1345 if (
B !=
ID.getInductionBinOp())
1357 if (isa<SCEVCouldNotCompute>(ExitValue) ||
1359 !
Rewriter.isSafeToExpand(ExitValue)) {
1365 if (isa<SCEVCouldNotCompute>(ExitCount))
1367 if (
auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE->
getSCEV(Inst)))
1368 if (AddRec->getLoop() == L)
1369 ExitValue = AddRec->evaluateAtIteration(ExitCount, *SE);
1370 if (isa<SCEVCouldNotCompute>(ExitValue) ||
1372 !
Rewriter.isSafeToExpand(ExitValue))
1386 bool HighCost =
Rewriter.isHighCostExpansion(
1397 (isa<PHINode>(Inst) || isa<LandingPadInst>(Inst)) ?
1399 RewritePhiSet.
emplace_back(PN, i, ExitValue, InsertPt, HighCost);
1410 int NumReplaced = 0;
1413 for (
const RewritePhi &Phi : RewritePhiSet) {
1420 !LoopCanBeDel && Phi.HighCost)
1424 Phi.ExpansionSCEV, Phi.PN->getType(), Phi.ExpansionPoint);
1426 LLVM_DEBUG(
dbgs() <<
"rewriteLoopExitValues: AfterLoopVal = " << *ExitVal
1428 <<
" LoopVal = " << *(Phi.ExpansionPoint) <<
"\n");
1434 if (
auto *ExitInsn = dyn_cast<Instruction>(ExitVal))
1435 if (
auto *EVL = LI->
getLoopFor(ExitInsn->getParent()))
1437 assert(EVL->contains(L) &&
"LCSSA breach detected!");
1473 assert(UF > 0 &&
"Zero unrolled factor is not supported");
1474 assert(UnrolledLoop != RemainderLoop &&
1475 "Unrolled and Remainder loops are expected to distinct");
1478 unsigned OrigLoopInvocationWeight = 0;
1479 std::optional<unsigned> OrigAverageTripCount =
1481 if (!OrigAverageTripCount)
1485 unsigned UnrolledAverageTripCount = *OrigAverageTripCount / UF;
1487 unsigned RemainderAverageTripCount = *OrigAverageTripCount % UF;
1490 OrigLoopInvocationWeight);
1492 OrigLoopInvocationWeight);
1498template <
typename RangeT>
1508 assert(PreOrderLoops.
empty() &&
"Must start with an empty preorder walk.");
1510 "Must start with an empty preorder walk worklist.");
1516 }
while (!PreOrderWorklist.
empty());
1518 Worklist.
insert(std::move(PreOrderLoops));
1519 PreOrderLoops.
clear();
1523template <
typename RangeT>
1529template void llvm::appendLoopsToWorklist<ArrayRef<Loop *> &>(
1533llvm::appendLoopsToWorklist<Loop &>(
Loop &L,
1545 PL->addChildLoop(&New);
1555 New.addBasicBlockToLoop(cast<BasicBlock>(VM[BB]), *LI);
1581 Value *Start =
nullptr, *End =
nullptr;
1583 Start = Exp.expandCodeFor(CG->
Low, PtrArithTy, Loc);
1584 End = Exp.expandCodeFor(CG->
High, PtrArithTy, Loc);
1587 Start =
Builder.CreateFreeze(Start, Start->getName() +
".fr");
1588 End =
Builder.CreateFreeze(End, End->getName() +
".fr");
1591 return {Start, End};
1603 transform(PointerChecks, std::back_inserter(ChecksWithBounds),
1607 return std::make_pair(First, Second);
1610 return ChecksWithBounds;
1619 auto ExpandedChecks =
expandBounds(PointerChecks, TheLoop, Loc, Exp);
1626 Value *MemoryRuntimeCheck =
nullptr;
1628 for (
const auto &
Check : ExpandedChecks) {
1632 unsigned AS0 =
A.Start->getType()->getPointerAddressSpace();
1633 unsigned AS1 =
B.Start->getType()->getPointerAddressSpace();
1635 assert((AS0 ==
B.End->getType()->getPointerAddressSpace()) &&
1636 (AS1 ==
A.End->getType()->getPointerAddressSpace()) &&
1637 "Trying to bounds check pointers with different address spaces");
1657 Value *IsConflict = ChkBuilder.
CreateAnd(Cmp0, Cmp1,
"found.conflict");
1658 if (MemoryRuntimeCheck) {
1660 ChkBuilder.
CreateOr(MemoryRuntimeCheck, IsConflict,
"conflict.rdx");
1662 MemoryRuntimeCheck = IsConflict;
1665 return MemoryRuntimeCheck;
1677 Value *MemoryRuntimeCheck =
nullptr;
1679 for (
const auto &
C : Checks) {
1680 Type *Ty =
C.SinkStart->getType();
1682 auto *VFTimesUFTimesSize =
1687 if (
C.NeedsFreeze) {
1689 Sink =
Builder.CreateFreeze(Sink, Sink->getName() +
".fr");
1690 Src =
Builder.CreateFreeze(Src, Src->getName() +
".fr");
1694 ChkBuilder.
CreateICmpULT(Diff, VFTimesUFTimesSize,
"diff.check");
1696 if (MemoryRuntimeCheck) {
1698 ChkBuilder.
CreateOr(MemoryRuntimeCheck, IsConflict,
"conflict.rdx");
1700 MemoryRuntimeCheck = IsConflict;
1703 return MemoryRuntimeCheck;
1706std::optional<IVConditionInfo>
1710 if (!TI || !TI->isConditional())
1713 auto *CondI = dyn_cast<CmpInst>(TI->getCondition());
1723 WorkList.
append(CondI->op_begin(), CondI->op_end());
1727 while (!WorkList.
empty()) {
1733 if (!isa<LoadInst>(
I) && !isa<GetElementPtrInst>(
I))
1737 if (
auto *LI = dyn_cast<LoadInst>(
I))
1738 if (LI->isVolatile() || LI->isAtomic())
1743 if (
auto *MemUse = dyn_cast_or_null<MemoryUse>(MA)) {
1745 AccessesToCheck.
push_back(MemUse->getDefiningAccess());
1753 WorkList.
append(
I->op_begin(),
I->op_end());
1756 if (InstToDuplicate.
empty())
1761 auto HasNoClobbersOnPath =
1762 [&L, &AA, &AccessedLocs, &ExitingBlocks, &InstToDuplicate,
1765 -> std::optional<IVConditionInfo> {
1777 while (!WorkList.
empty()) {
1781 const auto &SeenIns = Seen.
insert(Current);
1782 if (!SeenIns.second)
1786 *Current, [](
Instruction &
I) {
return !
I.mayHaveSideEffects(); });
1792 if (Seen.
size() < 2)
1800 while (!AccessesToCheck.
empty()) {
1802 auto SeenI = SeenAccesses.
insert(Current);
1811 if (isa<MemoryUse>(Current))
1816 if (
auto *CurrentDef = dyn_cast<MemoryDef>(Current)) {
1824 for (
Use &U : Current->
uses())
1825 AccessesToCheck.
push_back(cast<MemoryAccess>(U.getUser()));
1835 if (
Info.PathIsNoop) {
1836 for (
auto *Exiting : ExitingBlocks) {
1843 Info.PathIsNoop &= Succ->phis().empty() &&
1844 (!
Info.ExitForPath ||
Info.ExitForPath == Succ);
1845 if (!
Info.PathIsNoop)
1848 "cannot have multiple exit blocks");
1849 Info.ExitForPath = Succ;
1853 if (!
Info.ExitForPath)
1854 Info.PathIsNoop =
false;
1856 Info.InstToDuplicate = InstToDuplicate;
1862 if (TI->getSuccessor(0) == TI->getSuccessor(1))
1865 if (
auto Info = HasNoClobbersOnPath(TI->getSuccessor(0), L.
getHeader(),
1870 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.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
Analysis containing CSE Info
This file defines the DenseSet and SmallDenseSet classes.
This is the interface for a simple mod/ref and alias analysis over globals.
static const HTTPClientCleanup Cleanup
iv Induction Variable Users
static cl::opt< ReplaceExitVal > ReplaceExitValue("replexitval", cl::Hidden, cl::init(OnlyCheapRepl), cl::desc("Choose the strategy to replace exit value in IndVarSimplify"), cl::values(clEnumValN(NeverRepl, "never", "never replace exit value"), clEnumValN(OnlyCheapRepl, "cheap", "only replace exit value when the cost is cheap"), clEnumValN(UnusedIndVarInLoop, "unusedindvarinloop", "only replace exit value when it is an unused " "induction variable in the loop and has cheap replacement cost"), clEnumValN(NoHardUse, "noharduse", "only replace exit values when loop def likely dead"), clEnumValN(AlwaysRepl, "always", "always replace exit value whenever possible")))
static std::optional< uint64_t > getEstimatedTripCount(BranchInst *ExitingBranch, Loop *L, uint64_t &OrigExitWeight)
Return the estimated trip count for any exiting branch which dominates the loop latch.
static bool hasHardUserWithinLoop(const Loop *L, const Instruction *I)
static const char * LLVMLoopDisableLICM
static bool canLoopBeDeleted(Loop *L, SmallVector< RewritePhi, 8 > &RewritePhiSet)
static const char * LLVMLoopDisableNonforced
static MDNode * createStringMetadata(Loop *TheLoop, StringRef Name, unsigned V)
Create MDNode for input string.
static BranchInst * getExpectedExitLoopLatchBranch(Loop *L)
Checks if L has an exiting latch branch.
static bool checkIsIndPhi(PHINode *Phi, Loop *L, ScalarEvolution *SE, InductionDescriptor &ID)
Checks if it is safe to call InductionDescriptor::isInductionPHI for Phi, and returns true if this Ph...
static PointerBounds expandBounds(const RuntimeCheckingPtrGroup *CG, Loop *TheLoop, Instruction *Loc, SCEVExpander &Exp)
Expand code for the lower and upper bound of the pointer group CG in TheLoop.
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
Module.h This file contains the declarations for the Module class.
#define INITIALIZE_PASS_DEPENDENCY(depName)
This file provides a priority worklist.
This file contains the declarations for profiling metadata utility functions.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This is the interface for a SCEV-based alias analysis.
This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...
This file implements a set that has insertion order iteration characteristics.
static cl::opt< unsigned > MSSAThreshold("simple-loop-unswitch-memoryssa-threshold", cl::desc("Max number of memory uses to explore during " "partial unswitching analysis"), cl::init(100), cl::Hidden)
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
Virtual Register Rewriter
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
Check whether or not an instruction may read or write the optionally specified memory location.
Class for arbitrary precision integers.
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequiredID(const void *ID)
AnalysisUsage & addPreservedID(const void *ID)
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Legacy wrapper pass to provide the BasicAAResult object.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
InstListType::iterator iterator
Instruction iterators...
LLVMContext & getContext() const
Get the context in which this basic block lives.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Conditional or Unconditional Branch instruction.
unsigned getNumSuccessors() const
BasicBlock * getSuccessor(unsigned i) const
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ FCMP_OLT
0 1 0 0 True if ordered and less than
@ FCMP_OGT
0 0 1 0 True if ordered and greater than
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
static Constant * get(Type *Ty, double V)
This returns a ConstantFP, or a vector containing a splat of a ConstantFP, for the specified value in...
static Constant * getNegativeZero(Type *Ty)
This is the shared class of boolean and integer constants.
static ConstantInt * getTrue(LLVMContext &Context)
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
static ConstantInt * getFalse(LLVMContext &Context)
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
Identifies a unique instance of a variable.
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
static constexpr ElementCount get(ScalarTy MinVal, bool Scalable)
Legacy wrapper pass to provide the GlobalsAAResult object.
Common base class shared among various IRBuilders.
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
A struct for saving information about induction variables.
static bool isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D, const SCEV *Expr=nullptr, SmallVectorImpl< Instruction * > *CastsToIgnore=nullptr)
Returns true if Phi is an induction in the loop L.
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
const BasicBlock * getParent() const
bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
This is an important class for using LLVM in a threaded context.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
BlockT * getHeader() const
const LoopT * getOutermostLoop() const
Get the outermost loop in which this loop is contained.
std::vector< Loop * >::const_iterator iterator
iterator_range< block_iterator > blocks() const
block_iterator block_end() const
bool hasNoExitBlocks() const
Return true if this loop does not have any exit blocks.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
void getUniqueExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
bool isLoopExiting(const BlockT *BB) const
True if terminator in the block can branch to another block that is outside of the current loop.
block_iterator block_begin() const
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
LoopT * AllocateLoop(ArgsTy &&... Args)
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 * 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.
bool isLCSSAForm(const DominatorTree &DT, bool IgnoreTokens=true) const
Return true if the Loop is in LCSSA form.
bool hasLoopInvariantOperands(const Instruction *I) const
Return true if all the operands of the specified instruction are loop invariant.
bool isRecursivelyLCSSAForm(const DominatorTree &DT, const LoopInfo &LI, bool IgnoreTokens=true) const
Return true if this Loop and all inner subloops are in LCSSA form.
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.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
bool insert(const T &X)
Insert a new element into the PriorityWorklist.
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
FastMathFlags getFastMathFlags() const
TrackingVH< Value > getRecurrenceStartValue() const
RecurKind getRecurrenceKind() const
static bool isMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is any min/max kind.
static bool isSelectCmpRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...
A global registry used in conjunction with static constructors to make pluggable components (like tar...
Legacy wrapper pass to provide the SCEVAAResult object.
This class uses information about analyze scalars to rewrite expressions in canonical form.
Value * expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I)
Insert code to directly compute the specified SCEV expression into the program.
This class represents an analyzed expression in the program.
Type * getType() const
Return the LLVM type of this SCEV expression.
The main scalar evolution driver.
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
const SCEV * getConstant(ConstantInt *V)
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
@ LoopInvariant
The SCEV is loop-invariant.
bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS.
This class represents the LLVM 'select' instruction.
Implements a dense probed hash-table based set with some number of buckets stored inline.
A version of PriorityWorklist that selects small size optimized data structures for the vector and ma...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
bool startswith(StringRef Prefix) const
bool equals(StringRef RHS) const
equals - Check for string equality, this is more efficient than compare() when the relative ordering ...
Provides information about what library functions are available for the current target.
Value handle that tracks a Value across RAUW.
The instances of the Type class are immutable: once they are created, they are never changed.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
static IntegerType * getInt32Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< use_iterator > uses()
std::pair< iterator, bool > insert(const ValueT &V)
An efficient, type-erasing, non-owning reference to a callable.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
std::optional< ElementCount > getOptionalElementCountLoopAttribute(const Loop *TheLoop)
Find a combination of metadata ("llvm.loop.vectorize.width" and "llvm.loop.vectorize....
SmallVector< DomTreeNode *, 16 > collectChildrenInLoop(DomTreeNode *N, const Loop *CurLoop)
Does a BFS from a given node to all of its children inside a given loop.
Interval::succ_iterator succ_end(Interval *I)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
std::optional< unsigned > getLoopEstimatedTripCount(Loop *L, unsigned *EstimatedLoopInvocationWeight=nullptr)
Returns a loop's estimated trip count based on branch weight metadata.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
bool getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name)
Returns true if Name is applied to TheLoop and enabled.
std::pair< const RuntimeCheckingPtrGroup *, const RuntimeCheckingPtrGroup * > RuntimePointerCheck
A memcheck which made up of a pair of grouped pointers.
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
Value * createSelectCmpOp(IRBuilderBase &Builder, Value *StartVal, RecurKind RK, Value *Left, Value *Right)
See RecurrenceDescriptor::isSelectCmpPattern for a description of the pattern we are trying to match.
std::optional< bool > getOptionalBoolLoopAttribute(const Loop *TheLoop, StringRef Name)
Value * createSimpleTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI, Value *Src, RecurKind RdxKind)
Create a target reduction of the given vector.
void appendReversedLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
auto successors(const MachineBasicBlock *BB)
Value * createTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI, const RecurrenceDescriptor &Desc, Value *Src, PHINode *OrigPhi=nullptr)
Create a generic target reduction using a recurrence descriptor Desc The target is queried to determi...
void initializeLoopPassPass(PassRegistry &)
Manually defined generic "LoopPass" dependency initialization.
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
std::optional< MDNode * > makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef< StringRef > FollowupAttrs, const char *InheritOptionsAttrsPrefix="", bool AlwaysNew=false)
Create a new loop identifier for a loop created from a loop transformation.
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
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...
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...
CmpInst::Predicate getMinMaxReductionPredicate(RecurKind RK)
Returns the comparison predicate used when expanding a min/max reduction.
TransformationMode hasLICMVersioningTransformation(const Loop *L)
bool VerifyMemorySSA
Enables verification of MemorySSA.
TransformationMode
The mode sets how eager a transformation should be applied.
@ TM_Unspecified
The pass can use heuristics to determine whether a transformation should be applied.
@ TM_SuppressedByUser
The transformation must not be applied.
@ TM_ForcedByUser
The transformation was directed by the user, e.g.
@ TM_Disable
The transformation should not be applied.
@ TM_Enable
The transformation should be applied without considering a cost model.
bool hasDisableLICMTransformsHint(const Loop *L)
Look for the loop attribute that disables the LICM transformation heuristics.
Value * addRuntimeChecks(Instruction *Loc, Loop *TheLoop, const SmallVectorImpl< RuntimePointerCheck > &PointerChecks, SCEVExpander &Expander)
Add code that checks at runtime if the accessed arrays in PointerChecks overlap.
RecurKind
These are the kinds of recurrences that we support.
bool setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount, unsigned EstimatedLoopInvocationWeight)
Set a loop's branch weight metadata to reflect that loop has EstimatedTripCount iterations and Estima...
void setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop, Loop *RemainderLoop, uint64_t UF)
Set weights for UnrolledLoop and RemainderLoop based on weights for OrigLoop and the following distri...
bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Ensure that all exit blocks of the loop are dedicated exits.
void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
bool isKnownNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)
Returns true if we can prove that S is defined and always negative in loop L.
Value * createSelectCmpTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI, Value *Src, const RecurrenceDescriptor &Desc, PHINode *OrigPhi)
Create a target reduction of the given vector Src for a reduction of the kind RecurKind::SelectICmp o...
constexpr unsigned BitWidth
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
bool hasIterationCountInvariantInParent(Loop *L, ScalarEvolution &SE)
Check inner loop (L) backedge count is known to be invariant on all iterations of its outer loop.
auto predecessors(const MachineBasicBlock *BB)
int rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI, ScalarEvolution *SE, const TargetTransformInfo *TTI, SCEVExpander &Rewriter, DominatorTree *DT, ReplaceExitVal ReplaceExitValue, SmallVector< WeakTrackingVH, 16 > &DeadInsts)
If the final value of any expressions that are recurrent in the loop can be computed,...
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Value * addDiffRuntimeChecks(Instruction *Loc, ArrayRef< PointerDiffInfo > Checks, SCEVExpander &Expander, function_ref< Value *(IRBuilderBase &, unsigned)> GetVF, unsigned IC)
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
std::optional< IVConditionInfo > hasPartialIVCondition(const Loop &L, unsigned MSSAThreshold, const MemorySSA &MSSA, AAResults &AA)
Check if the loop header has a conditional branch that is not loop-invariant, because it involves loa...
bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, bool Signed)
Returns true if S is defined and never is equal to signed/unsigned min.
bool isKnownNonNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)
Returns true if we can prove that S is defined and always non-negative in loop L.
Value * getOrderedReduction(IRBuilderBase &Builder, Value *Acc, Value *Src, unsigned Op, RecurKind MinMaxKind=RecurKind::None)
Generates an ordered vector reduction using extracts to reduce the value.
MDNode * findOptionMDForLoopID(MDNode *LoopID, StringRef Name)
Find and return the loop attribute node for the attribute Name in LoopID.
Loop * cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, LoopInfo *LI, LPPassManager *LPM)
Recursively clone the specified loop and all of its children, mapping the blocks with the specified m...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
IR Values for the lower and upper bounds of a pointer evolution.
TrackingVH< Value > Start
RewritePhi(PHINode *P, unsigned I, const SCEV *Val, Instruction *ExpansionPt, bool H)
const SCEV * ExpansionSCEV
Instruction * ExpansionPoint
Struct to hold information about a partially invariant condition.
unsigned AddressSpace
Address space of the involved pointers.
bool NeedsFreeze
Whether the pointer needs to be frozen after expansion, e.g.
const SCEV * High
The SCEV expression which represents the upper bound of all the pointers in this group.
const SCEV * Low
The SCEV expression which represents the lower bound of all the pointers in this group.