LLVM 22.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 BasicBlock *TIBB = TI->getParent();
115 BasicBlock *DestBB = TI->getSuccessor(SuccNum);
116
117 // Splitting the critical edge to a pad block is non-trivial.
118 // And we cannot split block with IndirectBr as a terminator.
119 // Don't do it in this generic function.
120 if (DestBB->isEHPad() || isa<IndirectBrInst>(TI))
121 return nullptr;
122
123 if (Options.IgnoreUnreachableDests &&
124 isa<UnreachableInst>(DestBB->getFirstNonPHIOrDbgOrLifetime()))
125 return nullptr;
126
127 auto *LI = Options.LI;
129 // Check if extra modifications will be required to preserve loop-simplify
130 // form after splitting. If it would require splitting blocks with IndirectBr
131 // terminators, bail out if preserving loop-simplify form is requested.
132 if (LI) {
133 if (Loop *TIL = LI->getLoopFor(TIBB)) {
134
135 // The only way that we can break LoopSimplify form by splitting a
136 // critical edge is if after the split there exists some edge from TIL to
137 // DestBB *and* the only edge into DestBB from outside of TIL is that of
138 // NewBB. If the first isn't true, then LoopSimplify still holds, NewBB
139 // is the new exit block and it has no non-loop predecessors. If the
140 // second isn't true, then DestBB was not in LoopSimplify form prior to
141 // the split as it had a non-loop predecessor. In both of these cases,
142 // the predecessor must be directly in TIL, not in a subloop, or again
143 // LoopSimplify doesn't hold.
144 for (BasicBlock *P : predecessors(DestBB)) {
145 if (P == TIBB)
146 continue; // The new block is known.
147 if (LI->getLoopFor(P) != TIL) {
148 // No need to re-simplify, it wasn't to start with.
149 LoopPreds.clear();
150 break;
151 }
152 LoopPreds.push_back(P);
153 }
154 // Loop-simplify form can be preserved, if we can split all in-loop
155 // predecessors.
156 if (any_of(LoopPreds, [](BasicBlock *Pred) {
157 return isa<IndirectBrInst>(Pred->getTerminator());
158 })) {
159 if (Options.PreserveLoopSimplify)
160 return nullptr;
161 LoopPreds.clear();
162 }
163 }
164 }
165
166 // Create a new basic block, linking it into the CFG.
167 BasicBlock *NewBB = nullptr;
168 if (BBName.str() != "")
169 NewBB = BasicBlock::Create(TI->getContext(), BBName);
170 else
171 NewBB = BasicBlock::Create(TI->getContext(), TIBB->getName() + "." +
172 DestBB->getName() +
173 "_crit_edge");
174 // Create our unconditional branch.
175 BranchInst *NewBI = BranchInst::Create(DestBB, NewBB);
176 NewBI->setDebugLoc(TI->getDebugLoc());
177 if (auto *LoopMD = TI->getMetadata(LLVMContext::MD_loop))
178 NewBI->setMetadata(LLVMContext::MD_loop, LoopMD);
179
180 // Insert the block into the function... right after the block TI lives in.
181 Function &F = *TIBB->getParent();
182 Function::iterator FBBI = TIBB->getIterator();
183 F.insert(++FBBI, NewBB);
184
185 // Branch to the new block, breaking the edge.
186 TI->setSuccessor(SuccNum, NewBB);
187
188 // If there are any PHI nodes in DestBB, we need to update them so that they
189 // merge incoming values from NewBB instead of from TIBB.
190 {
191 unsigned BBIdx = 0;
192 for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) {
193 // We no longer enter through TIBB, now we come in through NewBB.
194 // Revector exactly one entry in the PHI node that used to come from
195 // TIBB to come from NewBB.
196 PHINode *PN = cast<PHINode>(I);
197
198 // Reuse the previous value of BBIdx if it lines up. In cases where we
199 // have multiple phi nodes with *lots* of predecessors, this is a speed
200 // win because we don't have to scan the PHI looking for TIBB. This
201 // happens because the BB list of PHI nodes are usually in the same
202 // order.
203 if (PN->getIncomingBlock(BBIdx) != TIBB)
204 BBIdx = PN->getBasicBlockIndex(TIBB);
205 PN->setIncomingBlock(BBIdx, NewBB);
206 }
207 }
208
209 unsigned NumSplitIdenticalEdges = 1;
210
211 // If there are any other edges from TIBB to DestBB, update those to go
212 // through the split block, making those edges non-critical as well (and
213 // reducing the number of phi entries in the DestBB if relevant).
214 if (Options.MergeIdenticalEdges) {
215 for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) {
216 if (TI->getSuccessor(i) != DestBB) continue;
217
218 // Remove an entry for TIBB from DestBB phi nodes.
219 DestBB->removePredecessor(TIBB, Options.KeepOneInputPHIs);
220
221 // We found another edge to DestBB, go to NewBB instead.
222 TI->setSuccessor(i, NewBB);
223
224 // Record the number of split identical edges to DestBB.
225 NumSplitIdenticalEdges++;
226 }
227 }
228
229 // If we have nothing to update, just return.
230 auto *DT = Options.DT;
231 auto *PDT = Options.PDT;
232 auto *MSSAU = Options.MSSAU;
233 if (MSSAU)
234 MSSAU->wireOldPredecessorsToNewImmediatePredecessor(
235 DestBB, NewBB, {TIBB}, Options.MergeIdenticalEdges);
236
237 if (!DT && !PDT && !LI)
238 return NewBB;
239
240 if (DT || PDT) {
241 // Update the DominatorTree.
242 // ---> NewBB -----\
243 // / V
244 // TIBB -------\\------> DestBB
245 //
246 // First, inform the DT about the new path from TIBB to DestBB via NewBB,
247 // then delete the old edge from TIBB to DestBB. By doing this in that order
248 // DestBB stays reachable in the DT the whole time and its subtree doesn't
249 // get disconnected.
251 Updates.push_back({DominatorTree::Insert, TIBB, NewBB});
252 Updates.push_back({DominatorTree::Insert, NewBB, DestBB});
253 if (!llvm::is_contained(successors(TIBB), DestBB))
254 Updates.push_back({DominatorTree::Delete, TIBB, DestBB});
255
256 if (DT)
257 DT->applyUpdates(Updates);
258 if (PDT)
259 PDT->applyUpdates(Updates);
260 }
261
262 // Update LoopInfo if it is around.
263 if (LI) {
264 if (Loop *TIL = LI->getLoopFor(TIBB)) {
265 // If one or the other blocks were not in a loop, the new block is not
266 // either, and thus LI doesn't need to be updated.
267 if (Loop *DestLoop = LI->getLoopFor(DestBB)) {
268 if (TIL == DestLoop) {
269 // Both in the same loop, the NewBB joins loop.
270 DestLoop->addBasicBlockToLoop(NewBB, *LI);
271 } else if (TIL->contains(DestLoop)) {
272 // Edge from an outer loop to an inner loop. Add to the outer loop.
273 TIL->addBasicBlockToLoop(NewBB, *LI);
274 } else if (DestLoop->contains(TIL)) {
275 // Edge from an inner loop to an outer loop. Add to the outer loop.
276 DestLoop->addBasicBlockToLoop(NewBB, *LI);
277 } else {
278 // Edge from two loops with no containment relation. Because these
279 // are natural loops, we know that the destination block must be the
280 // header of its loop (adding a branch into a loop elsewhere would
281 // create an irreducible loop).
282 assert(DestLoop->getHeader() == DestBB &&
283 "Should not create irreducible loops!");
284 if (Loop *P = DestLoop->getParentLoop())
285 P->addBasicBlockToLoop(NewBB, *LI);
286 }
287 }
288
289 // If TIBB is in a loop and DestBB is outside of that loop, we may need
290 // to update LoopSimplify form and LCSSA form.
291 if (!TIL->contains(DestBB)) {
292 assert(!TIL->contains(NewBB) &&
293 "Split point for loop exit is contained in loop!");
294
295 // Update LCSSA form in the newly created exit block.
296 if (Options.PreserveLCSSA) {
297 // If > 1 identical edges to be split, we need to introduce the same
298 // number of the incoming blocks for the new PHINode.
300 SmallVector<BasicBlock *, 4>(NumSplitIdenticalEdges, TIBB), NewBB,
301 DestBB);
302 }
303
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);
308 if (Options.PreserveLCSSA)
309 createPHIsForSplitLoopExit(LoopPreds, NewExitBB, DestBB);
310 }
311 }
312 }
313 }
314
315 return NewBB;
316}
317
318// Return the unique indirectbr predecessor of a block. This may return null
319// even if such a predecessor exists, if it's not useful for splitting.
320// If a predecessor is found, OtherPreds will contain all other (non-indirectbr)
321// predecessors of BB.
322static BasicBlock *
324 // Verify we have exactly one IBR predecessor.
325 // Conservatively bail out if one of the other predecessors is not a "regular"
326 // terminator (that is, not a switch or a br).
327 BasicBlock *IBB = nullptr;
328 for (BasicBlock *PredBB : predecessors(BB)) {
329 Instruction *PredTerm = PredBB->getTerminator();
330 switch (PredTerm->getOpcode()) {
331 case Instruction::IndirectBr:
332 if (IBB)
333 return nullptr;
334 IBB = PredBB;
335 break;
336 case Instruction::Br:
337 case Instruction::Switch:
338 OtherPreds.push_back(PredBB);
339 continue;
340 default:
341 return nullptr;
342 }
343 }
344
345 return IBB;
346}
347
349 bool IgnoreBlocksWithoutPHI,
351 BlockFrequencyInfo *BFI) {
352 // Check whether the function has any indirectbrs, and collect which blocks
353 // they may jump to. Since most functions don't have indirect branches,
354 // this lowers the common case's overhead to O(Blocks) instead of O(Edges).
356 for (auto &BB : F) {
357 if (isa<IndirectBrInst>(BB.getTerminator()))
358 Targets.insert_range(successors(&BB));
359 }
360
361 if (Targets.empty())
362 return false;
363
364 bool ShouldUpdateAnalysis = BPI && BFI;
365 bool Changed = false;
366 for (BasicBlock *Target : Targets) {
367 if (IgnoreBlocksWithoutPHI && Target->phis().empty())
368 continue;
369
371 BasicBlock *IBRPred = findIBRPredecessor(Target, OtherPreds);
372 // If we did not found an indirectbr, or the indirectbr is the only
373 // incoming edge, this isn't the kind of edge we're looking for.
374 if (!IBRPred || OtherPreds.empty())
375 continue;
376
377 // Don't even think about ehpads/landingpads.
378 auto FirstNonPHIIt = Target->getFirstNonPHIIt();
379 if (FirstNonPHIIt->isEHPad() || Target->isLandingPad())
380 continue;
381
382 // Remember edge probabilities if needed.
383 SmallVector<BranchProbability, 4> EdgeProbabilities;
384 if (ShouldUpdateAnalysis) {
385 EdgeProbabilities.reserve(Target->getTerminator()->getNumSuccessors());
386 for (unsigned I = 0, E = Target->getTerminator()->getNumSuccessors();
387 I < E; ++I)
388 EdgeProbabilities.emplace_back(BPI->getEdgeProbability(Target, I));
389 BPI->eraseBlock(Target);
390 }
391
392 BasicBlock *BodyBlock = Target->splitBasicBlock(FirstNonPHIIt, ".split");
393 if (ShouldUpdateAnalysis) {
394 // Copy the BFI/BPI from Target to BodyBlock.
395 BPI->setEdgeProbability(BodyBlock, EdgeProbabilities);
396 BFI->setBlockFreq(BodyBlock, BFI->getBlockFreq(Target));
397 }
398 // It's possible Target was its own successor through an indirectbr.
399 // In this case, the indirectbr now comes from BodyBlock.
400 if (IBRPred == Target)
401 IBRPred = BodyBlock;
402
403 // At this point Target only has PHIs, and BodyBlock has the rest of the
404 // block's body. Create a copy of Target that will be used by the "direct"
405 // preds.
407 BasicBlock *DirectSucc = CloneBasicBlock(Target, VMap, ".clone", &F);
408 if (!VMap.AtomMap.empty())
409 for (Instruction &I : *DirectSucc)
410 RemapSourceAtom(&I, VMap);
411
412 BlockFrequency BlockFreqForDirectSucc;
413 for (BasicBlock *Pred : OtherPreds) {
414 // If the target is a loop to itself, then the terminator of the split
415 // block (BodyBlock) needs to be updated.
416 BasicBlock *Src = Pred != Target ? Pred : BodyBlock;
417 Src->getTerminator()->replaceUsesOfWith(Target, DirectSucc);
418 if (ShouldUpdateAnalysis)
419 BlockFreqForDirectSucc += BFI->getBlockFreq(Src) *
420 BPI->getEdgeProbability(Src, DirectSucc);
421 }
422 if (ShouldUpdateAnalysis) {
423 BFI->setBlockFreq(DirectSucc, BlockFreqForDirectSucc);
424 BlockFrequency NewBlockFreqForTarget =
425 BFI->getBlockFreq(Target) - BlockFreqForDirectSucc;
426 BFI->setBlockFreq(Target, NewBlockFreqForTarget);
427 }
428
429 // Ok, now fix up the PHIs. We know the two blocks only have PHIs, and that
430 // they are clones, so the number of PHIs are the same.
431 // (a) Remove the edge coming from IBRPred from the "Direct" PHI
432 // (b) Leave that as the only edge in the "Indirect" PHI.
433 // (c) Merge the two in the body block.
434 BasicBlock::iterator Indirect = Target->begin(),
435 End = Target->getFirstNonPHIIt();
436 BasicBlock::iterator Direct = DirectSucc->begin();
437 BasicBlock::iterator MergeInsert = BodyBlock->getFirstInsertionPt();
438
439 assert(&*End == Target->getTerminator() &&
440 "Block was expected to only contain PHIs");
441
442 while (Indirect != End) {
443 PHINode *DirPHI = cast<PHINode>(Direct);
444 PHINode *IndPHI = cast<PHINode>(Indirect);
445 BasicBlock::iterator InsertPt = Indirect;
446
447 // Now, clean up - the direct block shouldn't get the indirect value,
448 // and vice versa.
449 DirPHI->removeIncomingValue(IBRPred);
450 Direct++;
451
452 // Advance the pointer here, to avoid invalidation issues when the old
453 // PHI is erased.
454 Indirect++;
455
456 PHINode *NewIndPHI = PHINode::Create(IndPHI->getType(), 1, "ind", InsertPt);
457 NewIndPHI->addIncoming(IndPHI->getIncomingValueForBlock(IBRPred),
458 IBRPred);
459 NewIndPHI->setDebugLoc(IndPHI->getDebugLoc());
460
461 // Create a PHI in the body block, to merge the direct and indirect
462 // predecessors.
463 PHINode *MergePHI = PHINode::Create(IndPHI->getType(), 2, "merge");
464 MergePHI->insertBefore(MergeInsert);
465 MergePHI->addIncoming(NewIndPHI, Target);
466 MergePHI->addIncoming(DirPHI, DirectSucc);
467 MergePHI->applyMergedLocation(DirPHI->getDebugLoc(),
468 IndPHI->getDebugLoc());
469
470 IndPHI->replaceAllUsesWith(MergePHI);
471 IndPHI->eraseFromParent();
472 }
473
474 Changed = true;
475 }
476
477 return Changed;
478}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
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:56
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:255
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:431
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:62
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:459
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...
Definition: BasicBlock.cpp:393
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:206
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:213
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:170
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,...
Definition: BasicBlock.cpp:372
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:707
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:233
LLVM_ABI void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:494
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.
bool empty() const
Definition: DenseMap.h:107
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:284
void applyUpdates(ArrayRef< UpdateType > Updates)
Inform the dominator tree about a sequence of CFG edge insertions and deletions and perform a batch u...
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:322
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:314
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
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.
Definition: Instruction.h:513
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.
Definition: Instruction.h:428
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.
Definition: Metadata.cpp:1718
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:312
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:510
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.
Definition: DebugInfo.cpp:897
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:570
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:597
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:40
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...
Definition: Pass.cpp:112
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:118
PreservedAnalyses & preserve()
Mark an analysis as preserved.
Definition: Analysis.h:132
void insert_range(Range &&R)
Definition: SetVector.h:193
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:99
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:356
bool empty() const
Definition: SmallVector.h:82
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:574
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:938
void reserve(size_type N)
Definition: SmallVector.h:664
void push_back(const T &Elt)
Definition: SmallVector.h:414
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1197
Target - Wrapper for Target specific information.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:82
LLVM_ABI std::string str() const
Return the twine contents as a std::string.
Definition: Twine.cpp:17
DMAtomT AtomMap
Map {(InlinedAt, old atom number) -> new atom number}.
Definition: ValueMap.h:123
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:546
LLVM_ABI LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:1101
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:322
const ParentTy * getParent() const
Definition: ilist_node.h:34
self_iterator getIterator()
Definition: ilist_node.h:134
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
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.
Definition: STLExtras.h:1751
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.
Definition: CFG.cpp:96
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1916
LLVM_ABI void RemapSourceAtom(Instruction *I, ValueToValueMapTy &VM)
Remap source location atom.
#define N
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Option class for critical edge splitting.