39 #define DEBUG_TYPE "break-crit-edges" 41 STATISTIC(NumBroken,
"Number of blocks inserted");
51 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
52 auto *DT = DTWP ? &DTWP->getDomTree() :
nullptr;
54 auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>();
55 auto *PDT = PDTWP ? &PDTWP->getPostDomTree() :
nullptr;
57 auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
58 auto *LI = LIWP ? &LIWP->getLoopInfo() :
nullptr;
77 "Break critical edges in CFG",
false,
false)
82 return new BreakCriticalEdges();
112 SplitBB->
isLandingPad()) &&
"SplitBB has non-PHI nodes!");
116 unsigned Idx = PN.getBasicBlockIndex(SplitBB);
117 Value *V = PN.getIncomingValue(Idx);
121 if (
const PHINode *VP = dyn_cast<PHINode>(V))
122 if (VP->getParent() == SplitBB)
127 PN.getType(), Preds.
size(),
"split",
129 for (
unsigned i = 0,
e = Preds.
size(); i !=
e; ++i)
133 PN.setIncomingValue(Idx, NewPN);
139 const Twine &BBName) {
143 assert(!isa<IndirectBrInst>(TI) &&
144 "Cannot split critical edge from IndirectBrInst");
151 if (DestBB->
isEHPad())
return nullptr;
157 auto *LI = Options.
LI;
164 if (
Loop *TIL = LI->getLoopFor(TIBB)) {
178 if (LI->getLoopFor(
P) != TIL) {
189 if (
const auto *CBR = dyn_cast<CallBrInst>(
T))
190 return CBR->getDefaultDest() != Pred;
191 return isa<IndirectBrInst>(
T);
202 if (BBName.
str() !=
"")
215 F.getBasicBlockList().insert(++FBBI, NewBB);
257 auto *DT = Options.
DT;
258 auto *PDT = Options.
PDT;
259 auto *MSSAU = Options.
MSSAU;
264 if (!DT && !PDT && !LI)
284 DT->applyUpdates(Updates);
286 PDT->applyUpdates(Updates);
291 if (
Loop *TIL = LI->getLoopFor(TIBB)) {
294 if (
Loop *DestLoop = LI->getLoopFor(DestBB)) {
295 if (TIL == DestLoop) {
297 DestLoop->addBasicBlockToLoop(NewBB, *LI);
298 }
else if (TIL->contains(DestLoop)) {
300 TIL->addBasicBlockToLoop(NewBB, *LI);
301 }
else if (DestLoop->contains(TIL)) {
303 DestLoop->addBasicBlockToLoop(NewBB, *LI);
309 assert(DestLoop->getHeader() == DestBB &&
310 "Should not create irreducible loops!");
311 if (
Loop *
P = DestLoop->getParentLoop())
312 P->addBasicBlockToLoop(NewBB, *LI);
318 if (!TIL->contains(DestBB)) {
319 assert(!TIL->contains(NewBB) &&
320 "Split point for loop exit is contained in loop!");
327 if (!LoopPreds.
empty()) {
328 assert(!DestBB->
isEHPad() &&
"We don't split edges to EH pads!");
330 DestBB, LoopPreds,
"split", DT, LI, MSSAU, Options.
PreserveLCSSA);
361 case Instruction::IndirectBr:
366 case Instruction::Br:
367 case Instruction::Switch:
386 auto *IBI = dyn_cast<IndirectBrInst>(BB.getTerminator());
390 for (
unsigned Succ = 0,
E = IBI->getNumSuccessors(); Succ !=
E; ++Succ)
391 Targets.
insert(IBI->getSuccessor(Succ));
397 bool ShouldUpdateAnalysis = BPI &&
BFI;
398 bool Changed =
false;
404 if (!IBRPred || OtherPreds.
empty())
414 if (ShouldUpdateAnalysis) {
415 EdgeProbabilities.
reserve(
Target->getTerminator()->getNumSuccessors());
416 for (
unsigned I = 0,
E =
Target->getTerminator()->getNumSuccessors();
423 if (ShouldUpdateAnalysis) {
426 BFI->setBlockFreq(BodyBlock,
BFI->getBlockFreq(
Target).getFrequency());
445 if (ShouldUpdateAnalysis)
446 BlockFreqForDirectSucc +=
BFI->getBlockFreq(Src) *
449 if (ShouldUpdateAnalysis) {
452 BFI->getBlockFreq(
Target) - BlockFreqForDirectSucc;
462 End =
Target->getFirstNonPHI()->getIterator();
467 "Block was expected to only contain PHIs");
469 while (Indirect != End) {
470 PHINode *DirPHI = cast<PHINode>(Direct);
471 PHINode *IndPHI = cast<PHINode>(Indirect);
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
reference emplace_back(ArgTypes &&... Args)
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
const Instruction * getFirstNonPHIOrDbgOrLifetime(bool SkipPseudoOp=false) const
Returns a pointer to the first instruction in this block that is not a PHINode, a debug intrinsic,...
This class represents lattice values for constants.
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
LLVM_NODISCARD bool empty() const
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
void push_back(const T &Elt)
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
LLVMContext & getContext() const
All values hold a context through their type.
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
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 Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
bool IgnoreUnreachableDests
void initializeBreakCriticalEdgesPass(PassRegistry &)
void reserve(size_type N)
iterator begin()
Instruction iterator methods.
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Option class for critical edge splitting.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
static constexpr UpdateKind Delete
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Analysis pass that exposes the LoopInfo for a function.
Type * getType() const
All values are typed, get the type of this value.
bool insert(const value_type &X)
Insert a new element into the SetVector.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
AnalysisUsage & addPreservedID(const void *ID)
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
void wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New, ArrayRef< BasicBlock * > Preds, bool IdenticalEdgesWereMerged=true)
A new empty BasicBlock (New) now branches directly to Old.
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
static bool runOnFunction(Function &F, bool PostInlining)
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
A set of analyses that are preserved following a run of a transformation pass.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
static constexpr UpdateKind Insert
LLVM Basic Block Representation.
Conditional or Unconditional Branch instruction.
char & BreakCriticalEdgesID
size_t size() const
size - Get the array size.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Value * getIncomingValueForBlock(const BasicBlock *BB) const
const Instruction & front() const
FunctionPass * createBreakCriticalEdgesPass()
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.
void eraseBlock(const BasicBlock *BB)
Forget analysis results for the given basic block.
Represent the analysis usage information of a pass.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
FunctionPass class - This class is used to implement most global optimizations.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
self_iterator getIterator()
bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge's probability, relative to other out-edges of the Src.
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
bool isLandingPad() const
Return true if this basic block is a landing pad.
A SetVector that performs no allocations if smaller than a certain size.
Iterator for intrusive lists based on ilist_node.
void setIncomingBlock(unsigned i, BasicBlock *BB)
bool PreserveLoopSimplify
SplitCriticalEdge is guaranteed to preserve loop-simplify form if LI is provided.
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...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
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...
pred_range predecessors(BasicBlock *BB)
void setEdgeProbability(const BasicBlock *Src, const SmallVectorImpl< BranchProbability > &Probs)
Set the raw probabilities for all edges from the given block.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Target - Wrapper for Target specific information.
BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, DebugInfoFinder *DIFinder=nullptr)
Return a copy of the specified basic block, but without embedding the block into a particular functio...
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
Analysis providing branch probability information.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
bool SplitIndirectBrCriticalEdges(Function &F, BranchProbabilityInfo *BPI=nullptr, BlockFrequencyInfo *BFI=nullptr)
Represents a single loop in the control flow graph.
StringRef getName() const
Return a constant reference to the value's name.
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
bool empty() const
Determine if the SetVector is empty or not.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
void preserve()
Mark an analysis as preserved.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
std::string str() const
Return the twine contents as a std::string.
static BasicBlock * findIBRPredecessor(BasicBlock *BB, SmallVectorImpl< BasicBlock * > &OtherPreds)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isEHPad() const
Return true if this basic block is an exception handling block.
LLVM Value Representation.
succ_range successors(Instruction *I)
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
The legacy pass manager's analysis pass to compute loop information.
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
static 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.
const BasicBlock * getParent() const
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.