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  bool PredecessorWithTwoSuccessors) {
175  if (BB->hasAddressTaken())
176  return false;
177 
178  // Can't merge if there are multiple predecessors, or no predecessors.
179  BasicBlock *PredBB = BB->getUniquePredecessor();
180  if (!PredBB) return false;
181 
182  // Don't break self-loops.
183  if (PredBB == BB) return false;
184  // Don't break unwinding instructions.
185  if (PredBB->getTerminator()->isExceptionalTerminator())
186  return false;
187 
188  // Can't merge if there are multiple distinct successors.
189  if (!PredecessorWithTwoSuccessors && PredBB->getUniqueSuccessor() != BB)
190  return false;
191 
192  // Currently only allow PredBB to have two predecessors, one being BB.
193  // Update BI to branch to BB's only successor instead of BB.
194  BranchInst *PredBB_BI;
195  BasicBlock *NewSucc = nullptr;
196  unsigned FallThruPath;
197  if (PredecessorWithTwoSuccessors) {
198  if (!(PredBB_BI = dyn_cast<BranchInst>(PredBB->getTerminator())))
199  return false;
200  BranchInst *BB_JmpI = dyn_cast<BranchInst>(BB->getTerminator());
201  if (!BB_JmpI || !BB_JmpI->isUnconditional())
202  return false;
203  NewSucc = BB_JmpI->getSuccessor(0);
204  FallThruPath = PredBB_BI->getSuccessor(0) == BB ? 0 : 1;
205  }
206 
207  // Can't merge if there is PHI loop.
208  for (PHINode &PN : BB->phis())
209  for (Value *IncValue : PN.incoming_values())
210  if (IncValue == &PN)
211  return false;
212 
213  LLVM_DEBUG(dbgs() << "Merging: " << BB->getName() << " into "
214  << PredBB->getName() << "\n");
215 
216  // Begin by getting rid of unneeded PHIs.
217  SmallVector<AssertingVH<Value>, 4> IncomingValues;
218  if (isa<PHINode>(BB->front())) {
219  for (PHINode &PN : BB->phis())
220  if (!isa<PHINode>(PN.getIncomingValue(0)) ||
221  cast<PHINode>(PN.getIncomingValue(0))->getParent() != BB)
222  IncomingValues.push_back(PN.getIncomingValue(0));
223  FoldSingleEntryPHINodes(BB, MemDep);
224  }
225 
226  // DTU update: Collect all the edges that exit BB.
227  // These dominator edges will be redirected from Pred.
228  std::vector<DominatorTree::UpdateType> Updates;
229  if (DTU) {
230  Updates.reserve(1 + (2 * succ_size(BB)));
231  // Add insert edges first. Experimentally, for the particular case of two
232  // blocks that can be merged, with a single successor and single predecessor
233  // respectively, it is beneficial to have all insert updates first. Deleting
234  // edges first may lead to unreachable blocks, followed by inserting edges
235  // making the blocks reachable again. Such DT updates lead to high compile
236  // times. We add inserts before deletes here to reduce compile time.
237  for (auto I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
238  // This successor of BB may already have PredBB as a predecessor.
239  if (llvm::find(successors(PredBB), *I) == succ_end(PredBB))
240  Updates.push_back({DominatorTree::Insert, PredBB, *I});
241  for (auto I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
242  Updates.push_back({DominatorTree::Delete, BB, *I});
243  Updates.push_back({DominatorTree::Delete, PredBB, BB});
244  }
245 
246  Instruction *PTI = PredBB->getTerminator();
247  Instruction *STI = BB->getTerminator();
248  Instruction *Start = &*BB->begin();
249  // If there's nothing to move, mark the starting instruction as the last
250  // instruction in the block.
251  if (Start == STI)
252  Start = PTI;
253 
254  // Move all definitions in the successor to the predecessor...
255  PredBB->getInstList().splice(PTI->getIterator(), BB->getInstList(),
256  BB->begin(), STI->getIterator());
257 
258  if (MSSAU)
259  MSSAU->moveAllAfterMergeBlocks(BB, PredBB, Start);
260 
261  // Make all PHI nodes that referred to BB now refer to Pred as their
262  // source...
263  BB->replaceAllUsesWith(PredBB);
264 
265  if (PredecessorWithTwoSuccessors) {
266  // Delete the unconditional branch from BB.
267  BB->getInstList().pop_back();
268 
269  // Update branch in the predecessor.
270  PredBB_BI->setSuccessor(FallThruPath, NewSucc);
271  } else {
272  // Delete the unconditional branch from the predecessor.
273  PredBB->getInstList().pop_back();
274 
275  // Move terminator instruction.
276  PredBB->getInstList().splice(PredBB->end(), BB->getInstList());
277  }
278  // Add unreachable to now empty BB.
279  new UnreachableInst(BB->getContext(), BB);
280 
281  // Eliminate duplicate dbg.values describing the entry PHI node post-splice.
282  for (auto Incoming : IncomingValues) {
283  if (isa<Instruction>(*Incoming)) {
286  DbgValueSet;
287  llvm::findDbgValues(DbgValues, Incoming);
288  for (auto &DVI : DbgValues) {
289  auto R = DbgValueSet.insert({DVI->getVariable(), DVI->getExpression()});
290  if (!R.second)
291  DVI->eraseFromParent();
292  }
293  }
294  }
295 
296  // Inherit predecessors name if it exists.
297  if (!PredBB->hasName())
298  PredBB->takeName(BB);
299 
300  if (LI)
301  LI->removeBlock(BB);
302 
303  if (MemDep)
305 
306  // Finally, erase the old block and update dominator info.
307  if (DTU) {
308  assert(BB->getInstList().size() == 1 &&
309  isa<UnreachableInst>(BB->getTerminator()) &&
310  "The successor list of BB isn't empty before "
311  "applying corresponding DTU updates.");
312  DTU->applyUpdatesPermissive(Updates);
313  DTU->deleteBB(BB);
314  } else {
315  BB->eraseFromParent(); // Nuke BB if DTU is nullptr.
316  }
317 
318  return true;
319 }
320 
322  BasicBlock::iterator &BI, Value *V) {
323  Instruction &I = *BI;
324  // Replaces all of the uses of the instruction with uses of the value
325  I.replaceAllUsesWith(V);
326 
327  // Make sure to propagate a name if there is one already.
328  if (I.hasName() && !V->hasName())
329  V->takeName(&I);
330 
331  // Delete the unnecessary instruction now...
332  BI = BIL.erase(BI);
333 }
334 
337  assert(I->getParent() == nullptr &&
338  "ReplaceInstWithInst: Instruction already inserted into basic block!");
339 
340  // Copy debug location to newly added instruction, if it wasn't already set
341  // by the caller.
342  if (!I->getDebugLoc())
343  I->setDebugLoc(BI->getDebugLoc());
344 
345  // Insert the new instruction into the basic block...
346  BasicBlock::iterator New = BIL.insert(BI, I);
347 
348  // Replace all uses of the old instruction, and delete it.
349  ReplaceInstWithValue(BIL, BI, I);
350 
351  // Move BI back to point to the newly inserted instruction
352  BI = New;
353 }
354 
356  BasicBlock::iterator BI(From);
357  ReplaceInstWithInst(From->getParent()->getInstList(), BI, To);
358 }
359 
361  LoopInfo *LI, MemorySSAUpdater *MSSAU) {
362  unsigned SuccNum = GetSuccessorNumber(BB, Succ);
363 
364  // If this is a critical edge, let SplitCriticalEdge do it.
365  Instruction *LatchTerm = BB->getTerminator();
366  if (SplitCriticalEdge(
367  LatchTerm, SuccNum,
368  CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA()))
369  return LatchTerm->getSuccessor(SuccNum);
370 
371  // If the edge isn't critical, then BB has a single successor or Succ has a
372  // single pred. Split the block.
373  if (BasicBlock *SP = Succ->getSinglePredecessor()) {
374  // If the successor only has a single pred, split the top of the successor
375  // block.
376  assert(SP == BB && "CFG broken");
377  SP = nullptr;
378  return SplitBlock(Succ, &Succ->front(), DT, LI, MSSAU);
379  }
380 
381  // Otherwise, if BB has a single successor, split it at the bottom of the
382  // block.
383  assert(BB->getTerminator()->getNumSuccessors() == 1 &&
384  "Should have a single succ!");
385  return SplitBlock(BB, BB->getTerminator(), DT, LI, MSSAU);
386 }
387 
388 unsigned
390  const CriticalEdgeSplittingOptions &Options) {
391  unsigned NumBroken = 0;
392  for (BasicBlock &BB : F) {
393  Instruction *TI = BB.getTerminator();
394  if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI))
395  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
396  if (SplitCriticalEdge(TI, i, Options))
397  ++NumBroken;
398  }
399  return NumBroken;
400 }
401 
403  DominatorTree *DT, LoopInfo *LI,
404  MemorySSAUpdater *MSSAU, const Twine &BBName) {
405  BasicBlock::iterator SplitIt = SplitPt->getIterator();
406  while (isa<PHINode>(SplitIt) || SplitIt->isEHPad())
407  ++SplitIt;
408  std::string Name = BBName.str();
409  BasicBlock *New = Old->splitBasicBlock(
410  SplitIt, Name.empty() ? Old->getName() + ".split" : Name);
411 
412  // The new block lives in whichever loop the old one did. This preserves
413  // LCSSA as well, because we force the split point to be after any PHI nodes.
414  if (LI)
415  if (Loop *L = LI->getLoopFor(Old))
416  L->addBasicBlockToLoop(New, *LI);
417 
418  if (DT)
419  // Old dominates New. New node dominates all other nodes dominated by Old.
420  if (DomTreeNode *OldNode = DT->getNode(Old)) {
421  std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
422 
423  DomTreeNode *NewNode = DT->addNewBlock(New, Old);
424  for (DomTreeNode *I : Children)
425  DT->changeImmediateDominator(I, NewNode);
426  }
427 
428  // Move MemoryAccesses still tracked in Old, but part of New now.
429  // Update accesses in successor blocks accordingly.
430  if (MSSAU)
431  MSSAU->moveAllAfterSpliceBlocks(Old, New, &*(New->begin()));
432 
433  return New;
434 }
435 
436 /// Update DominatorTree, LoopInfo, and LCCSA analysis information.
439  DominatorTree *DT, LoopInfo *LI,
440  MemorySSAUpdater *MSSAU,
441  bool PreserveLCSSA, bool &HasLoopExit) {
442  // Update dominator tree if available.
443  if (DT) {
444  if (OldBB == DT->getRootNode()->getBlock()) {
445  assert(NewBB == &NewBB->getParent()->getEntryBlock());
446  DT->setNewRoot(NewBB);
447  } else {
448  // Split block expects NewBB to have a non-empty set of predecessors.
449  DT->splitBlock(NewBB);
450  }
451  }
452 
453  // Update MemoryPhis after split if MemorySSA is available
454  if (MSSAU)
455  MSSAU->wireOldPredecessorsToNewImmediatePredecessor(OldBB, NewBB, Preds);
456 
457  // The rest of the logic is only relevant for updating the loop structures.
458  if (!LI)
459  return;
460 
461  assert(DT && "DT should be available to update LoopInfo!");
462  Loop *L = LI->getLoopFor(OldBB);
463 
464  // If we need to preserve loop analyses, collect some information about how
465  // this split will affect loops.
466  bool IsLoopEntry = !!L;
467  bool SplitMakesNewLoopHeader = false;
468  for (BasicBlock *Pred : Preds) {
469  // Preds that are not reachable from entry should not be used to identify if
470  // OldBB is a loop entry or if SplitMakesNewLoopHeader. Unreachable blocks
471  // are not within any loops, so we incorrectly mark SplitMakesNewLoopHeader
472  // as true and make the NewBB the header of some loop. This breaks LI.
473  if (!DT->isReachableFromEntry(Pred))
474  continue;
475  // If we need to preserve LCSSA, determine if any of the preds is a loop
476  // exit.
477  if (PreserveLCSSA)
478  if (Loop *PL = LI->getLoopFor(Pred))
479  if (!PL->contains(OldBB))
480  HasLoopExit = true;
481 
482  // If we need to preserve LoopInfo, note whether any of the preds crosses
483  // an interesting loop boundary.
484  if (!L)
485  continue;
486  if (L->contains(Pred))
487  IsLoopEntry = false;
488  else
489  SplitMakesNewLoopHeader = true;
490  }
491 
492  // Unless we have a loop for OldBB, nothing else to do here.
493  if (!L)
494  return;
495 
496  if (IsLoopEntry) {
497  // Add the new block to the nearest enclosing loop (and not an adjacent
498  // loop). To find this, examine each of the predecessors and determine which
499  // loops enclose them, and select the most-nested loop which contains the
500  // loop containing the block being split.
501  Loop *InnermostPredLoop = nullptr;
502  for (BasicBlock *Pred : Preds) {
503  if (Loop *PredLoop = LI->getLoopFor(Pred)) {
504  // Seek a loop which actually contains the block being split (to avoid
505  // adjacent loops).
506  while (PredLoop && !PredLoop->contains(OldBB))
507  PredLoop = PredLoop->getParentLoop();
508 
509  // Select the most-nested of these loops which contains the block.
510  if (PredLoop && PredLoop->contains(OldBB) &&
511  (!InnermostPredLoop ||
512  InnermostPredLoop->getLoopDepth() < PredLoop->getLoopDepth()))
513  InnermostPredLoop = PredLoop;
514  }
515  }
516 
517  if (InnermostPredLoop)
518  InnermostPredLoop->addBasicBlockToLoop(NewBB, *LI);
519  } else {
520  L->addBasicBlockToLoop(NewBB, *LI);
521  if (SplitMakesNewLoopHeader)
522  L->moveToHeader(NewBB);
523  }
524 }
525 
526 /// Update the PHI nodes in OrigBB to include the values coming from NewBB.
527 /// This also updates AliasAnalysis, if available.
528 static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB,
530  bool HasLoopExit) {
531  // Otherwise, create a new PHI node in NewBB for each PHI node in OrigBB.
532  SmallPtrSet<BasicBlock *, 16> PredSet(Preds.begin(), Preds.end());
533  for (BasicBlock::iterator I = OrigBB->begin(); isa<PHINode>(I); ) {
534  PHINode *PN = cast<PHINode>(I++);
535 
536  // Check to see if all of the values coming in are the same. If so, we
537  // don't need to create a new PHI node, unless it's needed for LCSSA.
538  Value *InVal = nullptr;
539  if (!HasLoopExit) {
540  InVal = PN->getIncomingValueForBlock(Preds[0]);
541  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
542  if (!PredSet.count(PN->getIncomingBlock(i)))
543  continue;
544  if (!InVal)
545  InVal = PN->getIncomingValue(i);
546  else if (InVal != PN->getIncomingValue(i)) {
547  InVal = nullptr;
548  break;
549  }
550  }
551  }
552 
553  if (InVal) {
554  // If all incoming values for the new PHI would be the same, just don't
555  // make a new PHI. Instead, just remove the incoming values from the old
556  // PHI.
557 
558  // NOTE! This loop walks backwards for a reason! First off, this minimizes
559  // the cost of removal if we end up removing a large number of values, and
560  // second off, this ensures that the indices for the incoming values
561  // aren't invalidated when we remove one.
562  for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i)
563  if (PredSet.count(PN->getIncomingBlock(i)))
564  PN->removeIncomingValue(i, false);
565 
566  // Add an incoming value to the PHI node in the loop for the preheader
567  // edge.
568  PN->addIncoming(InVal, NewBB);
569  continue;
570  }
571 
572  // If the values coming into the block are not the same, we need a new
573  // PHI.
574  // Create the new PHI node, insert it into NewBB at the end of the block
575  PHINode *NewPHI =
576  PHINode::Create(PN->getType(), Preds.size(), PN->getName() + ".ph", BI);
577 
578  // NOTE! This loop walks backwards for a reason! First off, this minimizes
579  // the cost of removal if we end up removing a large number of values, and
580  // second off, this ensures that the indices for the incoming values aren't
581  // invalidated when we remove one.
582  for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) {
583  BasicBlock *IncomingBB = PN->getIncomingBlock(i);
584  if (PredSet.count(IncomingBB)) {
585  Value *V = PN->removeIncomingValue(i, false);
586  NewPHI->addIncoming(V, IncomingBB);
587  }
588  }
589 
590  PN->addIncoming(NewPHI, NewBB);
591  }
592 }
593 
596  const char *Suffix, DominatorTree *DT,
597  LoopInfo *LI, MemorySSAUpdater *MSSAU,
598  bool PreserveLCSSA) {
599  // Do not attempt to split that which cannot be split.
600  if (!BB->canSplitPredecessors())
601  return nullptr;
602 
603  // For the landingpads we need to act a bit differently.
604  // Delegate this work to the SplitLandingPadPredecessors.
605  if (BB->isLandingPad()) {
607  std::string NewName = std::string(Suffix) + ".split-lp";
608 
609  SplitLandingPadPredecessors(BB, Preds, Suffix, NewName.c_str(), NewBBs, DT,
610  LI, MSSAU, PreserveLCSSA);
611  return NewBBs[0];
612  }
613 
614  // Create new basic block, insert right before the original block.
616  BB->getContext(), BB->getName() + Suffix, BB->getParent(), BB);
617 
618  // The new block unconditionally branches to the old block.
619  BranchInst *BI = BranchInst::Create(BB, NewBB);
620  // Splitting the predecessors of a loop header creates a preheader block.
621  if (LI && LI->isLoopHeader(BB))
622  // Using the loop start line number prevents debuggers stepping into the
623  // loop body for this instruction.
624  BI->setDebugLoc(LI->getLoopFor(BB)->getStartLoc());
625  else
626  BI->setDebugLoc(BB->getFirstNonPHIOrDbg()->getDebugLoc());
627 
628  // Move the edges from Preds to point to NewBB instead of BB.
629  for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
630  // This is slightly more strict than necessary; the minimum requirement
631  // is that there be no more than one indirectbr branching to BB. And
632  // all BlockAddress uses would need to be updated.
633  assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&
634  "Cannot split an edge from an IndirectBrInst");
635  assert(!isa<CallBrInst>(Preds[i]->getTerminator()) &&
636  "Cannot split an edge from a CallBrInst");
637  Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB);
638  }
639 
640  // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI
641  // node becomes an incoming value for BB's phi node. However, if the Preds
642  // list is empty, we need to insert dummy entries into the PHI nodes in BB to
643  // account for the newly created predecessor.
644  if (Preds.empty()) {
645  // Insert dummy values as the incoming value.
646  for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I)
647  cast<PHINode>(I)->addIncoming(UndefValue::get(I->getType()), NewBB);
648  }
649 
650  // Update DominatorTree, LoopInfo, and LCCSA analysis information.
651  bool HasLoopExit = false;
652  UpdateAnalysisInformation(BB, NewBB, Preds, DT, LI, MSSAU, PreserveLCSSA,
653  HasLoopExit);
654 
655  if (!Preds.empty()) {
656  // Update the PHI nodes in BB with the values coming from NewBB.
657  UpdatePHINodes(BB, NewBB, Preds, BI, HasLoopExit);
658  }
659 
660  return NewBB;
661 }
662 
665  const char *Suffix1, const char *Suffix2,
667  DominatorTree *DT, LoopInfo *LI,
668  MemorySSAUpdater *MSSAU,
669  bool PreserveLCSSA) {
670  assert(OrigBB->isLandingPad() && "Trying to split a non-landing pad!");
671 
672  // Create a new basic block for OrigBB's predecessors listed in Preds. Insert
673  // it right before the original block.
674  BasicBlock *NewBB1 = BasicBlock::Create(OrigBB->getContext(),
675  OrigBB->getName() + Suffix1,
676  OrigBB->getParent(), OrigBB);
677  NewBBs.push_back(NewBB1);
678 
679  // The new block unconditionally branches to the old block.
680  BranchInst *BI1 = BranchInst::Create(OrigBB, NewBB1);
681  BI1->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc());
682 
683  // Move the edges from Preds to point to NewBB1 instead of OrigBB.
684  for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
685  // This is slightly more strict than necessary; the minimum requirement
686  // is that there be no more than one indirectbr branching to BB. And
687  // all BlockAddress uses would need to be updated.
688  assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&
689  "Cannot split an edge from an IndirectBrInst");
690  Preds[i]->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1);
691  }
692 
693  bool HasLoopExit = false;
694  UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DT, LI, MSSAU, PreserveLCSSA,
695  HasLoopExit);
696 
697  // Update the PHI nodes in OrigBB with the values coming from NewBB1.
698  UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, HasLoopExit);
699 
700  // Move the remaining edges from OrigBB to point to NewBB2.
701  SmallVector<BasicBlock*, 8> NewBB2Preds;
702  for (pred_iterator i = pred_begin(OrigBB), e = pred_end(OrigBB);
703  i != e; ) {
704  BasicBlock *Pred = *i++;
705  if (Pred == NewBB1) continue;
706  assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
707  "Cannot split an edge from an IndirectBrInst");
708  NewBB2Preds.push_back(Pred);
709  e = pred_end(OrigBB);
710  }
711 
712  BasicBlock *NewBB2 = nullptr;
713  if (!NewBB2Preds.empty()) {
714  // Create another basic block for the rest of OrigBB's predecessors.
715  NewBB2 = BasicBlock::Create(OrigBB->getContext(),
716  OrigBB->getName() + Suffix2,
717  OrigBB->getParent(), OrigBB);
718  NewBBs.push_back(NewBB2);
719 
720  // The new block unconditionally branches to the old block.
721  BranchInst *BI2 = BranchInst::Create(OrigBB, NewBB2);
722  BI2->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc());
723 
724  // Move the remaining edges from OrigBB to point to NewBB2.
725  for (BasicBlock *NewBB2Pred : NewBB2Preds)
726  NewBB2Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2);
727 
728  // Update DominatorTree, LoopInfo, and LCCSA analysis information.
729  HasLoopExit = false;
730  UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DT, LI, MSSAU,
731  PreserveLCSSA, HasLoopExit);
732 
733  // Update the PHI nodes in OrigBB with the values coming from NewBB2.
734  UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, HasLoopExit);
735  }
736 
737  LandingPadInst *LPad = OrigBB->getLandingPadInst();
738  Instruction *Clone1 = LPad->clone();
739  Clone1->setName(Twine("lpad") + Suffix1);
740  NewBB1->getInstList().insert(NewBB1->getFirstInsertionPt(), Clone1);
741 
742  if (NewBB2) {
743  Instruction *Clone2 = LPad->clone();
744  Clone2->setName(Twine("lpad") + Suffix2);
745  NewBB2->getInstList().insert(NewBB2->getFirstInsertionPt(), Clone2);
746 
747  // Create a PHI node for the two cloned landingpad instructions only
748  // if the original landingpad instruction has some uses.
749  if (!LPad->use_empty()) {
750  assert(!LPad->getType()->isTokenTy() &&
751  "Split cannot be applied if LPad is token type. Otherwise an "
752  "invalid PHINode of token type would be created.");
753  PHINode *PN = PHINode::Create(LPad->getType(), 2, "lpad.phi", LPad);
754  PN->addIncoming(Clone1, NewBB1);
755  PN->addIncoming(Clone2, NewBB2);
756  LPad->replaceAllUsesWith(PN);
757  }
758  LPad->eraseFromParent();
759  } else {
760  // There is no second clone. Just replace the landing pad with the first
761  // clone.
762  LPad->replaceAllUsesWith(Clone1);
763  LPad->eraseFromParent();
764  }
765 }
766 
768  BasicBlock *Pred,
769  DomTreeUpdater *DTU) {
770  Instruction *UncondBranch = Pred->getTerminator();
771  // Clone the return and add it to the end of the predecessor.
772  Instruction *NewRet = RI->clone();
773  Pred->getInstList().push_back(NewRet);
774 
775  // If the return instruction returns a value, and if the value was a
776  // PHI node in "BB", propagate the right value into the return.
777  for (User::op_iterator i = NewRet->op_begin(), e = NewRet->op_end();
778  i != e; ++i) {
779  Value *V = *i;
780  Instruction *NewBC = nullptr;
781  if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) {
782  // Return value might be bitcasted. Clone and insert it before the
783  // return instruction.
784  V = BCI->getOperand(0);
785  NewBC = BCI->clone();
786  Pred->getInstList().insert(NewRet->getIterator(), NewBC);
787  *i = NewBC;
788  }
789  if (PHINode *PN = dyn_cast<PHINode>(V)) {
790  if (PN->getParent() == BB) {
791  if (NewBC)
792  NewBC->setOperand(0, PN->getIncomingValueForBlock(Pred));
793  else
794  *i = PN->getIncomingValueForBlock(Pred);
795  }
796  }
797  }
798 
799  // Update any PHI nodes in the returning block to realize that we no
800  // longer branch to them.
801  BB->removePredecessor(Pred);
802  UncondBranch->eraseFromParent();
803 
804  if (DTU)
805  DTU->applyUpdates({{DominatorTree::Delete, Pred, BB}});
806 
807  return cast<ReturnInst>(NewRet);
808 }
809 
811  Instruction *SplitBefore,
812  bool Unreachable,
813  MDNode *BranchWeights,
814  DominatorTree *DT, LoopInfo *LI,
815  BasicBlock *ThenBlock) {
816  BasicBlock *Head = SplitBefore->getParent();
817  BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator());
818  Instruction *HeadOldTerm = Head->getTerminator();
819  LLVMContext &C = Head->getContext();
820  Instruction *CheckTerm;
821  bool CreateThenBlock = (ThenBlock == nullptr);
822  if (CreateThenBlock) {
823  ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
824  if (Unreachable)
825  CheckTerm = new UnreachableInst(C, ThenBlock);
826  else
827  CheckTerm = BranchInst::Create(Tail, ThenBlock);
828  CheckTerm->setDebugLoc(SplitBefore->getDebugLoc());
829  } else
830  CheckTerm = ThenBlock->getTerminator();
831  BranchInst *HeadNewTerm =
832  BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/Tail, Cond);
833  HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
834  ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
835 
836  if (DT) {
837  if (DomTreeNode *OldNode = DT->getNode(Head)) {
838  std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
839 
840  DomTreeNode *NewNode = DT->addNewBlock(Tail, Head);
841  for (DomTreeNode *Child : Children)
842  DT->changeImmediateDominator(Child, NewNode);
843 
844  // Head dominates ThenBlock.
845  if (CreateThenBlock)
846  DT->addNewBlock(ThenBlock, Head);
847  else
848  DT->changeImmediateDominator(ThenBlock, Head);
849  }
850  }
851 
852  if (LI) {
853  if (Loop *L = LI->getLoopFor(Head)) {
854  L->addBasicBlockToLoop(ThenBlock, *LI);
855  L->addBasicBlockToLoop(Tail, *LI);
856  }
857  }
858 
859  return CheckTerm;
860 }
861 
863  Instruction **ThenTerm,
864  Instruction **ElseTerm,
865  MDNode *BranchWeights) {
866  BasicBlock *Head = SplitBefore->getParent();
867  BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator());
868  Instruction *HeadOldTerm = Head->getTerminator();
869  LLVMContext &C = Head->getContext();
870  BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
871  BasicBlock *ElseBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
872  *ThenTerm = BranchInst::Create(Tail, ThenBlock);
873  (*ThenTerm)->setDebugLoc(SplitBefore->getDebugLoc());
874  *ElseTerm = BranchInst::Create(Tail, ElseBlock);
875  (*ElseTerm)->setDebugLoc(SplitBefore->getDebugLoc());
876  BranchInst *HeadNewTerm =
877  BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/ElseBlock, Cond);
878  HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
879  ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
880 }
881 
883  BasicBlock *&IfFalse) {
884  PHINode *SomePHI = dyn_cast<PHINode>(BB->begin());
885  BasicBlock *Pred1 = nullptr;
886  BasicBlock *Pred2 = nullptr;
887 
888  if (SomePHI) {
889  if (SomePHI->getNumIncomingValues() != 2)
890  return nullptr;
891  Pred1 = SomePHI->getIncomingBlock(0);
892  Pred2 = SomePHI->getIncomingBlock(1);
893  } else {
894  pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
895  if (PI == PE) // No predecessor
896  return nullptr;
897  Pred1 = *PI++;
898  if (PI == PE) // Only one predecessor
899  return nullptr;
900  Pred2 = *PI++;
901  if (PI != PE) // More than two predecessors
902  return nullptr;
903  }
904 
905  // We can only handle branches. Other control flow will be lowered to
906  // branches if possible anyway.
907  BranchInst *Pred1Br = dyn_cast<BranchInst>(Pred1->getTerminator());
908  BranchInst *Pred2Br = dyn_cast<BranchInst>(Pred2->getTerminator());
909  if (!Pred1Br || !Pred2Br)
910  return nullptr;
911 
912  // Eliminate code duplication by ensuring that Pred1Br is conditional if
913  // either are.
914  if (Pred2Br->isConditional()) {
915  // If both branches are conditional, we don't have an "if statement". In
916  // reality, we could transform this case, but since the condition will be
917  // required anyway, we stand no chance of eliminating it, so the xform is
918  // probably not profitable.
919  if (Pred1Br->isConditional())
920  return nullptr;
921 
922  std::swap(Pred1, Pred2);
923  std::swap(Pred1Br, Pred2Br);
924  }
925 
926  if (Pred1Br->isConditional()) {
927  // The only thing we have to watch out for here is to make sure that Pred2
928  // doesn't have incoming edges from other blocks. If it does, the condition
929  // doesn't dominate BB.
930  if (!Pred2->getSinglePredecessor())
931  return nullptr;
932 
933  // If we found a conditional branch predecessor, make sure that it branches
934  // to BB and Pred2Br. If it doesn't, this isn't an "if statement".
935  if (Pred1Br->getSuccessor(0) == BB &&
936  Pred1Br->getSuccessor(1) == Pred2) {
937  IfTrue = Pred1;
938  IfFalse = Pred2;
939  } else if (Pred1Br->getSuccessor(0) == Pred2 &&
940  Pred1Br->getSuccessor(1) == BB) {
941  IfTrue = Pred2;
942  IfFalse = Pred1;
943  } else {
944  // We know that one arm of the conditional goes to BB, so the other must
945  // go somewhere unrelated, and this must not be an "if statement".
946  return nullptr;
947  }
948 
949  return Pred1Br->getCondition();
950  }
951 
952  // Ok, if we got here, both predecessors end with an unconditional branch to
953  // BB. Don't panic! If both blocks only have a single (identical)
954  // predecessor, and THAT is a conditional branch, then we're all ok!
955  BasicBlock *CommonPred = Pred1->getSinglePredecessor();
956  if (CommonPred == nullptr || CommonPred != Pred2->getSinglePredecessor())
957  return nullptr;
958 
959  // Otherwise, if this is a conditional branch, then we can use it!
960  BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator());
961  if (!BI) return nullptr;
962 
963  assert(BI->isConditional() && "Two successors but not conditional?");
964  if (BI->getSuccessor(0) == Pred1) {
965  IfTrue = Pred1;
966  IfFalse = Pred2;
967  } else {
968  IfTrue = Pred2;
969  IfFalse = Pred1;
970  }
971  return BI->getCondition();
972 }
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:378
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
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:687
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
unsigned getLoopDepth() const
Return the nesting level of this loop.
Definition: LoopInfo.h:97
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Notify the BasicBlock that the predecessor Pred is no longer able to reach it.
Definition: BasicBlock.cpp:308
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:423
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:144
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the specified block at the specified instruction - everything before SplitPt stays in Old and e...
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:273
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false)
Attempts to merge a block into its predecessor, if possible.
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:928
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:1514
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:246
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Definition: LoopInfoImpl.h:235
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:253
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:685
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:669
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:196
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:223
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:328
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:240
bool hasName() const
Definition: Value.h:252
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:285
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
constexpr double e
Definition: MathExtras.h:57
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:1446
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
Definition: LoopInfo.cpp:611
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:1186
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1222
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
bool isLandingPad() const
Return true if this basic block is a landing pad.
Definition: BasicBlock.cpp:470
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches, switches, etc.
Definition: BasicBlock.h:396
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:338
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:115
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:275
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:523
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:941
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:106
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:331
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:509
bool isTokenTy() const
Return true if this is &#39;token&#39;.
Definition: Type.h:194
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:121
#define I(x, y, z)
Definition: MD5.cpp:58
Tail - This calling convention attemps to make calls as fast as possible while guaranteeing that tail...
Definition: CallingConv.h:81
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:329
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="")
Split the basic block into two basic blocks at the specified instruction.
Definition: BasicBlock.cpp:414
bool isUnconditional() const
std::string str() const
Return the twine contents as a std::string.
Definition: Twine.cpp:17
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:74
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)
const LandingPadInst * getLandingPadInst() const
Return the landingpad instruction associated with the landing pad.
Definition: BasicBlock.cpp:475
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:203
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:343
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:987
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:283