54#define DEBUG_TYPE "basicblock-utils"
58 cl::desc(
"Set the maximum path length when checking whether a basic block "
59 "is followed by a block that either has a terminating "
60 "deoptimizing call or is terminated with an unreachable"));
65 bool KeepOneInputPHIs) {
66 for (
auto *BB : BBs) {
71 Succ->removePredecessor(BB, KeepOneInputPHIs);
72 if (Updates && UniqueSuccessors.
insert(Succ).second)
73 Updates->
push_back({DominatorTree::Delete, BB, Succ});
77 while (!BB->empty()) {
86 BB->back().eraseFromParent();
90 isa<UnreachableInst>(BB->getTerminator()) &&
91 "The successor list of BB isn't empty before "
92 "applying corresponding DTU updates.");
97 bool KeepOneInputPHIs) {
102 bool KeepOneInputPHIs) {
106 assert(Dead.size() == BBs.
size() &&
"Duplicating blocks?");
107 for (
auto *BB : Dead)
109 assert(Dead.count(Pred) &&
"All predecessors must be dead!");
122 BB->eraseFromParent();
126 bool KeepOneInputPHIs) {
134 std::vector<BasicBlock*> DeadBlocks;
136 if (!Reachable.
count(&BB))
137 DeadBlocks.push_back(&BB);
142 return !DeadBlocks.empty();
147 if (!isa<PHINode>(BB->
begin()))
151 if (PN->getIncomingValue(0) != PN)
152 PN->replaceAllUsesWith(PN->getIncomingValue(0));
159 PN->eraseFromParent();
172 bool Changed =
false;
173 for (
unsigned i = 0, e = PHIs.
size(); i != e; ++i)
174 if (
PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i].
operator Value*()))
183 bool PredecessorWithTwoSuccessors,
190 if (!PredBB)
return false;
193 if (PredBB == BB)
return false;
208 unsigned FallThruPath;
209 if (PredecessorWithTwoSuccessors) {
210 if (!(PredBB_BI = dyn_cast<BranchInst>(PTI)))
216 FallThruPath = PredBB_BI->
getSuccessor(0) == BB ? 0 : 1;
229 if (isa<PHINode>(BB->
front())) {
231 if (!isa<PHINode>(PN.getIncomingValue(0)) ||
232 cast<PHINode>(PN.getIncomingValue(0))->getParent() != BB)
233 IncomingValues.
push_back(PN.getIncomingValue(0));
238 assert(!DTU &&
"cannot use both DT and DTU for updates");
242 assert(BBNode &&
"PredNode unreachable but BBNode reachable?");
244 C->setIDom(PredNode);
249 std::vector<DominatorTree::UpdateType> Updates;
251 assert(!DT &&
"cannot use both DT and DTU for updates");
256 Updates.reserve(Updates.size() + 2 *
succ_size(BB) + 1);
265 if (!SuccsOfPredBB.
contains(SuccOfBB))
266 if (SeenSuccs.
insert(SuccOfBB).second)
267 Updates.push_back({DominatorTree::Insert, PredBB, SuccOfBB});
270 if (SeenSuccs.
insert(SuccOfBB).second)
271 Updates.push_back({DominatorTree::Delete, BB, SuccOfBB});
272 Updates.push_back({DominatorTree::Delete, PredBB, BB});
292 if (PredecessorWithTwoSuccessors) {
329 "successors should have been transferred to PredBB");
342 assert(!MergeBlocks.
empty() &&
"MergeBlocks should not be empty");
344 bool BlocksHaveBeenMerged =
false;
345 while (!MergeBlocks.
empty()) {
348 if (Dest && (!L || L->contains(Dest))) {
353 "Expecting BB to be unique predecessor of the Dest block");
354 MergeBlocks.
erase(Dest);
355 BlocksHaveBeenMerged =
true;
357 MergeBlocks.
erase(BB);
359 MergeBlocks.
erase(BB);
361 return BlocksHaveBeenMerged;
391 if (isa<DbgLabelRecord>(DR)) {
401 if (DVR.
getType() == DbgVariableRecord::LocationType::Declare) {
413 auto R = VariableSet.
insert(Key);
436 for (
auto &DVR : ToBeRemoved)
437 DVR->eraseFromParent();
439 return !ToBeRemoved.
empty();
451 DVI->getExpression(),
452 DVI->getDebugLoc()->getInlinedAt());
453 auto R = VariableSet.
insert(Key);
459 if (
auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI)) {
478 for (
auto &Instr : ToBeRemoved)
479 Instr->eraseFromParent();
481 return !ToBeRemoved.
empty();
508 for (
auto &
I : *BB) {
510 if (DVR.getType() == DbgVariableRecord::LocationType::Declare)
513 DVR.getDebugLoc()->getInlinedAt());
514 auto VMI = VariableMap.
find(Key);
517 bool IsDbgValueKind =
523 if (VMI == VariableMap.
end() || VMI->second.first != Values ||
524 VMI->second.second != DVR.getExpression()) {
526 VariableMap[Key] = {Values, DVR.getExpression()};
528 VariableMap[Key] = {Values,
nullptr};
539 for (
auto *DVR : ToBeRemoved)
540 DVR->eraseFromParent();
542 return !ToBeRemoved.
empty();
553 DVR.getDebugLoc().getInlinedAt());
558 for (
auto &
I : *BB) {
560 if (!DVR.isDbgValue() && !DVR.isDbgAssign())
562 bool IsDbgValueKind =
565 if (!SeenDefForAggregate.
contains(Aggregate)) {
566 bool IsKill = DVR.isKillLocation() && IsDbgValueKind;
568 SeenDefForAggregate.
insert(Aggregate);
569 }
else if (DVR.isDbgAssign()) {
577 DVR->eraseFromParent();
579 return !ToBeRemoved.
empty();
589 for (
auto &
I : *BB) {
592 DVI->getDebugLoc()->getInlinedAt());
593 auto VMI = VariableMap.
find(Key);
594 auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI);
602 if (VMI == VariableMap.
end() || VMI->second.first != Values ||
603 VMI->second.second != DVI->getExpression()) {
608 VariableMap[Key] = {Values, DVI->getExpression()};
610 VariableMap[Key] = {Values,
nullptr};
621 for (
auto &Instr : ToBeRemoved)
622 Instr->eraseFromParent();
624 return !ToBeRemoved.
empty();
656 DVI->getDebugLoc()->getInlinedAt());
661 for (
auto &
I : *BB) {
665 auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI);
668 if (!SeenDefForAggregate.
contains(Aggregate)) {
671 SeenDefForAggregate.
insert(Aggregate);
679 DAI->eraseFromParent();
681 return !ToBeRemoved.
empty();
685 bool MadeChanges =
false;
712 I.replaceAllUsesWith(V);
715 if (
I.hasName() && !V->hasName())
719 BI = BI->eraseFromParent();
724 assert(
I->getParent() ==
nullptr &&
725 "ReplaceInstWithInst: Instruction already inserted into basic block!");
729 if (!
I->getDebugLoc())
730 I->setDebugLoc(BI->getDebugLoc());
747 VisitedBlocks.
insert(BB).second) {
763 const Twine &BBName) {
786 assert(SP == BB &&
"CFG broken");
795 "Should have a single succ!");
800 if (
auto *II = dyn_cast<InvokeInst>(TI))
801 II->setUnwindDest(Succ);
802 else if (
auto *CS = dyn_cast<CatchSwitchInst>(TI))
803 CS->setUnwindDest(Succ);
804 else if (
auto *CR = dyn_cast<CleanupReturnInst>(TI))
805 CR->setUnwindDest(Succ);
824 if (PN.getIncomingBlock(BBIdx) != OldPred)
825 BBIdx = PN.getBasicBlockIndex(OldPred);
827 assert(BBIdx != -1 &&
"Invalid PHI Index!");
828 PN.setIncomingBlock(BBIdx, NewPred);
834 PHINode *LandingPadReplacement,
836 const Twine &BBName) {
839 if (!LandingPadReplacement && !PadInst->
isEHPad())
847 if (
Options.PreserveLoopSimplify && LI) {
848 if (
Loop *BBLoop = LI->getLoopFor(BB)) {
862 if (LI->getLoopFor(
P) != BBLoop) {
885 if (LandingPadReplacement) {
886 auto *NewLP = OriginalPad->
clone();
888 NewLP->insertBefore(Terminator);
891 Value *ParentPad =
nullptr;
892 if (
auto *FuncletPad = dyn_cast<FuncletPadInst>(PadInst))
893 ParentPad = FuncletPad->getParentPad();
894 else if (
auto *CatchSwitch = dyn_cast<CatchSwitchInst>(PadInst))
895 ParentPad = CatchSwitch->getParentPad();
896 else if (
auto *CleanupPad = dyn_cast<CleanupPadInst>(PadInst))
897 ParentPad = CleanupPad->getParentPad();
898 else if (
auto *LandingPad = dyn_cast<LandingPadInst>(PadInst))
899 ParentPad = LandingPad->getParent();
916 Updates.
push_back({DominatorTree::Insert, BB, NewBB});
917 Updates.
push_back({DominatorTree::Insert, NewBB, Succ});
918 Updates.
push_back({DominatorTree::Delete, BB, Succ});
924 MSSAU->applyUpdates(Updates, *DT);
926 MSSAU->getMemorySSA()->verifyMemorySSA();
931 if (
Loop *BBLoop = LI->getLoopFor(BB)) {
934 if (
Loop *SuccLoop = LI->getLoopFor(Succ)) {
935 if (BBLoop == SuccLoop) {
937 SuccLoop->addBasicBlockToLoop(NewBB, *LI);
938 }
else if (BBLoop->contains(SuccLoop)) {
940 BBLoop->addBasicBlockToLoop(NewBB, *LI);
941 }
else if (SuccLoop->contains(BBLoop)) {
943 SuccLoop->addBasicBlockToLoop(NewBB, *LI);
949 assert(SuccLoop->getHeader() == Succ &&
950 "Should not create irreducible loops!");
951 if (
Loop *
P = SuccLoop->getParentLoop())
952 P->addBasicBlockToLoop(NewBB, *LI);
958 if (!BBLoop->contains(Succ)) {
959 assert(!BBLoop->contains(NewBB) &&
960 "Split point for loop exit is contained in loop!");
967 if (!LoopPreds.
empty()) {
969 Succ, LoopPreds,
"split", DT, LI, MSSAU,
Options.PreserveLCSSA);
985 "SplitBB has non-PHI nodes!");
989 int Idx = PN.getBasicBlockIndex(SplitBB);
990 assert(
Idx >= 0 &&
"Invalid Block Index");
991 Value *V = PN.getIncomingValue(
Idx);
995 if (
const PHINode *VP = dyn_cast<PHINode>(V))
996 if (VP->getParent() == SplitBB)
1009 PN.setIncomingValue(
Idx, NewPN);
1016 unsigned NumBroken = 0;
1032 DomTreeUpdater LocalDTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
1034 DTU ? DTU : (DT ? &LocalDTU :
nullptr), LI, MSSAU,
1038 while (isa<PHINode>(SplitIt) || SplitIt->isEHPad()) {
1040 assert(SplitIt != SplitPt->getParent()->end());
1042 std::string
Name = BBName.
str();
1050 L->addBasicBlockToLoop(New, *LI);
1056 Updates.
push_back({DominatorTree::Insert, Old, New});
1059 if (UniqueSuccessorsOfOld.
insert(SuccessorOfOld).second) {
1060 Updates.
push_back({DominatorTree::Insert, New, SuccessorOfOld});
1061 Updates.
push_back({DominatorTree::Delete, Old, SuccessorOfOld});
1068 std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
1087 return SplitBlockImpl(Old, SplitPt,
nullptr, DT, LI, MSSAU, BBName,
1094 return SplitBlockImpl(Old, SplitPt, DTU,
nullptr, LI, MSSAU, BBName,
1101 const Twine &BBName) {
1104 while (isa<PHINode>(SplitIt) || SplitIt->isEHPad())
1106 std::string
Name = BBName.
str();
1115 L->addBasicBlockToLoop(New, *LI);
1122 DTUpdates.
push_back({DominatorTree::Insert, New, Old});
1125 if (UniquePredecessorsOfOld.
insert(PredecessorOfOld).second) {
1126 DTUpdates.
push_back({DominatorTree::Insert, PredecessorOfOld, New});
1127 DTUpdates.
push_back({DominatorTree::Delete, PredecessorOfOld, Old});
1148 bool PreserveLCSSA,
bool &HasLoopExit) {
1162 Updates.
push_back({DominatorTree::Insert, NewBB, OldBB});
1164 for (
auto *Pred : Preds)
1165 if (UniquePreds.
insert(Pred).second) {
1166 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
1167 Updates.
push_back({DominatorTree::Delete, Pred, OldBB});
1191 assert(DT &&
"DT should be available to update LoopInfo!");
1196 bool IsLoopEntry = !!L;
1197 bool SplitMakesNewLoopHeader =
false;
1209 if (!PL->contains(OldBB))
1216 if (L->contains(Pred))
1217 IsLoopEntry =
false;
1219 SplitMakesNewLoopHeader =
true;
1231 Loop *InnermostPredLoop =
nullptr;
1236 while (PredLoop && !PredLoop->contains(OldBB))
1240 if (PredLoop && PredLoop->contains(OldBB) &&
1241 (!InnermostPredLoop ||
1242 InnermostPredLoop->
getLoopDepth() < PredLoop->getLoopDepth()))
1243 InnermostPredLoop = PredLoop;
1247 if (InnermostPredLoop)
1250 L->addBasicBlockToLoop(NewBB, *LI);
1251 if (SplitMakesNewLoopHeader)
1252 L->moveToHeader(NewBB);
1268 Value *InVal =
nullptr;
1311 if (PredSet.
count(IncomingBB)) {
1340 std::string NewName = std::string(Suffix) +
".split-lp";
1343 DTU, DT, LI, MSSAU, PreserveLCSSA);
1367 OldLatch = L->getLoopLatch();
1376 assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
1377 "Cannot split an edge from an IndirectBrInst");
1378 Pred->getTerminator()->replaceSuccessorWith(BB, NewBB);
1385 if (Preds.
empty()) {
1392 bool HasLoopExit =
false;
1396 if (!Preds.
empty()) {
1403 if (NewLatch != OldLatch) {
1421 bool PreserveLCSSA) {
1423 MSSAU, PreserveLCSSA);
1430 bool PreserveLCSSA) {
1432 nullptr, LI, MSSAU, PreserveLCSSA);
1458 assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
1459 "Cannot split an edge from an IndirectBrInst");
1460 Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1);
1463 bool HasLoopExit =
false;
1465 PreserveLCSSA, HasLoopExit);
1475 if (Pred == NewBB1)
continue;
1477 "Cannot split an edge from an IndirectBrInst");
1483 if (!NewBB2Preds.
empty()) {
1496 NewBB2Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2);
1499 HasLoopExit =
false;
1501 PreserveLCSSA, HasLoopExit);
1521 "Split cannot be applied if LPad is token type. Otherwise an "
1522 "invalid PHINode of token type would be created.");
1539 const char *Suffix1,
const char *Suffix2,
1543 bool PreserveLCSSA) {
1545 NewBBs, DTU,
nullptr, LI, MSSAU,
1562 if (
BitCastInst *BCI = dyn_cast<BitCastInst>(V)) {
1565 V = BCI->getOperand(0);
1566 NewBC = BCI->
clone();
1573 V = EVI->getOperand(0);
1574 NewEV = EVI->
clone();
1584 if (
PHINode *PN = dyn_cast<PHINode>(V)) {
1585 if (PN->getParent() == BB) {
1587 NewEV->
setOperand(0, PN->getIncomingValueForBlock(Pred));
1589 NewBC->
setOperand(0, PN->getIncomingValueForBlock(Pred));
1591 Op = PN->getIncomingValueForBlock(Pred);
1602 DTU->
applyUpdates({{DominatorTree::Delete, Pred, BB}});
1604 return cast<ReturnInst>(NewRet);
1614 Cond, SplitBefore, &ThenBlock,
nullptr,
1616 false, BranchWeights, DTU, LI);
1627 Cond, SplitBefore,
nullptr, &ElseBlock,
1629 Unreachable, BranchWeights, DTU, LI);
1641 Cond, SplitBefore, &ThenBlock, &ElseBlock,
false,
1642 false, BranchWeights, DTU, LI);
1650 BasicBlock **ElseBlock,
bool UnreachableThen,
bool UnreachableElse,
1652 assert((ThenBlock || ElseBlock) &&
1653 "At least one branch block must be created");
1654 assert((!UnreachableThen || !UnreachableElse) &&
1655 "Split block tail must be reachable");
1662 Updates.
reserve(4 + 2 * UniqueOrigSuccessors.
size());
1669 bool ThenToTailEdge =
false;
1670 bool ElseToTailEdge =
false;
1689 BB->getTerminator()->
setDebugLoc(SplitBefore->getDebugLoc());
1695 handleBlock(ThenBlock, UnreachableThen, TrueBlock, ThenToTailEdge);
1696 handleBlock(ElseBlock, UnreachableElse, FalseBlock, ElseToTailEdge);
1701 HeadNewTerm->
setMetadata(LLVMContext::MD_prof, BranchWeights);
1705 Updates.
emplace_back(DominatorTree::Insert, Head, TrueBlock);
1706 Updates.
emplace_back(DominatorTree::Insert, Head, FalseBlock);
1711 for (
BasicBlock *UniqueOrigSuccessor : UniqueOrigSuccessors)
1713 for (
BasicBlock *UniqueOrigSuccessor : UniqueOrigSuccessors)
1714 Updates.
emplace_back(DominatorTree::Delete, Head, UniqueOrigSuccessor);
1721 L->addBasicBlockToLoop(TrueBlock, *LI);
1723 L->addBasicBlockToLoop(FalseBlock, *LI);
1724 L->addBasicBlockToLoop(
Tail, *LI);
1729std::pair<Instruction*, Value*>
1735 auto *Ty =
End->getType();
1737 const unsigned Bitwidth =
DL.getTypeSizeInBits(Ty);
1742 Builder.
CreateAdd(
IV, ConstantInt::get(Ty, 1),
IV->getName() +
".next",
1743 true, Bitwidth != 2);
1745 IV->getName() +
".check");
1750 IV->addIncoming(ConstantInt::get(Ty, 0), LoopPred);
1751 IV->addIncoming(IVNext, LoopBody);
1762 if (EC.isScalable()) {
1765 auto [BodyIP,
Index] =
1773 unsigned Num = EC.getFixedValue();
1774 for (
unsigned Idx = 0;
Idx < Num; ++
Idx) {
1776 Func(IRB, ConstantInt::get(IndexTy,
Idx));
1787 if (!isa<ConstantInt>(EVL)) {
1794 unsigned Num = cast<ConstantInt>(EVL)->getZExtValue();
1795 for (
unsigned Idx = 0;
Idx < Num; ++
Idx) {
1797 Func(IRB, ConstantInt::get(Ty,
Idx));
1828 if (!Pred1Br || !Pred2Br)
1880 if (!BI)
return nullptr;
1906 while (
I != Out->
end() && isa<PHINode>(
I)) {
1907 auto Phi = cast<PHINode>(
I);
1910 Phi->getName() +
".moved", FirstGuardBlock->
begin());
1915 }
else if (Phi->getBasicBlockIndex(In) != -1) {
1916 V = Phi->removeIncomingValue(In,
false);
1918 NewPhi->addIncoming(V, In);
1921 if (Phi->getNumOperands() == 0) {
1922 Phi->replaceAllUsesWith(NewPhi);
1923 I = Phi->eraseFromParent();
1926 Phi->addIncoming(NewPhi, GuardBlock);
1944static std::tuple<Value *, BasicBlock *, BasicBlock *>
1948 "Only support branch terminator.");
1950 auto Condition = Branch->isConditional() ? Branch->getCondition() :
nullptr;
1954 Succ0 = Outgoing.
count(Succ0) ? Succ0 :
nullptr;
1956 if (Branch->isUnconditional()) {
1957 Branch->setSuccessor(0, FirstGuardBlock);
1960 Succ1 = Branch->getSuccessor(1);
1961 Succ1 = Outgoing.
count(Succ1) ? Succ1 :
nullptr;
1963 if (Succ0 && !Succ1) {
1964 Branch->setSuccessor(0, FirstGuardBlock);
1965 }
else if (Succ1 && !Succ0) {
1966 Branch->setSuccessor(1, FirstGuardBlock);
1968 Branch->eraseFromParent();
1974 return std::make_tuple(Condition, Succ0, Succ1);
1991 for (
int i = 0, e = GuardBlocks.
size() - 1; i != e; ++i) {
1992 auto Out = Outgoing[i];
2008 auto FirstGuardBlock = GuardBlocks.
front();
2011 "merged.bb.idx", FirstGuardBlock);
2017 std::tie(Condition, Succ0, Succ1) =
2019 Value *IncomingId =
nullptr;
2020 if (Succ0 && Succ1) {
2022 auto Succ0Iter =
find(Outgoing, Succ0);
2023 auto Succ1Iter =
find(Outgoing, Succ1);
2025 std::distance(Outgoing.
begin(), Succ0Iter));
2027 std::distance(Outgoing.
begin(), Succ1Iter));
2029 In->getTerminator()->getIterator());
2032 auto SuccIter = Succ0 ?
find(Outgoing, Succ0) :
find(Outgoing, Succ1);
2034 std::distance(Outgoing.
begin(), SuccIter));
2036 Phi->addIncoming(IncomingId, In);
2039 for (
int i = 0, e = Outgoing.
size() - 1; i != e; ++i) {
2040 auto Out = Outgoing[i];
2041 auto Cmp = ICmpInst::Create(Instruction::ICmp, ICmpInst::ICMP_EQ, Phi,
2043 Out->getName() +
".predicate", GuardBlocks[i]);
2044 GuardPredicates[Out] = Cmp;
2056 auto FirstGuardBlock = GuardBlocks.
front();
2060 for (
int i = 0, e = Outgoing.
size() - 1; i != e; ++i) {
2061 auto Out = Outgoing[i];
2062 LLVM_DEBUG(
dbgs() <<
"Creating guard for " << Out->getName() <<
"\n");
2066 StringRef(
"Guard.") + Out->getName(), FirstGuardBlock);
2067 GuardPredicates[Out] = Phi;
2074 std::tie(Condition, Succ0, Succ1) =
2084 bool OneSuccessorDone =
false;
2085 for (
int i = 0, e = Outgoing.
size() - 1; i != e; ++i) {
2086 auto Out = Outgoing[i];
2087 PHINode *Phi = cast<PHINode>(GuardPredicates[Out]);
2088 if (Out != Succ0 && Out != Succ1) {
2089 Phi->addIncoming(BoolFalse, In);
2090 }
else if (!Succ0 || !Succ1 || OneSuccessorDone) {
2093 Phi->addIncoming(BoolTrue, In);
2097 Phi->addIncoming(Condition, In);
2100 DeletionCandidates.
push_back(Condition);
2101 Phi->addIncoming(Inverted, In);
2103 OneSuccessorDone =
true;
2123 std::optional<unsigned> MaxControlFlowBooleans) {
2127 for (
int i = 0, e = Outgoing.
size() - 1; i != e; ++i)
2136 if (!MaxControlFlowBooleans || Outgoing.
size() <= *MaxControlFlowBooleans)
2138 DeletionCandidates);
2148 const StringRef Prefix, std::optional<unsigned> MaxControlFlowBooleans) {
2149 if (Outgoing.
size() < 2)
2150 return Outgoing.
front();
2156 if (Outgoing.
count(Succ))
2157 Updates.
push_back({DominatorTree::Delete,
In, Succ});
2163 Prefix, MaxControlFlowBooleans);
2164 auto FirstGuardBlock = GuardBlocks.
front();
2167 for (
int i = 0, e = GuardBlocks.
size(); i != e; ++i)
2173 int NumGuards = GuardBlocks.
size();
2174 assert((
int)Outgoing.
size() == NumGuards + 1);
2177 Updates.
push_back({DominatorTree::Insert,
In, FirstGuardBlock});
2179 for (
int i = 0; i != NumGuards - 1; ++i) {
2180 Updates.
push_back({DominatorTree::Insert, GuardBlocks[i], Outgoing[i]});
2182 {DominatorTree::Insert, GuardBlocks[i], GuardBlocks[i + 1]});
2184 Updates.
push_back({DominatorTree::Insert, GuardBlocks[NumGuards - 1],
2185 Outgoing[NumGuards - 1]});
2186 Updates.
push_back({DominatorTree::Insert, GuardBlocks[NumGuards - 1],
2187 Outgoing[NumGuards]});
2191 for (
auto I : DeletionCandidates) {
2193 if (
auto Inst = dyn_cast_or_null<Instruction>(
I))
2194 Inst->eraseFromParent();
2197 return FirstGuardBlock;
2204 if (NewCond->
hasOneUse() && isa<CmpInst>(NewCond)) {
2205 CmpInst *CI = cast<CmpInst>(NewCond);
2215 for (
auto &BB :
F) {
2216 auto *Term = BB.getTerminator();
2217 if (!(isa<ReturnInst>(Term) || isa<UnreachableInst>(Term) ||
2218 isa<BranchInst>(Term)))
2227 if (!Src.getParent()->isPresplitCoroutine())
2229 if (
auto *SW = dyn_cast<SwitchInst>(Src.getTerminator()))
2230 if (
auto *
Intr = dyn_cast<IntrinsicInst>(SW->getCondition()))
2231 return Intr->getIntrinsicID() == Intrinsic::coro_suspend &&
2232 SW->getDefaultDest() == &Dest;
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static BasicBlock * SplitBlockPredecessorsImpl(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
static void convertToGuardPredicates(SmallVectorImpl< BasicBlock * > &GuardBlocks, SmallVectorImpl< WeakVH > &DeletionCandidates, const BBSetVector &Incoming, const BBSetVector &Outgoing, const StringRef Prefix, std::optional< unsigned > MaxControlFlowBooleans)
static bool removeRedundantDbgInstrsUsingBackwardScan(BasicBlock *BB)
static BasicBlock * SplitBlockImpl(BasicBlock *Old, BasicBlock::iterator SplitPt, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, const Twine &BBName, bool Before)
static void calcPredicateUsingBooleans(const BBSetVector &Incoming, const BBSetVector &Outgoing, SmallVectorImpl< BasicBlock * > &GuardBlocks, BBPredicates &GuardPredicates, SmallVectorImpl< WeakVH > &DeletionCandidates)
We record the predicate of each outgoing block using a phi of boolean.
static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB, ArrayRef< BasicBlock * > Preds, BranchInst *BI, bool HasLoopExit)
Update the PHI nodes in OrigBB to include the values coming from NewBB.
static bool removeUndefDbgAssignsFromEntryBlock(BasicBlock *BB)
Remove redundant undef dbg.assign intrinsic from an entry block using a forward scan.
static std::tuple< Value *, BasicBlock *, BasicBlock * > redirectToHub(BasicBlock *BB, BasicBlock *FirstGuardBlock, const BBSetVector &Outgoing)
static void setupBranchForGuard(SmallVectorImpl< BasicBlock * > &GuardBlocks, const BBSetVector &Outgoing, BBPredicates &GuardPredicates)
static bool DbgVariableRecordsRemoveRedundantDbgInstrsUsingForwardScan(BasicBlock *BB)
Remove redundant dbg.value instructions using a forward scan.
static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB, ArrayRef< BasicBlock * > Preds, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA, bool &HasLoopExit)
Update DominatorTree, LoopInfo, and LCCSA analysis information.
static void reconnectPhis(BasicBlock *Out, BasicBlock *GuardBlock, const SetVector< BasicBlock * > &Incoming, BasicBlock *FirstGuardBlock)
static bool DbgVariableRecordsRemoveUndefDbgAssignsFromEntryBlock(BasicBlock *BB)
static void calcPredicateUsingInteger(const BBSetVector &Incoming, const BBSetVector &Outgoing, SmallVectorImpl< BasicBlock * > &GuardBlocks, BBPredicates &GuardPredicates)
We are using one integer to represent the block we are branching to.
static bool DbgVariableRecordsRemoveRedundantDbgInstrsUsingBackwardScan(BasicBlock *BB)
Remove redundant instructions within sequences of consecutive dbg.value instructions.
static bool removeRedundantDbgInstrsUsingForwardScan(BasicBlock *BB)
static void SplitLandingPadPredecessorsImpl(BasicBlock *OrigBB, ArrayRef< BasicBlock * > Preds, const char *Suffix1, const char *Suffix2, SmallVectorImpl< BasicBlock * > &NewBBs, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
static cl::opt< unsigned > MaxDeoptOrUnreachableSuccessorCheckDepth("max-deopt-or-unreachable-succ-check-depth", cl::init(8), cl::Hidden, cl::desc("Set the maximum path length when checking whether a basic block " "is followed by a block that either has a terminating " "deoptimizing call or is terminated with an unreachable"))
BlockVerifier::State From
This file contains the declarations for the subclasses of Constant, which represent the different fla...
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 provides various utilities for inspecting and working with the control flow graph in LLVM I...
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
static const uint32_t IV[8]
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.
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.
const LandingPadInst * getLandingPadInst() const
Return the landingpad instruction associated with the landing pad.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
const Instruction & front() const
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
bool isEntryBlock() const
Return true if this is the entry block of the containing function.
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)
Split the basic block into two basic blocks at the specified instruction.
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
const Function * getParent() const
Return the enclosing method, or null if none.
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
InstListType::iterator iterator
Instruction iterators...
LLVMContext & getContext() const
Get the context in which this basic block lives.
bool IsNewDbgInfoFormat
Flag recording whether or not this block stores debug-info in the form of intrinsic instructions (fal...
bool isLandingPad() const
Return true if this basic block is a landing pad.
bool isEHPad() const
Return true if this basic block is an exception handling block.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
bool canSplitPredecessors() const
void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
const Instruction & back() const
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
This class represents a no-op cast from one type to another.
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
bool isUnconditional() const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Value * getCondition() const
static CleanupPadInst * Create(Value *ParentPad, ArrayRef< Value * > Args, const Twine &NameStr, BasicBlock::iterator InsertBefore)
static CleanupReturnInst * Create(Value *CleanupPad, BasicBlock *UnwindBB, BasicBlock::iterator InsertBefore)
This class is the base class for the comparison instructions.
void setPredicate(Predicate P)
Set the predicate for this instruction to the specified value.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
static ConstantInt * getTrue(LLVMContext &Context)
static ConstantInt * getFalse(LLVMContext &Context)
This class represents an Operation in the Expression.
This represents the llvm.dbg.assign instruction.
Base class for non-instruction debug metadata records that have positions within IR.
DebugLoc getDebugLoc() const
This represents the llvm.dbg.value instruction.
bool isKillLocation() const
Record of a variable value-assignment, aka a non instruction representation of the dbg....
LocationType getType() const
DIExpression * getExpression() const
DILocalVariable * getVariable() const
Identifies a unique instance of a variable.
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.
Implements a dense probed hash-table based set.
iterator_range< iterator > children()
void flush()
Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.
void recalculate(Function &F)
Notify DTU that the entry block was replaced.
bool hasDomTree() const
Returns true if it holds a DominatorTree.
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
DominatorTree & getDomTree()
Flush DomTree updates and return DomTree.
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
void splitBlock(NodeT *NewBB)
splitBlock - BB is split and now it has one successor.
DomTreeNodeBase< NodeT > * setNewRoot(NodeT *BB)
Add a new node to the forward dominator tree and make it a new root.
void eraseNode(NodeT *BB)
eraseNode - Removes a node from the dominator 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.
Module * getParent()
Get the module that this global value is contained inside of...
Common base class shared among various IRBuilders.
PHINode * CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name="")
Value * CreateNot(Value *V, const Twine &Name="")
Value * CreateICmpEQ(Value *LHS, Value *RHS, 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 * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreateElementCount(Type *DstType, ElementCount EC)
Create an expression which evaluates to the number of elements in EC at runtime.
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:
void moveBeforePreserving(Instruction *MovePos)
Perform a moveBefore operation, while signalling that the caller intends to preserve the original ord...
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
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 mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
bool isSpecialTerminator() const
InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
This is an important class for using LLVM in a threaded context.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
unsigned getLoopDepth() const
Return the nesting level of this loop.
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
void removeBlock(BlockT *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
bool isLoopHeader(const BlockT *BB) const
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Represents a single loop in the control flow graph.
Provides a lazy, caching interface for making common memory aliasing information queries,...
void invalidateCachedPredecessors()
Clears the PredIteratorCache info.
void removeInstruction(Instruction *InstToRemove)
Removes an instruction from the dependence analysis, updating the dependence of instructions that pre...
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was spliced into From and To.
void applyUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT, bool UpdateDTFirst=false)
Apply CFG updates, analogous with the DT edge updates.
void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was merged into To.
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
void wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New, ArrayRef< BasicBlock * > Preds, bool IdenticalEdgesWereMerged=true)
A new empty BasicBlock (New) now branches directly to Old.
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.
Class that has the common methods + fields of memory uses/defs.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
void removeIncomingValueIf(function_ref< bool(unsigned)> Predicate, bool DeletePHIIfEmpty=true)
Remove all incoming values for which the predicate returns true.
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...
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Return a value (possibly void), from a function.
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr, BasicBlock::iterator InsertBefore, Instruction *MDFrom=nullptr)
A vector that has set insertion semantics.
size_type size() const
Determine the number of elements in the SetVector.
const value_type & front() const
Return the first element of the SetVector.
const value_type & back() const
Return the last element of 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.
Implements a dense probed hash-table based set with some number of buckets stored inline.
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.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
Provides information about what library functions are available for the current target.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
std::string str() const
Return the twine contents as a std::string.
The instances of the Type class are immutable: once they are created, they are never changed.
static IntegerType * getInt1Ty(LLVMContext &C)
static IntegerType * getInt32Ty(LLVMContext &C)
bool isTokenTy() const
Return true if this is 'token'.
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
void setOperand(unsigned i, Value *Val)
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.
bool hasOneUse() const
Return true if there is exactly one use of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
std::pair< iterator, bool > insert(const ValueT &V)
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
self_iterator getIterator()
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ Tail
Attemps to make calls as fast as possible while guaranteeing that tail call optimization can always b...
@ C
The default llvm calling convention, compatible with C.
AssignmentInstRange getAssignmentInsts(DIAssignID *ID)
Return a range of instructions (typically just one) that have ID as an attachment.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
void ReplaceInstWithInst(BasicBlock *BB, BasicBlock::iterator &BI, Instruction *I)
Replace the instruction specified by BI with the instruction specified by I.
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
Interval::succ_iterator succ_end(Interval *I)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
bool RemoveRedundantDbgInstrs(BasicBlock *BB)
Try to remove redundant dbg.value instructions from given basic block.
bool succ_empty(const Instruction *I)
bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB)
Check if we can prove that all paths starting from this block converge to a block that either has a @...
BranchInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
unsigned GetSuccessorNumber(const BasicBlock *BB, const BasicBlock *Succ)
Search for the specified successor of basic block BB and return its position in the terminator instru...
void detachDeadBlocks(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< DominatorTree::UpdateType > *Updates, bool KeepOneInputPHIs=false)
Replace contents of every block in BBs with single unreachable instruction.
bool hasOnlySimpleTerminator(const Function &F)
auto successors(const MachineBasicBlock *BB)
ReturnInst * FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, BasicBlock *Pred, DomTreeUpdater *DTU=nullptr)
This method duplicates the specified return instruction into a predecessor which ends in an unconditi...
BasicBlock * splitBlockBefore(BasicBlock *Old, BasicBlock::iterator SplitPt, DomTreeUpdater *DTU, LoopInfo *LI, MemorySSAUpdater *MSSAU, const Twine &BBName="")
Split the specified block at the specified instruction SplitPt.
Instruction * SplitBlockAndInsertIfElse(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ElseBlock=nullptr)
Similar to SplitBlockAndInsertIfThen, but the inserted block is on the false path of the branch.
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
void ReplaceInstWithValue(BasicBlock::iterator &BI, Value *V)
Replace all uses of an instruction (specified by BI) with a value, then remove and delete the origina...
BasicBlock * SplitKnownCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")
If it is known that an edge is critical, SplitKnownCriticalEdge can be called directly,...
Interval::pred_iterator pred_end(Interval *I)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Examine each PHI in the given block and delete it if it is dead.
auto reverse(ContainerTy &&C)
void InvertBranch(BranchInst *PBI, IRBuilderBase &Builder)
bool EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete all basic blocks from F that are not reachable from its entry node.
bool MergeBlockSuccessorsIntoGivenBlocks(SmallPtrSetImpl< BasicBlock * > &MergeBlocks, Loop *L=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr)
Merge block(s) sucessors, if possible.
void SplitBlockAndInsertIfThenElse(Value *Cond, BasicBlock::iterator SplitBefore, Instruction **ThenTerm, Instruction **ElseTerm, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr)
SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, but also creates the ElseBlock...
void SplitBlockAndInsertForEachLane(ElementCount EC, Type *IndexTy, Instruction *InsertBefore, std::function< void(IRBuilderBase &, Value *)> Func)
Utility function for performing a given action on each lane of a vector with EC elements.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
BasicBlock * ehAwareSplitEdge(BasicBlock *BB, BasicBlock *Succ, LandingPadInst *OriginalPad=nullptr, PHINode *LandingPadReplacement=nullptr, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")
Split the edge connect the specficed blocks in the case that Succ is an Exception Handling Block.
SmallVector< ValueTypeFromRangeType< R >, Size > to_vector(R &&Range)
Given a range of type R, iterate the entire range and return a SmallVector with elements of the vecto...
void SplitLandingPadPredecessors(BasicBlock *OrigBB, ArrayRef< BasicBlock * > Preds, const char *Suffix, const char *Suffix2, SmallVectorImpl< BasicBlock * > &NewBBs, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method transforms the landing pad, OrigBB, by introducing two new basic blocks into the function...
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
bool VerifyMemorySSA
Enables verification of MemorySSA.
void createPHIsForSplitLoopExit(ArrayRef< BasicBlock * > Preds, BasicBlock *SplitBB, BasicBlock *DestBB)
When a loop exit edge is split, LCSSA form may require new PHIs in the new exit block.
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
bool isAssignmentTrackingEnabled(const Module &M)
Return true if assignment tracking is enabled for module M.
BasicBlock * CreateControlFlowHub(DomTreeUpdater *DTU, SmallVectorImpl< BasicBlock * > &GuardBlocks, const SetVector< BasicBlock * > &Predecessors, const SetVector< BasicBlock * > &Successors, const StringRef Prefix, std::optional< unsigned > MaxControlFlowBooleans=std::nullopt)
Given a set of incoming and outgoing blocks, create a "hub" such that every edge from an incoming blo...
std::pair< Instruction *, Value * > SplitBlockAndInsertSimpleForLoop(Value *End, Instruction *SplitBefore)
Insert a for (int i = 0; i < End; i++) loop structure (with the exception that End is assumed > 0,...
DWARFExpression::Operation Op
BasicBlock * SplitCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")
If this edge is a critical edge, insert a new node to split the critical edge.
bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
unsigned SplitAllCriticalEdges(Function &F, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
Loop over all of the edges in the CFG, breaking critical edges as they are found.
void updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred, BasicBlock *NewPred, PHINode *Until=nullptr)
Replaces all uses of OldPred with the NewPred block in all PHINodes in a block.
bool isPresplitCoroSuspendExitEdge(const BasicBlock &Src, const BasicBlock &Dest)
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.
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
bool RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
If the specified value is an effectively dead PHI node, due to being a def-use chain of single-use no...
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 ...
unsigned succ_size(const MachineBasicBlock *BB)
Value * invertCondition(Value *Condition)
Invert the given true/false value, possibly reusing an existing copy.
void DeleteDeadBlocks(ArrayRef< BasicBlock * > BBs, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified blocks from BB.
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...
void setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ)
Sets the unwind edge of an instruction to a particular successor.
unsigned pred_size(const MachineBasicBlock *BB)
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Option class for critical edge splitting.
CriticalEdgeSplittingOptions & setPreserveLCSSA()
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...