Go to the documentation of this file.
37 #define DEBUG_TYPE "break-crit-edges"
39 STATISTIC(NumBroken,
"Number of blocks inserted");
49 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
50 auto *DT = DTWP ? &DTWP->getDomTree() :
nullptr;
52 auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>();
53 auto *PDT = PDTWP ? &PDTWP->getPostDomTree() :
nullptr;
55 auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
56 auto *LI = LIWP ? &LIWP->getLoopInfo() :
nullptr;
75 "Break critical edges in CFG",
false,
false)
80 return new BreakCriticalEdges();
103 const Twine &BBName) {
113 const Twine &BBName) {
114 assert(!isa<IndirectBrInst>(TI) &&
115 "Cannot split critical edge from IndirectBrInst");
122 if (DestBB->
isEHPad())
return nullptr;
124 if (
Options.IgnoreUnreachableDests &&
135 if (
Loop *TIL = LI->getLoopFor(TIBB)) {
149 if (LI->getLoopFor(
P) != TIL) {
154 LoopPreds.push_back(
P);
160 if (
const auto *CBR = dyn_cast<CallBrInst>(
T))
161 return CBR->getDefaultDest() != Pred;
162 return isa<IndirectBrInst>(
T);
164 if (
Options.PreserveLoopSimplify)
173 if (BBName.
str() !=
"")
186 F.getBasicBlockList().insert(++FBBI, NewBB);
215 if (
Options.MergeIdenticalEdges) {
232 MSSAU->wireOldPredecessorsToNewImmediatePredecessor(
233 DestBB, NewBB, {TIBB},
Options.MergeIdenticalEdges);
235 if (!DT && !PDT && !LI)
255 DT->applyUpdates(Updates);
257 PDT->applyUpdates(Updates);
262 if (
Loop *TIL = LI->getLoopFor(TIBB)) {
265 if (
Loop *DestLoop = LI->getLoopFor(DestBB)) {
266 if (TIL == DestLoop) {
268 DestLoop->addBasicBlockToLoop(NewBB, *LI);
269 }
else if (TIL->contains(DestLoop)) {
271 TIL->addBasicBlockToLoop(NewBB, *LI);
272 }
else if (DestLoop->contains(TIL)) {
274 DestLoop->addBasicBlockToLoop(NewBB, *LI);
280 assert(DestLoop->getHeader() == DestBB &&
281 "Should not create irreducible loops!");
282 if (
Loop *
P = DestLoop->getParentLoop())
283 P->addBasicBlockToLoop(NewBB, *LI);
289 if (!TIL->contains(DestBB)) {
290 assert(!TIL->contains(NewBB) &&
291 "Split point for loop exit is contained in loop!");
298 if (!LoopPreds.empty()) {
299 assert(!DestBB->
isEHPad() &&
"We don't split edges to EH pads!");
301 DestBB, LoopPreds,
"split", DT, LI, MSSAU,
Options.PreserveLCSSA);
325 case Instruction::IndirectBr:
330 case Instruction::Br:
331 case Instruction::Switch:
332 OtherPreds.push_back(PredBB);
343 bool IgnoreBlocksWithoutPHI,
351 auto *IBI = dyn_cast<IndirectBrInst>(
BB.getTerminator());
355 for (
unsigned Succ = 0,
E = IBI->getNumSuccessors(); Succ !=
E; ++Succ)
356 Targets.
insert(IBI->getSuccessor(Succ));
362 bool ShouldUpdateAnalysis = BPI &&
BFI;
363 bool Changed =
false;
365 if (IgnoreBlocksWithoutPHI &&
Target->phis().empty())
372 if (!IBRPred || OtherPreds.empty())
382 if (ShouldUpdateAnalysis) {
383 EdgeProbabilities.
reserve(
Target->getTerminator()->getNumSuccessors());
384 for (
unsigned I = 0,
E =
Target->getTerminator()->getNumSuccessors();
391 if (ShouldUpdateAnalysis) {
394 BFI->setBlockFreq(BodyBlock,
BFI->getBlockFreq(
Target).getFrequency());
412 Src->getTerminator()->replaceUsesOfWith(
Target, DirectSucc);
413 if (ShouldUpdateAnalysis)
414 BlockFreqForDirectSucc +=
BFI->getBlockFreq(Src) *
417 if (ShouldUpdateAnalysis) {
420 BFI->getBlockFreq(
Target) - BlockFreqForDirectSucc;
430 End =
Target->getFirstNonPHI()->getIterator();
435 "Block was expected to only contain PHIs");
437 while (Indirect != End) {
438 PHINode *DirPHI = cast<PHINode>(Direct);
439 PHINode *IndPHI = cast<PHINode>(Indirect);
A set of analyses that are preserved following a run of a transformation pass.
This is an optimization pass for GlobalISel generic memory operations.
FunctionPass * createBreakCriticalEdgesPass()
InstListType::iterator iterator
Instruction iterators...
const Function * getParent() const
Return the enclosing method, or null if none.
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
Target - Wrapper for Target specific information.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
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.
The legacy pass manager's analysis pass to compute loop information.
static constexpr UpdateKind Insert
auto successors(MachineBasicBlock *BB)
bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
LLVM Basic Block Representation.
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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.
Analysis providing branch probability information.
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Represent the analysis usage information of a pass.
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...
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Legacy analysis pass which computes a DominatorTree.
const char LLVMTargetMachineRef LLVMPassBuilderOptionsRef Options
STATISTIC(NumFunctions, "Total number of functions")
auto predecessors(MachineBasicBlock *BB)
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
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 empty() const
Determine if the SetVector is empty or not.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
std::string str() const
Return the twine contents as a std::string.
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...
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void setIncomingBlock(unsigned i, BasicBlock *BB)
void preserve()
Mark an analysis as preserved.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool SplitIndirectBrCriticalEdges(Function &F, bool IgnoreBlocksWithoutPHI, BranchProbabilityInfo *BPI=nullptr, BlockFrequencyInfo *BFI=nullptr)
void eraseBlock(const BasicBlock *BB)
Forget analysis results for the given basic block.
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge's probability, relative to other out-edges of the Src.
bool insert(const value_type &X)
Insert a new element into the SetVector.
void setEdgeProbability(const BasicBlock *Src, const SmallVectorImpl< BranchProbability > &Probs)
Set the raw probabilities for all edges from the given block.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
AnalysisUsage & addPreservedID(const void *ID)
Type * getType() const
All values are typed, get the type of this value.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
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.
LLVMContext & getContext() const
All values hold a context through their type.
self_iterator getIterator()
StringRef getName() const
Return a constant reference to the value's name.
static bool runOnFunction(Function &F, bool PostInlining)
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
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...
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
char & BreakCriticalEdgesID
const Instruction * getFirstNonPHIOrDbgOrLifetime(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode, a debug intrinsic,...
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.
static BasicBlock * findIBRPredecessor(BasicBlock *BB, SmallVectorImpl< BasicBlock * > &OtherPreds)
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
const BasicBlock * getParent() const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
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 removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
A SetVector that performs no allocations if smaller than a certain size.
A container for analyses that lazily runs them and caches their results.
FunctionPass class - This class is used to implement most global optimizations.
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
Conditional or Unconditional Branch instruction.
void reserve(size_type N)
void initializeBreakCriticalEdgesPass(PassRegistry &)
bool isEHPad() const
Return true if this basic block is an exception handling block.
Analysis pass that exposes the LoopInfo for a function.
static constexpr UpdateKind Delete
reference emplace_back(ArgTypes &&... Args)
BasicBlockListType::iterator iterator