94#define DEBUG_TYPE "licm"
96STATISTIC(NumCreatedBlocks,
"Number of blocks created");
97STATISTIC(NumClonedBranches,
"Number of branches cloned");
98STATISTIC(NumSunk,
"Number of instructions sunk out of loop");
99STATISTIC(NumHoisted,
"Number of instructions hoisted out of loop");
100STATISTIC(NumMovedLoads,
"Number of load insts hoisted or sunk");
101STATISTIC(NumMovedCalls,
"Number of call insts hoisted or sunk");
102STATISTIC(NumPromotionCandidates,
"Number of promotion candidates");
103STATISTIC(NumLoadPromoted,
"Number of load-only promotions");
104STATISTIC(NumLoadStorePromoted,
"Number of load and store promotions");
109 cl::desc(
"Disable memory promotion in LICM pass"));
113 cl::desc(
"Enable control flow (and PHI) hoisting in LICM"));
117 cl::desc(
"Force thread model single in LICM pass"));
121 cl::desc(
"Max num uses visited for identifying load "
122 "invariance in loop using invariant start (default = 8)"));
134 cl::desc(
"Enable imprecision in LICM in pathological cases, in exchange "
135 "for faster compile. Caps the MemorySSA clobbering calls."));
142 cl::desc(
"[LICM & MemorySSA] When MSSA in LICM is disabled, this has no "
143 "effect. When MSSA in LICM is enabled, then this is the maximum "
144 "number of accesses allowed to be present in a loop in order to "
145 "enable memory promotion."));
183 std::pair<SmallSetVector<Value *, 8>,
bool>;
188struct LoopInvariantCodeMotion {
194 LoopInvariantCodeMotion(
unsigned LicmMssaOptCap,
195 unsigned LicmMssaNoAccForPromotionCap,
196 bool LicmAllowSpeculation)
197 : LicmMssaOptCap(LicmMssaOptCap),
198 LicmMssaNoAccForPromotionCap(LicmMssaNoAccForPromotionCap),
199 LicmAllowSpeculation(LicmAllowSpeculation) {}
202 unsigned LicmMssaOptCap;
203 unsigned LicmMssaNoAccForPromotionCap;
204 bool LicmAllowSpeculation;
207struct LegacyLICMPass :
public LoopPass {
212 bool LicmAllowSpeculation =
true)
213 :
LoopPass(
ID),
LICM(LicmMssaOptCap, LicmMssaNoAccForPromotionCap,
214 LicmAllowSpeculation) {
227 auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
228 MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
233 return LICM.runOnLoop(
234 L, &getAnalysis<AAResultsWrapperPass>().getAAResults(),
235 &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
236 &getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
237 &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(*
F),
238 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(*
F),
239 &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(*
F),
240 SE ? &SE->getSE() :
nullptr, MSSA, &ORE);
261 LoopInvariantCodeMotion
LICM;
294 OS, MapClassName2PassName);
317 bool Changed =
LICM.runOnLoop(&OutermostLoop, &AR.
AA, &AR.
LI, &AR.
DT, &AR.
AC,
335 OS, MapClassName2PassName);
342char LegacyLICMPass::ID = 0;
355 unsigned LicmMssaNoAccForPromotionCap,
356 bool LicmAllowSpeculation) {
357 return new LegacyLICMPass(LicmMssaOptCap, LicmMssaNoAccForPromotionCap,
358 LicmAllowSpeculation);
367 unsigned LicmMssaOptCap,
unsigned LicmMssaNoAccForPromotionCap,
bool IsSink,
369 : LicmMssaOptCap(LicmMssaOptCap),
370 LicmMssaNoAccForPromotionCap(LicmMssaNoAccForPromotionCap),
372 assert(((L !=
nullptr) == (MSSA !=
nullptr)) &&
373 "Unexpected values for SinkAndHoistLICMFlags");
377 unsigned AccessCapCount = 0;
380 for (
const auto &MA : *Accesses) {
400 bool Changed =
false;
421 return llvm::any_of(*BB, [](Instruction &I) {
422 IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I);
423 return II && II->getIntrinsicID() == Intrinsic::coro_suspend;
451 TLI,
TTI, L, MSSAU, &SafetyInfo, Flags, ORE)
452 :
sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI,
TTI, L,
453 MSSAU, &SafetyInfo,
Flags, ORE);
454 Flags.setIsSink(
false);
457 MSSAU, SE, &SafetyInfo, Flags, ORE, LoopNestMode,
458 LicmAllowSpeculation);
468 !
Flags.tooManyMemoryAccesses() && !HasCoroSuspendInst) {
478 if (!HasCatchSwitch) {
484 InsertPts.
push_back(&*ExitBlock->getFirstInsertionPt());
492 bool Promoted =
false;
495 LocalPromoted =
false;
496 for (
auto [PointerMustAliases, HasReadsOutsideSet] :
499 PointerMustAliases, ExitBlocks, InsertPts, MSSAInsertPts,
PIC, LI,
500 DT, AC, TLI,
TTI, L, MSSAU, &SafetyInfo, ORE,
501 LicmAllowSpeculation, HasReadsOutsideSet);
503 Promoted |= LocalPromoted;
504 }
while (LocalPromoted);
524 "Parent loop not left in LCSSA form after LICM!");
547 assert(
N !=
nullptr && AA !=
nullptr && LI !=
nullptr && DT !=
nullptr &&
548 CurLoop !=
nullptr && SafetyInfo !=
nullptr &&
549 "Unexpected input to sinkRegion.");
556 bool Changed =
false;
584 bool FreeInLoop =
false;
585 bool LoopNestMode = OutermostLoop !=
nullptr;
586 if (!
I.mayHaveSideEffects() &&
588 SafetyInfo,
TTI, FreeInLoop, LoopNestMode) &&
590 if (
sink(
I, LI, DT, CurLoop, SafetyInfo, MSSAU, ORE)) {
614 bool Changed =
false;
618 while (!Worklist.
empty()) {
621 MSSAU, SafetyInfo, Flags, ORE, CurLoop);
634class ControlFlowHoister {
653 : LI(LI), DT(DT), CurLoop(CurLoop), MSSAU(MSSAU) {}
655 void registerPossiblyHoistableBranch(
BranchInst *BI) {
667 TrueDest == FalseDest)
679 if (TrueDestSucc.
count(FalseDest)) {
680 CommonSucc = FalseDest;
681 }
else if (FalseDestSucc.
count(TrueDest)) {
682 CommonSucc = TrueDest;
686 if (TrueDestSucc.
size() == 1)
687 CommonSucc = *TrueDestSucc.
begin();
691 else if (!TrueDestSucc.
empty()) {
695 assert(It !=
F->end() &&
"Could not find successor in function");
707 if (CommonSucc && DT->
dominates(BI, CommonSucc))
708 HoistableBranches[BI] = CommonSucc;
711 bool canHoistPHI(
PHINode *PN) {
720 PredecessorBlocks.
insert(PredBB);
728 for (
auto &Pair : HoistableBranches) {
729 if (Pair.second == BB) {
732 if (Pair.first->getSuccessor(0) == BB) {
733 PredecessorBlocks.
erase(Pair.first->getParent());
734 PredecessorBlocks.
erase(Pair.first->getSuccessor(1));
735 }
else if (Pair.first->getSuccessor(1) == BB) {
736 PredecessorBlocks.
erase(Pair.first->getParent());
737 PredecessorBlocks.
erase(Pair.first->getSuccessor(0));
739 PredecessorBlocks.
erase(Pair.first->getSuccessor(0));
740 PredecessorBlocks.
erase(Pair.first->getSuccessor(1));
746 return PredecessorBlocks.
empty();
753 if (HoistDestinationMap.
count(BB))
754 return HoistDestinationMap[BB];
757 auto HasBBAsSuccessor =
759 return BB != Pair.second && (Pair.first->getSuccessor(0) == BB ||
760 Pair.first->getSuccessor(1) == BB);
762 auto It =
llvm::find_if(HoistableBranches, HasBBAsSuccessor);
766 if (It == HoistableBranches.end()) {
769 <<
" as hoist destination for "
771 HoistDestinationMap[BB] = InitialPreheader;
772 return InitialPreheader;
775 assert(std::find_if(++It, HoistableBranches.end(), HasBBAsSuccessor) ==
776 HoistableBranches.end() &&
777 "BB is expected to be the target of at most one branch");
782 BasicBlock *CommonSucc = HoistableBranches[BI];
786 auto CreateHoistedBlock = [&](
BasicBlock *Orig) {
787 if (HoistDestinationMap.
count(Orig))
788 return HoistDestinationMap[Orig];
791 HoistDestinationMap[Orig] =
New;
797 <<
" as hoist destination for " << Orig->getName()
801 BasicBlock *HoistTrueDest = CreateHoistedBlock(TrueDest);
802 BasicBlock *HoistFalseDest = CreateHoistedBlock(FalseDest);
803 BasicBlock *HoistCommonSucc = CreateHoistedBlock(CommonSucc);
810 assert(TargetSucc &&
"Expected hoist target to have a single successor");
825 if (HoistTarget == InitialPreheader) {
836 for (
auto &Pair : HoistDestinationMap)
837 if (Pair.second == InitialPreheader && Pair.first != BI->
getParent())
838 Pair.second = HoistCommonSucc;
848 "Hoisting blocks should not have destroyed preheader");
849 return HoistDestinationMap[BB];
866 bool AllowSpeculation) {
868 assert(
N !=
nullptr && AA !=
nullptr && LI !=
nullptr && DT !=
nullptr &&
869 CurLoop !=
nullptr && SafetyInfo !=
nullptr &&
870 "Unexpected input to hoistRegion.");
872 ControlFlowHoister CFH(LI, DT, CurLoop, MSSAU);
883 bool Changed =
false;
887 if (!LoopNestMode &&
inSubLoop(BB, CurLoop, LI))
895 &
I,
I.getModule()->getDataLayout(), TLI)) {
899 I.replaceAllUsesWith(
C);
916 I, DT, TLI, CurLoop, SafetyInfo, ORE,
919 hoist(
I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
928 if (
I.getOpcode() == Instruction::FDiv &&
I.hasAllowReciprocal() &&
930 auto Divisor =
I.getOperand(1);
932 auto ReciprocalDivisor = BinaryOperator::CreateFDiv(One, Divisor);
933 ReciprocalDivisor->setFastMathFlags(
I.getFastMathFlags());
935 ReciprocalDivisor->insertBefore(&
I);
938 BinaryOperator::CreateFMul(
I.getOperand(0), ReciprocalDivisor);
939 Product->setFastMathFlags(
I.getFastMathFlags());
941 Product->insertAfter(&
I);
942 I.replaceAllUsesWith(Product);
945 hoist(*ReciprocalDivisor, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB),
946 SafetyInfo, MSSAU, SE, ORE);
947 HoistedInstructions.
push_back(ReciprocalDivisor);
953 using namespace PatternMatch;
954 return I.use_empty() &&
955 match(&
I, m_Intrinsic<Intrinsic::invariant_start>());
957 auto MustExecuteWithoutWritesBefore = [&](
Instruction &
I) {
961 if ((IsInvariantStart(
I) ||
isGuard(&
I)) &&
963 MustExecuteWithoutWritesBefore(
I)) {
964 hoist(
I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
971 if (
PHINode *PN = dyn_cast<PHINode>(&
I)) {
972 if (CFH.canHoistPHI(PN)) {
978 hoist(*PN, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
989 CFH.registerPossiblyHoistableBranch(BI);
1004 [&](
Use &U) { return DT->dominates(I, U); })) {
1010 "New hoist point expected to dominate old hoist point");
1015 <<
": " << *
I <<
"\n");
1027#ifdef EXPENSIVE_CHECKS
1029 assert(DT->
verify(DominatorTree::VerificationLevel::Fast) &&
1030 "Dominator tree verification failed");
1064 unsigned BitcastsVisited = 0;
1067 while (
Addr->getType() != PtrInt8Ty) {
1068 auto *BC = dyn_cast<BitCastInst>(
Addr);
1072 Addr = BC->getOperand(0);
1076 if (isa<Constant>(
Addr))
1079 unsigned UsesVisited = 0;
1082 for (
auto *U :
Addr->users()) {
1116 return (isa<LoadInst>(
I) || isa<StoreInst>(
I) || isa<CallInst>(
I) ||
1117 isa<FenceInst>(
I) || isa<CastInst>(
I) || isa<UnaryOperator>(
I) ||
1118 isa<BinaryOperator>(
I) || isa<SelectInst>(
I) ||
1119 isa<GetElementPtrInst>(
I) || isa<CmpInst>(
I) ||
1120 isa<InsertElementInst>(
I) || isa<ExtractElementInst>(
I) ||
1121 isa<ShuffleVectorInst>(
I) || isa<ExtractValueInst>(
I) ||
1122 isa<InsertValueInst>(
I) || isa<FreezeInst>(
I));
1138 for (
const auto &Acc : *Accs) {
1139 if (isa<MemoryPhi>(&Acc))
1141 const auto *MUD = cast<MemoryUseOrDef>(&Acc);
1142 if (MUD->getMemoryInst() !=
I || NotAPhi++ == 1)
1152 bool TargetExecutesOncePerLoop,
1156 if (!isHoistableAndSinkableInst(
I))
1161 if (
LoadInst *LI = dyn_cast<LoadInst>(&
I)) {
1162 if (!LI->isUnordered())
1169 if (LI->hasMetadata(LLVMContext::MD_invariant_load))
1172 if (LI->isAtomic() && !TargetExecutesOncePerLoop)
1183 if (ORE && Invalidated && CurLoop->
isLoopInvariant(LI->getPointerOperand()))
1186 DEBUG_TYPE,
"LoadWithLoopInvariantAddressInvalidated", LI)
1187 <<
"failed to move load with loop-invariant address "
1188 "because the loop may invalidate its value";
1191 return !Invalidated;
1192 }
else if (
CallInst *CI = dyn_cast<CallInst>(&
I)) {
1194 if (isa<DbgInfoIntrinsic>(
I))
1205 if (CI->isConvergent())
1208 using namespace PatternMatch;
1209 if (
match(CI, m_Intrinsic<Intrinsic::assume>()))
1213 if (
match(CI, m_Intrinsic<Intrinsic::experimental_widenable_condition>()))
1227 for (
Value *Op : CI->args())
1228 if (Op->getType()->isPointerTy() &&
1238 if (isReadOnly(MSSAU, CurLoop))
1246 }
else if (
auto *FI = dyn_cast<FenceInst>(&
I)) {
1249 return isOnlyMemoryAccess(FI, CurLoop, MSSAU);
1250 }
else if (
auto *
SI = dyn_cast<StoreInst>(&
I)) {
1251 if (!
SI->isUnordered())
1259 if (isOnlyMemoryAccess(
SI, CurLoop, MSSAU))
1263 if (Flags.tooManyMemoryAccesses() || Flags.tooManyClobberingCalls())
1273 for (
const auto &MA : *Accesses)
1274 if (
const auto *MU = dyn_cast<MemoryUse>(&MA)) {
1283 if (!Flags.getIsSink() && !MSSA->
dominates(SIMD, MU))
1285 }
else if (
const auto *MD = dyn_cast<MemoryDef>(&MA)) {
1286 if (
auto *LI = dyn_cast<LoadInst>(MD->getMemoryInst())) {
1288 assert(!LI->isUnordered() &&
"Expected unordered load");
1292 if (
auto *CI = dyn_cast<CallInst>(MD->getMemoryInst())) {
1303 Flags.incrementClobberingCalls();
1306 !CurLoop->
contains(Source->getBlock());
1309 assert(!
I.mayReadOrWriteMemory() &&
"unhandled aliasing");
1335 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(&
I)) {
1342 for (
const User *U :
GEP->users()) {
1346 (!isa<StoreInst>(UI) && !isa<LoadInst>(UI))))
1364 bool LoopNestMode) {
1367 for (
const User *U :
I.users()) {
1369 if (
const PHINode *PN = dyn_cast<PHINode>(UI)) {
1377 if (isa<CallInst>(
I))
1378 if (!BlockColors.empty() &&
1379 BlockColors.find(
const_cast<BasicBlock *
>(BB))->second.size() != 1)
1383 while (isa<PHINode>(UI) && UI->
hasOneUser() &&
1387 UI = cast<Instruction>(UI->
user_back());
1407 if (
auto *CI = dyn_cast<CallInst>(&
I)) {
1414 for (
unsigned BundleIdx = 0, BundleEnd = CI->getNumOperandBundles();
1415 BundleIdx != BundleEnd; ++BundleIdx) {
1423 if (!BlockColors.empty()) {
1424 const ColorVector &CV = BlockColors.find(&ExitBlock)->second;
1425 assert(CV.
size() == 1 &&
"non-unique color for exit block!");
1438 if (!
I.getName().empty())
1439 New->setName(
I.getName() +
".le");
1446 if (
auto *MemDef = dyn_cast<MemoryDef>(NewMemAcc))
1449 auto *MemUse = cast<MemoryUse>(NewMemAcc);
1462 for (
Use &Op : New->operands())
1464 auto *OInst = cast<Instruction>(Op.get());
1467 OInst->getName() +
".lcssa", &ExitBlock.
front());
1479 I.eraseFromParent();
1488 I.moveBefore(&Dest);
1502 "Expect only trivially replaceable PHI");
1505 auto It = SunkCopies.
find(ExitBlock);
1506 if (It != SunkCopies.
end())
1510 *
I, *ExitBlock, *TPN, LI, SafetyInfo, MSSAU);
1525 if (isa<IndirectBrInst>(BBPred->getTerminator()))
1542 assert(ExitBlockSet.
count(ExitBB) &&
"Expect the PHI is in an exit block.");
1578 while (!PredBBs.
empty()) {
1581 "Expect all predecessors are in the loop");
1584 ExitBB, PredBB,
".split.loop.exit", DT, LI, MSSAU,
true);
1588 if (!BlockColors.empty())
1606 bool Changed =
false;
1613 auto *
User = cast<Instruction>(*UI);
1614 Use &U = UI.getUse();
1652 UI =
I.user_begin();
1656 if (VisitedUsers.
empty())
1661 <<
"sinking " <<
ore::NV(
"Inst", &
I);
1663 if (isa<LoadInst>(
I))
1665 else if (isa<CallInst>(
I))
1685 for (
auto *UI :
Users) {
1686 auto *
User = cast<Instruction>(UI);
1693 "The LCSSA PHI is not in an exit block!");
1697 PN, &
I, LI, SunkCopies, SafetyInfo, CurLoop, MSSAU);
1727 if ((
I.hasMetadataOtherThanDebugLoc() || isa<CallInst>(
I)) &&
1732 I.dropUndefImplyingAttrsAndUnknownMetadata();
1734 if (isa<PHINode>(
I))
1741 I.updateLocationAfterHoist();
1743 if (isa<LoadInst>(
I))
1745 else if (isa<CallInst>(
I))
1758 if (AllowSpeculation &&
1762 bool GuaranteedToExecute =
1765 if (!GuaranteedToExecute) {
1766 auto *LI = dyn_cast<LoadInst>(&Inst);
1770 DEBUG_TYPE,
"LoadWithLoopInvariantAddressCondExecuted", LI)
1771 <<
"failed to hoist load with loop-invariant address "
1772 "because load is conditionally executed";
1776 return GuaranteedToExecute;
1790 bool UnorderedAtomic;
1793 bool CanInsertStoresInExitBlocks;
1807 I->getName() +
".lcssa", &BB->
front());
1822 LoopInsertPts(LIP), MSSAInsertPts(MSSAIP), PredCache(
PIC), MSSAU(MSSAU),
1823 LI(li),
DL(
std::
move(dl)), Alignment(Alignment),
1824 UnorderedAtomic(UnorderedAtomic), AATags(AATags),
1825 SafetyInfo(SafetyInfo),
1826 CanInsertStoresInExitBlocks(CanInsertStoresInExitBlocks),
Uses(Insts) {}
1828 void insertStoresInLoopExitBlocks() {
1834 for (
unsigned i = 0, e = LoopExitBlocks.
size(); i != e; ++i) {
1836 Value *LiveInValue =
SSA.GetValueInMiddleOfBlock(ExitBlock);
1837 LiveInValue = maybeInsertLCSSAPHI(LiveInValue, ExitBlock);
1838 Value *
Ptr = maybeInsertLCSSAPHI(SomePtr, ExitBlock);
1841 if (UnorderedAtomic)
1852 NewID = cast_or_null<DIAssignID>(
1857 NewSI->
setMetadata(LLVMContext::MD_DIAssignID, NewID);
1865 if (!MSSAInsertPoint) {
1872 MSSAInsertPts[i] = NewMemAcc;
1873 MSSAU.
insertDef(cast<MemoryDef>(NewMemAcc),
true);
1878 void doExtraRewritesBeforeFinalDeletion()
override {
1879 if (CanInsertStoresInExitBlocks)
1880 insertStoresInLoopExitBlocks();
1883 void instructionDeleted(
Instruction *
I)
const override {
1889 if (isa<StoreInst>(
I))
1890 return CanInsertStoresInExitBlocks;
1895bool isNotCapturedBeforeOrInLoop(
const Value *V,
const Loop *L,
1910 bool RequiresNoCaptureBeforeUnwind;
1914 return !RequiresNoCaptureBeforeUnwind ||
1915 isNotCapturedBeforeOrInLoop(
Object, L, DT);
1921 if (isa<AllocaInst>(
Object))
1925 if (
auto *
A = dyn_cast<Argument>(
Object))
1926 return A->hasByValAttr();
1928 if (
auto *
G = dyn_cast<GlobalVariable>(
Object))
1929 return !
G->isConstant();
1941 isNotCapturedBeforeOrInLoop(
Object, L, DT)) ||
1961 bool HasReadsOutsideSet) {
1963 assert(LI !=
nullptr && DT !=
nullptr && CurLoop !=
nullptr &&
1964 SafetyInfo !=
nullptr &&
1965 "Unexpected Input to promoteLoopAccessesToScalars");
1968 dbgs() <<
"Trying to promote set of must-aliased pointers:\n";
1969 for (
Value *
Ptr : PointerMustAliases)
1970 dbgs() <<
" " << *
Ptr <<
"\n";
1972 ++NumPromotionCandidates;
1974 Value *SomePtr = *PointerMustAliases.
begin();
2014 bool DereferenceableInPH =
false;
2015 bool StoreIsGuanteedToExecute =
false;
2016 bool FoundLoadToPromote =
false;
2022 } StoreSafety = StoreSafetyUnknown;
2030 bool SawUnorderedAtomic =
false;
2031 bool SawNotAtomic =
false;
2038 if (HasReadsOutsideSet)
2039 StoreSafety = StoreUnsafe;
2048 if (!isNotVisibleOnUnwindInLoop(
Object, CurLoop, DT))
2049 StoreSafety = StoreUnsafe;
2055 Type *AccessTy =
nullptr;
2056 for (
Value *ASIV : PointerMustAliases) {
2059 Instruction *UI = dyn_cast<Instruction>(U.getUser());
2065 if (
LoadInst *Load = dyn_cast<LoadInst>(UI)) {
2066 if (!Load->isUnordered())
2069 SawUnorderedAtomic |= Load->isAtomic();
2070 SawNotAtomic |= !Load->isAtomic();
2071 FoundLoadToPromote =
true;
2073 Align InstAlignment = Load->getAlign();
2079 if (!DereferenceableInPH || (InstAlignment > Alignment))
2081 *Load, DT, TLI, CurLoop, SafetyInfo, ORE,
2083 DereferenceableInPH =
true;
2084 Alignment = std::max(Alignment, InstAlignment);
2086 }
else if (
const StoreInst *Store = dyn_cast<StoreInst>(UI)) {
2091 if (!Store->isUnordered())
2094 SawUnorderedAtomic |= Store->isAtomic();
2095 SawNotAtomic |= !Store->isAtomic();
2102 Align InstAlignment = Store->getAlign();
2103 bool GuaranteedToExecute =
2105 StoreIsGuanteedToExecute |= GuaranteedToExecute;
2106 if (GuaranteedToExecute) {
2107 DereferenceableInPH =
true;
2108 if (StoreSafety == StoreSafetyUnknown)
2109 StoreSafety = StoreSafe;
2110 Alignment = std::max(Alignment, InstAlignment);
2119 if (StoreSafety == StoreSafetyUnknown &&
2121 return DT->
dominates(Store->getParent(), Exit);
2123 StoreSafety = StoreSafe;
2127 if (!DereferenceableInPH) {
2129 Store->getPointerOperand(), Store->getValueOperand()->getType(),
2130 Store->getAlign(), MDL, Preheader->
getTerminator(), AC, DT, TLI);
2141 if (LoopUses.
empty()) {
2144 }
else if (AATags) {
2156 if (SawUnorderedAtomic && SawNotAtomic)
2166 if (!DereferenceableInPH) {
2167 LLVM_DEBUG(
dbgs() <<
"Not promoting: Not dereferenceable in preheader\n");
2175 if (StoreSafety == StoreSafetyUnknown) {
2177 if (isWritableObject(
Object) &&
2178 isThreadLocalObject(
Object, CurLoop, DT,
TTI))
2179 StoreSafety = StoreSafe;
2184 if (StoreSafety != StoreSafe && !FoundLoadToPromote)
2189 if (StoreSafety == StoreSafe) {
2190 LLVM_DEBUG(
dbgs() <<
"LICM: Promoting load/store of the value: " << *SomePtr
2192 ++NumLoadStorePromoted;
2194 LLVM_DEBUG(
dbgs() <<
"LICM: Promoting load of the value: " << *SomePtr
2202 <<
"Moving accesses to memory location out of the loop";
2206 std::vector<const DILocation *> LoopUsesLocs;
2207 for (
auto *U : LoopUses)
2208 LoopUsesLocs.push_back(U->getDebugLoc().get());
2214 LoopPromoter Promoter(SomePtr, LoopUses,
SSA, ExitBlocks, InsertPts,
2215 MSSAInsertPts,
PIC, MSSAU, *LI,
DL, Alignment,
2216 SawUnorderedAtomic, AATags, *SafetyInfo,
2217 StoreSafety == StoreSafe);
2222 if (FoundLoadToPromote || !StoreIsGuanteedToExecute) {
2226 if (SawUnorderedAtomic)
2235 MemoryUse *NewMemUse = cast<MemoryUse>(PreheaderLoadMemoryAccess);
2237 SSA.AddAvailableValue(Preheader, PreheaderLoad);
2246 Promoter.run(LoopUses);
2251 if (PreheaderLoad && PreheaderLoad->
use_empty())
2261 for (
const auto &Access : *Accesses)
2262 if (
const auto *MUD = dyn_cast<MemoryUseOrDef>(&Access))
2263 Fn(MUD->getMemoryInst());
2273 auto IsPotentiallyPromotable = [L](
const Instruction *
I) {
2274 if (
const auto *
SI = dyn_cast<StoreInst>(
I))
2276 if (
const auto *LI = dyn_cast<LoadInst>(
I))
2284 if (IsPotentiallyPromotable(
I)) {
2285 AttemptingPromotion.
insert(
I);
2293 if (!AS.isForwardingAliasSet() && AS.isMod() && AS.isMustAlias())
2305 ModRefInfo MR = Pair.getPointer()->aliasesUnknownInst(I, BatchAA);
2314 return !Pair.getPointer()->isRef();
2321 for (
auto [Set, HasReadsOutsideSet] : Sets) {
2323 for (
const auto &ASI : *Set)
2324 PointerMustAliases.
insert(ASI.getValue());
2325 Result.emplace_back(std::move(PointerMustAliases), HasReadsOutsideSet);
2335 if (!Flags.getIsSink()) {
2338 if (Flags.tooManyClobberingCalls())
2342 Flags.incrementClobberingCalls();
2345 CurLoop->
contains(Source->getBlock());
2365 if (Flags.tooManyMemoryAccesses())
2379 for (
const auto &MA : *Accesses)
2380 if (
const auto *MD = dyn_cast<MemoryDef>(&MA))
2390 assert(CurLoop->
contains(BB) &&
"Only valid if BB is IN the loop");
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
SmallPtrSet< MachineInstr *, 2 > Uses
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
gvn hoist
When an instruction is found to only use loop invariant operands that is safe to hoist,...
gvn sink
When an instruction is found to only be used outside of the loop, this function moves it to the exit ...
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
iv Induction Variable Users
static cl::opt< bool > SingleThread("licm-force-thread-model-single", cl::Hidden, cl::init(false), cl::desc("Force thread model single in LICM pass"))
static bool pointerInvalidatedByLoop(MemorySSA *MSSA, MemoryUse *MU, Loop *CurLoop, Instruction &I, SinkAndHoistLICMFlags &Flags)
static void splitPredecessorsOfLoopExit(PHINode *PN, DominatorTree *DT, LoopInfo *LI, const Loop *CurLoop, LoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU)
static bool isNotUsedOrFreeInLoop(const Instruction &I, const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo, TargetTransformInfo *TTI, bool &FreeInLoop, bool LoopNestMode)
Return true if the only users of this instruction are outside of the loop.
static Instruction * cloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI, const LoopSafetyInfo *SafetyInfo, MemorySSAUpdater &MSSAU)
static cl::opt< bool > ControlFlowHoisting("licm-control-flow-hoisting", cl::Hidden, cl::init(false), cl::desc("Enable control flow (and PHI) hoisting in LICM"))
static SmallVector< PointersAndHasReadsOutsideSet, 0 > collectPromotionCandidates(MemorySSA *MSSA, AliasAnalysis *AA, Loop *L)
static bool canSplitPredecessors(PHINode *PN, LoopSafetyInfo *SafetyInfo)
static void moveInstructionBefore(Instruction &I, Instruction &Dest, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU, ScalarEvolution *SE)
static cl::opt< uint32_t > MaxNumUsesTraversed("licm-max-num-uses-traversed", cl::Hidden, cl::init(8), cl::desc("Max num uses visited for identifying load " "invariance in loop using invariant start (default = 8)"))
static void foreachMemoryAccess(MemorySSA *MSSA, Loop *L, function_ref< void(Instruction *)> Fn)
static bool isLoadInvariantInLoop(LoadInst *LI, DominatorTree *DT, Loop *CurLoop)
static Instruction * sinkThroughTriviallyReplaceablePHI(PHINode *TPN, Instruction *I, LoopInfo *LI, SmallDenseMap< BasicBlock *, Instruction *, 32 > &SunkCopies, const LoopSafetyInfo *SafetyInfo, const Loop *CurLoop, MemorySSAUpdater &MSSAU)
static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI)
Little predicate that returns true if the specified basic block is in a subloop of the current one,...
static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU)
static bool isSafeToExecuteUnconditionally(Instruction &Inst, const DominatorTree *DT, const TargetLibraryInfo *TLI, const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE, const Instruction *CtxI, AssumptionCache *AC, bool AllowSpeculation)
Only sink or hoist an instruction if it is not a trapping instruction, or if the instruction is known...
static bool isTriviallyReplaceablePHI(const PHINode &PN, const Instruction &I)
Returns true if a PHINode is a trivially replaceable with an Instruction.
std::pair< SmallSetVector< Value *, 8 >, bool > PointersAndHasReadsOutsideSet
static cl::opt< bool > DisablePromotion("disable-licm-promotion", cl::Hidden, cl::init(false), cl::desc("Disable memory promotion in LICM pass"))
Memory promotion is enabled by default.
static bool isFreeInLoop(const Instruction &I, const Loop *CurLoop, const TargetTransformInfo *TTI)
Return true if the instruction is free in the loop.
static bool pointerInvalidatedByBlock(BasicBlock &BB, MemorySSA &MSSA, MemoryUse &MU)
This file defines the interface for the loop nest analysis.
loop versioning Loop Versioning For LICM
Machine Loop Invariant Code Motion
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
Contains a collection of routines for determining if a given instruction is guaranteed to execute if ...
PassInstrumentationCallbacks PIC
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
This file provides a priority worklist.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines generic set operations that may be used on set's of different types,...
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
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.
ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, bool IgnoreLocals=false)
Returns a bitmask that should be unconditionally applied to the ModRef info of a memory location.
MemoryEffects getMemoryEffects(const CallBase *Call)
Return the behavior of the given call site.
void add(Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo)
These methods are used to add different types of instructions to the alias sets.
A container for analyses that lazily runs them and caches their results.
Represent the analysis usage information of a pass.
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),...
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
void replaceSuccessorsPhiUsesWith(BasicBlock *Old, BasicBlock *New)
Update all phi nodes in this basic block's successors to refer to basic block New instead of basic bl...
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...
void moveBefore(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it into the function that MovePos lives ...
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
const Instruction & front() const
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
const Function * getParent() const
Return the enclosing method, or null if none.
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...
bool canSplitPredecessors() const
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
Conditional or Unconditional Branch instruction.
bool isConditional() const
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
Value * getCondition() const
Value * getArgOperand(unsigned i) const
This class represents a function call, abstracting a target machine's calling convention.
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
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...
This is the shared class of boolean and integer constants.
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
This is an important base class in LLVM.
static const DILocation * getMergedLocations(ArrayRef< const DILocation * > Locs)
Try to combine the vector of locations passed as input in a single one.
A parsed version of the target data layout string in and methods for querying it.
TypeSize getTypeStoreSize(Type *Ty) const
Returns the maximum number of bytes that may be overwritten by storing the specified type.
iterator find(const_arg_type_t< KeyT > Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
DomTreeNodeBase * getIDom() const
Analysis pass which computes a DominatorTree.
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
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.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to give precise answers on "may...
bool doesNotWriteMemoryBefore(const BasicBlock *BB, const Loop *CurLoop) const
Returns true if we could not execute a memory-modifying instruction before we enter BB under assumpti...
void removeInstruction(const Instruction *Inst)
Inform safety info that we are planning to remove the instruction Inst from its block.
bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop) const override
Returns true if the instruction in a loop is guaranteed to execute at least once (under the assumptio...
bool anyBlockMayThrow() const override
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
void computeLoopSafetyInfo(const Loop *CurLoop) override
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB)
Inform the safety info that we are planning to insert a new instruction Inst into the basic block BB.
void mergeDIAssignID(ArrayRef< const Instruction * > SourceInstructions)
Merge the DIAssignID metadata from this instruction and those attached to instructions in SourceInstr...
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
void setAAMetadata(const AAMDNodes &N)
Sets the AA metadata on this instruction from the AAMDNodes structure.
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
const BasicBlock * getParent() const
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
A wrapper class for inspecting calls to intrinsic functions.
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
This is an important class for using LLVM in a threaded context.
PreservedAnalyses run(LoopNest &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
This is an alternative analysis pass to BlockFrequencyInfoWrapperPass.
static void getLazyBFIAnalysisUsage(AnalysisUsage &AU)
Helper for client passes to set up the analysis usage on behalf of this pass.
This is an alternative analysis pass to BranchProbabilityInfoWrapperPass.
An instruction for reading from memory.
unsigned getPointerAddressSpace() const
Returns the address space of the pointer operand.
void setAlignment(Align Align)
void setOrdering(AtomicOrdering Ordering)
Sets the ordering constraint of this load instruction.
Analysis pass that exposes the LoopInfo for a function.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
bool isOutermost() const
Return true if the loop does not have a parent (natural) loop.
BlockT * getHeader() const
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
iterator_range< block_iterator > blocks() const
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.
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
bool wouldBeOutOfLoopUseRequiringLCSSA(const Value *V, const BasicBlock *ExitBB) const
This class represents a loop nest and can be used to query its properties.
Function * getParent() const
Return the function to which the loop-nest belongs.
Loop & getOutermostLoop() const
Return the outermost loop in the loop nest.
Captures loop safety information.
void copyColors(BasicBlock *New, BasicBlock *Old)
Copy colors of block Old into the block New.
const DenseMap< BasicBlock *, ColorVector > & getBlockColors() const
Returns block colors map that is used to update funclet operand bundles.
virtual bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop) const =0
Returns true if the instruction in a loop is guaranteed to execute at least once (under the assumptio...
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 isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
BasicBlock * getBlock() const
Summary of how a function affects memory in the program.
bool onlyAccessesArgPointees() const
Whether this function only (at most) accesses argument memory.
bool onlyReadsMemory() const
Whether this function only (at most) reads memory.
bool doesNotAccessMemory() const
Whether this function accesses no memory.
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
An analysis that produces MemorySSA for a function.
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
void insertDef(MemoryDef *Def, bool RenameUses=false)
Insert a definition into the MemorySSA IR.
MemoryAccess * createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition, const BasicBlock *BB, MemorySSA::InsertionPlace Point)
Create a MemoryAccess in MemorySSA at a specified point in a block, with a specified clobbering defin...
void insertUse(MemoryUse *Use, bool RenameUses=false)
void removeMemoryAccess(MemoryAccess *, bool OptimizePhis=false)
Remove a MemoryAccess from MemorySSA, including updating all definitions and uses.
MemoryUseOrDef * createMemoryAccessAfter(Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt)
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
void wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New, ArrayRef< BasicBlock * > Preds, bool IdenticalEdgesWereMerged=true)
A new empty BasicBlock (New) now branches directly to Old.
MemoryAccess * getClobberingMemoryAccess(const Instruction *I, BatchAAResults &AA)
Given a memory Mod/Ref/ModRef'ing instruction, calling this will give you the nearest dominating Memo...
Legacy analysis pass which computes MemorySSA.
Encapsulates MemorySSA, including all data associated with memory accesses.
const AccessList * getBlockAccesses(const BasicBlock *BB) const
Return the list of MemoryAccess's for a given basic block.
MemorySSAWalker * getSkipSelfWalker()
bool dominates(const MemoryAccess *A, const MemoryAccess *B) const
Given two memory accesses in potentially different blocks, determine whether MemoryAccess A dominates...
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
void ensureOptimizedUses()
By default, uses are not optimized during MemorySSA construction.
const DefsList * getBlockDefs(const BasicBlock *BB) const
Return the list of MemoryDef's and MemoryPhi's for a given basic block.
bool locallyDominates(const MemoryAccess *A, const MemoryAccess *B) const
Given two memory accesses in the same basic block, determine whether MemoryAccess A dominates MemoryA...
bool isLiveOnEntryDef(const MemoryAccess *MA) const
Return true if MA represents the live on entry value.
Class that has the common methods + fields of memory uses/defs.
MemoryAccess * getDefiningAccess() const
Get the access that produces the memory state used by this Use.
Represents read-only accesses to memory.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
op_range incoming_values()
void setIncomingBlock(unsigned i, BasicBlock *BB)
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
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.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
PointerIntPair - This class implements a pair of a pointer and small integer.
static PointerType * get(Type *ElementType, unsigned AddressSpace)
This constructs a pointer to an object of the specified type in a numbered address space.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
PredIteratorCache - This class is an extremely trivial cache for predecessor iterator queries.
size_t size(BasicBlock *BB) const
ArrayRef< BasicBlock * > get(BasicBlock *BB)
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
bool empty() const
Determine if the PriorityWorklist is empty or not.
bool insert(const T &X)
Insert a new element into the PriorityWorklist.
Helper class for SSA formation on a set of values defined in multiple blocks.
The main scalar evolution driver.
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 forgetLoopDispositions()
Called when the client has changed the disposition of values in this loop.
bool remove(const value_type &X)
Remove an item from the set vector.
bool insert(const value_type &X)
Insert a new element into the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
iterator begin()
Get an iterator to the beginning of the SetVector.
Flags controlling how much is checked when sinking or hoisting instructions.
SinkAndHoistLICMFlags(unsigned LicmMssaOptCap, unsigned LicmMssaNoAccForPromotionCap, bool IsSink, Loop *L=nullptr, MemorySSA *MSSA=nullptr)
unsigned LicmMssaNoAccForPromotionCap
A version of PriorityWorklist that selects small size optimized data structures for the vector and ma...
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
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 reserve(size_type N)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
void setAlignment(Align Align)
void setOrdering(AtomicOrdering Ordering)
Sets the ordering constraint of this store instruction.
static unsigned getPointerOperandIndex()
StringRef - Represent a constant reference to a string, i.e.
Provides information about what library functions are available for the current target.
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
The instances of the Type class are immutable: once they are created, they are never changed.
static IntegerType * getInt8Ty(LLVMContext &C)
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
bool hasOneUser() const
Return true if there is exactly one user of this value.
std::string getNameOrAsOperand() const
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< use_iterator > uses()
user_iterator_impl< User > user_iterator
StringRef getName() const
Return a constant reference to the value's name.
constexpr ScalarTy getFixedValue() const
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
An efficient, type-erasing, non-owning reference to a callable.
This class implements an extremely fast bulk output stream that can only output to a stream.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
bool match(Val *V, const Pattern &P)
initializer< Ty > init(const Ty &Val)
DiagnosticInfoOptimizationBase::Argument NV
This is an optimization pass for GlobalISel generic memory operations.
void ReplaceInstWithInst(BasicBlock *BB, BasicBlock::iterator &BI, Instruction *I)
Replace the instruction specified by BI with the instruction specified by I.
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)
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 canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, Loop *CurLoop, MemorySSAUpdater &MSSAU, bool TargetExecutesOncePerLoop, SinkAndHoistLICMFlags &LICMFlags, OptimizationRemarkEmitter *ORE=nullptr)
Returns true if is legal to hoist or sink this instruction disregarding the possible introduction of ...
void set_intersect(S1Ty &S1, const S2Ty &S2)
set_intersect(A, B) - Compute A := A ^ B Identical to set_intersection, except that it works on set<>...
void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
void initializeLegacyLICMPassPass(PassRegistry &)
bool isDereferenceableAndAlignedPointer(const Value *V, Type *Ty, Align Alignment, const DataLayout &DL, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Returns true if V is always a dereferenceable pointer with alignment greater or equal than requested.
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, bool StoreCaptures, const Instruction *I, const DominatorTree *DT, bool IncludeI=false, unsigned MaxUsesToExplore=0, const LoopInfo *LI=nullptr)
PointerMayBeCapturedBefore - Return true if this pointer value may be captured by the enclosing funct...
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...
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
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...
bool isNoAliasCall(const Value *V)
Return true if this pointer is returned by a noalias function.
Interval::pred_iterator pred_end(Interval *I)
bool hoistRegion(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *, AssumptionCache *, TargetLibraryInfo *, Loop *, MemorySSAUpdater &, ScalarEvolution *, ICFLoopSafetyInfo *, SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *, bool, bool AllowSpeculation)
Walk the specified region of the CFG (defined by all blocks dominated by the specified block,...
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.
bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....
auto reverse(ContainerTy &&C)
bool isModSet(const ModRefInfo MRI)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
bool isModOrRefSet(const ModRefInfo MRI)
bool isNotVisibleOnUnwind(const Value *Object, bool &RequiresNoCaptureBeforeUnwind)
Return true if Object memory is not visible after an unwind, in the sense that program semantics cann...
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
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...
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
bool VerifyMemorySSA
Enables verification of MemorySSA.
void salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I.
bool hasDisableLICMTransformsHint(const Loop *L)
Look for the loop attribute that disables the LICM transformation heuristics.
Constant * ConstantFoldInstruction(Instruction *I, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstruction - Try to constant fold the specified instruction.
void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
bool promoteLoopAccessesToScalars(const SmallSetVector< Value *, 8 > &, SmallVectorImpl< BasicBlock * > &, SmallVectorImpl< Instruction * > &, SmallVectorImpl< MemoryAccess * > &, PredIteratorCache &, LoopInfo *, DominatorTree *, AssumptionCache *AC, const TargetLibraryInfo *, TargetTransformInfo *, Loop *, MemorySSAUpdater &, ICFLoopSafetyInfo *, OptimizationRemarkEmitter *, bool AllowSpeculation, bool HasReadsOutsideSet)
Try to promote memory values to scalars by sinking stores out of the loop and moving loads to before ...
bool isIdentifiedFunctionLocal(const Value *V)
Return true if V is umabigously identified at the function-level.
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
auto predecessors(const MachineBasicBlock *BB)
bool sinkRegion(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, TargetTransformInfo *, Loop *CurLoop, MemorySSAUpdater &, ICFLoopSafetyInfo *, SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *, Loop *OutermostLoop=nullptr)
Walk the specified region of the CFG (defined by all blocks dominated by the specified block,...
cl::opt< unsigned > SetLicmMssaNoAccForPromotionCap
unsigned pred_size(const MachineBasicBlock *BB)
cl::opt< unsigned > SetLicmMssaOptCap
bool sinkRegionForLoopNest(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, TargetTransformInfo *, Loop *, MemorySSAUpdater &, ICFLoopSafetyInfo *, SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *)
Call sinkRegion on loops contained within the specified loop in order from innermost to outermost.
Type * getLoadStoreType(Value *I)
A helper function that returns the type of a load or store instruction.
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
AAMDNodes merge(const AAMDNodes &Other) const
Given two sets of AAMDNodes applying to potentially different locations, determine the best AAMDNodes...
This struct is a compact representation of a valid (non-zero power of two) alignment.
unsigned MssaNoAccForPromotionCap
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
TargetTransformInfo & TTI
A lightweight accessor for an operand bundle meant to be passed around by value.
uint32_t getTagID() const
Return the tag of this operand bundle as an integer.
A CRTP mix-in to automatically provide informational APIs needed for passes.