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