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 DVI->getExpression(),
392 DVI->getDebugLoc()->getInlinedAt());
393 auto R = VariableSet.
insert(Key);
399 if (
auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI)) {
418 for (
auto &Instr : ToBeRemoved)
419 Instr->eraseFromParent();
421 return !ToBeRemoved.
empty();
447 for (
auto &
I : *BB) {
450 DVI->getDebugLoc()->getInlinedAt());
451 auto VMI = VariableMap.
find(Key);
452 auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI);
460 if (VMI == VariableMap.
end() || VMI->second.first != Values ||
461 VMI->second.second != DVI->getExpression()) {
466 VariableMap[Key] = {Values, DVI->getExpression()};
468 VariableMap[Key] = {Values,
nullptr};
479 for (
auto &Instr : ToBeRemoved)
480 Instr->eraseFromParent();
482 return !ToBeRemoved.
empty();
511 DVI->getDebugLoc()->getInlinedAt());
516 for (
auto &
I : *BB) {
520 auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI);
523 if (!SeenDefForAggregate.
contains(Aggregate)) {
526 SeenDefForAggregate.
insert(Aggregate);
534 DAI->eraseFromParent();
536 return !ToBeRemoved.
empty();
540 bool MadeChanges =
false;
567 I.replaceAllUsesWith(V);
570 if (
I.hasName() && !V->hasName())
574 BI = BI->eraseFromParent();
579 assert(
I->getParent() ==
nullptr &&
580 "ReplaceInstWithInst: Instruction already inserted into basic block!");
584 if (!
I->getDebugLoc())
585 I->setDebugLoc(BI->getDebugLoc());
602 VisitedBlocks.
insert(BB).second) {
618 const Twine &BBName) {
641 assert(SP == BB &&
"CFG broken");
650 "Should have a single succ!");
655 if (
auto *II = dyn_cast<InvokeInst>(TI))
656 II->setUnwindDest(Succ);
657 else if (
auto *CS = dyn_cast<CatchSwitchInst>(TI))
658 CS->setUnwindDest(Succ);
659 else if (
auto *CR = dyn_cast<CleanupReturnInst>(TI))
660 CR->setUnwindDest(Succ);
679 if (PN.getIncomingBlock(BBIdx) != OldPred)
680 BBIdx = PN.getBasicBlockIndex(OldPred);
682 assert(BBIdx != -1 &&
"Invalid PHI Index!");
683 PN.setIncomingBlock(BBIdx, NewPred);
689 PHINode *LandingPadReplacement,
691 const Twine &BBName) {
694 if (!LandingPadReplacement && !PadInst->
isEHPad())
702 if (
Options.PreserveLoopSimplify && LI) {
703 if (
Loop *BBLoop = LI->getLoopFor(BB)) {
717 if (LI->getLoopFor(
P) != BBLoop) {
740 if (LandingPadReplacement) {
741 auto *NewLP = OriginalPad->
clone();
743 NewLP->insertBefore(Terminator);
746 Value *ParentPad =
nullptr;
747 if (
auto *FuncletPad = dyn_cast<FuncletPadInst>(PadInst))
748 ParentPad = FuncletPad->getParentPad();
749 else if (
auto *CatchSwitch = dyn_cast<CatchSwitchInst>(PadInst))
750 ParentPad = CatchSwitch->getParentPad();
751 else if (
auto *CleanupPad = dyn_cast<CleanupPadInst>(PadInst))
752 ParentPad = CleanupPad->getParentPad();
753 else if (
auto *LandingPad = dyn_cast<LandingPadInst>(PadInst))
754 ParentPad = LandingPad->getParent();
771 Updates.
push_back({DominatorTree::Insert, BB, NewBB});
772 Updates.
push_back({DominatorTree::Insert, NewBB, Succ});
773 Updates.
push_back({DominatorTree::Delete, BB, Succ});
779 MSSAU->applyUpdates(Updates, *DT);
781 MSSAU->getMemorySSA()->verifyMemorySSA();
786 if (
Loop *BBLoop = LI->getLoopFor(BB)) {
789 if (
Loop *SuccLoop = LI->getLoopFor(Succ)) {
790 if (BBLoop == SuccLoop) {
792 SuccLoop->addBasicBlockToLoop(NewBB, *LI);
793 }
else if (BBLoop->contains(SuccLoop)) {
795 BBLoop->addBasicBlockToLoop(NewBB, *LI);
796 }
else if (SuccLoop->contains(BBLoop)) {
798 SuccLoop->addBasicBlockToLoop(NewBB, *LI);
804 assert(SuccLoop->getHeader() == Succ &&
805 "Should not create irreducible loops!");
806 if (
Loop *
P = SuccLoop->getParentLoop())
807 P->addBasicBlockToLoop(NewBB, *LI);
813 if (!BBLoop->contains(Succ)) {
814 assert(!BBLoop->contains(NewBB) &&
815 "Split point for loop exit is contained in loop!");
822 if (!LoopPreds.
empty()) {
824 Succ, LoopPreds,
"split", DT, LI, MSSAU,
Options.PreserveLCSSA);
840 "SplitBB has non-PHI nodes!");
844 int Idx = PN.getBasicBlockIndex(SplitBB);
845 assert(
Idx >= 0 &&
"Invalid Block Index");
846 Value *V = PN.getIncomingValue(
Idx);
850 if (
const PHINode *VP = dyn_cast<PHINode>(V))
851 if (VP->getParent() == SplitBB)
856 PN.getType(), Preds.
size(),
"split",
862 PN.setIncomingValue(
Idx, NewPN);
869 unsigned NumBroken = 0;
883 const Twine &BBName,
bool Before) {
885 DomTreeUpdater LocalDTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
887 DTU ? DTU : (DT ? &LocalDTU :
nullptr), LI, MSSAU,
891 while (isa<PHINode>(SplitIt) || SplitIt->isEHPad()) {
895 std::string
Name = BBName.
str();
903 L->addBasicBlockToLoop(New, *LI);
909 Updates.
push_back({DominatorTree::Insert, Old, New});
912 if (UniqueSuccessorsOfOld.
insert(SuccessorOfOld).second) {
913 Updates.
push_back({DominatorTree::Insert, New, SuccessorOfOld});
914 Updates.
push_back({DominatorTree::Delete, Old, SuccessorOfOld});
921 std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
940 return SplitBlockImpl(Old, SplitPt,
nullptr, DT, LI, MSSAU, BBName,
947 return SplitBlockImpl(Old, SplitPt, DTU,
nullptr, LI, MSSAU, BBName,
954 const Twine &BBName) {
957 while (isa<PHINode>(SplitIt) || SplitIt->isEHPad())
959 std::string
Name = BBName.
str();
968 L->addBasicBlockToLoop(New, *LI);
975 DTUpdates.
push_back({DominatorTree::Insert, New, Old});
978 if (UniquePredecessorsOfOld.
insert(PredecessorOfOld).second) {
979 DTUpdates.
push_back({DominatorTree::Insert, PredecessorOfOld, New});
980 DTUpdates.
push_back({DominatorTree::Delete, PredecessorOfOld, Old});
1001 bool PreserveLCSSA,
bool &HasLoopExit) {
1015 Updates.
push_back({DominatorTree::Insert, NewBB, OldBB});
1017 for (
auto *Pred : Preds)
1018 if (UniquePreds.
insert(Pred).second) {
1019 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
1020 Updates.
push_back({DominatorTree::Delete, Pred, OldBB});
1044 assert(DT &&
"DT should be available to update LoopInfo!");
1049 bool IsLoopEntry = !!L;
1050 bool SplitMakesNewLoopHeader =
false;
1062 if (!PL->contains(OldBB))
1069 if (L->contains(Pred))
1070 IsLoopEntry =
false;
1072 SplitMakesNewLoopHeader =
true;
1084 Loop *InnermostPredLoop =
nullptr;
1089 while (PredLoop && !PredLoop->contains(OldBB))
1093 if (PredLoop && PredLoop->contains(OldBB) &&
1094 (!InnermostPredLoop ||
1095 InnermostPredLoop->
getLoopDepth() < PredLoop->getLoopDepth()))
1096 InnermostPredLoop = PredLoop;
1100 if (InnermostPredLoop)
1103 L->addBasicBlockToLoop(NewBB, *LI);
1104 if (SplitMakesNewLoopHeader)
1105 L->moveToHeader(NewBB);
1121 Value *InVal =
nullptr;
1167 if (PredSet.
count(IncomingBB)) {
1196 std::string NewName = std::string(Suffix) +
".split-lp";
1199 DTU, DT, LI, MSSAU, PreserveLCSSA);
1223 OldLatch = L->getLoopLatch();
1232 assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
1233 "Cannot split an edge from an IndirectBrInst");
1234 Pred->getTerminator()->replaceSuccessorWith(BB, NewBB);
1241 if (Preds.
empty()) {
1248 bool HasLoopExit =
false;
1252 if (!Preds.
empty()) {
1259 if (NewLatch != OldLatch) {
1277 bool PreserveLCSSA) {
1279 MSSAU, PreserveLCSSA);
1286 bool PreserveLCSSA) {
1288 nullptr, LI, MSSAU, PreserveLCSSA);
1314 assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
1315 "Cannot split an edge from an IndirectBrInst");
1316 Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1);
1319 bool HasLoopExit =
false;
1321 PreserveLCSSA, HasLoopExit);
1331 if (Pred == NewBB1)
continue;
1333 "Cannot split an edge from an IndirectBrInst");
1339 if (!NewBB2Preds.
empty()) {
1352 NewBB2Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2);
1355 HasLoopExit =
false;
1357 PreserveLCSSA, HasLoopExit);
1377 "Split cannot be applied if LPad is token type. Otherwise an "
1378 "invalid PHINode of token type would be created.");
1395 const char *Suffix1,
const char *Suffix2,
1399 bool PreserveLCSSA) {
1401 OrigBB, Preds, Suffix1, Suffix2, NewBBs,
1402 nullptr, DT, LI, MSSAU, PreserveLCSSA);
1406 const char *Suffix1,
const char *Suffix2,
1410 bool PreserveLCSSA) {
1412 NewBBs, DTU,
nullptr, LI, MSSAU,
1429 if (
BitCastInst *BCI = dyn_cast<BitCastInst>(V)) {
1432 V = BCI->getOperand(0);
1433 NewBC = BCI->
clone();
1440 V = EVI->getOperand(0);
1441 NewEV = EVI->
clone();
1451 if (
PHINode *PN = dyn_cast<PHINode>(V)) {
1452 if (PN->getParent() == BB) {
1454 NewEV->
setOperand(0, PN->getIncomingValueForBlock(Pred));
1456 NewBC->
setOperand(0, PN->getIncomingValueForBlock(Pred));
1458 Op = PN->getIncomingValueForBlock(Pred);
1469 DTU->
applyUpdates({{DominatorTree::Delete, Pred, BB}});
1471 return cast<ReturnInst>(NewRet);
1488 if (UniqueSuccessorsOfHead.
insert(SuccessorOfHead).second) {
1489 Updates.
push_back({DominatorTree::Insert,
Tail, SuccessorOfHead});
1490 Updates.
push_back({DominatorTree::Delete, Head, SuccessorOfHead});
1496 bool CreateThenBlock = (ThenBlock ==
nullptr);
1497 if (CreateThenBlock) {
1504 Updates.
push_back({DominatorTree::Insert, ThenBlock,
Tail});
1512 Updates.
push_back({DominatorTree::Insert, Head, ThenBlock});
1513 HeadNewTerm->
setMetadata(LLVMContext::MD_prof, BranchWeights);
1521 L->addBasicBlockToLoop(ThenBlock, *LI);
1522 L->addBasicBlockToLoop(
Tail, *LI);
1546 (*ThenTerm)->setDebugLoc(SplitBefore->
getDebugLoc());
1548 (*ElseTerm)->setDebugLoc(SplitBefore->
getDebugLoc());
1551 HeadNewTerm->
setMetadata(LLVMContext::MD_prof, BranchWeights);
1555 Updates.
reserve(4 + 2 * UniqueOrigSuccessors.
size());
1557 Updates.
push_back({DominatorTree::Insert, Head, Succ});
1560 for (
BasicBlock *UniqueOrigSuccessor : UniqueOrigSuccessors)
1561 Updates.
push_back({DominatorTree::Insert,
Tail, UniqueOrigSuccessor});
1562 for (
BasicBlock *UniqueOrigSuccessor : UniqueOrigSuccessors)
1563 Updates.
push_back({DominatorTree::Delete, Head, UniqueOrigSuccessor});
1568std::pair<Instruction*, Value*>
1574 auto *Ty =
End->getType();
1576 const unsigned Bitwidth =
DL.getTypeSizeInBits(Ty);
1579 auto *
IV =
Builder.CreatePHI(Ty, 2,
"iv");
1582 true, Bitwidth != 2);
1583 auto *IVCheck =
Builder.CreateICmpEQ(IVNext,
End,
1584 IV->getName() +
".check");
1585 Builder.CreateCondBr(IVCheck, LoopExit, LoopBody);
1590 IV->addIncoming(IVNext, LoopBody);
1601 if (EC.isScalable()) {
1604 auto [BodyIP,
Index] =
1612 unsigned Num = EC.getFixedValue();
1613 for (
unsigned Idx = 0;
Idx < Num; ++
Idx) {
1626 if (!isa<ConstantInt>(EVL)) {
1633 unsigned Num = cast<ConstantInt>(EVL)->getZExtValue();
1634 for (
unsigned Idx = 0;
Idx < Num; ++
Idx) {
1667 if (!Pred1Br || !Pred2Br)
1719 if (!BI)
return nullptr;
1745 while (
I != Out->
end() && isa<PHINode>(
I)) {
1746 auto Phi = cast<PHINode>(
I);
1749 Phi->getName() +
".moved", &FirstGuardBlock->
front());
1750 for (
auto *In : Incoming) {
1754 }
else if (Phi->getBasicBlockIndex(In) != -1) {
1755 V = Phi->removeIncomingValue(In,
false);
1757 NewPhi->addIncoming(V, In);
1759 assert(NewPhi->getNumIncomingValues() == Incoming.size());
1760 if (Phi->getNumOperands() == 0) {
1761 Phi->replaceAllUsesWith(NewPhi);
1762 I = Phi->eraseFromParent();
1765 Phi->addIncoming(NewPhi, GuardBlock);
1783static std::tuple<Value *, BasicBlock *, BasicBlock *>
1787 "Only support branch terminator.");
1789 auto Condition = Branch->isConditional() ? Branch->getCondition() :
nullptr;
1793 Succ0 = Outgoing.
count(Succ0) ? Succ0 :
nullptr;
1795 if (Branch->isUnconditional()) {
1796 Branch->setSuccessor(0, FirstGuardBlock);
1799 Succ1 = Branch->getSuccessor(1);
1800 Succ1 = Outgoing.
count(Succ1) ? Succ1 :
nullptr;
1802 if (Succ0 && !Succ1) {
1803 Branch->setSuccessor(0, FirstGuardBlock);
1804 }
else if (Succ1 && !Succ0) {
1805 Branch->setSuccessor(1, FirstGuardBlock);
1807 Branch->eraseFromParent();
1813 return std::make_tuple(Condition, Succ0, Succ1);
1830 for (
int i = 0, e = GuardBlocks.
size() - 1; i != e; ++i) {
1831 auto Out = Outgoing[i];
1847 auto FirstGuardBlock = GuardBlocks.
front();
1850 "merged.bb.idx", FirstGuardBlock);
1852 for (
auto In : Incoming) {
1856 std::tie(Condition, Succ0, Succ1) =
1858 Value *IncomingId =
nullptr;
1859 if (Succ0 && Succ1) {
1861 auto Succ0Iter =
find(Outgoing, Succ0);
1862 auto Succ1Iter =
find(Outgoing, Succ1);
1864 std::distance(Outgoing.
begin(), Succ0Iter));
1866 std::distance(Outgoing.
begin(), Succ1Iter));
1868 In->getTerminator());
1871 auto SuccIter = Succ0 ?
find(Outgoing, Succ0) :
find(Outgoing, Succ1);
1873 std::distance(Outgoing.
begin(), SuccIter));
1875 Phi->addIncoming(IncomingId, In);
1878 for (
int i = 0, e = Outgoing.
size() - 1; i != e; ++i) {
1879 auto Out = Outgoing[i];
1880 auto Cmp = ICmpInst::Create(Instruction::ICmp, ICmpInst::ICMP_EQ, Phi,
1882 Out->
getName() +
".predicate", GuardBlocks[i]);
1883 GuardPredicates[Out] = Cmp;
1895 auto FirstGuardBlock = GuardBlocks.
front();
1899 for (
int i = 0, e = Outgoing.
size() - 1; i != e; ++i) {
1900 auto Out = Outgoing[i];
1901 LLVM_DEBUG(
dbgs() <<
"Creating guard for " << Out->getName() <<
"\n");
1905 StringRef(
"Guard.") + Out->getName(), FirstGuardBlock);
1906 GuardPredicates[Out] = Phi;
1909 for (
auto *In : Incoming) {
1913 std::tie(Condition, Succ0, Succ1) =
1923 bool OneSuccessorDone =
false;
1924 for (
int i = 0, e = Outgoing.
size() - 1; i != e; ++i) {
1925 auto Out = Outgoing[i];
1926 PHINode *Phi = cast<PHINode>(GuardPredicates[Out]);
1927 if (Out != Succ0 && Out != Succ1) {
1929 }
else if (!Succ0 || !Succ1 || OneSuccessorDone) {
1939 DeletionCandidates.
push_back(Condition);
1942 OneSuccessorDone =
true;
1962 std::optional<unsigned> MaxControlFlowBooleans) {
1964 auto F = Incoming.
front()->getParent();
1966 for (
int i = 0, e = Outgoing.
size() - 1; i != e; ++i)
1975 if (!MaxControlFlowBooleans || Outgoing.
size() <= *MaxControlFlowBooleans)
1977 DeletionCandidates);
1987 const StringRef Prefix, std::optional<unsigned> MaxControlFlowBooleans) {
1988 if (Outgoing.
size() < 2)
1989 return Outgoing.
front();
1993 for (
auto *In : Incoming) {
1995 if (Outgoing.
count(Succ))
1996 Updates.
push_back({DominatorTree::Delete,
In, Succ});
2002 Prefix, MaxControlFlowBooleans);
2003 auto FirstGuardBlock = GuardBlocks.
front();
2006 for (
int i = 0, e = GuardBlocks.
size(); i != e; ++i)
2007 reconnectPhis(Outgoing[i], GuardBlocks[i], Incoming, FirstGuardBlock);
2012 int NumGuards = GuardBlocks.
size();
2013 assert((
int)Outgoing.
size() == NumGuards + 1);
2015 for (
auto In : Incoming)
2016 Updates.
push_back({DominatorTree::Insert,
In, FirstGuardBlock});
2018 for (
int i = 0; i != NumGuards - 1; ++i) {
2019 Updates.
push_back({DominatorTree::Insert, GuardBlocks[i], Outgoing[i]});
2021 {DominatorTree::Insert, GuardBlocks[i], GuardBlocks[i + 1]});
2023 Updates.
push_back({DominatorTree::Insert, GuardBlocks[NumGuards - 1],
2024 Outgoing[NumGuards - 1]});
2025 Updates.
push_back({DominatorTree::Insert, GuardBlocks[NumGuards - 1],
2026 Outgoing[NumGuards]});
2030 for (
auto I : DeletionCandidates) {
2032 if (
auto Inst = dyn_cast_or_null<Instruction>(
I))
2033 Inst->eraseFromParent();
2036 return FirstGuardBlock;
2043 if (NewCond->
hasOneUse() && isa<CmpInst>(NewCond)) {
2044 CmpInst *CI = cast<CmpInst>(NewCond);
2047 NewCond =
Builder.CreateNot(NewCond, NewCond->
getName() +
".not");
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
SmallVector< MachineOperand, 4 > Cond
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)
Remove redundant instructions within sequences of consecutive dbg.value instructions.
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 BasicBlock * SplitBlockImpl(BasicBlock *Old, Instruction *SplitPt, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, const Twine &BBName, bool Before)
static std::tuple< Value *, BasicBlock *, BasicBlock * > redirectToHub(BasicBlock *BB, BasicBlock *FirstGuardBlock, const BBSetVector &Outgoing)
static bool remomveUndefDbgAssignsFromEntryBlock(BasicBlock *BB)
Remove redundant undef dbg.assign intrinsic from an entry block using a forward scan.
static void setupBranchForGuard(SmallVectorImpl< BasicBlock * > &GuardBlocks, const BBSetVector &Outgoing, BBPredicates &GuardPredicates)
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 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 removeRedundantDbgInstrsUsingForwardScan(BasicBlock *BB)
Remove redundant dbg.value instructions using a forward scan.
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...
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 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.
bool isConditional() const
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
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=std::nullopt, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
static CleanupReturnInst * Create(Value *CleanupPad, BasicBlock *UnwindBB=nullptr, Instruction *InsertBefore=nullptr)
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 Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
static ConstantInt * getFalse(LLVMContext &Context)
This represents the llvm.dbg.assign instruction.
This represents the llvm.dbg.value instruction.
bool isKillLocation() 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.
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:
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
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
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.
bool isExceptionalTerminator() const
SymbolTableList< Instruction >::iterator insertInto(BasicBlock *ParentBB, SymbolTableList< Instruction >::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
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.
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
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...
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="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
A vector that has set insertion semantics.
size_type size() const
Determine the number of elements in the SetVector.
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
const value_type & front() const
Return the first element of the SetVector.
const value_type & back() const
Return the last element of 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...
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.
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...
Instruction * SplitBlockAndInsertIfThen(Value *Cond, Instruction *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 ...
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 SplitLandingPadPredecessors(BasicBlock *OrigBB, ArrayRef< BasicBlock * > Preds, const char *Suffix, const char *Suffix2, SmallVectorImpl< BasicBlock * > &NewBBs, DominatorTree *DT, 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 * splitBlockBefore(BasicBlock *Old, Instruction *SplitPt, DomTreeUpdater *DTU, LoopInfo *LI, MemorySSAUpdater *MSSAU, const Twine &BBName="")
Split the specified block at the specified instruction SplitPt.
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...
void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, Instruction **ThenTerm, Instruction **ElseTerm, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr)
SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, but also creates the ElseBlock...
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 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...
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,...
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.
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
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.
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...
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)
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Option class for critical edge splitting.
CriticalEdgeSplittingOptions & setPreserveLCSSA()