68#define DEBUG_TYPE "simple-loop-unswitch"
73STATISTIC(NumBranches,
"Number of branches unswitched");
74STATISTIC(NumSwitches,
"Number of switches unswitched");
75STATISTIC(NumSelects,
"Number of selects turned into branches for unswitching");
76STATISTIC(NumGuards,
"Number of guards turned into branches for unswitching");
77STATISTIC(NumTrivial,
"Number of unswitches that are trivial");
79 NumCostMultiplierSkipped,
80 "Number of unswitch candidates that had their cost multiplier skipped");
82 "Number of invariant conditions injected and unswitched");
86 cl::desc(
"Forcibly enables non-trivial loop unswitching rather than "
87 "following the configuration passed into the pass."));
91 cl::desc(
"The cost threshold for unswitching a loop."));
95 cl::desc(
"Enable unswitch cost multiplier that prohibits exponential "
96 "explosion in nontrivial unswitch."));
99 cl::desc(
"Toplevel siblings divisor for cost multiplier."));
102 cl::desc(
"Number of unswitch candidates that are ignored when calculating "
103 "cost multiplier."));
106 cl::desc(
"If enabled, simple loop unswitching will also consider "
107 "llvm.experimental.guard intrinsics as unswitch candidates."));
109 "simple-loop-unswitch-drop-non-trivial-implicit-null-checks",
111 cl::desc(
"If enabled, drop make.implicit metadata in unswitched implicit "
112 "null checks to save time analyzing if we can keep it."));
115 cl::desc(
"Max number of memory uses to explore during "
116 "partial unswitching analysis"),
120 cl::desc(
"If enabled, the freeze instruction will be added to condition "
121 "of loop unswitch to prevent miscompilation."));
124 "simple-loop-unswitch-inject-invariant-conditions",
cl::Hidden,
125 cl::desc(
"Whether we should inject new invariants and unswitch them to "
126 "eliminate some existing (non-invariant) conditions."),
130 "simple-loop-unswitch-inject-invariant-condition-hotness-threshold",
132 "unswitch on them to eliminate branches that are "
133 "not-taken 1/<this option> times or less."),
144 : Term(Term), Invariant(Invariant), InLoopSucc(InLoopSucc) {}
147struct InjectedInvariant {
155 : Pred(Pred),
LHS(
LHS),
RHS(
RHS), InLoopSucc(InLoopSucc) {}
158struct NonTrivialUnswitchCandidate {
161 std::optional<InstructionCost>
Cost;
162 std::optional<InjectedInvariant> PendingInjection;
163 NonTrivialUnswitchCandidate(
165 std::optional<InstructionCost>
Cost = std::nullopt,
166 std::optional<InjectedInvariant> PendingInjection = std::nullopt)
167 : TI(TI), Invariants(Invariants),
Cost(
Cost),
168 PendingInjection(PendingInjection) {};
170 bool hasPendingInjection()
const {
return PendingInjection.has_value(); }
194 assert(!L.isLoopInvariant(&Root) &&
195 "Only need to walk the graph if root itself is not invariant.");
208 for (
Value *OpV :
I.operand_values()) {
210 if (isa<Constant>(OpV))
214 if (L.isLoopInvariant(OpV)) {
225 if (Visited.
insert(OpI).second)
229 }
while (!Worklist.
empty());
236 assert(!isa<Constant>(Invariant) &&
"Why are we unswitching on a constant?");
241 Instruction *UserI = dyn_cast<Instruction>(U.getUser());
244 if (UserI && L.contains(UserI))
255 auto *PN = dyn_cast<PHINode>(&
I);
262 if (!L.isLoopInvariant(PN->getIncomingValueForBlock(&ExitingBB)))
278 for (
Value *Inv : Invariants) {
287 Direction ? &NormalSucc : &UnswitchedSucc);
296 for (
auto *Val :
reverse(ToDuplicate)) {
310 auto *DefiningAccess = MemUse->getDefiningAccess();
312 while (L.contains(DefiningAccess->getBlock())) {
315 if (
auto *MemPhi = dyn_cast<MemoryPhi>(DefiningAccess))
317 MemPhi->getIncomingValueForBlock(L.getLoopPreheader());
319 DefiningAccess = cast<MemoryDef>(DefiningAccess)->getDefiningAccess();
330 Direction ? &NormalSucc : &UnswitchedSucc);
347 for (
auto i : seq<int>(0, PN.getNumOperands())) {
348 assert(PN.getIncomingBlock(i) == &OldExitingBB &&
349 "Found incoming block different from unique predecessor!");
350 PN.setIncomingBlock(i, &OldPH);
367 assert(&ExitBB != &UnswitchedBB &&
368 "Must have different loop exit and unswitched blocks!");
372 PN.getName() +
".split");
373 NewPN->insertBefore(InsertPt);
384 for (
int i = PN.getNumIncomingValues() - 1; i >= 0; --i) {
385 if (PN.getIncomingBlock(i) != &OldExitingBB)
391 PN.removeIncomingValue(i);
393 NewPN->addIncoming(
Incoming, &OldPH);
398 PN.replaceAllUsesWith(NewPN);
399 NewPN->addIncoming(&PN, &ExitBB);
412 Loop *OldParentL = L.getParentLoop();
417 L.getExitBlocks(Exits);
418 Loop *NewParentL =
nullptr;
419 for (
auto *ExitBB : Exits)
421 if (!NewParentL || NewParentL->
contains(ExitL))
424 if (NewParentL == OldParentL)
430 "Can only hoist this loop up the nest!");
435 "Parent loop of this loop should contain this loop's preheader!");
450 for (
Loop *OldContainingL = OldParentL; OldContainingL != NewParentL;
454 return BB == &Preheader || L.contains(BB);
457 OldContainingL->getBlocksSet().erase(&Preheader);
459 OldContainingL->getBlocksSet().erase(BB);
482 Loop *Current = TopMost;
512 LLVM_DEBUG(
dbgs() <<
" Trying to unswitch branch: " << BI <<
"\n");
519 bool FullUnswitch =
false;
522 if (L.isLoopInvariant(
Cond)) {
526 if (
auto *CondInst = dyn_cast<Instruction>(
Cond))
528 if (Invariants.
empty()) {
535 bool ExitDirection =
true;
536 int LoopExitSuccIdx = 0;
538 if (L.contains(LoopExitBB)) {
539 ExitDirection =
false;
542 if (L.contains(LoopExitBB)) {
547 auto *ContinueBB = BI.
getSuccessor(1 - LoopExitSuccIdx);
550 LLVM_DEBUG(
dbgs() <<
" Loop exit PHI's aren't loop-invariant!\n");
563 "non-full unswitch!\n");
569 dbgs() <<
" unswitching trivial invariant conditions for: " << BI
571 for (
Value *Invariant : Invariants) {
572 dbgs() <<
" " << *Invariant <<
" == true";
573 if (Invariant != Invariants.back())
605 if (FullUnswitch && LoopExitBB->getUniquePredecessor()) {
607 "A branch's parent isn't a predecessor!");
608 UnswitchedBB = LoopExitBB;
611 SplitBlock(LoopExitBB, LoopExitBB->begin(), &DT, &LI, MSSAU,
"",
false);
643 "Must have an `or` of `i1`s or `select i1 X, true, Y`s for the "
647 "Must have an `and` of `i1`s or `select i1 X, Y, false`s for the"
650 *OldPH, Invariants, ExitDirection, *UnswitchedBB, *NewPH,
661 Updates.
push_back({cfg::UpdateKind::Insert, OldPH, UnswitchedBB});
669 ParentBB->getTerminator()->eraseFromParent();
681 if (UnswitchedBB == LoopExitBB)
685 *ParentBB, *OldPH, FullUnswitch);
696 for (
Value *Invariant : Invariants)
742 LLVM_DEBUG(
dbgs() <<
" Trying to unswitch switch: " << SI <<
"\n");
743 Value *LoopCond = SI.getCondition();
746 if (!L.isLoopInvariant(LoopCond))
749 auto *ParentBB = SI.getParent();
756 auto IsTriviallyUnswitchableExitBlock = [&](
BasicBlock &BBToCheck) {
758 if (L.contains(&BBToCheck))
767 auto *TI = BBToCheck.getTerminator();
768 bool isUnreachable = isa<UnreachableInst>(TI);
769 return !isUnreachable ||
770 (isUnreachable && (BBToCheck.getFirstNonPHIOrDbg() != TI));
774 for (
auto Case : SI.cases())
775 if (IsTriviallyUnswitchableExitBlock(*Case.getCaseSuccessor()))
776 ExitCaseIndices.
push_back(Case.getCaseIndex());
780 if (IsTriviallyUnswitchableExitBlock(*SI.getDefaultDest())) {
781 DefaultExitBB = SI.getDefaultDest();
782 }
else if (ExitCaseIndices.
empty())
797 if (!ExitL || ExitL->
contains(OuterL))
800 for (
unsigned Index : ExitCaseIndices) {
801 auto CaseI = SI.case_begin() +
Index;
804 if (!ExitL || ExitL->
contains(OuterL))
818 SI.setDefaultDest(
nullptr);
826 ExitCases.reserve(ExitCaseIndices.
size());
831 auto CaseI = SI.case_begin() +
Index;
834 ExitCases.emplace_back(CaseI->getCaseValue(), CaseI->getCaseSuccessor(), W);
842 if (SI.getNumCases() > 0 &&
844 return Case.getCaseSuccessor() == SI.case_begin()->getCaseSuccessor();
846 CommonSuccBB = SI.case_begin()->getCaseSuccessor();
847 if (!DefaultExitBB) {
851 if (SI.getNumCases() == 0)
852 CommonSuccBB = SI.getDefaultDest();
853 else if (SI.getDefaultDest() != CommonSuccBB)
854 CommonSuccBB =
nullptr;
880 UnswitchedExitBBs.
insert(DefaultExitBB);
888 DefaultExitBB = SplitExitBBMap[DefaultExitBB] = SplitBB;
893 for (
auto &ExitCase :
reverse(ExitCases)) {
901 if (UnswitchedExitBBs.
insert(ExitBB).second)
908 BasicBlock *&SplitExitBB = SplitExitBBMap[ExitBB];
917 std::get<1>(ExitCase) = SplitExitBB;
922 for (
auto &ExitCase :
reverse(ExitCases)) {
924 BasicBlock *UnswitchedBB = std::get<1>(ExitCase);
926 NewSIW.
addCase(CaseVal, UnswitchedBB, std::get<2>(ExitCase));
937 for (
const auto &Case : SI.cases())
940 }
else if (DefaultCaseWeight) {
943 for (
const auto &Case : SI.cases()) {
946 "case weight must be defined as default case weight is defined");
961 bool SkippedFirst = DefaultExitBB ==
nullptr;
962 for (
auto Case : SI.cases()) {
964 "Non-common successor!");
976 }
else if (DefaultExitBB) {
977 assert(SI.getNumCases() > 0 &&
978 "If we had no cases we'd have a common successor!");
983 auto LastCaseI = std::prev(SI.case_end());
985 SI.setDefaultDest(LastCaseI->getCaseSuccessor());
996 for (
auto *UnswitchedExitBB : UnswitchedExitBBs) {
1000 for (
auto SplitUnswitchedPair : SplitExitBBMap) {
1001 DTUpdates.
push_back({DT.
Delete, ParentBB, SplitUnswitchedPair.first});
1013 assert(DT.
verify(DominatorTree::VerificationLevel::Fast));
1043 bool Changed =
false;
1058 Visited.
insert(CurrentBB);
1065 if (!isa<MemoryPhi>(*Defs->begin()) || (++Defs->begin() != Defs->end()))
1073 if (
auto *SI = dyn_cast<SwitchInst>(CurrentTerm)) {
1077 if (isa<Constant>(SI->getCondition()))
1091 auto *BI = dyn_cast<BranchInst>(CurrentBB->
getTerminator());
1092 if (!BI || BI->isConditional())
1095 CurrentBB = BI->getSuccessor(0);
1099 auto *BI = dyn_cast<BranchInst>(CurrentTerm);
1107 if (!BI->isConditional() ||
1122 if (BI->isConditional())
1126 CurrentBB = BI->getSuccessor(0);
1131 }
while (L.contains(CurrentBB) && Visited.
insert(CurrentBB).second);
1169 NewBlocks.
reserve(L.getNumBlocks() + ExitBlocks.
size());
1180 VMap[OldBB] = NewBB;
1188 auto It = DominatingSucc.
find(BB);
1189 return It != DominatingSucc.
end() && It->second != UnswitchedSuccBB;
1193 auto *ClonedPH = CloneBlock(LoopPH);
1196 for (
auto *LoopBB : L.blocks())
1197 if (!SkipBlock(LoopBB))
1203 for (
auto *ExitBB : ExitBlocks) {
1204 if (SkipBlock(ExitBB))
1212 auto *MergeBB =
SplitBlock(ExitBB, ExitBB->begin(), &DT, &LI, MSSAU);
1217 MergeBB->takeName(ExitBB);
1218 ExitBB->setName(
Twine(MergeBB->getName()) +
".split");
1221 auto *ClonedExitBB = CloneBlock(ExitBB);
1222 assert(ClonedExitBB->getTerminator()->getNumSuccessors() == 1 &&
1223 "Exit block should have been split to have one successor!");
1224 assert(ClonedExitBB->getTerminator()->getSuccessor(0) == MergeBB &&
1225 "Cloned exit block has the wrong successor!");
1231 std::prev(ClonedExitBB->end())))) {
1238 (isa<PHINode>(
I) || isa<LandingPadInst>(
I) || isa<CatchPadInst>(
I)) &&
1239 "Bad instruction in exit block!");
1241 assert(VMap.
lookup(&
I) == &ClonedI &&
"Mismatch in the value map!");
1244 if (SE && isa<PHINode>(
I))
1249 MergePN->insertBefore(MergeBB->getFirstInsertionPt());
1250 I.replaceAllUsesWith(MergePN);
1251 MergePN->addIncoming(&
I, ExitBB);
1252 MergePN->addIncoming(&ClonedI, ClonedExitBB);
1261 Module *M = ClonedPH->getParent()->getParent();
1262 for (
auto *ClonedBB : NewBlocks)
1268 if (
auto *II = dyn_cast<AssumeInst>(&
I))
1274 for (
auto *LoopBB : L.blocks())
1275 if (SkipBlock(LoopBB))
1277 if (
auto *ClonedSuccBB = cast_or_null<BasicBlock>(VMap.
lookup(SuccBB)))
1278 for (
PHINode &PN : ClonedSuccBB->phis())
1279 PN.removeIncomingValue(LoopBB,
false);
1283 auto *ClonedParentBB = cast<BasicBlock>(VMap.
lookup(ParentBB));
1285 if (SuccBB == UnswitchedSuccBB)
1288 auto *ClonedSuccBB = cast_or_null<BasicBlock>(VMap.
lookup(SuccBB));
1292 ClonedSuccBB->removePredecessor(ClonedParentBB,
1298 auto *ClonedSuccBB = cast<BasicBlock>(VMap.
lookup(UnswitchedSuccBB));
1299 Instruction *ClonedTerminator = ClonedParentBB->getTerminator();
1302 Value *ClonedConditionToErase =
nullptr;
1303 if (
auto *BI = dyn_cast<BranchInst>(ClonedTerminator))
1304 ClonedConditionToErase = BI->getCondition();
1305 else if (
auto *SI = dyn_cast<SwitchInst>(ClonedTerminator))
1306 ClonedConditionToErase = SI->getCondition();
1311 if (ClonedConditionToErase)
1318 for (
PHINode &PN : ClonedSuccBB->phis()) {
1322 for (
int i = PN.getNumOperands() - 1; i >= 0; --i) {
1323 if (PN.getIncomingBlock(i) != ClonedParentBB)
1329 PN.removeIncomingValue(i,
false);
1335 for (
auto *ClonedBB : NewBlocks) {
1337 if (SuccSet.
insert(SuccBB).second)
1338 DTUpdates.
push_back({DominatorTree::Insert, ClonedBB, SuccBB});
1353 auto AddClonedBlocksToLoop = [&](
Loop &OrigL,
Loop &ClonedL) {
1354 assert(ClonedL.getBlocks().empty() &&
"Must start with an empty loop!");
1356 for (
auto *BB : OrigL.
blocks()) {
1357 auto *ClonedBB = cast<BasicBlock>(VMap.
lookup(BB));
1358 ClonedL.addBlockEntry(ClonedBB);
1371 AddClonedBlocksToLoop(OrigRootL, *ClonedRootL);
1383 LoopsToClone.
push_back({ClonedRootL, ChildL});
1385 Loop *ClonedParentL, *L;
1386 std::tie(ClonedParentL, L) = LoopsToClone.
pop_back_val();
1389 AddClonedBlocksToLoop(*L, *ClonedL);
1391 LoopsToClone.
push_back({ClonedL, ChildL});
1392 }
while (!LoopsToClone.
empty());
1413 Loop *ClonedL =
nullptr;
1418 auto *ClonedPH = cast<BasicBlock>(VMap.
lookup(OrigPH));
1419 auto *ClonedHeader = cast<BasicBlock>(VMap.
lookup(OrigHeader));
1425 Loop *ParentL =
nullptr;
1429 for (
auto *ExitBB : ExitBlocks)
1430 if (
auto *ClonedExitBB = cast_or_null<BasicBlock>(VMap.
lookup(ExitBB)))
1432 ExitLoopMap[ClonedExitBB] = ExitL;
1433 ClonedExitsInLoops.
push_back(ClonedExitBB);
1434 if (!ParentL || (ParentL != ExitL && ParentL->
contains(ExitL)))
1439 "The computed parent loop should always contain (or be) the parent of "
1440 "the original loop.");
1447 for (
auto *BB : OrigL.
blocks())
1448 if (
auto *ClonedBB = cast_or_null<BasicBlock>(VMap.
lookup(BB)))
1449 ClonedLoopBlocks.
insert(ClonedBB);
1460 if (Pred == ClonedPH)
1465 assert(ClonedLoopBlocks.
count(Pred) &&
"Found a predecessor of the loop "
1466 "header other than the preheader "
1467 "that is not part of the loop!");
1472 if (BlocksInClonedLoop.
insert(Pred).second && Pred != ClonedHeader)
1479 if (!BlocksInClonedLoop.
empty()) {
1480 BlocksInClonedLoop.
insert(ClonedHeader);
1482 while (!Worklist.
empty()) {
1485 "Didn't put block into the loop set!");
1493 if (ClonedLoopBlocks.
count(Pred) &&
1494 BlocksInClonedLoop.
insert(Pred).second)
1513 for (
auto *BB : OrigL.
blocks()) {
1514 auto *ClonedBB = cast_or_null<BasicBlock>(VMap.
lookup(BB));
1515 if (!ClonedBB || !BlocksInClonedLoop.
count(ClonedBB))
1527 for (
Loop *PL = ClonedL; PL; PL = PL->getParentLoop())
1528 PL->addBlockEntry(ClonedBB);
1535 for (
Loop *ChildL : OrigL) {
1536 auto *ClonedChildHeader =
1537 cast_or_null<BasicBlock>(VMap.
lookup(ChildL->getHeader()));
1538 if (!ClonedChildHeader || !BlocksInClonedLoop.
count(ClonedChildHeader))
1544 for (
auto *ChildLoopBB : ChildL->blocks())
1546 cast<BasicBlock>(VMap.
lookup(ChildLoopBB))) &&
1547 "Child cloned loop has a header within the cloned outer "
1548 "loop but not all of its blocks!");
1563 if (BlocksInClonedLoop.
empty())
1564 UnloopedBlockSet.
insert(ClonedPH);
1565 for (
auto *ClonedBB : ClonedLoopBlocks)
1566 if (!BlocksInClonedLoop.
count(ClonedBB))
1567 UnloopedBlockSet.
insert(ClonedBB);
1573 auto OrderedClonedExitsInLoops = ClonedExitsInLoops;
1575 return ExitLoopMap.
lookup(
LHS)->getLoopDepth() <
1576 ExitLoopMap.
lookup(
RHS)->getLoopDepth();
1581 while (!UnloopedBlockSet.
empty() && !OrderedClonedExitsInLoops.empty()) {
1582 assert(Worklist.
empty() &&
"Didn't clear worklist!");
1584 BasicBlock *ExitBB = OrderedClonedExitsInLoops.pop_back_val();
1599 if (!UnloopedBlockSet.
erase(PredBB)) {
1601 (BlocksInClonedLoop.
count(PredBB) || ExitLoopMap.
count(PredBB)) &&
1602 "Predecessor not mapped to a loop!");
1609 bool Inserted = ExitLoopMap.
insert({PredBB, ExitL}).second;
1611 assert(Inserted &&
"Should only visit an unlooped block once!");
1616 }
while (!Worklist.
empty());
1625 for (
auto *BB : llvm::concat<BasicBlock *const>(
1626 ArrayRef(ClonedPH), ClonedLoopBlocks, ClonedExitsInLoops))
1628 OuterL->addBasicBlockToLoop(BB, LI);
1631 for (
auto &BBAndL : ExitLoopMap) {
1632 auto *BB = BBAndL.first;
1633 auto *OuterL = BBAndL.second;
1635 "Failed to put all blocks into outer loops!");
1642 for (
Loop *ChildL : OrigL) {
1643 auto *ClonedChildHeader =
1644 cast_or_null<BasicBlock>(VMap.
lookup(ChildL->getHeader()));
1645 if (!ClonedChildHeader || BlocksInClonedLoop.
count(ClonedChildHeader))
1649 for (
auto *ChildLoopBB : ChildL->blocks())
1651 "Cloned a child loop header but not all of that loops blocks!");
1655 *ChildL, ExitLoopMap.
lookup(ClonedChildHeader), VMap, LI));
1661 ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps,
1665 for (
BasicBlock *BB : llvm::concat<BasicBlock *const>(L.blocks(), ExitBlocks))
1666 for (
const auto &VMap : VMaps)
1667 if (
BasicBlock *ClonedBB = cast_or_null<BasicBlock>(VMap->lookup(BB)))
1670 SuccBB->removePredecessor(ClonedBB);
1683 BB->dropAllReferences();
1686 BB->eraseFromParent();
1703 DeathCandidates.
append(L.blocks().begin(), L.blocks().end());
1704 while (!DeathCandidates.
empty()) {
1708 SuccBB->removePredecessor(BB);
1725 for (
Loop *ParentL = &L; ParentL; ParentL = ParentL->getParentLoop()) {
1726 for (
auto *BB : DeadBlockSet)
1727 ParentL->getBlocksSet().erase(BB);
1729 [&](
BasicBlock *BB) { return DeadBlockSet.count(BB); });
1735 if (!DeadBlockSet.count(ChildL->getHeader()))
1738 assert(llvm::all_of(ChildL->blocks(),
1739 [&](BasicBlock *ChildBB) {
1740 return DeadBlockSet.count(ChildBB);
1742 "If the child loop header is dead all blocks in the child loop must "
1743 "be dead as well!");
1754 for (
auto *BB : DeadBlockSet) {
1756 assert(!DT.getNode(BB) &&
"Should already have cleared domtree!");
1757 LI.changeLoopFor(BB,
nullptr);
1763 BB->dropAllReferences();
1768 for (
auto *BB : DeadBlockSet)
1769 BB->eraseFromParent();
1787 auto *PH = L.getLoopPreheader();
1788 auto *Header = L.getHeader();
1802 assert(L.contains(Pred) &&
"Found a predecessor of the loop header other "
1803 "than the preheader that is not part of the "
1809 if (LoopBlockSet.
insert(Pred).second && Pred != Header)
1814 if (LoopBlockSet.
empty())
1815 return LoopBlockSet;
1818 while (!Worklist.
empty()) {
1820 assert(LoopBlockSet.
count(BB) &&
"Didn't put block into the loop set!");
1832 assert(L.contains(InnerL) &&
1833 "Should not reach a loop *outside* this loop!");
1836 auto *InnerPH = InnerL->getLoopPreheader();
1837 assert(L.contains(InnerPH) &&
"Cannot contain an inner loop block "
1838 "but not contain the inner loop "
1840 if (!LoopBlockSet.
insert(InnerPH).second)
1850 for (
auto *InnerBB : InnerL->blocks()) {
1851 if (InnerBB == BB) {
1853 "Block should already be in the set!");
1857 LoopBlockSet.
insert(InnerBB);
1869 if (L.contains(Pred) && LoopBlockSet.
insert(Pred).second)
1873 assert(LoopBlockSet.
count(Header) &&
"Cannot fail to add the header!");
1877 return LoopBlockSet;
1898 auto *PH = L.getLoopPreheader();
1902 Loop *ParentL =
nullptr;
1906 for (
auto *ExitBB : ExitBlocks)
1910 if (!ParentL || (ParentL != ExitL && ParentL->
contains(ExitL)))
1922 if (!LoopBlockSet.empty() && L.getParentLoop() != ParentL) {
1924 for (
Loop *IL = L.getParentLoop(); IL != ParentL;
1926 IL->getBlocksSet().erase(PH);
1927 for (
auto *BB : L.blocks())
1928 IL->getBlocksSet().erase(BB);
1930 return BB == PH || L.contains(BB);
1935 L.getParentLoop()->removeChildLoop(&L);
1943 auto &
Blocks = L.getBlocksVector();
1945 LoopBlockSet.empty()
1947 : std::stable_partition(
1949 [&](
BasicBlock *BB) { return LoopBlockSet.count(BB); });
1953 if (LoopBlockSet.empty())
1954 UnloopedBlocks.
insert(PH);
1958 L.getBlocksSet().erase(BB);
1969 Loop *PrevExitL = L.getParentLoop();
1971 auto RemoveUnloopedBlocksFromLoop =
1973 for (
auto *BB : UnloopedBlocks)
1974 L.getBlocksSet().erase(BB);
1976 return UnloopedBlocks.count(BB);
1981 while (!UnloopedBlocks.
empty() && !ExitsInLoops.
empty()) {
1982 assert(Worklist.
empty() &&
"Didn't clear worklist!");
1983 assert(NewExitLoopBlocks.empty() &&
"Didn't clear loop set!");
1988 assert(ExitL.
contains(&L) &&
"Exit loop must contain the inner loop!");
1994 for (; PrevExitL != &ExitL; PrevExitL = PrevExitL->
getParentLoop())
1995 RemoveUnloopedBlocksFromLoop(*PrevExitL, UnloopedBlocks);
2009 if (!UnloopedBlocks.
erase(PredBB)) {
2010 assert((NewExitLoopBlocks.count(PredBB) ||
2012 "Predecessor not in a nested loop (or already visited)!");
2019 bool Inserted = NewExitLoopBlocks.insert(PredBB).second;
2021 assert(Inserted &&
"Should only visit an unlooped block once!");
2026 }
while (!Worklist.
empty());
2031 for (
auto *BB : NewExitLoopBlocks)
2033 if (BBL == &L || !L.contains(BBL))
2038 NewExitLoopBlocks.clear();
2044 RemoveUnloopedBlocksFromLoop(*PrevExitL, UnloopedBlocks);
2045 for (
auto *BB : UnloopedBlocks)
2047 if (BBL == &L || !L.contains(BBL))
2053 auto &SubLoops = L.getSubLoopsVector();
2054 auto SubLoopsSplitI =
2055 LoopBlockSet.empty()
2057 : std::stable_partition(
2058 SubLoops.begin(), SubLoops.end(), [&](
Loop *SubL) {
2059 return LoopBlockSet.count(SubL->getHeader());
2061 for (
auto *HoistedL :
make_range(SubLoopsSplitI, SubLoops.end())) {
2063 HoistedL->setParentLoop(
nullptr);
2073 if (
auto *NewParentL = LI.
getLoopFor(HoistedL->getLoopPreheader()))
2074 NewParentL->addChildLoop(HoistedL);
2078 SubLoops.erase(SubLoopsSplitI, SubLoops.end());
2082 assert(SubLoops.empty() &&
2083 "Failed to remove all subloops from the original loop!");
2084 if (
Loop *ParentL = L.getParentLoop())
2102template <
typename CallableT>
2114 if (!Callable(
N->getBlock()))
2120 "Cannot visit a node twice when walking a tree!");
2123 }
while (!DomWorklist.
empty());
2127 bool CurrentLoopValid,
bool PartiallyInvariant,
2130 if (!NewLoops.
empty())
2131 U.addSiblingLoops(NewLoops);
2135 if (CurrentLoopValid) {
2136 if (PartiallyInvariant) {
2139 auto &
Context = L.getHeader()->getContext();
2144 Context, L.getLoopID(), {
"llvm.loop.unswitch.partial"},
2145 {DisableUnswitchMD});
2146 L.setLoopID(NewLoopID);
2147 }
else if (InjectedCondition) {
2149 auto &
Context = L.getHeader()->getContext();
2154 Context, L.getLoopID(), {
"llvm.loop.unswitch.injection"},
2155 {DisableUnswitchMD});
2156 L.setLoopID(NewLoopID);
2158 U.revisitCurrentLoop();
2160 U.markLoopAsDeleted(L, LoopName);
2167 LPMUpdater &LoopUpdater,
bool InsertFreeze,
bool InjectedCondition) {
2170 SwitchInst *SI = BI ? nullptr : cast<SwitchInst>(&TI);
2174 std::string LoopName(L.getName());
2180 "Can only unswitch switches and conditional branch!");
2184 !PartiallyInvariant);
2187 "Cannot have other invariants with full unswitching!");
2190 "Partial unswitching requires an instruction as the condition!");
2203 if (!FullUnswitch) {
2207 PartiallyInvariant) &&
2208 "Only `or`, `and`, an `select`, partially invariant instructions "
2209 "can combine invariants being unswitched.");
2220 BI ? BI->
getSuccessor(1 - ClonedSucc) : SI->getDefaultDest();
2225 for (
auto Case : SI->cases())
2226 if (Case.getCaseSuccessor() != RetainedSuccBB)
2227 UnswitchedSuccBBs.
insert(Case.getCaseSuccessor());
2229 assert(!UnswitchedSuccBBs.
count(RetainedSuccBB) &&
2230 "Should not unswitch the same successor we are retaining!");
2239 Loop *ParentL = L.getParentLoop();
2248 Loop *OuterExitL = &L;
2250 L.getUniqueExitBlocks(ExitBlocks);
2251 for (
auto *ExitBB : ExitBlocks) {
2255 if (!NewOuterExitL) {
2257 OuterExitL =
nullptr;
2260 if (NewOuterExitL != OuterExitL && NewOuterExitL->
contains(OuterExitL))
2261 OuterExitL = NewOuterExitL;
2281 for (
auto *SuccBB : llvm::concat<BasicBlock *const>(
ArrayRef(RetainedSuccBB),
2283 if (SuccBB->getUniquePredecessor() ||
2285 return PredBB == ParentBB || DT.
dominates(SuccBB, PredBB);
2288 DominatingSucc[BB] = SuccBB;
2307 for (
auto *SuccBB : UnswitchedSuccBBs) {
2310 L, LoopPH, SplitBB, ExitBlocks, ParentBB, SuccBB, RetainedSuccBB,
2311 DominatingSucc, *VMaps.
back(), DTUpdates, AC, DT, LI, MSSAU, SE);
2316 if (TI.
getMetadata(LLVMContext::MD_make_implicit)) {
2320 TI.
setMetadata(LLVMContext::MD_make_implicit,
nullptr);
2327 TI.
setMetadata(LLVMContext::MD_make_implicit,
nullptr);
2334 SplitBB->getTerminator()->eraseFromParent();
2342 NewTI->
insertInto(ParentBB, ParentBB->end());
2353 DTUpdates.
push_back({DominatorTree::Insert, SplitBB, ClonedPH});
2355 assert(SI &&
"Must either be a branch or switch!");
2358 assert(SI->getDefaultDest() == RetainedSuccBB &&
2359 "Not retaining default successor!");
2360 SI->setDefaultDest(LoopPH);
2361 for (
const auto &Case : SI->cases())
2362 if (Case.getCaseSuccessor() == RetainedSuccBB)
2363 Case.setSuccessor(LoopPH);
2365 Case.setSuccessor(ClonedPHs.
find(Case.getCaseSuccessor())->second);
2368 SI->setCondition(
new FreezeInst(SI->getCondition(),
2369 SI->getCondition()->getName() +
".fr",
2370 SI->getIterator()));
2377 {DominatorTree::Insert, SplitBB, ClonedPHs.
find(SuccBB)->second});
2391 for (
auto &VMap : VMaps)
2407 "Only one possible unswitched block for a branch!");
2411 DTUpdates.
push_back({DominatorTree::Delete, ParentBB, UnswitchedSuccBB});
2421 "Not retaining default successor!");
2422 for (
const auto &Case : NewSI->
cases())
2423 Case.getCaseSuccessor()->removePredecessor(
2431 DTUpdates.
push_back({DominatorTree::Delete, ParentBB, SuccBB});
2435 ParentBB->getTerminator()->eraseFromParent();
2441 assert(BI &&
"Only branches have partial unswitching.");
2443 "Only one possible unswitched block for a branch!");
2447 if (PartiallyInvariant)
2449 *SplitBB, Invariants,
Direction, *ClonedPH, *LoopPH, L, MSSAU);
2452 *SplitBB, Invariants,
Direction, *ClonedPH, *LoopPH,
2455 DTUpdates.
push_back({DominatorTree::Insert, SplitBB, ClonedPH});
2462 for (
auto &VMap : VMaps)
2482 for (std::unique_ptr<ValueToValueMapTy> &VMap : VMaps)
2505 assert(DT.
verify(DominatorTree::VerificationLevel::Fast));
2507 if (BI && !PartiallyInvariant) {
2513 "Only one possible unswitched block for a branch!");
2525 bool ReplaceUnswitched =
2526 FullUnswitch || (Invariants.
size() == 1) || PartiallyInvariant;
2534 for (
Value *Invariant : Invariants) {
2535 assert(!isa<Constant>(Invariant) &&
2536 "Should not be replacing constant values!");
2539 Instruction *UserI = dyn_cast<Instruction>(U.getUser());
2546 U.set(ContinueReplacement);
2547 else if (ReplaceUnswitched &&
2549 U.set(UnswitchedReplacement);
2566 auto UpdateLoop = [&](
Loop &UpdateL) {
2568 UpdateL.verifyLoop();
2569 for (
Loop *ChildL : UpdateL) {
2570 ChildL->verifyLoop();
2571 assert(ChildL->isRecursivelyLCSSAForm(DT, LI) &&
2572 "Perturbed a child loop's LCSSA form!");
2592 for (
Loop *UpdatedL :
2593 llvm::concat<Loop *>(NonChildClonedLoops, HoistedLoops)) {
2594 UpdateLoop(*UpdatedL);
2595 if (UpdatedL->isOutermost())
2596 OuterExitL =
nullptr;
2600 if (L.isOutermost())
2601 OuterExitL =
nullptr;
2606 if (OuterExitL != &L)
2607 for (
Loop *OuterL = ParentL; OuterL != OuterExitL;
2609 UpdateLoop(*OuterL);
2621 for (
Loop *UpdatedL : llvm::concat<Loop *>(NonChildClonedLoops, HoistedLoops))
2622 if (UpdatedL->getParentLoop() == ParentL)
2624 postUnswitch(L, LoopUpdater, LoopName, IsStillLoop, PartiallyInvariant,
2625 InjectedCondition, SibLoops);
2648 auto BBCostIt = BBCostMap.
find(
N.getBlock());
2649 if (BBCostIt == BBCostMap.
end())
2653 auto DTCostIt = DTCostMap.
find(&
N);
2654 if (DTCostIt != DTCostMap.
end())
2655 return DTCostIt->second;
2660 N.begin(),
N.end(), BBCostIt->second,
2662 return Sum + computeDomSubtreeCost(*ChildN, BBCostMap, DTCostMap);
2664 bool Inserted = DTCostMap.
insert({&
N,
Cost}).second;
2666 assert(Inserted &&
"Should not insert a node while visiting children!");
2701 SI->getMetadata(LLVMContext::MD_prof), &DTU, &LI);
2703 BasicBlock *ThenBB = CondBr->getSuccessor(0),
2704 *TailBB = CondBr->getSuccessor(1);
2709 PHINode::Create(SI->getType(), 2,
"unswitched.select", SI->getIterator());
2710 Phi->addIncoming(SI->getTrueValue(), ThenBB);
2711 Phi->addIncoming(SI->getFalseValue(), HeadBB);
2712 SI->replaceAllUsesWith(Phi);
2713 SI->eraseFromParent();
2756 GI->
getMetadata(LLVMContext::MD_prof), &DTU, &LI);
2763 GuardedBlock->
setName(
"guarded");
2814 return L.contains(SuccBB);
2816 NumCostMultiplierSkipped++;
2820 auto *ParentL = L.getParentLoop();
2821 int SiblingsCount = (ParentL ? ParentL->getSubLoopsVector().size()
2822 : std::distance(LI.
begin(), LI.
end()));
2826 int UnswitchedClones = 0;
2827 for (
const auto &Candidate : UnswitchCandidates) {
2830 bool SkipExitingSuccessors = DT.
dominates(CondBlock, Latch);
2831 if (isa<SelectInst>(CI)) {
2836 if (!SkipExitingSuccessors)
2840 int NonExitingSuccessors =
2842 [SkipExitingSuccessors, &L](
const BasicBlock *SuccBB) {
2843 return !SkipExitingSuccessors || L.contains(SuccBB);
2845 UnswitchedClones +=
Log2_32(NonExitingSuccessors);
2853 unsigned ClonesPower =
2857 int SiblingsMultiplier =
2858 std::max((ParentL ? SiblingsCount
2868 CostMultiplier = std::min(SiblingsMultiplier * (1 << ClonesPower),
2872 <<
" (siblings " << SiblingsMultiplier <<
" * clones "
2873 << (1 << ClonesPower) <<
")"
2874 <<
" for unswitch candidate: " << TI <<
"\n");
2875 return CostMultiplier;
2883 assert(UnswitchCandidates.
empty() &&
"Should be!");
2887 if (isa<Constant>(
Cond))
2889 if (L.isLoopInvariant(
Cond)) {
2897 if (!Invariants.
empty())
2898 UnswitchCandidates.
push_back({
I, std::move(Invariants)});
2903 bool CollectGuards =
false;
2905 auto *GuardDecl = L.getHeader()->getParent()->getParent()->getFunction(
2907 if (GuardDecl && !GuardDecl->use_empty())
2908 CollectGuards =
true;
2911 for (
auto *BB : L.blocks()) {
2915 for (
auto &
I : *BB) {
2916 if (
auto *SI = dyn_cast<SelectInst>(&
I)) {
2917 auto *
Cond = SI->getCondition();
2919 if (
Cond->getType()->isIntegerTy(1) && !SI->getType()->isIntegerTy(1))
2920 AddUnswitchCandidatesForInst(SI,
Cond);
2921 }
else if (CollectGuards &&
isGuard(&
I)) {
2925 if (!isa<Constant>(
Cond) && L.isLoopInvariant(
Cond))
2930 if (
auto *SI = dyn_cast<SwitchInst>(BB->getTerminator())) {
2933 if (!isa<Constant>(SI->getCondition()) &&
2934 L.isLoopInvariant(SI->getCondition()) && !BB->getUniqueSuccessor())
2935 UnswitchCandidates.
push_back({SI, {SI->getCondition()}});
2939 auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
2940 if (!BI || !BI->isConditional() ||
2941 BI->getSuccessor(0) == BI->getSuccessor(1))
2944 AddUnswitchCandidatesForInst(BI, BI->getCondition());
2948 !
any_of(UnswitchCandidates, [&L](
auto &TerminatorAndInvariants) {
2949 return TerminatorAndInvariants.TI == L.getHeader()->getTerminator();
2954 dbgs() <<
"simple-loop-unswitch: Found partially invariant condition "
2955 << *
Info->InstToDuplicate[0] <<
"\n");
2956 PartialIVInfo = *
Info;
2957 PartialIVCondBranch = L.getHeader()->getTerminator();
2961 {L.getHeader()->getTerminator(), std::move(ValsToDuplicate)});
2964 return !UnswitchCandidates.
empty();
2977 if (!L.contains(IfTrue)) {
2978 Pred = ICmpInst::getInversePredicate(Pred);
2983 if (L.isLoopInvariant(
LHS)) {
2984 Pred = ICmpInst::getSwappedPredicate(Pred);
2990 Pred = ICmpInst::ICMP_ULT;
2991 RHS = ConstantInt::get(
3003 if (L.isLoopInvariant(
LHS) || !L.isLoopInvariant(
RHS))
3006 if (Pred != ICmpInst::ICMP_ULT)
3009 if (!L.contains(IfTrue) || L.contains(IfFalse))
3013 if (L.getHeader() == IfTrue)
3030 assert(Weights.
size() == 2 &&
"Unexpected profile data!");
3032 auto Num = Weights[
Idx];
3033 auto Denom = Weights[0] + Weights[1];
3035 if (Denom == 0 || Num > Denom)
3038 if (LikelyTaken > ActualTaken)
3061static NonTrivialUnswitchCandidate
3065 assert(Candidate.hasPendingInjection() &&
"Nothing to inject!");
3066 BasicBlock *Preheader = L.getLoopPreheader();
3067 assert(Preheader &&
"Loop is not in simplified form?");
3069 "Unswitching branch of inner loop!");
3071 auto Pred = Candidate.PendingInjection->Pred;
3072 auto *
LHS = Candidate.PendingInjection->LHS;
3073 auto *
RHS = Candidate.PendingInjection->RHS;
3074 auto *InLoopSucc = Candidate.PendingInjection->InLoopSucc;
3075 auto *TI = cast<BranchInst>(Candidate.TI);
3076 auto *BB = Candidate.TI->getParent();
3077 auto *OutOfLoopSucc = InLoopSucc == TI->getSuccessor(0) ? TI->getSuccessor(1)
3078 : TI->getSuccessor(0);
3080 assert(L.contains(InLoopSucc) &&
"Not supported yet!");
3081 assert(!L.contains(OutOfLoopSucc) &&
"Not supported yet!");
3082 auto &Ctx = BB->getContext();
3085 assert(ICmpInst::isUnsigned(Pred) &&
"Not supported yet!");
3095 auto *InjectedCond =
3096 ICmpInst::Create(Instruction::ICmp, Pred,
LHS,
RHS,
"injected.cond",
3100 BB->getParent(), InLoopSucc);
3103 Builder.
CreateCondBr(InjectedCond, InLoopSucc, CheckBlock);
3106 Builder.
CreateCondBr(TI->getCondition(), TI->getSuccessor(0),
3107 TI->getSuccessor(1));
3111 for (
auto &
I : *InLoopSucc) {
3112 auto *PN = dyn_cast<PHINode>(&
I);
3115 auto *Inc = PN->getIncomingValueForBlock(BB);
3116 PN->addIncoming(Inc, CheckBlock);
3118 OutOfLoopSucc->replacePhiUsesWith(BB, CheckBlock);
3121 { DominatorTree::Insert, BB, CheckBlock },
3122 { DominatorTree::Insert, CheckBlock, InLoopSucc },
3123 { DominatorTree::Insert, CheckBlock, OutOfLoopSucc },
3124 { DominatorTree::Delete, BB, OutOfLoopSucc }
3130 L.addBasicBlockToLoop(CheckBlock, LI);
3142 LLVM_DEBUG(
dbgs() <<
"Injected a new loop-invariant branch " << *InvariantBr
3143 <<
" and considering it for unswitching.");
3144 ++NumInvariantConditionsInjected;
3145 return NonTrivialUnswitchCandidate(InvariantBr, { InjectedCond },
3166 assert(ICmpInst::isStrictPredicate(Pred));
3167 if (Compares.
size() < 2)
3170 for (
auto Prev = Compares.
begin(), Next = Compares.
begin() + 1;
3171 Next != Compares.
end(); ++Prev, ++Next) {
3175 InjectedInvariant ToInject(NonStrictPred,
LHS,
RHS, InLoopSucc);
3176 NonTrivialUnswitchCandidate Candidate(Prev->Term, { LHS, RHS },
3177 std::nullopt, std::move(ToInject));
3178 UnswitchCandidates.
push_back(std::move(Candidate));
3208 auto *Latch = L.getLoopLatch();
3212 assert(L.getLoopPreheader() &&
"Must have a preheader!");
3217 for (
auto *DTN = DT.
getNode(Latch); L.contains(DTN->getBlock());
3218 DTN = DTN->getIDom()) {
3221 BasicBlock *IfTrue =
nullptr, *IfFalse =
nullptr;
3222 auto *BB = DTN->getBlock();
3226 auto *Term = BB->getTerminator();
3240 CompareDesc
Desc(cast<BranchInst>(Term),
RHS, IfTrue);
3241 while (
auto *Zext = dyn_cast<ZExtInst>(
LHS))
3242 LHS = Zext->getOperand(0);
3243 CandidatesULT[
LHS].push_back(
Desc);
3247 for (
auto &It : CandidatesULT)
3249 UnswitchCandidates, L, ICmpInst::ICMP_ULT, It.second, DT);
3254 if (!L.isSafeToClone())
3256 for (
auto *BB : L.blocks())
3257 for (
auto &
I : *BB) {
3258 if (
I.getType()->isTokenTy() &&
I.isUsedOutsideOfBlock(BB))
3260 if (
auto *CB = dyn_cast<CallBase>(&
I)) {
3261 assert(!CB->cannotDuplicate() &&
"Checked by L.isSafeToClone().");
3262 if (CB->isConvergent())
3275 if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))
3279 L.getUniqueExitBlocks(ExitBlocks);
3284 for (
auto *ExitBB : ExitBlocks) {
3285 auto *
I = ExitBB->getFirstNonPHI();
3286 if (isa<CleanupPadInst>(
I) || isa<CatchSwitchInst>(
I)) {
3287 LLVM_DEBUG(
dbgs() <<
"Cannot unswitch because of cleanuppad/catchswitch "
3315 L.getHeader()->getParent()->hasMinSize()
3319 for (
auto *BB : L.blocks()) {
3321 for (
auto &
I : *BB) {
3326 assert(
Cost >= 0 &&
"Must not have negative costs!");
3328 assert(LoopCost >= 0 &&
"Must not have negative loop costs!");
3329 BBCostMap[BB] =
Cost;
3353 if (isa<SelectInst>(TI))
3362 if (!Visited.
insert(SuccBB).second)
3370 if (!FullUnswitch) {
3371 auto &BI = cast<BranchInst>(TI);
3374 if (SuccBB == BI.getSuccessor(1))
3377 if (SuccBB == BI.getSuccessor(0))
3380 SuccBB == BI.getSuccessor(0)) ||
3382 SuccBB == BI.getSuccessor(1)))
3390 if (SuccBB->getUniquePredecessor() ||
3392 return PredBB == &BB || DT.
dominates(SuccBB, PredBB);
3396 "Non-duplicated cost should never exceed total loop cost!");
3405 int SuccessorsCount =
isGuard(&TI) ? 2 : Visited.
size();
3406 assert(SuccessorsCount > 1 &&
3407 "Cannot unswitch a condition without multiple distinct successors!");
3408 return (LoopCost -
Cost) * (SuccessorsCount - 1);
3411 std::optional<NonTrivialUnswitchCandidate> Best;
3412 for (
auto &Candidate : UnswitchCandidates) {
3417 !BI || Candidate.hasPendingInjection() ||
3418 (Invariants.
size() == 1 &&
3420 InstructionCost CandidateCost = ComputeUnswitchedCost(TI, FullUnswitch);
3424 int CostMultiplier =
3428 "cost multiplier needs to be in the range of 1..UnswitchThreshold");
3429 CandidateCost *= CostMultiplier;
3431 <<
" (multiplier: " << CostMultiplier <<
")"
3432 <<
" for unswitch candidate: " << TI <<
"\n");
3435 <<
" for unswitch candidate: " << TI <<
"\n");
3438 if (!Best || CandidateCost < Best->
Cost) {
3440 Best->Cost = CandidateCost;
3443 assert(Best &&
"Must be!");
3455 assert(isa<BranchInst>(TI) || isa<SwitchInst>(TI));
3465 if (
BranchInst *BI = dyn_cast<BranchInst>(&TI))
3470 Cond, &AC, L.getLoopPreheader()->getTerminator(), &DT);
3484 PartialIVCondBranch, L, LI, AA, MSSAU);
3487 PartialIVCondBranch, L, DT, LI, AA,
3490 if (UnswitchCandidates.
empty())
3494 dbgs() <<
"Considering " << UnswitchCandidates.
size()
3495 <<
" non-trivial loop invariant conditions for unswitching.\n");
3498 UnswitchCandidates, L, DT, LI, AC,
TTI, PartialIVInfo);
3500 assert(Best.TI &&
"Failed to find loop unswitch candidate");
3501 assert(Best.Cost &&
"Failed to compute cost");
3504 LLVM_DEBUG(
dbgs() <<
"Cannot unswitch, lowest cost found: " << *Best.Cost
3509 bool InjectedCondition =
false;
3510 if (Best.hasPendingInjection()) {
3512 InjectedCondition =
true;
3514 assert(!Best.hasPendingInjection() &&
3515 "All injections should have been done by now!");
3517 if (Best.TI != PartialIVCondBranch)
3521 if (
auto *SI = dyn_cast<SelectInst>(Best.TI)) {
3527 SI->getCondition(), &AC, L.getLoopPreheader()->getTerminator(), &DT);
3537 LLVM_DEBUG(
dbgs() <<
" Unswitching non-trivial (cost = " << Best.Cost
3538 <<
") terminator: " << *Best.TI <<
"\n");
3540 LI, AC, SE, MSSAU, LoopUpdater, InsertFreeze,
3572 assert(L.isRecursivelyLCSSAForm(DT, LI) &&
3573 "Loops must be in LCSSA form before unswitching.");
3576 if (!L.isLoopSimplifyForm())
3589 const Function *
F = L.getHeader()->getParent();
3602 bool ContinueWithNonTrivial =
3604 if (!ContinueWithNonTrivial)
3608 if (
F->hasOptSize())
3613 auto IsLoopNestCold = [&](
const Loop *L) {
3619 Parent = Parent->getParentLoop();
3623 Worklist.
insert(Worklist.
end(), L->getSubLoops().begin(),
3624 L->getSubLoops().end());
3625 while (!Worklist.
empty()) {
3629 Worklist.
insert(Worklist.
end(), CurLoop->getSubLoops().begin(),
3630 CurLoop->getSubLoops().end());
3664 Function &
F = *L.getHeader()->getParent();
3667 if (
auto OuterProxy =
3671 LLVM_DEBUG(
dbgs() <<
"Unswitching loop in " <<
F.getName() <<
": " << L
3674 std::optional<MemorySSAUpdater> MSSAU;
3681 &AR.
SE, MSSAU ? &*MSSAU :
nullptr, PSI, AR.
BFI, U))
3700 OS, MapClassName2PassName);
3703 OS << (NonTrivial ?
"" :
"no-") <<
"nontrivial;";
3704 OS << (Trivial ?
"" :
"no-") <<
"trivial";
Analysis containing CSE Info
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static cl::opt< TargetTransformInfo::TargetCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(TargetTransformInfo::TCK_RecipThroughput), cl::values(clEnumValN(TargetTransformInfo::TCK_RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(TargetTransformInfo::TCK_Latency, "latency", "Instruction latency"), clEnumValN(TargetTransformInfo::TCK_CodeSize, "code-size", "Code size"), clEnumValN(TargetTransformInfo::TCK_SizeAndLatency, "size-latency", "Code size and latency")))
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
DenseMap< Block *, BlockRelaxAux > Blocks
This file defines a set of templates that efficiently compute a dominator tree over a generic graph.
This file defines an InstructionCost class that is used when calculating the cost of an instruction,...
This header provides classes for managing per-loop analyses.
This header provides classes for managing a pipeline of passes over loops in LLVM IR.
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 ...
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Provides some synthesis utilities to produce sequences of values.
This file implements a set that has insertion order iteration characteristics.
static void rewritePHINodesForUnswitchedExitBlock(BasicBlock &UnswitchedBB, BasicBlock &OldExitingBB, BasicBlock &OldPH)
Rewrite the PHI nodes in an unswitched loop exit basic block.
static bool unswitchLoop(Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, AAResults &AA, TargetTransformInfo &TTI, bool Trivial, bool NonTrivial, ScalarEvolution *SE, MemorySSAUpdater *MSSAU, ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI, LPMUpdater &LoopUpdater)
Unswitch control flow predicated on loop invariant conditions.
static void canonicalizeForInvariantConditionInjection(ICmpInst::Predicate &Pred, Value *&LHS, Value *&RHS, BasicBlock *&IfTrue, BasicBlock *&IfFalse, const Loop &L)
Tries to canonicalize condition described by:
static bool unswitchAllTrivialConditions(Loop &L, DominatorTree &DT, LoopInfo &LI, ScalarEvolution *SE, MemorySSAUpdater *MSSAU)
This routine scans the loop to find a branch or switch which occurs before any side effects occur.
static cl::opt< bool > EnableNonTrivialUnswitch("enable-nontrivial-unswitch", cl::init(false), cl::Hidden, cl::desc("Forcibly enables non-trivial loop unswitching rather than " "following the configuration passed into the pass."))
static cl::opt< bool > UnswitchGuards("simple-loop-unswitch-guards", cl::init(true), cl::Hidden, cl::desc("If enabled, simple loop unswitching will also consider " "llvm.experimental.guard intrinsics as unswitch candidates."))
static SmallPtrSet< const BasicBlock *, 16 > recomputeLoopBlockSet(Loop &L, LoopInfo &LI)
Recompute the set of blocks in a loop after unswitching.
static int CalculateUnswitchCostMultiplier(const Instruction &TI, const Loop &L, const LoopInfo &LI, const DominatorTree &DT, ArrayRef< NonTrivialUnswitchCandidate > UnswitchCandidates)
Cost multiplier is a way to limit potentially exponential behavior of loop-unswitch.
static void buildPartialInvariantUnswitchConditionalBranch(BasicBlock &BB, ArrayRef< Value * > ToDuplicate, bool Direction, BasicBlock &UnswitchedSucc, BasicBlock &NormalSucc, Loop &L, MemorySSAUpdater *MSSAU)
Copy a set of loop invariant values, and conditionally branch on them.
static TinyPtrVector< Value * > collectHomogenousInstGraphLoopInvariants(const Loop &L, Instruction &Root, const LoopInfo &LI)
Collect all of the loop invariant input values transitively used by the homogeneous instruction graph...
static void deleteDeadClonedBlocks(Loop &L, ArrayRef< BasicBlock * > ExitBlocks, ArrayRef< std::unique_ptr< ValueToValueMapTy > > VMaps, DominatorTree &DT, MemorySSAUpdater *MSSAU)
void visitDomSubTree(DominatorTree &DT, BasicBlock *BB, CallableT Callable)
Helper to visit a dominator subtree, invoking a callable on each node.
static BranchInst * turnSelectIntoBranch(SelectInst *SI, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU, AssumptionCache *AC)
Turns a select instruction into implicit control flow branch, making the following replacement:
static bool isSafeForNoNTrivialUnswitching(Loop &L, LoopInfo &LI)
void postUnswitch(Loop &L, LPMUpdater &U, StringRef LoopName, bool CurrentLoopValid, bool PartiallyInvariant, bool InjectedCondition, ArrayRef< Loop * > NewLoops)
static void buildPartialUnswitchConditionalBranch(BasicBlock &BB, ArrayRef< Value * > Invariants, bool Direction, BasicBlock &UnswitchedSucc, BasicBlock &NormalSucc, bool InsertFreeze, const Instruction *I, AssumptionCache *AC, const DominatorTree &DT)
Copy a set of loop invariant values ToDuplicate and insert them at the end of BB and conditionally br...
static cl::opt< int > UnswitchNumInitialUnscaledCandidates("unswitch-num-initial-unscaled-candidates", cl::init(8), cl::Hidden, cl::desc("Number of unswitch candidates that are ignored when calculating " "cost multiplier."))
static bool shouldTryInjectInvariantCondition(const ICmpInst::Predicate Pred, const Value *LHS, const Value *RHS, const BasicBlock *IfTrue, const BasicBlock *IfFalse, const Loop &L)
Returns true, if predicate described by ( Pred, LHS, RHS ) succeeding into blocks ( IfTrue,...
static NonTrivialUnswitchCandidate findBestNonTrivialUnswitchCandidate(ArrayRef< NonTrivialUnswitchCandidate > UnswitchCandidates, const Loop &L, const DominatorTree &DT, const LoopInfo &LI, AssumptionCache &AC, const TargetTransformInfo &TTI, const IVConditionInfo &PartialIVInfo)
static cl::opt< bool > EnableUnswitchCostMultiplier("enable-unswitch-cost-multiplier", cl::init(true), cl::Hidden, cl::desc("Enable unswitch cost multiplier that prohibits exponential " "explosion in nontrivial unswitch."))
static Value * skipTrivialSelect(Value *Cond)
static Loop * getTopMostExitingLoop(const BasicBlock *ExitBB, const LoopInfo &LI)
static bool collectUnswitchCandidatesWithInjections(SmallVectorImpl< NonTrivialUnswitchCandidate > &UnswitchCandidates, IVConditionInfo &PartialIVInfo, Instruction *&PartialIVCondBranch, Loop &L, const DominatorTree &DT, const LoopInfo &LI, AAResults &AA, const MemorySSAUpdater *MSSAU)
Collect unswitch candidates by invariant conditions that are not immediately present in the loop.
static cl::opt< int > UnswitchThreshold("unswitch-threshold", cl::init(50), cl::Hidden, cl::desc("The cost threshold for unswitching a loop."))
static void replaceLoopInvariantUses(const Loop &L, Value *Invariant, Constant &Replacement)
static bool unswitchTrivialBranch(Loop &L, BranchInst &BI, DominatorTree &DT, LoopInfo &LI, ScalarEvolution *SE, MemorySSAUpdater *MSSAU)
Unswitch a trivial branch if the condition is loop invariant.
static bool collectUnswitchCandidates(SmallVectorImpl< NonTrivialUnswitchCandidate > &UnswitchCandidates, IVConditionInfo &PartialIVInfo, Instruction *&PartialIVCondBranch, const Loop &L, const LoopInfo &LI, AAResults &AA, const MemorySSAUpdater *MSSAU)
static cl::opt< bool > InjectInvariantConditions("simple-loop-unswitch-inject-invariant-conditions", cl::Hidden, cl::desc("Whether we should inject new invariants and unswitch them to " "eliminate some existing (non-invariant) conditions."), cl::init(true))
static cl::opt< bool > FreezeLoopUnswitchCond("freeze-loop-unswitch-cond", cl::init(true), cl::Hidden, cl::desc("If enabled, the freeze instruction will be added to condition " "of loop unswitch to prevent miscompilation."))
static InstructionCost computeDomSubtreeCost(DomTreeNode &N, const SmallDenseMap< BasicBlock *, InstructionCost, 4 > &BBCostMap, SmallDenseMap< DomTreeNode *, InstructionCost, 4 > &DTCostMap)
Recursively compute the cost of a dominator subtree based on the per-block cost map provided.
static bool shouldInsertFreeze(Loop &L, Instruction &TI, DominatorTree &DT, AssumptionCache &AC)
static cl::opt< int > UnswitchSiblingsToplevelDiv("unswitch-siblings-toplevel-div", cl::init(2), cl::Hidden, cl::desc("Toplevel siblings divisor for cost multiplier."))
static cl::opt< unsigned > MSSAThreshold("simple-loop-unswitch-memoryssa-threshold", cl::desc("Max number of memory uses to explore during " "partial unswitching analysis"), cl::init(100), cl::Hidden)
static bool areLoopExitPHIsLoopInvariant(const Loop &L, const BasicBlock &ExitingBB, const BasicBlock &ExitBB)
Check that all the LCSSA PHI nodes in the loop exit block have trivial incoming values along this edg...
static void rewritePHINodesForExitAndUnswitchedBlocks(BasicBlock &ExitBB, BasicBlock &UnswitchedBB, BasicBlock &OldExitingBB, BasicBlock &OldPH, bool FullUnswitch)
Rewrite the PHI nodes in the loop exit basic block and the split off unswitched block.
static bool insertCandidatesWithPendingInjections(SmallVectorImpl< NonTrivialUnswitchCandidate > &UnswitchCandidates, Loop &L, ICmpInst::Predicate Pred, ArrayRef< CompareDesc > Compares, const DominatorTree &DT)
Given chain of loop branch conditions looking like: br (Variant < Invariant1) br (Variant < Invariant...
static NonTrivialUnswitchCandidate injectPendingInvariantConditions(NonTrivialUnswitchCandidate Candidate, Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, MemorySSAUpdater *MSSAU)
Materialize pending invariant condition of the given candidate into IR.
static cl::opt< bool > DropNonTrivialImplicitNullChecks("simple-loop-unswitch-drop-non-trivial-implicit-null-checks", cl::init(false), cl::Hidden, cl::desc("If enabled, drop make.implicit metadata in unswitched implicit " "null checks to save time analyzing if we can keep it."))
static cl::opt< unsigned > InjectInvariantConditionHotnesThreshold("simple-loop-unswitch-inject-invariant-condition-hotness-threshold", cl::Hidden, cl::desc("Only try to inject loop invariant conditions and " "unswitch on them to eliminate branches that are " "not-taken 1/<this option> times or less."), cl::init(16))
static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT, LoopInfo &LI, ScalarEvolution *SE, MemorySSAUpdater *MSSAU)
Unswitch a trivial switch if the condition is loop invariant.
static void unswitchNontrivialInvariants(Loop &L, Instruction &TI, ArrayRef< Value * > Invariants, IVConditionInfo &PartialIVInfo, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, ScalarEvolution *SE, MemorySSAUpdater *MSSAU, LPMUpdater &LoopUpdater, bool InsertFreeze, bool InjectedCondition)
static bool rebuildLoopAfterUnswitch(Loop &L, ArrayRef< BasicBlock * > ExitBlocks, LoopInfo &LI, SmallVectorImpl< Loop * > &HoistedLoops, ScalarEvolution *SE)
Rebuild a loop after unswitching removes some subset of blocks and edges.
static bool unswitchBestCondition(Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, AAResults &AA, TargetTransformInfo &TTI, ScalarEvolution *SE, MemorySSAUpdater *MSSAU, LPMUpdater &LoopUpdater)
static BasicBlock * buildClonedLoopBlocks(Loop &L, BasicBlock *LoopPH, BasicBlock *SplitBB, ArrayRef< BasicBlock * > ExitBlocks, BasicBlock *ParentBB, BasicBlock *UnswitchedSuccBB, BasicBlock *ContinueSuccBB, const SmallDenseMap< BasicBlock *, BasicBlock *, 16 > &DominatingSucc, ValueToValueMapTy &VMap, SmallVectorImpl< DominatorTree::UpdateType > &DTUpdates, AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU, ScalarEvolution *SE)
Build the cloned blocks for an unswitched copy of the given loop.
static void deleteDeadBlocksFromLoop(Loop &L, SmallVectorImpl< BasicBlock * > &ExitBlocks, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU, ScalarEvolution *SE, LPMUpdater &LoopUpdater)
bool shouldTryInjectBasingOnMetadata(const BranchInst *BI, const BasicBlock *TakenSucc)
Returns true, if metadata on BI allows us to optimize branching into TakenSucc via injection of invar...
static BranchInst * turnGuardIntoBranch(IntrinsicInst *GI, Loop &L, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU)
Turns a llvm.experimental.guard intrinsic into implicit control flow branch, making the following rep...
static Loop * cloneLoopNest(Loop &OrigRootL, Loop *RootParentL, const ValueToValueMapTy &VMap, LoopInfo &LI)
Recursively clone the specified loop and all of its children.
static void hoistLoopToNewParent(Loop &L, BasicBlock &Preheader, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU, ScalarEvolution *SE)
Hoist the current loop up to the innermost loop containing a remaining exit.
static void buildClonedLoops(Loop &OrigL, ArrayRef< BasicBlock * > ExitBlocks, const ValueToValueMapTy &VMap, LoopInfo &LI, SmallVectorImpl< Loop * > &NonChildClonedLoops)
Build the cloned loops of an original loop from unswitching.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
This defines the Use class.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
size - Get the array size.
bool empty() const
empty - Check if the array is empty.
A cache of @llvm.assume calls within a function.
void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
InstListType::iterator iterator
Instruction iterators...
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...
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Conditional or Unconditional Branch instruction.
void setCondition(Value *V)
void swapSuccessors()
Swap the successors of this branch instruction.
static BranchInst * Create(BasicBlock *IfTrue, BasicBlock::iterator InsertBefore)
bool isConditional() const
BasicBlock * getSuccessor(unsigned i) const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Value * getCondition() const
Value * getArgOperand(unsigned i) const
void setArgOperand(unsigned i, Value *v)
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
This is the shared class of boolean and integer constants.
static ConstantInt * getTrue(LLVMContext &Context)
static ConstantInt * getFalse(LLVMContext &Context)
This is an important base class in LLVM.
bool isOneValue() const
Returns true if the value is one.
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
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.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
void applyUpdates(ArrayRef< UpdateType > Updates)
Inform the dominator tree about a sequence of CFG edge insertions and deletions and perform a batch u...
void insertEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge insertion and update the tree.
static constexpr UpdateKind Delete
static constexpr UpdateKind Insert
void deleteEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge deletion and update the tree.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
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 class represents a freeze function that returns random concrete value if an operand is either a ...
This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to give precise answers on "may...
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...
void computeLoopSafetyInfo(const Loop *CurLoop) override
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
Value * CreateFreeze(Value *V, const Twine &Name="")
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
const BasicBlock * getParent() const
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
bool isTerminator() const
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
A wrapper class for inspecting calls to intrinsic functions.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
void markLoopAsDeleted(Loop &L, llvm::StringRef Name)
Loop passes should use this method to indicate they have deleted a loop from the nest.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
bool isInnermost() const
Return true if the loop does not contain any (natural) loops.
unsigned getNumBlocks() const
Get the number of blocks in this loop in constant time.
BlockT * getHeader() const
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
void reserveBlocks(unsigned size)
interface to do reserve() for Blocks
iterator_range< block_iterator > blocks() const
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
bool isLoopExiting(const BlockT *BB) const
True if terminator in the block can branch to another block that is outside of the current loop.
LoopT * removeChildLoop(iterator I)
This removes the specified child from being a subloop of this loop.
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
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
LoopT * AllocateLoop(ArgsTy &&...Args)
LoopT * removeLoop(iterator I)
This removes the specified top-level loop from this loop info object.
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
void destroy(LoopT *L)
Destroy a loop that has been removed from the LoopInfo nest.
Represents a single loop in the control flow graph.
StringRef getName() const
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
static MDString * get(LLVMContext &Context, StringRef Str)
Represents a read-write access to memory, whether it is a must-alias, or a may-alias.
An analysis that produces MemorySSA for a function.
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
void removeEdge(BasicBlock *From, BasicBlock *To)
Update the MemoryPhi in To following an edge deletion between From and To.
void updateForClonedLoop(const LoopBlocksRPO &LoopBlocks, ArrayRef< BasicBlock * > ExitBlocks, const ValueToValueMapTy &VM, bool IgnoreIncomingWithNoClones=false)
Update MemorySSA after a loop was cloned, given the blocks in RPO order, the exit blocks and a 1:1 ma...
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 removeDuplicatePhiEdgesBetween(const BasicBlock *From, const BasicBlock *To)
Update the MemoryPhi in To to have a single incoming edge from From, following a CFG change that repl...
void removeBlocks(const SmallSetVector< BasicBlock *, 8 > &DeadBlocks)
Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was spliced into From and To.
void applyInsertUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT)
Apply CFG insert updates, analogous with the DT edge updates.
void applyUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT, bool UpdateDTFirst=false)
Apply CFG updates, analogous with the DT edge updates.
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
void updateExitBlocksForClonedLoop(ArrayRef< BasicBlock * > ExitBlocks, const ValueToValueMapTy &VMap, DominatorTree &DT)
Update phi nodes in exit block successors following cloning.
Encapsulates MemorySSA, including all data associated with memory accesses.
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.
A Module instance is used to store all the information related to an LLVM module.
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
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...
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
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.
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
Analysis providing profile information.
bool hasProfileSummary() const
Returns true if profile summary is available.
bool isColdBlock(const BBType *BB, BFIT *BFI) const
Returns true if BasicBlock BB is considered cold.
The main scalar evolution driver.
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
void forgetTopmostLoop(const Loop *L)
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
This class represents the LLVM 'select' instruction.
size_type size() const
Determine the number of elements in the SetVector.
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
iterator begin()
Get an iterator to the beginning of the SetVector.
bool insert(const value_type &X)
Insert a new element into the SetVector.
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
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.
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 append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
iterator insert(iterator I, T &&Elt)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
void setSuccessorWeight(unsigned idx, CaseWeightOpt W)
Instruction::InstListType::iterator eraseFromParent()
Delegate the call to the underlying SwitchInst::eraseFromParent() and mark this object to not touch t...
void addCase(ConstantInt *OnVal, BasicBlock *Dest, CaseWeightOpt W)
Delegate the call to the underlying SwitchInst::addCase() and set the specified branch weight for the...
CaseWeightOpt getSuccessorWeight(unsigned idx)
std::optional< uint32_t > CaseWeightOpt
SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I)
Delegate the call to the underlying SwitchInst::removeCase() and remove correspondent branch weight.
unsigned getSuccessorIndex() const
Returns successor index for current case successor.
BasicBlockT * getCaseSuccessor() const
Resolves successor for current case.
ConstantIntT * getCaseValue() const
Resolves case value for current case.
static SwitchInst * Create(Value *Value, BasicBlock *Default, unsigned NumCases, BasicBlock::iterator InsertBefore)
BasicBlock * getDefaultDest() const
void setDefaultDest(BasicBlock *DefaultCase)
iterator_range< CaseIt > cases()
Iteration adapter for range-for loops.
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
void push_back(EltTy NewVal)
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
unsigned getIntegerBitWidth() const
bool isIntegerTy() const
True if this is an instance of IntegerType.
A Use represents the edge between a Value definition and its users.
ValueT lookup(const KeyT &Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
size_type count(const KeyT &Val) const
Return 1 if the specified key is in the map, 0 otherwise.
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void setName(const Twine &Name)
Change the name of the value.
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< use_iterator > uses()
StringRef getName() const
Return a constant reference to the value's name.
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.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
bool match(Val *V, const Pattern &P)
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
void stable_sort(R &&Range)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
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 RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
auto successors(const MachineBasicBlock *BB)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
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...
MDNode * findOptionMDForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for a loop.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
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)
BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, DebugInfoFinder *DIFinder=nullptr)
Return a copy of the specified basic block, but without embedding the block into a particular functio...
detail::zippy< detail::zip_first, T, U, Args... > zip_first(T &&t, U &&u, Args &&...args)
zip iterator that, for the sake of efficiency, assumes the first iteratee to be the shortest.
void sort(IteratorTy Start, IteratorTy End)
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool VerifyLoopInfo
Enable verification of loop info.
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
bool VerifyMemorySSA
Enables verification of MemorySSA.
bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Ensure that all exit blocks of the loop are dedicated exits.
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
llvm::MDNode * makePostTransformationMetadata(llvm::LLVMContext &Context, MDNode *OrigLoopID, llvm::ArrayRef< llvm::StringRef > RemovePrefixes, llvm::ArrayRef< llvm::MDNode * > AddAttrs)
Create a new LoopID after the loop has been transformed.
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 pred_empty(const BasicBlock *BB)
Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
std::optional< IVConditionInfo > hasPartialIVCondition(const Loop &L, unsigned MSSAThreshold, const MemorySSA &MSSA, AAResults &AA)
Check if the loop header has a conditional branch that is not loop-invariant, because it involves loa...
bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put loop into LCSSA form.
void RemapDbgRecordRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Remap the Values used in the DbgRecords Range using the value map VM.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
A special type used by analysis passes to provide an address that identifies that particular analysis...
static void collectEphemeralValues(const Loop *L, AssumptionCache *AC, SmallPtrSetImpl< const Value * > &EphValues)
Collect a loop's ephemeral values (those used only by an assume or similar intrinsics in the loop).
Description of the encoding of one expression Op.
Struct to hold information about a partially invariant condition.
SmallVector< Instruction * > InstToDuplicate
Instructions that need to be duplicated and checked for the unswitching condition.
Constant * KnownValue
Constant to indicate for which value the condition is invariant.
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
TargetTransformInfo & TTI
Direction
An enum for the direction of the loop.
A CRTP mix-in to automatically provide informational APIs needed for passes.