Go to the documentation of this file.
66 #define DEBUG_TYPE "simple-loop-unswitch"
71 STATISTIC(NumBranches,
"Number of branches unswitched");
72 STATISTIC(NumSwitches,
"Number of switches unswitched");
73 STATISTIC(NumGuards,
"Number of guards turned into branches for unswitching");
74 STATISTIC(NumTrivial,
"Number of unswitches that are trivial");
76 NumCostMultiplierSkipped,
77 "Number of unswitch candidates that had their cost multiplier skipped");
81 cl::desc(
"Forcibly enables non-trivial loop unswitching rather than "
82 "following the configuration passed into the pass."));
86 cl::desc(
"The cost threshold for unswitching a loop."));
90 cl::desc(
"Enable unswitch cost multiplier that prohibits exponential "
91 "explosion in nontrivial unswitch."));
94 cl::desc(
"Toplevel siblings divisor for cost multiplier."));
97 cl::desc(
"Number of unswitch candidates that are ignored when calculating "
101 cl::desc(
"If enabled, simple loop unswitching will also consider "
102 "llvm.experimental.guard intrinsics as unswitch candidates."));
104 "simple-loop-unswitch-drop-non-trivial-implicit-null-checks",
106 cl::desc(
"If enabled, drop make.implicit metadata in unswitched implicit "
107 "null checks to save time analyzing if we can keep it."));
110 cl::desc(
"Max number of memory uses to explore during "
111 "partial unswitching analysis"),
115 cl::desc(
"If enabled, the freeze instruction will be added to condition "
116 "of loop unswitch to prevent miscompilation."));
139 "Only need to walk the graph if root itself is not invariant.");
148 Worklist.push_back(&Root);
152 for (
Value *OpV :
I.operand_values()) {
154 if (isa<Constant>(OpV))
169 if (Visited.
insert(OpI).second)
170 Worklist.push_back(OpI);
173 }
while (!Worklist.empty());
180 assert(!isa<Constant>(Invariant) &&
"Why are we unswitching on a constant?");
185 Instruction *UserI = dyn_cast<Instruction>(U.getUser());
198 auto *PN = dyn_cast<PHINode>(&
I);
221 for (
Value *Inv : Invariants) {
224 FrozenInvariants.push_back(Inv);
230 Direction ? &NormalSucc : &UnswitchedSucc);
239 for (
auto *Val :
reverse(ToDuplicate)) {
242 BB.getInstList().insert(
BB.end(), NewInst);
253 auto *DefiningAccess = MemUse->getDefiningAccess();
255 while (L.
contains(DefiningAccess->getBlock())) {
258 if (
auto *MemPhi = dyn_cast<MemoryPhi>(DefiningAccess))
262 DefiningAccess = cast<MemoryDef>(DefiningAccess)->getDefiningAccess();
273 Direction ? &NormalSucc : &UnswitchedSucc);
290 for (
auto i : seq<int>(0, PN.getNumOperands())) {
291 assert(PN.getIncomingBlock(
i) == &OldExitingBB &&
292 "Found incoming block different from unique predecessor!");
293 PN.setIncomingBlock(
i, &OldPH);
310 assert(&ExitBB != &UnswitchedBB &&
311 "Must have different loop exit and unswitched blocks!");
315 PN.getName() +
".split", InsertPt);
326 for (
int i = PN.getNumIncomingValues() - 1;
i >= 0; --
i) {
327 if (PN.getIncomingBlock(
i) != &OldExitingBB)
330 Value *Incoming = PN.getIncomingValue(
i);
333 PN.removeIncomingValue(
i);
335 NewPN->addIncoming(Incoming, &OldPH);
341 NewPN->addIncoming(&PN, &ExitBB);
360 Loop *NewParentL =
nullptr;
361 for (
auto *ExitBB : Exits)
363 if (!NewParentL || NewParentL->
contains(ExitL))
366 if (NewParentL == OldParentL)
372 "Can only hoist this loop up the nest!");
377 "Parent loop of this loop should contain this loop's preheader!");
392 for (
Loop *OldContainingL = OldParentL; OldContainingL != NewParentL;
396 return BB == &Preheader || L.contains(BB);
399 OldContainingL->getBlocksSet().erase(&Preheader);
401 OldContainingL->getBlocksSet().erase(
BB);
423 Loop *Current = TopMost;
453 LLVM_DEBUG(
dbgs() <<
" Trying to unswitch branch: " << BI <<
"\n");
460 bool FullUnswitch =
false;
467 if (
auto *CondInst = dyn_cast<Instruction>(
Cond))
469 if (Invariants.
empty()) {
476 bool ExitDirection =
true;
477 int LoopExitSuccIdx = 0;
480 ExitDirection =
false;
488 auto *ContinueBB = BI.
getSuccessor(1 - LoopExitSuccIdx);
491 LLVM_DEBUG(
dbgs() <<
" Loop exit PHI's aren't loop-invariant!\n");
504 "non-full unswitch!\n");
510 dbgs() <<
" unswitching trivial invariant conditions for: " << BI
512 for (
Value *Invariant : Invariants) {
513 dbgs() <<
" " << *Invariant <<
" == true";
514 if (Invariant != Invariants.back())
545 if (FullUnswitch && LoopExitBB->getUniquePredecessor()) {
547 "A branch's parent isn't a predecessor!");
548 UnswitchedBB = LoopExitBB;
551 SplitBlock(LoopExitBB, &LoopExitBB->front(), &DT, &LI, MSSAU);
571 ParentBB->getInstList().push_back(BI.
clone());
584 "Must have an `or` of `i1`s or `select i1 X, true, Y`s for the "
588 "Must have an `and` of `i1`s or `select i1 X, Y, false`s for the"
591 *OldPH, Invariants, ExitDirection, *UnswitchedBB, *NewPH,
610 ParentBB->getTerminator()->eraseFromParent();
622 if (UnswitchedBB == LoopExitBB)
626 *ParentBB, *OldPH, FullUnswitch);
637 for (
Value *Invariant : Invariants)
684 Value *LoopCond =
SI.getCondition();
690 auto *ParentBB =
SI.getParent();
697 auto IsTriviallyUnswitchableExitBlock = [&](
BasicBlock &BBToCheck) {
708 auto *TI = BBToCheck.getTerminator();
709 bool isUnreachable = isa<UnreachableInst>(TI);
710 return !isUnreachable ||
711 (isUnreachable && (BBToCheck.getFirstNonPHIOrDbg() != TI));
715 for (
auto Case :
SI.cases())
716 if (IsTriviallyUnswitchableExitBlock(*Case.getCaseSuccessor()))
717 ExitCaseIndices.push_back(Case.getCaseIndex());
721 if (IsTriviallyUnswitchableExitBlock(*
SI.getDefaultDest())) {
722 DefaultExitBB =
SI.getDefaultDest();
723 }
else if (ExitCaseIndices.empty())
738 SI.setDefaultDest(
nullptr);
741 if (!ExitL || ExitL->
contains(OuterL))
750 ExitCases.reserve(ExitCaseIndices.size());
755 auto CaseI =
SI.case_begin() +
Index;
758 if (!ExitL || ExitL->
contains(OuterL))
762 ExitCases.emplace_back(CaseI->getCaseValue(), CaseI->getCaseSuccessor(),
W);
777 if (
SI.getNumCases() > 0 &&
779 return Case.getCaseSuccessor() == SI.case_begin()->getCaseSuccessor();
781 CommonSuccBB =
SI.case_begin()->getCaseSuccessor();
782 if (!DefaultExitBB) {
786 if (
SI.getNumCases() == 0)
787 CommonSuccBB =
SI.getDefaultDest();
788 else if (
SI.getDefaultDest() != CommonSuccBB)
789 CommonSuccBB =
nullptr;
815 UnswitchedExitBBs.
insert(DefaultExitBB);
823 DefaultExitBB = SplitExitBBMap[DefaultExitBB] = SplitBB;
828 for (
auto &ExitCase :
reverse(ExitCases)) {
836 if (UnswitchedExitBBs.
insert(ExitBB).second)
843 BasicBlock *&SplitExitBB = SplitExitBBMap[ExitBB];
852 std::get<1>(ExitCase) = SplitExitBB;
857 for (
auto &ExitCase :
reverse(ExitCases)) {
859 BasicBlock *UnswitchedBB = std::get<1>(ExitCase);
861 NewSIW.
addCase(CaseVal, UnswitchedBB, std::get<2>(ExitCase));
872 for (
const auto &Case :
SI.cases())
875 }
else if (DefaultCaseWeight) {
878 for (
const auto &Case :
SI.cases()) {
881 "case weight must be defined as default case weight is defined");
896 bool SkippedFirst = DefaultExitBB ==
nullptr;
897 for (
auto Case :
SI.cases()) {
899 "Non-common successor!");
911 }
else if (DefaultExitBB) {
913 "If we had no cases we'd have a common successor!");
918 auto LastCaseI = std::prev(
SI.case_end());
920 SI.setDefaultDest(LastCaseI->getCaseSuccessor());
931 for (
auto *UnswitchedExitBB : UnswitchedExitBBs) {
932 DTUpdates.push_back({DT.
Delete, ParentBB, UnswitchedExitBB});
933 DTUpdates.push_back({DT.
Insert, OldPH, UnswitchedExitBB});
935 for (
auto SplitUnswitchedPair : SplitExitBBMap) {
936 DTUpdates.push_back({DT.
Delete, ParentBB, SplitUnswitchedPair.first});
937 DTUpdates.push_back({DT.
Insert, OldPH, SplitUnswitchedPair.second});
978 bool Changed =
false;
993 Visited.
insert(CurrentBB);
1000 if (!isa<MemoryPhi>(*Defs->begin()) || (++Defs->begin() != Defs->end()))
1008 if (
auto *
SI = dyn_cast<SwitchInst>(CurrentTerm)) {
1012 if (isa<Constant>(
SI->getCondition()))
1026 auto *BI = dyn_cast<BranchInst>(CurrentBB->
getTerminator());
1027 if (!BI || BI->isConditional())
1030 CurrentBB = BI->getSuccessor(0);
1034 auto *BI = dyn_cast<BranchInst>(CurrentTerm);
1042 if (!BI->isConditional() ||
1057 if (BI->isConditional())
1061 CurrentBB = BI->getSuccessor(0);
1066 }
while (L.
contains(CurrentBB) && Visited.
insert(CurrentBB).second);
1113 NewBlocks.push_back(NewBB);
1114 VMap[OldBB] = NewBB;
1122 auto It = DominatingSucc.
find(
BB);
1123 return It != DominatingSucc.
end() && It->second != UnswitchedSuccBB;
1127 auto *ClonedPH = CloneBlock(LoopPH);
1130 for (
auto *LoopBB : L.
blocks())
1131 if (!SkipBlock(LoopBB))
1137 for (
auto *ExitBB : ExitBlocks) {
1138 if (SkipBlock(ExitBB))
1146 auto *MergeBB =
SplitBlock(ExitBB, &ExitBB->front(), &DT, &LI, MSSAU);
1151 MergeBB->takeName(ExitBB);
1152 ExitBB->setName(
Twine(MergeBB->getName()) +
".split");
1155 auto *ClonedExitBB = CloneBlock(ExitBB);
1156 assert(ClonedExitBB->getTerminator()->getNumSuccessors() == 1 &&
1157 "Exit block should have been split to have one successor!");
1158 assert(ClonedExitBB->getTerminator()->getSuccessor(0) == MergeBB &&
1159 "Cloned exit block has the wrong successor!");
1165 std::prev(ClonedExitBB->end())))) {
1172 (isa<PHINode>(
I) || isa<LandingPadInst>(
I) || isa<CatchPadInst>(
I)) &&
1173 "Bad instruction in exit block!");
1175 assert(VMap.
lookup(&
I) == &ClonedI &&
"Mismatch in the value map!");
1179 &*MergeBB->getFirstInsertionPt());
1180 I.replaceAllUsesWith(MergePN);
1181 MergePN->addIncoming(&
I, ExitBB);
1182 MergePN->addIncoming(&ClonedI, ClonedExitBB);
1191 for (
auto *ClonedBB : NewBlocks)
1195 if (
auto *II = dyn_cast<AssumeInst>(&
I))
1201 for (
auto *LoopBB : L.
blocks())
1202 if (SkipBlock(LoopBB))
1204 if (
auto *ClonedSuccBB = cast_or_null<BasicBlock>(VMap.
lookup(SuccBB)))
1205 for (
PHINode &PN : ClonedSuccBB->phis())
1206 PN.removeIncomingValue(LoopBB,
false);
1210 auto *ClonedParentBB = cast<BasicBlock>(VMap.
lookup(ParentBB));
1212 if (SuccBB == UnswitchedSuccBB)
1215 auto *ClonedSuccBB = cast_or_null<BasicBlock>(VMap.
lookup(SuccBB));
1219 ClonedSuccBB->removePredecessor(ClonedParentBB,
1225 auto *ClonedSuccBB = cast<BasicBlock>(VMap.
lookup(UnswitchedSuccBB));
1226 Instruction *ClonedTerminator = ClonedParentBB->getTerminator();
1229 Value *ClonedConditionToErase =
nullptr;
1230 if (
auto *BI = dyn_cast<BranchInst>(ClonedTerminator))
1231 ClonedConditionToErase = BI->getCondition();
1232 else if (
auto *
SI = dyn_cast<SwitchInst>(ClonedTerminator))
1233 ClonedConditionToErase =
SI->getCondition();
1238 if (ClonedConditionToErase)
1245 for (
PHINode &PN : ClonedSuccBB->phis()) {
1249 for (
int i = PN.getNumOperands() - 1;
i >= 0; --
i) {
1250 if (PN.getIncomingBlock(
i) != ClonedParentBB)
1256 PN.removeIncomingValue(
i,
false);
1262 for (
auto *ClonedBB : NewBlocks) {
1264 if (SuccSet.
insert(SuccBB).second)
1280 auto AddClonedBlocksToLoop = [&](
Loop &OrigL,
Loop &ClonedL) {
1281 assert(ClonedL.getBlocks().empty() &&
"Must start with an empty loop!");
1284 auto *ClonedBB = cast<BasicBlock>(VMap.
lookup(
BB));
1285 ClonedL.addBlockEntry(ClonedBB);
1298 AddClonedBlocksToLoop(OrigRootL, *ClonedRootL);
1310 LoopsToClone.push_back({ClonedRootL, ChildL});
1312 Loop *ClonedParentL, *L;
1313 std::tie(ClonedParentL, L) = LoopsToClone.
pop_back_val();
1316 AddClonedBlocksToLoop(*L, *ClonedL);
1318 LoopsToClone.push_back({ClonedL, ChildL});
1319 }
while (!LoopsToClone.empty());
1340 Loop *ClonedL =
nullptr;
1345 auto *ClonedPH = cast<BasicBlock>(VMap.
lookup(OrigPH));
1346 auto *ClonedHeader = cast<BasicBlock>(VMap.
lookup(OrigHeader));
1352 Loop *ParentL =
nullptr;
1356 for (
auto *ExitBB : ExitBlocks)
1357 if (
auto *ClonedExitBB = cast_or_null<BasicBlock>(VMap.
lookup(ExitBB)))
1359 ExitLoopMap[ClonedExitBB] = ExitL;
1360 ClonedExitsInLoops.push_back(ClonedExitBB);
1361 if (!ParentL || (ParentL != ExitL && ParentL->
contains(ExitL)))
1366 "The computed parent loop should always contain (or be) the parent of "
1367 "the original loop.");
1375 if (
auto *ClonedBB = cast_or_null<BasicBlock>(VMap.
lookup(
BB)))
1376 ClonedLoopBlocks.
insert(ClonedBB);
1387 if (Pred == ClonedPH)
1392 assert(ClonedLoopBlocks.
count(Pred) &&
"Found a predecessor of the loop "
1393 "header other than the preheader "
1394 "that is not part of the loop!");
1399 if (BlocksInClonedLoop.
insert(Pred).second && Pred != ClonedHeader)
1400 Worklist.push_back(Pred);
1406 if (!BlocksInClonedLoop.
empty()) {
1407 BlocksInClonedLoop.
insert(ClonedHeader);
1409 while (!Worklist.empty()) {
1412 "Didn't put block into the loop set!");
1420 if (ClonedLoopBlocks.
count(Pred) &&
1421 BlocksInClonedLoop.
insert(Pred).second)
1422 Worklist.push_back(Pred);
1432 NonChildClonedLoops.push_back(ClonedL);
1441 auto *ClonedBB = cast_or_null<BasicBlock>(VMap.
lookup(
BB));
1442 if (!ClonedBB || !BlocksInClonedLoop.
count(ClonedBB))
1455 PL->addBlockEntry(ClonedBB);
1462 for (
Loop *ChildL : OrigL) {
1463 auto *ClonedChildHeader =
1464 cast_or_null<BasicBlock>(VMap.
lookup(ChildL->getHeader()));
1465 if (!ClonedChildHeader || !BlocksInClonedLoop.
count(ClonedChildHeader))
1471 for (
auto *ChildLoopBB : ChildL->blocks())
1473 cast<BasicBlock>(VMap.
lookup(ChildLoopBB))) &&
1474 "Child cloned loop has a header within the cloned outer "
1475 "loop but not all of its blocks!");
1490 if (BlocksInClonedLoop.
empty())
1491 UnloopedBlockSet.
insert(ClonedPH);
1492 for (
auto *ClonedBB : ClonedLoopBlocks)
1493 if (!BlocksInClonedLoop.
count(ClonedBB))
1494 UnloopedBlockSet.
insert(ClonedBB);
1500 auto OrderedClonedExitsInLoops = ClonedExitsInLoops;
1502 return ExitLoopMap.
lookup(
LHS)->getLoopDepth() <
1508 while (!UnloopedBlockSet.
empty() && !OrderedClonedExitsInLoops.empty()) {
1509 assert(Worklist.empty() &&
"Didn't clear worklist!");
1511 BasicBlock *ExitBB = OrderedClonedExitsInLoops.pop_back_val();
1516 Worklist.push_back(ExitBB);
1526 if (!UnloopedBlockSet.
erase(PredBB)) {
1528 (BlocksInClonedLoop.
count(PredBB) || ExitLoopMap.
count(PredBB)) &&
1529 "Predecessor not mapped to a loop!");
1536 bool Inserted = ExitLoopMap.
insert({PredBB, ExitL}).second;
1538 assert(Inserted &&
"Should only visit an unlooped block once!");
1541 Worklist.push_back(PredBB);
1543 }
while (!Worklist.empty());
1552 for (
auto *
BB : llvm::concat<BasicBlock *const>(
1553 makeArrayRef(ClonedPH), ClonedLoopBlocks, ClonedExitsInLoops))
1555 OuterL->addBasicBlockToLoop(
BB, LI);
1558 for (
auto &BBAndL : ExitLoopMap) {
1559 auto *
BB = BBAndL.first;
1560 auto *OuterL = BBAndL.second;
1562 "Failed to put all blocks into outer loops!");
1569 for (
Loop *ChildL : OrigL) {
1570 auto *ClonedChildHeader =
1571 cast_or_null<BasicBlock>(VMap.
lookup(ChildL->getHeader()));
1572 if (!ClonedChildHeader || BlocksInClonedLoop.
count(ClonedChildHeader))
1576 for (
auto *ChildLoopBB : ChildL->blocks())
1578 "Cloned a child loop header but not all of that loops blocks!");
1582 *ChildL, ExitLoopMap.lookup(ClonedChildHeader), VMap, LI));
1588 ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps,
1593 for (
auto &VMap : VMaps)
1594 if (
BasicBlock *ClonedBB = cast_or_null<BasicBlock>(VMap->lookup(
BB)))
1597 SuccBB->removePredecessor(ClonedBB);
1598 DeadBlocks.push_back(ClonedBB);
1610 BB->dropAllReferences();
1613 BB->eraseFromParent();
1631 while (!DeathCandidates.empty()) {
1636 DeathCandidates.push_back(SuccBB);
1653 for (
auto *
BB : DeadBlockSet)
1654 ParentL->getBlocksSet().erase(
BB);
1656 [&](
BasicBlock *
BB) { return DeadBlockSet.count(BB); });
1662 if (!DeadBlockSet.count(ChildL->getHeader()))
1665 assert(llvm::all_of(ChildL->blocks(),
1666 [&](BasicBlock *ChildBB) {
1667 return DeadBlockSet.count(ChildBB);
1669 "If the child loop header is dead all blocks in the child loop must "
1670 "be dead as well!");
1671 DestroyLoopCB(*ChildL, ChildL->
getName());
1679 for (
auto *
BB : DeadBlockSet) {
1688 BB->dropAllReferences();
1693 for (
auto *
BB : DeadBlockSet)
1694 BB->eraseFromParent();
1727 assert(L.
contains(Pred) &&
"Found a predecessor of the loop header other "
1728 "than the preheader that is not part of the "
1734 if (LoopBlockSet.
insert(Pred).second && Pred != Header)
1735 Worklist.push_back(Pred);
1739 if (LoopBlockSet.
empty())
1740 return LoopBlockSet;
1743 while (!Worklist.empty()) {
1745 assert(LoopBlockSet.
count(
BB) &&
"Didn't put block into the loop set!");
1758 "Should not reach a loop *outside* this loop!");
1761 auto *InnerPH = InnerL->getLoopPreheader();
1762 assert(L.
contains(InnerPH) &&
"Cannot contain an inner loop block "
1763 "but not contain the inner loop "
1765 if (!LoopBlockSet.
insert(InnerPH).second)
1775 for (
auto *InnerBB : InnerL->blocks()) {
1776 if (InnerBB ==
BB) {
1778 "Block should already be in the set!");
1782 LoopBlockSet.
insert(InnerBB);
1787 Worklist.push_back(InnerPH);
1795 Worklist.push_back(Pred);
1798 assert(LoopBlockSet.
count(Header) &&
"Cannot fail to add the header!");
1802 return LoopBlockSet;
1826 Loop *ParentL =
nullptr;
1830 for (
auto *ExitBB : ExitBlocks)
1832 ExitLoops.push_back(ExitL);
1833 ExitsInLoops.push_back(ExitBB);
1834 if (!ParentL || (ParentL != ExitL && ParentL->
contains(ExitL)))
1846 if (!LoopBlockSet.empty() && L.
getParentLoop() != ParentL) {
1850 IL->getBlocksSet().erase(PH);
1852 IL->getBlocksSet().erase(
BB);
1854 return BB == PH || L.contains(BB);
1869 LoopBlockSet.empty()
1871 : std::stable_partition(
1872 Blocks.begin(), Blocks.end(),
1873 [&](
BasicBlock *
BB) { return LoopBlockSet.count(BB); });
1877 if (LoopBlockSet.empty())
1878 UnloopedBlocks.
insert(PH);
1881 for (
auto *
BB :
make_range(BlocksSplitI, Blocks.end()))
1883 Blocks.erase(BlocksSplitI, Blocks.end());
1895 auto RemoveUnloopedBlocksFromLoop =
1897 for (
auto *
BB : UnloopedBlocks)
1900 return UnloopedBlocks.count(BB);
1905 while (!UnloopedBlocks.
empty() && !ExitsInLoops.empty()) {
1906 assert(Worklist.empty() &&
"Didn't clear worklist!");
1907 assert(NewExitLoopBlocks.empty() &&
"Didn't clear loop set!");
1912 assert(ExitL.
contains(&L) &&
"Exit loop must contain the inner loop!");
1918 for (; PrevExitL != &ExitL; PrevExitL = PrevExitL->
getParentLoop())
1919 RemoveUnloopedBlocksFromLoop(*PrevExitL, UnloopedBlocks);
1923 Worklist.push_back(ExitBB);
1933 if (!UnloopedBlocks.
erase(PredBB)) {
1934 assert((NewExitLoopBlocks.count(PredBB) ||
1936 "Predecessor not in a nested loop (or already visited)!");
1943 bool Inserted = NewExitLoopBlocks.insert(PredBB).second;
1945 assert(Inserted &&
"Should only visit an unlooped block once!");
1948 Worklist.push_back(PredBB);
1950 }
while (!Worklist.empty());
1955 for (
auto *
BB : NewExitLoopBlocks)
1962 NewExitLoopBlocks.clear();
1968 RemoveUnloopedBlocksFromLoop(*PrevExitL, UnloopedBlocks);
1969 for (
auto *
BB : UnloopedBlocks)
1978 auto SubLoopsSplitI =
1979 LoopBlockSet.empty()
1981 : std::stable_partition(
1982 SubLoops.begin(), SubLoops.end(), [&](
Loop *SubL) {
1983 return LoopBlockSet.count(SubL->getHeader());
1985 for (
auto *HoistedL :
make_range(SubLoopsSplitI, SubLoops.end())) {
1986 HoistedLoops.push_back(HoistedL);
1987 HoistedL->setParentLoop(
nullptr);
1997 if (
auto *NewParentL = LI.
getLoopFor(HoistedL->getLoopPreheader()))
1998 NewParentL->addChildLoop(HoistedL);
2002 SubLoops.erase(SubLoopsSplitI, SubLoops.end());
2005 if (Blocks.empty()) {
2006 assert(SubLoops.empty() &&
2007 "Failed to remove all subloops from the original loop!");
2024 template <
typename CallableT>
2027 DomWorklist.push_back(DT[
BB]);
2036 if (!Callable(
N->getBlock()))
2042 "Cannot visit a node twice when walking a tree!");
2043 DomWorklist.push_back(ChildN);
2045 }
while (!DomWorklist.empty());
2063 "Can only unswitch switches and conditional branch!");
2067 !PartiallyInvariant);
2070 "Cannot have other invariants with full unswitching!");
2073 "Partial unswitching requires an instruction as the condition!");
2086 if (!FullUnswitch) {
2090 PartiallyInvariant) &&
2091 "Only `or`, `and`, an `select`, partially invariant instructions "
2092 "can combine invariants being unswitched.");
2108 for (
auto Case :
SI->cases())
2109 if (Case.getCaseSuccessor() != RetainedSuccBB)
2110 UnswitchedSuccBBs.
insert(Case.getCaseSuccessor());
2112 assert(!UnswitchedSuccBBs.
count(RetainedSuccBB) &&
2113 "Should not unswitch the same successor we are retaining!");
2131 Loop *OuterExitL = &L;
2132 for (
auto *ExitBB : ExitBlocks) {
2134 if (!NewOuterExitL) {
2136 OuterExitL =
nullptr;
2139 if (NewOuterExitL != OuterExitL && NewOuterExitL->
contains(OuterExitL))
2140 OuterExitL = NewOuterExitL;
2153 bool InsertFreeze =
false;
2166 for (
auto *SuccBB : llvm::concat<BasicBlock *const>(
2168 if (SuccBB->getUniquePredecessor() ||
2170 return PredBB == ParentBB || DT.
dominates(SuccBB, PredBB);
2173 DominatingSucc[
BB] = SuccBB;
2192 for (
auto *SuccBB : UnswitchedSuccBBs) {
2195 L, LoopPH, SplitBB, ExitBlocks, ParentBB, SuccBB, RetainedSuccBB,
2196 DominatingSucc, *VMaps.back(), DTUpdates, AC, DT, LI, MSSAU);
2201 if (TI.
getMetadata(LLVMContext::MD_make_implicit)) {
2205 TI.
setMetadata(LLVMContext::MD_make_implicit,
nullptr);
2212 TI.
setMetadata(LLVMContext::MD_make_implicit,
nullptr);
2219 SplitBB->getTerminator()->eraseFromParent();
2223 SplitBB->getInstList().splice(SplitBB->end(), ParentBB->getInstList(), TI);
2227 ParentBB->getInstList().push_back(NewTI);
2242 assert(
SI &&
"Must either be a branch or switch!");
2245 assert(
SI->getDefaultDest() == RetainedSuccBB &&
2246 "Not retaining default successor!");
2247 SI->setDefaultDest(LoopPH);
2248 for (
auto &Case :
SI->cases())
2249 if (Case.getCaseSuccessor() == RetainedSuccBB)
2250 Case.setSuccessor(LoopPH);
2252 Case.setSuccessor(ClonedPHs.
find(Case.getCaseSuccessor())->second);
2255 auto Cond =
SI->getCondition();
2263 DTUpdates.push_back(
2278 for (
auto &VMap : VMaps)
2293 assert(UnswitchedSuccBBs.size() == 1 &&
2294 "Only one possible unswitched block for a branch!");
2308 "Not retaining default successor!");
2309 for (
auto &Case : NewSI->
cases())
2310 Case.getCaseSuccessor()->removePredecessor(
2322 ParentBB->getTerminator()->eraseFromParent();
2328 assert(BI &&
"Only branches have partial unswitching.");
2329 assert(UnswitchedSuccBBs.size() == 1 &&
2330 "Only one possible unswitched block for a branch!");
2334 if (PartiallyInvariant)
2336 *SplitBB, Invariants,
Direction, *ClonedPH, *LoopPH, L, MSSAU);
2339 *SplitBB, Invariants,
Direction, *ClonedPH, *LoopPH,
2349 for (
auto &VMap : VMaps)
2369 for (std::unique_ptr<ValueToValueMapTy> &VMap : VMaps)
2393 if (BI && !PartiallyInvariant) {
2398 assert(UnswitchedSuccBBs.size() == 1 &&
2399 "Only one possible unswitched block for a branch!");
2411 bool ReplaceUnswitched =
2412 FullUnswitch || (Invariants.
size() == 1) || PartiallyInvariant;
2420 for (
Value *Invariant : Invariants) {
2421 assert(!isa<Constant>(Invariant) &&
2422 "Should not be replacing constant values!");
2425 Instruction *UserI = dyn_cast<Instruction>(U.getUser());
2432 U.set(ContinueReplacement);
2433 else if (ReplaceUnswitched &&
2435 U.set(UnswitchedReplacement);
2452 auto UpdateLoop = [&](
Loop &UpdateL) {
2454 UpdateL.verifyLoop();
2455 for (
Loop *ChildL : UpdateL) {
2456 ChildL->verifyLoop();
2457 assert(ChildL->isRecursivelyLCSSAForm(DT, LI) &&
2458 "Perturbed a child loop's LCSSA form!");
2478 for (
Loop *UpdatedL :
2479 llvm::concat<Loop *>(NonChildClonedLoops, HoistedLoops)) {
2480 UpdateLoop(*UpdatedL);
2481 if (UpdatedL->isOutermost())
2482 OuterExitL =
nullptr;
2487 OuterExitL =
nullptr;
2492 if (OuterExitL != &L)
2493 for (
Loop *OuterL = ParentL; OuterL != OuterExitL;
2495 UpdateLoop(*OuterL);
2507 for (
Loop *UpdatedL : llvm::concat<Loop *>(NonChildClonedLoops, HoistedLoops))
2508 if (UpdatedL->getParentLoop() == ParentL)
2509 SibLoops.push_back(UpdatedL);
2510 UnswitchCB(IsStillLoop, PartiallyInvariant, SibLoops);
2533 auto BBCostIt = BBCostMap.
find(
N.getBlock());
2534 if (BBCostIt == BBCostMap.
end())
2538 auto DTCostIt = DTCostMap.
find(&
N);
2539 if (DTCostIt != DTCostMap.
end())
2540 return DTCostIt->second;
2545 N.begin(),
N.end(), BBCostIt->second,
2547 return Sum + computeDomSubtreeCost(*ChildN, BBCostMap, DTCostMap);
2549 bool Inserted = DTCostMap.
insert({&
N, Cost}).second;
2551 assert(Inserted &&
"Should not insert a node while visiting children!");
2591 if (Successors.
insert(Succ).second)
2602 GuardedBlock->
setName(
"guarded");
2621 for (
auto *Succ : Successors)
2656 UnswitchCandidates) {
2669 NumCostMultiplierSkipped++;
2674 int SiblingsCount = (ParentL ? ParentL->getSubLoopsVector().size()
2675 : std::distance(LI.
begin(), LI.
end()));
2678 int UnswitchedClones = 0;
2679 for (
auto Candidate : UnswitchCandidates) {
2682 bool SkipExitingSuccessors = DT.
dominates(CondBlock, Latch);
2684 if (!SkipExitingSuccessors)
2690 return !SkipExitingSuccessors || L.
contains(SuccBB);
2692 UnswitchedClones +=
Log2_32(NonExitingSuccessors);
2700 unsigned ClonesPower =
2704 int SiblingsMultiplier =
2715 CostMultiplier =
std::min(SiblingsMultiplier * (1 << ClonesPower),
2719 <<
" (siblings " << SiblingsMultiplier <<
" * clones "
2720 << (1 << ClonesPower) <<
")"
2721 <<
" for unswitch candidate: " << TI <<
"\n");
2722 return CostMultiplier;
2737 bool CollectGuards =
false;
2741 if (GuardDecl && !GuardDecl->use_empty())
2742 CollectGuards =
true;
2753 auto *
Cond = cast<IntrinsicInst>(&
I)->getArgOperand(0);
2756 UnswitchCandidates.push_back({&
I, {
Cond}});
2759 if (
auto *
SI = dyn_cast<SwitchInst>(
BB->getTerminator())) {
2762 if (!isa<Constant>(
SI->getCondition()) &&
2764 UnswitchCandidates.push_back({
SI, {
SI->getCondition()}});
2768 auto *BI = dyn_cast<BranchInst>(
BB->getTerminator());
2769 if (!BI || !BI->isConditional() || isa<Constant>(BI->getCondition()) ||
2770 BI->getSuccessor(0) == BI->getSuccessor(1))
2774 if (isa<Constant>(
Cond))
2778 UnswitchCandidates.push_back({BI, {
Cond}});
2786 if (Invariants.
empty())
2789 UnswitchCandidates.push_back({BI,
std::move(Invariants)});
2796 !
any_of(UnswitchCandidates, [&L](
auto &TerminatorAndInvariants) {
2797 return TerminatorAndInvariants.first == L.
getHeader()->getTerminator();
2802 dbgs() <<
"simple-loop-unswitch: Found partially invariant condition "
2803 << *
Info->InstToDuplicate[0] <<
"\n");
2804 PartialIVInfo = *
Info;
2808 UnswitchCandidates.push_back(
2814 if (UnswitchCandidates.empty())
2825 if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))
2835 for (
auto *ExitBB : ExitBlocks) {
2836 auto *
I = ExitBB->getFirstNonPHI();
2837 if (isa<CleanupPadInst>(
I) || isa<CatchSwitchInst>(
I)) {
2838 LLVM_DEBUG(
dbgs() <<
"Cannot unswitch because of cleanuppad/catchswitch "
2845 dbgs() <<
"Considering " << UnswitchCandidates.size()
2846 <<
" non-trivial loop invariant conditions for unswitching.\n");
2869 for (
auto &
I : *
BB) {
2873 if (
I.getType()->isTokenTy() &&
I.isUsedOutsideOfBlock(
BB))
2875 if (
auto *CB = dyn_cast<CallBase>(&
I))
2876 if (CB->isConvergent() || CB->cannotDuplicate())
2881 assert(Cost >= 0 &&
"Must not have negative costs!");
2883 assert(LoopCost >= 0 &&
"Must not have negative loop costs!");
2884 BBCostMap[
BB] = Cost;
2913 if (!Visited.
insert(SuccBB).second)
2921 if (!FullUnswitch) {
2922 auto &BI = cast<BranchInst>(TI);
2925 if (SuccBB == BI.getSuccessor(1))
2928 if (SuccBB == BI.getSuccessor(0))
2931 SuccBB == BI.getSuccessor(0)) ||
2933 SuccBB == BI.getSuccessor(1)))
2941 if (SuccBB->getUniquePredecessor() ||
2943 return PredBB == &
BB || DT.
dominates(SuccBB, PredBB);
2946 assert(Cost <= LoopCost &&
2947 "Non-duplicated cost should never exceed total loop cost!");
2956 int SuccessorsCount =
isGuard(&TI) ? 2 : Visited.
size();
2957 assert(SuccessorsCount > 1 &&
2958 "Cannot unswitch a condition without multiple distinct successors!");
2959 return (LoopCost - Cost) * (SuccessorsCount - 1);
2964 for (
auto &TerminatorAndInvariants : UnswitchCandidates) {
2970 (Invariants.
size() == 1 &&
2975 int CostMultiplier =
2979 "cost multiplier needs to be in the range of 1..UnswitchThreshold");
2980 CandidateCost *= CostMultiplier;
2982 <<
" (multiplier: " << CostMultiplier <<
")"
2983 <<
" for unswitch candidate: " << TI <<
"\n");
2986 <<
" for unswitch candidate: " << TI <<
"\n");
2989 if (!BestUnswitchTI || CandidateCost < BestUnswitchCost) {
2990 BestUnswitchTI = &TI;
2991 BestUnswitchCost = CandidateCost;
2992 BestUnswitchInvariants = Invariants;
2995 assert(BestUnswitchTI &&
"Failed to find loop unswitch candidate");
2999 << BestUnswitchCost <<
"\n");
3003 if (BestUnswitchTI != PartialIVCondBranch)
3009 ExitBlocks, DT, LI, MSSAU);
3012 << BestUnswitchCost <<
") terminator: " << *BestUnswitchTI
3015 ExitBlocks, PartialIVInfo, DT, LI, AC,
3016 UnswitchCB, SE, MSSAU, DestroyLoopCB);
3049 "Loops must be in LCSSA form before unswitching.");
3059 UnswitchCB(
true,
false, {});
3074 bool ContinueWithNonTrivial =
3076 if (!ContinueWithNonTrivial)
3109 LLVM_DEBUG(
dbgs() <<
"Unswitching loop in " <<
F.getName() <<
": " << L
3114 std::string LoopName = std::string(L.
getName());
3116 auto UnswitchCB = [&L, &U, &LoopName](
bool CurrentLoopValid,
3117 bool PartiallyInvariant,
3120 if (!NewLoops.empty())
3121 U.addSiblingLoops(NewLoops);
3125 if (CurrentLoopValid) {
3126 if (PartiallyInvariant) {
3135 {DisableUnswitchMD});
3138 U.revisitCurrentLoop();
3140 U.markLoopAsDeleted(L, LoopName);
3144 U.markLoopAsDeleted(L,
Name);
3154 UnswitchCB, &AR.
SE, MSSAU ? MSSAU.
getPointer() :
nullptr,
3174 OS, MapClassName2PassName);
3177 OS << (NonTrivial ?
"" :
"no-") <<
"nontrivial;";
3178 OS << (Trivial ?
"" :
"no-") <<
"trivial";
3184 class SimpleLoopUnswitchLegacyPass :
public LoopPass {
3190 explicit SimpleLoopUnswitchLegacyPass(
bool NonTrivial =
false)
3215 LLVM_DEBUG(
dbgs() <<
"Unswitching loop in " <<
F.getName() <<
": " << *L
3218 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
3219 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
3220 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
3221 auto &
AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
3222 auto &
TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
3223 MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
3226 auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
3227 auto *SE = SEWP ? &SEWP->getSE() :
nullptr;
3229 auto UnswitchCB = [&L, &LPM](
bool CurrentLoopValid,
bool PartiallyInvariant,
3232 for (
auto *NewL : NewLoops)
3238 if (CurrentLoopValid) {
3242 if (!PartiallyInvariant)
3256 UnswitchCB, SE, &MSSAU, DestroyLoopCB);
3270 "Simple unswitch loops",
false,
false)
3281 return new SimpleLoopUnswitchLegacyPass(NonTrivial);
A set of analyses that are preserved following a run of a transformation pass.
bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put loop into LCSSA form.
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.
static Loop * cloneLoopNest(Loop &OrigRootL, Loop *RootParentL, const ValueToValueMapTy &VMap, LoopInfo &LI)
Recursively clone the specified loop and all of its children.
Pass * createSimpleLoopUnswitchLegacyPass(bool NonTrivial=false)
Create the legacy pass object for the simple loop unswitcher.
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
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."))
This is an optimization pass for GlobalISel generic memory operations.
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all of the successor blocks of this loop.
void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
const Function * getParent() const
Return the enclosing method, or null if none.
CaseWeightOpt getSuccessorWeight(unsigned idx)
Represents a single loop in the control flow graph.
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::lookup 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...
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.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
size_type size() const
Determine the number of elements in the SetVector.
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.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
static SwitchInst * Create(Value *Value, BasicBlock *Default, unsigned NumCases, Instruction *InsertBefore=nullptr)
static SmallPtrSet< const BasicBlock *, 16 > recomputeLoopBlockSet(Loop &L, LoopInfo &LI)
Recompute the set of blocks in a loop after unswitching.
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
The main scalar evolution driver.
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
void removeBlocks(const SmallSetVector< BasicBlock *, 8 > &DeadBlocks)
Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
static void unswitchNontrivialInvariants(Loop &L, Instruction &TI, ArrayRef< Value * > Invariants, SmallVectorImpl< BasicBlock * > &ExitBlocks, IVConditionInfo &PartialIVInfo, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, function_ref< void(bool, bool, ArrayRef< Loop * >)> UnswitchCB, ScalarEvolution *SE, MemorySSAUpdater *MSSAU, function_ref< void(Loop &, StringRef)> DestroyLoopCB)
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::begin iterator begin()
static int CalculateUnswitchCostMultiplier(Instruction &TI, Loop &L, LoopInfo &LI, DominatorTree &DT, ArrayRef< std::pair< Instruction *, TinyPtrVector< Value * >>> UnswitchCandidates)
Cost multiplier is a way to limit potentially exponential behavior of loop-unswitch.
static bool unswitchBestCondition(Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, AAResults &AA, TargetTransformInfo &TTI, function_ref< void(bool, bool, ArrayRef< Loop * >)> UnswitchCB, ScalarEvolution *SE, MemorySSAUpdater *MSSAU, function_ref< void(Loop &, StringRef)> DestroyLoopCB)
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
The legacy pass manager's analysis pass to compute loop information.
static bool areLoopExitPHIsLoopInvariant(Loop &L, BasicBlock &ExitingBB, BasicBlock &ExitBB)
Check that all the LCSSA PHI nodes in the loop exit block have trivial incoming values along this edg...
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
static constexpr UpdateKind Insert
void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was spliced into From and To.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
static BranchInst * turnGuardIntoBranch(IntrinsicInst *GI, Loop &L, SmallVectorImpl< BasicBlock * > &ExitBlocks, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU)
Turns a llvm.experimental.guard intrinsic into implicit control flow branch, making the following rep...
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::count size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
auto successors(MachineBasicBlock *BB)
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I)
Delegate the call to the underlying SwitchInst::removeCase() and remove correspondent branch weight.
LLVM_NODISCARD T pop_back_val()
iterator_range< CaseIt > cases()
Iteration adapter for range-for loops.
BasicBlock * getDefaultDest() const
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
bool isOneValue() const
Returns true if the value is one.
Function * getFunction(StringRef Name) const
Look up the specified function in the module symbol table.
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.
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...
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.
unsigned getNumBlocks() const
Get the number of blocks in this loop in constant time.
void applyUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT, bool UpdateDTFirst=false)
Apply CFG updates, analogous with the DT edge updates.
MemoryAccess * createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition, const BasicBlock *BB, MemorySSA::InsertionPlace Point)
Create a MemoryAccess in MemorySSA at a specified point in a block, with a specified clobbering defin...
void applyUpdates(ArrayRef< UpdateType > Updates)
Inform the dominator tree about a sequence of CFG edge insertions and deletions and perform a batch u...
void swapSuccessors()
Swap the successors of this branch instruction.
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
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.
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Analysis the ScalarEvolution expression for r is< loop > Outside the loop
LLVM Basic Block Representation.
constexpr const T * getPointer() const
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.
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
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 void replaceLoopInvariantUses(Loop &L, Value *Invariant, Constant &Replacement)
BasicBlockT * getCaseSuccessor() const
Resolves successor for current case.
This is the shared class of boolean and integer constants.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
void 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.
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.
Legacy analysis pass which computes MemorySSA.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
bool match(Val *V, const Pattern &P)
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
void insertEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge insertion and update the tree.
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."))
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
iterator begin()
Instruction iterator methods.
unsigned getSuccessorIndex() const
Returns successor index for current case successor.
Represent the analysis usage information of a pass.
void push_back(EltTy NewVal)
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.
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
iterator_range< block_iterator > blocks() const
void destroy(LoopT *L)
Destroy a loop that has been removed from the LoopInfo nest.
static cl::opt< int > UnswitchThreshold("unswitch-threshold", cl::init(50), cl::Hidden, cl::desc("The cost threshold for unswitching a loop."))
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
void setCondition(Value *V)
Legacy analysis pass which computes a DominatorTree.
static bool unswitchLoop(Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, AAResults &AA, TargetTransformInfo &TTI, bool Trivial, bool NonTrivial, function_ref< void(bool, bool, ArrayRef< Loop * >)> UnswitchCB, ScalarEvolution *SE, MemorySSAUpdater *MSSAU, function_ref< void(Loop &, StringRef)> DestroyLoopCB)
Unswitch control flow predicated on loop invariant conditions.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
STATISTIC(NumFunctions, "Total number of functions")
auto predecessors(MachineBasicBlock *BB)
This class implements an extremely fast bulk output stream that can only output to a stream.
void setName(const Twine &Name)
Change the name of the value.
void setSuccessorWeight(unsigned idx, CaseWeightOpt W)
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
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).
Analysis containing CSE Info
void visitDomSubTree(DominatorTree &DT, BasicBlock *BB, CallableT Callable)
Helper to visit a dominator subtree, invoking a callable on each node.
size_type count(const KeyT &Val) const
Return 1 if the specified key is in the map, 0 otherwise.
StringRef getName() const
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
static void deleteDeadClonedBlocks(Loop &L, ArrayRef< BasicBlock * > ExitBlocks, ArrayRef< std::unique_ptr< ValueToValueMapTy >> VMaps, DominatorTree &DT, MemorySSAUpdater *MSSAU)
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Direction
An enum for the direction of the loop.
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...
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
LoopT * AllocateLoop(ArgsTy &&... Args)
static TinyPtrVector< Value * > collectHomogenousInstGraphLoopInvariants(Loop &L, Instruction &Root, LoopInfo &LI)
Collect all of the loop invariant input values transitively used by the homogeneous instruction graph...
Value * getCondition() const
An efficient, type-erasing, non-owning reference to a callable.
void applyInsertUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT)
Apply CFG insert updates, analogous with the DT edge updates.
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
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...
static Value * skipTrivialSelect(Value *Cond)
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
This is an important base class in LLVM.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void removeEdge(BasicBlock *From, BasicBlock *To)
Update the MemoryPhi in To following an edge deletion between From and To.
void setDefaultDest(BasicBlock *DefaultCase)
LogicalOp_match< LHS, RHS, Instruction::Or > m_LogicalOr(const LHS &L, const RHS &R)
Matches L || R either in the form of L | R or L ? true : R.
Module * getParent()
Get the module that this global value is contained inside of...
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
void getUniqueExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop.
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...
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Encapsulates MemorySSA, including all data associated with memory accesses.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
initializer< Ty > init(const Ty &Val)
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Represents a read-write access to memory, whether it is a must-alias, or a may-alias.
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 MDString * get(LLVMContext &Context, StringRef Str)
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find iterator find(const_arg_type_t< KeyT > Val)
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
INITIALIZE_PASS_BEGIN(SimpleLoopUnswitchLegacyPass, "simple-loop-unswitch", "Simple unswitch loops", false, false) INITIALIZE_PASS_END(SimpleLoopUnswitchLegacyPass
unsigned getLoopDepth() const
Return the nesting level of this loop.
Constant * KnownValue
Constant to indicate for which value the condition is invariant.
StandardInstrumentations SI(Debug, VerifyEach)
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
std::vector< BlockT * > & getBlocksVector()
Return a direct, mutable handle to the blocks vector so that we can mutate it efficiently with techni...
SmallVector< Instruction * > InstToDuplicate
Instructions that need to be duplicated and checked for the unswitching condition.
void forgetTopmostLoop(const Loop *L)
An analysis that produces MemorySSA for a function.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
bool insert(const value_type &X)
Insert a new element into the SetVector.
static Loop * getTopMostExitingLoop(BasicBlock *ExitBB, LoopInfo &LI)
static void buildPartialUnswitchConditionalBranch(BasicBlock &BB, ArrayRef< Value * > Invariants, bool Direction, BasicBlock &UnswitchedSucc, BasicBlock &NormalSucc, bool InsertFreeze, Instruction *I, AssumptionCache *AC, DominatorTree &DT)
Copy a set of loop invariant values ToDuplicate and insert them at the end of BB and conditionally br...
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
LoopT * removeChildLoop(iterator I)
This removes the specified child from being a subloop of this loop.
static bool rebuildLoopAfterUnswitch(Loop &L, ArrayRef< BasicBlock * > ExitBlocks, LoopInfo &LI, SmallVectorImpl< Loop * > &HoistedLoops)
Rebuild a loop after unswitching removes some subset of blocks and edges.
std::vector< LoopT * > & getSubLoopsVector()
An immutable pass that tracks lazily created AssumptionCache objects.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
SmallVector< MachineOperand, 4 > Cond
StringRef - Represent a constant reference to a string, i.e.
A cache of @llvm.assume calls within a function.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
const DefsList * getBlockDefs(const BasicBlock *BB) const
Return the list of MemoryDef's and MemoryPhi's for a given basic block.
void initializeSimpleLoopUnswitchLegacyPassPass(PassRegistry &)
ConstantIntT * getCaseValue() const
Resolves case value for current case.
bool isOutermost() const
Return true if the loop does not have a parent (natural) loop.
void reserveBlocks(unsigned size)
interface to do reserve() for Blocks
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
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")))
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
LLVMContext & getContext() const
All values hold a context through their type.
simple loop Simple unswitch loops
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.
bool pred_empty(const BasicBlock *BB)
MDNode * findOptionMDForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for a loop.
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::insert std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
void setArgOperand(unsigned i, Value *v)
LoopT * removeLoop(iterator I)
This removes the specified top-level loop from this loop info object.
static ConstantInt * getFalse(LLVMContext &Context)
bool hasOptSize() const
Optimize this function for size (-Os) or minimum size (-Oz).
void updateExitBlocksForClonedLoop(ArrayRef< BasicBlock * > ExitBlocks, const ValueToValueMapTy &VMap, DominatorTree &DT)
Update phi nodes in exit block successors following cloning.
const Instruction & front() const
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
LLVMContext & getContext() const
Get the context in which this basic block lives.
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
bool isInnermost() const
Return true if the loop does not contain any (natural) loops.
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...
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Ensure that all exit blocks of the loop are dedicated exits.
void stable_sort(R &&Range)
static void deleteDeadBlocksFromLoop(Loop &L, SmallVectorImpl< BasicBlock * > &ExitBlocks, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU, function_ref< void(Loop &, StringRef)> DestroyLoopCB)
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...
static ConstantInt * getTrue(LLVMContext &Context)
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
void addCase(ConstantInt *OnVal, BasicBlock *Dest, CaseWeightOpt W)
Delegate the call to the underlying SwitchInst::addCase() and set the specified branch weight for the...
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)
void markLoopAsDeleted(Loop &L)
TargetTransformInfo & TTI
Value * CreateFreeze(Value *V, const Twine &Name="")
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end iterator end()
This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to give precise answers on "may...
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
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.
SmallPtrSetImpl< const BlockT * > & getBlocksSet()
Return a direct, mutable handle to the blocks set so that we can mutate it efficiently.
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
BlockT * getHeader() const
void sort(IteratorTy Start, IteratorTy End)
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Struct to hold information about a partially invariant condition.
bool isRecursivelyLCSSAForm(const DominatorTree &DT, const LoopInfo &LI) const
Return true if this Loop and all inner subloops are in LCSSA form.
Optional< IVConditionInfo > hasPartialIVCondition(Loop &L, unsigned MSSAThreshold, MemorySSA &MSSA, AAResults &AA)
Check if the loop header has a conditional branch that is not loop-invariant, because it involves loa...
SymbolTableList< Instruction >::iterator eraseFromParent()
Delegate the call to the underlying SwitchInst::eraseFromParent() and mark this object to not touch t...
A wrapper class for inspecting calls to intrinsic functions.
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
const InstListType & getInstList() const
Return the underlying instruction list container.
Pass interface - Implemented by all 'passes'.
void moveBefore(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it into the function that MovePos lives ...
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Value * getArgOperand(unsigned i) const
This class represents a freeze function that returns random concrete value if an operand is either a ...
LLVM_NODISCARD bool empty() const
static void rewritePHINodesForUnswitchedExitBlock(BasicBlock &UnswitchedBB, BasicBlock &OldExitingBB, BasicBlock &OldPH)
Rewrite the PHI nodes in an unswitched loop exit basic block.
const BasicBlock * getParent() const
bool isSafeToClone() const
Return true if the loop body is safe to clone in practice.
void computeLoopSafetyInfo(const Loop *CurLoop) override
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
size_t size() const
size - Get the array size.
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
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.
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
A SetVector that performs no allocations if smaller than a certain size.
A container for analyses that lazily runs them and caches their results.
bool isLoopExiting(const BlockT *BB) const
True if terminator in the block can branch to another block that is outside of the current loop.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop) const override
Returns true if the instruction in a loop is guaranteed to execute at least once (under the assumptio...
ValueT lookup(const KeyT &Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
AnalysisUsage & addRequired()
bool VerifyMemorySSA
Enables verification of MemorySSA.
Instruction * SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore, bool Unreachable, MDNode *BranchWeights, DominatorTree *DT, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
Conditional or Unconditional Branch instruction.
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
void reserve(size_type N)
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
LLVM Value Representation.
void deleteEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge deletion and update the tree.
bool isConditional() const
LogicalOp_match< LHS, RHS, Instruction::And > m_LogicalAnd(const LHS &L, const RHS &R)
Matches L && R either in the form of L & R or L ? R : false.
BasicBlock * getSuccessor(unsigned i) const
static constexpr UpdateKind Delete
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
A Use represents the edge between a Value definition and its users.
reference emplace_back(ArgTypes &&... Args)
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< int > UnswitchSiblingsToplevelDiv("unswitch-siblings-toplevel-div", cl::init(2), cl::Hidden, cl::desc("Toplevel siblings divisor for cost multiplier."))
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."))
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
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 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)
Build the cloned blocks for an unswitched copy of the given loop.