Go to the documentation of this file.
93 #define DEBUG_TYPE "licm"
95 STATISTIC(NumCreatedBlocks,
"Number of blocks created");
96 STATISTIC(NumClonedBranches,
"Number of branches cloned");
97 STATISTIC(NumSunk,
"Number of instructions sunk out of loop");
98 STATISTIC(NumHoisted,
"Number of instructions hoisted out of loop");
99 STATISTIC(NumMovedLoads,
"Number of load insts hoisted or sunk");
100 STATISTIC(NumMovedCalls,
"Number of call insts hoisted or sunk");
101 STATISTIC(NumPromoted,
"Number of memory locations promoted to registers");
106 cl::desc(
"Disable memory promotion in LICM pass"));
110 cl::desc(
"Enable control flow (and PHI) hoisting in LICM"));
114 cl::desc(
"Max num uses visited for identifying load "
115 "invariance in loop using invariant start (default = 8)"));
127 cl::desc(
"Enable imprecision in LICM in pathological cases, in exchange "
128 "for faster compile. Caps the MemorySSA clobbering calls."));
135 cl::desc(
"[LICM & MemorySSA] When MSSA in LICM is disabled, this has no "
136 "effect. When MSSA in LICM is enabled, then this is the maximum "
137 "number of accesses allowed to be present in a loop in order to "
138 "enable memory promotion."));
157 bool AllowSpeculation);
180 struct LoopInvariantCodeMotion {
186 LoopInvariantCodeMotion(
unsigned LicmMssaOptCap,
187 unsigned LicmMssaNoAccForPromotionCap,
188 bool LicmAllowSpeculation)
189 : LicmMssaOptCap(LicmMssaOptCap),
190 LicmMssaNoAccForPromotionCap(LicmMssaNoAccForPromotionCap),
191 LicmAllowSpeculation(LicmAllowSpeculation) {}
194 unsigned LicmMssaOptCap;
195 unsigned LicmMssaNoAccForPromotionCap;
196 bool LicmAllowSpeculation;
199 struct LegacyLICMPass :
public LoopPass {
204 bool LicmAllowSpeculation =
true)
205 :
LoopPass(
ID),
LICM(LicmMssaOptCap, LicmMssaNoAccForPromotionCap,
206 LicmAllowSpeculation) {
217 auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
218 MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
221 hasProfileData ? &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI()
227 return LICM.runOnLoop(
228 L, &getAnalysis<AAResultsWrapperPass>().getAAResults(),
229 &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
230 &getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
BFI,
231 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
233 &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
235 SE ? &SE->getSE() :
nullptr, MSSA, &ORE);
255 LoopInvariantCodeMotion
LICM;
287 OS, MapClassName2PassName);
309 bool Changed =
LICM.runOnLoop(&OutermostLoop, &AR.
AA, &AR.
LI, &AR.
DT, AR.
BFI,
327 OS, MapClassName2PassName);
347 unsigned LicmMssaNoAccForPromotionCap,
348 bool LicmAllowSpeculation) {
349 return new LegacyLICMPass(LicmMssaOptCap, LicmMssaNoAccForPromotionCap,
350 LicmAllowSpeculation);
359 unsigned LicmMssaOptCap,
unsigned LicmMssaNoAccForPromotionCap,
bool IsSink,
361 : LicmMssaOptCap(LicmMssaOptCap),
362 LicmMssaNoAccForPromotionCap(LicmMssaNoAccForPromotionCap),
364 assert(((L !=
nullptr) == (MSSA !=
nullptr)) &&
365 "Unexpected values for SinkAndHoistLICMFlags");
369 unsigned AccessCapCount = 0;
372 for (
const auto &MA : *Accesses) {
385 bool LoopInvariantCodeMotion::runOnLoop(
390 bool Changed =
false;
411 return llvm::any_of(*BB, [](Instruction &I) {
412 IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I);
413 return II && II->getIntrinsicID() == Intrinsic::coro_suspend;
438 Changed |= LoopNestMode
440 DT,
BFI, TLI,
TTI, L, MSSAU,
441 &SafetyInfo, Flags, ORE)
443 TLI,
TTI, L, MSSAU, &SafetyInfo, Flags, ORE);
444 Flags.setIsSink(
false);
447 MSSAU, SE, &SafetyInfo, Flags, ORE, LoopNestMode,
448 LicmAllowSpeculation);
458 !Flags.tooManyMemoryAccesses() && !HasCoroSuspendInst) {
468 if (!HasCatchSwitch) {
471 InsertPts.
reserve(ExitBlocks.size());
472 MSSAInsertPts.
reserve(ExitBlocks.size());
474 InsertPts.push_back(&*ExitBlock->getFirstInsertionPt());
475 MSSAInsertPts.push_back(
nullptr);
482 bool Promoted =
false;
485 LocalPromoted =
false;
489 PointerMustAliases, ExitBlocks, InsertPts, MSSAInsertPts,
PIC, LI,
490 DT, TLI, L, MSSAU, &SafetyInfo, ORE, LicmAllowSpeculation);
492 Promoted |= LocalPromoted;
493 }
while (LocalPromoted);
513 "Parent loop not left in LCSSA form after LICM!");
537 assert(
N !=
nullptr &&
AA !=
nullptr && LI !=
nullptr && DT !=
nullptr &&
538 CurLoop !=
nullptr && SafetyInfo !=
nullptr &&
539 "Unexpected input to sinkRegion.");
546 bool Changed =
false;
574 bool FreeInLoop =
false;
575 bool LoopNestMode = OutermostLoop !=
nullptr;
576 if (!
I.mayHaveSideEffects() &&
578 SafetyInfo,
TTI, FreeInLoop, LoopNestMode) &&
580 if (
sink(
I, LI, DT,
BFI, CurLoop, SafetyInfo, MSSAU, ORE)) {
602 bool Changed =
false;
606 while (!Worklist.
empty()) {
609 TTI, L, MSSAU, SafetyInfo, Flags, ORE, CurLoop);
622 class ControlFlowHoister {
641 : LI(LI), DT(DT), CurLoop(CurLoop), MSSAU(MSSAU) {}
643 void registerPossiblyHoistableBranch(
BranchInst *BI) {
655 TrueDest == FalseDest)
667 if (TrueDestSucc.
count(FalseDest)) {
668 CommonSucc = FalseDest;
669 }
else if (FalseDestSucc.
count(TrueDest)) {
670 CommonSucc = TrueDest;
674 if (TrueDestSucc.
size() == 1)
675 CommonSucc = *TrueDestSucc.
begin();
679 else if (!TrueDestSucc.
empty()) {
683 assert(It !=
F->end() &&
"Could not find successor in function");
695 if (CommonSucc && DT->
dominates(BI, CommonSucc))
696 HoistableBranches[BI] = CommonSucc;
699 bool canHoistPHI(
PHINode *PN) {
708 PredecessorBlocks.
insert(PredBB);
716 for (
auto &Pair : HoistableBranches) {
717 if (Pair.second ==
BB) {
720 if (Pair.first->getSuccessor(0) ==
BB) {
721 PredecessorBlocks.
erase(Pair.first->getParent());
722 PredecessorBlocks.
erase(Pair.first->getSuccessor(1));
723 }
else if (Pair.first->getSuccessor(1) ==
BB) {
724 PredecessorBlocks.
erase(Pair.first->getParent());
725 PredecessorBlocks.
erase(Pair.first->getSuccessor(0));
727 PredecessorBlocks.
erase(Pair.first->getSuccessor(0));
728 PredecessorBlocks.
erase(Pair.first->getSuccessor(1));
734 return PredecessorBlocks.
empty();
741 if (HoistDestinationMap.
count(
BB))
742 return HoistDestinationMap[
BB];
745 auto HasBBAsSuccessor =
747 return BB != Pair.second && (Pair.first->getSuccessor(0) ==
BB ||
748 Pair.first->getSuccessor(1) ==
BB);
750 auto It =
llvm::find_if(HoistableBranches, HasBBAsSuccessor);
754 if (It == HoistableBranches.end()) {
757 <<
" as hoist destination for "
758 <<
BB->getNameOrAsOperand() <<
"\n");
759 HoistDestinationMap[
BB] = InitialPreheader;
760 return InitialPreheader;
764 HoistableBranches.end() &&
765 "BB is expected to be the target of at most one branch");
770 BasicBlock *CommonSucc = HoistableBranches[BI];
774 auto CreateHoistedBlock = [&](
BasicBlock *Orig) {
775 if (HoistDestinationMap.
count(Orig))
776 return HoistDestinationMap[Orig];
778 BasicBlock::Create(
C, Orig->getName() +
".licm", Orig->getParent());
779 HoistDestinationMap[Orig] =
New;
785 <<
" as hoist destination for " << Orig->getName()
789 BasicBlock *HoistTrueDest = CreateHoistedBlock(TrueDest);
790 BasicBlock *HoistFalseDest = CreateHoistedBlock(FalseDest);
791 BasicBlock *HoistCommonSucc = CreateHoistedBlock(CommonSucc);
798 assert(TargetSucc &&
"Expected hoist target to have a single successor");
800 BranchInst::Create(TargetSucc, HoistCommonSucc);
804 BranchInst::Create(HoistCommonSucc, HoistTrueDest);
808 BranchInst::Create(HoistCommonSucc, HoistFalseDest);
813 if (HoistTarget == InitialPreheader) {
824 for (
auto &Pair : HoistDestinationMap)
825 if (Pair.second == InitialPreheader && Pair.first != BI->
getParent())
826 Pair.second = HoistCommonSucc;
832 BranchInst::Create(HoistTrueDest, HoistFalseDest, BI->
getCondition()));
836 "Hoisting blocks should not have destroyed preheader");
837 return HoistDestinationMap[
BB];
854 bool AllowSpeculation) {
856 assert(
N !=
nullptr &&
AA !=
nullptr && LI !=
nullptr && DT !=
nullptr &&
857 CurLoop !=
nullptr && SafetyInfo !=
nullptr &&
858 "Unexpected input to hoistRegion.");
860 ControlFlowHoister CFH(LI, DT, CurLoop, MSSAU);
871 bool Changed =
false;
883 &
I,
I.getModule()->getDataLayout(), TLI)) {
887 I.replaceAllUsesWith(
C);
904 I, DT, TLI, CurLoop, SafetyInfo, ORE,
906 hoist(
I, DT, CurLoop, CFH.getOrCreateHoistedBlock(
BB), SafetyInfo,
908 HoistedInstructions.push_back(&
I);
915 if (
I.getOpcode() == Instruction::FDiv &&
I.hasAllowReciprocal() &&
917 auto Divisor =
I.getOperand(1);
919 auto ReciprocalDivisor = BinaryOperator::CreateFDiv(One, Divisor);
920 ReciprocalDivisor->setFastMathFlags(
I.getFastMathFlags());
922 ReciprocalDivisor->insertBefore(&
I);
925 BinaryOperator::CreateFMul(
I.getOperand(0), ReciprocalDivisor);
926 Product->setFastMathFlags(
I.getFastMathFlags());
928 Product->insertAfter(&
I);
929 I.replaceAllUsesWith(Product);
932 hoist(*ReciprocalDivisor, DT, CurLoop, CFH.getOrCreateHoistedBlock(
BB),
933 SafetyInfo, MSSAU, SE, ORE);
934 HoistedInstructions.push_back(ReciprocalDivisor);
940 using namespace PatternMatch;
941 return I.use_empty() &&
942 match(&
I, m_Intrinsic<Intrinsic::invariant_start>());
944 auto MustExecuteWithoutWritesBefore = [&](
Instruction &
I) {
948 if ((IsInvariantStart(
I) ||
isGuard(&
I)) &&
950 MustExecuteWithoutWritesBefore(
I)) {
951 hoist(
I, DT, CurLoop, CFH.getOrCreateHoistedBlock(
BB), SafetyInfo,
953 HoistedInstructions.push_back(&
I);
958 if (
PHINode *PN = dyn_cast<PHINode>(&
I)) {
959 if (CFH.canHoistPHI(PN)) {
965 hoist(*PN, DT, CurLoop, CFH.getOrCreateHoistedBlock(
BB), SafetyInfo,
976 CFH.registerPossiblyHoistableBranch(BI);
991 [&](
Use &U) { return DT->dominates(I, U); })) {
997 "New hoist point expected to dominate old hoist point");
1002 <<
": " << *
I <<
"\n");
1014 #ifdef EXPENSIVE_CHECKS
1017 "Dominator tree verification failed");
1051 unsigned BitcastsVisited = 0;
1054 while (
Addr->getType() != PtrInt8Ty) {
1055 auto *BC = dyn_cast<BitCastInst>(
Addr);
1059 Addr = BC->getOperand(0);
1063 if (isa<Constant>(
Addr))
1066 unsigned UsesVisited = 0;
1069 for (
auto *U :
Addr->users()) {
1089 if (LocSizeInBits.
getFixedSize() <= InvariantSizeInBits &&
1103 return (isa<LoadInst>(
I) || isa<StoreInst>(
I) || isa<CallInst>(
I) ||
1104 isa<FenceInst>(
I) || isa<CastInst>(
I) || isa<UnaryOperator>(
I) ||
1105 isa<BinaryOperator>(
I) || isa<SelectInst>(
I) ||
1106 isa<GetElementPtrInst>(
I) || isa<CmpInst>(
I) ||
1107 isa<InsertElementInst>(
I) || isa<ExtractElementInst>(
I) ||
1108 isa<ShuffleVectorInst>(
I) || isa<ExtractValueInst>(
I) ||
1109 isa<InsertValueInst>(
I) || isa<FreezeInst>(
I));
1125 for (
const auto &Acc : *Accs) {
1126 if (isa<MemoryPhi>(&Acc))
1128 const auto *MUD = cast<MemoryUseOrDef>(&Acc);
1129 if (MUD->getMemoryInst() !=
I || NotAPhi++ == 1)
1139 bool TargetExecutesOncePerLoop,
1143 if (!isHoistableAndSinkableInst(
I))
1148 if (
LoadInst *LI = dyn_cast<LoadInst>(&
I)) {
1149 if (!LI->isUnordered())
1154 if (
AA->pointsToConstantMemory(LI->getOperand(0)))
1156 if (LI->hasMetadata(LLVMContext::MD_invariant_load))
1159 if (LI->isAtomic() && !TargetExecutesOncePerLoop)
1170 if (ORE && Invalidated && CurLoop->
isLoopInvariant(LI->getPointerOperand()))
1173 DEBUG_TYPE,
"LoadWithLoopInvariantAddressInvalidated", LI)
1174 <<
"failed to move load with loop-invariant address "
1175 "because the loop may invalidate its value";
1178 return !Invalidated;
1179 }
else if (
CallInst *CI = dyn_cast<CallInst>(&
I)) {
1181 if (isa<DbgInfoIntrinsic>(
I))
1192 if (CI->isConvergent())
1195 using namespace PatternMatch;
1196 if (
match(CI, m_Intrinsic<Intrinsic::assume>()))
1200 if (
match(CI, m_Intrinsic<Intrinsic::experimental_widenable_condition>()))
1208 if (AAResults::onlyReadsMemory(Behavior)) {
1212 if (AAResults::onlyAccessesArgPointees(Behavior)) {
1215 if (
Op->getType()->isPointerTy() &&
1225 if (isReadOnly(MSSAU, CurLoop))
1233 }
else if (
auto *FI = dyn_cast<FenceInst>(&
I)) {
1236 return isOnlyMemoryAccess(FI, CurLoop, MSSAU);
1237 }
else if (
auto *
SI = dyn_cast<StoreInst>(&
I)) {
1238 if (!
SI->isUnordered())
1246 if (isOnlyMemoryAccess(
SI, CurLoop, MSSAU))
1260 for (
const auto &MA : *Accesses)
1261 if (
const auto *MU = dyn_cast<MemoryUse>(&MA)) {
1272 }
else if (
const auto *MD = dyn_cast<MemoryDef>(&MA)) {
1273 if (
auto *LI = dyn_cast<LoadInst>(MD->getMemoryInst())) {
1275 assert(!LI->isUnordered() &&
"Expected unordered load");
1279 if (
auto *CI = dyn_cast<CallInst>(MD->getMemoryInst())) {
1296 assert(!
I.mayReadOrWriteMemory() &&
"unhandled aliasing");
1322 TargetTransformInfo::TCC_Free)
1328 for (
const User *U :
GEP->users()) {
1332 (!isa<StoreInst>(UI) && !isa<LoadInst>(UI))))
1337 return TTI->
getUserCost(&
I, TargetTransformInfo::TCK_SizeAndLatency) ==
1338 TargetTransformInfo::TCC_Free;
1350 bool LoopNestMode) {
1353 for (
const User *U :
I.users()) {
1355 if (
const PHINode *PN = dyn_cast<PHINode>(UI)) {
1358 if (isa<CatchSwitchInst>(
BB->getTerminator()))
1363 if (isa<CallInst>(
I))
1364 if (!BlockColors.empty() &&
1365 BlockColors.find(
const_cast<BasicBlock *
>(
BB))->second.size() != 1)
1369 while (isa<PHINode>(UI) && UI->
hasOneUser() &&
1373 UI = cast<Instruction>(UI->
user_back());
1393 if (
auto *CI = dyn_cast<CallInst>(&
I)) {
1400 for (
unsigned BundleIdx = 0, BundleEnd = CI->getNumOperandBundles();
1401 BundleIdx != BundleEnd; ++BundleIdx) {
1403 if (Bundle.
getTagID() == LLVMContext::OB_funclet)
1409 if (!BlockColors.empty()) {
1410 const ColorVector &CV = BlockColors.find(&ExitBlock)->second;
1411 assert(CV.
size() == 1 &&
"non-unique color for exit block!");
1418 New = CallInst::Create(CI, OpBundles);
1424 if (!
I.getName().empty())
1425 New->setName(
I.getName() +
".le");
1430 New,
nullptr, New->getParent(), MemorySSA::Beginning);
1432 if (
auto *MemDef = dyn_cast<MemoryDef>(NewMemAcc))
1435 auto *MemUse = cast<MemoryUse>(NewMemAcc);
1448 for (
Use &
Op : New->operands())
1450 auto *OInst = cast<Instruction>(
Op.get());
1453 OInst->getName() +
".lcssa", &ExitBlock.
front());
1465 I.eraseFromParent();
1474 I.moveBefore(&Dest);
1488 "Expect only trivially replaceable PHI");
1491 auto It = SunkCopies.
find(ExitBlock);
1492 if (It != SunkCopies.
end())
1496 *
I, *ExitBlock, *TPN, LI, SafetyInfo, MSSAU);
1502 if (!
BB->canSplitPredecessors())
1508 if (!SafetyInfo->
getBlockColors().empty() &&
BB->getFirstNonPHI()->isEHPad())
1511 if (isa<IndirectBrInst>(BBPred->getTerminator()) ||
1512 isa<CallBrInst>(BBPred->getTerminator()))
1529 assert(ExitBlockSet.
count(ExitBB) &&
"Expect the PHI is in an exit block.");
1565 while (!PredBBs.
empty()) {
1568 "Expect all predecessors are in the loop");
1571 ExitBB, PredBB,
".split.loop.exit", DT, LI, MSSAU,
true);
1575 if (!BlockColors.empty())
1594 bool Changed =
false;
1601 auto *
User = cast<Instruction>(*UI);
1602 Use &U = UI.getUse();
1640 UI =
I.user_begin();
1644 if (VisitedUsers.
empty())
1649 <<
"sinking " <<
ore::NV(
"Inst", &
I);
1651 if (isa<LoadInst>(
I))
1653 else if (isa<CallInst>(
I))
1673 for (
auto *UI :
Users) {
1674 auto *
User = cast<Instruction>(UI);
1681 "The LCSSA PHI is not in an exit block!");
1685 PN, &
I, LI, SunkCopies, SafetyInfo, CurLoop, MSSAU);
1715 if ((
I.hasMetadataOtherThanDebugLoc() || isa<CallInst>(
I)) &&
1720 I.dropUndefImplyingAttrsAndUnknownMetadata();
1722 if (isa<PHINode>(
I))
1729 I.updateLocationAfterHoist();
1731 if (isa<LoadInst>(
I))
1733 else if (isa<CallInst>(
I))
1745 bool AllowSpeculation) {
1749 bool GuaranteedToExecute =
1752 if (!GuaranteedToExecute) {
1753 auto *LI = dyn_cast<LoadInst>(&Inst);
1757 DEBUG_TYPE,
"LoadWithLoopInvariantAddressCondExecuted", LI)
1758 <<
"failed to hoist load with loop-invariant address "
1759 "because load is conditionally executed";
1763 return GuaranteedToExecute;
1778 bool UnorderedAtomic;
1781 bool CanInsertStoresInExitBlocks;
1794 I->getName() +
".lcssa", &
BB->front());
1810 LoopExitBlocks(LEB), LoopInsertPts(LIP), MSSAInsertPts(MSSAIP),
1811 PredCache(
PIC), MSSAU(MSSAU), LI(li),
DL(
std::
move(dl)),
1813 SafetyInfo(SafetyInfo),
1814 CanInsertStoresInExitBlocks(CanInsertStoresInExitBlocks) {}
1819 if (
LoadInst *LI = dyn_cast<LoadInst>(
I))
1820 Ptr = LI->getOperand(0);
1822 Ptr = cast<StoreInst>(
I)->getPointerOperand();
1823 return PointerMustAliases.
count(Ptr);
1826 void insertStoresInLoopExitBlocks() {
1831 for (
unsigned i = 0,
e = LoopExitBlocks.size();
i !=
e; ++
i) {
1833 Value *LiveInValue =
SSA.GetValueInMiddleOfBlock(ExitBlock);
1834 LiveInValue = maybeInsertLCSSAPHI(LiveInValue, ExitBlock);
1835 Value *Ptr = maybeInsertLCSSAPHI(SomePtr, ExitBlock);
1838 if (UnorderedAtomic)
1847 if (!MSSAInsertPoint) {
1849 NewSI,
nullptr, NewSI->
getParent(), MemorySSA::Beginning);
1854 MSSAInsertPts[
i] = NewMemAcc;
1855 MSSAU.
insertDef(cast<MemoryDef>(NewMemAcc),
true);
1861 if (CanInsertStoresInExitBlocks)
1862 insertStoresInLoopExitBlocks();
1871 if (isa<StoreInst>(
I))
1872 return CanInsertStoresInExitBlocks;
1877 bool isNotCapturedBeforeOrInLoop(
const Value *V,
const Loop *L,
1890 bool isNotVisibleOnUnwindInLoop(
const Value *Object,
const Loop *L,
1892 bool RequiresNoCaptureBeforeUnwind;
1896 return !RequiresNoCaptureBeforeUnwind ||
1897 isNotCapturedBeforeOrInLoop(Object, L, DT);
1916 assert(LI !=
nullptr && DT !=
nullptr && CurLoop !=
nullptr &&
1917 SafetyInfo !=
nullptr &&
1918 "Unexpected Input to promoteLoopAccessesToScalars");
1920 Value *SomePtr = *PointerMustAliases.
begin();
1960 bool DereferenceableInPH =
false;
1961 bool SafeToInsertStore =
false;
1962 bool FoundLoadToPromote =
false;
1970 bool SawUnorderedAtomic =
false;
1971 bool SawNotAtomic =
false;
1976 bool IsKnownThreadLocalObject =
false;
1984 if (!isNotVisibleOnUnwindInLoop(
Object, CurLoop, DT))
1988 IsKnownThreadLocalObject = !isa<AllocaInst>(
Object);
1994 Type *AccessTy =
nullptr;
1995 for (
Value *ASIV : PointerMustAliases) {
1998 Instruction *UI = dyn_cast<Instruction>(U.getUser());
2005 if (!
Load->isUnordered())
2008 SawUnorderedAtomic |=
Load->isAtomic();
2009 SawNotAtomic |= !
Load->isAtomic();
2010 FoundLoadToPromote =
true;
2018 if (!DereferenceableInPH || (InstAlignment > Alignment))
2020 *
Load, DT, TLI, CurLoop, SafetyInfo, ORE,
2022 DereferenceableInPH =
true;
2023 Alignment =
std::max(Alignment, InstAlignment);
2030 if (!
Store->isUnordered())
2033 SawUnorderedAtomic |=
Store->isAtomic();
2034 SawNotAtomic |= !
Store->isAtomic();
2043 if (!DereferenceableInPH || !SafeToInsertStore ||
2044 (InstAlignment > Alignment)) {
2046 DereferenceableInPH =
true;
2047 SafeToInsertStore =
true;
2048 Alignment =
std::max(Alignment, InstAlignment);
2058 if (!SafeToInsertStore)
2065 if (!DereferenceableInPH) {
2067 Store->getPointerOperand(),
Store->getValueOperand()->getType(),
2079 if (LoopUses.empty()) {
2082 }
else if (AATags) {
2086 LoopUses.push_back(UI);
2094 if (SawUnorderedAtomic && SawNotAtomic)
2104 if (!DereferenceableInPH)
2111 if (!SafeToInsertStore) {
2112 if (IsKnownThreadLocalObject)
2113 SafeToInsertStore =
true;
2118 isNotCapturedBeforeOrInLoop(
Object, CurLoop, DT);
2124 if (!SafeToInsertStore && !FoundLoadToPromote)
2129 if (SafeToInsertStore)
2130 LLVM_DEBUG(
dbgs() <<
"LICM: Promoting load/store of the value: " << *SomePtr
2133 LLVM_DEBUG(
dbgs() <<
"LICM: Promoting load of the value: " << *SomePtr
2139 <<
"Moving accesses to memory location out of the loop";
2144 std::vector<const DILocation *> LoopUsesLocs;
2145 for (
auto U : LoopUses)
2146 LoopUsesLocs.push_back(U->getDebugLoc().get());
2147 auto DL =
DebugLoc(DILocation::getMergedLocations(LoopUsesLocs));
2152 LoopPromoter Promoter(SomePtr, LoopUses,
SSA, PointerMustAliases, ExitBlocks,
2153 InsertPts, MSSAInsertPts,
PIC, MSSAU, *LI,
DL,
2154 Alignment, SawUnorderedAtomic, AATags, *SafetyInfo,
2160 AccessTy, SomePtr, SomePtr->
getName() +
".promoted",
2162 if (SawUnorderedAtomic)
2168 SSA.AddAvailableValue(Preheader, PreheaderLoad);
2171 PreheaderLoad,
nullptr, PreheaderLoad->
getParent(), MemorySSA::End);
2172 MemoryUse *NewMemUse = cast<MemoryUse>(PreheaderLoadMemoryAccess);
2179 Promoter.run(LoopUses);
2194 for (
const auto &Access : *Accesses)
2195 if (
const auto *MUD = dyn_cast<MemoryUseOrDef>(&Access))
2196 Fn(MUD->getMemoryInst());
2203 auto IsPotentiallyPromotable = [L](
const Instruction *
I) {
2204 if (
const auto *
SI = dyn_cast<StoreInst>(
I))
2206 if (
const auto *LI = dyn_cast<LoadInst>(
I))
2214 if (IsPotentiallyPromotable(
I)) {
2215 AttemptingPromotion.
insert(
I);
2223 if (!AS.isForwardingAliasSet() && AS.isMod() && AS.isMustAlias())
2224 Sets.push_back(&AS);
2235 return AS->aliasesUnknownInst(I, *AA);
2242 for (
const auto &ASI : *Set)
2243 PointerMustAliases.
insert(ASI.getValue());
2244 Result.push_back(
std::move(PointerMustAliases));
2298 for (
const auto &MA : *Accesses)
2299 if (
const auto *MD = dyn_cast<MemoryDef>(&MA))
A set of analyses that are preserved following a run of a transformation pass.
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...
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
This is an optimization pass for GlobalISel generic memory operations.
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,...
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
void initializeLegacyLICMPassPass(PassRegistry &)
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
op_range incoming_values()
A parsed version of the target data layout string in and methods for querying it.
InstListType::iterator iterator
Instruction iterators...
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=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 ...
LLVM_NODISCARD bool isModOrRefSet(const ModRefInfo MRI)
const Function * getParent() const
Return the enclosing method, or null if none.
bool hoistRegion(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *, BlockFrequencyInfo *, 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,...
Interval::succ_iterator succ_end(Interval *I)
void forgetLoopDispositions(const Loop *L)
Called when the client has changed the disposition of values in this loop.
ScalarTy getFixedSize() const
Represents a single loop in the control flow graph.
PredIteratorCache - This class is an extremely trivial cache for predecessor iterator queries.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
static bool isDereferenceableAndAlignedPointer(const Value *V, Align Alignment, const APInt &Size, const DataLayout &DL, const Instruction *CtxI, const DominatorTree *DT, const TargetLibraryInfo *TLI, SmallPtrSetImpl< const Value * > &Visited, unsigned MaxDepth)
Test if V is always a pointer to allocated and suitably aligned memory for a simple load or store.
bool insert(const T &X)
Insert a new element into the PriorityWorklist.
cl::opt< unsigned > SetLicmMssaNoAccForPromotionCap
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
TypeSize getTypeStoreSize(Type *Ty) const
Returns the maximum number of bytes that may be overwritten by storing the specified type.
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...
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
static bool isLoadInvariantInLoop(LoadInst *LI, DominatorTree *DT, Loop *CurLoop)
The main scalar evolution driver.
bool dominates(const MemoryAccess *A, const MemoryAccess *B) const
Given two memory accesses in potentially different blocks, determine whether MemoryAccess A dominates...
static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU)
bool tooManyClobberingCalls()
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
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...
static void getLazyBFIAnalysisUsage(AnalysisUsage &AU)
Helper for client passes to set up the analysis usage on behalf of this pass.
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)"))
The instances of the Type class are immutable: once they are created, they are never changed.
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
The legacy pass manager's analysis pass to compute loop information.
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
void setAlignment(Align Align)
PassInstrumentationCallbacks PIC
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
bool hasDisableLICMTransformsHint(const Loop *L)
Look for the loop attribute that disables the LICM transformation heuristics.
static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT, BlockFrequencyInfo *BFI, 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 cl::opt< bool > ControlFlowHoisting("licm-control-flow-hoisting", cl::Hidden, cl::init(false), cl::desc("Enable control flow (and PHI) hoisting in LICM"))
bool hasOneUser() const
Return true if there is exactly one user of this value.
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
DiagnosticInfoOptimizationBase::Argument NV
unsigned LicmMssaNoAccForPromotionCap
DomTreeNodeBase * getIDom() const
Represents read-only accesses to memory.
void incrementClobberingCalls()
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 ...
bool isScalable() const
Returns whether the size is scaled by a runtime quantity (vscale).
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...
bool sinkRegionForLoopNest(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *, BlockFrequencyInfo *, TargetLibraryInfo *, TargetTransformInfo *, Loop *, MemorySSAUpdater &, ICFLoopSafetyInfo *, SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *)
Call sinkRegion on loops contained within the specified loop in order from innermost to outermost.
static Instruction * cloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI, const LoopSafetyInfo *SafetyInfo, MemorySSAUpdater &MSSAU)
This is an alternative analysis pass to BlockFrequencyInfoWrapperPass.
LLVM Basic Block Representation.
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
bool remove(const value_type &X)
Remove an item from the set vector.
This is the shared class of boolean and integer constants.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
void insertUse(MemoryUse *Use, bool RenameUses=false)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
void setOrdering(AtomicOrdering Ordering)
Sets the ordering constraint of this store instruction.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
bool isNoAliasCall(const Value *V)
Return true if this pointer is returned by a noalias function.
Legacy analysis pass which computes MemorySSA.
iterator begin()
Get an iterator to the beginning of the SetVector.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
static SmallVector< SmallSetVector< Value *, 8 >, 0 > collectPromotionCandidates(MemorySSA *MSSA, AliasAnalysis *AA, Loop *L)
bool match(Val *V, const Pattern &P)
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,...
Captures loop safety information.
bool isLiveOnEntryDef(const MemoryAccess *MA) const
Return true if MA represents the live on entry value.
static void foreachMemoryAccess(MemorySSA *MSSA, Loop *L, function_ref< void(Instruction *)> Fn)
size_t size(BasicBlock *BB) const
SinkAndHoistLICMFlags(unsigned LicmMssaOptCap, unsigned LicmMssaNoAccForPromotionCap, bool IsSink, Loop *L=nullptr, MemorySSA *MSSA=nullptr)
(vector float) vec_cmpeq(*A, *B) C
Flags controlling how much is checked when sinking or hoisting instructions.
bool promoteLoopAccessesToScalars(const SmallSetVector< Value *, 8 > &, SmallVectorImpl< BasicBlock * > &, SmallVectorImpl< Instruction * > &, SmallVectorImpl< MemoryAccess * > &, PredIteratorCache &, LoopInfo *, DominatorTree *, const TargetLibraryInfo *, Loop *, MemorySSAUpdater &, ICFLoopSafetyInfo *, OptimizationRemarkEmitter *, bool AllowSpeculation)
Try to promote memory values to scalars by sinking stores out of the loop and moving loads to before ...
Represent the analysis usage information of a pass.
LLVM_NODISCARD T pop_back_val()
void ReplaceInstWithInst(BasicBlock::InstListType &BIL, BasicBlock::iterator &BI, Instruction *I)
Replace the instruction specified by BI with the instruction specified by I.
iterator_range< block_iterator > blocks() const
const DenseMap< BasicBlock *, ColorVector > & getBlockColors() const
Returns block colors map that is used to update funclet operand bundles.
iterator_range< use_iterator > uses()
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Legacy analysis pass which computes a DominatorTree.
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
STATISTIC(NumFunctions, "Total number of functions")
auto predecessors(MachineBasicBlock *BB)
This class implements an extremely fast bulk output stream that can only output to a stream.
const AccessList * getBlockAccesses(const BasicBlock *BB) const
Return the list of MemoryAccess's for a given basic block.
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
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...
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
This struct is a compact representation of a valid (non-zero power of two) alignment.
bool empty() const
Determine if the SetVector is empty or not.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
BasicBlock * getBlock() const
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
bool locallyDominates(const MemoryAccess *A, const MemoryAccess *B) const
Given two memory accesses in the same basic block, determine whether MemoryAccess A dominates MemoryA...
uint32_t getTagID() const
Return the tag of this operand bundle as an integer.
Value * getCondition() const
An efficient, type-erasing, non-owning reference to a callable.
static bool isTriviallyReplaceablePHI(const PHINode &PN, const Instruction &I)
Returns true if a PHINode is a trivially replaceable with an Instruction.
MemoryAccess * getClobberingMemoryAccess(const Instruction *I)
Given a memory Mod/Ref/ModRef'ing instruction, calling this will give you the nearest dominating Memo...
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
unsigned getPointerAddressSpace() const
Returns the address space of the pointer operand.
An instruction for storing to memory.
This is an important base class in LLVM.
void add(Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo)
These methods are used to add different types of instructions to the alias sets.
std::string getNameOrAsOperand() const
loop versioning Loop Versioning For LICM
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
void setOrdering(AtomicOrdering Ordering)
Sets the ordering constraint of this load instruction.
void getUniqueExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
void setIncomingBlock(unsigned i, BasicBlock *BB)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
A version of PriorityWorklist that selects small size optimized data structures for the vector and ma...
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
This is an important class for using LLVM in a threaded context.
bool anyBlockMayThrow() const override
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
Encapsulates MemorySSA, including all data associated with memory accesses.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
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...
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
void setAlignment(Align Align)
initializer< Ty > init(const Ty &Val)
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...
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
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...
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...
bool empty() const
Determine if the PriorityWorklist is empty or not.
static void splitPredecessorsOfLoopExit(PHINode *PN, DominatorTree *DT, LoopInfo *LI, const Loop *CurLoop, LoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU)
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find iterator find(const_arg_type_t< KeyT > Val)
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
PreservedAnalyses run(LoopNest &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
StandardInstrumentations SI(Debug, VerifyEach)
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
static bool isFreeInLoop(const Instruction &I, const Loop *CurLoop, const TargetTransformInfo *TTI)
Return true if the instruction is free in the loop.
static bool isSafeToExecuteUnconditionally(Instruction &Inst, const DominatorTree *DT, const TargetLibraryInfo *TLI, const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE, const Instruction *CtxI, bool AllowSpeculation)
Only sink or hoist an instruction if it is not a trapping instruction, or if the instruction is known...
void salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I.
static bool pointerInvalidatedByBlock(BasicBlock &BB, MemorySSA &MSSA, MemoryUse &MU)
@ FMRB_DoesNotAccessMemory
This function does not perform any non-local loads or stores to memory.
Loop & getOutermostLoop() const
Return the outermost loop in the loop nest.
An analysis that produces MemorySSA for a function.
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.
static bool hasProfileData(const Function &F, const FunctionOutliningInfo &OI)
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
bool insert(const value_type &X)
Insert a new element into the SetVector.
MemoryUseOrDef * createMemoryAccessAfter(Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt)
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
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.
AAMDNodes merge(const AAMDNodes &Other) const
Given two sets of AAMDNodes applying to potentially different locations, determine the best AAMDNodes...
void insertDef(MemoryDef *Def, bool RenameUses=false)
Insert a definition into the MemorySSA IR.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
MemorySSAWalker * getSkipSelfWalker()
StringRef - Represent a constant reference to a string, i.e.
Loop Invariant Code Motion
Type * getType() const
All values are typed, get the type of this value.
const DefsList * getBlockDefs(const BasicBlock *BB) const
Return the list of MemoryDef's and MemoryPhi's for a given basic block.
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...
unsigned pred_size(const BasicBlock *BB)
Get the number of predecessors of BB.
void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
bool isOutermost() const
Return true if the loop does not have a parent (natural) loop.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
A lightweight accessor for an operand bundle meant to be passed around by value.
LLVMContext & getContext() const
All values hold a context through their type.
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
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.
FunctionModRefBehavior
Summary of how a function affects memory in the program.
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
Function * getParent() const
Return the function to which the loop-nest belongs.
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
bool hasLoopInvariantOperands(const Instruction *I) const
Return true if all the operands of the specified instruction are loop invariant.
StringRef getName() const
Return a constant reference to the value's name.
An instruction for reading from memory.
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
unsigned const MachineRegisterInfo * MRI
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
const Instruction & front() const
void ensureOptimizedUses()
By default, uses are not optimized during MemorySSA construction.
void removeInstruction(const Instruction *Inst)
Inform safety info that we are planning to remove the instruction Inst from its block.
static unsigned getPointerOperandIndex(Instruction *I)
bool isLCSSAForm(const DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
user_iterator_impl< User > user_iterator
MemoryAccess * getDefiningAccess() const
Get the access that produces the memory state used by this Use.
TargetTransformInfo & TTI
Should compile to something r4 addze r3 instead we get
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end iterator end()
This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to give precise answers on "may...
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
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...
void wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New, ArrayRef< BasicBlock * > Preds, bool IdenticalEdgesWereMerged=true)
A new empty BasicBlock (New) now branches directly to Old.
Interval::pred_iterator pred_end(Interval *I)
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...
void setAAMetadata(const AAMDNodes &N)
Sets the AA metadata on this instruction from the AAMDNodes structure.
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
BlockT * getHeader() const
unsigned MssaNoAccForPromotionCap
static Instruction * sinkThroughTriviallyReplaceablePHI(PHINode *TPN, Instruction *I, LoopInfo *LI, SmallDenseMap< BasicBlock *, Instruction *, 32 > &SunkCopies, const LoopSafetyInfo *SafetyInfo, const Loop *CurLoop, MemorySSAUpdater &MSSAU)
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
void salvageDebugInfo(Instruction &I)
Assuming the instruction I is going to be deleted, attempt to salvage debug users of I by writing the...
Provides information about what library functions are available for the current target.
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Class that has the common methods + fields of memory uses/defs.
bool hasProfileData(bool IncludeSynthetic=false) const
Return true if the function is annotated with profile data.
void copyColors(BasicBlock *New, BasicBlock *Old)
Copy colors of block Old into the block New.
QP Compare Ordered Unordered
A wrapper class for inspecting calls to intrinsic functions.
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.
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...
Analysis pass which computes a DominatorTree.
const InstListType & getInstList() const
Return the underlying instruction list container.
Pass interface - Implemented by all 'passes'.
unsigned getNumOperands() const
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
void moveBefore(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it into the function that MovePos lives ...
static void moveInstructionBefore(Instruction &I, Instruction &Dest, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU, ScalarEvolution *SE)
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Value * getArgOperand(unsigned i) const
LLVM_NODISCARD bool empty() const
const BasicBlock * getParent() const
void computeLoopSafetyInfo(const Loop *CurLoop) override
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Align max(MaybeAlign Lhs, Align Rhs)
INITIALIZE_PASS_BEGIN(LegacyLICMPass, "licm", "Loop Invariant Code Motion", false, false) INITIALIZE_PASS_END(LegacyLICMPass
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
iv Induction Variable Users
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...
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<>...
ArrayRef< BasicBlock * > get(BasicBlock *BB)
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
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.
A SetVector that performs no allocations if smaller than a certain size.
A container for analyses that lazily runs them and caches their results.
static bool pointerInvalidatedByLoop(MemorySSA *MSSA, MemoryUse *MU, Loop *CurLoop, Instruction &I, SinkAndHoistLICMFlags &Flags)
This class represents a function call, abstracting a target machine's calling convention.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
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...
AnalysisUsage & addRequired()
bool VerifyMemorySSA
Enables verification of MemorySSA.
bool tooManyMemoryAccesses()
Value * getOperand(unsigned i) const
Conditional or Unconditional Branch instruction.
Constant * ConstantFoldInstruction(Instruction *I, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstruction - Try to constant fold the specified instruction.
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
Helper class for SSA formation on a set of values defined in multiple blocks.
bool contains(ConstPtrType Ptr) const
void reserve(size_type N)
cl::opt< unsigned > SetLicmMssaOptCap
This is an alternative analysis pass to BranchProbabilityInfoWrapperPass.
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...
This class represents a loop nest and can be used to query its properties.
LLVM Value Representation.
bool isConditional() const
bool sinkRegion(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *, BlockFrequencyInfo *, 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,...
BasicBlock * getSuccessor(unsigned i) const
Analysis pass that exposes the LoopInfo for a function.
void removeMemoryAccess(MemoryAccess *, bool OptimizePhis=false)
Remove a MemoryAccess from MemorySSA, including updating all definitions and uses.
bool wouldBeOutOfLoopUseRequiringLCSSA(const Value *V, const BasicBlock *ExitBB) const
static bool canSplitPredecessors(PHINode *PN, LoopSafetyInfo *SafetyInfo)
A Use represents the edge between a Value definition and its users.
reference emplace_back(ArgTypes &&... Args)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.