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