LLVM  16.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  // terminators, bail out if preserving loop-simplify form is requested.
133  if (LI) {
134  if (Loop *TIL = LI->getLoopFor(TIBB)) {
135 
136  // The only way that we can break LoopSimplify form by splitting a
137  // critical edge is if after the split there exists some edge from TIL to
138  // DestBB *and* the only edge into DestBB from outside of TIL is that of
139  // NewBB. If the first isn't true, then LoopSimplify still holds, NewBB
140  // is the new exit block and it has no non-loop predecessors. If the
141  // second isn't true, then DestBB was not in LoopSimplify form prior to
142  // the split as it had a non-loop predecessor. In both of these cases,
143  // the predecessor must be directly in TIL, not in a subloop, or again
144  // LoopSimplify doesn't hold.
145  for (BasicBlock *P : predecessors(DestBB)) {
146  if (P == TIBB)
147  continue; // The new block is known.
148  if (LI->getLoopFor(P) != TIL) {
149  // No need to re-simplify, it wasn't to start with.
150  LoopPreds.clear();
151  break;
152  }
153  LoopPreds.push_back(P);
154  }
155  // Loop-simplify form can be preserved, if we can split all in-loop
156  // predecessors.
157  if (any_of(LoopPreds, [](BasicBlock *Pred) {
158  return isa<IndirectBrInst>(Pred->getTerminator());
159  })) {
160  if (Options.PreserveLoopSimplify)
161  return nullptr;
162  LoopPreds.clear();
163  }
164  }
165  }
166 
167  // Create a new basic block, linking it into the CFG.
168  BasicBlock *NewBB = nullptr;
169  if (BBName.str() != "")
170  NewBB = BasicBlock::Create(TI->getContext(), BBName);
171  else
172  NewBB = BasicBlock::Create(TI->getContext(), TIBB->getName() + "." +
173  DestBB->getName() +
174  "_crit_edge");
175  // Create our unconditional branch.
176  BranchInst *NewBI = BranchInst::Create(DestBB, NewBB);
177  NewBI->setDebugLoc(TI->getDebugLoc());
178 
179  // Insert the block into the function... right after the block TI lives in.
180  Function &F = *TIBB->getParent();
181  Function::iterator FBBI = TIBB->getIterator();
182  F.getBasicBlockList().insert(++FBBI, NewBB);
183 
184  // Branch to the new block, breaking the edge.
185  TI->setSuccessor(SuccNum, NewBB);
186 
187  // If there are any PHI nodes in DestBB, we need to update them so that they
188  // merge incoming values from NewBB instead of from TIBB.
189  {
190  unsigned BBIdx = 0;
191  for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) {
192  // We no longer enter through TIBB, now we come in through NewBB.
193  // Revector exactly one entry in the PHI node that used to come from
194  // TIBB to come from NewBB.
195  PHINode *PN = cast<PHINode>(I);
196 
197  // Reuse the previous value of BBIdx if it lines up. In cases where we
198  // have multiple phi nodes with *lots* of predecessors, this is a speed
199  // win because we don't have to scan the PHI looking for TIBB. This
200  // happens because the BB list of PHI nodes are usually in the same
201  // order.
202  if (PN->getIncomingBlock(BBIdx) != TIBB)
203  BBIdx = PN->getBasicBlockIndex(TIBB);
204  PN->setIncomingBlock(BBIdx, NewBB);
205  }
206  }
207 
208  // If there are any other edges from TIBB to DestBB, update those to go
209  // through the split block, making those edges non-critical as well (and
210  // reducing the number of phi entries in the DestBB if relevant).
211  if (Options.MergeIdenticalEdges) {
212  for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) {
213  if (TI->getSuccessor(i) != DestBB) continue;
214 
215  // Remove an entry for TIBB from DestBB phi nodes.
216  DestBB->removePredecessor(TIBB, Options.KeepOneInputPHIs);
217 
218  // We found another edge to DestBB, go to NewBB instead.
219  TI->setSuccessor(i, NewBB);
220  }
221  }
222 
223  // If we have nothing to update, just return.
224  auto *DT = Options.DT;
225  auto *PDT = Options.PDT;
226  auto *MSSAU = Options.MSSAU;
227  if (MSSAU)
228  MSSAU->wireOldPredecessorsToNewImmediatePredecessor(
229  DestBB, NewBB, {TIBB}, Options.MergeIdenticalEdges);
230 
231  if (!DT && !PDT && !LI)
232  return NewBB;
233 
234  if (DT || PDT) {
235  // Update the DominatorTree.
236  // ---> NewBB -----\
237  // / V
238  // TIBB -------\\------> DestBB
239  //
240  // First, inform the DT about the new path from TIBB to DestBB via NewBB,
241  // then delete the old edge from TIBB to DestBB. By doing this in that order
242  // DestBB stays reachable in the DT the whole time and its subtree doesn't
243  // get disconnected.
245  Updates.push_back({DominatorTree::Insert, TIBB, NewBB});
246  Updates.push_back({DominatorTree::Insert, NewBB, DestBB});
247  if (!llvm::is_contained(successors(TIBB), DestBB))
248  Updates.push_back({DominatorTree::Delete, TIBB, DestBB});
249 
250  if (DT)
251  DT->applyUpdates(Updates);
252  if (PDT)
253  PDT->applyUpdates(Updates);
254  }
255 
256  // Update LoopInfo if it is around.
257  if (LI) {
258  if (Loop *TIL = LI->getLoopFor(TIBB)) {
259  // If one or the other blocks were not in a loop, the new block is not
260  // either, and thus LI doesn't need to be updated.
261  if (Loop *DestLoop = LI->getLoopFor(DestBB)) {
262  if (TIL == DestLoop) {
263  // Both in the same loop, the NewBB joins loop.
264  DestLoop->addBasicBlockToLoop(NewBB, *LI);
265  } else if (TIL->contains(DestLoop)) {
266  // Edge from an outer loop to an inner loop. Add to the outer loop.
267  TIL->addBasicBlockToLoop(NewBB, *LI);
268  } else if (DestLoop->contains(TIL)) {
269  // Edge from an inner loop to an outer loop. Add to the outer loop.
270  DestLoop->addBasicBlockToLoop(NewBB, *LI);
271  } else {
272  // Edge from two loops with no containment relation. Because these
273  // are natural loops, we know that the destination block must be the
274  // header of its loop (adding a branch into a loop elsewhere would
275  // create an irreducible loop).
276  assert(DestLoop->getHeader() == DestBB &&
277  "Should not create irreducible loops!");
278  if (Loop *P = DestLoop->getParentLoop())
279  P->addBasicBlockToLoop(NewBB, *LI);
280  }
281  }
282 
283  // If TIBB is in a loop and DestBB is outside of that loop, we may need
284  // to update LoopSimplify form and LCSSA form.
285  if (!TIL->contains(DestBB)) {
286  assert(!TIL->contains(NewBB) &&
287  "Split point for loop exit is contained in loop!");
288 
289  // Update LCSSA form in the newly created exit block.
290  if (Options.PreserveLCSSA) {
291  createPHIsForSplitLoopExit(TIBB, NewBB, DestBB);
292  }
293 
294  if (!LoopPreds.empty()) {
295  assert(!DestBB->isEHPad() && "We don't split edges to EH pads!");
296  BasicBlock *NewExitBB = SplitBlockPredecessors(
297  DestBB, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA);
298  if (Options.PreserveLCSSA)
299  createPHIsForSplitLoopExit(LoopPreds, NewExitBB, DestBB);
300  }
301  }
302  }
303  }
304 
305  return NewBB;
306 }
307 
308 // Return the unique indirectbr predecessor of a block. This may return null
309 // even if such a predecessor exists, if it's not useful for splitting.
310 // If a predecessor is found, OtherPreds will contain all other (non-indirectbr)
311 // predecessors of BB.
312 static BasicBlock *
314  // Verify we have exactly one IBR predecessor.
315  // Conservatively bail out if one of the other predecessors is not a "regular"
316  // terminator (that is, not a switch or a br).
317  BasicBlock *IBB = nullptr;
318  for (BasicBlock *PredBB : predecessors(BB)) {
319  Instruction *PredTerm = PredBB->getTerminator();
320  switch (PredTerm->getOpcode()) {
321  case Instruction::IndirectBr:
322  if (IBB)
323  return nullptr;
324  IBB = PredBB;
325  break;
326  case Instruction::Br:
327  case Instruction::Switch:
328  OtherPreds.push_back(PredBB);
329  continue;
330  default:
331  return nullptr;
332  }
333  }
334 
335  return IBB;
336 }
337 
339  bool IgnoreBlocksWithoutPHI,
342  // Check whether the function has any indirectbrs, and collect which blocks
343  // they may jump to. Since most functions don't have indirect branches,
344  // this lowers the common case's overhead to O(Blocks) instead of O(Edges).
346  for (auto &BB : F) {
347  auto *IBI = dyn_cast<IndirectBrInst>(BB.getTerminator());
348  if (!IBI)
349  continue;
350 
351  for (unsigned Succ = 0, E = IBI->getNumSuccessors(); Succ != E; ++Succ)
352  Targets.insert(IBI->getSuccessor(Succ));
353  }
354 
355  if (Targets.empty())
356  return false;
357 
358  bool ShouldUpdateAnalysis = BPI && BFI;
359  bool Changed = false;
360  for (BasicBlock *Target : Targets) {
361  if (IgnoreBlocksWithoutPHI && Target->phis().empty())
362  continue;
363 
365  BasicBlock *IBRPred = findIBRPredecessor(Target, OtherPreds);
366  // If we did not found an indirectbr, or the indirectbr is the only
367  // incoming edge, this isn't the kind of edge we're looking for.
368  if (!IBRPred || OtherPreds.empty())
369  continue;
370 
371  // Don't even think about ehpads/landingpads.
372  Instruction *FirstNonPHI = Target->getFirstNonPHI();
373  if (FirstNonPHI->isEHPad() || Target->isLandingPad())
374  continue;
375 
376  // Remember edge probabilities if needed.
377  SmallVector<BranchProbability, 4> EdgeProbabilities;
378  if (ShouldUpdateAnalysis) {
379  EdgeProbabilities.reserve(Target->getTerminator()->getNumSuccessors());
380  for (unsigned I = 0, E = Target->getTerminator()->getNumSuccessors();
381  I < E; ++I)
382  EdgeProbabilities.emplace_back(BPI->getEdgeProbability(Target, I));
383  BPI->eraseBlock(Target);
384  }
385 
386  BasicBlock *BodyBlock = Target->splitBasicBlock(FirstNonPHI, ".split");
387  if (ShouldUpdateAnalysis) {
388  // Copy the BFI/BPI from Target to BodyBlock.
389  BPI->setEdgeProbability(BodyBlock, EdgeProbabilities);
390  BFI->setBlockFreq(BodyBlock, BFI->getBlockFreq(Target).getFrequency());
391  }
392  // It's possible Target was its own successor through an indirectbr.
393  // In this case, the indirectbr now comes from BodyBlock.
394  if (IBRPred == Target)
395  IBRPred = BodyBlock;
396 
397  // At this point Target only has PHIs, and BodyBlock has the rest of the
398  // block's body. Create a copy of Target that will be used by the "direct"
399  // preds.
400  ValueToValueMapTy VMap;
401  BasicBlock *DirectSucc = CloneBasicBlock(Target, VMap, ".clone", &F);
402 
403  BlockFrequency BlockFreqForDirectSucc;
404  for (BasicBlock *Pred : OtherPreds) {
405  // If the target is a loop to itself, then the terminator of the split
406  // block (BodyBlock) needs to be updated.
407  BasicBlock *Src = Pred != Target ? Pred : BodyBlock;
408  Src->getTerminator()->replaceUsesOfWith(Target, DirectSucc);
409  if (ShouldUpdateAnalysis)
410  BlockFreqForDirectSucc += BFI->getBlockFreq(Src) *
411  BPI->getEdgeProbability(Src, DirectSucc);
412  }
413  if (ShouldUpdateAnalysis) {
414  BFI->setBlockFreq(DirectSucc, BlockFreqForDirectSucc.getFrequency());
415  BlockFrequency NewBlockFreqForTarget =
416  BFI->getBlockFreq(Target) - BlockFreqForDirectSucc;
417  BFI->setBlockFreq(Target, NewBlockFreqForTarget.getFrequency());
418  }
419 
420  // Ok, now fix up the PHIs. We know the two blocks only have PHIs, and that
421  // they are clones, so the number of PHIs are the same.
422  // (a) Remove the edge coming from IBRPred from the "Direct" PHI
423  // (b) Leave that as the only edge in the "Indirect" PHI.
424  // (c) Merge the two in the body block.
425  BasicBlock::iterator Indirect = Target->begin(),
426  End = Target->getFirstNonPHI()->getIterator();
427  BasicBlock::iterator Direct = DirectSucc->begin();
428  BasicBlock::iterator MergeInsert = BodyBlock->getFirstInsertionPt();
429 
430  assert(&*End == Target->getTerminator() &&
431  "Block was expected to only contain PHIs");
432 
433  while (Indirect != End) {
434  PHINode *DirPHI = cast<PHINode>(Direct);
435  PHINode *IndPHI = cast<PHINode>(Indirect);
436 
437  // Now, clean up - the direct block shouldn't get the indirect value,
438  // and vice versa.
439  DirPHI->removeIncomingValue(IBRPred);
440  Direct++;
441 
442  // Advance the pointer here, to avoid invalidation issues when the old
443  // PHI is erased.
444  Indirect++;
445 
446  PHINode *NewIndPHI = PHINode::Create(IndPHI->getType(), 1, "ind", IndPHI);
447  NewIndPHI->addIncoming(IndPHI->getIncomingValueForBlock(IBRPred),
448  IBRPred);
449 
450  // Create a PHI in the body block, to merge the direct and indirect
451  // predecessors.
452  PHINode *MergePHI =
453  PHINode::Create(IndPHI->getType(), 2, "merge", &*MergeInsert);
454  MergePHI->addIncoming(NewIndPHI, Target);
455  MergePHI->addIncoming(DirPHI, DirectSucc);
456 
457  IndPHI->replaceAllUsesWith(MergePHI);
458  IndPHI->eraseFromParent();
459  }
460 
461  Changed = true;
462  }
463 
464  return Changed;
465 }
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::Instruction::getNumSuccessors
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
Definition: Instruction.cpp:807
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
ValueMapper.h
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
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
MemorySSAUpdater.h
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
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:149
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
Statistic.h
llvm::PHINode::removeIncomingValue
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
Definition: Instructions.cpp:115
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:817
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:1293
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::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:164
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:24
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:306
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:2884
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::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:1255
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:42
llvm::BlockFrequency
Definition: BlockFrequency.h:23
llvm::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:819
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:81
BranchProbabilityInfo.h
llvm::PHINode::setIncomingBlock
void setIncomingBlock(unsigned i, BasicBlock *BB)
Definition: Instructions.h:2834
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:2849
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3190
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:2877
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:1843
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:351
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:338
llvm::BranchProbabilityInfo::eraseBlock
void eraseBlock(const BasicBlock *BB)
Forget analysis results for the given basic block.
Definition: BranchProbabilityInfo.cpp:1195
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:1100
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:1137
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:1716
llvm::Instruction::setSuccessor
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
Definition: Instruction.cpp:831
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:532
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:994
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
BlockFrequencyInfo.h
llvm::AMDGPUISD::BFI
@ BFI
Definition: AMDGPUISelLowering.h:432
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
llvm::ValueMap< const Value *, WeakTrackingVH >
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:85
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
llvm::LoopSimplifyID
char & LoopSimplifyID
Definition: LoopSimplify.cpp:789
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:2741
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:793
llvm::Instruction::isEHPad
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:664
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:614
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:849
findIBRPredecessor
static BasicBlock * findIBRPredecessor(BasicBlock *BB, SmallVectorImpl< BasicBlock * > &OtherPreds)
Definition: BreakCriticalEdges.cpp:313
Instructions.h
SmallVector.h
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:354
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:2815
llvm::PHINode
Definition: Instructions.h:2699
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:342
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:3134
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:667
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:475
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1268
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:941
llvm::Function::iterator
BasicBlockListType::iterator iterator
Definition: Function.h:66