LLVM  12.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"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/Statistic.h"
23 #include "llvm/Analysis/CFG.h"
24 #include "llvm/Analysis/LoopInfo.h"
27 #include "llvm/IR/CFG.h"
28 #include "llvm/IR/Dominators.h"
29 #include "llvm/IR/Instructions.h"
30 #include "llvm/IR/Type.h"
31 #include "llvm/InitializePasses.h"
33 #include "llvm/Transforms/Utils.h"
37 using namespace llvm;
38 
39 #define DEBUG_TYPE "break-crit-edges"
40 
41 STATISTIC(NumBroken, "Number of blocks inserted");
42 
43 namespace {
44  struct BreakCriticalEdges : public FunctionPass {
45  static char ID; // Pass identification, replacement for typeid
46  BreakCriticalEdges() : FunctionPass(ID) {
48  }
49 
50  bool runOnFunction(Function &F) override {
51  auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
52  auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
53 
54  auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>();
55  auto *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr;
56 
57  auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
58  auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
59  unsigned N =
60  SplitAllCriticalEdges(F, CriticalEdgeSplittingOptions(DT, LI, nullptr, PDT));
61  NumBroken += N;
62  return N > 0;
63  }
64 
65  void getAnalysisUsage(AnalysisUsage &AU) const override {
68 
69  // No loop canonicalization guarantees are broken by this pass.
71  }
72  };
73 }
74 
75 char BreakCriticalEdges::ID = 0;
76 INITIALIZE_PASS(BreakCriticalEdges, "break-crit-edges",
77  "Break critical edges in CFG", false, false)
78 
79 // Publicly exposed interface to pass...
80 char &llvm::BreakCriticalEdgesID = BreakCriticalEdges::ID;
82  return new BreakCriticalEdges();
83 }
84 
87  auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F);
88  auto *LI = AM.getCachedResult<LoopAnalysis>(F);
90  NumBroken += N;
91  if (N == 0)
92  return PreservedAnalyses::all();
95  PA.preserve<LoopAnalysis>();
96  return PA;
97 }
98 
99 //===----------------------------------------------------------------------===//
100 // Implementation of the external critical edge manipulation functions
101 //===----------------------------------------------------------------------===//
102 
103 /// When a loop exit edge is split, LCSSA form may require new PHIs in the new
104 /// exit block. This function inserts the new PHIs, as needed. Preds is a list
105 /// of preds inside the loop, SplitBB is the new loop exit block, and DestBB is
106 /// the old loop exit, now the successor of SplitBB.
108  BasicBlock *SplitBB,
109  BasicBlock *DestBB) {
110  // SplitBB shouldn't have anything non-trivial in it yet.
111  assert((SplitBB->getFirstNonPHI() == SplitBB->getTerminator() ||
112  SplitBB->isLandingPad()) && "SplitBB has non-PHI nodes!");
113 
114  // For each PHI in the destination block.
115  for (PHINode &PN : DestBB->phis()) {
116  unsigned Idx = PN.getBasicBlockIndex(SplitBB);
117  Value *V = PN.getIncomingValue(Idx);
118 
119  // If the input is a PHI which already satisfies LCSSA, don't create
120  // a new one.
121  if (const PHINode *VP = dyn_cast<PHINode>(V))
122  if (VP->getParent() == SplitBB)
123  continue;
124 
125  // Otherwise a new PHI is needed. Create one and populate it.
126  PHINode *NewPN = PHINode::Create(
127  PN.getType(), Preds.size(), "split",
128  SplitBB->isLandingPad() ? &SplitBB->front() : SplitBB->getTerminator());
129  for (unsigned i = 0, e = Preds.size(); i != e; ++i)
130  NewPN->addIncoming(V, Preds[i]);
131 
132  // Update the original PHI.
133  PN.setIncomingValue(Idx, NewPN);
134  }
135 }
136 
137 BasicBlock *
138 llvm::SplitCriticalEdge(Instruction *TI, unsigned SuccNum,
139  const CriticalEdgeSplittingOptions &Options) {
140  if (!isCriticalEdge(TI, SuccNum, Options.MergeIdenticalEdges))
141  return nullptr;
142 
143  assert(!isa<IndirectBrInst>(TI) &&
144  "Cannot split critical edge from IndirectBrInst");
145 
146  BasicBlock *TIBB = TI->getParent();
147  BasicBlock *DestBB = TI->getSuccessor(SuccNum);
148 
149  // Splitting the critical edge to a pad block is non-trivial. Don't do
150  // it in this generic function.
151  if (DestBB->isEHPad()) return nullptr;
152 
153  if (Options.IgnoreUnreachableDests &&
154  isa<UnreachableInst>(DestBB->getFirstNonPHIOrDbgOrLifetime()))
155  return nullptr;
156 
157  auto *LI = Options.LI;
159  // Check if extra modifications will be required to preserve loop-simplify
160  // form after splitting. If it would require splitting blocks with IndirectBr
161  // terminators, bail out if preserving loop-simplify form is requested.
162  if (LI) {
163  if (Loop *TIL = LI->getLoopFor(TIBB)) {
164 
165  // The only that we can break LoopSimplify form by splitting a critical
166  // edge is if after the split there exists some edge from TIL to DestBB
167  // *and* the only edge into DestBB from outside of TIL is that of
168  // NewBB. If the first isn't true, then LoopSimplify still holds, NewBB
169  // is the new exit block and it has no non-loop predecessors. If the
170  // second isn't true, then DestBB was not in LoopSimplify form prior to
171  // the split as it had a non-loop predecessor. In both of these cases,
172  // the predecessor must be directly in TIL, not in a subloop, or again
173  // LoopSimplify doesn't hold.
174  for (pred_iterator I = pred_begin(DestBB), E = pred_end(DestBB); I != E;
175  ++I) {
176  BasicBlock *P = *I;
177  if (P == TIBB)
178  continue; // The new block is known.
179  if (LI->getLoopFor(P) != TIL) {
180  // No need to re-simplify, it wasn't to start with.
181  LoopPreds.clear();
182  break;
183  }
184  LoopPreds.push_back(P);
185  }
186  // Loop-simplify form can be preserved, if we can split all in-loop
187  // predecessors.
188  if (any_of(LoopPreds, [](BasicBlock *Pred) {
189  return isa<IndirectBrInst>(Pred->getTerminator());
190  })) {
191  if (Options.PreserveLoopSimplify)
192  return nullptr;
193  LoopPreds.clear();
194  }
195  }
196  }
197 
198  // Create a new basic block, linking it into the CFG.
200  TIBB->getName() + "." + DestBB->getName() + "_crit_edge");
201  // Create our unconditional branch.
202  BranchInst *NewBI = BranchInst::Create(DestBB, NewBB);
203  NewBI->setDebugLoc(TI->getDebugLoc());
204 
205  // Insert the block into the function... right after the block TI lives in.
206  Function &F = *TIBB->getParent();
207  Function::iterator FBBI = TIBB->getIterator();
208  F.getBasicBlockList().insert(++FBBI, NewBB);
209 
210  // Branch to the new block, breaking the edge.
211  TI->setSuccessor(SuccNum, NewBB);
212 
213  // If there are any PHI nodes in DestBB, we need to update them so that they
214  // merge incoming values from NewBB instead of from TIBB.
215  {
216  unsigned BBIdx = 0;
217  for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) {
218  // We no longer enter through TIBB, now we come in through NewBB.
219  // Revector exactly one entry in the PHI node that used to come from
220  // TIBB to come from NewBB.
221  PHINode *PN = cast<PHINode>(I);
222 
223  // Reuse the previous value of BBIdx if it lines up. In cases where we
224  // have multiple phi nodes with *lots* of predecessors, this is a speed
225  // win because we don't have to scan the PHI looking for TIBB. This
226  // happens because the BB list of PHI nodes are usually in the same
227  // order.
228  if (PN->getIncomingBlock(BBIdx) != TIBB)
229  BBIdx = PN->getBasicBlockIndex(TIBB);
230  PN->setIncomingBlock(BBIdx, NewBB);
231  }
232  }
233 
234  // If there are any other edges from TIBB to DestBB, update those to go
235  // through the split block, making those edges non-critical as well (and
236  // reducing the number of phi entries in the DestBB if relevant).
237  if (Options.MergeIdenticalEdges) {
238  for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) {
239  if (TI->getSuccessor(i) != DestBB) continue;
240 
241  // Remove an entry for TIBB from DestBB phi nodes.
242  DestBB->removePredecessor(TIBB, Options.KeepOneInputPHIs);
243 
244  // We found another edge to DestBB, go to NewBB instead.
245  TI->setSuccessor(i, NewBB);
246  }
247  }
248 
249  // If we have nothing to update, just return.
250  auto *DT = Options.DT;
251  auto *PDT = Options.PDT;
252  auto *MSSAU = Options.MSSAU;
253  if (MSSAU)
255  DestBB, NewBB, {TIBB}, Options.MergeIdenticalEdges);
256 
257  if (!DT && !PDT && !LI)
258  return NewBB;
259 
260  if (DT || PDT) {
261  // Update the DominatorTree.
262  // ---> NewBB -----\
263  // / V
264  // TIBB -------\\------> DestBB
265  //
266  // First, inform the DT about the new path from TIBB to DestBB via NewBB,
267  // then delete the old edge from TIBB to DestBB. By doing this in that order
268  // DestBB stays reachable in the DT the whole time and its subtree doesn't
269  // get disconnected.
271  Updates.push_back({DominatorTree::Insert, TIBB, NewBB});
272  Updates.push_back({DominatorTree::Insert, NewBB, DestBB});
273  if (llvm::find(successors(TIBB), DestBB) == succ_end(TIBB))
274  Updates.push_back({DominatorTree::Delete, TIBB, DestBB});
275 
276  if (DT)
277  DT->applyUpdates(Updates);
278  if (PDT)
279  PDT->applyUpdates(Updates);
280  }
281 
282  // Update LoopInfo if it is around.
283  if (LI) {
284  if (Loop *TIL = LI->getLoopFor(TIBB)) {
285  // If one or the other blocks were not in a loop, the new block is not
286  // either, and thus LI doesn't need to be updated.
287  if (Loop *DestLoop = LI->getLoopFor(DestBB)) {
288  if (TIL == DestLoop) {
289  // Both in the same loop, the NewBB joins loop.
290  DestLoop->addBasicBlockToLoop(NewBB, *LI);
291  } else if (TIL->contains(DestLoop)) {
292  // Edge from an outer loop to an inner loop. Add to the outer loop.
293  TIL->addBasicBlockToLoop(NewBB, *LI);
294  } else if (DestLoop->contains(TIL)) {
295  // Edge from an inner loop to an outer loop. Add to the outer loop.
296  DestLoop->addBasicBlockToLoop(NewBB, *LI);
297  } else {
298  // Edge from two loops with no containment relation. Because these
299  // are natural loops, we know that the destination block must be the
300  // header of its loop (adding a branch into a loop elsewhere would
301  // create an irreducible loop).
302  assert(DestLoop->getHeader() == DestBB &&
303  "Should not create irreducible loops!");
304  if (Loop *P = DestLoop->getParentLoop())
305  P->addBasicBlockToLoop(NewBB, *LI);
306  }
307  }
308 
309  // If TIBB is in a loop and DestBB is outside of that loop, we may need
310  // to update LoopSimplify form and LCSSA form.
311  if (!TIL->contains(DestBB)) {
312  assert(!TIL->contains(NewBB) &&
313  "Split point for loop exit is contained in loop!");
314 
315  // Update LCSSA form in the newly created exit block.
316  if (Options.PreserveLCSSA) {
317  createPHIsForSplitLoopExit(TIBB, NewBB, DestBB);
318  }
319 
320  if (!LoopPreds.empty()) {
321  assert(!DestBB->isEHPad() && "We don't split edges to EH pads!");
322  BasicBlock *NewExitBB = SplitBlockPredecessors(
323  DestBB, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA);
324  if (Options.PreserveLCSSA)
325  createPHIsForSplitLoopExit(LoopPreds, NewExitBB, DestBB);
326  }
327  }
328  }
329  }
330 
331  return NewBB;
332 }
333 
334 // Return the unique indirectbr predecessor of a block. This may return null
335 // even if such a predecessor exists, if it's not useful for splitting.
336 // If a predecessor is found, OtherPreds will contain all other (non-indirectbr)
337 // predecessors of BB.
338 static BasicBlock *
340  // If the block doesn't have any PHIs, we don't care about it, since there's
341  // no point in splitting it.
342  PHINode *PN = dyn_cast<PHINode>(BB->begin());
343  if (!PN)
344  return nullptr;
345 
346  // Verify we have exactly one IBR predecessor.
347  // Conservatively bail out if one of the other predecessors is not a "regular"
348  // terminator (that is, not a switch or a br).
349  BasicBlock *IBB = nullptr;
350  for (unsigned Pred = 0, E = PN->getNumIncomingValues(); Pred != E; ++Pred) {
351  BasicBlock *PredBB = PN->getIncomingBlock(Pred);
352  Instruction *PredTerm = PredBB->getTerminator();
353  switch (PredTerm->getOpcode()) {
354  case Instruction::IndirectBr:
355  if (IBB)
356  return nullptr;
357  IBB = PredBB;
358  break;
359  case Instruction::Br:
360  case Instruction::Switch:
361  OtherPreds.push_back(PredBB);
362  continue;
363  default:
364  return nullptr;
365  }
366  }
367 
368  return IBB;
369 }
370 
374  // Check whether the function has any indirectbrs, and collect which blocks
375  // they may jump to. Since most functions don't have indirect branches,
376  // this lowers the common case's overhead to O(Blocks) instead of O(Edges).
378  for (auto &BB : F) {
379  auto *IBI = dyn_cast<IndirectBrInst>(BB.getTerminator());
380  if (!IBI)
381  continue;
382 
383  for (unsigned Succ = 0, E = IBI->getNumSuccessors(); Succ != E; ++Succ)
384  Targets.insert(IBI->getSuccessor(Succ));
385  }
386 
387  if (Targets.empty())
388  return false;
389 
390  bool ShouldUpdateAnalysis = BPI && BFI;
391  bool Changed = false;
392  for (BasicBlock *Target : Targets) {
394  BasicBlock *IBRPred = findIBRPredecessor(Target, OtherPreds);
395  // If we did not found an indirectbr, or the indirectbr is the only
396  // incoming edge, this isn't the kind of edge we're looking for.
397  if (!IBRPred || OtherPreds.empty())
398  continue;
399 
400  // Don't even think about ehpads/landingpads.
401  Instruction *FirstNonPHI = Target->getFirstNonPHI();
402  if (FirstNonPHI->isEHPad() || Target->isLandingPad())
403  continue;
404 
405  // Remember edge probabilities if needed.
406  SmallVector<BranchProbability, 4> EdgeProbabilities;
407  if (ShouldUpdateAnalysis) {
408  EdgeProbabilities.reserve(Target->getTerminator()->getNumSuccessors());
409  for (unsigned I = 0, E = Target->getTerminator()->getNumSuccessors();
410  I < E; ++I)
411  EdgeProbabilities.emplace_back(BPI->getEdgeProbability(Target, I));
412  BPI->eraseBlock(Target);
413  }
414 
415  BasicBlock *BodyBlock = Target->splitBasicBlock(FirstNonPHI, ".split");
416  if (ShouldUpdateAnalysis) {
417  // Copy the BFI/BPI from Target to BodyBlock.
418  BPI->setEdgeProbability(BodyBlock, EdgeProbabilities);
419  BFI->setBlockFreq(BodyBlock, BFI->getBlockFreq(Target).getFrequency());
420  }
421  // It's possible Target was its own successor through an indirectbr.
422  // In this case, the indirectbr now comes from BodyBlock.
423  if (IBRPred == Target)
424  IBRPred = BodyBlock;
425 
426  // At this point Target only has PHIs, and BodyBlock has the rest of the
427  // block's body. Create a copy of Target that will be used by the "direct"
428  // preds.
429  ValueToValueMapTy VMap;
430  BasicBlock *DirectSucc = CloneBasicBlock(Target, VMap, ".clone", &F);
431 
432  BlockFrequency BlockFreqForDirectSucc;
433  for (BasicBlock *Pred : OtherPreds) {
434  // If the target is a loop to itself, then the terminator of the split
435  // block (BodyBlock) needs to be updated.
436  BasicBlock *Src = Pred != Target ? Pred : BodyBlock;
437  Src->getTerminator()->replaceUsesOfWith(Target, DirectSucc);
438  if (ShouldUpdateAnalysis)
439  BlockFreqForDirectSucc += BFI->getBlockFreq(Src) *
440  BPI->getEdgeProbability(Src, DirectSucc);
441  }
442  if (ShouldUpdateAnalysis) {
443  BFI->setBlockFreq(DirectSucc, BlockFreqForDirectSucc.getFrequency());
444  BlockFrequency NewBlockFreqForTarget =
445  BFI->getBlockFreq(Target) - BlockFreqForDirectSucc;
446  BFI->setBlockFreq(Target, NewBlockFreqForTarget.getFrequency());
447  }
448 
449  // Ok, now fix up the PHIs. We know the two blocks only have PHIs, and that
450  // they are clones, so the number of PHIs are the same.
451  // (a) Remove the edge coming from IBRPred from the "Direct" PHI
452  // (b) Leave that as the only edge in the "Indirect" PHI.
453  // (c) Merge the two in the body block.
454  BasicBlock::iterator Indirect = Target->begin(),
455  End = Target->getFirstNonPHI()->getIterator();
456  BasicBlock::iterator Direct = DirectSucc->begin();
457  BasicBlock::iterator MergeInsert = BodyBlock->getFirstInsertionPt();
458 
459  assert(&*End == Target->getTerminator() &&
460  "Block was expected to only contain PHIs");
461 
462  while (Indirect != End) {
463  PHINode *DirPHI = cast<PHINode>(Direct);
464  PHINode *IndPHI = cast<PHINode>(Indirect);
465 
466  // Now, clean up - the direct block shouldn't get the indirect value,
467  // and vice versa.
468  DirPHI->removeIncomingValue(IBRPred);
469  Direct++;
470 
471  // Advance the pointer here, to avoid invalidation issues when the old
472  // PHI is erased.
473  Indirect++;
474 
475  PHINode *NewIndPHI = PHINode::Create(IndPHI->getType(), 1, "ind", IndPHI);
476  NewIndPHI->addIncoming(IndPHI->getIncomingValueForBlock(IBRPred),
477  IBRPred);
478 
479  // Create a PHI in the body block, to merge the direct and indirect
480  // predecessors.
481  PHINode *MergePHI =
482  PHINode::Create(IndPHI->getType(), 2, "merge", &*MergeInsert);
483  MergePHI->addIncoming(NewIndPHI, Target);
484  MergePHI->addIncoming(DirPHI, DirectSucc);
485 
486  IndPHI->replaceAllUsesWith(MergePHI);
487  IndPHI->eraseFromParent();
488  }
489 
490  Changed = true;
491  }
492 
493  return Changed;
494 }
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:687
LLVM_NODISCARD std::enable_if_t< !is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > dyn_cast(const Y &Val)
Definition: Casting.h:334
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:326
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:826
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:233
F(f)
unsigned SplitAllCriticalEdges(Function &F, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
Loop over all of the edges in the CFG, breaking critical edges as they are found. ...
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.cpp:150
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
void initializeBreakCriticalEdgesPass(PassRegistry &)
void reserve(size_type N)
Definition: SmallVector.h:415
static BasicBlock * findIBRPredecessor(BasicBlock *BB, SmallVectorImpl< BasicBlock *> &OtherPreds)
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:289
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Option class for critical edge splitting.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1208
const Instruction * getFirstNonPHIOrDbgOrLifetime() const
Returns a pointer to the first instruction in this block that is not a PHINode, a debug intrinsic...
Definition: BasicBlock.cpp:228
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:160
BasicBlock * SplitCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
If this edge is a critical edge, insert a new node to split the critical edge.
AnalysisUsage & addPreservedID(const void *ID)
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:105
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:21
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
static bool runOnFunction(Function &F, bool PostInlining)
#define P(N)
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock *> Preds, const char *Suffix, DominatorTree *DT=nullptr, 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...
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:214
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
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:241
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
Conditional or Unconditional Branch instruction.
char & BreakCriticalEdgesID
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:156
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
const Instruction & front() const
Definition: BasicBlock.h:301
Indirect Branch Instruction.
FunctionPass * createBreakCriticalEdgesPass()
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:112
void eraseBlock(const BasicBlock *BB)
Forget analysis results for the given basic block.
Represent the analysis usage information of a pass.
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:1498
constexpr double e
Definition: MathExtras.h:58
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:115
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
self_iterator getIterator()
Definition: ilist_node.h:81
bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
Definition: CFG.cpp:86
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge&#39;s probability, relative to other out-edges of the Src.
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:37
char & LoopSimplifyID
bool isLandingPad() const
Return true if this basic block is a landing pad.
Definition: BasicBlock.cpp:448
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:302
Iterator for intrusive lists based on ilist_node.
void setIncomingBlock(unsigned i, BasicBlock *BB)
bool PreserveLoopSimplify
SplitCriticalEdge is guaranteed to preserve loop-simplify form if LI is provided. ...
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:883
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1511
void wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New, ArrayRef< BasicBlock *> Preds, bool IdenticalEdgesWereMerged=true)
A new empty BasicBlock (New) now branches directly to Old.
void setEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors, BranchProbability Prob)
Set the raw edge probability for the given edge.
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
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...
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Target - Wrapper for Target specific information.
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...
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
Analysis providing branch probability information.
iterator insert(iterator where, pointer New)
Definition: ilist.h:228
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:363
static 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.
bool SplitIndirectBrCriticalEdges(Function &F, BranchProbabilityInfo *BPI=nullptr, BlockFrequencyInfo *BFI=nullptr)
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:516
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:270
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
#define I(x, y, z)
Definition: MD5.cpp:59
#define N
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:788
const BasicBlockListType & getBasicBlockList() const
Get the underlying elements of the Function...
Definition: Function.h:682
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:175
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:345
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:429
LLVM Value Representation.
Definition: Value.h:74
succ_range successors(Instruction *I)
Definition: CFG.h:260
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:630
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:1233
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:262
const BasicBlock * getParent() const
Definition: Instruction.h:94