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