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);
936 ReciprocalDivisor->setDebugLoc(
I.getDebugLoc());
939 BinaryOperator::CreateFMul(
I.getOperand(0), ReciprocalDivisor);
940 Product->setFastMathFlags(
I.getFastMathFlags());
942 Product->insertAfter(&
I);
943 Product->setDebugLoc(
I.getDebugLoc());
944 I.replaceAllUsesWith(Product);
947 hoist(*ReciprocalDivisor, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB),
948 SafetyInfo, MSSAU, SE, ORE);
949 HoistedInstructions.
push_back(ReciprocalDivisor);
955 using namespace PatternMatch;
956 return I.use_empty() &&
957 match(&
I, m_Intrinsic<Intrinsic::invariant_start>());
959 auto MustExecuteWithoutWritesBefore = [&](
Instruction &
I) {
963 if ((IsInvariantStart(
I) ||
isGuard(&
I)) &&
965 MustExecuteWithoutWritesBefore(
I)) {
966 hoist(
I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
973 if (
PHINode *PN = dyn_cast<PHINode>(&
I)) {
974 if (CFH.canHoistPHI(PN)) {
980 hoist(*PN, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
998 CFH.registerPossiblyHoistableBranch(BI);
1013 [&](
Use &U) { return DT->dominates(I, U); })) {
1019 "New hoist point expected to dominate old hoist point");
1024 <<
": " << *
I <<
"\n");
1037#ifdef EXPENSIVE_CHECKS
1039 assert(DT->
verify(DominatorTree::VerificationLevel::Fast) &&
1040 "Dominator tree verification failed");
1072 if (isa<Constant>(
Addr))
1075 unsigned UsesVisited = 0;
1078 for (
auto *U :
Addr->users()) {
1112 return (isa<LoadInst>(
I) || isa<StoreInst>(
I) || isa<CallInst>(
I) ||
1113 isa<FenceInst>(
I) || isa<CastInst>(
I) || isa<UnaryOperator>(
I) ||
1114 isa<BinaryOperator>(
I) || isa<SelectInst>(
I) ||
1115 isa<GetElementPtrInst>(
I) || isa<CmpInst>(
I) ||
1116 isa<InsertElementInst>(
I) || isa<ExtractElementInst>(
I) ||
1117 isa<ShuffleVectorInst>(
I) || isa<ExtractValueInst>(
I) ||
1118 isa<InsertValueInst>(
I) || isa<FreezeInst>(
I));
1122 for (
auto *BB :
L->getBlocks())
1131 for (
auto *BB :
L->getBlocks())
1134 for (
const auto &Acc : *Accs) {
1135 if (isa<MemoryPhi>(&Acc))
1137 const auto *MUD = cast<MemoryUseOrDef>(&Acc);
1138 if (MUD->getMemoryInst() !=
I || NotAPhi++ == 1)
1151 if (Flags.tooManyClobberingCalls())
1156 Flags.incrementClobberingCalls();
1162 bool TargetExecutesOncePerLoop,
1166 if (!isHoistableAndSinkableInst(
I))
1171 if (
LoadInst *LI = dyn_cast<LoadInst>(&
I)) {
1172 if (!LI->isUnordered())
1179 if (LI->hasMetadata(LLVMContext::MD_invariant_load))
1182 if (LI->isAtomic() && !TargetExecutesOncePerLoop)
1191 bool InvariantGroup = LI->hasMetadata(LLVMContext::MD_invariant_group);
1194 MSSA, MU, CurLoop,
I, Flags, InvariantGroup);
1200 DEBUG_TYPE,
"LoadWithLoopInvariantAddressInvalidated", LI)
1201 <<
"failed to move load with loop-invariant address "
1202 "because the loop may invalidate its value";
1206 }
else if (
CallInst *CI = dyn_cast<CallInst>(&
I)) {
1208 if (isa<DbgInfoIntrinsic>(
I))
1219 if (CI->isConvergent())
1227 if (CI->getFunction()->isPresplitCoroutine())
1230 using namespace PatternMatch;
1231 if (
match(CI, m_Intrinsic<Intrinsic::assume>()))
1247 if (
Op->getType()->isPointerTy() &&
1257 if (isReadOnly(MSSAU, CurLoop))
1265 }
else if (
auto *FI = dyn_cast<FenceInst>(&
I)) {
1268 return isOnlyMemoryAccess(FI, CurLoop, MSSAU);
1269 }
else if (
auto *SI = dyn_cast<StoreInst>(&
I)) {
1270 if (!SI->isUnordered())
1278 if (isOnlyMemoryAccess(SI, CurLoop, MSSAU))
1282 if (Flags.tooManyMemoryAccesses())
1290 CurLoop->
contains(Source->getBlock()))
1300 for (
const auto &MA : *Accesses)
1301 if (
const auto *MU = dyn_cast<MemoryUse>(&MA)) {
1311 if (!Flags.getIsSink() && !MSSA->
dominates(SIMD, MU))
1313 }
else if (
const auto *MD = dyn_cast<MemoryDef>(&MA)) {
1314 if (
auto *LI = dyn_cast<LoadInst>(MD->getMemoryInst())) {
1316 assert(!LI->isUnordered() &&
"Expected unordered load");
1320 if (
auto *CI = dyn_cast<CallInst>(MD->getMemoryInst())) {
1333 assert(!
I.mayReadOrWriteMemory() &&
"unhandled aliasing");
1356 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(&
I)) {
1365 for (
const User *U :
GEP->users()) {
1369 (!isa<StoreInst>(UI) && !isa<LoadInst>(UI))))
1387 bool &FoldableInLoop,
bool LoopNestMode) {
1390 for (
const User *U :
I.users()) {
1392 if (
const PHINode *PN = dyn_cast<PHINode>(UI)) {
1400 if (isa<CallInst>(
I))
1401 if (!BlockColors.empty() &&
1402 BlockColors.find(
const_cast<BasicBlock *
>(BB))->second.size() != 1)
1406 while (isa<PHINode>(UI) && UI->
hasOneUser() &&
1410 UI = cast<Instruction>(UI->
user_back());
1417 FoldableInLoop =
true;
1430 if (
auto *CI = dyn_cast<CallInst>(&
I)) {
1437 for (
unsigned BundleIdx = 0, BundleEnd = CI->getNumOperandBundles();
1438 BundleIdx != BundleEnd; ++BundleIdx) {
1446 if (!BlockColors.empty()) {
1447 const ColorVector &CV = BlockColors.find(&ExitBlock)->second;
1448 assert(CV.
size() == 1 &&
"non-unique color for exit block!");
1461 if (!
I.getName().empty())
1462 New->setName(
I.getName() +
".le");
1469 if (
auto *MemDef = dyn_cast<MemoryDef>(NewMemAcc))
1472 auto *MemUse = cast<MemoryUse>(NewMemAcc);
1485 for (
Use &
Op : New->operands())
1487 auto *OInst = cast<Instruction>(
Op.get());
1490 OInst->getName() +
".lcssa");
1503 I.eraseFromParent();
1512 I.moveBefore(*Dest->getParent(), Dest);
1527 "Expect only trivially replaceable PHI");
1530 auto It = SunkCopies.
find(ExitBlock);
1531 if (It != SunkCopies.
end())
1535 *
I, *ExitBlock, *TPN, LI, SafetyInfo, MSSAU);
1550 if (isa<IndirectBrInst>(BBPred->getTerminator()))
1567 assert(ExitBlockSet.
count(ExitBB) &&
"Expect the PHI is in an exit block.");
1603 while (!PredBBs.
empty()) {
1606 "Expect all predecessors are in the loop");
1609 ExitBB, PredBB,
".split.loop.exit", DT, LI, MSSAU,
true);
1613 if (!BlockColors.empty())
1631 bool Changed =
false;
1638 auto *
User = cast<Instruction>(*UI);
1639 Use &U = UI.getUse();
1677 UI =
I.user_begin();
1681 if (VisitedUsers.
empty())
1686 <<
"sinking " <<
ore::NV(
"Inst", &
I);
1688 if (isa<LoadInst>(
I))
1690 else if (isa<CallInst>(
I))
1710 for (
auto *UI :
Users) {
1711 auto *
User = cast<Instruction>(UI);
1718 "The LCSSA PHI is not in an exit block!");
1722 PN, &
I, LI, SunkCopies, SafetyInfo, CurLoop, MSSAU);
1724 New->dropLocation();
1754 if ((
I.hasMetadataOtherThanDebugLoc() || isa<CallInst>(
I)) &&
1759 I.dropUBImplyingAttrsAndMetadata();
1761 if (isa<PHINode>(
I))
1769 I.updateLocationAfterHoist();
1771 if (isa<LoadInst>(
I))
1773 else if (isa<CallInst>(
I))
1786 if (AllowSpeculation &&
1790 bool GuaranteedToExecute =
1793 if (!GuaranteedToExecute) {
1794 auto *LI = dyn_cast<LoadInst>(&Inst);
1798 DEBUG_TYPE,
"LoadWithLoopInvariantAddressCondExecuted", LI)
1799 <<
"failed to hoist load with loop-invariant address "
1800 "because load is conditionally executed";
1804 return GuaranteedToExecute;
1818 bool UnorderedAtomic;
1821 bool CanInsertStoresInExitBlocks;
1835 I->getName() +
".lcssa");
1851 LoopInsertPts(LIP), MSSAInsertPts(MSSAIP), PredCache(
PIC), MSSAU(MSSAU),
1852 LI(li),
DL(
std::
move(dl)), Alignment(Alignment),
1853 UnorderedAtomic(UnorderedAtomic), AATags(AATags),
1854 SafetyInfo(SafetyInfo),
1855 CanInsertStoresInExitBlocks(CanInsertStoresInExitBlocks),
Uses(Insts) {}
1857 void insertStoresInLoopExitBlocks() {
1863 for (
unsigned i = 0, e = LoopExitBlocks.
size(); i != e; ++i) {
1865 Value *LiveInValue =
SSA.GetValueInMiddleOfBlock(ExitBlock);
1866 LiveInValue = maybeInsertLCSSAPHI(LiveInValue, ExitBlock);
1867 Value *
Ptr = maybeInsertLCSSAPHI(SomePtr, ExitBlock);
1870 if (UnorderedAtomic)
1881 NewID = cast_or_null<DIAssignID>(
1886 NewSI->
setMetadata(LLVMContext::MD_DIAssignID, NewID);
1894 if (!MSSAInsertPoint) {
1901 MSSAInsertPts[i] = NewMemAcc;
1902 MSSAU.
insertDef(cast<MemoryDef>(NewMemAcc),
true);
1907 void doExtraRewritesBeforeFinalDeletion()
override {
1908 if (CanInsertStoresInExitBlocks)
1909 insertStoresInLoopExitBlocks();
1912 void instructionDeleted(
Instruction *
I)
const override {
1918 if (isa<StoreInst>(
I))
1919 return CanInsertStoresInExitBlocks;
1924bool isNotCapturedBeforeOrInLoop(
const Value *V,
const Loop *L,
1932 L->getHeader()->getTerminator(), DT);
1937bool isNotVisibleOnUnwindInLoop(
const Value *Object,
const Loop *L,
1939 bool RequiresNoCaptureBeforeUnwind;
1943 return !RequiresNoCaptureBeforeUnwind ||
1944 isNotCapturedBeforeOrInLoop(Object, L, DT);
1952 isNotCapturedBeforeOrInLoop(Object, L, DT)) ||
1972 bool HasReadsOutsideSet) {
1974 assert(LI !=
nullptr && DT !=
nullptr && CurLoop !=
nullptr &&
1975 SafetyInfo !=
nullptr &&
1976 "Unexpected Input to promoteLoopAccessesToScalars");
1979 dbgs() <<
"Trying to promote set of must-aliased pointers:\n";
1980 for (
Value *
Ptr : PointerMustAliases)
1981 dbgs() <<
" " << *
Ptr <<
"\n";
1983 ++NumPromotionCandidates;
1985 Value *SomePtr = *PointerMustAliases.
begin();
2025 bool DereferenceableInPH =
false;
2026 bool StoreIsGuanteedToExecute =
false;
2027 bool FoundLoadToPromote =
false;
2033 } StoreSafety = StoreSafetyUnknown;
2041 bool SawUnorderedAtomic =
false;
2042 bool SawNotAtomic =
false;
2049 if (HasReadsOutsideSet)
2050 StoreSafety = StoreUnsafe;
2059 if (!isNotVisibleOnUnwindInLoop(Object, CurLoop, DT))
2060 StoreSafety = StoreUnsafe;
2066 Type *AccessTy =
nullptr;
2067 for (
Value *ASIV : PointerMustAliases) {
2068 for (
Use &U : ASIV->uses()) {
2070 Instruction *UI = dyn_cast<Instruction>(U.getUser());
2076 if (
LoadInst *Load = dyn_cast<LoadInst>(UI)) {
2077 if (!Load->isUnordered())
2080 SawUnorderedAtomic |= Load->isAtomic();
2081 SawNotAtomic |= !Load->isAtomic();
2082 FoundLoadToPromote =
true;
2084 Align InstAlignment = Load->getAlign();
2090 if (!DereferenceableInPH || (InstAlignment > Alignment))
2092 *Load, DT, TLI, CurLoop, SafetyInfo, ORE,
2094 DereferenceableInPH =
true;
2095 Alignment = std::max(Alignment, InstAlignment);
2097 }
else if (
const StoreInst *Store = dyn_cast<StoreInst>(UI)) {
2102 if (!Store->isUnordered())
2105 SawUnorderedAtomic |= Store->isAtomic();
2106 SawNotAtomic |= !Store->isAtomic();
2113 Align InstAlignment = Store->getAlign();
2114 bool GuaranteedToExecute =
2116 StoreIsGuanteedToExecute |= GuaranteedToExecute;
2117 if (GuaranteedToExecute) {
2118 DereferenceableInPH =
true;
2119 if (StoreSafety == StoreSafetyUnknown)
2120 StoreSafety = StoreSafe;
2121 Alignment = std::max(Alignment, InstAlignment);
2130 if (StoreSafety == StoreSafetyUnknown &&
2132 return DT->
dominates(Store->getParent(), Exit);
2134 StoreSafety = StoreSafe;
2138 if (!DereferenceableInPH) {
2140 Store->getPointerOperand(), Store->getValueOperand()->getType(),
2141 Store->getAlign(), MDL, Preheader->
getTerminator(), AC, DT, TLI);
2152 if (LoopUses.
empty()) {
2155 }
else if (AATags) {
2167 if (SawUnorderedAtomic && SawNotAtomic)
2177 if (!DereferenceableInPH) {
2178 LLVM_DEBUG(
dbgs() <<
"Not promoting: Not dereferenceable in preheader\n");
2186 if (StoreSafety == StoreSafetyUnknown) {
2188 bool ExplicitlyDereferenceableOnly;
2190 (!ExplicitlyDereferenceableOnly ||
2192 isThreadLocalObject(Object, CurLoop, DT,
TTI))
2193 StoreSafety = StoreSafe;
2198 if (StoreSafety != StoreSafe && !FoundLoadToPromote)
2203 if (StoreSafety == StoreSafe) {
2204 LLVM_DEBUG(
dbgs() <<
"LICM: Promoting load/store of the value: " << *SomePtr
2206 ++NumLoadStorePromoted;
2208 LLVM_DEBUG(
dbgs() <<
"LICM: Promoting load of the value: " << *SomePtr
2216 <<
"Moving accesses to memory location out of the loop";
2220 std::vector<DILocation *> LoopUsesLocs;
2221 for (
auto *U : LoopUses)
2222 LoopUsesLocs.push_back(U->getDebugLoc().get());
2228 LoopPromoter Promoter(SomePtr, LoopUses,
SSA, ExitBlocks, InsertPts,
2229 MSSAInsertPts,
PIC, MSSAU, *LI,
DL, Alignment,
2230 SawUnorderedAtomic, AATags, *SafetyInfo,
2231 StoreSafety == StoreSafe);
2236 if (FoundLoadToPromote || !StoreIsGuanteedToExecute) {
2240 if (SawUnorderedAtomic)
2249 MemoryUse *NewMemUse = cast<MemoryUse>(PreheaderLoadMemoryAccess);
2251 SSA.AddAvailableValue(Preheader, PreheaderLoad);
2260 Promoter.run(LoopUses);
2265 if (PreheaderLoad && PreheaderLoad->
use_empty())
2275 for (
const auto &Access : *Accesses)
2276 if (
const auto *MUD = dyn_cast<MemoryUseOrDef>(&Access))
2277 Fn(MUD->getMemoryInst());
2287 auto IsPotentiallyPromotable = [L](
const Instruction *
I) {
2288 if (
const auto *SI = dyn_cast<StoreInst>(
I))
2289 return L->isLoopInvariant(SI->getPointerOperand());
2290 if (
const auto *LI = dyn_cast<LoadInst>(
I))
2291 return L->isLoopInvariant(LI->getPointerOperand());
2298 if (IsPotentiallyPromotable(
I)) {
2299 AttemptingPromotion.
insert(
I);
2307 if (!AS.isForwardingAliasSet() && AS.isMod() && AS.isMustAlias())
2319 ModRefInfo MR = Pair.getPointer()->aliasesUnknownInst(I, BatchAA);
2328 return !Pair.getPointer()->isRef();
2335 for (
auto [Set, HasReadsOutsideSet] : Sets) {
2337 for (
const auto &MemLoc : *Set)
2338 PointerMustAliases.
insert(
const_cast<Value *
>(MemLoc.Ptr));
2339 Result.emplace_back(std::move(PointerMustAliases), HasReadsOutsideSet);
2348 bool InvariantGroup) {
2350 if (!Flags.getIsSink()) {
2363 CurLoop->
contains(Source->getBlock()) &&
2364 !(InvariantGroup && Source->getBlock() == CurLoop->
getHeader() && isa<MemoryPhi>(Source));
2384 if (Flags.tooManyMemoryAccesses())
2398 for (
const auto &MA : *Accesses)
2399 if (
const auto *MD = dyn_cast<MemoryDef>(&MA))
2411 using namespace PatternMatch;
2412 Value *Cond1, *Cond2;
2428 if (L.isLoopInvariant(
LHS)) {
2432 if (L.isLoopInvariant(
LHS) || !L.isLoopInvariant(
RHS))
2439 Value *LHS1, *LHS2, *RHS1, *RHS2;
2440 if (!MatchICmpAgainstInvariant(Cond1, P1, LHS1, RHS1) ||
2441 !MatchICmpAgainstInvariant(Cond2, P2, LHS2, RHS2))
2443 if (P1 != P2 || LHS1 != LHS2)
2450 "Relational predicate is either less (or equal) or greater (or equal)!");
2452 ? (UseMin ? Intrinsic::smin : Intrinsic::smax)
2453 : (UseMin ? Intrinsic::umin : Intrinsic::umax);
2454 auto *Preheader = L.getLoopPreheader();
2455 assert(Preheader &&
"Loop is not in simplify form?");
2461 if (isa<SelectInst>(
I))
2464 id, RHS1, RHS2,
nullptr,
StringRef(
"invariant.") +
2466 (UseMin ?
"min" :
"max"));
2473 I.replaceAllUsesWith(NewCond);
2485 auto *
GEP = dyn_cast<GetElementPtrInst>(&
I);
2489 auto *Src = dyn_cast<GetElementPtrInst>(
GEP->getPointerOperand());
2490 if (!Src || !Src->hasOneUse() || !L.contains(Src))
2493 Value *SrcPtr = Src->getPointerOperand();
2494 auto LoopInvariant = [&](
Value *V) {
return L.isLoopInvariant(V); };
2495 if (!L.isLoopInvariant(SrcPtr) || !
all_of(
GEP->indices(), LoopInvariant))
2502 if (
all_of(Src->indices(), LoopInvariant))
2512 bool IsInBounds = Src->isInBounds() &&
GEP->isInBounds() &&
2516 BasicBlock *Preheader = L.getLoopPreheader();
2520 "invariant.gep", IsInBounds);
2522 Value *NewGEP = Builder.
CreateGEP(Src->getSourceElementType(), NewSrc,
2525 GEP->replaceAllUsesWith(NewGEP);
2538 assert(!L.isLoopInvariant(VariantLHS) &&
"Precondition.");
2539 assert(L.isLoopInvariant(InvariantRHS) &&
"Precondition.");
2542 using namespace PatternMatch;
2543 Value *VariantOp, *InvariantOp;
2549 if (L.isLoopInvariant(VariantOp))
2551 if (L.isLoopInvariant(VariantOp) || !L.isLoopInvariant(InvariantOp))
2558 auto &
DL = L.getHeader()->getModule()->getDataLayout();
2559 bool ProvedNoOverflowAfterReassociate =
2563 if (!ProvedNoOverflowAfterReassociate)
2565 auto *Preheader = L.getLoopPreheader();
2566 assert(Preheader &&
"Loop is not in simplify form?");
2568 Value *NewCmpOp = Builder.
CreateSub(InvariantRHS, InvariantOp,
"invariant.op",
2585 assert(!L.isLoopInvariant(VariantLHS) &&
"Precondition.");
2586 assert(L.isLoopInvariant(InvariantRHS) &&
"Precondition.");
2589 using namespace PatternMatch;
2590 Value *VariantOp, *InvariantOp;
2594 bool VariantSubtracted =
false;
2598 if (L.isLoopInvariant(VariantOp)) {
2600 VariantSubtracted =
true;
2603 if (L.isLoopInvariant(VariantOp) || !L.isLoopInvariant(InvariantOp))
2611 auto &
DL = L.getHeader()->getModule()->getDataLayout();
2613 if (VariantSubtracted) {
2624 auto *Preheader = L.getLoopPreheader();
2625 assert(Preheader &&
"Loop is not in simplify form?");
2629 ? Builder.
CreateSub(InvariantOp, InvariantRHS,
"invariant.op",
2631 : Builder.
CreateAdd(InvariantOp, InvariantRHS,
"invariant.op",
2644 using namespace PatternMatch;
2655 if (L.isLoopInvariant(
LHS)) {
2666 if (
hoistAdd(Pred,
LHS,
RHS, cast<ICmpInst>(
I), L, SafetyInfo, MSSAU, AC, DT))
2669 if (
hoistSub(Pred,
LHS,
RHS, cast<ICmpInst>(
I), L, SafetyInfo, MSSAU, AC, DT))
2676 unsigned FPOpcode) {
2677 if (
I->getOpcode() == IntOpcode)
2679 if (
I->getOpcode() == FPOpcode &&
I->hasAllowReassoc() &&
2680 I->hasNoSignedZeros())
2696 Value *VariantOp =
I.getOperand(0);
2697 Value *InvariantOp =
I.getOperand(1);
2698 if (L.isLoopInvariant(VariantOp))
2700 if (L.isLoopInvariant(VariantOp) || !L.isLoopInvariant(InvariantOp))
2702 Value *Factor = InvariantOp;
2708 if (
BinaryOperator *VariantBinOp = dyn_cast<BinaryOperator>(VariantOp))
2710 while (!Worklist.
empty()) {
2723 L.isLoopInvariant(BO))
2727 if (L.isLoopInvariant(U0))
2729 else if (L.isLoopInvariant(U1))
2733 unsigned Limit =
I.getType()->isIntOrIntVectorTy()
2736 if (Changes.
size() > Limit)
2739 if (Changes.
empty())
2743 if (
I.getType()->isIntOrIntVectorTy()) {
2744 for (
auto *
Add : Adds)
2745 Add->dropPoisonGeneratingFlags();
2749 auto *Preheader = L.getLoopPreheader();
2750 assert(Preheader &&
"Loop is not in simplify form?");
2752 for (
auto *U : Changes) {
2753 assert(L.isLoopInvariant(U->get()));
2754 Instruction *Ins = cast<Instruction>(U->getUser());
2756 if (
I.getType()->isIntOrIntVectorTy()) {
2757 Mul = Builder.
CreateMul(U->get(), Factor,
"factor.op.mul");
2759 Ins->dropPoisonGeneratingFlags();
2764 I.replaceAllUsesWith(VariantOp);
2783 if (
hoistGEP(
I, L, SafetyInfo, MSSAU, AC, DT)) {
2796 bool IsInt =
I.getType()->isIntOrIntVectorTy();
2800 ++NumIntAssociationsHoisted;
2802 ++NumFPAssociationsHoisted;
2813 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.