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");
111STATISTIC(NumFPAssociationsHoisted,
"Number of invariant FP expressions "
112 "reassociated and hoisted out of the loop");
114 "Number of invariant int expressions "
115 "reassociated and hoisted out of the loop");
120 cl::desc(
"Disable memory promotion in LICM pass"));
124 cl::desc(
"Enable control flow (and PHI) hoisting in LICM"));
128 cl::desc(
"Force thread model single in LICM pass"));
132 cl::desc(
"Max num uses visited for identifying load "
133 "invariance in loop using invariant start (default = 8)"));
138 "Set upper limit for the number of transformations performed "
139 "during a single round of hoisting the reassociated expressions."));
144 "Set upper limit for the number of transformations performed "
145 "during a single round of hoisting the reassociated expressions."));
157 cl::desc(
"Enable imprecision in LICM in pathological cases, in exchange "
158 "for faster compile. Caps the MemorySSA clobbering calls."));
165 cl::desc(
"[LICM & MemorySSA] When MSSA in LICM is disabled, this has no "
166 "effect. When MSSA in LICM is enabled, then this is the maximum "
167 "number of accesses allowed to be present in a loop in order to "
168 "enable memory promotion."));
174 bool &FoldableInLoop,
bool LoopNestMode);
190 bool InvariantGroup);
212 std::pair<SmallSetVector<Value *, 8>,
bool>;
217struct LoopInvariantCodeMotion {
223 LoopInvariantCodeMotion(
unsigned LicmMssaOptCap,
224 unsigned LicmMssaNoAccForPromotionCap,
225 bool LicmAllowSpeculation)
226 : LicmMssaOptCap(LicmMssaOptCap),
227 LicmMssaNoAccForPromotionCap(LicmMssaNoAccForPromotionCap),
228 LicmAllowSpeculation(LicmAllowSpeculation) {}
231 unsigned LicmMssaOptCap;
232 unsigned LicmMssaNoAccForPromotionCap;
233 bool LicmAllowSpeculation;
236struct LegacyLICMPass :
public LoopPass {
241 bool LicmAllowSpeculation =
true)
242 :
LoopPass(
ID), LICM(LicmMssaOptCap, LicmMssaNoAccForPromotionCap,
243 LicmAllowSpeculation) {
252 <<
L->getHeader()->getNameOrAsOperand() <<
"\n");
256 auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
257 MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
262 return LICM.runOnLoop(
263 L, &getAnalysis<AAResultsWrapperPass>().getAAResults(),
264 &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
265 &getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
266 &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(*
F),
267 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(*
F),
268 &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(*
F),
269 SE ? &SE->getSE() :
nullptr, MSSA, &ORE);
290 LoopInvariantCodeMotion LICM;
307 if (!LICM.runOnLoop(&L, &AR.
AA, &AR.
LI, &AR.
DT, &AR.
AC, &AR.
TLI, &AR.
TTI,
320 OS, MapClassName2PassName);
343 bool Changed = LICM.runOnLoop(&OutermostLoop, &AR.
AA, &AR.
LI, &AR.
DT, &AR.
AC,
361 OS, MapClassName2PassName);
368char LegacyLICMPass::ID = 0;
387 unsigned LicmMssaOptCap,
unsigned LicmMssaNoAccForPromotionCap,
bool IsSink,
389 : LicmMssaOptCap(LicmMssaOptCap),
390 LicmMssaNoAccForPromotionCap(LicmMssaNoAccForPromotionCap),
392 unsigned AccessCapCount = 0;
393 for (
auto *BB : L.getBlocks())
395 for (
const auto &MA : *Accesses) {
415 bool Changed =
false;
417 assert(L->isLCSSAForm(*DT) &&
"Loop is not in LCSSA form.");
435 return llvm::any_of(*BB, [](Instruction &I) {
436 IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I);
437 return II && II->getIntrinsicID() == Intrinsic::coro_suspend;
461 if (
L->hasDedicatedExits())
465 TLI,
TTI, L, MSSAU, &SafetyInfo, Flags, ORE)
467 MSSAU, &SafetyInfo,
Flags, ORE);
468 Flags.setIsSink(
false);
471 MSSAU, SE, &SafetyInfo, Flags, ORE, LoopNestMode,
472 LicmAllowSpeculation);
482 !
Flags.tooManyMemoryAccesses() && !HasCoroSuspendInst) {
485 L->getUniqueExitBlocks(ExitBlocks);
489 return isa<CatchSwitchInst>(
Exit->getTerminator());
492 if (!HasCatchSwitch) {
498 InsertPts.
push_back(ExitBlock->getFirstInsertionPt());
506 bool Promoted =
false;
509 LocalPromoted =
false;
510 for (
auto [PointerMustAliases, HasReadsOutsideSet] :
513 PointerMustAliases, ExitBlocks, InsertPts, MSSAInsertPts,
PIC, LI,
514 DT, AC, TLI,
TTI, L, MSSAU, &SafetyInfo, ORE,
515 LicmAllowSpeculation, HasReadsOutsideSet);
517 Promoted |= LocalPromoted;
518 }
while (LocalPromoted);
536 assert(
L->isLCSSAForm(*DT) &&
"Loop not left in LCSSA form after LICM!");
537 assert((
L->isOutermost() ||
L->getParentLoop()->isLCSSAForm(*DT)) &&
538 "Parent loop not left in LCSSA form after LICM!");
561 assert(
N !=
nullptr && AA !=
nullptr && LI !=
nullptr && DT !=
nullptr &&
562 CurLoop !=
nullptr && SafetyInfo !=
nullptr &&
563 "Unexpected input to sinkRegion.");
570 bool Changed =
false;
598 bool FoldableInLoop =
false;
599 bool LoopNestMode = OutermostLoop !=
nullptr;
600 if (!
I.mayHaveSideEffects() &&
602 SafetyInfo,
TTI, FoldableInLoop,
605 if (
sink(
I, LI, DT, CurLoop, SafetyInfo, MSSAU, ORE)) {
606 if (!FoldableInLoop) {
629 bool Changed =
false;
633 while (!Worklist.
empty()) {
636 MSSAU, SafetyInfo, Flags, ORE, CurLoop);
649class ControlFlowHoister {
668 : LI(LI), DT(DT), CurLoop(CurLoop), MSSAU(MSSAU) {}
670 void registerPossiblyHoistableBranch(
BranchInst *BI) {
682 TrueDest == FalseDest)
694 if (TrueDestSucc.
count(FalseDest)) {
695 CommonSucc = FalseDest;
696 }
else if (FalseDestSucc.
count(TrueDest)) {
697 CommonSucc = TrueDest;
701 if (TrueDestSucc.
size() == 1)
702 CommonSucc = *TrueDestSucc.
begin();
706 else if (!TrueDestSucc.
empty()) {
710 assert(It !=
F->end() &&
"Could not find successor in function");
722 if (CommonSucc && DT->
dominates(BI, CommonSucc))
723 HoistableBranches[BI] = CommonSucc;
726 bool canHoistPHI(
PHINode *PN) {
735 PredecessorBlocks.
insert(PredBB);
743 for (
auto &Pair : HoistableBranches) {
744 if (Pair.second == BB) {
747 if (Pair.first->getSuccessor(0) == BB) {
748 PredecessorBlocks.
erase(Pair.first->getParent());
749 PredecessorBlocks.
erase(Pair.first->getSuccessor(1));
750 }
else if (Pair.first->getSuccessor(1) == BB) {
751 PredecessorBlocks.
erase(Pair.first->getParent());
752 PredecessorBlocks.
erase(Pair.first->getSuccessor(0));
754 PredecessorBlocks.
erase(Pair.first->getSuccessor(0));
755 PredecessorBlocks.
erase(Pair.first->getSuccessor(1));
761 return PredecessorBlocks.
empty();
768 if (HoistDestinationMap.
count(BB))
769 return HoistDestinationMap[BB];
772 auto HasBBAsSuccessor =
774 return BB != Pair.second && (Pair.first->getSuccessor(0) == BB ||
775 Pair.first->getSuccessor(1) == BB);
777 auto It =
llvm::find_if(HoistableBranches, HasBBAsSuccessor);
781 if (It == HoistableBranches.end()) {
784 <<
" as hoist destination for "
786 HoistDestinationMap[BB] = InitialPreheader;
787 return InitialPreheader;
790 assert(std::find_if(++It, HoistableBranches.end(), HasBBAsSuccessor) ==
791 HoistableBranches.end() &&
792 "BB is expected to be the target of at most one branch");
797 BasicBlock *CommonSucc = HoistableBranches[BI];
801 auto CreateHoistedBlock = [&](
BasicBlock *Orig) {
802 if (HoistDestinationMap.
count(Orig))
803 return HoistDestinationMap[Orig];
806 HoistDestinationMap[Orig] =
New;
812 <<
" as hoist destination for " << Orig->getName()
816 BasicBlock *HoistTrueDest = CreateHoistedBlock(TrueDest);
817 BasicBlock *HoistFalseDest = CreateHoistedBlock(FalseDest);
818 BasicBlock *HoistCommonSucc = CreateHoistedBlock(CommonSucc);
825 assert(TargetSucc &&
"Expected hoist target to have a single successor");
840 if (HoistTarget == InitialPreheader) {
851 for (
auto &Pair : HoistDestinationMap)
852 if (Pair.second == InitialPreheader && Pair.first != BI->
getParent())
853 Pair.second = HoistCommonSucc;
863 "Hoisting blocks should not have destroyed preheader");
864 return HoistDestinationMap[BB];
881 bool AllowSpeculation) {
883 assert(
N !=
nullptr && AA !=
nullptr && LI !=
nullptr && DT !=
nullptr &&
884 CurLoop !=
nullptr && SafetyInfo !=
nullptr &&
885 "Unexpected input to hoistRegion.");
887 ControlFlowHoister CFH(LI, DT, CurLoop, MSSAU);
898 bool Changed =
false;
903 if (!LoopNestMode &&
inSubLoop(BB, CurLoop, LI))
917 I, DT, TLI, CurLoop, SafetyInfo, ORE,
919 hoist(
I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
928 if (
I.getOpcode() == Instruction::FDiv &&
I.hasAllowReciprocal() &&
930 auto Divisor =
I.getOperand(1);
931 auto One = llvm::ConstantFP::get(Divisor->getType(), 1.0);
932 auto ReciprocalDivisor = BinaryOperator::CreateFDiv(One, Divisor);
933 ReciprocalDivisor->setFastMathFlags(
I.getFastMathFlags());
935 ReciprocalDivisor->insertBefore(&
I);
938 BinaryOperator::CreateFMul(
I.getOperand(0), ReciprocalDivisor);
939 Product->setFastMathFlags(
I.getFastMathFlags());
941 Product->insertAfter(&
I);
942 I.replaceAllUsesWith(Product);
945 hoist(*ReciprocalDivisor, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB),
946 SafetyInfo, MSSAU, SE, ORE);
947 HoistedInstructions.
push_back(ReciprocalDivisor);
953 using namespace PatternMatch;
954 return I.use_empty() &&
955 match(&
I, m_Intrinsic<Intrinsic::invariant_start>());
957 auto MustExecuteWithoutWritesBefore = [&](
Instruction &
I) {
961 if ((IsInvariantStart(
I) ||
isGuard(&
I)) &&
963 MustExecuteWithoutWritesBefore(
I)) {
964 hoist(
I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
971 if (
PHINode *PN = dyn_cast<PHINode>(&
I)) {
972 if (CFH.canHoistPHI(PN)) {
978 hoist(*PN, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
996 CFH.registerPossiblyHoistableBranch(BI);
1011 [&](
Use &U) { return DT->dominates(I, U); })) {
1017 "New hoist point expected to dominate old hoist point");
1022 <<
": " << *
I <<
"\n");
1035#ifdef EXPENSIVE_CHECKS
1037 assert(DT->
verify(DominatorTree::VerificationLevel::Fast) &&
1038 "Dominator tree verification failed");
1070 if (isa<Constant>(
Addr))
1073 unsigned UsesVisited = 0;
1076 for (
auto *U :
Addr->users()) {
1110 return (isa<LoadInst>(
I) || isa<StoreInst>(
I) || isa<CallInst>(
I) ||
1111 isa<FenceInst>(
I) || isa<CastInst>(
I) || isa<UnaryOperator>(
I) ||
1112 isa<BinaryOperator>(
I) || isa<SelectInst>(
I) ||
1113 isa<GetElementPtrInst>(
I) || isa<CmpInst>(
I) ||
1114 isa<InsertElementInst>(
I) || isa<ExtractElementInst>(
I) ||
1115 isa<ShuffleVectorInst>(
I) || isa<ExtractValueInst>(
I) ||
1116 isa<InsertValueInst>(
I) || isa<FreezeInst>(
I));
1120 for (
auto *BB :
L->getBlocks())
1129 for (
auto *BB :
L->getBlocks())
1132 for (
const auto &Acc : *Accs) {
1133 if (isa<MemoryPhi>(&Acc))
1135 const auto *MUD = cast<MemoryUseOrDef>(&Acc);
1136 if (MUD->getMemoryInst() !=
I || NotAPhi++ == 1)
1149 if (Flags.tooManyClobberingCalls())
1154 Flags.incrementClobberingCalls();
1160 bool TargetExecutesOncePerLoop,
1164 if (!isHoistableAndSinkableInst(
I))
1169 if (
LoadInst *LI = dyn_cast<LoadInst>(&
I)) {
1170 if (!LI->isUnordered())
1177 if (LI->hasMetadata(LLVMContext::MD_invariant_load))
1180 if (LI->isAtomic() && !TargetExecutesOncePerLoop)
1189 bool InvariantGroup = LI->hasMetadata(LLVMContext::MD_invariant_group);
1192 MSSA, MU, CurLoop,
I, Flags, InvariantGroup);
1198 DEBUG_TYPE,
"LoadWithLoopInvariantAddressInvalidated", LI)
1199 <<
"failed to move load with loop-invariant address "
1200 "because the loop may invalidate its value";
1204 }
else if (
CallInst *CI = dyn_cast<CallInst>(&
I)) {
1206 if (isa<DbgInfoIntrinsic>(
I))
1217 if (CI->isConvergent())
1225 if (CI->getFunction()->isPresplitCoroutine())
1228 using namespace PatternMatch;
1229 if (
match(CI, m_Intrinsic<Intrinsic::assume>()))
1245 if (
Op->getType()->isPointerTy() &&
1255 if (isReadOnly(MSSAU, CurLoop))
1263 }
else if (
auto *FI = dyn_cast<FenceInst>(&
I)) {
1266 return isOnlyMemoryAccess(FI, CurLoop, MSSAU);
1267 }
else if (
auto *SI = dyn_cast<StoreInst>(&
I)) {
1268 if (!SI->isUnordered())
1276 if (isOnlyMemoryAccess(SI, CurLoop, MSSAU))
1280 if (Flags.tooManyMemoryAccesses())
1288 CurLoop->
contains(Source->getBlock()))
1298 for (
const auto &MA : *Accesses)
1299 if (
const auto *MU = dyn_cast<MemoryUse>(&MA)) {
1309 if (!Flags.getIsSink() && !MSSA->
dominates(SIMD, MU))
1311 }
else if (
const auto *MD = dyn_cast<MemoryDef>(&MA)) {
1312 if (
auto *LI = dyn_cast<LoadInst>(MD->getMemoryInst())) {
1314 assert(!LI->isUnordered() &&
"Expected unordered load");
1318 if (
auto *CI = dyn_cast<CallInst>(MD->getMemoryInst())) {
1331 assert(!
I.mayReadOrWriteMemory() &&
"unhandled aliasing");
1354 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(&
I)) {
1363 for (
const User *U :
GEP->users()) {
1367 (!isa<StoreInst>(UI) && !isa<LoadInst>(UI))))
1385 bool &FoldableInLoop,
bool LoopNestMode) {
1388 for (
const User *U :
I.users()) {
1390 if (
const PHINode *PN = dyn_cast<PHINode>(UI)) {
1398 if (isa<CallInst>(
I))
1399 if (!BlockColors.empty() &&
1400 BlockColors.find(
const_cast<BasicBlock *
>(BB))->second.size() != 1)
1404 while (isa<PHINode>(UI) && UI->
hasOneUser() &&
1408 UI = cast<Instruction>(UI->
user_back());
1415 FoldableInLoop =
true;
1428 if (
auto *CI = dyn_cast<CallInst>(&
I)) {
1435 for (
unsigned BundleIdx = 0, BundleEnd = CI->getNumOperandBundles();
1436 BundleIdx != BundleEnd; ++BundleIdx) {
1444 if (!BlockColors.empty()) {
1445 const ColorVector &CV = BlockColors.find(&ExitBlock)->second;
1446 assert(CV.
size() == 1 &&
"non-unique color for exit block!");
1459 if (!
I.getName().empty())
1460 New->setName(
I.getName() +
".le");
1467 if (
auto *MemDef = dyn_cast<MemoryDef>(NewMemAcc))
1470 auto *MemUse = cast<MemoryUse>(NewMemAcc);
1483 for (
Use &
Op : New->operands())
1485 auto *OInst = cast<Instruction>(
Op.get());
1488 OInst->getName() +
".lcssa");
1501 I.eraseFromParent();
1510 I.moveBefore(*Dest->getParent(), Dest);
1525 "Expect only trivially replaceable PHI");
1528 auto It = SunkCopies.
find(ExitBlock);
1529 if (It != SunkCopies.
end())
1533 *
I, *ExitBlock, *TPN, LI, SafetyInfo, MSSAU);
1548 if (isa<IndirectBrInst>(BBPred->getTerminator()))
1565 assert(ExitBlockSet.
count(ExitBB) &&
"Expect the PHI is in an exit block.");
1601 while (!PredBBs.
empty()) {
1604 "Expect all predecessors are in the loop");
1607 ExitBB, PredBB,
".split.loop.exit", DT, LI, MSSAU,
true);
1611 if (!BlockColors.empty())
1629 bool Changed =
false;
1636 auto *
User = cast<Instruction>(*UI);
1637 Use &U = UI.getUse();
1675 UI =
I.user_begin();
1679 if (VisitedUsers.
empty())
1684 <<
"sinking " <<
ore::NV(
"Inst", &
I);
1686 if (isa<LoadInst>(
I))
1688 else if (isa<CallInst>(
I))
1708 for (
auto *UI :
Users) {
1709 auto *
User = cast<Instruction>(UI);
1716 "The LCSSA PHI is not in an exit block!");
1720 PN, &
I, LI, SunkCopies, SafetyInfo, CurLoop, MSSAU);
1722 New->dropLocation();
1752 if ((
I.hasMetadataOtherThanDebugLoc() || isa<CallInst>(
I)) &&
1757 I.dropUBImplyingAttrsAndMetadata();
1759 if (isa<PHINode>(
I))
1767 I.updateLocationAfterHoist();
1769 if (isa<LoadInst>(
I))
1771 else if (isa<CallInst>(
I))
1784 if (AllowSpeculation &&
1788 bool GuaranteedToExecute =
1791 if (!GuaranteedToExecute) {
1792 auto *LI = dyn_cast<LoadInst>(&Inst);
1796 DEBUG_TYPE,
"LoadWithLoopInvariantAddressCondExecuted", LI)
1797 <<
"failed to hoist load with loop-invariant address "
1798 "because load is conditionally executed";
1802 return GuaranteedToExecute;
1816 bool UnorderedAtomic;
1819 bool CanInsertStoresInExitBlocks;
1833 I->getName() +
".lcssa");
1849 LoopInsertPts(LIP), MSSAInsertPts(MSSAIP), PredCache(
PIC), MSSAU(MSSAU),
1850 LI(li),
DL(
std::
move(dl)), Alignment(Alignment),
1851 UnorderedAtomic(UnorderedAtomic), AATags(AATags),
1852 SafetyInfo(SafetyInfo),
1853 CanInsertStoresInExitBlocks(CanInsertStoresInExitBlocks),
Uses(Insts) {}
1855 void insertStoresInLoopExitBlocks() {
1861 for (
unsigned i = 0, e = LoopExitBlocks.
size(); i != e; ++i) {
1863 Value *LiveInValue =
SSA.GetValueInMiddleOfBlock(ExitBlock);
1864 LiveInValue = maybeInsertLCSSAPHI(LiveInValue, ExitBlock);
1865 Value *
Ptr = maybeInsertLCSSAPHI(SomePtr, ExitBlock);
1868 if (UnorderedAtomic)
1879 NewID = cast_or_null<DIAssignID>(
1884 NewSI->
setMetadata(LLVMContext::MD_DIAssignID, NewID);
1892 if (!MSSAInsertPoint) {
1899 MSSAInsertPts[i] = NewMemAcc;
1900 MSSAU.
insertDef(cast<MemoryDef>(NewMemAcc),
true);
1905 void doExtraRewritesBeforeFinalDeletion()
override {
1906 if (CanInsertStoresInExitBlocks)
1907 insertStoresInLoopExitBlocks();
1910 void instructionDeleted(
Instruction *
I)
const override {
1916 if (isa<StoreInst>(
I))
1917 return CanInsertStoresInExitBlocks;
1922bool isNotCapturedBeforeOrInLoop(
const Value *V,
const Loop *L,
1930 L->getHeader()->getTerminator(), DT);
1935bool isNotVisibleOnUnwindInLoop(
const Value *Object,
const Loop *L,
1937 bool RequiresNoCaptureBeforeUnwind;
1941 return !RequiresNoCaptureBeforeUnwind ||
1942 isNotCapturedBeforeOrInLoop(Object, L, DT);
1950 isNotCapturedBeforeOrInLoop(Object, L, DT)) ||
1970 bool HasReadsOutsideSet) {
1972 assert(LI !=
nullptr && DT !=
nullptr && CurLoop !=
nullptr &&
1973 SafetyInfo !=
nullptr &&
1974 "Unexpected Input to promoteLoopAccessesToScalars");
1977 dbgs() <<
"Trying to promote set of must-aliased pointers:\n";
1978 for (
Value *
Ptr : PointerMustAliases)
1979 dbgs() <<
" " << *
Ptr <<
"\n";
1981 ++NumPromotionCandidates;
1983 Value *SomePtr = *PointerMustAliases.
begin();
2023 bool DereferenceableInPH =
false;
2024 bool StoreIsGuanteedToExecute =
false;
2025 bool FoundLoadToPromote =
false;
2031 } StoreSafety = StoreSafetyUnknown;
2039 bool SawUnorderedAtomic =
false;
2040 bool SawNotAtomic =
false;
2047 if (HasReadsOutsideSet)
2048 StoreSafety = StoreUnsafe;
2057 if (!isNotVisibleOnUnwindInLoop(Object, CurLoop, DT))
2058 StoreSafety = StoreUnsafe;
2064 Type *AccessTy =
nullptr;
2065 for (
Value *ASIV : PointerMustAliases) {
2066 for (
Use &U : ASIV->uses()) {
2068 Instruction *UI = dyn_cast<Instruction>(U.getUser());
2074 if (
LoadInst *Load = dyn_cast<LoadInst>(UI)) {
2075 if (!Load->isUnordered())
2078 SawUnorderedAtomic |= Load->isAtomic();
2079 SawNotAtomic |= !Load->isAtomic();
2080 FoundLoadToPromote =
true;
2082 Align InstAlignment = Load->getAlign();
2088 if (!DereferenceableInPH || (InstAlignment > Alignment))
2090 *Load, DT, TLI, CurLoop, SafetyInfo, ORE,
2092 DereferenceableInPH =
true;
2093 Alignment = std::max(Alignment, InstAlignment);
2095 }
else if (
const StoreInst *Store = dyn_cast<StoreInst>(UI)) {
2100 if (!Store->isUnordered())
2103 SawUnorderedAtomic |= Store->isAtomic();
2104 SawNotAtomic |= !Store->isAtomic();
2111 Align InstAlignment = Store->getAlign();
2112 bool GuaranteedToExecute =
2114 StoreIsGuanteedToExecute |= GuaranteedToExecute;
2115 if (GuaranteedToExecute) {
2116 DereferenceableInPH =
true;
2117 if (StoreSafety == StoreSafetyUnknown)
2118 StoreSafety = StoreSafe;
2119 Alignment = std::max(Alignment, InstAlignment);
2128 if (StoreSafety == StoreSafetyUnknown &&
2130 return DT->
dominates(Store->getParent(), Exit);
2132 StoreSafety = StoreSafe;
2136 if (!DereferenceableInPH) {
2138 Store->getPointerOperand(), Store->getValueOperand()->getType(),
2139 Store->getAlign(), MDL, Preheader->
getTerminator(), AC, DT, TLI);
2150 if (LoopUses.
empty()) {
2153 }
else if (AATags) {
2165 if (SawUnorderedAtomic && SawNotAtomic)
2175 if (!DereferenceableInPH) {
2176 LLVM_DEBUG(
dbgs() <<
"Not promoting: Not dereferenceable in preheader\n");
2184 if (StoreSafety == StoreSafetyUnknown) {
2186 bool ExplicitlyDereferenceableOnly;
2188 (!ExplicitlyDereferenceableOnly ||
2190 isThreadLocalObject(Object, CurLoop, DT,
TTI))
2191 StoreSafety = StoreSafe;
2196 if (StoreSafety != StoreSafe && !FoundLoadToPromote)
2201 if (StoreSafety == StoreSafe) {
2202 LLVM_DEBUG(
dbgs() <<
"LICM: Promoting load/store of the value: " << *SomePtr
2204 ++NumLoadStorePromoted;
2206 LLVM_DEBUG(
dbgs() <<
"LICM: Promoting load of the value: " << *SomePtr
2214 <<
"Moving accesses to memory location out of the loop";
2218 std::vector<DILocation *> LoopUsesLocs;
2219 for (
auto *U : LoopUses)
2220 LoopUsesLocs.push_back(U->getDebugLoc().get());
2226 LoopPromoter Promoter(SomePtr, LoopUses,
SSA, ExitBlocks, InsertPts,
2227 MSSAInsertPts,
PIC, MSSAU, *LI,
DL, Alignment,
2228 SawUnorderedAtomic, AATags, *SafetyInfo,
2229 StoreSafety == StoreSafe);
2234 if (FoundLoadToPromote || !StoreIsGuanteedToExecute) {
2238 if (SawUnorderedAtomic)
2247 MemoryUse *NewMemUse = cast<MemoryUse>(PreheaderLoadMemoryAccess);
2249 SSA.AddAvailableValue(Preheader, PreheaderLoad);
2258 Promoter.run(LoopUses);
2263 if (PreheaderLoad && PreheaderLoad->
use_empty())
2273 for (
const auto &Access : *Accesses)
2274 if (
const auto *MUD = dyn_cast<MemoryUseOrDef>(&Access))
2275 Fn(MUD->getMemoryInst());
2285 auto IsPotentiallyPromotable = [L](
const Instruction *
I) {
2286 if (
const auto *SI = dyn_cast<StoreInst>(
I))
2287 return L->isLoopInvariant(SI->getPointerOperand());
2288 if (
const auto *LI = dyn_cast<LoadInst>(
I))
2289 return L->isLoopInvariant(LI->getPointerOperand());
2296 if (IsPotentiallyPromotable(
I)) {
2297 AttemptingPromotion.
insert(
I);
2305 if (!AS.isForwardingAliasSet() && AS.isMod() && AS.isMustAlias())
2317 ModRefInfo MR = Pair.getPointer()->aliasesUnknownInst(I, BatchAA);
2326 return !Pair.getPointer()->isRef();
2333 for (
auto [Set, HasReadsOutsideSet] : Sets) {
2335 for (
const auto &MemLoc : *Set)
2336 PointerMustAliases.
insert(
const_cast<Value *
>(MemLoc.Ptr));
2337 Result.emplace_back(std::move(PointerMustAliases), HasReadsOutsideSet);
2346 bool InvariantGroup) {
2348 if (!Flags.getIsSink()) {
2361 CurLoop->
contains(Source->getBlock()) &&
2362 !(InvariantGroup && Source->getBlock() == CurLoop->
getHeader() && isa<MemoryPhi>(Source));
2382 if (Flags.tooManyMemoryAccesses())
2396 for (
const auto &MA : *Accesses)
2397 if (
const auto *MD = dyn_cast<MemoryDef>(&MA))
2409 using namespace PatternMatch;
2410 Value *Cond1, *Cond2;
2426 if (L.isLoopInvariant(
LHS)) {
2430 if (L.isLoopInvariant(
LHS) || !L.isLoopInvariant(
RHS))
2437 Value *LHS1, *LHS2, *RHS1, *RHS2;
2438 if (!MatchICmpAgainstInvariant(Cond1, P1, LHS1, RHS1) ||
2439 !MatchICmpAgainstInvariant(Cond2, P2, LHS2, RHS2))
2441 if (P1 != P2 || LHS1 != LHS2)
2448 "Relational predicate is either less (or equal) or greater (or equal)!");
2450 ? (UseMin ? Intrinsic::smin : Intrinsic::smax)
2451 : (UseMin ? Intrinsic::umin : Intrinsic::umax);
2452 auto *Preheader = L.getLoopPreheader();
2453 assert(Preheader &&
"Loop is not in simplify form?");
2459 if (isa<SelectInst>(
I))
2462 id, RHS1, RHS2,
nullptr,
StringRef(
"invariant.") +
2464 (UseMin ?
"min" :
"max"));
2471 I.replaceAllUsesWith(NewCond);
2483 auto *
GEP = dyn_cast<GetElementPtrInst>(&
I);
2487 auto *Src = dyn_cast<GetElementPtrInst>(
GEP->getPointerOperand());
2488 if (!Src || !Src->hasOneUse() || !L.contains(Src))
2491 Value *SrcPtr = Src->getPointerOperand();
2492 auto LoopInvariant = [&](
Value *V) {
return L.isLoopInvariant(V); };
2493 if (!L.isLoopInvariant(SrcPtr) || !
all_of(
GEP->indices(), LoopInvariant))
2500 if (
all_of(Src->indices(), LoopInvariant))
2510 bool IsInBounds = Src->isInBounds() &&
GEP->isInBounds() &&
2514 BasicBlock *Preheader = L.getLoopPreheader();
2518 "invariant.gep", IsInBounds);
2520 Value *NewGEP = Builder.
CreateGEP(Src->getSourceElementType(), NewSrc,
2523 GEP->replaceAllUsesWith(NewGEP);
2536 assert(!L.isLoopInvariant(VariantLHS) &&
"Precondition.");
2537 assert(L.isLoopInvariant(InvariantRHS) &&
"Precondition.");
2540 using namespace PatternMatch;
2541 Value *VariantOp, *InvariantOp;
2547 if (L.isLoopInvariant(VariantOp))
2549 if (L.isLoopInvariant(VariantOp) || !L.isLoopInvariant(InvariantOp))
2556 auto &
DL = L.getHeader()->getModule()->getDataLayout();
2557 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",
2583 assert(!L.isLoopInvariant(VariantLHS) &&
"Precondition.");
2584 assert(L.isLoopInvariant(InvariantRHS) &&
"Precondition.");
2587 using namespace PatternMatch;
2588 Value *VariantOp, *InvariantOp;
2592 bool VariantSubtracted =
false;
2596 if (L.isLoopInvariant(VariantOp)) {
2598 VariantSubtracted =
true;
2601 if (L.isLoopInvariant(VariantOp) || !L.isLoopInvariant(InvariantOp))
2609 auto &
DL = L.getHeader()->getModule()->getDataLayout();
2611 if (VariantSubtracted) {
2622 auto *Preheader = L.getLoopPreheader();
2623 assert(Preheader &&
"Loop is not in simplify form?");
2627 ? Builder.
CreateSub(InvariantOp, InvariantRHS,
"invariant.op",
2629 : Builder.
CreateAdd(InvariantOp, InvariantRHS,
"invariant.op",
2642 using namespace PatternMatch;
2653 if (L.isLoopInvariant(
LHS)) {
2664 if (
hoistAdd(Pred,
LHS,
RHS, cast<ICmpInst>(
I), L, SafetyInfo, MSSAU, AC, DT))
2667 if (
hoistSub(Pred,
LHS,
RHS, cast<ICmpInst>(
I), L, SafetyInfo, MSSAU, AC, DT))
2674 unsigned FPOpcode) {
2675 if (
I->getOpcode() == IntOpcode)
2677 if (
I->getOpcode() == FPOpcode &&
I->hasAllowReassoc() &&
2678 I->hasNoSignedZeros())
2694 Value *VariantOp =
I.getOperand(0);
2695 Value *InvariantOp =
I.getOperand(1);
2696 if (L.isLoopInvariant(VariantOp))
2698 if (L.isLoopInvariant(VariantOp) || !L.isLoopInvariant(InvariantOp))
2700 Value *Factor = InvariantOp;
2706 if (
BinaryOperator *VariantBinOp = dyn_cast<BinaryOperator>(VariantOp))
2708 while (!Worklist.
empty()) {
2721 L.isLoopInvariant(BO))
2725 if (L.isLoopInvariant(U0))
2727 else if (L.isLoopInvariant(U1))
2731 unsigned Limit =
I.getType()->isIntOrIntVectorTy()
2734 if (Changes.
size() > Limit)
2737 if (Changes.
empty())
2741 if (
I.getType()->isIntOrIntVectorTy()) {
2742 for (
auto *
Add : Adds)
2743 Add->dropPoisonGeneratingFlags();
2747 auto *Preheader = L.getLoopPreheader();
2748 assert(Preheader &&
"Loop is not in simplify form?");
2750 for (
auto *U : Changes) {
2751 assert(L.isLoopInvariant(U->get()));
2752 Instruction *Ins = cast<Instruction>(U->getUser());
2754 if (
I.getType()->isIntOrIntVectorTy()) {
2755 Mul = Builder.
CreateMul(U->get(), Factor,
"factor.op.mul");
2757 Ins->dropPoisonGeneratingFlags();
2762 I.replaceAllUsesWith(VariantOp);
2781 if (
hoistGEP(
I, L, SafetyInfo, MSSAU, AC, DT)) {
2794 bool IsInt =
I.getType()->isIntOrIntVectorTy();
2798 ++NumIntAssociationsHoisted;
2800 ++NumFPAssociationsHoisted;
2811 assert(CurLoop->
contains(BB) &&
"Only valid if BB is IN the loop");
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
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 isReassociableOp(Instruction *I, unsigned IntOpcode, unsigned FPOpcode)
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 cl::opt< unsigned > FPAssociationUpperLimit("licm-max-num-fp-reassociations", cl::init(5U), cl::Hidden, cl::desc("Set upper limit for the number of transformations performed " "during a single round of hoisting the reassociated expressions."))
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 void moveInstructionBefore(Instruction &I, BasicBlock::iterator Dest, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU, ScalarEvolution *SE)
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 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 bool hoistMulAddAssociation(Instruction &I, Loop &L, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU, AssumptionCache *AC, DominatorTree *DT)
Try to reassociate expressions like ((A1 * B1) + (A2 * B2) + ...) * C where A1, A2,...
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)"))
cl::opt< unsigned > IntAssociationUpperLimit("licm-max-num-int-reassociations", cl::init(5U), cl::Hidden, cl::desc("Set upper limit for the number of transformations performed " "during a single round of hoisting the reassociated expressions."))
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 bool hoistSub(ICmpInst::Predicate Pred, Value *VariantLHS, Value *InvariantRHS, ICmpInst &ICmp, Loop &L, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU, AssumptionCache *AC, DominatorTree *DT)
Try to reassociate and hoist the following two patterns: LV - C1 < C2 --> LV < C1 + C2,...
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(const MemoryLocation &Loc)
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...
InstListType::const_iterator getFirstNonPHIIt() const
Iterator returning form of getFirstNonPHI.
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
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.
void moveBefore(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it into the function that MovePos 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.
static BranchInst * Create(BasicBlock *IfTrue, BasicBlock::iterator InsertBefore)
bool isConditional() const
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, BasicBlock::iterator InsertBefore)
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,...
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.
This class represents an Operation in the Expression.
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.
Value * CreateBinaryIntrinsic(Intrinsic::ID ID, Value *LHS, Value *RHS, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with 2 operands which is mangled on the first type.
Value * CreateFMulFMF(Value *L, Value *R, Instruction *FMFSource, const Twine &Name="")
Copy fast-math-flags from an instruction rather than using the builder's default FMF.
Value * CreateFreeze(Value *V, const Twine &Name="")
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="", bool IsInBounds=false)
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
void mergeDIAssignID(ArrayRef< const Instruction * > SourceInstructions)
Merge the DIAssignID metadata from this instruction and those attached to instructions in SourceInstr...
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
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.
void setAlignment(Align Align)
Value * getPointerOperand()
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(const 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
bool doesNotAccessMemory() const
Whether this function accesses no memory.
bool onlyAccessesArgPointees() const
Whether this function only (at most) accesses argument memory.
bool onlyReadsMemory() const
Whether this function only (at most) reads 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.
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)
Create a MemoryAccess in MemorySSA after an existing MemoryAccess.
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, BasicBlock::iterator InsertBefore)
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 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 empty() const
Determine if the SetVector is empty or not.
iterator begin()
Get an iterator to the beginning of the SetVector.
bool insert(const value_type &X)
Insert a new element into 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.
bool isIntegerTy() const
True if this is an instance of IntegerType.
A Use represents the edge between a Value definition and its users.
const Use & getOperandUse(unsigned i) const
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.
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.
self_iterator getIterator()
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.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap > m_NSWSub(const LHS &L, const RHS &R)
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.
pred_iterator pred_end(BasicBlock *BB)
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.
@ 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.
bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, Loop *CurLoop, MemorySSAUpdater &MSSAU, bool TargetExecutesOncePerLoop, SinkAndHoistLICMFlags &LICMFlags, OptimizationRemarkEmitter *ORE=nullptr)
Returns true if is legal to hoist or sink this instruction disregarding the possible introduction of ...
void set_intersect(S1Ty &S1, const S2Ty &S2)
set_intersect(A, B) - Compute A := A ^ B Identical to set_intersection, except that it works on set<>...
void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
void initializeLegacyLICMPassPass(PassRegistry &)
bool isDereferenceableAndAlignedPointer(const Value *V, Type *Ty, Align Alignment, const DataLayout &DL, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Returns true if V is always a dereferenceable pointer with alignment greater or equal than requested.
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, bool StoreCaptures, const Instruction *I, const DominatorTree *DT, bool IncludeI=false, unsigned MaxUsesToExplore=0, const LoopInfo *LI=nullptr)
PointerMayBeCapturedBefore - Return true if this pointer value may be captured by the enclosing funct...
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
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 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.
pred_iterator pred_begin(BasicBlock *BB)
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)
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const SimplifyQuery &SQ)
bool isModSet(const ModRefInfo MRI)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
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.
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
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.
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
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.
OverflowResult computeOverflowForSignedAdd(const WithCache< const Value * > &LHS, const WithCache< const Value * > &RHS, const SimplifyQuery &SQ)
@ Mul
Product of integers.
void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
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 ...
bool isDereferenceablePointer(const Value *V, Type *Ty, const DataLayout &DL, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if this is always a dereferenceable pointer.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
auto predecessors(const MachineBasicBlock *BB)
bool sinkRegion(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, TargetTransformInfo *, Loop *CurLoop, MemorySSAUpdater &, ICFLoopSafetyInfo *, SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *, Loop *OutermostLoop=nullptr)
Walk the specified region of the CFG (defined by all blocks dominated by the specified block,...
cl::opt< unsigned > SetLicmMssaNoAccForPromotionCap
unsigned pred_size(const MachineBasicBlock *BB)
bool isKnownNonNegative(const Value *V, const SimplifyQuery &SQ, unsigned Depth=0)
Returns true if the give value is known to be non-negative.
bool promoteLoopAccessesToScalars(const SmallSetVector< Value *, 8 > &, SmallVectorImpl< BasicBlock * > &, SmallVectorImpl< BasicBlock::iterator > &, 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 ...
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.
bool isWritableObject(const Value *Object, bool &ExplicitlyDereferenceableOnly)
Return true if the Object is writable, in the sense that any location based on this pointer that can ...
Implement std::hash so that hash_code can be used in STL containers.
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.