LLVM  15.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/InitializePasses.h"
31 #include "llvm/Transforms/Utils.h"
35 using namespace llvm;
36 
37 #define DEBUG_TYPE "break-crit-edges"
38 
39 STATISTIC(NumBroken, "Number of blocks inserted");
40 
41 namespace {
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 
73 char BreakCriticalEdges::ID = 0;
74 INITIALIZE_PASS(BreakCriticalEdges, "break-crit-edges",
75  "Break critical edges in CFG", false, false)
76 
77 // Publicly exposed interface to pass...
78 char &llvm::BreakCriticalEdgesID = BreakCriticalEdges::ID;
80  return new BreakCriticalEdges();
81 }
82 
85  auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F);
86  auto *LI = AM.getCachedResult<LoopAnalysis>(F);
88  NumBroken += N;
89  if (N == 0)
90  return PreservedAnalyses::all();
93  PA.preserve<LoopAnalysis>();
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 
110 BasicBlock *
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  // or CallBr terminators, bail out if preserving loop-simplify form is
133  // requested.
134  if (LI) {
135  if (Loop *TIL = LI->getLoopFor(TIBB)) {
136 
137  // The only way that we can break LoopSimplify form by splitting a
138  // critical edge is if after the split there exists some edge from TIL to
139  // DestBB *and* the only edge into DestBB from outside of TIL is that of
140  // NewBB. If the first isn't true, then LoopSimplify still holds, NewBB
141  // is the new exit block and it has no non-loop predecessors. If the
142  // second isn't true, then DestBB was not in LoopSimplify form prior to
143  // the split as it had a non-loop predecessor. In both of these cases,
144  // the predecessor must be directly in TIL, not in a subloop, or again
145  // LoopSimplify doesn't hold.
146  for (BasicBlock *P : predecessors(DestBB)) {
147  if (P == TIBB)
148  continue; // The new block is known.
149  if (LI->getLoopFor(P) != TIL) {
150  // No need to re-simplify, it wasn't to start with.
151  LoopPreds.clear();
152  break;
153  }
154  LoopPreds.push_back(P);
155  }
156  // Loop-simplify form can be preserved, if we can split all in-loop
157  // predecessors.
158  if (any_of(LoopPreds, [](BasicBlock *Pred) {
159  const Instruction *T = Pred->getTerminator();
160  if (const auto *CBR = dyn_cast<CallBrInst>(T))
161  return CBR->getDefaultDest() != Pred;
162  return isa<IndirectBrInst>(T);
163  })) {
164  if (Options.PreserveLoopSimplify)
165  return nullptr;
166  LoopPreds.clear();
167  }
168  }
169  }
170 
171  // Create a new basic block, linking it into the CFG.
172  BasicBlock *NewBB = nullptr;
173  if (BBName.str() != "")
174  NewBB = BasicBlock::Create(TI->getContext(), BBName);
175  else
176  NewBB = BasicBlock::Create(TI->getContext(), TIBB->getName() + "." +
177  DestBB->getName() +
178  "_crit_edge");
179  // Create our unconditional branch.
180  BranchInst *NewBI = BranchInst::Create(DestBB, NewBB);
181  NewBI->setDebugLoc(TI->getDebugLoc());
182 
183  // Insert the block into the function... right after the block TI lives in.
184  Function &F = *TIBB->getParent();
185  Function::iterator FBBI = TIBB->getIterator();
186  F.getBasicBlockList().insert(++FBBI, NewBB);
187 
188  // Branch to the new block, breaking the edge.
189  TI->setSuccessor(SuccNum, NewBB);
190 
191  // If there are any PHI nodes in DestBB, we need to update them so that they
192  // merge incoming values from NewBB instead of from TIBB.
193  {
194  unsigned BBIdx = 0;
195  for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) {
196  // We no longer enter through TIBB, now we come in through NewBB.
197  // Revector exactly one entry in the PHI node that used to come from
198  // TIBB to come from NewBB.
199  PHINode *PN = cast<PHINode>(I);
200 
201  // Reuse the previous value of BBIdx if it lines up. In cases where we
202  // have multiple phi nodes with *lots* of predecessors, this is a speed
203  // win because we don't have to scan the PHI looking for TIBB. This
204  // happens because the BB list of PHI nodes are usually in the same
205  // order.
206  if (PN->getIncomingBlock(BBIdx) != TIBB)
207  BBIdx = PN->getBasicBlockIndex(TIBB);
208  PN->setIncomingBlock(BBIdx, NewBB);
209  }
210  }
211 
212  // If there are any other edges from TIBB to DestBB, update those to go
213  // through the split block, making those edges non-critical as well (and
214  // reducing the number of phi entries in the DestBB if relevant).
215  if (Options.MergeIdenticalEdges) {
216  for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) {
217  if (TI->getSuccessor(i) != DestBB) continue;
218 
219  // Remove an entry for TIBB from DestBB phi nodes.
220  DestBB->removePredecessor(TIBB, Options.KeepOneInputPHIs);
221 
222  // We found another edge to DestBB, go to NewBB instead.
223  TI->setSuccessor(i, NewBB);
224  }
225  }
226 
227  // If we have nothing to update, just return.
228  auto *DT = Options.DT;
229  auto *PDT = Options.PDT;
230  auto *MSSAU = Options.MSSAU;
231  if (MSSAU)
232  MSSAU->wireOldPredecessorsToNewImmediatePredecessor(
233  DestBB, NewBB, {TIBB}, Options.MergeIdenticalEdges);
234 
235  if (!DT && !PDT && !LI)
236  return NewBB;
237 
238  if (DT || PDT) {
239  // Update the DominatorTree.
240  // ---> NewBB -----\
241  // / V
242  // TIBB -------\\------> DestBB
243  //
244  // First, inform the DT about the new path from TIBB to DestBB via NewBB,
245  // then delete the old edge from TIBB to DestBB. By doing this in that order
246  // DestBB stays reachable in the DT the whole time and its subtree doesn't
247  // get disconnected.
249  Updates.push_back({DominatorTree::Insert, TIBB, NewBB});
250  Updates.push_back({DominatorTree::Insert, NewBB, DestBB});
251  if (!llvm::is_contained(successors(TIBB), DestBB))
252  Updates.push_back({DominatorTree::Delete, TIBB, DestBB});
253 
254  if (DT)
255  DT->applyUpdates(Updates);
256  if (PDT)
257  PDT->applyUpdates(Updates);
258  }
259 
260  // Update LoopInfo if it is around.
261  if (LI) {
262  if (Loop *TIL = LI->getLoopFor(TIBB)) {
263  // If one or the other blocks were not in a loop, the new block is not
264  // either, and thus LI doesn't need to be updated.
265  if (Loop *DestLoop = LI->getLoopFor(DestBB)) {
266  if (TIL == DestLoop) {
267  // Both in the same loop, the NewBB joins loop.
268  DestLoop->addBasicBlockToLoop(NewBB, *LI);
269  } else if (TIL->contains(DestLoop)) {
270  // Edge from an outer loop to an inner loop. Add to the outer loop.
271  TIL->addBasicBlockToLoop(NewBB, *LI);
272  } else if (DestLoop->contains(TIL)) {
273  // Edge from an inner loop to an outer loop. Add to the outer loop.
274  DestLoop->addBasicBlockToLoop(NewBB, *LI);
275  } else {
276  // Edge from two loops with no containment relation. Because these
277  // are natural loops, we know that the destination block must be the
278  // header of its loop (adding a branch into a loop elsewhere would
279  // create an irreducible loop).
280  assert(DestLoop->getHeader() == DestBB &&
281  "Should not create irreducible loops!");
282  if (Loop *P = DestLoop->getParentLoop())
283  P->addBasicBlockToLoop(NewBB, *LI);
284  }
285  }
286 
287  // If TIBB is in a loop and DestBB is outside of that loop, we may need
288  // to update LoopSimplify form and LCSSA form.
289  if (!TIL->contains(DestBB)) {
290  assert(!TIL->contains(NewBB) &&
291  "Split point for loop exit is contained in loop!");
292 
293  // Update LCSSA form in the newly created exit block.
294  if (Options.PreserveLCSSA) {
295  createPHIsForSplitLoopExit(TIBB, NewBB, DestBB);
296  }
297 
298  if (!LoopPreds.empty()) {
299  assert(!DestBB->isEHPad() && "We don't split edges to EH pads!");
300  BasicBlock *NewExitBB = SplitBlockPredecessors(
301  DestBB, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA);
302  if (Options.PreserveLCSSA)
303  createPHIsForSplitLoopExit(LoopPreds, NewExitBB, DestBB);
304  }
305  }
306  }
307  }
308 
309  return NewBB;
310 }
311 
312 // Return the unique indirectbr predecessor of a block. This may return null
313 // even if such a predecessor exists, if it's not useful for splitting.
314 // If a predecessor is found, OtherPreds will contain all other (non-indirectbr)
315 // predecessors of BB.
316 static BasicBlock *
318  // Verify we have exactly one IBR predecessor.
319  // Conservatively bail out if one of the other predecessors is not a "regular"
320  // terminator (that is, not a switch or a br).
321  BasicBlock *IBB = nullptr;
322  for (BasicBlock *PredBB : predecessors(BB)) {
323  Instruction *PredTerm = PredBB->getTerminator();
324  switch (PredTerm->getOpcode()) {
325  case Instruction::IndirectBr:
326  if (IBB)
327  return nullptr;
328  IBB = PredBB;
329  break;
330  case Instruction::Br:
331  case Instruction::Switch:
332  OtherPreds.push_back(PredBB);
333  continue;
334  default:
335  return nullptr;
336  }
337  }
338 
339  return IBB;
340 }
341 
343  bool IgnoreBlocksWithoutPHI,
346  // Check whether the function has any indirectbrs, and collect which blocks
347  // they may jump to. Since most functions don't have indirect branches,
348  // this lowers the common case's overhead to O(Blocks) instead of O(Edges).
350  for (auto &BB : F) {
351  auto *IBI = dyn_cast<IndirectBrInst>(BB.getTerminator());
352  if (!IBI)
353  continue;
354 
355  for (unsigned Succ = 0, E = IBI->getNumSuccessors(); Succ != E; ++Succ)
356  Targets.insert(IBI->getSuccessor(Succ));
357  }
358 
359  if (Targets.empty())
360  return false;
361 
362  bool ShouldUpdateAnalysis = BPI && BFI;
363  bool Changed = false;
364  for (BasicBlock *Target : Targets) {
365  if (IgnoreBlocksWithoutPHI && Target->phis().empty())
366  continue;
367 
369  BasicBlock *IBRPred = findIBRPredecessor(Target, OtherPreds);
370  // If we did not found an indirectbr, or the indirectbr is the only
371  // incoming edge, this isn't the kind of edge we're looking for.
372  if (!IBRPred || OtherPreds.empty())
373  continue;
374 
375  // Don't even think about ehpads/landingpads.
376  Instruction *FirstNonPHI = Target->getFirstNonPHI();
377  if (FirstNonPHI->isEHPad() || Target->isLandingPad())
378  continue;
379 
380  // Remember edge probabilities if needed.
381  SmallVector<BranchProbability, 4> EdgeProbabilities;
382  if (ShouldUpdateAnalysis) {
383  EdgeProbabilities.reserve(Target->getTerminator()->getNumSuccessors());
384  for (unsigned I = 0, E = Target->getTerminator()->getNumSuccessors();
385  I < E; ++I)
386  EdgeProbabilities.emplace_back(BPI->getEdgeProbability(Target, I));
387  BPI->eraseBlock(Target);
388  }
389 
390  BasicBlock *BodyBlock = Target->splitBasicBlock(FirstNonPHI, ".split");
391  if (ShouldUpdateAnalysis) {
392  // Copy the BFI/BPI from Target to BodyBlock.
393  BPI->setEdgeProbability(BodyBlock, EdgeProbabilities);
394  BFI->setBlockFreq(BodyBlock, BFI->getBlockFreq(Target).getFrequency());
395  }
396  // It's possible Target was its own successor through an indirectbr.
397  // In this case, the indirectbr now comes from BodyBlock.
398  if (IBRPred == Target)
399  IBRPred = BodyBlock;
400 
401  // At this point Target only has PHIs, and BodyBlock has the rest of the
402  // block's body. Create a copy of Target that will be used by the "direct"
403  // preds.
404  ValueToValueMapTy VMap;
405  BasicBlock *DirectSucc = CloneBasicBlock(Target, VMap, ".clone", &F);
406 
407  BlockFrequency BlockFreqForDirectSucc;
408  for (BasicBlock *Pred : OtherPreds) {
409  // If the target is a loop to itself, then the terminator of the split
410  // block (BodyBlock) needs to be updated.
411  BasicBlock *Src = Pred != Target ? Pred : BodyBlock;
412  Src->getTerminator()->replaceUsesOfWith(Target, DirectSucc);
413  if (ShouldUpdateAnalysis)
414  BlockFreqForDirectSucc += BFI->getBlockFreq(Src) *
415  BPI->getEdgeProbability(Src, DirectSucc);
416  }
417  if (ShouldUpdateAnalysis) {
418  BFI->setBlockFreq(DirectSucc, BlockFreqForDirectSucc.getFrequency());
419  BlockFrequency NewBlockFreqForTarget =
420  BFI->getBlockFreq(Target) - BlockFreqForDirectSucc;
421  BFI->setBlockFreq(Target, NewBlockFreqForTarget.getFrequency());
422  }
423 
424  // Ok, now fix up the PHIs. We know the two blocks only have PHIs, and that
425  // they are clones, so the number of PHIs are the same.
426  // (a) Remove the edge coming from IBRPred from the "Direct" PHI
427  // (b) Leave that as the only edge in the "Indirect" PHI.
428  // (c) Merge the two in the body block.
429  BasicBlock::iterator Indirect = Target->begin(),
430  End = Target->getFirstNonPHI()->getIterator();
431  BasicBlock::iterator Direct = DirectSucc->begin();
432  BasicBlock::iterator MergeInsert = BodyBlock->getFirstInsertionPt();
433 
434  assert(&*End == Target->getTerminator() &&
435  "Block was expected to only contain PHIs");
436 
437  while (Indirect != End) {
438  PHINode *DirPHI = cast<PHINode>(Direct);
439  PHINode *IndPHI = cast<PHINode>(Indirect);
440 
441  // Now, clean up - the direct block shouldn't get the indirect value,
442  // and vice versa.
443  DirPHI->removeIncomingValue(IBRPred);
444  Direct++;
445 
446  // Advance the pointer here, to avoid invalidation issues when the old
447  // PHI is erased.
448  Indirect++;
449 
450  PHINode *NewIndPHI = PHINode::Create(IndPHI->getType(), 1, "ind", IndPHI);
451  NewIndPHI->addIncoming(IndPHI->getIncomingValueForBlock(IBRPred),
452  IBRPred);
453 
454  // Create a PHI in the body block, to merge the direct and indirect
455  // predecessors.
456  PHINode *MergePHI =
457  PHINode::Create(IndPHI->getType(), 2, "merge", &*MergeInsert);
458  MergePHI->addIncoming(NewIndPHI, Target);
459  MergePHI->addIncoming(DirPHI, DirectSucc);
460 
461  IndPHI->replaceAllUsesWith(MergePHI);
462  IndPHI->eraseFromParent();
463  }
464 
465  Changed = true;
466  }
467 
468  return Changed;
469 }
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:152
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
ValueMapper.h
llvm::createBreakCriticalEdgesPass
FunctionPass * createBreakCriticalEdgesPass()
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
BreakCriticalEdges.h
T
MemorySSAUpdater.h
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
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:145
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
Statistic.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:735
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:101
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1287
llvm::DominatorTreeBase< BasicBlock, false >::Insert
static constexpr UpdateKind Insert
Definition: GenericDomTree.h:242
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
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:83
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::Instruction::getNumSuccessors
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Definition: Instruction.cpp:777
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:157
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:111
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:297
llvm::BranchProbabilityInfo
Analysis providing branch probability information.
Definition: BranchProbabilityInfo.h:113
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:142
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:246
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2836
llvm::Instruction
Definition: Instruction.h:42
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
Options
const char LLVMTargetMachineRef LLVMPassBuilderOptionsRef Options
Definition: PassBuilderBindings.cpp:48
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
llvm::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:789
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:1176
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::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
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:41
llvm::BlockFrequency
Definition: BlockFrequency.h:23
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:77
BranchProbabilityInfo.h
llvm::PHINode::setIncomingBlock
void setIncomingBlock(unsigned i, BasicBlock *BB)
Definition: Instructions.h:2786
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2801
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3142
I
#define I(x, y, z)
Definition: MD5.cpp:58
Cloning.h
llvm::BlockFrequency::getFrequency
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
Definition: BlockFrequency.h:34
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:2829
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:1682
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:364
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::SplitIndirectBrCriticalEdges
bool SplitIndirectBrCriticalEdges(Function &F, bool IgnoreBlocksWithoutPHI, BranchProbabilityInfo *BPI=nullptr, BlockFrequencyInfo *BFI=nullptr)
Definition: BreakCriticalEdges.cpp:342
llvm::BranchProbabilityInfo::eraseBlock
void eraseBlock(const BasicBlock *BB)
Forget analysis results for the given basic block.
Definition: BranchProbabilityInfo.cpp:1199
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:1104
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:1141
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:1624
llvm::Instruction::setSuccessor
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
Definition: Instruction.cpp:801
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:255
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:529
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:97
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:991
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
BlockFrequencyInfo.h
llvm::AMDGPUISD::BFI
@ BFI
Definition: AMDGPUISelLowering.h:429
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:305
llvm::ValueMap< const Value *, WeakTrackingVH >
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:794
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
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:2693
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:799
llvm::Instruction::isEHPad
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:662
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
llvm::BreakCriticalEdgesID
char & BreakCriticalEdgesID
llvm::BasicBlock::getFirstNonPHIOrDbgOrLifetime
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:230
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
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:767
findIBRPredecessor
static BasicBlock * findIBRPredecessor(BasicBlock *BB, SmallVectorImpl< BasicBlock * > &OtherPreds)
Definition: BreakCriticalEdges.cpp:317
Instructions.h
SmallVector.h
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:367
Dominators.h
N
#define N
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2767
llvm::PHINode
Definition: Instructions.h:2651
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.h:119
llvm::BasicBlock::removePredecessor
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:318
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:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
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:3086
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:644
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:466
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1262
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:927
llvm::Function::iterator
BasicBlockListType::iterator iterator
Definition: Function.h:66
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38