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");
106 "Number of min/max expressions hoisted out of the loop");
108 "Number of geps reassociated and hoisted out of the loop");
109STATISTIC(NumAddSubHoisted,
"Number of add/subtract expressions reassociated "
110 "and hoisted out of the loop");
115 cl::desc(
"Disable memory promotion in LICM pass"));
119 cl::desc(
"Enable control flow (and PHI) hoisting in LICM"));
123 cl::desc(
"Force thread model single in LICM pass"));
127 cl::desc(
"Max num uses visited for identifying load "
128 "invariance in loop using invariant start (default = 8)"));
140 cl::desc(
"Enable imprecision in LICM in pathological cases, in exchange "
141 "for faster compile. Caps the MemorySSA clobbering calls."));
148 cl::desc(
"[LICM & MemorySSA] When MSSA in LICM is disabled, this has no "
149 "effect. When MSSA in LICM is enabled, then this is the maximum "
150 "number of accesses allowed to be present in a loop in order to "
151 "enable memory promotion."));
157 bool &FoldableInLoop,
bool LoopNestMode);
173 bool InvariantGroup);
195 std::pair<SmallSetVector<Value *, 8>,
bool>;
200struct LoopInvariantCodeMotion {
206 LoopInvariantCodeMotion(
unsigned LicmMssaOptCap,
207 unsigned LicmMssaNoAccForPromotionCap,
208 bool LicmAllowSpeculation)
209 : LicmMssaOptCap(LicmMssaOptCap),
210 LicmMssaNoAccForPromotionCap(LicmMssaNoAccForPromotionCap),
211 LicmAllowSpeculation(LicmAllowSpeculation) {}
214 unsigned LicmMssaOptCap;
215 unsigned LicmMssaNoAccForPromotionCap;
216 bool LicmAllowSpeculation;
219struct LegacyLICMPass :
public LoopPass {
224 bool LicmAllowSpeculation =
true)
225 :
LoopPass(
ID), LICM(LicmMssaOptCap, LicmMssaNoAccForPromotionCap,
226 LicmAllowSpeculation) {
235 <<
L->getHeader()->getNameOrAsOperand() <<
"\n");
239 auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
240 MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
245 return LICM.runOnLoop(
246 L, &getAnalysis<AAResultsWrapperPass>().getAAResults(),
247 &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
248 &getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
249 &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(*
F),
250 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(*
F),
251 &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(*
F),
252 SE ? &SE->getSE() :
nullptr, MSSA, &ORE);
273 LoopInvariantCodeMotion LICM;
290 if (!LICM.runOnLoop(&L, &AR.
AA, &AR.
LI, &AR.
DT, &AR.
AC, &AR.
TLI, &AR.
TTI,
303 OS, MapClassName2PassName);
326 bool Changed = LICM.runOnLoop(&OutermostLoop, &AR.
AA, &AR.
LI, &AR.
DT, &AR.
AC,
344 OS, MapClassName2PassName);
351char LegacyLICMPass::ID = 0;
364 unsigned LicmMssaNoAccForPromotionCap,
365 bool LicmAllowSpeculation) {
366 return new LegacyLICMPass(LicmMssaOptCap, LicmMssaNoAccForPromotionCap,
367 LicmAllowSpeculation);
376 unsigned LicmMssaOptCap,
unsigned LicmMssaNoAccForPromotionCap,
bool IsSink,
378 : LicmMssaOptCap(LicmMssaOptCap),
379 LicmMssaNoAccForPromotionCap(LicmMssaNoAccForPromotionCap),
381 unsigned AccessCapCount = 0;
382 for (
auto *BB : L.getBlocks())
384 for (
const auto &MA : *Accesses) {
404 bool Changed =
false;
406 assert(L->isLCSSAForm(*DT) &&
"Loop is not in LCSSA form.");
424 return llvm::any_of(*BB, [](Instruction &I) {
425 IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I);
426 return II && II->getIntrinsicID() == Intrinsic::coro_suspend;
450 if (
L->hasDedicatedExits())
454 TLI,
TTI, L, MSSAU, &SafetyInfo, Flags, ORE)
456 MSSAU, &SafetyInfo,
Flags, ORE);
457 Flags.setIsSink(
false);
460 MSSAU, SE, &SafetyInfo, Flags, ORE, LoopNestMode,
461 LicmAllowSpeculation);
471 !
Flags.tooManyMemoryAccesses() && !HasCoroSuspendInst) {
474 L->getUniqueExitBlocks(ExitBlocks);
481 if (!HasCatchSwitch) {
487 InsertPts.
push_back(&*ExitBlock->getFirstInsertionPt());
495 bool Promoted =
false;
498 LocalPromoted =
false;
499 for (
auto [PointerMustAliases, HasReadsOutsideSet] :
502 PointerMustAliases, ExitBlocks, InsertPts, MSSAInsertPts,
PIC, LI,
503 DT, AC, TLI,
TTI, L, MSSAU, &SafetyInfo, ORE,
504 LicmAllowSpeculation, HasReadsOutsideSet);
506 Promoted |= LocalPromoted;
507 }
while (LocalPromoted);
525 assert(
L->isLCSSAForm(*DT) &&
"Loop not left in LCSSA form after LICM!");
526 assert((
L->isOutermost() ||
L->getParentLoop()->isLCSSAForm(*DT)) &&
527 "Parent loop not left in LCSSA form after LICM!");
550 assert(
N !=
nullptr && AA !=
nullptr && LI !=
nullptr && DT !=
nullptr &&
551 CurLoop !=
nullptr && SafetyInfo !=
nullptr &&
552 "Unexpected input to sinkRegion.");
559 bool Changed =
false;
587 bool FoldableInLoop =
false;
588 bool LoopNestMode = OutermostLoop !=
nullptr;
589 if (!
I.mayHaveSideEffects() &&
591 SafetyInfo,
TTI, FoldableInLoop,
594 if (
sink(
I, LI, DT, CurLoop, SafetyInfo, MSSAU, ORE)) {
595 if (!FoldableInLoop) {
618 bool Changed =
false;
622 while (!Worklist.
empty()) {
625 MSSAU, SafetyInfo,
Flags, ORE, CurLoop);
638class ControlFlowHoister {
657 : LI(LI), DT(DT), CurLoop(CurLoop), MSSAU(MSSAU) {}
659 void registerPossiblyHoistableBranch(
BranchInst *BI) {
671 TrueDest == FalseDest)
683 if (TrueDestSucc.
count(FalseDest)) {
684 CommonSucc = FalseDest;
685 }
else if (FalseDestSucc.
count(TrueDest)) {
686 CommonSucc = TrueDest;
690 if (TrueDestSucc.
size() == 1)
691 CommonSucc = *TrueDestSucc.
begin();
695 else if (!TrueDestSucc.
empty()) {
699 assert(It !=
F->end() &&
"Could not find successor in function");
711 if (CommonSucc && DT->
dominates(BI, CommonSucc))
712 HoistableBranches[BI] = CommonSucc;
715 bool canHoistPHI(
PHINode *PN) {
724 PredecessorBlocks.
insert(PredBB);
732 for (
auto &Pair : HoistableBranches) {
733 if (Pair.second == BB) {
736 if (Pair.first->getSuccessor(0) == BB) {
737 PredecessorBlocks.
erase(Pair.first->getParent());
738 PredecessorBlocks.
erase(Pair.first->getSuccessor(1));
739 }
else if (Pair.first->getSuccessor(1) == BB) {
740 PredecessorBlocks.
erase(Pair.first->getParent());
741 PredecessorBlocks.
erase(Pair.first->getSuccessor(0));
743 PredecessorBlocks.
erase(Pair.first->getSuccessor(0));
744 PredecessorBlocks.
erase(Pair.first->getSuccessor(1));
750 return PredecessorBlocks.
empty();
757 if (HoistDestinationMap.
count(BB))
758 return HoistDestinationMap[BB];
761 auto HasBBAsSuccessor =
763 return BB != Pair.second && (Pair.first->getSuccessor(0) == BB ||
764 Pair.first->getSuccessor(1) == BB);
766 auto It =
llvm::find_if(HoistableBranches, HasBBAsSuccessor);
770 if (It == HoistableBranches.end()) {
773 <<
" as hoist destination for "
775 HoistDestinationMap[BB] = InitialPreheader;
776 return InitialPreheader;
779 assert(std::find_if(++It, HoistableBranches.end(), HasBBAsSuccessor) ==
780 HoistableBranches.end() &&
781 "BB is expected to be the target of at most one branch");
786 BasicBlock *CommonSucc = HoistableBranches[BI];
790 auto CreateHoistedBlock = [&](
BasicBlock *Orig) {
791 if (HoistDestinationMap.
count(Orig))
792 return HoistDestinationMap[Orig];
795 HoistDestinationMap[Orig] =
New;
801 <<
" as hoist destination for " << Orig->getName()
805 BasicBlock *HoistTrueDest = CreateHoistedBlock(TrueDest);
806 BasicBlock *HoistFalseDest = CreateHoistedBlock(FalseDest);
807 BasicBlock *HoistCommonSucc = CreateHoistedBlock(CommonSucc);
814 assert(TargetSucc &&
"Expected hoist target to have a single successor");
829 if (HoistTarget == InitialPreheader) {
840 for (
auto &Pair : HoistDestinationMap)
841 if (Pair.second == InitialPreheader && Pair.first != BI->
getParent())
842 Pair.second = HoistCommonSucc;
852 "Hoisting blocks should not have destroyed preheader");
853 return HoistDestinationMap[BB];
870 bool AllowSpeculation) {
872 assert(
N !=
nullptr && AA !=
nullptr && LI !=
nullptr && DT !=
nullptr &&
873 CurLoop !=
nullptr && SafetyInfo !=
nullptr &&
874 "Unexpected input to hoistRegion.");
876 ControlFlowHoister CFH(LI, DT, CurLoop, MSSAU);
887 bool Changed =
false;
892 if (!LoopNestMode &&
inSubLoop(BB, CurLoop, LI))
906 I, DT, TLI, CurLoop, SafetyInfo, ORE,
908 hoist(
I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
917 if (
I.getOpcode() == Instruction::FDiv &&
I.hasAllowReciprocal() &&
919 auto Divisor =
I.getOperand(1);
921 auto ReciprocalDivisor = BinaryOperator::CreateFDiv(One, Divisor);
922 ReciprocalDivisor->setFastMathFlags(
I.getFastMathFlags());
924 ReciprocalDivisor->insertBefore(&
I);
927 BinaryOperator::CreateFMul(
I.getOperand(0), ReciprocalDivisor);
928 Product->setFastMathFlags(
I.getFastMathFlags());
930 Product->insertAfter(&
I);
931 I.replaceAllUsesWith(Product);
934 hoist(*ReciprocalDivisor, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB),
935 SafetyInfo, MSSAU, SE, ORE);
936 HoistedInstructions.
push_back(ReciprocalDivisor);
942 using namespace PatternMatch;
943 return I.use_empty() &&
944 match(&
I, m_Intrinsic<Intrinsic::invariant_start>());
946 auto MustExecuteWithoutWritesBefore = [&](
Instruction &
I) {
950 if ((IsInvariantStart(
I) ||
isGuard(&
I)) &&
952 MustExecuteWithoutWritesBefore(
I)) {
953 hoist(
I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
960 if (
PHINode *PN = dyn_cast<PHINode>(&
I)) {
961 if (CFH.canHoistPHI(PN)) {
967 hoist(*PN, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
985 CFH.registerPossiblyHoistableBranch(BI);
1000 [&](
Use &U) { return DT->dominates(I, U); })) {
1006 "New hoist point expected to dominate old hoist point");
1011 <<
": " << *
I <<
"\n");
1023#ifdef EXPENSIVE_CHECKS
1025 assert(DT->
verify(DominatorTree::VerificationLevel::Fast) &&
1026 "Dominator tree verification failed");
1060 unsigned BitcastsVisited = 0;
1063 while (
Addr->getType() != PtrInt8Ty) {
1064 auto *BC = dyn_cast<BitCastInst>(
Addr);
1068 Addr = BC->getOperand(0);
1072 if (isa<Constant>(
Addr))
1075 unsigned UsesVisited = 0;
1078 for (
auto *U :
Addr->users()) {
1112 return (isa<LoadInst>(
I) || isa<StoreInst>(
I) || isa<CallInst>(
I) ||
1113 isa<FenceInst>(
I) || isa<CastInst>(
I) || isa<UnaryOperator>(
I) ||
1114 isa<BinaryOperator>(
I) || isa<SelectInst>(
I) ||
1115 isa<GetElementPtrInst>(
I) || isa<CmpInst>(
I) ||
1116 isa<InsertElementInst>(
I) || isa<ExtractElementInst>(
I) ||
1117 isa<ShuffleVectorInst>(
I) || isa<ExtractValueInst>(
I) ||
1118 isa<InsertValueInst>(
I) || isa<FreezeInst>(
I));
1122 for (
auto *BB :
L->getBlocks())
1131 for (
auto *BB :
L->getBlocks())
1134 for (
const auto &Acc : *Accs) {
1135 if (isa<MemoryPhi>(&Acc))
1137 const auto *MUD = cast<MemoryUseOrDef>(&Acc);
1138 if (MUD->getMemoryInst() !=
I || NotAPhi++ == 1)
1151 if (
Flags.tooManyClobberingCalls())
1156 Flags.incrementClobberingCalls();
1162 bool TargetExecutesOncePerLoop,
1166 if (!isHoistableAndSinkableInst(
I))
1171 if (
LoadInst *LI = dyn_cast<LoadInst>(&
I)) {
1172 if (!LI->isUnordered())
1179 if (LI->hasMetadata(LLVMContext::MD_invariant_load))
1182 if (LI->isAtomic() && !TargetExecutesOncePerLoop)
1191 bool InvariantGroup = LI->hasMetadata(LLVMContext::MD_invariant_group);
1194 MSSA, MU, CurLoop,
I,
Flags, InvariantGroup);
1197 if (ORE && Invalidated && CurLoop->
isLoopInvariant(LI->getPointerOperand()))
1200 DEBUG_TYPE,
"LoadWithLoopInvariantAddressInvalidated", LI)
1201 <<
"failed to move load with loop-invariant address "
1202 "because the loop may invalidate its value";
1205 return !Invalidated;
1206 }
else if (
CallInst *CI = dyn_cast<CallInst>(&
I)) {
1208 if (isa<DbgInfoIntrinsic>(
I))
1219 if (CI->isConvergent())
1222 using namespace PatternMatch;
1223 if (
match(CI, m_Intrinsic<Intrinsic::assume>()))
1237 for (
Value *Op : CI->args())
1238 if (Op->getType()->isPointerTy() &&
1248 if (isReadOnly(MSSAU, CurLoop))
1256 }
else if (
auto *FI = dyn_cast<FenceInst>(&
I)) {
1259 return isOnlyMemoryAccess(FI, CurLoop, MSSAU);
1260 }
else if (
auto *
SI = dyn_cast<StoreInst>(&
I)) {
1261 if (!
SI->isUnordered())
1269 if (isOnlyMemoryAccess(
SI, CurLoop, MSSAU))
1273 if (
Flags.tooManyMemoryAccesses())
1281 CurLoop->
contains(Source->getBlock()))
1291 for (
const auto &MA : *Accesses)
1292 if (
const auto *MU = dyn_cast<MemoryUse>(&MA)) {
1304 }
else if (
const auto *MD = dyn_cast<MemoryDef>(&MA)) {
1305 if (
auto *LI = dyn_cast<LoadInst>(MD->getMemoryInst())) {
1307 assert(!LI->isUnordered() &&
"Expected unordered load");
1311 if (
auto *CI = dyn_cast<CallInst>(MD->getMemoryInst())) {
1324 assert(!
I.mayReadOrWriteMemory() &&
"unhandled aliasing");
1347 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(&
I)) {
1356 for (
const User *U :
GEP->users()) {
1360 (!isa<StoreInst>(UI) && !isa<LoadInst>(UI))))
1378 bool &FoldableInLoop,
bool LoopNestMode) {
1381 for (
const User *U :
I.users()) {
1383 if (
const PHINode *PN = dyn_cast<PHINode>(UI)) {
1391 if (isa<CallInst>(
I))
1392 if (!BlockColors.empty() &&
1393 BlockColors.find(
const_cast<BasicBlock *
>(BB))->second.size() != 1)
1397 while (isa<PHINode>(UI) && UI->
hasOneUser() &&
1401 UI = cast<Instruction>(UI->
user_back());
1408 FoldableInLoop =
true;
1421 if (
auto *CI = dyn_cast<CallInst>(&
I)) {
1428 for (
unsigned BundleIdx = 0, BundleEnd = CI->getNumOperandBundles();
1429 BundleIdx != BundleEnd; ++BundleIdx) {
1437 if (!BlockColors.empty()) {
1438 const ColorVector &CV = BlockColors.find(&ExitBlock)->second;
1439 assert(CV.
size() == 1 &&
"non-unique color for exit block!");
1452 if (!
I.getName().empty())
1453 New->setName(
I.getName() +
".le");
1460 if (
auto *MemDef = dyn_cast<MemoryDef>(NewMemAcc))
1463 auto *MemUse = cast<MemoryUse>(NewMemAcc);
1476 for (
Use &Op : New->operands())
1478 auto *OInst = cast<Instruction>(Op.get());
1481 OInst->getName() +
".lcssa", &ExitBlock.
front());
1493 I.eraseFromParent();
1502 I.moveBefore(&Dest);
1516 "Expect only trivially replaceable PHI");
1519 auto It = SunkCopies.
find(ExitBlock);
1520 if (It != SunkCopies.
end())
1524 *
I, *ExitBlock, *TPN, LI, SafetyInfo, MSSAU);
1539 if (isa<IndirectBrInst>(BBPred->getTerminator()))
1556 assert(ExitBlockSet.
count(ExitBB) &&
"Expect the PHI is in an exit block.");
1592 while (!PredBBs.
empty()) {
1595 "Expect all predecessors are in the loop");
1598 ExitBB, PredBB,
".split.loop.exit", DT, LI, MSSAU,
true);
1602 if (!BlockColors.empty())
1620 bool Changed =
false;
1627 auto *
User = cast<Instruction>(*UI);
1628 Use &U = UI.getUse();
1666 UI =
I.user_begin();
1670 if (VisitedUsers.
empty())
1675 <<
"sinking " <<
ore::NV(
"Inst", &
I);
1677 if (isa<LoadInst>(
I))
1679 else if (isa<CallInst>(
I))
1699 for (
auto *UI :
Users) {
1700 auto *
User = cast<Instruction>(UI);
1707 "The LCSSA PHI is not in an exit block!");
1711 PN, &
I, LI, SunkCopies, SafetyInfo, CurLoop, MSSAU);
1741 if ((
I.hasMetadataOtherThanDebugLoc() || isa<CallInst>(
I)) &&
1746 I.dropUBImplyingAttrsAndMetadata();
1748 if (isa<PHINode>(
I))
1755 I.updateLocationAfterHoist();
1757 if (isa<LoadInst>(
I))
1759 else if (isa<CallInst>(
I))
1772 if (AllowSpeculation &&
1776 bool GuaranteedToExecute =
1779 if (!GuaranteedToExecute) {
1780 auto *LI = dyn_cast<LoadInst>(&Inst);
1784 DEBUG_TYPE,
"LoadWithLoopInvariantAddressCondExecuted", LI)
1785 <<
"failed to hoist load with loop-invariant address "
1786 "because load is conditionally executed";
1790 return GuaranteedToExecute;
1804 bool UnorderedAtomic;
1807 bool CanInsertStoresInExitBlocks;
1821 I->getName() +
".lcssa", &BB->
front());
1836 LoopInsertPts(LIP), MSSAInsertPts(MSSAIP), PredCache(
PIC), MSSAU(MSSAU),
1837 LI(li),
DL(
std::
move(dl)), Alignment(Alignment),
1838 UnorderedAtomic(UnorderedAtomic), AATags(AATags),
1839 SafetyInfo(SafetyInfo),
1840 CanInsertStoresInExitBlocks(CanInsertStoresInExitBlocks),
Uses(Insts) {}
1842 void insertStoresInLoopExitBlocks() {
1848 for (
unsigned i = 0, e = LoopExitBlocks.
size(); i != e; ++i) {
1850 Value *LiveInValue =
SSA.GetValueInMiddleOfBlock(ExitBlock);
1851 LiveInValue = maybeInsertLCSSAPHI(LiveInValue, ExitBlock);
1852 Value *
Ptr = maybeInsertLCSSAPHI(SomePtr, ExitBlock);
1855 if (UnorderedAtomic)
1866 NewID = cast_or_null<DIAssignID>(
1871 NewSI->
setMetadata(LLVMContext::MD_DIAssignID, NewID);
1879 if (!MSSAInsertPoint) {
1886 MSSAInsertPts[i] = NewMemAcc;
1887 MSSAU.
insertDef(cast<MemoryDef>(NewMemAcc),
true);
1892 void doExtraRewritesBeforeFinalDeletion()
override {
1893 if (CanInsertStoresInExitBlocks)
1894 insertStoresInLoopExitBlocks();
1897 void instructionDeleted(
Instruction *
I)
const override {
1903 if (isa<StoreInst>(
I))
1904 return CanInsertStoresInExitBlocks;
1909bool isNotCapturedBeforeOrInLoop(
const Value *V,
const Loop *L,
1917 L->getHeader()->getTerminator(), DT);
1924 bool RequiresNoCaptureBeforeUnwind;
1928 return !RequiresNoCaptureBeforeUnwind ||
1929 isNotCapturedBeforeOrInLoop(
Object, L, DT);
1937 if (isa<AllocaInst>(
Object))
1941 if (
auto *
A = dyn_cast<Argument>(
Object))
1942 return A->hasByValAttr();
1954 isNotCapturedBeforeOrInLoop(
Object, L, DT)) ||
1974 bool HasReadsOutsideSet) {
1976 assert(LI !=
nullptr && DT !=
nullptr && CurLoop !=
nullptr &&
1977 SafetyInfo !=
nullptr &&
1978 "Unexpected Input to promoteLoopAccessesToScalars");
1981 dbgs() <<
"Trying to promote set of must-aliased pointers:\n";
1982 for (
Value *
Ptr : PointerMustAliases)
1983 dbgs() <<
" " << *
Ptr <<
"\n";
1985 ++NumPromotionCandidates;
1987 Value *SomePtr = *PointerMustAliases.
begin();
2027 bool DereferenceableInPH =
false;
2028 bool StoreIsGuanteedToExecute =
false;
2029 bool FoundLoadToPromote =
false;
2035 } StoreSafety = StoreSafetyUnknown;
2043 bool SawUnorderedAtomic =
false;
2044 bool SawNotAtomic =
false;
2051 if (HasReadsOutsideSet)
2052 StoreSafety = StoreUnsafe;
2061 if (!isNotVisibleOnUnwindInLoop(
Object, CurLoop, DT))
2062 StoreSafety = StoreUnsafe;
2068 Type *AccessTy =
nullptr;
2069 for (
Value *ASIV : PointerMustAliases) {
2070 for (
Use &U : ASIV->uses()) {
2072 Instruction *UI = dyn_cast<Instruction>(U.getUser());
2078 if (
LoadInst *Load = dyn_cast<LoadInst>(UI)) {
2079 if (!Load->isUnordered())
2082 SawUnorderedAtomic |= Load->isAtomic();
2083 SawNotAtomic |= !Load->isAtomic();
2084 FoundLoadToPromote =
true;
2086 Align InstAlignment = Load->getAlign();
2092 if (!DereferenceableInPH || (InstAlignment > Alignment))
2094 *Load, DT, TLI, CurLoop, SafetyInfo, ORE,
2096 DereferenceableInPH =
true;
2097 Alignment = std::max(Alignment, InstAlignment);
2099 }
else if (
const StoreInst *Store = dyn_cast<StoreInst>(UI)) {
2104 if (!Store->isUnordered())
2107 SawUnorderedAtomic |= Store->isAtomic();
2108 SawNotAtomic |= !Store->isAtomic();
2115 Align InstAlignment = Store->getAlign();
2116 bool GuaranteedToExecute =
2118 StoreIsGuanteedToExecute |= GuaranteedToExecute;
2119 if (GuaranteedToExecute) {
2120 DereferenceableInPH =
true;
2121 if (StoreSafety == StoreSafetyUnknown)
2122 StoreSafety = StoreSafe;
2123 Alignment = std::max(Alignment, InstAlignment);
2132 if (StoreSafety == StoreSafetyUnknown &&
2134 return DT->
dominates(Store->getParent(), Exit);
2136 StoreSafety = StoreSafe;
2140 if (!DereferenceableInPH) {
2142 Store->getPointerOperand(), Store->getValueOperand()->getType(),
2143 Store->getAlign(), MDL, Preheader->
getTerminator(), AC, DT, TLI);
2154 if (LoopUses.
empty()) {
2157 }
else if (AATags) {
2169 if (SawUnorderedAtomic && SawNotAtomic)
2179 if (!DereferenceableInPH) {
2180 LLVM_DEBUG(
dbgs() <<
"Not promoting: Not dereferenceable in preheader\n");
2188 if (StoreSafety == StoreSafetyUnknown) {
2190 if (isWritableObject(
Object) &&
2191 isThreadLocalObject(
Object, CurLoop, DT,
TTI))
2192 StoreSafety = StoreSafe;
2197 if (StoreSafety != StoreSafe && !FoundLoadToPromote)
2202 if (StoreSafety == StoreSafe) {
2203 LLVM_DEBUG(
dbgs() <<
"LICM: Promoting load/store of the value: " << *SomePtr
2205 ++NumLoadStorePromoted;
2207 LLVM_DEBUG(
dbgs() <<
"LICM: Promoting load of the value: " << *SomePtr
2215 <<
"Moving accesses to memory location out of the loop";
2219 std::vector<DILocation *> LoopUsesLocs;
2220 for (
auto *U : LoopUses)
2221 LoopUsesLocs.push_back(U->getDebugLoc().get());
2227 LoopPromoter Promoter(SomePtr, LoopUses,
SSA, ExitBlocks, InsertPts,
2228 MSSAInsertPts,
PIC, MSSAU, *LI,
DL, Alignment,
2229 SawUnorderedAtomic, AATags, *SafetyInfo,
2230 StoreSafety == StoreSafe);
2235 if (FoundLoadToPromote || !StoreIsGuanteedToExecute) {
2239 if (SawUnorderedAtomic)
2248 MemoryUse *NewMemUse = cast<MemoryUse>(PreheaderLoadMemoryAccess);
2250 SSA.AddAvailableValue(Preheader, PreheaderLoad);
2259 Promoter.run(LoopUses);
2264 if (PreheaderLoad && PreheaderLoad->
use_empty())
2274 for (
const auto &Access : *Accesses)
2275 if (
const auto *MUD = dyn_cast<MemoryUseOrDef>(&Access))
2276 Fn(MUD->getMemoryInst());
2286 auto IsPotentiallyPromotable = [L](
const Instruction *
I) {
2287 if (
const auto *
SI = dyn_cast<StoreInst>(
I))
2288 return L->isLoopInvariant(
SI->getPointerOperand());
2289 if (
const auto *LI = dyn_cast<LoadInst>(
I))
2290 return L->isLoopInvariant(LI->getPointerOperand());
2297 if (IsPotentiallyPromotable(
I)) {
2298 AttemptingPromotion.
insert(
I);
2306 if (!AS.isForwardingAliasSet() && AS.isMod() && AS.isMustAlias())
2318 ModRefInfo MR = Pair.getPointer()->aliasesUnknownInst(I, BatchAA);
2327 return !Pair.getPointer()->isRef();
2334 for (
auto [Set, HasReadsOutsideSet] : Sets) {
2336 for (
const auto &ASI : *Set)
2337 PointerMustAliases.
insert(ASI.getValue());
2338 Result.emplace_back(std::move(PointerMustAliases), HasReadsOutsideSet);
2347 bool InvariantGroup) {
2349 if (!
Flags.getIsSink()) {
2362 CurLoop->
contains(Source->getBlock()) &&
2363 !(InvariantGroup && Source->getBlock() == CurLoop->
getHeader() && isa<MemoryPhi>(Source));
2383 if (
Flags.tooManyMemoryAccesses())
2397 for (
const auto &MA : *Accesses)
2398 if (
const auto *MD = dyn_cast<MemoryDef>(&MA))
2410 using namespace PatternMatch;
2411 Value *Cond1, *Cond2;
2427 if (L.isLoopInvariant(
LHS)) {
2431 if (L.isLoopInvariant(
LHS) || !L.isLoopInvariant(
RHS))
2438 Value *LHS1, *LHS2, *RHS1, *RHS2;
2439 if (!MatchICmpAgainstInvariant(Cond1, P1, LHS1, RHS1) ||
2440 !MatchICmpAgainstInvariant(Cond2, P2, LHS2, RHS2))
2442 if (P1 != P2 || LHS1 != LHS2)
2449 "Relational predicate is either less (or equal) or greater (or equal)!");
2451 ? (UseMin ? Intrinsic::smin : Intrinsic::smax)
2452 : (UseMin ? Intrinsic::umin : Intrinsic::umax);
2453 auto *Preheader = L.getLoopPreheader();
2454 assert(Preheader &&
"Loop is not in simplify form?");
2460 if (isa<SelectInst>(
I))
2463 id, RHS1, RHS2,
nullptr,
StringRef(
"invariant.") +
2465 (UseMin ?
"min" :
"max"));
2472 I.replaceAllUsesWith(NewCond);
2484 auto *
GEP = dyn_cast<GetElementPtrInst>(&
I);
2488 auto *Src = dyn_cast<GetElementPtrInst>(
GEP->getPointerOperand());
2489 if (!Src || !Src->hasOneUse() || !L.contains(Src))
2492 Value *SrcPtr = Src->getPointerOperand();
2493 auto LoopInvariant = [&](
Value *V) {
return L.isLoopInvariant(V); };
2494 if (!L.isLoopInvariant(SrcPtr) || !
all_of(
GEP->indices(), LoopInvariant))
2501 if (
all_of(Src->indices(), LoopInvariant))
2511 bool IsInBounds = Src->isInBounds() &&
GEP->isInBounds() &&
2515 BasicBlock *Preheader = L.getLoopPreheader();
2517 Value *NewSrc =
Builder.CreateGEP(
GEP->getSourceElementType(), SrcPtr,
2519 "invariant.gep", IsInBounds);
2521 Value *NewGEP =
Builder.CreateGEP(Src->getSourceElementType(), NewSrc,
2524 GEP->replaceAllUsesWith(NewGEP);
2537 assert(!L.isLoopInvariant(VariantLHS) &&
"Precondition.");
2538 assert(L.isLoopInvariant(InvariantRHS) &&
"Precondition.");
2541 using namespace PatternMatch;
2542 Value *VariantOp, *InvariantOp;
2548 if (L.isLoopInvariant(VariantOp))
2550 if (L.isLoopInvariant(VariantOp) || !L.isLoopInvariant(InvariantOp))
2557 auto &
DL = L.getHeader()->getModule()->getDataLayout();
2558 bool ProvedNoOverflowAfterReassociate =
2561 if (!ProvedNoOverflowAfterReassociate)
2563 auto *Preheader = L.getLoopPreheader();
2564 assert(Preheader &&
"Loop is not in simplify form?");
2566 Value *NewCmpOp =
Builder.CreateSub(InvariantRHS, InvariantOp,
"invariant.op",
2579 using namespace PatternMatch;
2590 if (L.isLoopInvariant(
LHS)) {
2601 if (
hoistAdd(Pred,
LHS,
RHS, cast<ICmpInst>(
I), L, SafetyInfo, MSSAU, AC, DT))
2623 if (
hoistGEP(
I, L, SafetyInfo, MSSAU, AC, DT)) {
2643 assert(CurLoop->
contains(BB) &&
"Only valid if BB is IN the loop");
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
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...
Rewrite Partial Register Uses
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
iv Induction Variable Users
static bool isNotUsedOrFoldableInLoop(const Instruction &I, const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo, TargetTransformInfo *TTI, bool &FoldableInLoop, bool LoopNestMode)
Return true if the only users of this instruction are outside of the loop.
static bool hoistGEP(Instruction &I, Loop &L, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU, AssumptionCache *AC, DominatorTree *DT)
Reassociate gep (gep ptr, idx1), idx2 to gep (gep ptr, idx2), idx1 if this allows hoisting the inner ...
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 void splitPredecessorsOfLoopExit(PHINode *PN, DominatorTree *DT, LoopInfo *LI, const Loop *CurLoop, LoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU)
static bool isFoldableInLoop(const Instruction &I, const Loop *CurLoop, const TargetTransformInfo *TTI)
Return true if the instruction is foldable in the loop.
static bool hoistMinMax(Instruction &I, Loop &L, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU)
Try to simplify things like (A < INV_1 AND icmp A < INV_2) into (A < min(INV_1, INV_2)),...
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 bool pointerInvalidatedByLoop(MemorySSA *MSSA, MemoryUse *MU, Loop *CurLoop, Instruction &I, SinkAndHoistLICMFlags &Flags, bool InvariantGroup)
static bool hoistAdd(ICmpInst::Predicate Pred, Value *VariantLHS, Value *InvariantRHS, ICmpInst &ICmp, Loop &L, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU, AssumptionCache *AC, DominatorTree *DT)
Try to turn things like "LV + C1 < C2" into "LV < C2 - C1".
static MemoryAccess * getClobberingMemoryAccess(MemorySSA &MSSA, BatchAAResults &BAA, SinkAndHoistLICMFlags &Flags, MemoryUseOrDef *MA)
static SmallVector< PointersAndHasReadsOutsideSet, 0 > collectPromotionCandidates(MemorySSA *MSSA, AliasAnalysis *AA, Loop *L)
static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop, BasicBlock *Dest, ICFLoopSafetyInfo *SafetyInfo, MemorySSAUpdater &MSSAU, ScalarEvolution *SE, OptimizationRemarkEmitter *ORE)
When an instruction is found to only use loop invariant operands that is safe to hoist,...
static bool canSplitPredecessors(PHINode *PN, LoopSafetyInfo *SafetyInfo)
static void moveInstructionBefore(Instruction &I, Instruction &Dest, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU, ScalarEvolution *SE)
static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT, const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo, MemorySSAUpdater &MSSAU, OptimizationRemarkEmitter *ORE)
When an instruction is found to only be used outside of the loop, this function moves it to the exit ...
static bool hoistAddSub(Instruction &I, Loop &L, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU, AssumptionCache *AC, DominatorTree *DT)
Reassociate and hoist add/sub expressions.
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 hoistArithmetics(Instruction &I, Loop &L, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU, AssumptionCache *AC, DominatorTree *DT)
Aggregates various functions for hoisting computations out of loop.
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 pointerInvalidatedByBlock(BasicBlock &BB, MemorySSA &MSSA, MemoryUse &MU)
This file defines the interface for the loop nest analysis.
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 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...
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
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)
void setPredicate(Predicate P)
Set the predicate for this instruction to the specified value.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
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 ...
static DILocation * getMergedLocations(ArrayRef< 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.
This instruction compares its operands according to the predicate given to the constructor.
static bool isGE(Predicate P)
Return true if the predicate is SGE or UGE.
static bool isLT(Predicate P)
Return true if the predicate is SLT or ULT.
static bool isGT(Predicate P)
Return true if the predicate is SGT or UGT.
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
static bool isLE(Predicate P)
Return true if the predicate is SLE or ULE.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
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.
BlockT * getHeader() const
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
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.
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 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.
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 forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
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, MemorySSA &MSSA)
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)
bool isIntegerTy() const
True if this is an instance of IntegerType.
A Use represents the edge between a Value definition and its users.
void setOperand(unsigned i, Value *Val)
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
bool hasOneUse() const
Return true if there is exactly one use of this value.
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.
user_iterator_impl< User > user_iterator
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
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)
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
OneUse_match< T > m_OneUse(const T &SubPattern)
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoSignedWrap > m_NSWAdd(const LHS &L, const RHS &R)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
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)
@ NeverOverflows
Never overflows.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
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 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.
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI)
Put a loop nest into LCSSA form.
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.
bool 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.
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.
bool isKnownNonNegative(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Returns true if the give value is known to be non-negative.
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.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
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.