LLVM  10.0.0svn
BasicBlockUtils.cpp
Go to the documentation of this file.
1 //===- BasicBlockUtils.cpp - BasicBlock Utilities --------------------------==//
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 // This family of functions perform manipulations on basic blocks, and
10 // instructions contained within basic blocks.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/ArrayRef.h"
16 #include "llvm/ADT/SmallPtrSet.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/Twine.h"
19 #include "llvm/Analysis/CFG.h"
21 #include "llvm/Analysis/LoopInfo.h"
25 #include "llvm/IR/BasicBlock.h"
26 #include "llvm/IR/CFG.h"
27 #include "llvm/IR/Constants.h"
29 #include "llvm/IR/Dominators.h"
30 #include "llvm/IR/Function.h"
31 #include "llvm/IR/InstrTypes.h"
32 #include "llvm/IR/Instruction.h"
33 #include "llvm/IR/Instructions.h"
34 #include "llvm/IR/IntrinsicInst.h"
35 #include "llvm/IR/LLVMContext.h"
36 #include "llvm/IR/Type.h"
37 #include "llvm/IR/User.h"
38 #include "llvm/IR/Value.h"
39 #include "llvm/IR/ValueHandle.h"
40 #include "llvm/Support/Casting.h"
41 #include "llvm/Support/Debug.h"
44 #include <cassert>
45 #include <cstdint>
46 #include <string>
47 #include <utility>
48 #include <vector>
49 
50 using namespace llvm;
51 
52 #define DEBUG_TYPE "basicblock-utils"
53 
57  bool KeepOneInputPHIs) {
58  for (auto *BB : BBs) {
59  // Loop through all of our successors and make sure they know that one
60  // of their predecessors is going away.
61  SmallPtrSet<BasicBlock *, 4> UniqueSuccessors;
62  for (BasicBlock *Succ : successors(BB)) {
63  Succ->removePredecessor(BB, KeepOneInputPHIs);
64  if (Updates && UniqueSuccessors.insert(Succ).second)
65  Updates->push_back({DominatorTree::Delete, BB, Succ});
66  }
67 
68  // Zap all the instructions in the block.
69  while (!BB->empty()) {
70  Instruction &I = BB->back();
71  // If this instruction is used, replace uses with an arbitrary value.
72  // Because control flow can't get here, we don't care what we replace the
73  // value with. Note that since this block is unreachable, and all values
74  // contained within it must dominate their uses, that all uses will
75  // eventually be removed (they are themselves dead).
76  if (!I.use_empty())
78  BB->getInstList().pop_back();
79  }
80  new UnreachableInst(BB->getContext(), BB);
81  assert(BB->getInstList().size() == 1 &&
82  isa<UnreachableInst>(BB->getTerminator()) &&
83  "The successor list of BB isn't empty before "
84  "applying corresponding DTU updates.");
85  }
86 }
87 
89  bool KeepOneInputPHIs) {
90  DeleteDeadBlocks({BB}, DTU, KeepOneInputPHIs);
91 }
92 
94  bool KeepOneInputPHIs) {
95 #ifndef NDEBUG
96  // Make sure that all predecessors of each dead block is also dead.
98  assert(Dead.size() == BBs.size() && "Duplicating blocks?");
99  for (auto *BB : Dead)
100  for (BasicBlock *Pred : predecessors(BB))
101  assert(Dead.count(Pred) && "All predecessors must be dead!");
102 #endif
103 
105  DetatchDeadBlocks(BBs, DTU ? &Updates : nullptr, KeepOneInputPHIs);
106 
107  if (DTU)
108  DTU->applyUpdatesPermissive(Updates);
109 
110  for (BasicBlock *BB : BBs)
111  if (DTU)
112  DTU->deleteBB(BB);
113  else
114  BB->eraseFromParent();
115 }
116 
118  bool KeepOneInputPHIs) {
120 
121  // Mark all reachable blocks.
122  for (BasicBlock *BB : depth_first_ext(&F, Reachable))
123  (void)BB/* Mark all reachable blocks */;
124 
125  // Collect all dead blocks.
126  std::vector<BasicBlock*> DeadBlocks;
127  for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
128  if (!Reachable.count(&*I)) {
129  BasicBlock *BB = &*I;
130  DeadBlocks.push_back(BB);
131  }
132 
133  // Delete the dead blocks.
134  DeleteDeadBlocks(DeadBlocks, DTU, KeepOneInputPHIs);
135 
136  return !DeadBlocks.empty();
137 }
138 
140  MemoryDependenceResults *MemDep) {
141  if (!isa<PHINode>(BB->begin())) return;
142 
143  while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
144  if (PN->getIncomingValue(0) != PN)
145  PN->replaceAllUsesWith(PN->getIncomingValue(0));
146  else
147  PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
148 
149  if (MemDep)
150  MemDep->removeInstruction(PN); // Memdep updates AA itself.
151 
152  PN->eraseFromParent();
153  }
154 }
155 
157  // Recursively deleting a PHI may cause multiple PHIs to be deleted
158  // or RAUW'd undef, so use an array of WeakTrackingVH for the PHIs to delete.
160  for (PHINode &PN : BB->phis())
161  PHIs.push_back(&PN);
162 
163  bool Changed = false;
164  for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
165  if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i].operator Value*()))
166  Changed |= RecursivelyDeleteDeadPHINode(PN, TLI);
167 
168  return Changed;
169 }
170 
172  LoopInfo *LI, MemorySSAUpdater *MSSAU,
173  MemoryDependenceResults *MemDep) {
174  if (BB->hasAddressTaken())
175  return false;
176 
177  // Can't merge if there are multiple predecessors, or no predecessors.
178  BasicBlock *PredBB = BB->getUniquePredecessor();
179  if (!PredBB) return false;
180 
181  // Don't break self-loops.
182  if (PredBB == BB) return false;
183  // Don't break unwinding instructions.
184  if (PredBB->getTerminator()->isExceptionalTerminator())
185  return false;
186 
187  // Can't merge if there are multiple distinct successors.
188  if (PredBB->getUniqueSuccessor() != BB)
189  return false;
190 
191  // Can't merge if there is PHI loop.
192  for (PHINode &PN : BB->phis())
193  for (Value *IncValue : PN.incoming_values())
194  if (IncValue == &PN)
195  return false;
196 
197  LLVM_DEBUG(dbgs() << "Merging: " << BB->getName() << " into "
198  << PredBB->getName() << "\n");
199 
200  // Begin by getting rid of unneeded PHIs.
201  SmallVector<AssertingVH<Value>, 4> IncomingValues;
202  if (isa<PHINode>(BB->front())) {
203  for (PHINode &PN : BB->phis())
204  if (!isa<PHINode>(PN.getIncomingValue(0)) ||
205  cast<PHINode>(PN.getIncomingValue(0))->getParent() != BB)
206  IncomingValues.push_back(PN.getIncomingValue(0));
207  FoldSingleEntryPHINodes(BB, MemDep);
208  }
209 
210  // DTU update: Collect all the edges that exit BB.
211  // These dominator edges will be redirected from Pred.
212  std::vector<DominatorTree::UpdateType> Updates;
213  if (DTU) {
214  Updates.reserve(1 + (2 * succ_size(BB)));
215  // Add insert edges first. Experimentally, for the particular case of two
216  // blocks that can be merged, with a single successor and single predecessor
217  // respectively, it is beneficial to have all insert updates first. Deleting
218  // edges first may lead to unreachable blocks, followed by inserting edges
219  // making the blocks reachable again. Such DT updates lead to high compile
220  // times. We add inserts before deletes here to reduce compile time.
221  for (auto I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
222  // This successor of BB may already have PredBB as a predecessor.
223  if (llvm::find(successors(PredBB), *I) == succ_end(PredBB))
224  Updates.push_back({DominatorTree::Insert, PredBB, *I});
225  for (auto I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
226  Updates.push_back({DominatorTree::Delete, BB, *I});
227  Updates.push_back({DominatorTree::Delete, PredBB, BB});
228  }
229 
230  if (MSSAU)
231  MSSAU->moveAllAfterMergeBlocks(BB, PredBB, &*(BB->begin()));
232 
233  // Delete the unconditional branch from the predecessor...
234  PredBB->getInstList().pop_back();
235 
236  // Make all PHI nodes that referred to BB now refer to Pred as their
237  // source...
238  BB->replaceAllUsesWith(PredBB);
239 
240  // Move all definitions in the successor to the predecessor...
241  PredBB->getInstList().splice(PredBB->end(), BB->getInstList());
242  new UnreachableInst(BB->getContext(), BB);
243 
244  // Eliminate duplicate dbg.values describing the entry PHI node post-splice.
245  for (auto Incoming : IncomingValues) {
246  if (isa<Instruction>(*Incoming)) {
249  DbgValueSet;
250  llvm::findDbgValues(DbgValues, Incoming);
251  for (auto &DVI : DbgValues) {
252  auto R = DbgValueSet.insert({DVI->getVariable(), DVI->getExpression()});
253  if (!R.second)
254  DVI->eraseFromParent();
255  }
256  }
257  }
258 
259  // Inherit predecessors name if it exists.
260  if (!PredBB->hasName())
261  PredBB->takeName(BB);
262 
263  if (LI)
264  LI->removeBlock(BB);
265 
266  if (MemDep)
268 
269  // Finally, erase the old block and update dominator info.
270  if (DTU) {
271  assert(BB->getInstList().size() == 1 &&
272  isa<UnreachableInst>(BB->getTerminator()) &&
273  "The successor list of BB isn't empty before "
274  "applying corresponding DTU updates.");
275  DTU->applyUpdatesPermissive(Updates);
276  DTU->deleteBB(BB);
277  }
278 
279  else {
280  BB->eraseFromParent(); // Nuke BB if DTU is nullptr.
281  }
282  return true;
283 }
284 
286  BasicBlock::iterator &BI, Value *V) {
287  Instruction &I = *BI;
288  // Replaces all of the uses of the instruction with uses of the value
289  I.replaceAllUsesWith(V);
290 
291  // Make sure to propagate a name if there is one already.
292  if (I.hasName() && !V->hasName())
293  V->takeName(&I);
294 
295  // Delete the unnecessary instruction now...
296  BI = BIL.erase(BI);
297 }
298 
301  assert(I->getParent() == nullptr &&
302  "ReplaceInstWithInst: Instruction already inserted into basic block!");
303 
304  // Copy debug location to newly added instruction, if it wasn't already set
305  // by the caller.
306  if (!I->getDebugLoc())
307  I->setDebugLoc(BI->getDebugLoc());
308 
309  // Insert the new instruction into the basic block...
310  BasicBlock::iterator New = BIL.insert(BI, I);
311 
312  // Replace all uses of the old instruction, and delete it.
313  ReplaceInstWithValue(BIL, BI, I);
314 
315  // Move BI back to point to the newly inserted instruction
316  BI = New;
317 }
318 
320  BasicBlock::iterator BI(From);
321  ReplaceInstWithInst(From->getParent()->getInstList(), BI, To);
322 }
323 
325  LoopInfo *LI, MemorySSAUpdater *MSSAU) {
326  unsigned SuccNum = GetSuccessorNumber(BB, Succ);
327 
328  // If this is a critical edge, let SplitCriticalEdge do it.
329  Instruction *LatchTerm = BB->getTerminator();
330  if (SplitCriticalEdge(
331  LatchTerm, SuccNum,
332  CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA()))
333  return LatchTerm->getSuccessor(SuccNum);
334 
335  // If the edge isn't critical, then BB has a single successor or Succ has a
336  // single pred. Split the block.
337  if (BasicBlock *SP = Succ->getSinglePredecessor()) {
338  // If the successor only has a single pred, split the top of the successor
339  // block.
340  assert(SP == BB && "CFG broken");
341  SP = nullptr;
342  return SplitBlock(Succ, &Succ->front(), DT, LI, MSSAU);
343  }
344 
345  // Otherwise, if BB has a single successor, split it at the bottom of the
346  // block.
347  assert(BB->getTerminator()->getNumSuccessors() == 1 &&
348  "Should have a single succ!");
349  return SplitBlock(BB, BB->getTerminator(), DT, LI, MSSAU);
350 }
351 
352 unsigned
354  const CriticalEdgeSplittingOptions &Options) {
355  unsigned NumBroken = 0;
356  for (BasicBlock &BB : F) {
357  Instruction *TI = BB.getTerminator();
358  if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI))
359  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
360  if (SplitCriticalEdge(TI, i, Options))
361  ++NumBroken;
362  }
363  return NumBroken;
364 }
365 
367  DominatorTree *DT, LoopInfo *LI,
368  MemorySSAUpdater *MSSAU) {
369  BasicBlock::iterator SplitIt = SplitPt->getIterator();
370  while (isa<PHINode>(SplitIt) || SplitIt->isEHPad())
371  ++SplitIt;
372  BasicBlock *New = Old->splitBasicBlock(SplitIt, Old->getName()+".split");
373 
374  // The new block lives in whichever loop the old one did. This preserves
375  // LCSSA as well, because we force the split point to be after any PHI nodes.
376  if (LI)
377  if (Loop *L = LI->getLoopFor(Old))
378  L->addBasicBlockToLoop(New, *LI);
379 
380  if (DT)
381  // Old dominates New. New node dominates all other nodes dominated by Old.
382  if (DomTreeNode *OldNode = DT->getNode(Old)) {
383  std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
384 
385  DomTreeNode *NewNode = DT->addNewBlock(New, Old);
386  for (DomTreeNode *I : Children)
387  DT->changeImmediateDominator(I, NewNode);
388  }
389 
390  // Move MemoryAccesses still tracked in Old, but part of New now.
391  // Update accesses in successor blocks accordingly.
392  if (MSSAU)
393  MSSAU->moveAllAfterSpliceBlocks(Old, New, &*(New->begin()));
394 
395  return New;
396 }
397 
398 /// Update DominatorTree, LoopInfo, and LCCSA analysis information.
401  DominatorTree *DT, LoopInfo *LI,
402  MemorySSAUpdater *MSSAU,
403  bool PreserveLCSSA, bool &HasLoopExit) {
404  // Update dominator tree if available.
405  if (DT) {
406  if (OldBB == DT->getRootNode()->getBlock()) {
407  assert(NewBB == &NewBB->getParent()->getEntryBlock());
408  DT->setNewRoot(NewBB);
409  } else {
410  // Split block expects NewBB to have a non-empty set of predecessors.
411  DT->splitBlock(NewBB);
412  }
413  }
414 
415  // Update MemoryPhis after split if MemorySSA is available
416  if (MSSAU)
417  MSSAU->wireOldPredecessorsToNewImmediatePredecessor(OldBB, NewBB, Preds);
418 
419  // The rest of the logic is only relevant for updating the loop structures.
420  if (!LI)
421  return;
422 
423  assert(DT && "DT should be available to update LoopInfo!");
424  Loop *L = LI->getLoopFor(OldBB);
425 
426  // If we need to preserve loop analyses, collect some information about how
427  // this split will affect loops.
428  bool IsLoopEntry = !!L;
429  bool SplitMakesNewLoopHeader = false;
430  for (BasicBlock *Pred : Preds) {
431  // Preds that are not reachable from entry should not be used to identify if
432  // OldBB is a loop entry or if SplitMakesNewLoopHeader. Unreachable blocks
433  // are not within any loops, so we incorrectly mark SplitMakesNewLoopHeader
434  // as true and make the NewBB the header of some loop. This breaks LI.
435  if (!DT->isReachableFromEntry(Pred))
436  continue;
437  // If we need to preserve LCSSA, determine if any of the preds is a loop
438  // exit.
439  if (PreserveLCSSA)
440  if (Loop *PL = LI->getLoopFor(Pred))
441  if (!PL->contains(OldBB))
442  HasLoopExit = true;
443 
444  // If we need to preserve LoopInfo, note whether any of the preds crosses
445  // an interesting loop boundary.
446  if (!L)
447  continue;
448  if (L->contains(Pred))
449  IsLoopEntry = false;
450  else
451  SplitMakesNewLoopHeader = true;
452  }
453 
454  // Unless we have a loop for OldBB, nothing else to do here.
455  if (!L)
456  return;
457 
458  if (IsLoopEntry) {
459  // Add the new block to the nearest enclosing loop (and not an adjacent
460  // loop). To find this, examine each of the predecessors and determine which
461  // loops enclose them, and select the most-nested loop which contains the
462  // loop containing the block being split.
463  Loop *InnermostPredLoop = nullptr;
464  for (BasicBlock *Pred : Preds) {
465  if (Loop *PredLoop = LI->getLoopFor(Pred)) {
466  // Seek a loop which actually contains the block being split (to avoid
467  // adjacent loops).
468  while (PredLoop && !PredLoop->contains(OldBB))
469  PredLoop = PredLoop->getParentLoop();
470 
471  // Select the most-nested of these loops which contains the block.
472  if (PredLoop && PredLoop->contains(OldBB) &&
473  (!InnermostPredLoop ||
474  InnermostPredLoop->getLoopDepth() < PredLoop->getLoopDepth()))
475  InnermostPredLoop = PredLoop;
476  }
477  }
478 
479  if (InnermostPredLoop)
480  InnermostPredLoop->addBasicBlockToLoop(NewBB, *LI);
481  } else {
482  L->addBasicBlockToLoop(NewBB, *LI);
483  if (SplitMakesNewLoopHeader)
484  L->moveToHeader(NewBB);
485  }
486 }
487 
488 /// Update the PHI nodes in OrigBB to include the values coming from NewBB.
489 /// This also updates AliasAnalysis, if available.
490 static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB,
492  bool HasLoopExit) {
493  // Otherwise, create a new PHI node in NewBB for each PHI node in OrigBB.
494  SmallPtrSet<BasicBlock *, 16> PredSet(Preds.begin(), Preds.end());
495  for (BasicBlock::iterator I = OrigBB->begin(); isa<PHINode>(I); ) {
496  PHINode *PN = cast<PHINode>(I++);
497 
498  // Check to see if all of the values coming in are the same. If so, we
499  // don't need to create a new PHI node, unless it's needed for LCSSA.
500  Value *InVal = nullptr;
501  if (!HasLoopExit) {
502  InVal = PN->getIncomingValueForBlock(Preds[0]);
503  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
504  if (!PredSet.count(PN->getIncomingBlock(i)))
505  continue;
506  if (!InVal)
507  InVal = PN->getIncomingValue(i);
508  else if (InVal != PN->getIncomingValue(i)) {
509  InVal = nullptr;
510  break;
511  }
512  }
513  }
514 
515  if (InVal) {
516  // If all incoming values for the new PHI would be the same, just don't
517  // make a new PHI. Instead, just remove the incoming values from the old
518  // PHI.
519 
520  // NOTE! This loop walks backwards for a reason! First off, this minimizes
521  // the cost of removal if we end up removing a large number of values, and
522  // second off, this ensures that the indices for the incoming values
523  // aren't invalidated when we remove one.
524  for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i)
525  if (PredSet.count(PN->getIncomingBlock(i)))
526  PN->removeIncomingValue(i, false);
527 
528  // Add an incoming value to the PHI node in the loop for the preheader
529  // edge.
530  PN->addIncoming(InVal, NewBB);
531  continue;
532  }
533 
534  // If the values coming into the block are not the same, we need a new
535  // PHI.
536  // Create the new PHI node, insert it into NewBB at the end of the block
537  PHINode *NewPHI =
538  PHINode::Create(PN->getType(), Preds.size(), PN->getName() + ".ph", BI);
539 
540  // NOTE! This loop walks backwards for a reason! First off, this minimizes
541  // the cost of removal if we end up removing a large number of values, and
542  // second off, this ensures that the indices for the incoming values aren't
543  // invalidated when we remove one.
544  for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) {
545  BasicBlock *IncomingBB = PN->getIncomingBlock(i);
546  if (PredSet.count(IncomingBB)) {
547  Value *V = PN->removeIncomingValue(i, false);
548  NewPHI->addIncoming(V, IncomingBB);
549  }
550  }
551 
552  PN->addIncoming(NewPHI, NewBB);
553  }
554 }
555 
558  const char *Suffix, DominatorTree *DT,
559  LoopInfo *LI, MemorySSAUpdater *MSSAU,
560  bool PreserveLCSSA) {
561  // Do not attempt to split that which cannot be split.
562  if (!BB->canSplitPredecessors())
563  return nullptr;
564 
565  // For the landingpads we need to act a bit differently.
566  // Delegate this work to the SplitLandingPadPredecessors.
567  if (BB->isLandingPad()) {
569  std::string NewName = std::string(Suffix) + ".split-lp";
570 
571  SplitLandingPadPredecessors(BB, Preds, Suffix, NewName.c_str(), NewBBs, DT,
572  LI, MSSAU, PreserveLCSSA);
573  return NewBBs[0];
574  }
575 
576  // Create new basic block, insert right before the original block.
578  BB->getContext(), BB->getName() + Suffix, BB->getParent(), BB);
579 
580  // The new block unconditionally branches to the old block.
581  BranchInst *BI = BranchInst::Create(BB, NewBB);
582  // Splitting the predecessors of a loop header creates a preheader block.
583  if (LI && LI->isLoopHeader(BB))
584  // Using the loop start line number prevents debuggers stepping into the
585  // loop body for this instruction.
586  BI->setDebugLoc(LI->getLoopFor(BB)->getStartLoc());
587  else
588  BI->setDebugLoc(BB->getFirstNonPHIOrDbg()->getDebugLoc());
589 
590  // Move the edges from Preds to point to NewBB instead of BB.
591  for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
592  // This is slightly more strict than necessary; the minimum requirement
593  // is that there be no more than one indirectbr branching to BB. And
594  // all BlockAddress uses would need to be updated.
595  assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&
596  "Cannot split an edge from an IndirectBrInst");
597  assert(!isa<CallBrInst>(Preds[i]->getTerminator()) &&
598  "Cannot split an edge from a CallBrInst");
599  Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB);
600  }
601 
602  // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI
603  // node becomes an incoming value for BB's phi node. However, if the Preds
604  // list is empty, we need to insert dummy entries into the PHI nodes in BB to
605  // account for the newly created predecessor.
606  if (Preds.empty()) {
607  // Insert dummy values as the incoming value.
608  for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I)
609  cast<PHINode>(I)->addIncoming(UndefValue::get(I->getType()), NewBB);
610  }
611 
612  // Update DominatorTree, LoopInfo, and LCCSA analysis information.
613  bool HasLoopExit = false;
614  UpdateAnalysisInformation(BB, NewBB, Preds, DT, LI, MSSAU, PreserveLCSSA,
615  HasLoopExit);
616 
617  if (!Preds.empty()) {
618  // Update the PHI nodes in BB with the values coming from NewBB.
619  UpdatePHINodes(BB, NewBB, Preds, BI, HasLoopExit);
620  }
621 
622  return NewBB;
623 }
624 
627  const char *Suffix1, const char *Suffix2,
629  DominatorTree *DT, LoopInfo *LI,
630  MemorySSAUpdater *MSSAU,
631  bool PreserveLCSSA) {
632  assert(OrigBB->isLandingPad() && "Trying to split a non-landing pad!");
633 
634  // Create a new basic block for OrigBB's predecessors listed in Preds. Insert
635  // it right before the original block.
636  BasicBlock *NewBB1 = BasicBlock::Create(OrigBB->getContext(),
637  OrigBB->getName() + Suffix1,
638  OrigBB->getParent(), OrigBB);
639  NewBBs.push_back(NewBB1);
640 
641  // The new block unconditionally branches to the old block.
642  BranchInst *BI1 = BranchInst::Create(OrigBB, NewBB1);
643  BI1->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc());
644 
645  // Move the edges from Preds to point to NewBB1 instead of OrigBB.
646  for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
647  // This is slightly more strict than necessary; the minimum requirement
648  // is that there be no more than one indirectbr branching to BB. And
649  // all BlockAddress uses would need to be updated.
650  assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&
651  "Cannot split an edge from an IndirectBrInst");
652  Preds[i]->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1);
653  }
654 
655  bool HasLoopExit = false;
656  UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DT, LI, MSSAU, PreserveLCSSA,
657  HasLoopExit);
658 
659  // Update the PHI nodes in OrigBB with the values coming from NewBB1.
660  UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, HasLoopExit);
661 
662  // Move the remaining edges from OrigBB to point to NewBB2.
663  SmallVector<BasicBlock*, 8> NewBB2Preds;
664  for (pred_iterator i = pred_begin(OrigBB), e = pred_end(OrigBB);
665  i != e; ) {
666  BasicBlock *Pred = *i++;
667  if (Pred == NewBB1) continue;
668  assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
669  "Cannot split an edge from an IndirectBrInst");
670  NewBB2Preds.push_back(Pred);
671  e = pred_end(OrigBB);
672  }
673 
674  BasicBlock *NewBB2 = nullptr;
675  if (!NewBB2Preds.empty()) {
676  // Create another basic block for the rest of OrigBB's predecessors.
677  NewBB2 = BasicBlock::Create(OrigBB->getContext(),
678  OrigBB->getName() + Suffix2,
679  OrigBB->getParent(), OrigBB);
680  NewBBs.push_back(NewBB2);
681 
682  // The new block unconditionally branches to the old block.
683  BranchInst *BI2 = BranchInst::Create(OrigBB, NewBB2);
684  BI2->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc());
685 
686  // Move the remaining edges from OrigBB to point to NewBB2.
687  for (BasicBlock *NewBB2Pred : NewBB2Preds)
688  NewBB2Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2);
689 
690  // Update DominatorTree, LoopInfo, and LCCSA analysis information.
691  HasLoopExit = false;
692  UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DT, LI, MSSAU,
693  PreserveLCSSA, HasLoopExit);
694 
695  // Update the PHI nodes in OrigBB with the values coming from NewBB2.
696  UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, HasLoopExit);
697  }
698 
699  LandingPadInst *LPad = OrigBB->getLandingPadInst();
700  Instruction *Clone1 = LPad->clone();
701  Clone1->setName(Twine("lpad") + Suffix1);
702  NewBB1->getInstList().insert(NewBB1->getFirstInsertionPt(), Clone1);
703 
704  if (NewBB2) {
705  Instruction *Clone2 = LPad->clone();
706  Clone2->setName(Twine("lpad") + Suffix2);
707  NewBB2->getInstList().insert(NewBB2->getFirstInsertionPt(), Clone2);
708 
709  // Create a PHI node for the two cloned landingpad instructions only
710  // if the original landingpad instruction has some uses.
711  if (!LPad->use_empty()) {
712  assert(!LPad->getType()->isTokenTy() &&
713  "Split cannot be applied if LPad is token type. Otherwise an "
714  "invalid PHINode of token type would be created.");
715  PHINode *PN = PHINode::Create(LPad->getType(), 2, "lpad.phi", LPad);
716  PN->addIncoming(Clone1, NewBB1);
717  PN->addIncoming(Clone2, NewBB2);
718  LPad->replaceAllUsesWith(PN);
719  }
720  LPad->eraseFromParent();
721  } else {
722  // There is no second clone. Just replace the landing pad with the first
723  // clone.
724  LPad->replaceAllUsesWith(Clone1);
725  LPad->eraseFromParent();
726  }
727 }
728 
730  BasicBlock *Pred,
731  DomTreeUpdater *DTU) {
732  Instruction *UncondBranch = Pred->getTerminator();
733  // Clone the return and add it to the end of the predecessor.
734  Instruction *NewRet = RI->clone();
735  Pred->getInstList().push_back(NewRet);
736 
737  // If the return instruction returns a value, and if the value was a
738  // PHI node in "BB", propagate the right value into the return.
739  for (User::op_iterator i = NewRet->op_begin(), e = NewRet->op_end();
740  i != e; ++i) {
741  Value *V = *i;
742  Instruction *NewBC = nullptr;
743  if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) {
744  // Return value might be bitcasted. Clone and insert it before the
745  // return instruction.
746  V = BCI->getOperand(0);
747  NewBC = BCI->clone();
748  Pred->getInstList().insert(NewRet->getIterator(), NewBC);
749  *i = NewBC;
750  }
751  if (PHINode *PN = dyn_cast<PHINode>(V)) {
752  if (PN->getParent() == BB) {
753  if (NewBC)
754  NewBC->setOperand(0, PN->getIncomingValueForBlock(Pred));
755  else
756  *i = PN->getIncomingValueForBlock(Pred);
757  }
758  }
759  }
760 
761  // Update any PHI nodes in the returning block to realize that we no
762  // longer branch to them.
763  BB->removePredecessor(Pred);
764  UncondBranch->eraseFromParent();
765 
766  if (DTU)
767  DTU->applyUpdates({{DominatorTree::Delete, Pred, BB}});
768 
769  return cast<ReturnInst>(NewRet);
770 }
771 
773  Instruction *SplitBefore,
774  bool Unreachable,
775  MDNode *BranchWeights,
776  DominatorTree *DT, LoopInfo *LI,
777  BasicBlock *ThenBlock) {
778  BasicBlock *Head = SplitBefore->getParent();
779  BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator());
780  Instruction *HeadOldTerm = Head->getTerminator();
781  LLVMContext &C = Head->getContext();
782  Instruction *CheckTerm;
783  bool CreateThenBlock = (ThenBlock == nullptr);
784  if (CreateThenBlock) {
785  ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
786  if (Unreachable)
787  CheckTerm = new UnreachableInst(C, ThenBlock);
788  else
789  CheckTerm = BranchInst::Create(Tail, ThenBlock);
790  CheckTerm->setDebugLoc(SplitBefore->getDebugLoc());
791  } else
792  CheckTerm = ThenBlock->getTerminator();
793  BranchInst *HeadNewTerm =
794  BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/Tail, Cond);
795  HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
796  ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
797 
798  if (DT) {
799  if (DomTreeNode *OldNode = DT->getNode(Head)) {
800  std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
801 
802  DomTreeNode *NewNode = DT->addNewBlock(Tail, Head);
803  for (DomTreeNode *Child : Children)
804  DT->changeImmediateDominator(Child, NewNode);
805 
806  // Head dominates ThenBlock.
807  if (CreateThenBlock)
808  DT->addNewBlock(ThenBlock, Head);
809  else
810  DT->changeImmediateDominator(ThenBlock, Head);
811  }
812  }
813 
814  if (LI) {
815  if (Loop *L = LI->getLoopFor(Head)) {
816  L->addBasicBlockToLoop(ThenBlock, *LI);
817  L->addBasicBlockToLoop(Tail, *LI);
818  }
819  }
820 
821  return CheckTerm;
822 }
823 
825  Instruction **ThenTerm,
826  Instruction **ElseTerm,
827  MDNode *BranchWeights) {
828  BasicBlock *Head = SplitBefore->getParent();
829  BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator());
830  Instruction *HeadOldTerm = Head->getTerminator();
831  LLVMContext &C = Head->getContext();
832  BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
833  BasicBlock *ElseBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
834  *ThenTerm = BranchInst::Create(Tail, ThenBlock);
835  (*ThenTerm)->setDebugLoc(SplitBefore->getDebugLoc());
836  *ElseTerm = BranchInst::Create(Tail, ElseBlock);
837  (*ElseTerm)->setDebugLoc(SplitBefore->getDebugLoc());
838  BranchInst *HeadNewTerm =
839  BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/ElseBlock, Cond);
840  HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
841  ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
842 }
843 
845  BasicBlock *&IfFalse) {
846  PHINode *SomePHI = dyn_cast<PHINode>(BB->begin());
847  BasicBlock *Pred1 = nullptr;
848  BasicBlock *Pred2 = nullptr;
849 
850  if (SomePHI) {
851  if (SomePHI->getNumIncomingValues() != 2)
852  return nullptr;
853  Pred1 = SomePHI->getIncomingBlock(0);
854  Pred2 = SomePHI->getIncomingBlock(1);
855  } else {
856  pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
857  if (PI == PE) // No predecessor
858  return nullptr;
859  Pred1 = *PI++;
860  if (PI == PE) // Only one predecessor
861  return nullptr;
862  Pred2 = *PI++;
863  if (PI != PE) // More than two predecessors
864  return nullptr;
865  }
866 
867  // We can only handle branches. Other control flow will be lowered to
868  // branches if possible anyway.
869  BranchInst *Pred1Br = dyn_cast<BranchInst>(Pred1->getTerminator());
870  BranchInst *Pred2Br = dyn_cast<BranchInst>(Pred2->getTerminator());
871  if (!Pred1Br || !Pred2Br)
872  return nullptr;
873 
874  // Eliminate code duplication by ensuring that Pred1Br is conditional if
875  // either are.
876  if (Pred2Br->isConditional()) {
877  // If both branches are conditional, we don't have an "if statement". In
878  // reality, we could transform this case, but since the condition will be
879  // required anyway, we stand no chance of eliminating it, so the xform is
880  // probably not profitable.
881  if (Pred1Br->isConditional())
882  return nullptr;
883 
884  std::swap(Pred1, Pred2);
885  std::swap(Pred1Br, Pred2Br);
886  }
887 
888  if (Pred1Br->isConditional()) {
889  // The only thing we have to watch out for here is to make sure that Pred2
890  // doesn't have incoming edges from other blocks. If it does, the condition
891  // doesn't dominate BB.
892  if (!Pred2->getSinglePredecessor())
893  return nullptr;
894 
895  // If we found a conditional branch predecessor, make sure that it branches
896  // to BB and Pred2Br. If it doesn't, this isn't an "if statement".
897  if (Pred1Br->getSuccessor(0) == BB &&
898  Pred1Br->getSuccessor(1) == Pred2) {
899  IfTrue = Pred1;
900  IfFalse = Pred2;
901  } else if (Pred1Br->getSuccessor(0) == Pred2 &&
902  Pred1Br->getSuccessor(1) == BB) {
903  IfTrue = Pred2;
904  IfFalse = Pred1;
905  } else {
906  // We know that one arm of the conditional goes to BB, so the other must
907  // go somewhere unrelated, and this must not be an "if statement".
908  return nullptr;
909  }
910 
911  return Pred1Br->getCondition();
912  }
913 
914  // Ok, if we got here, both predecessors end with an unconditional branch to
915  // BB. Don't panic! If both blocks only have a single (identical)
916  // predecessor, and THAT is a conditional branch, then we're all ok!
917  BasicBlock *CommonPred = Pred1->getSinglePredecessor();
918  if (CommonPred == nullptr || CommonPred != Pred2->getSinglePredecessor())
919  return nullptr;
920 
921  // Otherwise, if this is a conditional branch, then we can use it!
922  BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator());
923  if (!BI) return nullptr;
924 
925  assert(BI->isConditional() && "Two successors but not conditional?");
926  if (BI->getSuccessor(0) == Pred1) {
927  IfTrue = Pred1;
928  IfFalse = Pred2;
929  } else {
930  IfTrue = Pred2;
931  IfFalse = Pred1;
932  }
933  return BI->getCondition();
934 }
void DeleteDeadBlocks(ArrayRef< BasicBlock *> BBs, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified blocks from BB.
uint64_t CallInst * C
Return a value (possibly void), from a function.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
bool canSplitPredecessors() const
Definition: BasicBlock.cpp:371
void invalidateCachedPredecessors()
Clears the PredIteratorCache info.
void ReplaceInstWithInst(BasicBlock::InstListType &BIL, BasicBlock::iterator &BI, Instruction *I)
Replace the instruction specified by BI with the instruction specified by I.
Provides a lazy, caching interface for making common memory aliasing information queries, backed by LLVM&#39;s alias analysis passes.
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
void splitBlock(NodeT *NewBB)
splitBlock - BB is split and now it has one successor.
iterator erase(iterator where)
Definition: ilist.h:265
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr)
Attempts to merge a block into its predecessor, if possible.
iterator begin() const
Definition: ArrayRef.h:136
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
iterator end()
Definition: Function.h:682
unsigned getLoopDepth() const
Return the nesting level of this loop.
Definition: LoopInfo.h:94
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Notify the BasicBlock that the predecessor Pred is no longer able to reach it.
Definition: BasicBlock.cpp:301
void push_back(const T &Elt)
Definition: SmallVector.h:211
void moveToHeader(BlockT *BB)
This method is used to move BB (which must be part of this loop) to be the loop header of the loop (t...
Definition: LoopInfo.h:420
BasicBlock * getSuccessor(unsigned i) const
Metadata node.
Definition: Metadata.h:863
F(f)
unsigned SplitAllCriticalEdges(Function &F, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
Loop over all of the edges in the CFG, breaking critical edges as they are found. ...
Value * getCondition() const
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:137
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:32
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:299
op_iterator op_begin()
Definition: User.h:229
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:268
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Split the edge connecting specified block.
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
Option class for critical edge splitting.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:897
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:285
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:102
ReturnInst * FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, BasicBlock *Pred, DomTreeUpdater *DTU=nullptr)
This method duplicates the specified return instruction into a predecessor which ends in an unconditi...
Instruction * clone() const
Create a copy of &#39;this&#39; instruction that is identical in all ways except the following: ...
void findDbgValues(SmallVectorImpl< DbgValueInst *> &DbgValues, Value *V)
Finds the llvm.dbg.value intrinsics describing a value.
Definition: Local.cpp:1528
static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB, ArrayRef< BasicBlock *> Preds, BranchInst *BI, bool HasLoopExit)
Update the PHI nodes in OrigBB to include the values coming from NewBB.
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Definition: LoopInfoImpl.h:237
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:246
bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr)
Examine each PHI in the given block and delete it if it is dead.
This class represents a no-op cast from one type to another.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
BasicBlock * SplitCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
If this edge is a critical edge, insert a new node to split the critical edge.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
DomTreeNodeBase< NodeT > * setNewRoot(NodeT *BB)
Add a new node to the forward dominator tree and make it a new root.
void ReplaceInstWithValue(BasicBlock::InstListType &BIL, BasicBlock::iterator &BI, Value *V)
Replace all uses of an instruction (specified by BI) with a value, then remove and delete the origina...
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:291
iterator begin()
Definition: Function.h:680
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:105
void SplitLandingPadPredecessors(BasicBlock *OrigBB, ArrayRef< BasicBlock *> Preds, const char *Suffix, const char *Suffix2, SmallVectorImpl< BasicBlock *> &NewBBs, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method transforms the landing pad, OrigBB, by introducing two new basic blocks into the function...
const BasicBlock & getEntryBlock() const
Definition: Function.h:664
NodeT * getBlock() const
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock *> Preds, const char *Suffix, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
The landingpad instruction holds all of the information necessary to generate correct exception handl...
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:189
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:216
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:318
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:233
bool hasName() const
Definition: Value.h:250
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:64
Conditional or Unconditional Branch instruction.
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node&#39;s...
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:148
This function has undefined behavior.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Value * getIncomingValueForBlock(const BasicBlock *BB) const
This file contains the declarations for the subclasses of Constant, which represent the different fla...
const Instruction & front() const
Definition: BasicBlock.h:280
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:112
void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was spliced into From and To.
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
op_iterator op_end()
Definition: User.h:231
void splice(iterator where, iplist_impl &L2)
Definition: ilist.h:327
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:115
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:99
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
self_iterator getIterator()
Definition: ilist_node.h:81
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1436
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
Definition: LoopInfo.cpp:572
bool isExceptionalTerminator() const
Definition: Instruction.h:135
size_t size() const
Definition: SmallVector.h:52
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1213
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1222
bool isLandingPad() const
Return true if this basic block is a landing pad.
Definition: BasicBlock.cpp:463
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches, switches, etc.
Definition: BasicBlock.h:391
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:333
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:112
Iterator for intrusive lists based on ilist_node.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
BlockVerifier::State From
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
iterator end()
Definition: BasicBlock.h:270
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Provides information about what library functions are available for the current target.
iterator end() const
Definition: ArrayRef.h:137
bool RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI=nullptr)
If the specified value is an effectively dead PHI node, due to being a def-use chain of single-use no...
Definition: Local.cpp:517
Value * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
bool EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete all basic blocks from F that are not reachable from its entry node.
void wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New, ArrayRef< BasicBlock *> Preds, bool IdenticalEdgesWereMerged=true)
A new empty BasicBlock (New) now branches directly to Old.
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
bool isConditional() const
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...
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:124
unsigned getNumIncomingValues() const
Return the number of incoming edges.
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Implements a dense probed hash-table based set with some number of buckets stored inline...
Definition: DenseSet.h:267
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
void push_back(pointer val)
Definition: ilist.h:311
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:89
void FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
bool isLoopHeader(const BlockT *BB) const
Definition: LoopInfo.h:910
void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, Instruction **ThenTerm, Instruction **ElseTerm, MDNode *BranchWeights=nullptr)
SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, but also creates the ElseBlock...
LoopT * getParentLoop() const
Definition: LoopInfo.h:103
unsigned succ_size(const Instruction *I)
Definition: CFG.h:256
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
unsigned GetSuccessorNumber(const BasicBlock *BB, const BasicBlock *Succ)
Search for the specified successor of basic block BB and return its position in the terminator instru...
Definition: CFG.cpp:72
iterator insert(iterator where, pointer New)
Definition: ilist.h:226
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:321
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:506
bool isTokenTy() const
Return true if this is &#39;token&#39;.
Definition: Type.h:193
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink &#39;this&#39; from the containing function and delete it.
Definition: BasicBlock.cpp:114
#define I(x, y, z)
Definition: MD5.cpp:58
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was merged into To.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:324
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="")
Split the basic block into two basic blocks at the specified instruction.
Definition: BasicBlock.cpp:407
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:72
void removeInstruction(Instruction *InstToRemove)
Removes an instruction from the dependence analysis, updating the dependence of instructions that pre...
succ_range successors(Instruction *I)
Definition: CFG.h:259
static const Function * getParent(const Value *V)
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Split the specified block at the specified instruction - everything before SplitPt stays in Old and e...
const LandingPadInst * getLandingPadInst() const
Return the landingpad instruction associated with the landing pad.
Definition: BasicBlock.cpp:468
const Instruction * getFirstNonPHIOrDbg() const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic...
Definition: BasicBlock.cpp:196
void pop_back()
Definition: ilist.h:316
#define LLVM_DEBUG(X)
Definition: Debug.h:122
void DetatchDeadBlocks(ArrayRef< BasicBlock *> BBs, SmallVectorImpl< DominatorTree::UpdateType > *Updates, bool KeepOneInputPHIs=false)
Replace contents of every block in BBs with single unreachable instruction.
bool use_empty() const
Definition: Value.h:322
void removeBlock(BlockT *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
Definition: LoopInfo.h:956
Instruction * SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB, ArrayRef< BasicBlock *> Preds, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA, bool &HasLoopExit)
Update DominatorTree, LoopInfo, and LCCSA analysis information.
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:143
const BasicBlock * getParent() const
Definition: Instruction.h:66
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
Definition: BasicBlock.cpp:276