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;
390 if (isa<DPLabel>(DR)) {
397 DPValue &DPV = cast<DPValue>(DR);
400 if (DPV.
getType() == DPValue::LocationType::Declare) {
412 auto R = VariableSet.
insert(Key);
435 for (
auto &DPV : ToBeRemoved)
436 DPV->eraseFromParent();
438 return !ToBeRemoved.
empty();
450 DVI->getExpression(),
451 DVI->getDebugLoc()->getInlinedAt());
452 auto R = VariableSet.
insert(Key);
458 if (
auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI)) {
477 for (
auto &Instr : ToBeRemoved)
478 Instr->eraseFromParent();
480 return !ToBeRemoved.
empty();
506 for (
auto &
I : *BB) {
508 if (DPV.getType() == DPValue::LocationType::Declare)
511 DPV.getDebugLoc()->getInlinedAt());
512 auto VMI = VariableMap.
find(Key);
515 bool IsDbgValueKind =
521 if (VMI == VariableMap.
end() || VMI->second.first != Values ||
522 VMI->second.second != DPV.getExpression()) {
524 VariableMap[Key] = {Values, DPV.getExpression()};
526 VariableMap[Key] = {Values,
nullptr};
537 for (
auto *DPV : ToBeRemoved)
538 DPV->eraseFromParent();
540 return !ToBeRemoved.
empty();
548 auto GetAggregateVariable = [](
const DPValue &DPV) {
550 DPV.getDebugLoc().getInlinedAt());
555 for (
auto &
I : *BB) {
557 if (!DPV.isDbgValue() && !DPV.isDbgAssign())
559 bool IsDbgValueKind =
562 if (!SeenDefForAggregate.
contains(Aggregate)) {
563 bool IsKill = DPV.isKillLocation() && IsDbgValueKind;
565 SeenDefForAggregate.
insert(Aggregate);
566 }
else if (DPV.isDbgAssign()) {
573 for (
DPValue *DPV : ToBeRemoved)
574 DPV->eraseFromParent();
576 return !ToBeRemoved.
empty();
586 for (
auto &
I : *BB) {
589 DVI->getDebugLoc()->getInlinedAt());
590 auto VMI = VariableMap.
find(Key);
591 auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI);
599 if (VMI == VariableMap.
end() || VMI->second.first != Values ||
600 VMI->second.second != DVI->getExpression()) {
605 VariableMap[Key] = {Values, DVI->getExpression()};
607 VariableMap[Key] = {Values,
nullptr};
618 for (
auto &Instr : ToBeRemoved)
619 Instr->eraseFromParent();
621 return !ToBeRemoved.
empty();
653 DVI->getDebugLoc()->getInlinedAt());
658 for (
auto &
I : *BB) {
662 auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI);
665 if (!SeenDefForAggregate.
contains(Aggregate)) {
668 SeenDefForAggregate.
insert(Aggregate);
676 DAI->eraseFromParent();
678 return !ToBeRemoved.
empty();
682 bool MadeChanges =
false;
709 I.replaceAllUsesWith(V);
712 if (
I.hasName() && !V->hasName())
716 BI = BI->eraseFromParent();
721 assert(
I->getParent() ==
nullptr &&
722 "ReplaceInstWithInst: Instruction already inserted into basic block!");
726 if (!
I->getDebugLoc())
727 I->setDebugLoc(BI->getDebugLoc());
744 VisitedBlocks.
insert(BB).second) {
760 const Twine &BBName) {
783 assert(SP == BB &&
"CFG broken");
792 "Should have a single succ!");
797 if (
auto *II = dyn_cast<InvokeInst>(TI))
798 II->setUnwindDest(Succ);
799 else if (
auto *CS = dyn_cast<CatchSwitchInst>(TI))
800 CS->setUnwindDest(Succ);
801 else if (
auto *CR = dyn_cast<CleanupReturnInst>(TI))
802 CR->setUnwindDest(Succ);
821 if (PN.getIncomingBlock(BBIdx) != OldPred)
822 BBIdx = PN.getBasicBlockIndex(OldPred);
824 assert(BBIdx != -1 &&
"Invalid PHI Index!");
825 PN.setIncomingBlock(BBIdx, NewPred);
831 PHINode *LandingPadReplacement,
833 const Twine &BBName) {
836 if (!LandingPadReplacement && !PadInst->
isEHPad())
844 if (
Options.PreserveLoopSimplify && LI) {
845 if (
Loop *BBLoop = LI->getLoopFor(BB)) {
859 if (LI->getLoopFor(
P) != BBLoop) {
882 if (LandingPadReplacement) {
883 auto *NewLP = OriginalPad->
clone();
885 NewLP->insertBefore(Terminator);
888 Value *ParentPad =
nullptr;
889 if (
auto *FuncletPad = dyn_cast<FuncletPadInst>(PadInst))
890 ParentPad = FuncletPad->getParentPad();
891 else if (
auto *CatchSwitch = dyn_cast<CatchSwitchInst>(PadInst))
892 ParentPad = CatchSwitch->getParentPad();
893 else if (
auto *CleanupPad = dyn_cast<CleanupPadInst>(PadInst))
894 ParentPad = CleanupPad->getParentPad();
895 else if (
auto *LandingPad = dyn_cast<LandingPadInst>(PadInst))
896 ParentPad = LandingPad->getParent();
913 Updates.
push_back({DominatorTree::Insert, BB, NewBB});
914 Updates.
push_back({DominatorTree::Insert, NewBB, Succ});
915 Updates.
push_back({DominatorTree::Delete, BB, Succ});
921 MSSAU->applyUpdates(Updates, *DT);
923 MSSAU->getMemorySSA()->verifyMemorySSA();
928 if (
Loop *BBLoop = LI->getLoopFor(BB)) {
931 if (
Loop *SuccLoop = LI->getLoopFor(Succ)) {
932 if (BBLoop == SuccLoop) {
934 SuccLoop->addBasicBlockToLoop(NewBB, *LI);
935 }
else if (BBLoop->contains(SuccLoop)) {
937 BBLoop->addBasicBlockToLoop(NewBB, *LI);
938 }
else if (SuccLoop->contains(BBLoop)) {
940 SuccLoop->addBasicBlockToLoop(NewBB, *LI);
946 assert(SuccLoop->getHeader() == Succ &&
947 "Should not create irreducible loops!");
948 if (
Loop *
P = SuccLoop->getParentLoop())
949 P->addBasicBlockToLoop(NewBB, *LI);
955 if (!BBLoop->contains(Succ)) {
956 assert(!BBLoop->contains(NewBB) &&
957 "Split point for loop exit is contained in loop!");
964 if (!LoopPreds.
empty()) {
966 Succ, LoopPreds,
"split", DT, LI, MSSAU,
Options.PreserveLCSSA);
982 "SplitBB has non-PHI nodes!");
986 int Idx = PN.getBasicBlockIndex(SplitBB);
987 assert(
Idx >= 0 &&
"Invalid Block Index");
988 Value *V = PN.getIncomingValue(
Idx);
992 if (
const PHINode *VP = dyn_cast<PHINode>(V))
993 if (VP->getParent() == SplitBB)
1006 PN.setIncomingValue(
Idx, NewPN);
1013 unsigned NumBroken = 0;
1029 DomTreeUpdater LocalDTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
1031 DTU ? DTU : (DT ? &LocalDTU :
nullptr), LI, MSSAU,
1035 while (isa<PHINode>(SplitIt) || SplitIt->isEHPad()) {
1037 assert(SplitIt != SplitPt->getParent()->end());
1039 std::string
Name = BBName.
str();
1047 L->addBasicBlockToLoop(New, *LI);
1053 Updates.
push_back({DominatorTree::Insert, Old, New});
1056 if (UniqueSuccessorsOfOld.
insert(SuccessorOfOld).second) {
1057 Updates.
push_back({DominatorTree::Insert, New, SuccessorOfOld});
1058 Updates.
push_back({DominatorTree::Delete, Old, SuccessorOfOld});
1065 std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
1084 return SplitBlockImpl(Old, SplitPt,
nullptr, DT, LI, MSSAU, BBName,
1091 return SplitBlockImpl(Old, SplitPt, DTU,
nullptr, LI, MSSAU, BBName,
1098 const Twine &BBName) {
1101 while (isa<PHINode>(SplitIt) || SplitIt->isEHPad())
1103 std::string
Name = BBName.
str();
1112 L->addBasicBlockToLoop(New, *LI);
1119 DTUpdates.
push_back({DominatorTree::Insert, New, Old});
1122 if (UniquePredecessorsOfOld.
insert(PredecessorOfOld).second) {
1123 DTUpdates.
push_back({DominatorTree::Insert, PredecessorOfOld, New});
1124 DTUpdates.
push_back({DominatorTree::Delete, PredecessorOfOld, Old});
1145 bool PreserveLCSSA,
bool &HasLoopExit) {
1159 Updates.
push_back({DominatorTree::Insert, NewBB, OldBB});
1161 for (
auto *Pred : Preds)
1162 if (UniquePreds.
insert(Pred).second) {
1163 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
1164 Updates.
push_back({DominatorTree::Delete, Pred, OldBB});
1188 assert(DT &&
"DT should be available to update LoopInfo!");
1193 bool IsLoopEntry = !!L;
1194 bool SplitMakesNewLoopHeader =
false;
1206 if (!PL->contains(OldBB))
1213 if (L->contains(Pred))
1214 IsLoopEntry =
false;
1216 SplitMakesNewLoopHeader =
true;
1228 Loop *InnermostPredLoop =
nullptr;
1233 while (PredLoop && !PredLoop->contains(OldBB))
1237 if (PredLoop && PredLoop->contains(OldBB) &&
1238 (!InnermostPredLoop ||
1239 InnermostPredLoop->
getLoopDepth() < PredLoop->getLoopDepth()))
1240 InnermostPredLoop = PredLoop;
1244 if (InnermostPredLoop)
1247 L->addBasicBlockToLoop(NewBB, *LI);
1248 if (SplitMakesNewLoopHeader)
1249 L->moveToHeader(NewBB);
1265 Value *InVal =
nullptr;
1308 if (PredSet.
count(IncomingBB)) {
1337 std::string NewName = std::string(Suffix) +
".split-lp";
1340 DTU, DT, LI, MSSAU, PreserveLCSSA);
1364 OldLatch = L->getLoopLatch();
1373 assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
1374 "Cannot split an edge from an IndirectBrInst");
1375 Pred->getTerminator()->replaceSuccessorWith(BB, NewBB);
1382 if (Preds.
empty()) {
1389 bool HasLoopExit =
false;
1393 if (!Preds.
empty()) {
1400 if (NewLatch != OldLatch) {
1418 bool PreserveLCSSA) {
1420 MSSAU, PreserveLCSSA);
1427 bool PreserveLCSSA) {
1429 nullptr, LI, MSSAU, PreserveLCSSA);
1455 assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
1456 "Cannot split an edge from an IndirectBrInst");
1457 Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1);
1460 bool HasLoopExit =
false;
1462 PreserveLCSSA, HasLoopExit);
1472 if (Pred == NewBB1)
continue;
1474 "Cannot split an edge from an IndirectBrInst");
1480 if (!NewBB2Preds.
empty()) {
1493 NewBB2Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2);
1496 HasLoopExit =
false;
1498 PreserveLCSSA, HasLoopExit);
1518 "Split cannot be applied if LPad is token type. Otherwise an "
1519 "invalid PHINode of token type would be created.");
1536 const char *Suffix1,
const char *Suffix2,
1540 bool PreserveLCSSA) {
1542 NewBBs, DTU,
nullptr, LI, MSSAU,
1559 if (
BitCastInst *BCI = dyn_cast<BitCastInst>(V)) {
1562 V = BCI->getOperand(0);
1563 NewBC = BCI->
clone();
1570 V = EVI->getOperand(0);
1571 NewEV = EVI->
clone();
1581 if (
PHINode *PN = dyn_cast<PHINode>(V)) {
1582 if (PN->getParent() == BB) {
1584 NewEV->
setOperand(0, PN->getIncomingValueForBlock(Pred));
1586 NewBC->
setOperand(0, PN->getIncomingValueForBlock(Pred));
1588 Op = PN->getIncomingValueForBlock(Pred);
1599 DTU->
applyUpdates({{DominatorTree::Delete, Pred, BB}});
1601 return cast<ReturnInst>(NewRet);
1611 Cond, SplitBefore, &ThenBlock,
nullptr,
1613 false, BranchWeights, DTU, LI);
1624 Cond, SplitBefore,
nullptr, &ElseBlock,
1626 Unreachable, BranchWeights, DTU, LI);
1638 Cond, SplitBefore, &ThenBlock, &ElseBlock,
false,
1639 false, BranchWeights, DTU, LI);
1647 BasicBlock **ElseBlock,
bool UnreachableThen,
bool UnreachableElse,
1649 assert((ThenBlock || ElseBlock) &&
1650 "At least one branch block must be created");
1651 assert((!UnreachableThen || !UnreachableElse) &&
1652 "Split block tail must be reachable");
1659 Updates.
reserve(4 + 2 * UniqueOrigSuccessors.
size());
1666 bool ThenToTailEdge =
false;
1667 bool ElseToTailEdge =
false;
1686 BB->getTerminator()->
setDebugLoc(SplitBefore->getDebugLoc());
1692 handleBlock(ThenBlock, UnreachableThen, TrueBlock, ThenToTailEdge);
1693 handleBlock(ElseBlock, UnreachableElse, FalseBlock, ElseToTailEdge);
1698 HeadNewTerm->
setMetadata(LLVMContext::MD_prof, BranchWeights);
1702 Updates.
emplace_back(DominatorTree::Insert, Head, TrueBlock);
1703 Updates.
emplace_back(DominatorTree::Insert, Head, FalseBlock);
1708 for (
BasicBlock *UniqueOrigSuccessor : UniqueOrigSuccessors)
1710 for (
BasicBlock *UniqueOrigSuccessor : UniqueOrigSuccessors)
1711 Updates.
emplace_back(DominatorTree::Delete, Head, UniqueOrigSuccessor);
1718 L->addBasicBlockToLoop(TrueBlock, *LI);
1720 L->addBasicBlockToLoop(FalseBlock, *LI);
1721 L->addBasicBlockToLoop(
Tail, *LI);
1726std::pair<Instruction*, Value*>
1732 auto *Ty =
End->getType();
1734 const unsigned Bitwidth =
DL.getTypeSizeInBits(Ty);
1739 Builder.
CreateAdd(
IV, ConstantInt::get(Ty, 1),
IV->getName() +
".next",
1740 true, Bitwidth != 2);
1742 IV->getName() +
".check");
1747 IV->addIncoming(ConstantInt::get(Ty, 0), LoopPred);
1748 IV->addIncoming(IVNext, LoopBody);
1759 if (EC.isScalable()) {
1762 auto [BodyIP,
Index] =
1770 unsigned Num = EC.getFixedValue();
1771 for (
unsigned Idx = 0;
Idx < Num; ++
Idx) {
1773 Func(IRB, ConstantInt::get(IndexTy,
Idx));
1784 if (!isa<ConstantInt>(EVL)) {
1791 unsigned Num = cast<ConstantInt>(EVL)->getZExtValue();
1792 for (
unsigned Idx = 0;
Idx < Num; ++
Idx) {
1794 Func(IRB, ConstantInt::get(Ty,
Idx));
1825 if (!Pred1Br || !Pred2Br)
1877 if (!BI)
return nullptr;
1903 while (
I != Out->
end() && isa<PHINode>(
I)) {
1904 auto Phi = cast<PHINode>(
I);
1907 Phi->getName() +
".moved", FirstGuardBlock->
begin());
1912 }
else if (Phi->getBasicBlockIndex(In) != -1) {
1913 V = Phi->removeIncomingValue(In,
false);
1915 NewPhi->addIncoming(V, In);
1918 if (Phi->getNumOperands() == 0) {
1919 Phi->replaceAllUsesWith(NewPhi);
1920 I = Phi->eraseFromParent();
1923 Phi->addIncoming(NewPhi, GuardBlock);
1941static std::tuple<Value *, BasicBlock *, BasicBlock *>
1945 "Only support branch terminator.");
1947 auto Condition = Branch->isConditional() ? Branch->getCondition() :
nullptr;
1951 Succ0 = Outgoing.
count(Succ0) ? Succ0 :
nullptr;
1953 if (Branch->isUnconditional()) {
1954 Branch->setSuccessor(0, FirstGuardBlock);
1957 Succ1 = Branch->getSuccessor(1);
1958 Succ1 = Outgoing.
count(Succ1) ? Succ1 :
nullptr;
1960 if (Succ0 && !Succ1) {
1961 Branch->setSuccessor(0, FirstGuardBlock);
1962 }
else if (Succ1 && !Succ0) {
1963 Branch->setSuccessor(1, FirstGuardBlock);
1965 Branch->eraseFromParent();
1971 return std::make_tuple(Condition, Succ0, Succ1);
1988 for (
int i = 0, e = GuardBlocks.
size() - 1; i != e; ++i) {
1989 auto Out = Outgoing[i];
2005 auto FirstGuardBlock = GuardBlocks.
front();
2008 "merged.bb.idx", FirstGuardBlock);
2014 std::tie(Condition, Succ0, Succ1) =
2016 Value *IncomingId =
nullptr;
2017 if (Succ0 && Succ1) {
2019 auto Succ0Iter =
find(Outgoing, Succ0);
2020 auto Succ1Iter =
find(Outgoing, Succ1);
2022 std::distance(Outgoing.
begin(), Succ0Iter));
2024 std::distance(Outgoing.
begin(), Succ1Iter));
2026 In->getTerminator()->getIterator());
2029 auto SuccIter = Succ0 ?
find(Outgoing, Succ0) :
find(Outgoing, Succ1);
2031 std::distance(Outgoing.
begin(), SuccIter));
2033 Phi->addIncoming(IncomingId, In);
2036 for (
int i = 0, e = Outgoing.
size() - 1; i != e; ++i) {
2037 auto Out = Outgoing[i];
2038 auto Cmp = ICmpInst::Create(Instruction::ICmp, ICmpInst::ICMP_EQ, Phi,
2040 Out->getName() +
".predicate", GuardBlocks[i]);
2041 GuardPredicates[Out] = Cmp;
2053 auto FirstGuardBlock = GuardBlocks.
front();
2057 for (
int i = 0, e = Outgoing.
size() - 1; i != e; ++i) {
2058 auto Out = Outgoing[i];
2059 LLVM_DEBUG(
dbgs() <<
"Creating guard for " << Out->getName() <<
"\n");
2063 StringRef(
"Guard.") + Out->getName(), FirstGuardBlock);
2064 GuardPredicates[Out] = Phi;
2071 std::tie(Condition, Succ0, Succ1) =
2081 bool OneSuccessorDone =
false;
2082 for (
int i = 0, e = Outgoing.
size() - 1; i != e; ++i) {
2083 auto Out = Outgoing[i];
2084 PHINode *Phi = cast<PHINode>(GuardPredicates[Out]);
2085 if (Out != Succ0 && Out != Succ1) {
2086 Phi->addIncoming(BoolFalse, In);
2087 }
else if (!Succ0 || !Succ1 || OneSuccessorDone) {
2090 Phi->addIncoming(BoolTrue, In);
2094 Phi->addIncoming(Condition, In);
2097 DeletionCandidates.
push_back(Condition);
2098 Phi->addIncoming(Inverted, In);
2100 OneSuccessorDone =
true;
2120 std::optional<unsigned> MaxControlFlowBooleans) {
2124 for (
int i = 0, e = Outgoing.
size() - 1; i != e; ++i)
2133 if (!MaxControlFlowBooleans || Outgoing.
size() <= *MaxControlFlowBooleans)
2135 DeletionCandidates);
2145 const StringRef Prefix, std::optional<unsigned> MaxControlFlowBooleans) {
2146 if (Outgoing.
size() < 2)
2147 return Outgoing.
front();
2153 if (Outgoing.
count(Succ))
2154 Updates.
push_back({DominatorTree::Delete,
In, Succ});
2160 Prefix, MaxControlFlowBooleans);
2161 auto FirstGuardBlock = GuardBlocks.
front();
2164 for (
int i = 0, e = GuardBlocks.
size(); i != e; ++i)
2170 int NumGuards = GuardBlocks.
size();
2171 assert((
int)Outgoing.
size() == NumGuards + 1);
2174 Updates.
push_back({DominatorTree::Insert,
In, FirstGuardBlock});
2176 for (
int i = 0; i != NumGuards - 1; ++i) {
2177 Updates.
push_back({DominatorTree::Insert, GuardBlocks[i], Outgoing[i]});
2179 {DominatorTree::Insert, GuardBlocks[i], GuardBlocks[i + 1]});
2181 Updates.
push_back({DominatorTree::Insert, GuardBlocks[NumGuards - 1],
2182 Outgoing[NumGuards - 1]});
2183 Updates.
push_back({DominatorTree::Insert, GuardBlocks[NumGuards - 1],
2184 Outgoing[NumGuards]});
2188 for (
auto I : DeletionCandidates) {
2190 if (
auto Inst = dyn_cast_or_null<Instruction>(
I))
2191 Inst->eraseFromParent();
2194 return FirstGuardBlock;
2201 if (NewCond->
hasOneUse() && isa<CmpInst>(NewCond)) {
2202 CmpInst *CI = cast<CmpInst>(NewCond);
2212 for (
auto &BB :
F) {
2213 auto *Term = BB.getTerminator();
2214 if (!(isa<ReturnInst>(Term) || isa<UnreachableInst>(Term) ||
2215 isa<BranchInst>(Term)))
2224 if (!Src.getParent()->isPresplitCoroutine())
2226 if (
auto *SW = dyn_cast<SwitchInst>(Src.getTerminator()))
2227 if (
auto *
Intr = dyn_cast<IntrinsicInst>(SW->getCondition()))
2228 return Intr->getIntrinsicID() == Intrinsic::coro_suspend &&
2229 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 bool DPValuesRemoveRedundantDbgInstrsUsingForwardScan(BasicBlock *BB)
Remove redundant dbg.value instructions using a forward scan.
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 bool DPValuesRemoveUndefDbgAssignsFromEntryBlock(BasicBlock *BB)
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 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 DPValuesRemoveRedundantDbgInstrsUsingBackwardScan(BasicBlock *BB)
Remove redundant instructions within sequences of consecutive dbg.value instructions.
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)
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)
Record of a variable value-assignment, aka a non instruction representation of the dbg....
DIExpression * getExpression() const
LocationType getType() const
DILocalVariable * getVariable() const
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
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 DPValue 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...