LLVM 20.0.0git
BreakCriticalEdges.cpp
Go to the documentation of this file.
1//===- BreakCriticalEdges.cpp - Critical Edge Elimination Pass ------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// BreakCriticalEdges pass - Break all of the critical edges in the CFG by
10// inserting a dummy basic block. This pass may be "required" by passes that
11// cannot deal with critical edges. For this usage, the structure type is
12// forward declared. This pass obviously invalidates the CFG, but can update
13// dominator trees.
14//
15//===----------------------------------------------------------------------===//
16
18#include "llvm/ADT/SetVector.h"
20#include "llvm/ADT/Statistic.h"
23#include "llvm/Analysis/CFG.h"
27#include "llvm/IR/CFG.h"
28#include "llvm/IR/Dominators.h"
35using namespace llvm;
36
37#define DEBUG_TYPE "break-crit-edges"
38
39STATISTIC(NumBroken, "Number of blocks inserted");
40
41namespace {
42 struct BreakCriticalEdges : public FunctionPass {
43 static char ID; // Pass identification, replacement for typeid
44 BreakCriticalEdges() : FunctionPass(ID) {
46 }
47
48 bool runOnFunction(Function &F) override {
49 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
50 auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
51
52 auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>();
53 auto *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr;
54
55 auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
56 auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
57 unsigned N =
59 NumBroken += N;
60 return N > 0;
61 }
62
63 void getAnalysisUsage(AnalysisUsage &AU) const override {
66
67 // No loop canonicalization guarantees are broken by this pass.
69 }
70 };
71}
72
73char BreakCriticalEdges::ID = 0;
74INITIALIZE_PASS(BreakCriticalEdges, "break-crit-edges",
75 "Break critical edges in CFG", false, false)
76
77// Publicly exposed interface to pass...
78char &llvm::BreakCriticalEdgesID = BreakCriticalEdges::ID;
80 return new BreakCriticalEdges();
81}
82
86 auto *LI = AM.getCachedResult<LoopAnalysis>(F);
88 NumBroken += N;
89 if (N == 0)
94 return PA;
95}
96
97//===----------------------------------------------------------------------===//
98// Implementation of the external critical edge manipulation functions
99//===----------------------------------------------------------------------===//
100
103 const Twine &BBName) {
104 if (!isCriticalEdge(TI, SuccNum, Options.MergeIdenticalEdges))
105 return nullptr;
106
107 return SplitKnownCriticalEdge(TI, SuccNum, Options, BBName);
108}
109
113 const Twine &BBName) {
114 assert(!isa<IndirectBrInst>(TI) &&
115 "Cannot split critical edge from IndirectBrInst");
116
117 BasicBlock *TIBB = TI->getParent();
118 BasicBlock *DestBB = TI->getSuccessor(SuccNum);
119
120 // Splitting the critical edge to a pad block is non-trivial. Don't do
121 // it in this generic function.
122 if (DestBB->isEHPad()) return nullptr;
123
124 if (Options.IgnoreUnreachableDests &&
125 isa<UnreachableInst>(DestBB->getFirstNonPHIOrDbgOrLifetime()))
126 return nullptr;
127
128 auto *LI = Options.LI;
130 // Check if extra modifications will be required to preserve loop-simplify
131 // form after splitting. If it would require splitting blocks with IndirectBr
132 // terminators, bail out if preserving loop-simplify form is requested.
133 if (LI) {
134 if (Loop *TIL = LI->getLoopFor(TIBB)) {
135
136 // The only way that we can break LoopSimplify form by splitting a
137 // critical edge is if after the split there exists some edge from TIL to
138 // DestBB *and* the only edge into DestBB from outside of TIL is that of
139 // NewBB. If the first isn't true, then LoopSimplify still holds, NewBB
140 // is the new exit block and it has no non-loop predecessors. If the
141 // second isn't true, then DestBB was not in LoopSimplify form prior to
142 // the split as it had a non-loop predecessor. In both of these cases,
143 // the predecessor must be directly in TIL, not in a subloop, or again
144 // LoopSimplify doesn't hold.
145 for (BasicBlock *P : predecessors(DestBB)) {
146 if (P == TIBB)
147 continue; // The new block is known.
148 if (LI->getLoopFor(P) != TIL) {
149 // No need to re-simplify, it wasn't to start with.
150 LoopPreds.clear();
151 break;
152 }
153 LoopPreds.push_back(P);
154 }
155 // Loop-simplify form can be preserved, if we can split all in-loop
156 // predecessors.
157 if (any_of(LoopPreds, [](BasicBlock *Pred) {
158 return isa<IndirectBrInst>(Pred->getTerminator());
159 })) {
160 if (Options.PreserveLoopSimplify)
161 return nullptr;
162 LoopPreds.clear();
163 }
164 }
165 }
166
167 // Create a new basic block, linking it into the CFG.
168 BasicBlock *NewBB = nullptr;
169 if (BBName.str() != "")
170 NewBB = BasicBlock::Create(TI->getContext(), BBName);
171 else
172 NewBB = BasicBlock::Create(TI->getContext(), TIBB->getName() + "." +
173 DestBB->getName() +
174 "_crit_edge");
175 // Create our unconditional branch.
176 BranchInst *NewBI = BranchInst::Create(DestBB, NewBB);
177 NewBI->setDebugLoc(TI->getDebugLoc());
178
179 // Insert the block into the function... right after the block TI lives in.
180 Function &F = *TIBB->getParent();
181 Function::iterator FBBI = TIBB->getIterator();
182 F.insert(++FBBI, NewBB);
183
184 // Branch to the new block, breaking the edge.
185 TI->setSuccessor(SuccNum, NewBB);
186
187 // If there are any PHI nodes in DestBB, we need to update them so that they
188 // merge incoming values from NewBB instead of from TIBB.
189 {
190 unsigned BBIdx = 0;
191 for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) {
192 // We no longer enter through TIBB, now we come in through NewBB.
193 // Revector exactly one entry in the PHI node that used to come from
194 // TIBB to come from NewBB.
195 PHINode *PN = cast<PHINode>(I);
196
197 // Reuse the previous value of BBIdx if it lines up. In cases where we
198 // have multiple phi nodes with *lots* of predecessors, this is a speed
199 // win because we don't have to scan the PHI looking for TIBB. This
200 // happens because the BB list of PHI nodes are usually in the same
201 // order.
202 if (PN->getIncomingBlock(BBIdx) != TIBB)
203 BBIdx = PN->getBasicBlockIndex(TIBB);
204 PN->setIncomingBlock(BBIdx, NewBB);
205 }
206 }
207
208 // If there are any other edges from TIBB to DestBB, update those to go
209 // through the split block, making those edges non-critical as well (and
210 // reducing the number of phi entries in the DestBB if relevant).
211 if (Options.MergeIdenticalEdges) {
212 for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) {
213 if (TI->getSuccessor(i) != DestBB) continue;
214
215 // Remove an entry for TIBB from DestBB phi nodes.
216 DestBB->removePredecessor(TIBB, Options.KeepOneInputPHIs);
217
218 // We found another edge to DestBB, go to NewBB instead.
219 TI->setSuccessor(i, NewBB);
220 }
221 }
222
223 // If we have nothing to update, just return.
224 auto *DT = Options.DT;
225 auto *PDT = Options.PDT;
226 auto *MSSAU = Options.MSSAU;
227 if (MSSAU)
228 MSSAU->wireOldPredecessorsToNewImmediatePredecessor(
229 DestBB, NewBB, {TIBB}, Options.MergeIdenticalEdges);
230
231 if (!DT && !PDT && !LI)
232 return NewBB;
233
234 if (DT || PDT) {
235 // Update the DominatorTree.
236 // ---> NewBB -----\
237 // / V
238 // TIBB -------\\------> DestBB
239 //
240 // First, inform the DT about the new path from TIBB to DestBB via NewBB,
241 // then delete the old edge from TIBB to DestBB. By doing this in that order
242 // DestBB stays reachable in the DT the whole time and its subtree doesn't
243 // get disconnected.
245 Updates.push_back({DominatorTree::Insert, TIBB, NewBB});
246 Updates.push_back({DominatorTree::Insert, NewBB, DestBB});
247 if (!llvm::is_contained(successors(TIBB), DestBB))
248 Updates.push_back({DominatorTree::Delete, TIBB, DestBB});
249
250 if (DT)
251 DT->applyUpdates(Updates);
252 if (PDT)
253 PDT->applyUpdates(Updates);
254 }
255
256 // Update LoopInfo if it is around.
257 if (LI) {
258 if (Loop *TIL = LI->getLoopFor(TIBB)) {
259 // If one or the other blocks were not in a loop, the new block is not
260 // either, and thus LI doesn't need to be updated.
261 if (Loop *DestLoop = LI->getLoopFor(DestBB)) {
262 if (TIL == DestLoop) {
263 // Both in the same loop, the NewBB joins loop.
264 DestLoop->addBasicBlockToLoop(NewBB, *LI);
265 } else if (TIL->contains(DestLoop)) {
266 // Edge from an outer loop to an inner loop. Add to the outer loop.
267 TIL->addBasicBlockToLoop(NewBB, *LI);
268 } else if (DestLoop->contains(TIL)) {
269 // Edge from an inner loop to an outer loop. Add to the outer loop.
270 DestLoop->addBasicBlockToLoop(NewBB, *LI);
271 } else {
272 // Edge from two loops with no containment relation. Because these
273 // are natural loops, we know that the destination block must be the
274 // header of its loop (adding a branch into a loop elsewhere would
275 // create an irreducible loop).
276 assert(DestLoop->getHeader() == DestBB &&
277 "Should not create irreducible loops!");
278 if (Loop *P = DestLoop->getParentLoop())
279 P->addBasicBlockToLoop(NewBB, *LI);
280 }
281 }
282
283 // If TIBB is in a loop and DestBB is outside of that loop, we may need
284 // to update LoopSimplify form and LCSSA form.
285 if (!TIL->contains(DestBB)) {
286 assert(!TIL->contains(NewBB) &&
287 "Split point for loop exit is contained in loop!");
288
289 // Update LCSSA form in the newly created exit block.
290 if (Options.PreserveLCSSA) {
291 createPHIsForSplitLoopExit(TIBB, NewBB, DestBB);
292 }
293
294 if (!LoopPreds.empty()) {
295 assert(!DestBB->isEHPad() && "We don't split edges to EH pads!");
297 DestBB, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA);
298 if (Options.PreserveLCSSA)
299 createPHIsForSplitLoopExit(LoopPreds, NewExitBB, DestBB);
300 }
301 }
302 }
303 }
304
305 return NewBB;
306}
307
308// Return the unique indirectbr predecessor of a block. This may return null
309// even if such a predecessor exists, if it's not useful for splitting.
310// If a predecessor is found, OtherPreds will contain all other (non-indirectbr)
311// predecessors of BB.
312static BasicBlock *
314 // Verify we have exactly one IBR predecessor.
315 // Conservatively bail out if one of the other predecessors is not a "regular"
316 // terminator (that is, not a switch or a br).
317 BasicBlock *IBB = nullptr;
318 for (BasicBlock *PredBB : predecessors(BB)) {
319 Instruction *PredTerm = PredBB->getTerminator();
320 switch (PredTerm->getOpcode()) {
321 case Instruction::IndirectBr:
322 if (IBB)
323 return nullptr;
324 IBB = PredBB;
325 break;
326 case Instruction::Br:
327 case Instruction::Switch:
328 OtherPreds.push_back(PredBB);
329 continue;
330 default:
331 return nullptr;
332 }
333 }
334
335 return IBB;
336}
337
339 bool IgnoreBlocksWithoutPHI,
341 BlockFrequencyInfo *BFI) {
342 // Check whether the function has any indirectbrs, and collect which blocks
343 // they may jump to. Since most functions don't have indirect branches,
344 // this lowers the common case's overhead to O(Blocks) instead of O(Edges).
346 for (auto &BB : F) {
347 if (isa<IndirectBrInst>(BB.getTerminator()))
348 for (BasicBlock *Succ : successors(&BB))
349 Targets.insert(Succ);
350 }
351
352 if (Targets.empty())
353 return false;
354
355 bool ShouldUpdateAnalysis = BPI && BFI;
356 bool Changed = false;
357 for (BasicBlock *Target : Targets) {
358 if (IgnoreBlocksWithoutPHI && Target->phis().empty())
359 continue;
360
362 BasicBlock *IBRPred = findIBRPredecessor(Target, OtherPreds);
363 // If we did not found an indirectbr, or the indirectbr is the only
364 // incoming edge, this isn't the kind of edge we're looking for.
365 if (!IBRPred || OtherPreds.empty())
366 continue;
367
368 // Don't even think about ehpads/landingpads.
369 Instruction *FirstNonPHI = Target->getFirstNonPHI();
370 if (FirstNonPHI->isEHPad() || Target->isLandingPad())
371 continue;
372
373 // Remember edge probabilities if needed.
374 SmallVector<BranchProbability, 4> EdgeProbabilities;
375 if (ShouldUpdateAnalysis) {
376 EdgeProbabilities.reserve(Target->getTerminator()->getNumSuccessors());
377 for (unsigned I = 0, E = Target->getTerminator()->getNumSuccessors();
378 I < E; ++I)
379 EdgeProbabilities.emplace_back(BPI->getEdgeProbability(Target, I));
380 BPI->eraseBlock(Target);
381 }
382
383 BasicBlock *BodyBlock = Target->splitBasicBlock(FirstNonPHI, ".split");
384 if (ShouldUpdateAnalysis) {
385 // Copy the BFI/BPI from Target to BodyBlock.
386 BPI->setEdgeProbability(BodyBlock, EdgeProbabilities);
387 BFI->setBlockFreq(BodyBlock, BFI->getBlockFreq(Target));
388 }
389 // It's possible Target was its own successor through an indirectbr.
390 // In this case, the indirectbr now comes from BodyBlock.
391 if (IBRPred == Target)
392 IBRPred = BodyBlock;
393
394 // At this point Target only has PHIs, and BodyBlock has the rest of the
395 // block's body. Create a copy of Target that will be used by the "direct"
396 // preds.
398 BasicBlock *DirectSucc = CloneBasicBlock(Target, VMap, ".clone", &F);
399
400 BlockFrequency BlockFreqForDirectSucc;
401 for (BasicBlock *Pred : OtherPreds) {
402 // If the target is a loop to itself, then the terminator of the split
403 // block (BodyBlock) needs to be updated.
404 BasicBlock *Src = Pred != Target ? Pred : BodyBlock;
405 Src->getTerminator()->replaceUsesOfWith(Target, DirectSucc);
406 if (ShouldUpdateAnalysis)
407 BlockFreqForDirectSucc += BFI->getBlockFreq(Src) *
408 BPI->getEdgeProbability(Src, DirectSucc);
409 }
410 if (ShouldUpdateAnalysis) {
411 BFI->setBlockFreq(DirectSucc, BlockFreqForDirectSucc);
412 BlockFrequency NewBlockFreqForTarget =
413 BFI->getBlockFreq(Target) - BlockFreqForDirectSucc;
414 BFI->setBlockFreq(Target, NewBlockFreqForTarget);
415 }
416
417 // Ok, now fix up the PHIs. We know the two blocks only have PHIs, and that
418 // they are clones, so the number of PHIs are the same.
419 // (a) Remove the edge coming from IBRPred from the "Direct" PHI
420 // (b) Leave that as the only edge in the "Indirect" PHI.
421 // (c) Merge the two in the body block.
422 BasicBlock::iterator Indirect = Target->begin(),
423 End = Target->getFirstNonPHIIt();
424 BasicBlock::iterator Direct = DirectSucc->begin();
425 BasicBlock::iterator MergeInsert = BodyBlock->getFirstInsertionPt();
426
427 assert(&*End == Target->getTerminator() &&
428 "Block was expected to only contain PHIs");
429
430 while (Indirect != End) {
431 PHINode *DirPHI = cast<PHINode>(Direct);
432 PHINode *IndPHI = cast<PHINode>(Indirect);
433 BasicBlock::iterator InsertPt = Indirect;
434
435 // Now, clean up - the direct block shouldn't get the indirect value,
436 // and vice versa.
437 DirPHI->removeIncomingValue(IBRPred);
438 Direct++;
439
440 // Advance the pointer here, to avoid invalidation issues when the old
441 // PHI is erased.
442 Indirect++;
443
444 PHINode *NewIndPHI = PHINode::Create(IndPHI->getType(), 1, "ind", InsertPt);
445 NewIndPHI->addIncoming(IndPHI->getIncomingValueForBlock(IBRPred),
446 IBRPred);
447
448 // Create a PHI in the body block, to merge the direct and indirect
449 // predecessors.
450 PHINode *MergePHI = PHINode::Create(IndPHI->getType(), 2, "merge");
451 MergePHI->insertBefore(MergeInsert);
452 MergePHI->addIncoming(NewIndPHI, Target);
453 MergePHI->addIncoming(DirPHI, DirectSucc);
454
455 IndPHI->replaceAllUsesWith(MergePHI);
456 IndPHI->eraseFromParent();
457 }
458
459 Changed = true;
460 }
461
462 return Changed;
463}
static BasicBlock * findIBRPredecessor(BasicBlock *BB, SmallVectorImpl< BasicBlock * > &OtherPreds)
bool End
Definition: ELF_riscv.cpp:480
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
static LVOptions Options
Definition: LVOptions.cpp:25
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define P(N)
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)
Definition: PassSupport.h:38
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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)
Definition: Statistic.h:167
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:424
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.
Definition: BasicBlock.h:61
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:448
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:416
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:212
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,...
Definition: BasicBlock.cpp:400
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:219
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:177
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:675
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...
Definition: BasicBlock.h:239
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:516
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.
void eraseBlock(const BasicBlock *BB)
Forget analysis results for the given basic block.
void setEdgeProbability(const BasicBlock *Src, const SmallVectorImpl< BranchProbability > &Probs)
Set the raw probabilities for all edges from the given block.
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.
Definition: Dominators.h:279
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:317
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:310
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
BasicBlockListType::iterator iterator
Definition: Function.h:69
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:97
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:466
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:824
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:92
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:274
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:463
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:571
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:598
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
void setIncomingBlock(unsigned i, BasicBlock *BB)
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 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...
Definition: Pass.cpp:98
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:117
void preserve()
Mark an analysis as preserved.
Definition: Analysis.h:131
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:93
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:162
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
bool empty() const
Definition: SmallVector.h:95
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:587
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:951
void reserve(size_type N)
Definition: SmallVector.h:677
void push_back(const T &Elt)
Definition: SmallVector.h:427
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1210
Target - Wrapper for Target specific information.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
std::string str() const
Return the twine contents as a std::string.
Definition: Twine.cpp:17
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:534
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:1075
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
const ParentTy * getParent() const
Definition: ilist_node.h:32
self_iterator getIterator()
Definition: ilist_node.h:132
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto successors(const MachineBasicBlock *BB)
char & LoopSimplifyID
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,...
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.
Definition: STLExtras.h:1729
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...
void initializeBreakCriticalEdgesPass(PassRegistry &)
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 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.
bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
Definition: CFG.cpp:95
char & BreakCriticalEdgesID
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1879
FunctionPass * createBreakCriticalEdgesPass()
#define N
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Option class for critical edge splitting.