37#define DEBUG_TYPE "break-crit-edges"
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;
73char BreakCriticalEdges::ID = 0;
75 "Break critical edges in CFG",
false,
false)
80 return new BreakCriticalEdges();
103 const Twine &BBName) {
113 const Twine &BBName) {
120 if (DestBB->
isEHPad() || isa<IndirectBrInst>(TI))
123 if (
Options.IgnoreUnreachableDests &&
133 if (
Loop *TIL = LI->getLoopFor(TIBB)) {
147 if (LI->getLoopFor(
P) != TIL) {
159 if (
Options.PreserveLoopSimplify)
168 if (BBName.
str() !=
"")
177 if (
auto *LoopMD = TI->
getMetadata(LLVMContext::MD_loop))
183 F.insert(++FBBI, NewBB);
209 unsigned NumSplitIdenticalEdges = 1;
214 if (
Options.MergeIdenticalEdges) {
225 NumSplitIdenticalEdges++;
234 MSSAU->wireOldPredecessorsToNewImmediatePredecessor(
235 DestBB, NewBB, {TIBB},
Options.MergeIdenticalEdges);
237 if (!DT && !PDT && !LI)
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!");
304 if (!LoopPreds.
empty()) {
305 assert(!DestBB->
isEHPad() &&
"We don't split edges to EH pads!");
307 DestBB, LoopPreds,
"split", DT, LI, MSSAU,
Options.PreserveLCSSA);
331 case Instruction::IndirectBr:
336 case Instruction::Br:
337 case Instruction::Switch:
349 bool IgnoreBlocksWithoutPHI,
357 if (isa<IndirectBrInst>(BB.getTerminator()))
364 bool ShouldUpdateAnalysis = BPI && BFI;
365 bool Changed =
false;
367 if (IgnoreBlocksWithoutPHI &&
Target->phis().empty())
374 if (!IBRPred || OtherPreds.
empty())
378 auto FirstNonPHIIt =
Target->getFirstNonPHIIt();
379 if (FirstNonPHIIt->isEHPad() ||
Target->isLandingPad())
384 if (ShouldUpdateAnalysis) {
385 EdgeProbabilities.
reserve(
Target->getTerminator()->getNumSuccessors());
386 for (
unsigned I = 0, E =
Target->getTerminator()->getNumSuccessors();
393 if (ShouldUpdateAnalysis) {
396 BFI->setBlockFreq(BodyBlock, BFI->getBlockFreq(
Target));
417 Src->getTerminator()->replaceUsesOfWith(
Target, DirectSucc);
418 if (ShouldUpdateAnalysis)
419 BlockFreqForDirectSucc += BFI->getBlockFreq(Src) *
422 if (ShouldUpdateAnalysis) {
423 BFI->setBlockFreq(DirectSucc, BlockFreqForDirectSucc);
425 BFI->getBlockFreq(
Target) - BlockFreqForDirectSucc;
426 BFI->setBlockFreq(
Target, NewBlockFreqForTarget);
440 "Block was expected to only contain PHIs");
442 while (Indirect !=
End) {
443 PHINode *DirPHI = cast<PHINode>(Direct);
444 PHINode *IndPHI = cast<PHINode>(Indirect);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static BasicBlock * findIBRPredecessor(BasicBlock *BB, SmallVectorImpl< BasicBlock * > &OtherPreds)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
static cl::opt< bool > SplitAllCriticalEdges("phi-elim-split-all-critical-edges", cl::init(false), cl::Hidden, cl::desc("Split all critical edges during " "PHI elimination"))
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
A container for analyses that lazily runs them and caches their results.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
AnalysisUsage & addPreservedID(const void *ID)
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
LLVM_ABI const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
const Function * getParent() const
Return the enclosing method, or null if none.
InstListType::iterator iterator
Instruction iterators...
LLVM_ABI InstListType::const_iterator getFirstNonPHIOrDbgOrLifetime(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode, a debug intrinsic,...
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...
LLVM_ABI void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Conditional or Unconditional Branch instruction.
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
Analysis providing branch probability information.
LLVM_ABI void eraseBlock(const BasicBlock *BB)
Forget analysis results for the given basic block.
LLVM_ABI void setEdgeProbability(const BasicBlock *Src, const SmallVectorImpl< BranchProbability > &Probs)
Set the raw probabilities for all edges from the given block.
LLVM_ABI BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge's probability, relative to other out-edges of the Src.
Analysis pass which computes a DominatorTree.
void applyUpdates(ArrayRef< UpdateType > Updates)
Inform the dominator tree about a sequence of CFG edge insertions and deletions and perform a batch u...
static constexpr UpdateKind Delete
static constexpr UpdateKind Insert
Legacy analysis pass which computes a DominatorTree.
FunctionPass class - This class is used to implement most global optimizations.
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
BasicBlockListType::iterator iterator
LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_ABI void insertBefore(InstListType::iterator InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified position.
LLVM_ABI 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.
LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
LLVM_ABI void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
LLVM_ABI void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
LLVM_ABI void applyMergedLocation(DebugLoc LocA, DebugLoc LocB)
Merge 2 debug locations and apply it to the Instruction.
Analysis pass that exposes the LoopInfo for a function.
The legacy pass manager's analysis pass to compute loop information.
Represents a single loop in the control flow graph.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
void setIncomingBlock(unsigned i, BasicBlock *BB)
LLVM_ABI 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.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static LLVM_ABI PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
PreservedAnalyses & preserve()
Mark an analysis as preserved.
void insert_range(Range &&R)
bool empty() const
Determine if the SetVector is empty or not.
A SetVector that performs no allocations if smaller than a certain size.
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.
Target - Wrapper for Target specific information.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
LLVM_ABI std::string str() const
Return the twine contents as a std::string.
DMAtomT AtomMap
Map {(InlinedAt, old atom number) -> new atom number}.
Type * getType() const
All values are typed, get the type of this value.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
LLVM_ABI LLVMContext & getContext() const
All values hold a context through their type.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
const ParentTy * getParent() const
self_iterator getIterator()
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
This is an optimization pass for GlobalISel generic memory operations.
LLVM_ABI BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, bool MapAtoms=true)
Return a copy of the specified basic block, but without embedding the block into a particular functio...
auto successors(const MachineBasicBlock *BB)
LLVM_ABI FunctionPass * createBreakCriticalEdgesPass()
LLVM_ABI char & LoopSimplifyID
LLVM_ABI 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,...
LLVM_ABI bool SplitIndirectBrCriticalEdges(Function &F, bool IgnoreBlocksWithoutPHI, BranchProbabilityInfo *BPI=nullptr, BlockFrequencyInfo *BFI=nullptr)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI char & BreakCriticalEdgesID
LLVM_ABI 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...
LLVM_ABI 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.
LLVM_ABI void initializeBreakCriticalEdgesPass(PassRegistry &)
LLVM_ABI 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.
LLVM_ABI bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
LLVM_ABI void RemapSourceAtom(Instruction *I, ValueToValueMapTy &VM)
Remap source location atom.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Option class for critical edge splitting.