LLVM  13.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 
103 /// When a loop exit edge is split, LCSSA form may require new PHIs in the new
104 /// exit block. This function inserts the new PHIs, as needed. Preds is a list
105 /// of preds inside the loop, SplitBB is the new loop exit block, and DestBB is
106 /// the old loop exit, now the successor of SplitBB.
108  BasicBlock *SplitBB,
109  BasicBlock *DestBB) {
110  // SplitBB shouldn't have anything non-trivial in it yet.
111  assert((SplitBB->getFirstNonPHI() == SplitBB->getTerminator() ||
112  SplitBB->isLandingPad()) && "SplitBB has non-PHI nodes!");
113 
114  // For each PHI in the destination block.
115  for (PHINode &PN : DestBB->phis()) {
116  unsigned Idx = PN.getBasicBlockIndex(SplitBB);
117  Value *V = PN.getIncomingValue(Idx);
118 
119  // If the input is a PHI which already satisfies LCSSA, don't create
120  // a new one.
121  if (const PHINode *VP = dyn_cast<PHINode>(V))
122  if (VP->getParent() == SplitBB)
123  continue;
124 
125  // Otherwise a new PHI is needed. Create one and populate it.
126  PHINode *NewPN = PHINode::Create(
127  PN.getType(), Preds.size(), "split",
128  SplitBB->isLandingPad() ? &SplitBB->front() : SplitBB->getTerminator());
129  for (unsigned i = 0, e = Preds.size(); i != e; ++i)
130  NewPN->addIncoming(V, Preds[i]);
131 
132  // Update the original PHI.
133  PN.setIncomingValue(Idx, NewPN);
134  }
135 }
136 
138  const CriticalEdgeSplittingOptions &Options,
139  const Twine &BBName) {
140  if (!isCriticalEdge(TI, SuccNum, Options.MergeIdenticalEdges))
141  return nullptr;
142 
143  assert(!isa<IndirectBrInst>(TI) &&
144  "Cannot split critical edge from IndirectBrInst");
145 
146  BasicBlock *TIBB = TI->getParent();
147  BasicBlock *DestBB = TI->getSuccessor(SuccNum);
148 
149  // Splitting the critical edge to a pad block is non-trivial. Don't do
150  // it in this generic function.
151  if (DestBB->isEHPad()) return nullptr;
152 
153  if (Options.IgnoreUnreachableDests &&
154  isa<UnreachableInst>(DestBB->getFirstNonPHIOrDbgOrLifetime()))
155  return nullptr;
156 
157  auto *LI = Options.LI;
159  // Check if extra modifications will be required to preserve loop-simplify
160  // form after splitting. If it would require splitting blocks with IndirectBr
161  // or CallBr terminators, bail out if preserving loop-simplify form is
162  // requested.
163  if (LI) {
164  if (Loop *TIL = LI->getLoopFor(TIBB)) {
165 
166  // The only way that we can break LoopSimplify form by splitting a
167  // critical edge is if after the split there exists some edge from TIL to
168  // DestBB *and* the only edge into DestBB from outside of TIL is that of
169  // NewBB. If the first isn't true, then LoopSimplify still holds, NewBB
170  // is the new exit block and it has no non-loop predecessors. If the
171  // second isn't true, then DestBB was not in LoopSimplify form prior to
172  // the split as it had a non-loop predecessor. In both of these cases,
173  // the predecessor must be directly in TIL, not in a subloop, or again
174  // LoopSimplify doesn't hold.
175  for (BasicBlock *P : predecessors(DestBB)) {
176  if (P == TIBB)
177  continue; // The new block is known.
178  if (LI->getLoopFor(P) != TIL) {
179  // No need to re-simplify, it wasn't to start with.
180  LoopPreds.clear();
181  break;
182  }
183  LoopPreds.push_back(P);
184  }
185  // Loop-simplify form can be preserved, if we can split all in-loop
186  // predecessors.
187  if (any_of(LoopPreds, [](BasicBlock *Pred) {
188  const Instruction *T = Pred->getTerminator();
189  if (const auto *CBR = dyn_cast<CallBrInst>(T))
190  return CBR->getDefaultDest() != Pred;
191  return isa<IndirectBrInst>(T);
192  })) {
193  if (Options.PreserveLoopSimplify)
194  return nullptr;
195  LoopPreds.clear();
196  }
197  }
198  }
199 
200  // Create a new basic block, linking it into the CFG.
201  BasicBlock *NewBB = nullptr;
202  if (BBName.str() != "")
203  NewBB = BasicBlock::Create(TI->getContext(), BBName);
204  else
205  NewBB = BasicBlock::Create(TI->getContext(), TIBB->getName() + "." +
206  DestBB->getName() +
207  "_crit_edge");
208  // Create our unconditional branch.
209  BranchInst *NewBI = BranchInst::Create(DestBB, NewBB);
210  NewBI->setDebugLoc(TI->getDebugLoc());
211 
212  // Insert the block into the function... right after the block TI lives in.
213  Function &F = *TIBB->getParent();
214  Function::iterator FBBI = TIBB->getIterator();
215  F.getBasicBlockList().insert(++FBBI, NewBB);
216 
217  // Branch to the new block, breaking the edge.
218  TI->setSuccessor(SuccNum, NewBB);
219 
220  // If there are any PHI nodes in DestBB, we need to update them so that they
221  // merge incoming values from NewBB instead of from TIBB.
222  {
223  unsigned BBIdx = 0;
224  for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) {
225  // We no longer enter through TIBB, now we come in through NewBB.
226  // Revector exactly one entry in the PHI node that used to come from
227  // TIBB to come from NewBB.
228  PHINode *PN = cast<PHINode>(I);
229 
230  // Reuse the previous value of BBIdx if it lines up. In cases where we
231  // have multiple phi nodes with *lots* of predecessors, this is a speed
232  // win because we don't have to scan the PHI looking for TIBB. This
233  // happens because the BB list of PHI nodes are usually in the same
234  // order.
235  if (PN->getIncomingBlock(BBIdx) != TIBB)
236  BBIdx = PN->getBasicBlockIndex(TIBB);
237  PN->setIncomingBlock(BBIdx, NewBB);
238  }
239  }
240 
241  // If there are any other edges from TIBB to DestBB, update those to go
242  // through the split block, making those edges non-critical as well (and
243  // reducing the number of phi entries in the DestBB if relevant).
244  if (Options.MergeIdenticalEdges) {
245  for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) {
246  if (TI->getSuccessor(i) != DestBB) continue;
247 
248  // Remove an entry for TIBB from DestBB phi nodes.
249  DestBB->removePredecessor(TIBB, Options.KeepOneInputPHIs);
250 
251  // We found another edge to DestBB, go to NewBB instead.
252  TI->setSuccessor(i, NewBB);
253  }
254  }
255 
256  // If we have nothing to update, just return.
257  auto *DT = Options.DT;
258  auto *PDT = Options.PDT;
259  auto *MSSAU = Options.MSSAU;
260  if (MSSAU)
262  DestBB, NewBB, {TIBB}, Options.MergeIdenticalEdges);
263 
264  if (!DT && !PDT && !LI)
265  return NewBB;
266 
267  if (DT || PDT) {
268  // Update the DominatorTree.
269  // ---> NewBB -----\
270  // / V
271  // TIBB -------\\------> DestBB
272  //
273  // First, inform the DT about the new path from TIBB to DestBB via NewBB,
274  // then delete the old edge from TIBB to DestBB. By doing this in that order
275  // DestBB stays reachable in the DT the whole time and its subtree doesn't
276  // get disconnected.
278  Updates.push_back({DominatorTree::Insert, TIBB, NewBB});
279  Updates.push_back({DominatorTree::Insert, NewBB, DestBB});
280  if (!llvm::is_contained(successors(TIBB), DestBB))
281  Updates.push_back({DominatorTree::Delete, TIBB, DestBB});
282 
283  if (DT)
284  DT->applyUpdates(Updates);
285  if (PDT)
286  PDT->applyUpdates(Updates);
287  }
288 
289  // Update LoopInfo if it is around.
290  if (LI) {
291  if (Loop *TIL = LI->getLoopFor(TIBB)) {
292  // If one or the other blocks were not in a loop, the new block is not
293  // either, and thus LI doesn't need to be updated.
294  if (Loop *DestLoop = LI->getLoopFor(DestBB)) {
295  if (TIL == DestLoop) {
296  // Both in the same loop, the NewBB joins loop.
297  DestLoop->addBasicBlockToLoop(NewBB, *LI);
298  } else if (TIL->contains(DestLoop)) {
299  // Edge from an outer loop to an inner loop. Add to the outer loop.
300  TIL->addBasicBlockToLoop(NewBB, *LI);
301  } else if (DestLoop->contains(TIL)) {
302  // Edge from an inner loop to an outer loop. Add to the outer loop.
303  DestLoop->addBasicBlockToLoop(NewBB, *LI);
304  } else {
305  // Edge from two loops with no containment relation. Because these
306  // are natural loops, we know that the destination block must be the
307  // header of its loop (adding a branch into a loop elsewhere would
308  // create an irreducible loop).
309  assert(DestLoop->getHeader() == DestBB &&
310  "Should not create irreducible loops!");
311  if (Loop *P = DestLoop->getParentLoop())
312  P->addBasicBlockToLoop(NewBB, *LI);
313  }
314  }
315 
316  // If TIBB is in a loop and DestBB is outside of that loop, we may need
317  // to update LoopSimplify form and LCSSA form.
318  if (!TIL->contains(DestBB)) {
319  assert(!TIL->contains(NewBB) &&
320  "Split point for loop exit is contained in loop!");
321 
322  // Update LCSSA form in the newly created exit block.
323  if (Options.PreserveLCSSA) {
324  createPHIsForSplitLoopExit(TIBB, NewBB, DestBB);
325  }
326 
327  if (!LoopPreds.empty()) {
328  assert(!DestBB->isEHPad() && "We don't split edges to EH pads!");
329  BasicBlock *NewExitBB = SplitBlockPredecessors(
330  DestBB, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA);
331  if (Options.PreserveLCSSA)
332  createPHIsForSplitLoopExit(LoopPreds, NewExitBB, DestBB);
333  }
334  }
335  }
336  }
337 
338  return NewBB;
339 }
340 
341 // Return the unique indirectbr predecessor of a block. This may return null
342 // even if such a predecessor exists, if it's not useful for splitting.
343 // If a predecessor is found, OtherPreds will contain all other (non-indirectbr)
344 // predecessors of BB.
345 static BasicBlock *
347  // If the block doesn't have any PHIs, we don't care about it, since there's
348  // no point in splitting it.
349  PHINode *PN = dyn_cast<PHINode>(BB->begin());
350  if (!PN)
351  return nullptr;
352 
353  // Verify we have exactly one IBR predecessor.
354  // Conservatively bail out if one of the other predecessors is not a "regular"
355  // terminator (that is, not a switch or a br).
356  BasicBlock *IBB = nullptr;
357  for (unsigned Pred = 0, E = PN->getNumIncomingValues(); Pred != E; ++Pred) {
358  BasicBlock *PredBB = PN->getIncomingBlock(Pred);
359  Instruction *PredTerm = PredBB->getTerminator();
360  switch (PredTerm->getOpcode()) {
361  case Instruction::IndirectBr:
362  if (IBB)
363  return nullptr;
364  IBB = PredBB;
365  break;
366  case Instruction::Br:
367  case Instruction::Switch:
368  OtherPreds.push_back(PredBB);
369  continue;
370  default:
371  return nullptr;
372  }
373  }
374 
375  return IBB;
376 }
377 
381  // Check whether the function has any indirectbrs, and collect which blocks
382  // they may jump to. Since most functions don't have indirect branches,
383  // this lowers the common case's overhead to O(Blocks) instead of O(Edges).
385  for (auto &BB : F) {
386  auto *IBI = dyn_cast<IndirectBrInst>(BB.getTerminator());
387  if (!IBI)
388  continue;
389 
390  for (unsigned Succ = 0, E = IBI->getNumSuccessors(); Succ != E; ++Succ)
391  Targets.insert(IBI->getSuccessor(Succ));
392  }
393 
394  if (Targets.empty())
395  return false;
396 
397  bool ShouldUpdateAnalysis = BPI && BFI;
398  bool Changed = false;
399  for (BasicBlock *Target : Targets) {
401  BasicBlock *IBRPred = findIBRPredecessor(Target, OtherPreds);
402  // If we did not found an indirectbr, or the indirectbr is the only
403  // incoming edge, this isn't the kind of edge we're looking for.
404  if (!IBRPred || OtherPreds.empty())
405  continue;
406 
407  // Don't even think about ehpads/landingpads.
408  Instruction *FirstNonPHI = Target->getFirstNonPHI();
409  if (FirstNonPHI->isEHPad() || Target->isLandingPad())
410  continue;
411 
412  // Remember edge probabilities if needed.
413  SmallVector<BranchProbability, 4> EdgeProbabilities;
414  if (ShouldUpdateAnalysis) {
415  EdgeProbabilities.reserve(Target->getTerminator()->getNumSuccessors());
416  for (unsigned I = 0, E = Target->getTerminator()->getNumSuccessors();
417  I < E; ++I)
418  EdgeProbabilities.emplace_back(BPI->getEdgeProbability(Target, I));
419  BPI->eraseBlock(Target);
420  }
421 
422  BasicBlock *BodyBlock = Target->splitBasicBlock(FirstNonPHI, ".split");
423  if (ShouldUpdateAnalysis) {
424  // Copy the BFI/BPI from Target to BodyBlock.
425  BPI->setEdgeProbability(BodyBlock, EdgeProbabilities);
426  BFI->setBlockFreq(BodyBlock, BFI->getBlockFreq(Target).getFrequency());
427  }
428  // It's possible Target was its own successor through an indirectbr.
429  // In this case, the indirectbr now comes from BodyBlock.
430  if (IBRPred == Target)
431  IBRPred = BodyBlock;
432 
433  // At this point Target only has PHIs, and BodyBlock has the rest of the
434  // block's body. Create a copy of Target that will be used by the "direct"
435  // preds.
436  ValueToValueMapTy VMap;
437  BasicBlock *DirectSucc = CloneBasicBlock(Target, VMap, ".clone", &F);
438 
439  BlockFrequency BlockFreqForDirectSucc;
440  for (BasicBlock *Pred : OtherPreds) {
441  // If the target is a loop to itself, then the terminator of the split
442  // block (BodyBlock) needs to be updated.
443  BasicBlock *Src = Pred != Target ? Pred : BodyBlock;
444  Src->getTerminator()->replaceUsesOfWith(Target, DirectSucc);
445  if (ShouldUpdateAnalysis)
446  BlockFreqForDirectSucc += BFI->getBlockFreq(Src) *
447  BPI->getEdgeProbability(Src, DirectSucc);
448  }
449  if (ShouldUpdateAnalysis) {
450  BFI->setBlockFreq(DirectSucc, BlockFreqForDirectSucc.getFrequency());
451  BlockFrequency NewBlockFreqForTarget =
452  BFI->getBlockFreq(Target) - BlockFreqForDirectSucc;
453  BFI->setBlockFreq(Target, NewBlockFreqForTarget.getFrequency());
454  }
455 
456  // Ok, now fix up the PHIs. We know the two blocks only have PHIs, and that
457  // they are clones, so the number of PHIs are the same.
458  // (a) Remove the edge coming from IBRPred from the "Direct" PHI
459  // (b) Leave that as the only edge in the "Indirect" PHI.
460  // (c) Merge the two in the body block.
461  BasicBlock::iterator Indirect = Target->begin(),
462  End = Target->getFirstNonPHI()->getIterator();
463  BasicBlock::iterator Direct = DirectSucc->begin();
464  BasicBlock::iterator MergeInsert = BodyBlock->getFirstInsertionPt();
465 
466  assert(&*End == Target->getTerminator() &&
467  "Block was expected to only contain PHIs");
468 
469  while (Indirect != End) {
470  PHINode *DirPHI = cast<PHINode>(Direct);
471  PHINode *IndPHI = cast<PHINode>(Indirect);
472 
473  // Now, clean up - the direct block shouldn't get the indirect value,
474  // and vice versa.
475  DirPHI->removeIncomingValue(IBRPred);
476  Direct++;
477 
478  // Advance the pointer here, to avoid invalidation issues when the old
479  // PHI is erased.
480  Indirect++;
481 
482  PHINode *NewIndPHI = PHINode::Create(IndPHI->getType(), 1, "ind", IndPHI);
483  NewIndPHI->addIncoming(IndPHI->getIncomingValueForBlock(IBRPred),
484  IBRPred);
485 
486  // Create a PHI in the body block, to merge the direct and indirect
487  // predecessors.
488  PHINode *MergePHI =
489  PHINode::Create(IndPHI->getType(), 2, "merge", &*MergeInsert);
490  MergePHI->addIncoming(NewIndPHI, Target);
491  MergePHI->addIncoming(DirPHI, DirectSucc);
492 
493  IndPHI->replaceAllUsesWith(MergePHI);
494  IndPHI->eraseFromParent();
495  }
496 
497  Changed = true;
498  }
499 
500  return Changed;
501 }
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:125
llvm
This class represents lattice values for constants.
Definition: AllocatorList.h:23
llvm::CriticalEdgeSplittingOptions::MSSAU
MemorySSAUpdater * MSSAU
Definition: BasicBlockUtils.h:140
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:529
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:124
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:109
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:137
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1249
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::CriticalEdgeSplittingOptions::LI
LoopInfo * LI
Definition: BasicBlockUtils.h:139
llvm::BreakCriticalEdgesPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: BreakCriticalEdges.cpp:85
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:260
llvm::CriticalEdgeSplittingOptions::IgnoreUnreachableDests
bool IgnoreUnreachableDests
Definition: BasicBlockUtils.h:144
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:696
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::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::BasicBlock::isLandingPad
bool isLandingPad() const
Return true if this basic block is a landing pad.
Definition: BasicBlock.cpp:466
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:2755
llvm::Instruction
Definition: Instruction.h:45
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:278
llvm::BasicBlock::phis
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:354
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:708
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:933
llvm::BasicBlock::getFirstNonPHI
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:212
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:2662
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::CriticalEdgeSplittingOptions::KeepOneInputPHIs
bool KeepOneInputPHIs
Definition: BasicBlockUtils.h:142
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:77
BranchProbabilityInfo.h
llvm::PHINode::setIncomingBlock
void setIncomingBlock(unsigned i, BasicBlock *BB)
Definition: Instructions.h:2705
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:2720
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:58
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3061
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:378
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:2748
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:1563
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:362
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::CriticalEdgeSplittingOptions::PreserveLCSSA
bool PreserveLCSSA
Definition: BasicBlockUtils.h:143
llvm::User::replaceUsesOfWith
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:21
llvm::BranchProbabilityInfo::eraseBlock
void eraseBlock(const BasicBlock *BB)
Forget analysis results for the given basic block.
Definition: BranchProbabilityInfo.cpp:1227
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::CriticalEdgeSplittingOptions::PDT
PostDominatorTree * PDT
Definition: BasicBlockUtils.h:138
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:1133
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:1170
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
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:1505
llvm::Instruction::setSuccessor
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
Definition: Instruction.cpp:720
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:246
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:523
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:871
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
BlockFrequencyInfo.h
llvm::AMDGPUISD::BFI
@ BFI
Definition: AMDGPUISelLowering.h:419
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:295
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
llvm::CriticalEdgeSplittingOptions::MergeIdenticalEdges
bool MergeIdenticalEdges
Definition: BasicBlockUtils.h:141
llvm::BasicBlock::front
const Instruction & front() const
Definition: BasicBlock.h:308
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:80
llvm::LoopSimplifyID
char & LoopSimplifyID
Definition: LoopSimplify.cpp:801
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:2612
llvm::MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor
void wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New, ArrayRef< BasicBlock * > Preds, bool IdenticalEdgesWereMerged=true)
A new empty BasicBlock (New) now branches directly to Old.
Definition: MemorySSAUpdater.cpp:1271
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:641
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::BreakCriticalEdgesID
char & BreakCriticalEdgesID
llvm::CriticalEdgeSplittingOptions::DT
DominatorTree * DT
Definition: BasicBlockUtils.h:137
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:249
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:531
findIBRPredecessor
static BasicBlock * findIBRPredecessor(BasicBlock *BB, SmallVectorImpl< BasicBlock * > &OtherPreds)
Definition: BreakCriticalEdges.cpp:346
Instructions.h
SmallVector.h
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:365
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:2686
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:163
llvm::PHINode
Definition: Instructions.h:2572
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:43
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:3005
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:624
BasicBlockUtils.h
llvm::initializeBreakCriticalEdgesPass
void initializeBreakCriticalEdgesPass(PassRegistry &)
llvm::CriticalEdgeSplittingOptions::PreserveLoopSimplify
bool PreserveLoopSimplify
SplitCriticalEdge is guaranteed to preserve loop-simplify form if LI is provided.
Definition: BasicBlockUtils.h:148
InitializePasses.h
llvm::BasicBlock::isEHPad
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:465
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
createPHIsForSplitLoopExit
static void createPHIsForSplitLoopExit(ArrayRef< BasicBlock * > Preds, BasicBlock *SplitBB, BasicBlock *DestBB)
When a loop exit edge is split, LCSSA form may require new PHIs in the new exit block.
Definition: BreakCriticalEdges.cpp:107
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1224
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:66
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37