Go to the documentation of this file.
52 #define DEBUG_TYPE "basicblock-utils"
56 cl::desc(
"Set the maximum path length when checking whether a basic block "
57 "is followed by a block that either has a terminating "
58 "deoptimizing call or is terminated with an unreachable"));
63 bool KeepOneInputPHIs) {
64 for (
auto *
BB : BBs) {
69 Succ->removePredecessor(
BB, KeepOneInputPHIs);
70 if (Updates && UniqueSuccessors.
insert(Succ).second)
75 while (!
BB->empty()) {
84 BB->getInstList().pop_back();
87 assert(
BB->getInstList().size() == 1 &&
88 isa<UnreachableInst>(
BB->getTerminator()) &&
89 "The successor list of BB isn't empty before "
90 "applying corresponding DTU updates.");
95 bool KeepOneInputPHIs) {
100 bool KeepOneInputPHIs) {
107 assert(
Dead.count(Pred) &&
"All predecessors must be dead!");
120 BB->eraseFromParent();
124 bool KeepOneInputPHIs) {
132 std::vector<BasicBlock*> DeadBlocks;
135 DeadBlocks.push_back(&
BB);
140 return !DeadBlocks.empty();
145 if (!isa<PHINode>(
BB->begin()))
148 while (
PHINode *PN = dyn_cast<PHINode>(
BB->begin())) {
149 if (PN->getIncomingValue(0) != PN)
150 PN->replaceAllUsesWith(PN->getIncomingValue(0));
157 PN->eraseFromParent();
170 bool Changed =
false;
171 for (
unsigned i = 0,
e = PHIs.size();
i !=
e; ++
i)
172 if (
PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[
i].
operator Value*()))
181 bool PredecessorWithTwoSuccessors) {
182 if (
BB->hasAddressTaken())
187 if (!PredBB)
return false;
190 if (PredBB ==
BB)
return false;
203 unsigned FallThruPath;
204 if (PredecessorWithTwoSuccessors) {
205 if (!(PredBB_BI = dyn_cast<BranchInst>(PredBB->
getTerminator())))
207 BranchInst *BB_JmpI = dyn_cast<BranchInst>(
BB->getTerminator());
224 if (isa<PHINode>(
BB->front())) {
226 if (!isa<PHINode>(PN.getIncomingValue(0)) ||
227 cast<PHINode>(PN.getIncomingValue(0))->getParent() !=
BB)
228 IncomingValues.push_back(PN.getIncomingValue(0));
234 std::vector<DominatorTree::UpdateType> Updates;
240 Updates.reserve(Updates.size() + 2 *
succ_size(
BB) + 1);
249 if (!SuccsOfPredBB.
contains(SuccOfBB))
250 if (SeenSuccs.
insert(SuccOfBB).second)
254 if (SeenSuccs.
insert(SuccOfBB).second)
276 BB->replaceAllUsesWith(PredBB);
278 if (PredecessorWithTwoSuccessors) {
280 BB->getInstList().pop_back();
322 assert(!MergeBlocks.
empty() &&
"MergeBlocks should not be empty");
324 bool BlocksHaveBeenMerged =
false;
325 while (!MergeBlocks.
empty()) {
328 if (Dest && (!L || L->
contains(Dest))) {
333 "Expecting BB to be unique predecessor of the Dest block");
334 MergeBlocks.
erase(Dest);
335 BlocksHaveBeenMerged =
true;
341 return BlocksHaveBeenMerged;
371 DVI->getExpression(),
372 DVI->getDebugLoc()->getInlinedAt());
378 ToBeRemoved.push_back(DVI);
387 for (
auto &Instr : ToBeRemoved)
388 Instr->eraseFromParent();
390 return !ToBeRemoved.empty();
416 for (
auto &
I : *
BB) {
420 DVI->getDebugLoc()->getInlinedAt());
421 auto VMI = VariableMap.
find(
Key);
425 if (VMI == VariableMap.
end() || VMI->second.first != Values ||
426 VMI->second.second != DVI->getExpression()) {
427 VariableMap[
Key] = {Values, DVI->getExpression()};
431 ToBeRemoved.push_back(DVI);
435 for (
auto &Instr : ToBeRemoved)
436 Instr->eraseFromParent();
438 return !ToBeRemoved.empty();
442 bool MadeChanges =
false;
459 <<
BB->getName() <<
"\n");
467 I.replaceAllUsesWith(V);
479 assert(
I->getParent() ==
nullptr &&
480 "ReplaceInstWithInst: Instruction already inserted into basic block!");
484 if (!
I->getDebugLoc())
485 I->setDebugLoc(BI->getDebugLoc());
503 if (
BB->getTerminatingDeoptimizeCall() ||
504 isa<UnreachableInst>(
BB->getTerminator()))
506 BB =
BB->getUniqueSuccessor();
518 const Twine &BBName) {
549 assert(
BB->getTerminator()->getNumSuccessors() == 1 &&
550 "Should have a single succ!");
551 return SplitBlock(
BB,
BB->getTerminator(), DT, LI, MSSAU, BBName);
555 if (
auto *II = dyn_cast<InvokeInst>(TI))
556 II->setUnwindDest(Succ);
557 else if (
auto *CS = dyn_cast<CatchSwitchInst>(TI))
558 CS->setUnwindDest(Succ);
559 else if (
auto *CR = dyn_cast<CleanupReturnInst>(TI))
560 CR->setUnwindDest(Succ);
579 if (PN.getIncomingBlock(BBIdx) != OldPred)
580 BBIdx = PN.getBasicBlockIndex(OldPred);
582 assert(BBIdx != -1 &&
"Invalid PHI Index!");
583 PN.setIncomingBlock(BBIdx, NewPred);
589 PHINode *LandingPadReplacement,
591 const Twine &BBName) {
594 if (!LandingPadReplacement && !PadInst->
isEHPad())
602 if (
Options.PreserveLoopSimplify && LI) {
603 if (
Loop *BBLoop = LI->getLoopFor(
BB)) {
617 if (LI->getLoopFor(
P) != BBLoop) {
623 LoopPreds.push_back(
P);
640 if (LandingPadReplacement) {
641 auto *NewLP = OriginalPad->
clone();
646 Value *ParentPad =
nullptr;
647 if (
auto *FuncletPad = dyn_cast<FuncletPadInst>(PadInst))
648 ParentPad = FuncletPad->getParentPad();
649 else if (
auto *CatchSwitch = dyn_cast<CatchSwitchInst>(PadInst))
650 ParentPad = CatchSwitch->getParentPad();
651 else if (
auto *CleanupPad = dyn_cast<CleanupPadInst>(PadInst))
652 ParentPad = CleanupPad->getParentPad();
653 else if (
auto *LandingPad = dyn_cast<LandingPadInst>(PadInst))
654 ParentPad = LandingPad->getParent();
679 MSSAU->applyUpdates(Updates, *DT);
681 MSSAU->getMemorySSA()->verifyMemorySSA();
686 if (
Loop *BBLoop = LI->getLoopFor(
BB)) {
689 if (
Loop *SuccLoop = LI->getLoopFor(Succ)) {
690 if (BBLoop == SuccLoop) {
692 SuccLoop->addBasicBlockToLoop(NewBB, *LI);
693 }
else if (BBLoop->contains(SuccLoop)) {
695 BBLoop->addBasicBlockToLoop(NewBB, *LI);
696 }
else if (SuccLoop->contains(BBLoop)) {
698 SuccLoop->addBasicBlockToLoop(NewBB, *LI);
704 assert(SuccLoop->getHeader() == Succ &&
705 "Should not create irreducible loops!");
706 if (
Loop *
P = SuccLoop->getParentLoop())
707 P->addBasicBlockToLoop(NewBB, *LI);
713 if (!BBLoop->contains(Succ)) {
714 assert(!BBLoop->contains(NewBB) &&
715 "Split point for loop exit is contained in loop!");
722 if (!LoopPreds.empty()) {
724 Succ, LoopPreds,
"split", DT, LI, MSSAU,
Options.PreserveLCSSA);
740 "SplitBB has non-PHI nodes!");
744 int Idx = PN.getBasicBlockIndex(SplitBB);
745 assert(Idx >= 0 &&
"Invalid Block Index");
746 Value *V = PN.getIncomingValue(Idx);
750 if (
const PHINode *VP = dyn_cast<PHINode>(V))
751 if (VP->getParent() == SplitBB)
756 PN.getType(), Preds.
size(),
"split",
762 PN.setIncomingValue(Idx, NewPN);
769 unsigned NumBroken = 0;
773 !isa<CallBrInst>(TI))
784 const Twine &BBName,
bool Before) {
788 DTU ? DTU : (DT ? &LocalDTU :
nullptr), LI, MSSAU,
792 while (isa<PHINode>(SplitIt) || SplitIt->isEHPad()) {
796 std::string
Name = BBName.
str();
804 L->addBasicBlockToLoop(New, *LI);
813 if (UniqueSuccessorsOfOld.
insert(SuccessorOfOld).second) {
822 std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
841 return SplitBlockImpl(Old, SplitPt,
nullptr, DT, LI, MSSAU, BBName,
848 return SplitBlockImpl(Old, SplitPt, DTU,
nullptr, LI, MSSAU, BBName,
855 const Twine &BBName) {
858 while (isa<PHINode>(SplitIt) || SplitIt->isEHPad())
860 std::string
Name = BBName.
str();
869 L->addBasicBlockToLoop(New, *LI);
879 if (UniquePredecessorsOfOld.
insert(PredecessorOfOld).second) {
902 bool PreserveLCSSA,
bool &HasLoopExit) {
917 Updates.
reserve(Updates.size() + 2 * Preds.
size());
918 for (
auto *Pred : Preds)
919 if (UniquePreds.
insert(Pred).second) {
945 assert(DT &&
"DT should be available to update LoopInfo!");
950 bool IsLoopEntry = !!L;
951 bool SplitMakesNewLoopHeader =
false;
963 if (!
PL->contains(OldBB))
973 SplitMakesNewLoopHeader =
true;
985 Loop *InnermostPredLoop =
nullptr;
990 while (PredLoop && !PredLoop->contains(OldBB))
994 if (PredLoop && PredLoop->contains(OldBB) &&
995 (!InnermostPredLoop ||
996 InnermostPredLoop->
getLoopDepth() < PredLoop->getLoopDepth()))
997 InnermostPredLoop = PredLoop;
1001 if (InnermostPredLoop)
1005 if (SplitMakesNewLoopHeader)
1022 Value *InVal =
nullptr;
1068 if (PredSet.
count(IncomingBB)) {
1090 if (!
BB->canSplitPredecessors())
1095 if (
BB->isLandingPad()) {
1097 std::string NewName = std::string(Suffix) +
".split-lp";
1100 DTU, DT, LI, MSSAU, PreserveLCSSA);
1106 BB->getContext(),
BB->getName() + Suffix,
BB->getParent(),
BB);
1129 for (
unsigned i = 0,
e = Preds.
size();
i !=
e; ++
i) {
1133 assert(!isa<IndirectBrInst>(Preds[
i]->getTerminator()) &&
1134 "Cannot split an edge from an IndirectBrInst");
1135 assert(!isa<CallBrInst>(Preds[
i]->getTerminator()) &&
1136 "Cannot split an edge from a CallBrInst");
1137 Preds[
i]->getTerminator()->replaceUsesOfWith(
BB, NewBB);
1144 if (Preds.
empty()) {
1151 bool HasLoopExit =
false;
1155 if (!Preds.
empty()) {
1162 if (NewLatch != OldLatch) {
1180 bool PreserveLCSSA) {
1182 MSSAU, PreserveLCSSA);
1189 bool PreserveLCSSA) {
1191 nullptr, LI, MSSAU, PreserveLCSSA);
1206 NewBBs.push_back(NewBB1);
1213 for (
unsigned i = 0,
e = Preds.
size();
i !=
e; ++
i) {
1217 assert(!isa<IndirectBrInst>(Preds[
i]->getTerminator()) &&
1218 "Cannot split an edge from an IndirectBrInst");
1219 Preds[
i]->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1);
1222 bool HasLoopExit =
false;
1224 PreserveLCSSA, HasLoopExit);
1234 if (Pred == NewBB1)
continue;
1236 "Cannot split an edge from an IndirectBrInst");
1237 NewBB2Preds.push_back(Pred);
1242 if (!NewBB2Preds.empty()) {
1247 NewBBs.push_back(NewBB2);
1255 NewBB2Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2);
1258 HasLoopExit =
false;
1260 PreserveLCSSA, HasLoopExit);
1280 "Split cannot be applied if LPad is token type. Otherwise an "
1281 "invalid PHINode of token type would be created.");
1298 const char *Suffix1,
const char *Suffix2,
1302 bool PreserveLCSSA) {
1304 OrigBB, Preds, Suffix1, Suffix2, NewBBs,
1305 nullptr, DT, LI, MSSAU, PreserveLCSSA);
1309 const char *Suffix1,
const char *Suffix2,
1313 bool PreserveLCSSA) {
1315 NewBBs, DTU,
nullptr, LI, MSSAU,
1332 if (
BitCastInst *BCI = dyn_cast<BitCastInst>(V)) {
1335 V = BCI->getOperand(0);
1336 NewBC = BCI->
clone();
1343 V = EVI->getOperand(0);
1344 NewEV = EVI->
clone();
1354 if (
PHINode *PN = dyn_cast<PHINode>(V)) {
1355 if (PN->getParent() ==
BB) {
1357 NewEV->
setOperand(0, PN->getIncomingValueForBlock(Pred));
1359 NewBC->
setOperand(0, PN->getIncomingValueForBlock(Pred));
1361 Op = PN->getIncomingValueForBlock(Pred);
1368 BB->removePredecessor(Pred);
1374 return cast<ReturnInst>(NewRet);
1379 bool Unreachable,
MDNode *BranchWeights,
1390 if (UniqueSuccessorsOfHead.
insert(SuccessorOfHead).second) {
1398 bool CreateThenBlock = (ThenBlock ==
nullptr);
1399 if (CreateThenBlock) {
1415 HeadNewTerm->
setMetadata(LLVMContext::MD_prof, BranchWeights);
1422 std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
1429 if (CreateThenBlock)
1438 L->addBasicBlockToLoop(ThenBlock, *LI);
1439 L->addBasicBlockToLoop(
Tail, *LI);
1454 nullptr, DT, LI, ThenBlock);
1463 BranchWeights, DTU,
nullptr, LI,
1478 (*ThenTerm)->setDebugLoc(SplitBefore->
getDebugLoc());
1480 (*ElseTerm)->setDebugLoc(SplitBefore->
getDebugLoc());
1483 HeadNewTerm->
setMetadata(LLVMContext::MD_prof, BranchWeights);
1489 PHINode *SomePHI = dyn_cast<PHINode>(
BB->begin());
1514 if (!Pred1Br || !Pred2Br)
1566 if (!BI)
return nullptr;
1592 while (
I != Out->
end() && isa<PHINode>(
I)) {
1593 auto Phi = cast<PHINode>(
I);
1596 Phi->getName() +
".moved", &FirstGuardBlock->
back());
1597 for (
auto In : Incoming) {
1601 }
else if (Phi->getBasicBlockIndex(
In) != -1) {
1602 V = Phi->removeIncomingValue(
In,
false);
1604 NewPhi->addIncoming(V,
In);
1606 assert(NewPhi->getNumIncomingValues() == Incoming.size());
1607 if (Phi->getNumOperands() == 0) {
1608 Phi->replaceAllUsesWith(NewPhi);
1609 I = Phi->eraseFromParent();
1612 Phi->addIncoming(NewPhi, GuardBlock);
1630 static std::tuple<Value *, BasicBlock *, BasicBlock *>
1633 auto Branch = cast<BranchInst>(
BB->getTerminator());
1634 auto Condition =
Branch->isConditional() ?
Branch->getCondition() :
nullptr;
1638 Succ0 = Outgoing.
count(Succ0) ? Succ0 :
nullptr;
1640 if (
Branch->isUnconditional()) {
1641 Branch->setSuccessor(0, FirstGuardBlock);
1644 Succ1 =
Branch->getSuccessor(1);
1645 Succ1 = Outgoing.
count(Succ1) ? Succ1 :
nullptr;
1647 if (Succ0 && !Succ1) {
1648 Branch->setSuccessor(0, FirstGuardBlock);
1649 }
else if (Succ1 && !Succ0) {
1650 Branch->setSuccessor(1, FirstGuardBlock);
1652 Branch->eraseFromParent();
1658 return std::make_tuple(Condition, Succ0, Succ1);
1682 for (
int i = 0,
e = Outgoing.
size() - 1;
i !=
e; ++
i) {
1683 auto Out = Outgoing[
i];
1684 LLVM_DEBUG(
dbgs() <<
"Creating guard for " << Out->getName() <<
"\n");
1687 StringRef(
"Guard.") + Out->getName(), FirstGuardBlock);
1688 GuardPredicates[Out] = Phi;
1691 for (
auto In : Incoming) {
1695 std::tie(Condition, Succ0, Succ1) =
1705 bool OneSuccessorDone =
false;
1706 for (
int i = 0,
e = Outgoing.
size() - 1;
i !=
e; ++
i) {
1707 auto Out = Outgoing[
i];
1708 auto Phi = GuardPredicates[Out];
1709 if (Out != Succ0 && Out != Succ1) {
1710 Phi->addIncoming(BoolFalse,
In);
1715 if (!Succ0 || !Succ1 || OneSuccessorDone) {
1716 Phi->addIncoming(BoolTrue,
In);
1720 OneSuccessorDone =
true;
1722 Phi->addIncoming(Condition,
In);
1726 DeletionCandidates.push_back(Condition);
1727 Phi->addIncoming(Inverted,
In);
1745 for (
int i = 0,
e = Outgoing.
size() - 2;
i !=
e; ++
i) {
1746 GuardBlocks.push_back(
1749 assert(GuardBlocks.size() == GuardPredicates.
size());
1753 GuardBlocks.push_back(Outgoing.
back());
1755 for (
int i = 0,
e = GuardBlocks.size() - 1;
i !=
e; ++
i) {
1756 auto Out = Outgoing[
i];
1763 GuardBlocks.pop_back();
1770 auto F = Incoming.
front()->getParent();
1771 auto FirstGuardBlock =
1776 for (
auto In : Incoming) {
1779 if (Outgoing.
count(Succ))
1788 Incoming, Outgoing);
1790 GuardBlocks.push_back(FirstGuardBlock);
1794 for (
int i = 0,
e = GuardBlocks.size();
i !=
e; ++
i) {
1795 reconnectPhis(Outgoing[
i], GuardBlocks[
i], Incoming, FirstGuardBlock);
1800 int NumGuards = GuardBlocks.size();
1801 assert((
int)Outgoing.
size() == NumGuards + 1);
1802 for (
int i = 0;
i != NumGuards - 1; ++
i) {
1808 Outgoing[NumGuards - 1]});
1810 Outgoing[NumGuards]});
1814 for (
auto I : DeletionCandidates) {
1816 if (
auto Inst = dyn_cast_or_null<Instruction>(
I))
1817 Inst->eraseFromParent();
1820 return FirstGuardBlock;
void removeInstruction(Instruction *InstToRemove)
Removes an instruction from the dependence analysis, updating the dependence of instructions that pre...
Value * invertCondition(Value *Condition)
Invert the given true/false value, possibly reusing an existing copy.
This is an optimization pass for GlobalISel generic memory operations.
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...
static std::tuple< Value *, BasicBlock *, BasicBlock * > redirectToHub(BasicBlock *BB, BasicBlock *FirstGuardBlock, const BBSetVector &Outgoing)
static IntegerType * getInt1Ty(LLVMContext &C)
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
Return a value (possibly void), from a function.
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
InstListType::iterator iterator
Instruction iterators...
const Function * getParent() const
Return the enclosing method, or null if none.
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Interval::succ_iterator succ_end(Interval *I)
Represents a single loop in the control flow graph.
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
static void createGuardBlocks(SmallVectorImpl< BasicBlock * > &GuardBlocks, Function *F, const BBSetVector &Outgoing, BBPredicates &GuardPredicates, StringRef Prefix)
size_type size() const
Determine the number of elements in the SetVector.
This class represents a no-op cast from one type to another.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
unsigned pred_size(MachineBasicBlock *BB)
The landingpad instruction holds all of the information necessary to generate correct exception handl...
Implements a dense probed hash-table based set with some number of buckets stored inline.
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
DomTreeNodeBase< NodeT > * setNewRoot(NodeT *BB)
Add a new node to the forward dominator tree and make it a new root.
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
void DeleteDeadBlocks(ArrayRef< BasicBlock * > BBs, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified blocks from BB.
void invalidateCachedPredecessors()
Clears the PredIteratorCache info.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
void detachDeadBlocks(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< DominatorTree::UpdateType > *Updates, bool KeepOneInputPHIs=false)
Replace contents of every block in BBs with single unreachable instruction.
void removeBlock(BlockT *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
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.
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.
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
static constexpr UpdateKind Insert
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...
void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was spliced into From and To.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)
Split the basic block into two basic blocks at the specified instruction.
static Instruction * SplitBlockAndInsertIfThenImpl(Value *Cond, Instruction *SplitBefore, bool Unreachable, MDNode *BranchWeights, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, BasicBlock *ThenBlock)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
auto successors(MachineBasicBlock *BB)
bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
static BasicBlock * SplitBlockPredecessorsImpl(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
std::pair< iterator, bool > insert(const ValueT &V)
bool isExceptionalTerminator() const
void applyUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT, bool UpdateDTFirst=false)
Apply CFG updates, analogous with the DT edge updates.
bool empty() const
empty - Check if the array is empty.
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
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...
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
LLVM Basic Block Representation.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
@ Tail
Tail - This calling convention attemps to make calls as fast as possible while guaranteeing that tail...
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
This represents the llvm.dbg.value instruction.
BasicBlock * CreateControlFlowHub(DomTreeUpdater *DTU, SmallVectorImpl< BasicBlock * > &GuardBlocks, const SetVector< BasicBlock * > &Predecessors, const SetVector< BasicBlock * > &Successors, const StringRef Prefix)
Given a set of incoming and outgoing blocks, create a "hub" such that every edge from an incoming blo...
(vector float) vec_cmpeq(*A, *B) C
static CleanupReturnInst * Create(Value *CleanupPad, BasicBlock *UnwindBB=nullptr, Instruction *InsertBefore=nullptr)
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,...
iterator begin()
Instruction iterator methods.
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.
bool isLandingPad() const
Return true if this basic block is a landing pad.
void recalculate(Function &F)
Notify DTU that the entry block was replaced.
void ReplaceInstWithInst(BasicBlock::InstListType &BIL, BasicBlock::iterator &BI, Instruction *I)
Replace the instruction specified by BI with the instruction specified by I.
Option class for critical edge splitting.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
unsigned succ_size(MachineBasicBlock *BB)
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
bool isTokenTy() const
Return true if this is 'token'.
static void convertToGuardPredicates(BasicBlock *FirstGuardBlock, BBPredicates &GuardPredicates, SmallVectorImpl< WeakVH > &DeletionCandidates, const BBSetVector &Incoming, const BBSetVector &Outgoing)
const char LLVMTargetMachineRef LLVMPassBuilderOptionsRef Options
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
auto predecessors(MachineBasicBlock *BB)
void setName(const Twine &Name)
Change the name of the value.
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
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...
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
bool RemoveRedundantDbgInstrs(BasicBlock *BB)
Try to remove redundant dbg.value instructions from given basic block.
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.
static bool removeRedundantDbgInstrsUsingForwardScan(BasicBlock *BB)
Remove redundant dbg.value instructions using a forward scan.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
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 hasDomTree() const
Returns true if it holds a DominatorTree.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
std::string str() const
Return the twine contents as a std::string.
BranchInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
bool isEntryBlock() const
Return true if this is the entry block of the containing function.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
static bool removeRedundantDbgInstrsUsingBackwardScan(BasicBlock *BB)
Remove redundant instructions within sequences of consecutive dbg.value instructions.
void moveToHeader(BlockT *BB)
This method is used to move BB (which must be part of this loop) to be the loop header of the loop (t...
NoneType
A simple null object to allow implicit construction of Optional<T> and similar types without having t...
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
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"))
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
This is an important class for using LLVM in a threaded context.
DominatorTree & getDomTree()
Flush DomTree updates and return DomTree.
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
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...
initializer< Ty > init(const Ty &Val)
Identifies a unique instance of a variable.
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
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.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
iterator find(const_arg_type_t< KeyT > Val)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
unsigned getLoopDepth() const
Return the nesting level of this loop.
static BasicBlock * SplitBlockImpl(BasicBlock *Old, Instruction *SplitPt, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, const Twine &BBName, bool Before)
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, Instruction **ThenTerm, Instruction **ElseTerm, MDNode *BranchWeights=nullptr)
SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, but also creates the ElseBlock...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
bool isUnconditional() const
void setOperand(unsigned i, Value *Val)
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...
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false)
Attempts to merge a block into its predecessor, if possible.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
SmallVector< MachineOperand, 4 > Cond
StringRef - Represent a constant reference to a string, i.e.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Type * getType() const
All values are typed, get the type of this value.
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
self_iterator getIterator()
static CleanupPadInst * Create(Value *ParentPad, ArrayRef< Value * > Args=None, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
void flush()
Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.
StringRef getName() const
Return a constant reference to the value's name.
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
static ConstantInt * getFalse(LLVMContext &Context)
const Instruction & front() const
LLVMContext & getContext() const
Get the context in which this basic block lives.
void ReplaceInstWithValue(BasicBlock::InstListType &BIL, BasicBlock::iterator &BI, Value *V)
Replace all uses of an instruction (specified by BI) with a value, then remove and delete the origina...
Provides a lazy, caching interface for making common memory aliasing information queries,...
bool isLoopHeader(const BlockT *BB) const
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
static ConstantInt * getTrue(LLVMContext &Context)
void setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ)
Sets the unwind edge of an instruction to a particular successor.
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...
void wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New, ArrayRef< BasicBlock * > Preds, bool IdenticalEdgesWereMerged=true)
A new empty BasicBlock (New) now branches directly to Old.
void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was merged into To.
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.
Interval::pred_iterator pred_end(Interval *I)
void splitBlock(NodeT *NewBB)
splitBlock - BB is split and now it has one successor.
CriticalEdgeSplittingOptions & setPreserveLCSSA()
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Provides information about what library functions are available for the current target.
const T & front() const
Return the first element of the SetVector.
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Class that has the common methods + fields of memory uses/defs.
BasicBlock * splitBlockBefore(BasicBlock *Old, Instruction *SplitPt, DomTreeUpdater *DTU, LoopInfo *LI, MemorySSAUpdater *MSSAU, const Twine &BBName="")
Split the specified block at the specified instruction SplitPt.
bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
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.
const Instruction & back() const
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...
unsigned SplitAllCriticalEdges(Function &F, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
Loop over all of the edges in the CFG, breaking critical edges as they are found.
const InstListType & getInstList() const
Return the underlying instruction list container.
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 @...
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
bool MergeBlockSuccessorsIntoGivenBlocks(SmallPtrSetImpl< BasicBlock * > &MergeBlocks, Loop *L=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr)
Merge block(s) sucessors, if possible.
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
LLVM_NODISCARD bool empty() const
const BasicBlock * getParent() const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
size_t size() const
size - Get the array size.
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...
const LandingPadInst * getLandingPadInst() const
Return the landingpad instruction associated with the landing pad.
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
const T & back() const
Return the last element of the SetVector.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
This function has undefined behavior.
bool VerifyMemorySSA
Enables verification of MemorySSA.
BlockVerifier::State From
void takeName(Value *V)
Transfer the name from V to this value.
Instruction * SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore, bool Unreachable, MDNode *BranchWeights, DominatorTree *DT, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
Conditional or Unconditional Branch instruction.
A vector that has set insertion semantics.
bool contains(ConstPtrType Ptr) const
void reserve(size_type N)
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
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)
bool isEHPad() const
Return true if this basic block is an exception handling block.
LLVM Value Representation.
static void reconnectPhis(BasicBlock *Out, BasicBlock *GuardBlock, const SetVector< BasicBlock * > &Incoming, BasicBlock *FirstGuardBlock)
bool isConditional() const
BasicBlock * getSuccessor(unsigned i) const
static constexpr UpdateKind Delete
A Use represents the edge between a Value definition and its users.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.