LLVM  14.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 =
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 
105  const Twine &BBName) {
106  if (!isCriticalEdge(TI, SuccNum, Options.MergeIdenticalEdges))
107  return nullptr;
108 
109  return SplitKnownCriticalEdge(TI, SuccNum, Options, BBName);
110 }
111 
112 BasicBlock *
115  const Twine &BBName) {
116  assert(!isa<IndirectBrInst>(TI) &&
117  "Cannot split critical edge from IndirectBrInst");
118 
119  BasicBlock *TIBB = TI->getParent();
120  BasicBlock *DestBB = TI->getSuccessor(SuccNum);
121 
122  // Splitting the critical edge to a pad block is non-trivial. Don't do
123  // it in this generic function.
124  if (DestBB->isEHPad()) return nullptr;
125 
126  if (Options.IgnoreUnreachableDests &&
127  isa<UnreachableInst>(DestBB->getFirstNonPHIOrDbgOrLifetime()))
128  return nullptr;
129 
130  auto *LI = Options.LI;
132  // Check if extra modifications will be required to preserve loop-simplify
133  // form after splitting. If it would require splitting blocks with IndirectBr
134  // or CallBr terminators, bail out if preserving loop-simplify form is
135  // requested.
136  if (LI) {
137  if (Loop *TIL = LI->getLoopFor(TIBB)) {
138 
139  // The only way that we can break LoopSimplify form by splitting a
140  // critical edge is if after the split there exists some edge from TIL to
141  // DestBB *and* the only edge into DestBB from outside of TIL is that of
142  // NewBB. If the first isn't true, then LoopSimplify still holds, NewBB
143  // is the new exit block and it has no non-loop predecessors. If the
144  // second isn't true, then DestBB was not in LoopSimplify form prior to
145  // the split as it had a non-loop predecessor. In both of these cases,
146  // the predecessor must be directly in TIL, not in a subloop, or again
147  // LoopSimplify doesn't hold.
148  for (BasicBlock *P : predecessors(DestBB)) {
149  if (P == TIBB)
150  continue; // The new block is known.
151  if (LI->getLoopFor(P) != TIL) {
152  // No need to re-simplify, it wasn't to start with.
153  LoopPreds.clear();
154  break;
155  }
156  LoopPreds.push_back(P);
157  }
158  // Loop-simplify form can be preserved, if we can split all in-loop
159  // predecessors.
160  if (any_of(LoopPreds, [](BasicBlock *Pred) {
161  const Instruction *T = Pred->getTerminator();
162  if (const auto *CBR = dyn_cast<CallBrInst>(T))
163  return CBR->getDefaultDest() != Pred;
164  return isa<IndirectBrInst>(T);
165  })) {
166  if (Options.PreserveLoopSimplify)
167  return nullptr;
168  LoopPreds.clear();
169  }
170  }
171  }
172 
173  // Create a new basic block, linking it into the CFG.
174  BasicBlock *NewBB = nullptr;
175  if (BBName.str() != "")
176  NewBB = BasicBlock::Create(TI->getContext(), BBName);
177  else
178  NewBB = BasicBlock::Create(TI->getContext(), TIBB->getName() + "." +
179  DestBB->getName() +
180  "_crit_edge");
181  // Create our unconditional branch.
182  BranchInst *NewBI = BranchInst::Create(DestBB, NewBB);
183  NewBI->setDebugLoc(TI->getDebugLoc());
184 
185  // Insert the block into the function... right after the block TI lives in.
186  Function &F = *TIBB->getParent();
187  Function::iterator FBBI = TIBB->getIterator();
188  F.getBasicBlockList().insert(++FBBI, NewBB);
189 
190  // Branch to the new block, breaking the edge.
191  TI->setSuccessor(SuccNum, NewBB);
192 
193  // If there are any PHI nodes in DestBB, we need to update them so that they
194  // merge incoming values from NewBB instead of from TIBB.
195  {
196  unsigned BBIdx = 0;
197  for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) {
198  // We no longer enter through TIBB, now we come in through NewBB.
199  // Revector exactly one entry in the PHI node that used to come from
200  // TIBB to come from NewBB.
201  PHINode *PN = cast<PHINode>(I);
202 
203  // Reuse the previous value of BBIdx if it lines up. In cases where we
204  // have multiple phi nodes with *lots* of predecessors, this is a speed
205  // win because we don't have to scan the PHI looking for TIBB. This
206  // happens because the BB list of PHI nodes are usually in the same
207  // order.
208  if (PN->getIncomingBlock(BBIdx) != TIBB)
209  BBIdx = PN->getBasicBlockIndex(TIBB);
210  PN->setIncomingBlock(BBIdx, NewBB);
211  }
212  }
213 
214  // If there are any other edges from TIBB to DestBB, update those to go
215  // through the split block, making those edges non-critical as well (and
216  // reducing the number of phi entries in the DestBB if relevant).
217  if (Options.MergeIdenticalEdges) {
218  for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) {
219  if (TI->getSuccessor(i) != DestBB) continue;
220 
221  // Remove an entry for TIBB from DestBB phi nodes.
222  DestBB->removePredecessor(TIBB, Options.KeepOneInputPHIs);
223 
224  // We found another edge to DestBB, go to NewBB instead.
225  TI->setSuccessor(i, NewBB);
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  createPHIsForSplitLoopExit(TIBB, NewBB, DestBB);
298  }
299 
300  if (!LoopPreds.empty()) {
301  assert(!DestBB->isEHPad() && "We don't split edges to EH pads!");
302  BasicBlock *NewExitBB = SplitBlockPredecessors(
303  DestBB, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA);
304  if (Options.PreserveLCSSA)
305  createPHIsForSplitLoopExit(LoopPreds, NewExitBB, DestBB);
306  }
307  }
308  }
309  }
310 
311  return NewBB;
312 }
313 
314 // Return the unique indirectbr predecessor of a block. This may return null
315 // even if such a predecessor exists, if it's not useful for splitting.
316 // If a predecessor is found, OtherPreds will contain all other (non-indirectbr)
317 // predecessors of BB.
318 static BasicBlock *
320  // If the block doesn't have any PHIs, we don't care about it, since there's
321  // no point in splitting it.
322  PHINode *PN = dyn_cast<PHINode>(BB->begin());
323  if (!PN)
324  return nullptr;
325 
326  // Verify we have exactly one IBR predecessor.
327  // Conservatively bail out if one of the other predecessors is not a "regular"
328  // terminator (that is, not a switch or a br).
329  BasicBlock *IBB = nullptr;
330  for (unsigned Pred = 0, E = PN->getNumIncomingValues(); Pred != E; ++Pred) {
331  BasicBlock *PredBB = PN->getIncomingBlock(Pred);
332  Instruction *PredTerm = PredBB->getTerminator();
333  switch (PredTerm->getOpcode()) {
334  case Instruction::IndirectBr:
335  if (IBB)
336  return nullptr;
337  IBB = PredBB;
338  break;
339  case Instruction::Br:
340  case Instruction::Switch:
341  OtherPreds.push_back(PredBB);
342  continue;
343  default:
344  return nullptr;
345  }
346  }
347 
348  return IBB;
349 }
350 
354  // Check whether the function has any indirectbrs, and collect which blocks
355  // they may jump to. Since most functions don't have indirect branches,
356  // this lowers the common case's overhead to O(Blocks) instead of O(Edges).
358  for (auto &BB : F) {
359  auto *IBI = dyn_cast<IndirectBrInst>(BB.getTerminator());
360  if (!IBI)
361  continue;
362 
363  for (unsigned Succ = 0, E = IBI->getNumSuccessors(); Succ != E; ++Succ)
364  Targets.insert(IBI->getSuccessor(Succ));
365  }
366 
367  if (Targets.empty())
368  return false;
369 
370  bool ShouldUpdateAnalysis = BPI && BFI;
371  bool Changed = false;
372  for (BasicBlock *Target : Targets) {
374  BasicBlock *IBRPred = findIBRPredecessor(Target, OtherPreds);
375  // If we did not found an indirectbr, or the indirectbr is the only
376  // incoming edge, this isn't the kind of edge we're looking for.
377  if (!IBRPred || OtherPreds.empty())
378  continue;
379 
380  // Don't even think about ehpads/landingpads.
381  Instruction *FirstNonPHI = Target->getFirstNonPHI();
382  if (FirstNonPHI->isEHPad() || Target->isLandingPad())
383  continue;
384 
385  // Remember edge probabilities if needed.
386  SmallVector<BranchProbability, 4> EdgeProbabilities;
387  if (ShouldUpdateAnalysis) {
388  EdgeProbabilities.reserve(Target->getTerminator()->getNumSuccessors());
389  for (unsigned I = 0, E = Target->getTerminator()->getNumSuccessors();
390  I < E; ++I)
391  EdgeProbabilities.emplace_back(BPI->getEdgeProbability(Target, I));
392  BPI->eraseBlock(Target);
393  }
394 
395  BasicBlock *BodyBlock = Target->splitBasicBlock(FirstNonPHI, ".split");
396  if (ShouldUpdateAnalysis) {
397  // Copy the BFI/BPI from Target to BodyBlock.
398  BPI->setEdgeProbability(BodyBlock, EdgeProbabilities);
399  BFI->setBlockFreq(BodyBlock, BFI->getBlockFreq(Target).getFrequency());
400  }
401  // It's possible Target was its own successor through an indirectbr.
402  // In this case, the indirectbr now comes from BodyBlock.
403  if (IBRPred == Target)
404  IBRPred = BodyBlock;
405 
406  // At this point Target only has PHIs, and BodyBlock has the rest of the
407  // block's body. Create a copy of Target that will be used by the "direct"
408  // preds.
409  ValueToValueMapTy VMap;
410  BasicBlock *DirectSucc = CloneBasicBlock(Target, VMap, ".clone", &F);
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.getFrequency());
424  BlockFrequency NewBlockFreqForTarget =
425  BFI->getBlockFreq(Target) - BlockFreqForDirectSucc;
426  BFI->setBlockFreq(Target, NewBlockFreqForTarget.getFrequency());
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->getFirstNonPHI()->getIterator();
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 
446  // Now, clean up - the direct block shouldn't get the indirect value,
447  // and vice versa.
448  DirPHI->removeIncomingValue(IBRPred);
449  Direct++;
450 
451  // Advance the pointer here, to avoid invalidation issues when the old
452  // PHI is erased.
453  Indirect++;
454 
455  PHINode *NewIndPHI = PHINode::Create(IndPHI->getType(), 1, "ind", IndPHI);
456  NewIndPHI->addIncoming(IndPHI->getIncomingValueForBlock(IBRPred),
457  IBRPred);
458 
459  // Create a PHI in the body block, to merge the direct and indirect
460  // predecessors.
461  PHINode *MergePHI =
462  PHINode::Create(IndPHI->getType(), 2, "merge", &*MergeInsert);
463  MergePHI->addIncoming(NewIndPHI, Target);
464  MergePHI->addIncoming(DirPHI, DirectSucc);
465 
466  IndPHI->replaceAllUsesWith(MergePHI);
467  IndPHI->eraseFromParent();
468  }
469 
470  Changed = true;
471  }
472 
473  return Changed;
474 }
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::predecessors
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:127
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
ValueMapper.h
llvm::createBreakCriticalEdgesPass
FunctionPass * createBreakCriticalEdgesPass()
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
BreakCriticalEdges.h
MemorySSAUpdater.h
llvm::Function
Definition: Function.h:61
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::Target
Target - Wrapper for Target specific information.
Definition: TargetRegistry.h:137
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
ErrorHandling.h
llvm::PHINode::removeIncomingValue
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
Definition: Instructions.cpp:113
llvm::createPHIsForSplitLoopExit
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.
Definition: BasicBlockUtils.cpp:712
llvm::SplitCriticalEdge
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.
Definition: BreakCriticalEdges.cpp:103
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1268
llvm::DominatorTreeBase< BasicBlock, false >::Insert
static constexpr UpdateKind Insert
Definition: GenericDomTree.h:242
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::isCriticalEdge
bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
Definition: CFG.cpp:95
llvm::BreakCriticalEdgesPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: BreakCriticalEdges.cpp:85
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:262
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::Instruction::getNumSuccessors
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Definition: Instruction.cpp:765
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:160
llvm::BlockFrequencyInfo
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Definition: BlockFrequencyInfo.h:37
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
PostDominators.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::SplitKnownCriticalEdge
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,...
Definition: BreakCriticalEdges.cpp:113
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
llvm::BranchProbabilityInfo
Analysis providing branch probability information.
Definition: BranchProbabilityInfo.h:115
INITIALIZE_PASS
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:37
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::CriticalEdgeSplittingOptions
Option class for critical edge splitting.
Definition: BasicBlockUtils.h:136
llvm::BasicBlock::getFirstInsertionPt
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:249
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2810
llvm::Instruction
Definition: Instruction.h:45
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
Options
const char LLVMTargetMachineRef LLVMPassBuilderOptionsRef Options
Definition: PassBuilderBindings.cpp:48
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:777
llvm::SplitBlockPredecessors
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...
Definition: BasicBlockUtils.cpp:1148
Utils.h
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::empty
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2717
Type.h
CFG.h
LoopInfo.h
llvm::Twine::str
std::string str() const
Return the twine contents as a std::string.
Definition: Twine.cpp:17
llvm::CloneBasicBlock
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...
Definition: CloneFunction.cpp:43
llvm::BlockFrequency
Definition: BlockFrequency.h:24
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
BranchProbabilityInfo.h
llvm::PHINode::setIncomingBlock
void setIncomingBlock(unsigned i, BasicBlock *BB)
Definition: Instructions.h:2760
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:176
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2775
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3116
I
#define I(x, y, z)
Definition: MD5.cpp:59
Cloning.h
llvm::SplitIndirectBrCriticalEdges
bool SplitIndirectBrCriticalEdges(Function &F, BranchProbabilityInfo *BPI=nullptr, BlockFrequencyInfo *BFI=nullptr)
Definition: BreakCriticalEdges.cpp:351
llvm::BlockFrequency::getFrequency
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
Definition: BlockFrequency.h:35
llvm::PHINode::getBasicBlockIndex
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
Definition: Instructions.h:2803
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1612
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:367
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::BranchProbabilityInfo::eraseBlock
void eraseBlock(const BasicBlock *BB)
Forget analysis results for the given basic block.
Definition: BranchProbabilityInfo.cpp:1208
llvm::BasicBlock::getFirstNonPHIOrDbgOrLifetime
const Instruction * getFirstNonPHIOrDbgOrLifetime(bool SkipPseudoOp=false) const
Returns a pointer to the first instruction in this block that is not a PHINode, a debug intrinsic,...
Definition: BasicBlock.cpp:233
llvm::BranchProbabilityInfo::getEdgeProbability
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge's probability, relative to other out-edges of the Src.
Definition: BranchProbabilityInfo.cpp:1113
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
CFG.h
llvm::BranchProbabilityInfo::setEdgeProbability
void setEdgeProbability(const BasicBlock *Src, const SmallVectorImpl< BranchProbability > &Probs)
Set the raw probabilities for all edges from the given block.
Definition: BranchProbabilityInfo.cpp:1150
llvm::any_of
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:1554
llvm::Instruction::setSuccessor
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
Definition: Instruction.cpp:789
llvm::AnalysisUsage::addPreservedID
AnalysisUsage & addPreservedID(const void *ID)
Definition: PassAnalysisSupport.h:88
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:520
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:978
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
BlockFrequencyInfo.h
llvm::AMDGPUISD::BFI
@ BFI
Definition: AMDGPUISelLowering.h:421
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:297
llvm::ValueMap< const Value *, WeakTrackingVH >
llvm::BasicBlock::getTerminator
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:148
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:83
llvm::LoopSimplifyID
char & LoopSimplifyID
Definition: LoopSimplify.cpp:800
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::PHINode::Create
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...
Definition: Instructions.h:2667
llvm::AnalysisManager::getCachedResult
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:804
llvm::Instruction::isEHPad
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:661
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::BreakCriticalEdgesID
char & BreakCriticalEdgesID
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
llvm::SplitAllCriticalEdges
unsigned SplitAllCriticalEdges(Function &F, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
Loop over all of the edges in the CFG, breaking critical edges as they are found.
Definition: BasicBlockUtils.cpp:744
findIBRPredecessor
static BasicBlock * findIBRPredecessor(BasicBlock *BB, SmallVectorImpl< BasicBlock * > &OtherPreds)
Definition: BreakCriticalEdges.cpp:319
Instructions.h
SmallVector.h
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:370
Dominators.h
N
#define N
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2741
llvm::PHINode
Definition: Instructions.h:2625
llvm::BasicBlock::removePredecessor
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:321
llvm::SmallVectorImpl< BasicBlock * >
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3060
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:624
BasicBlockUtils.h
llvm::initializeBreakCriticalEdgesPass
void initializeBreakCriticalEdgesPass(PassRegistry &)
InitializePasses.h
llvm::BasicBlock::isEHPad
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:465
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1243
SetVector.h
llvm::DominatorTreeBase< BasicBlock, false >::Delete
static constexpr UpdateKind Delete
Definition: GenericDomTree.h:243
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:908
llvm::Function::iterator
BasicBlockListType::iterator iterator
Definition: Function.h:67
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37