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->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
105 
106  for (BasicBlock *BB : BBs)
107  if (DTU)
108  DTU->deleteBB(BB);
109  else
110  BB->eraseFromParent();
111 }
112 
114  MemoryDependenceResults *MemDep) {
115  if (!isa<PHINode>(BB->begin())) return;
116 
117  while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
118  if (PN->getIncomingValue(0) != PN)
119  PN->replaceAllUsesWith(PN->getIncomingValue(0));
120  else
121  PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
122 
123  if (MemDep)
124  MemDep->removeInstruction(PN); // Memdep updates AA itself.
125 
126  PN->eraseFromParent();
127  }
128 }
129 
131  // Recursively deleting a PHI may cause multiple PHIs to be deleted
132  // or RAUW'd undef, so use an array of WeakTrackingVH for the PHIs to delete.
134  for (PHINode &PN : BB->phis())
135  PHIs.push_back(&PN);
136 
137  bool Changed = false;
138  for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
139  if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i].operator Value*()))
140  Changed |= RecursivelyDeleteDeadPHINode(PN, TLI);
141 
142  return Changed;
143 }
144 
146  LoopInfo *LI, MemorySSAUpdater *MSSAU,
147  MemoryDependenceResults *MemDep) {
148  if (BB->hasAddressTaken())
149  return false;
150 
151  // Can't merge if there are multiple predecessors, or no predecessors.
152  BasicBlock *PredBB = BB->getUniquePredecessor();
153  if (!PredBB) return false;
154 
155  // Don't break self-loops.
156  if (PredBB == BB) return false;
157  // Don't break unwinding instructions.
158  if (PredBB->getTerminator()->isExceptionalTerminator())
159  return false;
160 
161  // Can't merge if there are multiple distinct successors.
162  if (PredBB->getUniqueSuccessor() != BB)
163  return false;
164 
165  // Can't merge if there is PHI loop.
166  for (PHINode &PN : BB->phis())
167  for (Value *IncValue : PN.incoming_values())
168  if (IncValue == &PN)
169  return false;
170 
171  // Begin by getting rid of unneeded PHIs.
172  SmallVector<AssertingVH<Value>, 4> IncomingValues;
173  if (isa<PHINode>(BB->front())) {
174  for (PHINode &PN : BB->phis())
175  if (!isa<PHINode>(PN.getIncomingValue(0)) ||
176  cast<PHINode>(PN.getIncomingValue(0))->getParent() != BB)
177  IncomingValues.push_back(PN.getIncomingValue(0));
178  FoldSingleEntryPHINodes(BB, MemDep);
179  }
180 
181  // DTU update: Collect all the edges that exit BB.
182  // These dominator edges will be redirected from Pred.
183  std::vector<DominatorTree::UpdateType> Updates;
184  if (DTU) {
185  Updates.reserve(1 + (2 * succ_size(BB)));
186  Updates.push_back({DominatorTree::Delete, PredBB, BB});
187  for (auto I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
188  Updates.push_back({DominatorTree::Delete, BB, *I});
189  Updates.push_back({DominatorTree::Insert, PredBB, *I});
190  }
191  }
192 
193  if (MSSAU)
194  MSSAU->moveAllAfterMergeBlocks(BB, PredBB, &*(BB->begin()));
195 
196  // Delete the unconditional branch from the predecessor...
197  PredBB->getInstList().pop_back();
198 
199  // Make all PHI nodes that referred to BB now refer to Pred as their
200  // source...
201  BB->replaceAllUsesWith(PredBB);
202 
203  // Move all definitions in the successor to the predecessor...
204  PredBB->getInstList().splice(PredBB->end(), BB->getInstList());
205  new UnreachableInst(BB->getContext(), BB);
206 
207  // Eliminate duplicate dbg.values describing the entry PHI node post-splice.
208  for (auto Incoming : IncomingValues) {
209  if (isa<Instruction>(*Incoming)) {
212  DbgValueSet;
213  llvm::findDbgValues(DbgValues, Incoming);
214  for (auto &DVI : DbgValues) {
215  auto R = DbgValueSet.insert({DVI->getVariable(), DVI->getExpression()});
216  if (!R.second)
217  DVI->eraseFromParent();
218  }
219  }
220  }
221 
222  // Inherit predecessors name if it exists.
223  if (!PredBB->hasName())
224  PredBB->takeName(BB);
225 
226  if (LI)
227  LI->removeBlock(BB);
228 
229  if (MemDep)
231 
232  // Finally, erase the old block and update dominator info.
233  if (DTU) {
234  assert(BB->getInstList().size() == 1 &&
235  isa<UnreachableInst>(BB->getTerminator()) &&
236  "The successor list of BB isn't empty before "
237  "applying corresponding DTU updates.");
238  DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
239  DTU->deleteBB(BB);
240  }
241 
242  else {
243  BB->eraseFromParent(); // Nuke BB if DTU is nullptr.
244  }
245  return true;
246 }
247 
249  BasicBlock::iterator &BI, Value *V) {
250  Instruction &I = *BI;
251  // Replaces all of the uses of the instruction with uses of the value
252  I.replaceAllUsesWith(V);
253 
254  // Make sure to propagate a name if there is one already.
255  if (I.hasName() && !V->hasName())
256  V->takeName(&I);
257 
258  // Delete the unnecessary instruction now...
259  BI = BIL.erase(BI);
260 }
261 
264  assert(I->getParent() == nullptr &&
265  "ReplaceInstWithInst: Instruction already inserted into basic block!");
266 
267  // Copy debug location to newly added instruction, if it wasn't already set
268  // by the caller.
269  if (!I->getDebugLoc())
270  I->setDebugLoc(BI->getDebugLoc());
271 
272  // Insert the new instruction into the basic block...
273  BasicBlock::iterator New = BIL.insert(BI, I);
274 
275  // Replace all uses of the old instruction, and delete it.
276  ReplaceInstWithValue(BIL, BI, I);
277 
278  // Move BI back to point to the newly inserted instruction
279  BI = New;
280 }
281 
283  BasicBlock::iterator BI(From);
284  ReplaceInstWithInst(From->getParent()->getInstList(), BI, To);
285 }
286 
288  LoopInfo *LI, MemorySSAUpdater *MSSAU) {
289  unsigned SuccNum = GetSuccessorNumber(BB, Succ);
290 
291  // If this is a critical edge, let SplitCriticalEdge do it.
292  Instruction *LatchTerm = BB->getTerminator();
293  if (SplitCriticalEdge(
294  LatchTerm, SuccNum,
295  CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA()))
296  return LatchTerm->getSuccessor(SuccNum);
297 
298  // If the edge isn't critical, then BB has a single successor or Succ has a
299  // single pred. Split the block.
300  if (BasicBlock *SP = Succ->getSinglePredecessor()) {
301  // If the successor only has a single pred, split the top of the successor
302  // block.
303  assert(SP == BB && "CFG broken");
304  SP = nullptr;
305  return SplitBlock(Succ, &Succ->front(), DT, LI, MSSAU);
306  }
307 
308  // Otherwise, if BB has a single successor, split it at the bottom of the
309  // block.
310  assert(BB->getTerminator()->getNumSuccessors() == 1 &&
311  "Should have a single succ!");
312  return SplitBlock(BB, BB->getTerminator(), DT, LI, MSSAU);
313 }
314 
315 unsigned
317  const CriticalEdgeSplittingOptions &Options) {
318  unsigned NumBroken = 0;
319  for (BasicBlock &BB : F) {
320  Instruction *TI = BB.getTerminator();
321  if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI))
322  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
323  if (SplitCriticalEdge(TI, i, Options))
324  ++NumBroken;
325  }
326  return NumBroken;
327 }
328 
330  DominatorTree *DT, LoopInfo *LI,
331  MemorySSAUpdater *MSSAU) {
332  BasicBlock::iterator SplitIt = SplitPt->getIterator();
333  while (isa<PHINode>(SplitIt) || SplitIt->isEHPad())
334  ++SplitIt;
335  BasicBlock *New = Old->splitBasicBlock(SplitIt, Old->getName()+".split");
336 
337  // The new block lives in whichever loop the old one did. This preserves
338  // LCSSA as well, because we force the split point to be after any PHI nodes.
339  if (LI)
340  if (Loop *L = LI->getLoopFor(Old))
341  L->addBasicBlockToLoop(New, *LI);
342 
343  if (DT)
344  // Old dominates New. New node dominates all other nodes dominated by Old.
345  if (DomTreeNode *OldNode = DT->getNode(Old)) {
346  std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
347 
348  DomTreeNode *NewNode = DT->addNewBlock(New, Old);
349  for (DomTreeNode *I : Children)
350  DT->changeImmediateDominator(I, NewNode);
351  }
352 
353  // Move MemoryAccesses still tracked in Old, but part of New now.
354  // Update accesses in successor blocks accordingly.
355  if (MSSAU)
356  MSSAU->moveAllAfterSpliceBlocks(Old, New, &*(New->begin()));
357 
358  return New;
359 }
360 
361 /// Update DominatorTree, LoopInfo, and LCCSA analysis information.
364  DominatorTree *DT, LoopInfo *LI,
365  MemorySSAUpdater *MSSAU,
366  bool PreserveLCSSA, bool &HasLoopExit) {
367  // Update dominator tree if available.
368  if (DT) {
369  if (OldBB == DT->getRootNode()->getBlock()) {
370  assert(NewBB == &NewBB->getParent()->getEntryBlock());
371  DT->setNewRoot(NewBB);
372  } else {
373  // Split block expects NewBB to have a non-empty set of predecessors.
374  DT->splitBlock(NewBB);
375  }
376  }
377 
378  // Update MemoryPhis after split if MemorySSA is available
379  if (MSSAU)
380  MSSAU->wireOldPredecessorsToNewImmediatePredecessor(OldBB, NewBB, Preds);
381 
382  // The rest of the logic is only relevant for updating the loop structures.
383  if (!LI)
384  return;
385 
386  assert(DT && "DT should be available to update LoopInfo!");
387  Loop *L = LI->getLoopFor(OldBB);
388 
389  // If we need to preserve loop analyses, collect some information about how
390  // this split will affect loops.
391  bool IsLoopEntry = !!L;
392  bool SplitMakesNewLoopHeader = false;
393  for (BasicBlock *Pred : Preds) {
394  // Preds that are not reachable from entry should not be used to identify if
395  // OldBB is a loop entry or if SplitMakesNewLoopHeader. Unreachable blocks
396  // are not within any loops, so we incorrectly mark SplitMakesNewLoopHeader
397  // as true and make the NewBB the header of some loop. This breaks LI.
398  if (!DT->isReachableFromEntry(Pred))
399  continue;
400  // If we need to preserve LCSSA, determine if any of the preds is a loop
401  // exit.
402  if (PreserveLCSSA)
403  if (Loop *PL = LI->getLoopFor(Pred))
404  if (!PL->contains(OldBB))
405  HasLoopExit = true;
406 
407  // If we need to preserve LoopInfo, note whether any of the preds crosses
408  // an interesting loop boundary.
409  if (!L)
410  continue;
411  if (L->contains(Pred))
412  IsLoopEntry = false;
413  else
414  SplitMakesNewLoopHeader = true;
415  }
416 
417  // Unless we have a loop for OldBB, nothing else to do here.
418  if (!L)
419  return;
420 
421  if (IsLoopEntry) {
422  // Add the new block to the nearest enclosing loop (and not an adjacent
423  // loop). To find this, examine each of the predecessors and determine which
424  // loops enclose them, and select the most-nested loop which contains the
425  // loop containing the block being split.
426  Loop *InnermostPredLoop = nullptr;
427  for (BasicBlock *Pred : Preds) {
428  if (Loop *PredLoop = LI->getLoopFor(Pred)) {
429  // Seek a loop which actually contains the block being split (to avoid
430  // adjacent loops).
431  while (PredLoop && !PredLoop->contains(OldBB))
432  PredLoop = PredLoop->getParentLoop();
433 
434  // Select the most-nested of these loops which contains the block.
435  if (PredLoop && PredLoop->contains(OldBB) &&
436  (!InnermostPredLoop ||
437  InnermostPredLoop->getLoopDepth() < PredLoop->getLoopDepth()))
438  InnermostPredLoop = PredLoop;
439  }
440  }
441 
442  if (InnermostPredLoop)
443  InnermostPredLoop->addBasicBlockToLoop(NewBB, *LI);
444  } else {
445  L->addBasicBlockToLoop(NewBB, *LI);
446  if (SplitMakesNewLoopHeader)
447  L->moveToHeader(NewBB);
448  }
449 }
450 
451 /// Update the PHI nodes in OrigBB to include the values coming from NewBB.
452 /// This also updates AliasAnalysis, if available.
453 static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB,
455  bool HasLoopExit) {
456  // Otherwise, create a new PHI node in NewBB for each PHI node in OrigBB.
457  SmallPtrSet<BasicBlock *, 16> PredSet(Preds.begin(), Preds.end());
458  for (BasicBlock::iterator I = OrigBB->begin(); isa<PHINode>(I); ) {
459  PHINode *PN = cast<PHINode>(I++);
460 
461  // Check to see if all of the values coming in are the same. If so, we
462  // don't need to create a new PHI node, unless it's needed for LCSSA.
463  Value *InVal = nullptr;
464  if (!HasLoopExit) {
465  InVal = PN->getIncomingValueForBlock(Preds[0]);
466  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
467  if (!PredSet.count(PN->getIncomingBlock(i)))
468  continue;
469  if (!InVal)
470  InVal = PN->getIncomingValue(i);
471  else if (InVal != PN->getIncomingValue(i)) {
472  InVal = nullptr;
473  break;
474  }
475  }
476  }
477 
478  if (InVal) {
479  // If all incoming values for the new PHI would be the same, just don't
480  // make a new PHI. Instead, just remove the incoming values from the old
481  // PHI.
482 
483  // NOTE! This loop walks backwards for a reason! First off, this minimizes
484  // the cost of removal if we end up removing a large number of values, and
485  // second off, this ensures that the indices for the incoming values
486  // aren't invalidated when we remove one.
487  for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i)
488  if (PredSet.count(PN->getIncomingBlock(i)))
489  PN->removeIncomingValue(i, false);
490 
491  // Add an incoming value to the PHI node in the loop for the preheader
492  // edge.
493  PN->addIncoming(InVal, NewBB);
494  continue;
495  }
496 
497  // If the values coming into the block are not the same, we need a new
498  // PHI.
499  // Create the new PHI node, insert it into NewBB at the end of the block
500  PHINode *NewPHI =
501  PHINode::Create(PN->getType(), Preds.size(), PN->getName() + ".ph", BI);
502 
503  // NOTE! This loop walks backwards for a reason! First off, this minimizes
504  // the cost of removal if we end up removing a large number of values, and
505  // second off, this ensures that the indices for the incoming values aren't
506  // invalidated when we remove one.
507  for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) {
508  BasicBlock *IncomingBB = PN->getIncomingBlock(i);
509  if (PredSet.count(IncomingBB)) {
510  Value *V = PN->removeIncomingValue(i, false);
511  NewPHI->addIncoming(V, IncomingBB);
512  }
513  }
514 
515  PN->addIncoming(NewPHI, NewBB);
516  }
517 }
518 
521  const char *Suffix, DominatorTree *DT,
522  LoopInfo *LI, MemorySSAUpdater *MSSAU,
523  bool PreserveLCSSA) {
524  // Do not attempt to split that which cannot be split.
525  if (!BB->canSplitPredecessors())
526  return nullptr;
527 
528  // For the landingpads we need to act a bit differently.
529  // Delegate this work to the SplitLandingPadPredecessors.
530  if (BB->isLandingPad()) {
532  std::string NewName = std::string(Suffix) + ".split-lp";
533 
534  SplitLandingPadPredecessors(BB, Preds, Suffix, NewName.c_str(), NewBBs, DT,
535  LI, MSSAU, PreserveLCSSA);
536  return NewBBs[0];
537  }
538 
539  // Create new basic block, insert right before the original block.
541  BB->getContext(), BB->getName() + Suffix, BB->getParent(), BB);
542 
543  // The new block unconditionally branches to the old block.
544  BranchInst *BI = BranchInst::Create(BB, NewBB);
545  BI->setDebugLoc(BB->getFirstNonPHIOrDbg()->getDebugLoc());
546 
547  // Move the edges from Preds to point to NewBB instead of BB.
548  for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
549  // This is slightly more strict than necessary; the minimum requirement
550  // is that there be no more than one indirectbr branching to BB. And
551  // all BlockAddress uses would need to be updated.
552  assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&
553  "Cannot split an edge from an IndirectBrInst");
554  assert(!isa<CallBrInst>(Preds[i]->getTerminator()) &&
555  "Cannot split an edge from a CallBrInst");
556  Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB);
557  }
558 
559  // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI
560  // node becomes an incoming value for BB's phi node. However, if the Preds
561  // list is empty, we need to insert dummy entries into the PHI nodes in BB to
562  // account for the newly created predecessor.
563  if (Preds.empty()) {
564  // Insert dummy values as the incoming value.
565  for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I)
566  cast<PHINode>(I)->addIncoming(UndefValue::get(I->getType()), NewBB);
567  }
568 
569  // Update DominatorTree, LoopInfo, and LCCSA analysis information.
570  bool HasLoopExit = false;
571  UpdateAnalysisInformation(BB, NewBB, Preds, DT, LI, MSSAU, PreserveLCSSA,
572  HasLoopExit);
573 
574  if (!Preds.empty()) {
575  // Update the PHI nodes in BB with the values coming from NewBB.
576  UpdatePHINodes(BB, NewBB, Preds, BI, HasLoopExit);
577  }
578 
579  return NewBB;
580 }
581 
584  const char *Suffix1, const char *Suffix2,
586  DominatorTree *DT, LoopInfo *LI,
587  MemorySSAUpdater *MSSAU,
588  bool PreserveLCSSA) {
589  assert(OrigBB->isLandingPad() && "Trying to split a non-landing pad!");
590 
591  // Create a new basic block for OrigBB's predecessors listed in Preds. Insert
592  // it right before the original block.
593  BasicBlock *NewBB1 = BasicBlock::Create(OrigBB->getContext(),
594  OrigBB->getName() + Suffix1,
595  OrigBB->getParent(), OrigBB);
596  NewBBs.push_back(NewBB1);
597 
598  // The new block unconditionally branches to the old block.
599  BranchInst *BI1 = BranchInst::Create(OrigBB, NewBB1);
600  BI1->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc());
601 
602  // Move the edges from Preds to point to NewBB1 instead of OrigBB.
603  for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
604  // This is slightly more strict than necessary; the minimum requirement
605  // is that there be no more than one indirectbr branching to BB. And
606  // all BlockAddress uses would need to be updated.
607  assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&
608  "Cannot split an edge from an IndirectBrInst");
609  Preds[i]->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1);
610  }
611 
612  bool HasLoopExit = false;
613  UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DT, LI, MSSAU, PreserveLCSSA,
614  HasLoopExit);
615 
616  // Update the PHI nodes in OrigBB with the values coming from NewBB1.
617  UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, HasLoopExit);
618 
619  // Move the remaining edges from OrigBB to point to NewBB2.
620  SmallVector<BasicBlock*, 8> NewBB2Preds;
621  for (pred_iterator i = pred_begin(OrigBB), e = pred_end(OrigBB);
622  i != e; ) {
623  BasicBlock *Pred = *i++;
624  if (Pred == NewBB1) continue;
625  assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
626  "Cannot split an edge from an IndirectBrInst");
627  NewBB2Preds.push_back(Pred);
628  e = pred_end(OrigBB);
629  }
630 
631  BasicBlock *NewBB2 = nullptr;
632  if (!NewBB2Preds.empty()) {
633  // Create another basic block for the rest of OrigBB's predecessors.
634  NewBB2 = BasicBlock::Create(OrigBB->getContext(),
635  OrigBB->getName() + Suffix2,
636  OrigBB->getParent(), OrigBB);
637  NewBBs.push_back(NewBB2);
638 
639  // The new block unconditionally branches to the old block.
640  BranchInst *BI2 = BranchInst::Create(OrigBB, NewBB2);
641  BI2->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc());
642 
643  // Move the remaining edges from OrigBB to point to NewBB2.
644  for (BasicBlock *NewBB2Pred : NewBB2Preds)
645  NewBB2Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2);
646 
647  // Update DominatorTree, LoopInfo, and LCCSA analysis information.
648  HasLoopExit = false;
649  UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DT, LI, MSSAU,
650  PreserveLCSSA, HasLoopExit);
651 
652  // Update the PHI nodes in OrigBB with the values coming from NewBB2.
653  UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, HasLoopExit);
654  }
655 
656  LandingPadInst *LPad = OrigBB->getLandingPadInst();
657  Instruction *Clone1 = LPad->clone();
658  Clone1->setName(Twine("lpad") + Suffix1);
659  NewBB1->getInstList().insert(NewBB1->getFirstInsertionPt(), Clone1);
660 
661  if (NewBB2) {
662  Instruction *Clone2 = LPad->clone();
663  Clone2->setName(Twine("lpad") + Suffix2);
664  NewBB2->getInstList().insert(NewBB2->getFirstInsertionPt(), Clone2);
665 
666  // Create a PHI node for the two cloned landingpad instructions only
667  // if the original landingpad instruction has some uses.
668  if (!LPad->use_empty()) {
669  assert(!LPad->getType()->isTokenTy() &&
670  "Split cannot be applied if LPad is token type. Otherwise an "
671  "invalid PHINode of token type would be created.");
672  PHINode *PN = PHINode::Create(LPad->getType(), 2, "lpad.phi", LPad);
673  PN->addIncoming(Clone1, NewBB1);
674  PN->addIncoming(Clone2, NewBB2);
675  LPad->replaceAllUsesWith(PN);
676  }
677  LPad->eraseFromParent();
678  } else {
679  // There is no second clone. Just replace the landing pad with the first
680  // clone.
681  LPad->replaceAllUsesWith(Clone1);
682  LPad->eraseFromParent();
683  }
684 }
685 
687  BasicBlock *Pred,
688  DomTreeUpdater *DTU) {
689  Instruction *UncondBranch = Pred->getTerminator();
690  // Clone the return and add it to the end of the predecessor.
691  Instruction *NewRet = RI->clone();
692  Pred->getInstList().push_back(NewRet);
693 
694  // If the return instruction returns a value, and if the value was a
695  // PHI node in "BB", propagate the right value into the return.
696  for (User::op_iterator i = NewRet->op_begin(), e = NewRet->op_end();
697  i != e; ++i) {
698  Value *V = *i;
699  Instruction *NewBC = nullptr;
700  if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) {
701  // Return value might be bitcasted. Clone and insert it before the
702  // return instruction.
703  V = BCI->getOperand(0);
704  NewBC = BCI->clone();
705  Pred->getInstList().insert(NewRet->getIterator(), NewBC);
706  *i = NewBC;
707  }
708  if (PHINode *PN = dyn_cast<PHINode>(V)) {
709  if (PN->getParent() == BB) {
710  if (NewBC)
711  NewBC->setOperand(0, PN->getIncomingValueForBlock(Pred));
712  else
713  *i = PN->getIncomingValueForBlock(Pred);
714  }
715  }
716  }
717 
718  // Update any PHI nodes in the returning block to realize that we no
719  // longer branch to them.
720  BB->removePredecessor(Pred);
721  UncondBranch->eraseFromParent();
722 
723  if (DTU)
724  DTU->deleteEdge(Pred, BB);
725 
726  return cast<ReturnInst>(NewRet);
727 }
728 
730  Instruction *SplitBefore,
731  bool Unreachable,
732  MDNode *BranchWeights,
733  DominatorTree *DT, LoopInfo *LI,
734  BasicBlock *ThenBlock) {
735  BasicBlock *Head = SplitBefore->getParent();
736  BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator());
737  Instruction *HeadOldTerm = Head->getTerminator();
738  LLVMContext &C = Head->getContext();
739  Instruction *CheckTerm;
740  bool CreateThenBlock = (ThenBlock == nullptr);
741  if (CreateThenBlock) {
742  ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
743  if (Unreachable)
744  CheckTerm = new UnreachableInst(C, ThenBlock);
745  else
746  CheckTerm = BranchInst::Create(Tail, ThenBlock);
747  CheckTerm->setDebugLoc(SplitBefore->getDebugLoc());
748  } else
749  CheckTerm = ThenBlock->getTerminator();
750  BranchInst *HeadNewTerm =
751  BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/Tail, Cond);
752  HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
753  ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
754 
755  if (DT) {
756  if (DomTreeNode *OldNode = DT->getNode(Head)) {
757  std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
758 
759  DomTreeNode *NewNode = DT->addNewBlock(Tail, Head);
760  for (DomTreeNode *Child : Children)
761  DT->changeImmediateDominator(Child, NewNode);
762 
763  // Head dominates ThenBlock.
764  if (CreateThenBlock)
765  DT->addNewBlock(ThenBlock, Head);
766  else
767  DT->changeImmediateDominator(ThenBlock, Head);
768  }
769  }
770 
771  if (LI) {
772  if (Loop *L = LI->getLoopFor(Head)) {
773  L->addBasicBlockToLoop(ThenBlock, *LI);
774  L->addBasicBlockToLoop(Tail, *LI);
775  }
776  }
777 
778  return CheckTerm;
779 }
780 
782  Instruction **ThenTerm,
783  Instruction **ElseTerm,
784  MDNode *BranchWeights) {
785  BasicBlock *Head = SplitBefore->getParent();
786  BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator());
787  Instruction *HeadOldTerm = Head->getTerminator();
788  LLVMContext &C = Head->getContext();
789  BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
790  BasicBlock *ElseBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
791  *ThenTerm = BranchInst::Create(Tail, ThenBlock);
792  (*ThenTerm)->setDebugLoc(SplitBefore->getDebugLoc());
793  *ElseTerm = BranchInst::Create(Tail, ElseBlock);
794  (*ElseTerm)->setDebugLoc(SplitBefore->getDebugLoc());
795  BranchInst *HeadNewTerm =
796  BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/ElseBlock, Cond);
797  HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
798  ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
799 }
800 
802  BasicBlock *&IfFalse) {
803  PHINode *SomePHI = dyn_cast<PHINode>(BB->begin());
804  BasicBlock *Pred1 = nullptr;
805  BasicBlock *Pred2 = nullptr;
806 
807  if (SomePHI) {
808  if (SomePHI->getNumIncomingValues() != 2)
809  return nullptr;
810  Pred1 = SomePHI->getIncomingBlock(0);
811  Pred2 = SomePHI->getIncomingBlock(1);
812  } else {
813  pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
814  if (PI == PE) // No predecessor
815  return nullptr;
816  Pred1 = *PI++;
817  if (PI == PE) // Only one predecessor
818  return nullptr;
819  Pred2 = *PI++;
820  if (PI != PE) // More than two predecessors
821  return nullptr;
822  }
823 
824  // We can only handle branches. Other control flow will be lowered to
825  // branches if possible anyway.
826  BranchInst *Pred1Br = dyn_cast<BranchInst>(Pred1->getTerminator());
827  BranchInst *Pred2Br = dyn_cast<BranchInst>(Pred2->getTerminator());
828  if (!Pred1Br || !Pred2Br)
829  return nullptr;
830 
831  // Eliminate code duplication by ensuring that Pred1Br is conditional if
832  // either are.
833  if (Pred2Br->isConditional()) {
834  // If both branches are conditional, we don't have an "if statement". In
835  // reality, we could transform this case, but since the condition will be
836  // required anyway, we stand no chance of eliminating it, so the xform is
837  // probably not profitable.
838  if (Pred1Br->isConditional())
839  return nullptr;
840 
841  std::swap(Pred1, Pred2);
842  std::swap(Pred1Br, Pred2Br);
843  }
844 
845  if (Pred1Br->isConditional()) {
846  // The only thing we have to watch out for here is to make sure that Pred2
847  // doesn't have incoming edges from other blocks. If it does, the condition
848  // doesn't dominate BB.
849  if (!Pred2->getSinglePredecessor())
850  return nullptr;
851 
852  // If we found a conditional branch predecessor, make sure that it branches
853  // to BB and Pred2Br. If it doesn't, this isn't an "if statement".
854  if (Pred1Br->getSuccessor(0) == BB &&
855  Pred1Br->getSuccessor(1) == Pred2) {
856  IfTrue = Pred1;
857  IfFalse = Pred2;
858  } else if (Pred1Br->getSuccessor(0) == Pred2 &&
859  Pred1Br->getSuccessor(1) == BB) {
860  IfTrue = Pred2;
861  IfFalse = Pred1;
862  } else {
863  // We know that one arm of the conditional goes to BB, so the other must
864  // go somewhere unrelated, and this must not be an "if statement".
865  return nullptr;
866  }
867 
868  return Pred1Br->getCondition();
869  }
870 
871  // Ok, if we got here, both predecessors end with an unconditional branch to
872  // BB. Don't panic! If both blocks only have a single (identical)
873  // predecessor, and THAT is a conditional branch, then we're all ok!
874  BasicBlock *CommonPred = Pred1->getSinglePredecessor();
875  if (CommonPred == nullptr || CommonPred != Pred2->getSinglePredecessor())
876  return nullptr;
877 
878  // Otherwise, if this is a conditional branch, then we can use it!
879  BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator());
880  if (!BI) return nullptr;
881 
882  assert(BI->isConditional() && "Two successors but not conditional?");
883  if (BI->getSuccessor(0) == Pred1) {
884  IfTrue = Pred1;
885  IfFalse = Pred2;
886  } else {
887  IfTrue = Pred2;
888  IfFalse = Pred1;
889  }
890  return BI->getCondition();
891 }
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.
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:689
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:1506
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
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:639
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:321
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:68
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.
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
self_iterator getIterator()
Definition: ilist_node.h:81
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:1414
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.
void deleteEdge(BasicBlock *From, BasicBlock *To)
Notify all available trees on an edge deletion.
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
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:839
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:512
Value * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
void wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New, ArrayRef< BasicBlock *> Preds, bool IdenticalEdgesWereMerged=true)
A new empty BasicBlock (New) now branches directly to Old.
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates, bool ForceRemoveDuplicates=false)
Apply updates on all available trees.
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:71
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:324
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:322
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:748
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