Go to the documentation of this file.
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();
105 const Twine &BBName) {
115 const Twine &BBName) {
116 assert(!isa<IndirectBrInst>(TI) &&
117 "Cannot split critical edge from IndirectBrInst");
124 if (DestBB->
isEHPad())
return nullptr;
130 auto *LI = Options.
LI;
137 if (
Loop *TIL = LI->getLoopFor(TIBB)) {
151 if (LI->getLoopFor(
P) != TIL) {
156 LoopPreds.push_back(
P);
162 if (
const auto *CBR = dyn_cast<CallBrInst>(
T))
163 return CBR->getDefaultDest() != Pred;
164 return isa<IndirectBrInst>(
T);
175 if (BBName.
str() !=
"")
188 F.getBasicBlockList().insert(++FBBI, NewBB);
230 auto *DT = Options.
DT;
231 auto *PDT = Options.
PDT;
232 auto *MSSAU = Options.
MSSAU;
237 if (!DT && !PDT && !LI)
257 DT->applyUpdates(Updates);
259 PDT->applyUpdates(Updates);
264 if (
Loop *TIL = LI->getLoopFor(TIBB)) {
267 if (
Loop *DestLoop = LI->getLoopFor(DestBB)) {
268 if (TIL == DestLoop) {
270 DestLoop->addBasicBlockToLoop(NewBB, *LI);
271 }
else if (TIL->contains(DestLoop)) {
273 TIL->addBasicBlockToLoop(NewBB, *LI);
274 }
else if (DestLoop->contains(TIL)) {
276 DestLoop->addBasicBlockToLoop(NewBB, *LI);
282 assert(DestLoop->getHeader() == DestBB &&
283 "Should not create irreducible loops!");
284 if (
Loop *
P = DestLoop->getParentLoop())
285 P->addBasicBlockToLoop(NewBB, *LI);
291 if (!TIL->contains(DestBB)) {
292 assert(!TIL->contains(NewBB) &&
293 "Split point for loop exit is contained in loop!");
300 if (!LoopPreds.empty()) {
301 assert(!DestBB->
isEHPad() &&
"We don't split edges to EH pads!");
303 DestBB, LoopPreds,
"split", DT, LI, MSSAU, Options.
PreserveLCSSA);
322 PHINode *PN = dyn_cast<PHINode>(
BB->begin());
334 case Instruction::IndirectBr:
339 case Instruction::Br:
340 case Instruction::Switch:
341 OtherPreds.push_back(PredBB);
359 auto *IBI = dyn_cast<IndirectBrInst>(
BB.getTerminator());
363 for (
unsigned Succ = 0,
E = IBI->getNumSuccessors(); Succ !=
E; ++Succ)
364 Targets.
insert(IBI->getSuccessor(Succ));
370 bool ShouldUpdateAnalysis = BPI &&
BFI;
371 bool Changed =
false;
377 if (!IBRPred || OtherPreds.empty())
387 if (ShouldUpdateAnalysis) {
388 EdgeProbabilities.
reserve(
Target->getTerminator()->getNumSuccessors());
389 for (
unsigned I = 0,
E =
Target->getTerminator()->getNumSuccessors();
396 if (ShouldUpdateAnalysis) {
399 BFI->setBlockFreq(BodyBlock,
BFI->getBlockFreq(
Target).getFrequency());
418 if (ShouldUpdateAnalysis)
419 BlockFreqForDirectSucc +=
BFI->getBlockFreq(Src) *
422 if (ShouldUpdateAnalysis) {
425 BFI->getBlockFreq(
Target) - BlockFreqForDirectSucc;
435 End =
Target->getFirstNonPHI()->getIterator();
440 "Block was expected to only contain PHIs");
442 while (Indirect != End) {
443 PHINode *DirPHI = cast<PHINode>(Direct);
444 PHINode *IndPHI = cast<PHINode>(Indirect);
A set of analyses that are preserved following a run of a transformation pass.
pred_range predecessors(BasicBlock *BB)
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
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)
succ_range successors(Instruction *I)
bool IgnoreUnreachableDests
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.
STATISTIC(NumFunctions, "Total number of functions")
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 getNumIncomingValues() const
Return the number of incoming edges.
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)
bool SplitIndirectBrCriticalEdges(Function &F, BranchProbabilityInfo *BPI=nullptr, BlockFrequencyInfo *BFI=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())
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
void eraseBlock(const BasicBlock *BB)
Forget analysis results for the given basic block.
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,...
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.
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...
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...
void wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New, ArrayRef< BasicBlock * > Preds, bool IdenticalEdgesWereMerged=true)
A new empty BasicBlock (New) now branches directly to Old.
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
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.
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 PreserveLoopSimplify
SplitCriticalEdge is guaranteed to preserve loop-simplify form if LI is provided.
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