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, const Twine &BBName) {
369  BasicBlock::iterator SplitIt = SplitPt->getIterator();
370  while (isa<PHINode>(SplitIt) || SplitIt->isEHPad())
371  ++SplitIt;
372  std::string Name = BBName.str();
373  BasicBlock *New = Old->splitBasicBlock(
374  SplitIt, Name.empty() ? Old->getName() + ".split" : Name);
375 
376  // The new block lives in whichever loop the old one did. This preserves
377  // LCSSA as well, because we force the split point to be after any PHI nodes.
378  if (LI)
379  if (Loop *L = LI->getLoopFor(Old))
380  L->addBasicBlockToLoop(New, *LI);
381 
382  if (DT)
383  // Old dominates New. New node dominates all other nodes dominated by Old.
384  if (DomTreeNode *OldNode = DT->getNode(Old)) {
385  std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
386 
387  DomTreeNode *NewNode = DT->addNewBlock(New, Old);
388  for (DomTreeNode *I : Children)
389  DT->changeImmediateDominator(I, NewNode);
390  }
391 
392  // Move MemoryAccesses still tracked in Old, but part of New now.
393  // Update accesses in successor blocks accordingly.
394  if (MSSAU)
395  MSSAU->moveAllAfterSpliceBlocks(Old, New, &*(New->begin()));
396 
397  return New;
398 }
399 
400 /// Update DominatorTree, LoopInfo, and LCCSA analysis information.
403  DominatorTree *DT, LoopInfo *LI,
404  MemorySSAUpdater *MSSAU,
405  bool PreserveLCSSA, bool &HasLoopExit) {
406  // Update dominator tree if available.
407  if (DT) {
408  if (OldBB == DT->getRootNode()->getBlock()) {
409  assert(NewBB == &NewBB->getParent()->getEntryBlock());
410  DT->setNewRoot(NewBB);
411  } else {
412  // Split block expects NewBB to have a non-empty set of predecessors.
413  DT->splitBlock(NewBB);
414  }
415  }
416 
417  // Update MemoryPhis after split if MemorySSA is available
418  if (MSSAU)
419  MSSAU->wireOldPredecessorsToNewImmediatePredecessor(OldBB, NewBB, Preds);
420 
421  // The rest of the logic is only relevant for updating the loop structures.
422  if (!LI)
423  return;
424 
425  assert(DT && "DT should be available to update LoopInfo!");
426  Loop *L = LI->getLoopFor(OldBB);
427 
428  // If we need to preserve loop analyses, collect some information about how
429  // this split will affect loops.
430  bool IsLoopEntry = !!L;
431  bool SplitMakesNewLoopHeader = false;
432  for (BasicBlock *Pred : Preds) {
433  // Preds that are not reachable from entry should not be used to identify if
434  // OldBB is a loop entry or if SplitMakesNewLoopHeader. Unreachable blocks
435  // are not within any loops, so we incorrectly mark SplitMakesNewLoopHeader
436  // as true and make the NewBB the header of some loop. This breaks LI.
437  if (!DT->isReachableFromEntry(Pred))
438  continue;
439  // If we need to preserve LCSSA, determine if any of the preds is a loop
440  // exit.
441  if (PreserveLCSSA)
442  if (Loop *PL = LI->getLoopFor(Pred))
443  if (!PL->contains(OldBB))
444  HasLoopExit = true;
445 
446  // If we need to preserve LoopInfo, note whether any of the preds crosses
447  // an interesting loop boundary.
448  if (!L)
449  continue;
450  if (L->contains(Pred))
451  IsLoopEntry = false;
452  else
453  SplitMakesNewLoopHeader = true;
454  }
455 
456  // Unless we have a loop for OldBB, nothing else to do here.
457  if (!L)
458  return;
459 
460  if (IsLoopEntry) {
461  // Add the new block to the nearest enclosing loop (and not an adjacent
462  // loop). To find this, examine each of the predecessors and determine which
463  // loops enclose them, and select the most-nested loop which contains the
464  // loop containing the block being split.
465  Loop *InnermostPredLoop = nullptr;
466  for (BasicBlock *Pred : Preds) {
467  if (Loop *PredLoop = LI->getLoopFor(Pred)) {
468  // Seek a loop which actually contains the block being split (to avoid
469  // adjacent loops).
470  while (PredLoop && !PredLoop->contains(OldBB))
471  PredLoop = PredLoop->getParentLoop();
472 
473  // Select the most-nested of these loops which contains the block.
474  if (PredLoop && PredLoop->contains(OldBB) &&
475  (!InnermostPredLoop ||
476  InnermostPredLoop->getLoopDepth() < PredLoop->getLoopDepth()))
477  InnermostPredLoop = PredLoop;
478  }
479  }
480 
481  if (InnermostPredLoop)
482  InnermostPredLoop->addBasicBlockToLoop(NewBB, *LI);
483  } else {
484  L->addBasicBlockToLoop(NewBB, *LI);
485  if (SplitMakesNewLoopHeader)
486  L->moveToHeader(NewBB);
487  }
488 }
489 
490 /// Update the PHI nodes in OrigBB to include the values coming from NewBB.
491 /// This also updates AliasAnalysis, if available.
492 static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB,
494  bool HasLoopExit) {
495  // Otherwise, create a new PHI node in NewBB for each PHI node in OrigBB.
496  SmallPtrSet<BasicBlock *, 16> PredSet(Preds.begin(), Preds.end());
497  for (BasicBlock::iterator I = OrigBB->begin(); isa<PHINode>(I); ) {
498  PHINode *PN = cast<PHINode>(I++);
499 
500  // Check to see if all of the values coming in are the same. If so, we
501  // don't need to create a new PHI node, unless it's needed for LCSSA.
502  Value *InVal = nullptr;
503  if (!HasLoopExit) {
504  InVal = PN->getIncomingValueForBlock(Preds[0]);
505  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
506  if (!PredSet.count(PN->getIncomingBlock(i)))
507  continue;
508  if (!InVal)
509  InVal = PN->getIncomingValue(i);
510  else if (InVal != PN->getIncomingValue(i)) {
511  InVal = nullptr;
512  break;
513  }
514  }
515  }
516 
517  if (InVal) {
518  // If all incoming values for the new PHI would be the same, just don't
519  // make a new PHI. Instead, just remove the incoming values from the old
520  // PHI.
521 
522  // NOTE! This loop walks backwards for a reason! First off, this minimizes
523  // the cost of removal if we end up removing a large number of values, and
524  // second off, this ensures that the indices for the incoming values
525  // aren't invalidated when we remove one.
526  for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i)
527  if (PredSet.count(PN->getIncomingBlock(i)))
528  PN->removeIncomingValue(i, false);
529 
530  // Add an incoming value to the PHI node in the loop for the preheader
531  // edge.
532  PN->addIncoming(InVal, NewBB);
533  continue;
534  }
535 
536  // If the values coming into the block are not the same, we need a new
537  // PHI.
538  // Create the new PHI node, insert it into NewBB at the end of the block
539  PHINode *NewPHI =
540  PHINode::Create(PN->getType(), Preds.size(), PN->getName() + ".ph", BI);
541 
542  // NOTE! This loop walks backwards for a reason! First off, this minimizes
543  // the cost of removal if we end up removing a large number of values, and
544  // second off, this ensures that the indices for the incoming values aren't
545  // invalidated when we remove one.
546  for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) {
547  BasicBlock *IncomingBB = PN->getIncomingBlock(i);
548  if (PredSet.count(IncomingBB)) {
549  Value *V = PN->removeIncomingValue(i, false);
550  NewPHI->addIncoming(V, IncomingBB);
551  }
552  }
553 
554  PN->addIncoming(NewPHI, NewBB);
555  }
556 }
557 
560  const char *Suffix, DominatorTree *DT,
561  LoopInfo *LI, MemorySSAUpdater *MSSAU,
562  bool PreserveLCSSA) {
563  // Do not attempt to split that which cannot be split.
564  if (!BB->canSplitPredecessors())
565  return nullptr;
566 
567  // For the landingpads we need to act a bit differently.
568  // Delegate this work to the SplitLandingPadPredecessors.
569  if (BB->isLandingPad()) {
571  std::string NewName = std::string(Suffix) + ".split-lp";
572 
573  SplitLandingPadPredecessors(BB, Preds, Suffix, NewName.c_str(), NewBBs, DT,
574  LI, MSSAU, PreserveLCSSA);
575  return NewBBs[0];
576  }
577 
578  // Create new basic block, insert right before the original block.
580  BB->getContext(), BB->getName() + Suffix, BB->getParent(), BB);
581 
582  // The new block unconditionally branches to the old block.
583  BranchInst *BI = BranchInst::Create(BB, NewBB);
584  // Splitting the predecessors of a loop header creates a preheader block.
585  if (LI && LI->isLoopHeader(BB))
586  // Using the loop start line number prevents debuggers stepping into the
587  // loop body for this instruction.
588  BI->setDebugLoc(LI->getLoopFor(BB)->getStartLoc());
589  else
590  BI->setDebugLoc(BB->getFirstNonPHIOrDbg()->getDebugLoc());
591 
592  // Move the edges from Preds to point to NewBB instead of BB.
593  for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
594  // This is slightly more strict than necessary; the minimum requirement
595  // is that there be no more than one indirectbr branching to BB. And
596  // all BlockAddress uses would need to be updated.
597  assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&
598  "Cannot split an edge from an IndirectBrInst");
599  assert(!isa<CallBrInst>(Preds[i]->getTerminator()) &&
600  "Cannot split an edge from a CallBrInst");
601  Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB);
602  }
603 
604  // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI
605  // node becomes an incoming value for BB's phi node. However, if the Preds
606  // list is empty, we need to insert dummy entries into the PHI nodes in BB to
607  // account for the newly created predecessor.
608  if (Preds.empty()) {
609  // Insert dummy values as the incoming value.
610  for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I)
611  cast<PHINode>(I)->addIncoming(UndefValue::get(I->getType()), NewBB);
612  }
613 
614  // Update DominatorTree, LoopInfo, and LCCSA analysis information.
615  bool HasLoopExit = false;
616  UpdateAnalysisInformation(BB, NewBB, Preds, DT, LI, MSSAU, PreserveLCSSA,
617  HasLoopExit);
618 
619  if (!Preds.empty()) {
620  // Update the PHI nodes in BB with the values coming from NewBB.
621  UpdatePHINodes(BB, NewBB, Preds, BI, HasLoopExit);
622  }
623 
624  return NewBB;
625 }
626 
629  const char *Suffix1, const char *Suffix2,
631  DominatorTree *DT, LoopInfo *LI,
632  MemorySSAUpdater *MSSAU,
633  bool PreserveLCSSA) {
634  assert(OrigBB->isLandingPad() && "Trying to split a non-landing pad!");
635 
636  // Create a new basic block for OrigBB's predecessors listed in Preds. Insert
637  // it right before the original block.
638  BasicBlock *NewBB1 = BasicBlock::Create(OrigBB->getContext(),
639  OrigBB->getName() + Suffix1,
640  OrigBB->getParent(), OrigBB);
641  NewBBs.push_back(NewBB1);
642 
643  // The new block unconditionally branches to the old block.
644  BranchInst *BI1 = BranchInst::Create(OrigBB, NewBB1);
645  BI1->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc());
646 
647  // Move the edges from Preds to point to NewBB1 instead of OrigBB.
648  for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
649  // This is slightly more strict than necessary; the minimum requirement
650  // is that there be no more than one indirectbr branching to BB. And
651  // all BlockAddress uses would need to be updated.
652  assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&
653  "Cannot split an edge from an IndirectBrInst");
654  Preds[i]->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1);
655  }
656 
657  bool HasLoopExit = false;
658  UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DT, LI, MSSAU, PreserveLCSSA,
659  HasLoopExit);
660 
661  // Update the PHI nodes in OrigBB with the values coming from NewBB1.
662  UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, HasLoopExit);
663 
664  // Move the remaining edges from OrigBB to point to NewBB2.
665  SmallVector<BasicBlock*, 8> NewBB2Preds;
666  for (pred_iterator i = pred_begin(OrigBB), e = pred_end(OrigBB);
667  i != e; ) {
668  BasicBlock *Pred = *i++;
669  if (Pred == NewBB1) continue;
670  assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
671  "Cannot split an edge from an IndirectBrInst");
672  NewBB2Preds.push_back(Pred);
673  e = pred_end(OrigBB);
674  }
675 
676  BasicBlock *NewBB2 = nullptr;
677  if (!NewBB2Preds.empty()) {
678  // Create another basic block for the rest of OrigBB's predecessors.
679  NewBB2 = BasicBlock::Create(OrigBB->getContext(),
680  OrigBB->getName() + Suffix2,
681  OrigBB->getParent(), OrigBB);
682  NewBBs.push_back(NewBB2);
683 
684  // The new block unconditionally branches to the old block.
685  BranchInst *BI2 = BranchInst::Create(OrigBB, NewBB2);
686  BI2->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc());
687 
688  // Move the remaining edges from OrigBB to point to NewBB2.
689  for (BasicBlock *NewBB2Pred : NewBB2Preds)
690  NewBB2Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2);
691 
692  // Update DominatorTree, LoopInfo, and LCCSA analysis information.
693  HasLoopExit = false;
694  UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DT, LI, MSSAU,
695  PreserveLCSSA, HasLoopExit);
696 
697  // Update the PHI nodes in OrigBB with the values coming from NewBB2.
698  UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, HasLoopExit);
699  }
700 
701  LandingPadInst *LPad = OrigBB->getLandingPadInst();
702  Instruction *Clone1 = LPad->clone();
703  Clone1->setName(Twine("lpad") + Suffix1);
704  NewBB1->getInstList().insert(NewBB1->getFirstInsertionPt(), Clone1);
705 
706  if (NewBB2) {
707  Instruction *Clone2 = LPad->clone();
708  Clone2->setName(Twine("lpad") + Suffix2);
709  NewBB2->getInstList().insert(NewBB2->getFirstInsertionPt(), Clone2);
710 
711  // Create a PHI node for the two cloned landingpad instructions only
712  // if the original landingpad instruction has some uses.
713  if (!LPad->use_empty()) {
714  assert(!LPad->getType()->isTokenTy() &&
715  "Split cannot be applied if LPad is token type. Otherwise an "
716  "invalid PHINode of token type would be created.");
717  PHINode *PN = PHINode::Create(LPad->getType(), 2, "lpad.phi", LPad);
718  PN->addIncoming(Clone1, NewBB1);
719  PN->addIncoming(Clone2, NewBB2);
720  LPad->replaceAllUsesWith(PN);
721  }
722  LPad->eraseFromParent();
723  } else {
724  // There is no second clone. Just replace the landing pad with the first
725  // clone.
726  LPad->replaceAllUsesWith(Clone1);
727  LPad->eraseFromParent();
728  }
729 }
730 
732  BasicBlock *Pred,
733  DomTreeUpdater *DTU) {
734  Instruction *UncondBranch = Pred->getTerminator();
735  // Clone the return and add it to the end of the predecessor.
736  Instruction *NewRet = RI->clone();
737  Pred->getInstList().push_back(NewRet);
738 
739  // If the return instruction returns a value, and if the value was a
740  // PHI node in "BB", propagate the right value into the return.
741  for (User::op_iterator i = NewRet->op_begin(), e = NewRet->op_end();
742  i != e; ++i) {
743  Value *V = *i;
744  Instruction *NewBC = nullptr;
745  if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) {
746  // Return value might be bitcasted. Clone and insert it before the
747  // return instruction.
748  V = BCI->getOperand(0);
749  NewBC = BCI->clone();
750  Pred->getInstList().insert(NewRet->getIterator(), NewBC);
751  *i = NewBC;
752  }
753  if (PHINode *PN = dyn_cast<PHINode>(V)) {
754  if (PN->getParent() == BB) {
755  if (NewBC)
756  NewBC->setOperand(0, PN->getIncomingValueForBlock(Pred));
757  else
758  *i = PN->getIncomingValueForBlock(Pred);
759  }
760  }
761  }
762 
763  // Update any PHI nodes in the returning block to realize that we no
764  // longer branch to them.
765  BB->removePredecessor(Pred);
766  UncondBranch->eraseFromParent();
767 
768  if (DTU)
769  DTU->applyUpdates({{DominatorTree::Delete, Pred, BB}});
770 
771  return cast<ReturnInst>(NewRet);
772 }
773 
775  Instruction *SplitBefore,
776  bool Unreachable,
777  MDNode *BranchWeights,
778  DominatorTree *DT, LoopInfo *LI,
779  BasicBlock *ThenBlock) {
780  BasicBlock *Head = SplitBefore->getParent();
781  BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator());
782  Instruction *HeadOldTerm = Head->getTerminator();
783  LLVMContext &C = Head->getContext();
784  Instruction *CheckTerm;
785  bool CreateThenBlock = (ThenBlock == nullptr);
786  if (CreateThenBlock) {
787  ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
788  if (Unreachable)
789  CheckTerm = new UnreachableInst(C, ThenBlock);
790  else
791  CheckTerm = BranchInst::Create(Tail, ThenBlock);
792  CheckTerm->setDebugLoc(SplitBefore->getDebugLoc());
793  } else
794  CheckTerm = ThenBlock->getTerminator();
795  BranchInst *HeadNewTerm =
796  BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/Tail, Cond);
797  HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
798  ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
799 
800  if (DT) {
801  if (DomTreeNode *OldNode = DT->getNode(Head)) {
802  std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
803 
804  DomTreeNode *NewNode = DT->addNewBlock(Tail, Head);
805  for (DomTreeNode *Child : Children)
806  DT->changeImmediateDominator(Child, NewNode);
807 
808  // Head dominates ThenBlock.
809  if (CreateThenBlock)
810  DT->addNewBlock(ThenBlock, Head);
811  else
812  DT->changeImmediateDominator(ThenBlock, Head);
813  }
814  }
815 
816  if (LI) {
817  if (Loop *L = LI->getLoopFor(Head)) {
818  L->addBasicBlockToLoop(ThenBlock, *LI);
819  L->addBasicBlockToLoop(Tail, *LI);
820  }
821  }
822 
823  return CheckTerm;
824 }
825 
827  Instruction **ThenTerm,
828  Instruction **ElseTerm,
829  MDNode *BranchWeights) {
830  BasicBlock *Head = SplitBefore->getParent();
831  BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator());
832  Instruction *HeadOldTerm = Head->getTerminator();
833  LLVMContext &C = Head->getContext();
834  BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
835  BasicBlock *ElseBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
836  *ThenTerm = BranchInst::Create(Tail, ThenBlock);
837  (*ThenTerm)->setDebugLoc(SplitBefore->getDebugLoc());
838  *ElseTerm = BranchInst::Create(Tail, ElseBlock);
839  (*ElseTerm)->setDebugLoc(SplitBefore->getDebugLoc());
840  BranchInst *HeadNewTerm =
841  BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/ElseBlock, Cond);
842  HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
843  ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
844 }
845 
847  BasicBlock *&IfFalse) {
848  PHINode *SomePHI = dyn_cast<PHINode>(BB->begin());
849  BasicBlock *Pred1 = nullptr;
850  BasicBlock *Pred2 = nullptr;
851 
852  if (SomePHI) {
853  if (SomePHI->getNumIncomingValues() != 2)
854  return nullptr;
855  Pred1 = SomePHI->getIncomingBlock(0);
856  Pred2 = SomePHI->getIncomingBlock(1);
857  } else {
858  pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
859  if (PI == PE) // No predecessor
860  return nullptr;
861  Pred1 = *PI++;
862  if (PI == PE) // Only one predecessor
863  return nullptr;
864  Pred2 = *PI++;
865  if (PI != PE) // More than two predecessors
866  return nullptr;
867  }
868 
869  // We can only handle branches. Other control flow will be lowered to
870  // branches if possible anyway.
871  BranchInst *Pred1Br = dyn_cast<BranchInst>(Pred1->getTerminator());
872  BranchInst *Pred2Br = dyn_cast<BranchInst>(Pred2->getTerminator());
873  if (!Pred1Br || !Pred2Br)
874  return nullptr;
875 
876  // Eliminate code duplication by ensuring that Pred1Br is conditional if
877  // either are.
878  if (Pred2Br->isConditional()) {
879  // If both branches are conditional, we don't have an "if statement". In
880  // reality, we could transform this case, but since the condition will be
881  // required anyway, we stand no chance of eliminating it, so the xform is
882  // probably not profitable.
883  if (Pred1Br->isConditional())
884  return nullptr;
885 
886  std::swap(Pred1, Pred2);
887  std::swap(Pred1Br, Pred2Br);
888  }
889 
890  if (Pred1Br->isConditional()) {
891  // The only thing we have to watch out for here is to make sure that Pred2
892  // doesn't have incoming edges from other blocks. If it does, the condition
893  // doesn't dominate BB.
894  if (!Pred2->getSinglePredecessor())
895  return nullptr;
896 
897  // If we found a conditional branch predecessor, make sure that it branches
898  // to BB and Pred2Br. If it doesn't, this isn't an "if statement".
899  if (Pred1Br->getSuccessor(0) == BB &&
900  Pred1Br->getSuccessor(1) == Pred2) {
901  IfTrue = Pred1;
902  IfFalse = Pred2;
903  } else if (Pred1Br->getSuccessor(0) == Pred2 &&
904  Pred1Br->getSuccessor(1) == BB) {
905  IfTrue = Pred2;
906  IfFalse = Pred1;
907  } else {
908  // We know that one arm of the conditional goes to BB, so the other must
909  // go somewhere unrelated, and this must not be an "if statement".
910  return nullptr;
911  }
912 
913  return Pred1Br->getCondition();
914  }
915 
916  // Ok, if we got here, both predecessors end with an unconditional branch to
917  // BB. Don't panic! If both blocks only have a single (identical)
918  // predecessor, and THAT is a conditional branch, then we're all ok!
919  BasicBlock *CommonPred = Pred1->getSinglePredecessor();
920  if (CommonPred == nullptr || CommonPred != Pred2->getSinglePredecessor())
921  return nullptr;
922 
923  // Otherwise, if this is a conditional branch, then we can use it!
924  BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator());
925  if (!BI) return nullptr;
926 
927  assert(BI->isConditional() && "Two successors but not conditional?");
928  if (BI->getSuccessor(0) == Pred1) {
929  IfTrue = Pred1;
930  IfFalse = Pred2;
931  } else {
932  IfTrue = Pred2;
933  IfFalse = Pred1;
934  }
935  return BI->getCondition();
936 }
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
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: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: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:137
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: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: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:245
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:328
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:251
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:1446
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
Definition: LoopInfo.cpp:607
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
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: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: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: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: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
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:73
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: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:342
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:276