LLVM  15.0.0git
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"
24 #include "llvm/IR/BasicBlock.h"
25 #include "llvm/IR/CFG.h"
26 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/Dominators.h"
29 #include "llvm/IR/Function.h"
30 #include "llvm/IR/InstrTypes.h"
31 #include "llvm/IR/Instruction.h"
32 #include "llvm/IR/Instructions.h"
33 #include "llvm/IR/IntrinsicInst.h"
34 #include "llvm/IR/LLVMContext.h"
35 #include "llvm/IR/Type.h"
36 #include "llvm/IR/User.h"
37 #include "llvm/IR/Value.h"
38 #include "llvm/IR/ValueHandle.h"
39 #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 
55  "max-deopt-or-unreachable-succ-check-depth", cl::init(8), cl::Hidden,
56  cl::desc("Set the maximum path length when checking whether a basic block "
57  "is followed by a block that either has a terminating "
58  "deoptimizing call or is terminated with an unreachable"));
59 
63  bool KeepOneInputPHIs) {
64  for (auto *BB : BBs) {
65  // Loop through all of our successors and make sure they know that one
66  // of their predecessors is going away.
67  SmallPtrSet<BasicBlock *, 4> UniqueSuccessors;
68  for (BasicBlock *Succ : successors(BB)) {
69  Succ->removePredecessor(BB, KeepOneInputPHIs);
70  if (Updates && UniqueSuccessors.insert(Succ).second)
71  Updates->push_back({DominatorTree::Delete, BB, Succ});
72  }
73 
74  // Zap all the instructions in the block.
75  while (!BB->empty()) {
76  Instruction &I = BB->back();
77  // If this instruction is used, replace uses with an arbitrary value.
78  // Because control flow can't get here, we don't care what we replace the
79  // value with. Note that since this block is unreachable, and all values
80  // contained within it must dominate their uses, that all uses will
81  // eventually be removed (they are themselves dead).
82  if (!I.use_empty())
83  I.replaceAllUsesWith(UndefValue::get(I.getType()));
84  BB->getInstList().pop_back();
85  }
86  new UnreachableInst(BB->getContext(), BB);
87  assert(BB->getInstList().size() == 1 &&
88  isa<UnreachableInst>(BB->getTerminator()) &&
89  "The successor list of BB isn't empty before "
90  "applying corresponding DTU updates.");
91  }
92 }
93 
95  bool KeepOneInputPHIs) {
96  DeleteDeadBlocks({BB}, DTU, KeepOneInputPHIs);
97 }
98 
100  bool KeepOneInputPHIs) {
101 #ifndef NDEBUG
102  // Make sure that all predecessors of each dead block is also dead.
104  assert(Dead.size() == BBs.size() && "Duplicating blocks?");
105  for (auto *BB : Dead)
106  for (BasicBlock *Pred : predecessors(BB))
107  assert(Dead.count(Pred) && "All predecessors must be dead!");
108 #endif
109 
111  detachDeadBlocks(BBs, DTU ? &Updates : nullptr, KeepOneInputPHIs);
112 
113  if (DTU)
114  DTU->applyUpdates(Updates);
115 
116  for (BasicBlock *BB : BBs)
117  if (DTU)
118  DTU->deleteBB(BB);
119  else
120  BB->eraseFromParent();
121 }
122 
124  bool KeepOneInputPHIs) {
126 
127  // Mark all reachable blocks.
128  for (BasicBlock *BB : depth_first_ext(&F, Reachable))
129  (void)BB/* Mark all reachable blocks */;
130 
131  // Collect all dead blocks.
132  std::vector<BasicBlock*> DeadBlocks;
133  for (BasicBlock &BB : F)
134  if (!Reachable.count(&BB))
135  DeadBlocks.push_back(&BB);
136 
137  // Delete the dead blocks.
138  DeleteDeadBlocks(DeadBlocks, DTU, KeepOneInputPHIs);
139 
140  return !DeadBlocks.empty();
141 }
142 
144  MemoryDependenceResults *MemDep) {
145  if (!isa<PHINode>(BB->begin()))
146  return false;
147 
148  while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
149  if (PN->getIncomingValue(0) != PN)
150  PN->replaceAllUsesWith(PN->getIncomingValue(0));
151  else
152  PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
153 
154  if (MemDep)
155  MemDep->removeInstruction(PN); // Memdep updates AA itself.
156 
157  PN->eraseFromParent();
158  }
159  return true;
160 }
161 
163  MemorySSAUpdater *MSSAU) {
164  // Recursively deleting a PHI may cause multiple PHIs to be deleted
165  // or RAUW'd undef, so use an array of WeakTrackingVH for the PHIs to delete.
167  for (PHINode &PN : BB->phis())
168  PHIs.push_back(&PN);
169 
170  bool Changed = false;
171  for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
172  if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i].operator Value*()))
173  Changed |= RecursivelyDeleteDeadPHINode(PN, TLI, MSSAU);
174 
175  return Changed;
176 }
177 
179  LoopInfo *LI, MemorySSAUpdater *MSSAU,
180  MemoryDependenceResults *MemDep,
181  bool PredecessorWithTwoSuccessors) {
182  if (BB->hasAddressTaken())
183  return false;
184 
185  // Can't merge if there are multiple predecessors, or no predecessors.
186  BasicBlock *PredBB = BB->getUniquePredecessor();
187  if (!PredBB) return false;
188 
189  // Don't break self-loops.
190  if (PredBB == BB) return false;
191  // Don't break unwinding instructions.
192  if (PredBB->getTerminator()->isExceptionalTerminator())
193  return false;
194 
195  // Can't merge if there are multiple distinct successors.
196  if (!PredecessorWithTwoSuccessors && PredBB->getUniqueSuccessor() != BB)
197  return false;
198 
199  // Currently only allow PredBB to have two predecessors, one being BB.
200  // Update BI to branch to BB's only successor instead of BB.
201  BranchInst *PredBB_BI;
202  BasicBlock *NewSucc = nullptr;
203  unsigned FallThruPath;
204  if (PredecessorWithTwoSuccessors) {
205  if (!(PredBB_BI = dyn_cast<BranchInst>(PredBB->getTerminator())))
206  return false;
207  BranchInst *BB_JmpI = dyn_cast<BranchInst>(BB->getTerminator());
208  if (!BB_JmpI || !BB_JmpI->isUnconditional())
209  return false;
210  NewSucc = BB_JmpI->getSuccessor(0);
211  FallThruPath = PredBB_BI->getSuccessor(0) == BB ? 0 : 1;
212  }
213 
214  // Can't merge if there is PHI loop.
215  for (PHINode &PN : BB->phis())
216  if (llvm::is_contained(PN.incoming_values(), &PN))
217  return false;
218 
219  LLVM_DEBUG(dbgs() << "Merging: " << BB->getName() << " into "
220  << PredBB->getName() << "\n");
221 
222  // Begin by getting rid of unneeded PHIs.
223  SmallVector<AssertingVH<Value>, 4> IncomingValues;
224  if (isa<PHINode>(BB->front())) {
225  for (PHINode &PN : BB->phis())
226  if (!isa<PHINode>(PN.getIncomingValue(0)) ||
227  cast<PHINode>(PN.getIncomingValue(0))->getParent() != BB)
228  IncomingValues.push_back(PN.getIncomingValue(0));
229  FoldSingleEntryPHINodes(BB, MemDep);
230  }
231 
232  // DTU update: Collect all the edges that exit BB.
233  // These dominator edges will be redirected from Pred.
234  std::vector<DominatorTree::UpdateType> Updates;
235  if (DTU) {
236  // To avoid processing the same predecessor more than once.
238  SmallPtrSet<BasicBlock *, 2> SuccsOfPredBB(succ_begin(PredBB),
239  succ_end(PredBB));
240  Updates.reserve(Updates.size() + 2 * succ_size(BB) + 1);
241  // Add insert edges first. Experimentally, for the particular case of two
242  // blocks that can be merged, with a single successor and single predecessor
243  // respectively, it is beneficial to have all insert updates first. Deleting
244  // edges first may lead to unreachable blocks, followed by inserting edges
245  // making the blocks reachable again. Such DT updates lead to high compile
246  // times. We add inserts before deletes here to reduce compile time.
247  for (BasicBlock *SuccOfBB : successors(BB))
248  // This successor of BB may already be a PredBB's successor.
249  if (!SuccsOfPredBB.contains(SuccOfBB))
250  if (SeenSuccs.insert(SuccOfBB).second)
251  Updates.push_back({DominatorTree::Insert, PredBB, SuccOfBB});
252  SeenSuccs.clear();
253  for (BasicBlock *SuccOfBB : successors(BB))
254  if (SeenSuccs.insert(SuccOfBB).second)
255  Updates.push_back({DominatorTree::Delete, BB, SuccOfBB});
256  Updates.push_back({DominatorTree::Delete, PredBB, BB});
257  }
258 
259  Instruction *PTI = PredBB->getTerminator();
260  Instruction *STI = BB->getTerminator();
261  Instruction *Start = &*BB->begin();
262  // If there's nothing to move, mark the starting instruction as the last
263  // instruction in the block. Terminator instruction is handled separately.
264  if (Start == STI)
265  Start = PTI;
266 
267  // Move all definitions in the successor to the predecessor...
268  PredBB->getInstList().splice(PTI->getIterator(), BB->getInstList(),
269  BB->begin(), STI->getIterator());
270 
271  if (MSSAU)
272  MSSAU->moveAllAfterMergeBlocks(BB, PredBB, Start);
273 
274  // Make all PHI nodes that referred to BB now refer to Pred as their
275  // source...
276  BB->replaceAllUsesWith(PredBB);
277 
278  if (PredecessorWithTwoSuccessors) {
279  // Delete the unconditional branch from BB.
280  BB->getInstList().pop_back();
281 
282  // Update branch in the predecessor.
283  PredBB_BI->setSuccessor(FallThruPath, NewSucc);
284  } else {
285  // Delete the unconditional branch from the predecessor.
286  PredBB->getInstList().pop_back();
287 
288  // Move terminator instruction.
289  PredBB->getInstList().splice(PredBB->end(), BB->getInstList());
290 
291  // Terminator may be a memory accessing instruction too.
292  if (MSSAU)
293  if (MemoryUseOrDef *MUD = cast_or_null<MemoryUseOrDef>(
294  MSSAU->getMemorySSA()->getMemoryAccess(PredBB->getTerminator())))
295  MSSAU->moveToPlace(MUD, PredBB, MemorySSA::End);
296  }
297  // Add unreachable to now empty BB.
298  new UnreachableInst(BB->getContext(), BB);
299 
300  // Inherit predecessors name if it exists.
301  if (!PredBB->hasName())
302  PredBB->takeName(BB);
303 
304  if (LI)
305  LI->removeBlock(BB);
306 
307  if (MemDep)
309 
310  if (DTU)
311  DTU->applyUpdates(Updates);
312 
313  // Finally, erase the old block and update dominator info.
314  DeleteDeadBlock(BB, DTU);
315 
316  return true;
317 }
318 
320  SmallPtrSetImpl<BasicBlock *> &MergeBlocks, Loop *L, DomTreeUpdater *DTU,
321  LoopInfo *LI) {
322  assert(!MergeBlocks.empty() && "MergeBlocks should not be empty");
323 
324  bool BlocksHaveBeenMerged = false;
325  while (!MergeBlocks.empty()) {
326  BasicBlock *BB = *MergeBlocks.begin();
327  BasicBlock *Dest = BB->getSingleSuccessor();
328  if (Dest && (!L || L->contains(Dest))) {
329  BasicBlock *Fold = Dest->getUniquePredecessor();
330  (void)Fold;
331  if (MergeBlockIntoPredecessor(Dest, DTU, LI)) {
332  assert(Fold == BB &&
333  "Expecting BB to be unique predecessor of the Dest block");
334  MergeBlocks.erase(Dest);
335  BlocksHaveBeenMerged = true;
336  } else
337  MergeBlocks.erase(BB);
338  } else
339  MergeBlocks.erase(BB);
340  }
341  return BlocksHaveBeenMerged;
342 }
343 
344 /// Remove redundant instructions within sequences of consecutive dbg.value
345 /// instructions. This is done using a backward scan to keep the last dbg.value
346 /// describing a specific variable/fragment.
347 ///
348 /// BackwardScan strategy:
349 /// ----------------------
350 /// Given a sequence of consecutive DbgValueInst like this
351 ///
352 /// dbg.value ..., "x", FragmentX1 (*)
353 /// dbg.value ..., "y", FragmentY1
354 /// dbg.value ..., "x", FragmentX2
355 /// dbg.value ..., "x", FragmentX1 (**)
356 ///
357 /// then the instruction marked with (*) can be removed (it is guaranteed to be
358 /// obsoleted by the instruction marked with (**) as the latter instruction is
359 /// describing the same variable using the same fragment info).
360 ///
361 /// Possible improvements:
362 /// - Check fully overlapping fragments and not only identical fragments.
363 /// - Support dbg.addr, dbg.declare. dbg.label, and possibly other meta
364 /// instructions being part of the sequence of consecutive instructions.
366  SmallVector<DbgValueInst *, 8> ToBeRemoved;
367  SmallDenseSet<DebugVariable> VariableSet;
368  for (auto &I : reverse(*BB)) {
369  if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(&I)) {
370  DebugVariable Key(DVI->getVariable(),
371  DVI->getExpression(),
372  DVI->getDebugLoc()->getInlinedAt());
373  auto R = VariableSet.insert(Key);
374  // If the same variable fragment is described more than once it is enough
375  // to keep the last one (i.e. the first found since we for reverse
376  // iteration).
377  if (!R.second)
378  ToBeRemoved.push_back(DVI);
379  continue;
380  }
381  // Sequence with consecutive dbg.value instrs ended. Clear the map to
382  // restart identifying redundant instructions if case we find another
383  // dbg.value sequence.
384  VariableSet.clear();
385  }
386 
387  for (auto &Instr : ToBeRemoved)
388  Instr->eraseFromParent();
389 
390  return !ToBeRemoved.empty();
391 }
392 
393 /// Remove redundant dbg.value instructions using a forward scan. This can
394 /// remove a dbg.value instruction that is redundant due to indicating that a
395 /// variable has the same value as already being indicated by an earlier
396 /// dbg.value.
397 ///
398 /// ForwardScan strategy:
399 /// ---------------------
400 /// Given two identical dbg.value instructions, separated by a block of
401 /// instructions that isn't describing the same variable, like this
402 ///
403 /// dbg.value X1, "x", FragmentX1 (**)
404 /// <block of instructions, none being "dbg.value ..., "x", ...">
405 /// dbg.value X1, "x", FragmentX1 (*)
406 ///
407 /// then the instruction marked with (*) can be removed. Variable "x" is already
408 /// described as being mapped to the SSA value X1.
409 ///
410 /// Possible improvements:
411 /// - Keep track of non-overlapping fragments.
413  SmallVector<DbgValueInst *, 8> ToBeRemoved;
415  VariableMap;
416  for (auto &I : *BB) {
417  if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(&I)) {
418  DebugVariable Key(DVI->getVariable(),
419  NoneType(),
420  DVI->getDebugLoc()->getInlinedAt());
421  auto VMI = VariableMap.find(Key);
422  // Update the map if we found a new value/expression describing the
423  // variable, or if the variable wasn't mapped already.
424  SmallVector<Value *, 4> Values(DVI->getValues());
425  if (VMI == VariableMap.end() || VMI->second.first != Values ||
426  VMI->second.second != DVI->getExpression()) {
427  VariableMap[Key] = {Values, DVI->getExpression()};
428  continue;
429  }
430  // Found an identical mapping. Remember the instruction for later removal.
431  ToBeRemoved.push_back(DVI);
432  }
433  }
434 
435  for (auto &Instr : ToBeRemoved)
436  Instr->eraseFromParent();
437 
438  return !ToBeRemoved.empty();
439 }
440 
442  bool MadeChanges = false;
443  // By using the "backward scan" strategy before the "forward scan" strategy we
444  // can remove both dbg.value (2) and (3) in a situation like this:
445  //
446  // (1) dbg.value V1, "x", DIExpression()
447  // ...
448  // (2) dbg.value V2, "x", DIExpression()
449  // (3) dbg.value V1, "x", DIExpression()
450  //
451  // The backward scan will remove (2), it is made obsolete by (3). After
452  // getting (2) out of the way, the foward scan will remove (3) since "x"
453  // already is described as having the value V1 at (1).
456 
457  if (MadeChanges)
458  LLVM_DEBUG(dbgs() << "Removed redundant dbg instrs from: "
459  << BB->getName() << "\n");
460  return MadeChanges;
461 }
462 
464  BasicBlock::iterator &BI, Value *V) {
465  Instruction &I = *BI;
466  // Replaces all of the uses of the instruction with uses of the value
467  I.replaceAllUsesWith(V);
468 
469  // Make sure to propagate a name if there is one already.
470  if (I.hasName() && !V->hasName())
471  V->takeName(&I);
472 
473  // Delete the unnecessary instruction now...
474  BI = BIL.erase(BI);
475 }
476 
479  assert(I->getParent() == nullptr &&
480  "ReplaceInstWithInst: Instruction already inserted into basic block!");
481 
482  // Copy debug location to newly added instruction, if it wasn't already set
483  // by the caller.
484  if (!I->getDebugLoc())
485  I->setDebugLoc(BI->getDebugLoc());
486 
487  // Insert the new instruction into the basic block...
488  BasicBlock::iterator New = BIL.insert(BI, I);
489 
490  // Replace all uses of the old instruction, and delete it.
491  ReplaceInstWithValue(BIL, BI, I);
492 
493  // Move BI back to point to the newly inserted instruction
494  BI = New;
495 }
496 
498  // Remember visited blocks to avoid infinite loop
500  unsigned Depth = 0;
502  VisitedBlocks.insert(BB).second) {
503  if (BB->getTerminatingDeoptimizeCall() ||
504  isa<UnreachableInst>(BB->getTerminator()))
505  return true;
506  BB = BB->getUniqueSuccessor();
507  }
508  return false;
509 }
510 
513  ReplaceInstWithInst(From->getParent()->getInstList(), BI, To);
514 }
515 
517  LoopInfo *LI, MemorySSAUpdater *MSSAU,
518  const Twine &BBName) {
519  unsigned SuccNum = GetSuccessorNumber(BB, Succ);
520 
521  Instruction *LatchTerm = BB->getTerminator();
522 
525 
526  if ((isCriticalEdge(LatchTerm, SuccNum, Options.MergeIdenticalEdges))) {
527  // If it is a critical edge, and the succesor is an exception block, handle
528  // the split edge logic in this specific function
529  if (Succ->isEHPad())
530  return ehAwareSplitEdge(BB, Succ, nullptr, nullptr, Options, BBName);
531 
532  // If this is a critical edge, let SplitKnownCriticalEdge do it.
533  return SplitKnownCriticalEdge(LatchTerm, SuccNum, Options, BBName);
534  }
535 
536  // If the edge isn't critical, then BB has a single successor or Succ has a
537  // single pred. Split the block.
538  if (BasicBlock *SP = Succ->getSinglePredecessor()) {
539  // If the successor only has a single pred, split the top of the successor
540  // block.
541  assert(SP == BB && "CFG broken");
542  SP = nullptr;
543  return SplitBlock(Succ, &Succ->front(), DT, LI, MSSAU, BBName,
544  /*Before=*/true);
545  }
546 
547  // Otherwise, if BB has a single successor, split it at the bottom of the
548  // block.
549  assert(BB->getTerminator()->getNumSuccessors() == 1 &&
550  "Should have a single succ!");
551  return SplitBlock(BB, BB->getTerminator(), DT, LI, MSSAU, BBName);
552 }
553 
555  if (auto *II = dyn_cast<InvokeInst>(TI))
556  II->setUnwindDest(Succ);
557  else if (auto *CS = dyn_cast<CatchSwitchInst>(TI))
558  CS->setUnwindDest(Succ);
559  else if (auto *CR = dyn_cast<CleanupReturnInst>(TI))
560  CR->setUnwindDest(Succ);
561  else
562  llvm_unreachable("unexpected terminator instruction");
563 }
564 
566  BasicBlock *NewPred, PHINode *Until) {
567  int BBIdx = 0;
568  for (PHINode &PN : DestBB->phis()) {
569  // We manually update the LandingPadReplacement PHINode and it is the last
570  // PHI Node. So, if we find it, we are done.
571  if (Until == &PN)
572  break;
573 
574  // Reuse the previous value of BBIdx if it lines up. In cases where we
575  // have multiple phi nodes with *lots* of predecessors, this is a speed
576  // win because we don't have to scan the PHI looking for TIBB. This
577  // happens because the BB list of PHI nodes are usually in the same
578  // order.
579  if (PN.getIncomingBlock(BBIdx) != OldPred)
580  BBIdx = PN.getBasicBlockIndex(OldPred);
581 
582  assert(BBIdx != -1 && "Invalid PHI Index!");
583  PN.setIncomingBlock(BBIdx, NewPred);
584  }
585 }
586 
588  LandingPadInst *OriginalPad,
589  PHINode *LandingPadReplacement,
591  const Twine &BBName) {
592 
593  auto *PadInst = Succ->getFirstNonPHI();
594  if (!LandingPadReplacement && !PadInst->isEHPad())
595  return SplitEdge(BB, Succ, Options.DT, Options.LI, Options.MSSAU, BBName);
596 
597  auto *LI = Options.LI;
599  // Check if extra modifications will be required to preserve loop-simplify
600  // form after splitting. If it would require splitting blocks with IndirectBr
601  // terminators, bail out if preserving loop-simplify form is requested.
602  if (Options.PreserveLoopSimplify && LI) {
603  if (Loop *BBLoop = LI->getLoopFor(BB)) {
604 
605  // The only way that we can break LoopSimplify form by splitting a
606  // critical edge is when there exists some edge from BBLoop to Succ *and*
607  // the only edge into Succ from outside of BBLoop is that of NewBB after
608  // the split. If the first isn't true, then LoopSimplify still holds,
609  // NewBB is the new exit block and it has no non-loop predecessors. If the
610  // second isn't true, then Succ was not in LoopSimplify form prior to
611  // the split as it had a non-loop predecessor. In both of these cases,
612  // the predecessor must be directly in BBLoop, not in a subloop, or again
613  // LoopSimplify doesn't hold.
614  for (BasicBlock *P : predecessors(Succ)) {
615  if (P == BB)
616  continue; // The new block is known.
617  if (LI->getLoopFor(P) != BBLoop) {
618  // Loop is not in LoopSimplify form, no need to re simplify after
619  // splitting edge.
620  LoopPreds.clear();
621  break;
622  }
623  LoopPreds.push_back(P);
624  }
625  // Loop-simplify form can be preserved, if we can split all in-loop
626  // predecessors.
627  if (any_of(LoopPreds, [](BasicBlock *Pred) {
628  return isa<IndirectBrInst>(Pred->getTerminator());
629  })) {
630  return nullptr;
631  }
632  }
633  }
634 
635  auto *NewBB =
636  BasicBlock::Create(BB->getContext(), BBName, BB->getParent(), Succ);
637  setUnwindEdgeTo(BB->getTerminator(), NewBB);
638  updatePhiNodes(Succ, BB, NewBB, LandingPadReplacement);
639 
640  if (LandingPadReplacement) {
641  auto *NewLP = OriginalPad->clone();
642  auto *Terminator = BranchInst::Create(Succ, NewBB);
643  NewLP->insertBefore(Terminator);
644  LandingPadReplacement->addIncoming(NewLP, NewBB);
645  } else {
646  Value *ParentPad = nullptr;
647  if (auto *FuncletPad = dyn_cast<FuncletPadInst>(PadInst))
648  ParentPad = FuncletPad->getParentPad();
649  else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(PadInst))
650  ParentPad = CatchSwitch->getParentPad();
651  else if (auto *CleanupPad = dyn_cast<CleanupPadInst>(PadInst))
652  ParentPad = CleanupPad->getParentPad();
653  else if (auto *LandingPad = dyn_cast<LandingPadInst>(PadInst))
654  ParentPad = LandingPad->getParent();
655  else
656  llvm_unreachable("handling for other EHPads not implemented yet");
657 
658  auto *NewCleanupPad = CleanupPadInst::Create(ParentPad, {}, BBName, NewBB);
659  CleanupReturnInst::Create(NewCleanupPad, Succ, NewBB);
660  }
661 
662  auto *DT = Options.DT;
663  auto *MSSAU = Options.MSSAU;
664  if (!DT && !LI)
665  return NewBB;
666 
667  if (DT) {
670 
671  Updates.push_back({DominatorTree::Insert, BB, NewBB});
672  Updates.push_back({DominatorTree::Insert, NewBB, Succ});
673  Updates.push_back({DominatorTree::Delete, BB, Succ});
674 
675  DTU.applyUpdates(Updates);
676  DTU.flush();
677 
678  if (MSSAU) {
679  MSSAU->applyUpdates(Updates, *DT);
680  if (VerifyMemorySSA)
681  MSSAU->getMemorySSA()->verifyMemorySSA();
682  }
683  }
684 
685  if (LI) {
686  if (Loop *BBLoop = LI->getLoopFor(BB)) {
687  // If one or the other blocks were not in a loop, the new block is not
688  // either, and thus LI doesn't need to be updated.
689  if (Loop *SuccLoop = LI->getLoopFor(Succ)) {
690  if (BBLoop == SuccLoop) {
691  // Both in the same loop, the NewBB joins loop.
692  SuccLoop->addBasicBlockToLoop(NewBB, *LI);
693  } else if (BBLoop->contains(SuccLoop)) {
694  // Edge from an outer loop to an inner loop. Add to the outer loop.
695  BBLoop->addBasicBlockToLoop(NewBB, *LI);
696  } else if (SuccLoop->contains(BBLoop)) {
697  // Edge from an inner loop to an outer loop. Add to the outer loop.
698  SuccLoop->addBasicBlockToLoop(NewBB, *LI);
699  } else {
700  // Edge from two loops with no containment relation. Because these
701  // are natural loops, we know that the destination block must be the
702  // header of its loop (adding a branch into a loop elsewhere would
703  // create an irreducible loop).
704  assert(SuccLoop->getHeader() == Succ &&
705  "Should not create irreducible loops!");
706  if (Loop *P = SuccLoop->getParentLoop())
707  P->addBasicBlockToLoop(NewBB, *LI);
708  }
709  }
710 
711  // If BB is in a loop and Succ is outside of that loop, we may need to
712  // update LoopSimplify form and LCSSA form.
713  if (!BBLoop->contains(Succ)) {
714  assert(!BBLoop->contains(NewBB) &&
715  "Split point for loop exit is contained in loop!");
716 
717  // Update LCSSA form in the newly created exit block.
718  if (Options.PreserveLCSSA) {
719  createPHIsForSplitLoopExit(BB, NewBB, Succ);
720  }
721 
722  if (!LoopPreds.empty()) {
723  BasicBlock *NewExitBB = SplitBlockPredecessors(
724  Succ, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA);
725  if (Options.PreserveLCSSA)
726  createPHIsForSplitLoopExit(LoopPreds, NewExitBB, Succ);
727  }
728  }
729  }
730  }
731 
732  return NewBB;
733 }
734 
736  BasicBlock *SplitBB, BasicBlock *DestBB) {
737  // SplitBB shouldn't have anything non-trivial in it yet.
738  assert((SplitBB->getFirstNonPHI() == SplitBB->getTerminator() ||
739  SplitBB->isLandingPad()) &&
740  "SplitBB has non-PHI nodes!");
741 
742  // For each PHI in the destination block.
743  for (PHINode &PN : DestBB->phis()) {
744  int Idx = PN.getBasicBlockIndex(SplitBB);
745  assert(Idx >= 0 && "Invalid Block Index");
746  Value *V = PN.getIncomingValue(Idx);
747 
748  // If the input is a PHI which already satisfies LCSSA, don't create
749  // a new one.
750  if (const PHINode *VP = dyn_cast<PHINode>(V))
751  if (VP->getParent() == SplitBB)
752  continue;
753 
754  // Otherwise a new PHI is needed. Create one and populate it.
755  PHINode *NewPN = PHINode::Create(
756  PN.getType(), Preds.size(), "split",
757  SplitBB->isLandingPad() ? &SplitBB->front() : SplitBB->getTerminator());
758  for (BasicBlock *BB : Preds)
759  NewPN->addIncoming(V, BB);
760 
761  // Update the original PHI.
762  PN.setIncomingValue(Idx, NewPN);
763  }
764 }
765 
766 unsigned
769  unsigned NumBroken = 0;
770  for (BasicBlock &BB : F) {
771  Instruction *TI = BB.getTerminator();
772  if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI) &&
773  !isa<CallBrInst>(TI))
774  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
775  if (SplitCriticalEdge(TI, i, Options))
776  ++NumBroken;
777  }
778  return NumBroken;
779 }
780 
782  DomTreeUpdater *DTU, DominatorTree *DT,
783  LoopInfo *LI, MemorySSAUpdater *MSSAU,
784  const Twine &BBName, bool Before) {
785  if (Before) {
787  return splitBlockBefore(Old, SplitPt,
788  DTU ? DTU : (DT ? &LocalDTU : nullptr), LI, MSSAU,
789  BBName);
790  }
791  BasicBlock::iterator SplitIt = SplitPt->getIterator();
792  while (isa<PHINode>(SplitIt) || SplitIt->isEHPad()) {
793  ++SplitIt;
794  assert(SplitIt != SplitPt->getParent()->end());
795  }
796  std::string Name = BBName.str();
797  BasicBlock *New = Old->splitBasicBlock(
798  SplitIt, Name.empty() ? Old->getName() + ".split" : Name);
799 
800  // The new block lives in whichever loop the old one did. This preserves
801  // LCSSA as well, because we force the split point to be after any PHI nodes.
802  if (LI)
803  if (Loop *L = LI->getLoopFor(Old))
804  L->addBasicBlockToLoop(New, *LI);
805 
806  if (DTU) {
808  // Old dominates New. New node dominates all other nodes dominated by Old.
809  SmallPtrSet<BasicBlock *, 8> UniqueSuccessorsOfOld;
810  Updates.push_back({DominatorTree::Insert, Old, New});
811  Updates.reserve(Updates.size() + 2 * succ_size(New));
812  for (BasicBlock *SuccessorOfOld : successors(New))
813  if (UniqueSuccessorsOfOld.insert(SuccessorOfOld).second) {
814  Updates.push_back({DominatorTree::Insert, New, SuccessorOfOld});
815  Updates.push_back({DominatorTree::Delete, Old, SuccessorOfOld});
816  }
817 
818  DTU->applyUpdates(Updates);
819  } else if (DT)
820  // Old dominates New. New node dominates all other nodes dominated by Old.
821  if (DomTreeNode *OldNode = DT->getNode(Old)) {
822  std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
823 
824  DomTreeNode *NewNode = DT->addNewBlock(New, Old);
825  for (DomTreeNode *I : Children)
826  DT->changeImmediateDominator(I, NewNode);
827  }
828 
829  // Move MemoryAccesses still tracked in Old, but part of New now.
830  // Update accesses in successor blocks accordingly.
831  if (MSSAU)
832  MSSAU->moveAllAfterSpliceBlocks(Old, New, &*(New->begin()));
833 
834  return New;
835 }
836 
838  DominatorTree *DT, LoopInfo *LI,
839  MemorySSAUpdater *MSSAU, const Twine &BBName,
840  bool Before) {
841  return SplitBlockImpl(Old, SplitPt, /*DTU=*/nullptr, DT, LI, MSSAU, BBName,
842  Before);
843 }
845  DomTreeUpdater *DTU, LoopInfo *LI,
846  MemorySSAUpdater *MSSAU, const Twine &BBName,
847  bool Before) {
848  return SplitBlockImpl(Old, SplitPt, DTU, /*DT=*/nullptr, LI, MSSAU, BBName,
849  Before);
850 }
851 
853  DomTreeUpdater *DTU, LoopInfo *LI,
854  MemorySSAUpdater *MSSAU,
855  const Twine &BBName) {
856 
857  BasicBlock::iterator SplitIt = SplitPt->getIterator();
858  while (isa<PHINode>(SplitIt) || SplitIt->isEHPad())
859  ++SplitIt;
860  std::string Name = BBName.str();
861  BasicBlock *New = Old->splitBasicBlock(
862  SplitIt, Name.empty() ? Old->getName() + ".split" : Name,
863  /* Before=*/true);
864 
865  // The new block lives in whichever loop the old one did. This preserves
866  // LCSSA as well, because we force the split point to be after any PHI nodes.
867  if (LI)
868  if (Loop *L = LI->getLoopFor(Old))
869  L->addBasicBlockToLoop(New, *LI);
870 
871  if (DTU) {
873  // New dominates Old. The predecessor nodes of the Old node dominate
874  // New node.
875  SmallPtrSet<BasicBlock *, 8> UniquePredecessorsOfOld;
876  DTUpdates.push_back({DominatorTree::Insert, New, Old});
877  DTUpdates.reserve(DTUpdates.size() + 2 * pred_size(New));
878  for (BasicBlock *PredecessorOfOld : predecessors(New))
879  if (UniquePredecessorsOfOld.insert(PredecessorOfOld).second) {
880  DTUpdates.push_back({DominatorTree::Insert, PredecessorOfOld, New});
881  DTUpdates.push_back({DominatorTree::Delete, PredecessorOfOld, Old});
882  }
883 
884  DTU->applyUpdates(DTUpdates);
885 
886  // Move MemoryAccesses still tracked in Old, but part of New now.
887  // Update accesses in successor blocks accordingly.
888  if (MSSAU) {
889  MSSAU->applyUpdates(DTUpdates, DTU->getDomTree());
890  if (VerifyMemorySSA)
891  MSSAU->getMemorySSA()->verifyMemorySSA();
892  }
893  }
894  return New;
895 }
896 
897 /// Update DominatorTree, LoopInfo, and LCCSA analysis information.
900  DomTreeUpdater *DTU, DominatorTree *DT,
901  LoopInfo *LI, MemorySSAUpdater *MSSAU,
902  bool PreserveLCSSA, bool &HasLoopExit) {
903  // Update dominator tree if available.
904  if (DTU) {
905  // Recalculation of DomTree is needed when updating a forward DomTree and
906  // the Entry BB is replaced.
907  if (NewBB->isEntryBlock() && DTU->hasDomTree()) {
908  // The entry block was removed and there is no external interface for
909  // the dominator tree to be notified of this change. In this corner-case
910  // we recalculate the entire tree.
911  DTU->recalculate(*NewBB->getParent());
912  } else {
913  // Split block expects NewBB to have a non-empty set of predecessors.
915  SmallPtrSet<BasicBlock *, 8> UniquePreds;
916  Updates.push_back({DominatorTree::Insert, NewBB, OldBB});
917  Updates.reserve(Updates.size() + 2 * Preds.size());
918  for (auto *Pred : Preds)
919  if (UniquePreds.insert(Pred).second) {
920  Updates.push_back({DominatorTree::Insert, Pred, NewBB});
921  Updates.push_back({DominatorTree::Delete, Pred, OldBB});
922  }
923  DTU->applyUpdates(Updates);
924  }
925  } else if (DT) {
926  if (OldBB == DT->getRootNode()->getBlock()) {
927  assert(NewBB->isEntryBlock());
928  DT->setNewRoot(NewBB);
929  } else {
930  // Split block expects NewBB to have a non-empty set of predecessors.
931  DT->splitBlock(NewBB);
932  }
933  }
934 
935  // Update MemoryPhis after split if MemorySSA is available
936  if (MSSAU)
937  MSSAU->wireOldPredecessorsToNewImmediatePredecessor(OldBB, NewBB, Preds);
938 
939  // The rest of the logic is only relevant for updating the loop structures.
940  if (!LI)
941  return;
942 
943  if (DTU && DTU->hasDomTree())
944  DT = &DTU->getDomTree();
945  assert(DT && "DT should be available to update LoopInfo!");
946  Loop *L = LI->getLoopFor(OldBB);
947 
948  // If we need to preserve loop analyses, collect some information about how
949  // this split will affect loops.
950  bool IsLoopEntry = !!L;
951  bool SplitMakesNewLoopHeader = false;
952  for (BasicBlock *Pred : Preds) {
953  // Preds that are not reachable from entry should not be used to identify if
954  // OldBB is a loop entry or if SplitMakesNewLoopHeader. Unreachable blocks
955  // are not within any loops, so we incorrectly mark SplitMakesNewLoopHeader
956  // as true and make the NewBB the header of some loop. This breaks LI.
957  if (!DT->isReachableFromEntry(Pred))
958  continue;
959  // If we need to preserve LCSSA, determine if any of the preds is a loop
960  // exit.
961  if (PreserveLCSSA)
962  if (Loop *PL = LI->getLoopFor(Pred))
963  if (!PL->contains(OldBB))
964  HasLoopExit = true;
965 
966  // If we need to preserve LoopInfo, note whether any of the preds crosses
967  // an interesting loop boundary.
968  if (!L)
969  continue;
970  if (L->contains(Pred))
971  IsLoopEntry = false;
972  else
973  SplitMakesNewLoopHeader = true;
974  }
975 
976  // Unless we have a loop for OldBB, nothing else to do here.
977  if (!L)
978  return;
979 
980  if (IsLoopEntry) {
981  // Add the new block to the nearest enclosing loop (and not an adjacent
982  // loop). To find this, examine each of the predecessors and determine which
983  // loops enclose them, and select the most-nested loop which contains the
984  // loop containing the block being split.
985  Loop *InnermostPredLoop = nullptr;
986  for (BasicBlock *Pred : Preds) {
987  if (Loop *PredLoop = LI->getLoopFor(Pred)) {
988  // Seek a loop which actually contains the block being split (to avoid
989  // adjacent loops).
990  while (PredLoop && !PredLoop->contains(OldBB))
991  PredLoop = PredLoop->getParentLoop();
992 
993  // Select the most-nested of these loops which contains the block.
994  if (PredLoop && PredLoop->contains(OldBB) &&
995  (!InnermostPredLoop ||
996  InnermostPredLoop->getLoopDepth() < PredLoop->getLoopDepth()))
997  InnermostPredLoop = PredLoop;
998  }
999  }
1000 
1001  if (InnermostPredLoop)
1002  InnermostPredLoop->addBasicBlockToLoop(NewBB, *LI);
1003  } else {
1004  L->addBasicBlockToLoop(NewBB, *LI);
1005  if (SplitMakesNewLoopHeader)
1006  L->moveToHeader(NewBB);
1007  }
1008 }
1009 
1010 /// Update the PHI nodes in OrigBB to include the values coming from NewBB.
1011 /// This also updates AliasAnalysis, if available.
1012 static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB,
1014  bool HasLoopExit) {
1015  // Otherwise, create a new PHI node in NewBB for each PHI node in OrigBB.
1016  SmallPtrSet<BasicBlock *, 16> PredSet(Preds.begin(), Preds.end());
1017  for (BasicBlock::iterator I = OrigBB->begin(); isa<PHINode>(I); ) {
1018  PHINode *PN = cast<PHINode>(I++);
1019 
1020  // Check to see if all of the values coming in are the same. If so, we
1021  // don't need to create a new PHI node, unless it's needed for LCSSA.
1022  Value *InVal = nullptr;
1023  if (!HasLoopExit) {
1024  InVal = PN->getIncomingValueForBlock(Preds[0]);
1025  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1026  if (!PredSet.count(PN->getIncomingBlock(i)))
1027  continue;
1028  if (!InVal)
1029  InVal = PN->getIncomingValue(i);
1030  else if (InVal != PN->getIncomingValue(i)) {
1031  InVal = nullptr;
1032  break;
1033  }
1034  }
1035  }
1036 
1037  if (InVal) {
1038  // If all incoming values for the new PHI would be the same, just don't
1039  // make a new PHI. Instead, just remove the incoming values from the old
1040  // PHI.
1041 
1042  // NOTE! This loop walks backwards for a reason! First off, this minimizes
1043  // the cost of removal if we end up removing a large number of values, and
1044  // second off, this ensures that the indices for the incoming values
1045  // aren't invalidated when we remove one.
1046  for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i)
1047  if (PredSet.count(PN->getIncomingBlock(i)))
1048  PN->removeIncomingValue(i, false);
1049 
1050  // Add an incoming value to the PHI node in the loop for the preheader
1051  // edge.
1052  PN->addIncoming(InVal, NewBB);
1053  continue;
1054  }
1055 
1056  // If the values coming into the block are not the same, we need a new
1057  // PHI.
1058  // Create the new PHI node, insert it into NewBB at the end of the block
1059  PHINode *NewPHI =
1060  PHINode::Create(PN->getType(), Preds.size(), PN->getName() + ".ph", BI);
1061 
1062  // NOTE! This loop walks backwards for a reason! First off, this minimizes
1063  // the cost of removal if we end up removing a large number of values, and
1064  // second off, this ensures that the indices for the incoming values aren't
1065  // invalidated when we remove one.
1066  for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) {
1067  BasicBlock *IncomingBB = PN->getIncomingBlock(i);
1068  if (PredSet.count(IncomingBB)) {
1069  Value *V = PN->removeIncomingValue(i, false);
1070  NewPHI->addIncoming(V, IncomingBB);
1071  }
1072  }
1073 
1074  PN->addIncoming(NewPHI, NewBB);
1075  }
1076 }
1077 
1079  BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix1,
1080  const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs,
1081  DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI,
1082  MemorySSAUpdater *MSSAU, bool PreserveLCSSA);
1083 
1084 static BasicBlock *
1086  const char *Suffix, DomTreeUpdater *DTU,
1087  DominatorTree *DT, LoopInfo *LI,
1088  MemorySSAUpdater *MSSAU, bool PreserveLCSSA) {
1089  // Do not attempt to split that which cannot be split.
1090  if (!BB->canSplitPredecessors())
1091  return nullptr;
1092 
1093  // For the landingpads we need to act a bit differently.
1094  // Delegate this work to the SplitLandingPadPredecessors.
1095  if (BB->isLandingPad()) {
1097  std::string NewName = std::string(Suffix) + ".split-lp";
1098 
1099  SplitLandingPadPredecessorsImpl(BB, Preds, Suffix, NewName.c_str(), NewBBs,
1100  DTU, DT, LI, MSSAU, PreserveLCSSA);
1101  return NewBBs[0];
1102  }
1103 
1104  // Create new basic block, insert right before the original block.
1105  BasicBlock *NewBB = BasicBlock::Create(
1106  BB->getContext(), BB->getName() + Suffix, BB->getParent(), BB);
1107 
1108  // The new block unconditionally branches to the old block.
1109  BranchInst *BI = BranchInst::Create(BB, NewBB);
1110 
1111  Loop *L = nullptr;
1112  BasicBlock *OldLatch = nullptr;
1113  // Splitting the predecessors of a loop header creates a preheader block.
1114  if (LI && LI->isLoopHeader(BB)) {
1115  L = LI->getLoopFor(BB);
1116  // Using the loop start line number prevents debuggers stepping into the
1117  // loop body for this instruction.
1118  BI->setDebugLoc(L->getStartLoc());
1119 
1120  // If BB is the header of the Loop, it is possible that the loop is
1121  // modified, such that the current latch does not remain the latch of the
1122  // loop. If that is the case, the loop metadata from the current latch needs
1123  // to be applied to the new latch.
1124  OldLatch = L->getLoopLatch();
1125  } else
1126  BI->setDebugLoc(BB->getFirstNonPHIOrDbg()->getDebugLoc());
1127 
1128  // Move the edges from Preds to point to NewBB instead of BB.
1129  for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
1130  // This is slightly more strict than necessary; the minimum requirement
1131  // is that there be no more than one indirectbr branching to BB. And
1132  // all BlockAddress uses would need to be updated.
1133  assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&
1134  "Cannot split an edge from an IndirectBrInst");
1135  assert(!isa<CallBrInst>(Preds[i]->getTerminator()) &&
1136  "Cannot split an edge from a CallBrInst");
1137  Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB);
1138  }
1139 
1140  // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI
1141  // node becomes an incoming value for BB's phi node. However, if the Preds
1142  // list is empty, we need to insert dummy entries into the PHI nodes in BB to
1143  // account for the newly created predecessor.
1144  if (Preds.empty()) {
1145  // Insert dummy values as the incoming value.
1146  for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I)
1147  cast<PHINode>(I)->addIncoming(UndefValue::get(I->getType()), NewBB);
1148  }
1149 
1150  // Update DominatorTree, LoopInfo, and LCCSA analysis information.
1151  bool HasLoopExit = false;
1152  UpdateAnalysisInformation(BB, NewBB, Preds, DTU, DT, LI, MSSAU, PreserveLCSSA,
1153  HasLoopExit);
1154 
1155  if (!Preds.empty()) {
1156  // Update the PHI nodes in BB with the values coming from NewBB.
1157  UpdatePHINodes(BB, NewBB, Preds, BI, HasLoopExit);
1158  }
1159 
1160  if (OldLatch) {
1161  BasicBlock *NewLatch = L->getLoopLatch();
1162  if (NewLatch != OldLatch) {
1163  MDNode *MD = OldLatch->getTerminator()->getMetadata("llvm.loop");
1164  NewLatch->getTerminator()->setMetadata("llvm.loop", MD);
1165  // It's still possible that OldLatch is the latch of another inner loop,
1166  // in which case we do not remove the metadata.
1167  Loop *IL = LI->getLoopFor(OldLatch);
1168  if (IL && IL->getLoopLatch() != OldLatch)
1169  OldLatch->getTerminator()->setMetadata("llvm.loop", nullptr);
1170  }
1171  }
1172 
1173  return NewBB;
1174 }
1175 
1177  ArrayRef<BasicBlock *> Preds,
1178  const char *Suffix, DominatorTree *DT,
1179  LoopInfo *LI, MemorySSAUpdater *MSSAU,
1180  bool PreserveLCSSA) {
1181  return SplitBlockPredecessorsImpl(BB, Preds, Suffix, /*DTU=*/nullptr, DT, LI,
1182  MSSAU, PreserveLCSSA);
1183 }
1185  ArrayRef<BasicBlock *> Preds,
1186  const char *Suffix,
1187  DomTreeUpdater *DTU, LoopInfo *LI,
1188  MemorySSAUpdater *MSSAU,
1189  bool PreserveLCSSA) {
1190  return SplitBlockPredecessorsImpl(BB, Preds, Suffix, DTU,
1191  /*DT=*/nullptr, LI, MSSAU, PreserveLCSSA);
1192 }
1193 
1195  BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix1,
1196  const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs,
1197  DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI,
1198  MemorySSAUpdater *MSSAU, bool PreserveLCSSA) {
1199  assert(OrigBB->isLandingPad() && "Trying to split a non-landing pad!");
1200 
1201  // Create a new basic block for OrigBB's predecessors listed in Preds. Insert
1202  // it right before the original block.
1203  BasicBlock *NewBB1 = BasicBlock::Create(OrigBB->getContext(),
1204  OrigBB->getName() + Suffix1,
1205  OrigBB->getParent(), OrigBB);
1206  NewBBs.push_back(NewBB1);
1207 
1208  // The new block unconditionally branches to the old block.
1209  BranchInst *BI1 = BranchInst::Create(OrigBB, NewBB1);
1210  BI1->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc());
1211 
1212  // Move the edges from Preds to point to NewBB1 instead of OrigBB.
1213  for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
1214  // This is slightly more strict than necessary; the minimum requirement
1215  // is that there be no more than one indirectbr branching to BB. And
1216  // all BlockAddress uses would need to be updated.
1217  assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&
1218  "Cannot split an edge from an IndirectBrInst");
1219  Preds[i]->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1);
1220  }
1221 
1222  bool HasLoopExit = false;
1223  UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DTU, DT, LI, MSSAU,
1224  PreserveLCSSA, HasLoopExit);
1225 
1226  // Update the PHI nodes in OrigBB with the values coming from NewBB1.
1227  UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, HasLoopExit);
1228 
1229  // Move the remaining edges from OrigBB to point to NewBB2.
1230  SmallVector<BasicBlock*, 8> NewBB2Preds;
1231  for (pred_iterator i = pred_begin(OrigBB), e = pred_end(OrigBB);
1232  i != e; ) {
1233  BasicBlock *Pred = *i++;
1234  if (Pred == NewBB1) continue;
1235  assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
1236  "Cannot split an edge from an IndirectBrInst");
1237  NewBB2Preds.push_back(Pred);
1238  e = pred_end(OrigBB);
1239  }
1240 
1241  BasicBlock *NewBB2 = nullptr;
1242  if (!NewBB2Preds.empty()) {
1243  // Create another basic block for the rest of OrigBB's predecessors.
1244  NewBB2 = BasicBlock::Create(OrigBB->getContext(),
1245  OrigBB->getName() + Suffix2,
1246  OrigBB->getParent(), OrigBB);
1247  NewBBs.push_back(NewBB2);
1248 
1249  // The new block unconditionally branches to the old block.
1250  BranchInst *BI2 = BranchInst::Create(OrigBB, NewBB2);
1251  BI2->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc());
1252 
1253  // Move the remaining edges from OrigBB to point to NewBB2.
1254  for (BasicBlock *NewBB2Pred : NewBB2Preds)
1255  NewBB2Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2);
1256 
1257  // Update DominatorTree, LoopInfo, and LCCSA analysis information.
1258  HasLoopExit = false;
1259  UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DTU, DT, LI, MSSAU,
1260  PreserveLCSSA, HasLoopExit);
1261 
1262  // Update the PHI nodes in OrigBB with the values coming from NewBB2.
1263  UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, HasLoopExit);
1264  }
1265 
1266  LandingPadInst *LPad = OrigBB->getLandingPadInst();
1267  Instruction *Clone1 = LPad->clone();
1268  Clone1->setName(Twine("lpad") + Suffix1);
1269  NewBB1->getInstList().insert(NewBB1->getFirstInsertionPt(), Clone1);
1270 
1271  if (NewBB2) {
1272  Instruction *Clone2 = LPad->clone();
1273  Clone2->setName(Twine("lpad") + Suffix2);
1274  NewBB2->getInstList().insert(NewBB2->getFirstInsertionPt(), Clone2);
1275 
1276  // Create a PHI node for the two cloned landingpad instructions only
1277  // if the original landingpad instruction has some uses.
1278  if (!LPad->use_empty()) {
1279  assert(!LPad->getType()->isTokenTy() &&
1280  "Split cannot be applied if LPad is token type. Otherwise an "
1281  "invalid PHINode of token type would be created.");
1282  PHINode *PN = PHINode::Create(LPad->getType(), 2, "lpad.phi", LPad);
1283  PN->addIncoming(Clone1, NewBB1);
1284  PN->addIncoming(Clone2, NewBB2);
1285  LPad->replaceAllUsesWith(PN);
1286  }
1287  LPad->eraseFromParent();
1288  } else {
1289  // There is no second clone. Just replace the landing pad with the first
1290  // clone.
1291  LPad->replaceAllUsesWith(Clone1);
1292  LPad->eraseFromParent();
1293  }
1294 }
1295 
1297  ArrayRef<BasicBlock *> Preds,
1298  const char *Suffix1, const char *Suffix2,
1300  DominatorTree *DT, LoopInfo *LI,
1301  MemorySSAUpdater *MSSAU,
1302  bool PreserveLCSSA) {
1304  OrigBB, Preds, Suffix1, Suffix2, NewBBs,
1305  /*DTU=*/nullptr, DT, LI, MSSAU, PreserveLCSSA);
1306 }
1308  ArrayRef<BasicBlock *> Preds,
1309  const char *Suffix1, const char *Suffix2,
1311  DomTreeUpdater *DTU, LoopInfo *LI,
1312  MemorySSAUpdater *MSSAU,
1313  bool PreserveLCSSA) {
1314  return SplitLandingPadPredecessorsImpl(OrigBB, Preds, Suffix1, Suffix2,
1315  NewBBs, DTU, /*DT=*/nullptr, LI, MSSAU,
1316  PreserveLCSSA);
1317 }
1318 
1320  BasicBlock *Pred,
1321  DomTreeUpdater *DTU) {
1322  Instruction *UncondBranch = Pred->getTerminator();
1323  // Clone the return and add it to the end of the predecessor.
1324  Instruction *NewRet = RI->clone();
1325  Pred->getInstList().push_back(NewRet);
1326 
1327  // If the return instruction returns a value, and if the value was a
1328  // PHI node in "BB", propagate the right value into the return.
1329  for (Use &Op : NewRet->operands()) {
1330  Value *V = Op;
1331  Instruction *NewBC = nullptr;
1332  if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) {
1333  // Return value might be bitcasted. Clone and insert it before the
1334  // return instruction.
1335  V = BCI->getOperand(0);
1336  NewBC = BCI->clone();
1337  Pred->getInstList().insert(NewRet->getIterator(), NewBC);
1338  Op = NewBC;
1339  }
1340 
1341  Instruction *NewEV = nullptr;
1342  if (ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(V)) {
1343  V = EVI->getOperand(0);
1344  NewEV = EVI->clone();
1345  if (NewBC) {
1346  NewBC->setOperand(0, NewEV);
1347  Pred->getInstList().insert(NewBC->getIterator(), NewEV);
1348  } else {
1349  Pred->getInstList().insert(NewRet->getIterator(), NewEV);
1350  Op = NewEV;
1351  }
1352  }
1353 
1354  if (PHINode *PN = dyn_cast<PHINode>(V)) {
1355  if (PN->getParent() == BB) {
1356  if (NewEV) {
1357  NewEV->setOperand(0, PN->getIncomingValueForBlock(Pred));
1358  } else if (NewBC)
1359  NewBC->setOperand(0, PN->getIncomingValueForBlock(Pred));
1360  else
1361  Op = PN->getIncomingValueForBlock(Pred);
1362  }
1363  }
1364  }
1365 
1366  // Update any PHI nodes in the returning block to realize that we no
1367  // longer branch to them.
1368  BB->removePredecessor(Pred);
1369  UncondBranch->eraseFromParent();
1370 
1371  if (DTU)
1372  DTU->applyUpdates({{DominatorTree::Delete, Pred, BB}});
1373 
1374  return cast<ReturnInst>(NewRet);
1375 }
1376 
1377 static Instruction *
1379  bool Unreachable, MDNode *BranchWeights,
1380  DomTreeUpdater *DTU, DominatorTree *DT,
1381  LoopInfo *LI, BasicBlock *ThenBlock) {
1383  BasicBlock *Head = SplitBefore->getParent();
1384  BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator());
1385  if (DTU) {
1386  SmallPtrSet<BasicBlock *, 8> UniqueSuccessorsOfHead;
1387  Updates.push_back({DominatorTree::Insert, Head, Tail});
1388  Updates.reserve(Updates.size() + 2 * succ_size(Tail));
1389  for (BasicBlock *SuccessorOfHead : successors(Tail))
1390  if (UniqueSuccessorsOfHead.insert(SuccessorOfHead).second) {
1391  Updates.push_back({DominatorTree::Insert, Tail, SuccessorOfHead});
1392  Updates.push_back({DominatorTree::Delete, Head, SuccessorOfHead});
1393  }
1394  }
1395  Instruction *HeadOldTerm = Head->getTerminator();
1396  LLVMContext &C = Head->getContext();
1397  Instruction *CheckTerm;
1398  bool CreateThenBlock = (ThenBlock == nullptr);
1399  if (CreateThenBlock) {
1400  ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
1401  if (Unreachable)
1402  CheckTerm = new UnreachableInst(C, ThenBlock);
1403  else {
1404  CheckTerm = BranchInst::Create(Tail, ThenBlock);
1405  if (DTU)
1406  Updates.push_back({DominatorTree::Insert, ThenBlock, Tail});
1407  }
1408  CheckTerm->setDebugLoc(SplitBefore->getDebugLoc());
1409  } else
1410  CheckTerm = ThenBlock->getTerminator();
1411  BranchInst *HeadNewTerm =
1412  BranchInst::Create(/*ifTrue*/ ThenBlock, /*ifFalse*/ Tail, Cond);
1413  if (DTU)
1414  Updates.push_back({DominatorTree::Insert, Head, ThenBlock});
1415  HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
1416  ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
1417 
1418  if (DTU)
1419  DTU->applyUpdates(Updates);
1420  else if (DT) {
1421  if (DomTreeNode *OldNode = DT->getNode(Head)) {
1422  std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
1423 
1424  DomTreeNode *NewNode = DT->addNewBlock(Tail, Head);
1425  for (DomTreeNode *Child : Children)
1426  DT->changeImmediateDominator(Child, NewNode);
1427 
1428  // Head dominates ThenBlock.
1429  if (CreateThenBlock)
1430  DT->addNewBlock(ThenBlock, Head);
1431  else
1432  DT->changeImmediateDominator(ThenBlock, Head);
1433  }
1434  }
1435 
1436  if (LI) {
1437  if (Loop *L = LI->getLoopFor(Head)) {
1438  L->addBasicBlockToLoop(ThenBlock, *LI);
1439  L->addBasicBlockToLoop(Tail, *LI);
1440  }
1441  }
1442 
1443  return CheckTerm;
1444 }
1445 
1447  Instruction *SplitBefore,
1448  bool Unreachable,
1449  MDNode *BranchWeights,
1450  DominatorTree *DT, LoopInfo *LI,
1451  BasicBlock *ThenBlock) {
1452  return SplitBlockAndInsertIfThenImpl(Cond, SplitBefore, Unreachable,
1453  BranchWeights,
1454  /*DTU=*/nullptr, DT, LI, ThenBlock);
1455 }
1457  Instruction *SplitBefore,
1458  bool Unreachable,
1459  MDNode *BranchWeights,
1460  DomTreeUpdater *DTU, LoopInfo *LI,
1461  BasicBlock *ThenBlock) {
1462  return SplitBlockAndInsertIfThenImpl(Cond, SplitBefore, Unreachable,
1463  BranchWeights, DTU, /*DT=*/nullptr, LI,
1464  ThenBlock);
1465 }
1466 
1468  Instruction **ThenTerm,
1469  Instruction **ElseTerm,
1470  MDNode *BranchWeights) {
1471  BasicBlock *Head = SplitBefore->getParent();
1472  BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator());
1473  Instruction *HeadOldTerm = Head->getTerminator();
1474  LLVMContext &C = Head->getContext();
1475  BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
1476  BasicBlock *ElseBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
1477  *ThenTerm = BranchInst::Create(Tail, ThenBlock);
1478  (*ThenTerm)->setDebugLoc(SplitBefore->getDebugLoc());
1479  *ElseTerm = BranchInst::Create(Tail, ElseBlock);
1480  (*ElseTerm)->setDebugLoc(SplitBefore->getDebugLoc());
1481  BranchInst *HeadNewTerm =
1482  BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/ElseBlock, Cond);
1483  HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
1484  ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
1485 }
1486 
1488  BasicBlock *&IfFalse) {
1489  PHINode *SomePHI = dyn_cast<PHINode>(BB->begin());
1490  BasicBlock *Pred1 = nullptr;
1491  BasicBlock *Pred2 = nullptr;
1492 
1493  if (SomePHI) {
1494  if (SomePHI->getNumIncomingValues() != 2)
1495  return nullptr;
1496  Pred1 = SomePHI->getIncomingBlock(0);
1497  Pred2 = SomePHI->getIncomingBlock(1);
1498  } else {
1499  pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1500  if (PI == PE) // No predecessor
1501  return nullptr;
1502  Pred1 = *PI++;
1503  if (PI == PE) // Only one predecessor
1504  return nullptr;
1505  Pred2 = *PI++;
1506  if (PI != PE) // More than two predecessors
1507  return nullptr;
1508  }
1509 
1510  // We can only handle branches. Other control flow will be lowered to
1511  // branches if possible anyway.
1512  BranchInst *Pred1Br = dyn_cast<BranchInst>(Pred1->getTerminator());
1513  BranchInst *Pred2Br = dyn_cast<BranchInst>(Pred2->getTerminator());
1514  if (!Pred1Br || !Pred2Br)
1515  return nullptr;
1516 
1517  // Eliminate code duplication by ensuring that Pred1Br is conditional if
1518  // either are.
1519  if (Pred2Br->isConditional()) {
1520  // If both branches are conditional, we don't have an "if statement". In
1521  // reality, we could transform this case, but since the condition will be
1522  // required anyway, we stand no chance of eliminating it, so the xform is
1523  // probably not profitable.
1524  if (Pred1Br->isConditional())
1525  return nullptr;
1526 
1527  std::swap(Pred1, Pred2);
1528  std::swap(Pred1Br, Pred2Br);
1529  }
1530 
1531  if (Pred1Br->isConditional()) {
1532  // The only thing we have to watch out for here is to make sure that Pred2
1533  // doesn't have incoming edges from other blocks. If it does, the condition
1534  // doesn't dominate BB.
1535  if (!Pred2->getSinglePredecessor())
1536  return nullptr;
1537 
1538  // If we found a conditional branch predecessor, make sure that it branches
1539  // to BB and Pred2Br. If it doesn't, this isn't an "if statement".
1540  if (Pred1Br->getSuccessor(0) == BB &&
1541  Pred1Br->getSuccessor(1) == Pred2) {
1542  IfTrue = Pred1;
1543  IfFalse = Pred2;
1544  } else if (Pred1Br->getSuccessor(0) == Pred2 &&
1545  Pred1Br->getSuccessor(1) == BB) {
1546  IfTrue = Pred2;
1547  IfFalse = Pred1;
1548  } else {
1549  // We know that one arm of the conditional goes to BB, so the other must
1550  // go somewhere unrelated, and this must not be an "if statement".
1551  return nullptr;
1552  }
1553 
1554  return Pred1Br;
1555  }
1556 
1557  // Ok, if we got here, both predecessors end with an unconditional branch to
1558  // BB. Don't panic! If both blocks only have a single (identical)
1559  // predecessor, and THAT is a conditional branch, then we're all ok!
1560  BasicBlock *CommonPred = Pred1->getSinglePredecessor();
1561  if (CommonPred == nullptr || CommonPred != Pred2->getSinglePredecessor())
1562  return nullptr;
1563 
1564  // Otherwise, if this is a conditional branch, then we can use it!
1565  BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator());
1566  if (!BI) return nullptr;
1567 
1568  assert(BI->isConditional() && "Two successors but not conditional?");
1569  if (BI->getSuccessor(0) == Pred1) {
1570  IfTrue = Pred1;
1571  IfFalse = Pred2;
1572  } else {
1573  IfTrue = Pred2;
1574  IfFalse = Pred1;
1575  }
1576  return BI;
1577 }
1578 
1579 // After creating a control flow hub, the operands of PHINodes in an outgoing
1580 // block Out no longer match the predecessors of that block. Predecessors of Out
1581 // that are incoming blocks to the hub are now replaced by just one edge from
1582 // the hub. To match this new control flow, the corresponding values from each
1583 // PHINode must now be moved a new PHINode in the first guard block of the hub.
1584 //
1585 // This operation cannot be performed with SSAUpdater, because it involves one
1586 // new use: If the block Out is in the list of Incoming blocks, then the newly
1587 // created PHI in the Hub will use itself along that edge from Out to Hub.
1588 static void reconnectPhis(BasicBlock *Out, BasicBlock *GuardBlock,
1589  const SetVector<BasicBlock *> &Incoming,
1590  BasicBlock *FirstGuardBlock) {
1591  auto I = Out->begin();
1592  while (I != Out->end() && isa<PHINode>(I)) {
1593  auto Phi = cast<PHINode>(I);
1594  auto NewPhi =
1595  PHINode::Create(Phi->getType(), Incoming.size(),
1596  Phi->getName() + ".moved", &FirstGuardBlock->back());
1597  for (auto In : Incoming) {
1598  Value *V = UndefValue::get(Phi->getType());
1599  if (In == Out) {
1600  V = NewPhi;
1601  } else if (Phi->getBasicBlockIndex(In) != -1) {
1602  V = Phi->removeIncomingValue(In, false);
1603  }
1604  NewPhi->addIncoming(V, In);
1605  }
1606  assert(NewPhi->getNumIncomingValues() == Incoming.size());
1607  if (Phi->getNumOperands() == 0) {
1608  Phi->replaceAllUsesWith(NewPhi);
1609  I = Phi->eraseFromParent();
1610  continue;
1611  }
1612  Phi->addIncoming(NewPhi, GuardBlock);
1613  ++I;
1614  }
1615 }
1616 
1619 
1620 // Redirects the terminator of the incoming block to the first guard
1621 // block in the hub. The condition of the original terminator (if it
1622 // was conditional) and its original successors are returned as a
1623 // tuple <condition, succ0, succ1>. The function additionally filters
1624 // out successors that are not in the set of outgoing blocks.
1625 //
1626 // - condition is non-null iff the branch is conditional.
1627 // - Succ1 is non-null iff the sole/taken target is an outgoing block.
1628 // - Succ2 is non-null iff condition is non-null and the fallthrough
1629 // target is an outgoing block.
1630 static std::tuple<Value *, BasicBlock *, BasicBlock *>
1632  const BBSetVector &Outgoing) {
1633  auto Branch = cast<BranchInst>(BB->getTerminator());
1634  auto Condition = Branch->isConditional() ? Branch->getCondition() : nullptr;
1635 
1636  BasicBlock *Succ0 = Branch->getSuccessor(0);
1637  BasicBlock *Succ1 = nullptr;
1638  Succ0 = Outgoing.count(Succ0) ? Succ0 : nullptr;
1639 
1640  if (Branch->isUnconditional()) {
1641  Branch->setSuccessor(0, FirstGuardBlock);
1642  assert(Succ0);
1643  } else {
1644  Succ1 = Branch->getSuccessor(1);
1645  Succ1 = Outgoing.count(Succ1) ? Succ1 : nullptr;
1646  assert(Succ0 || Succ1);
1647  if (Succ0 && !Succ1) {
1648  Branch->setSuccessor(0, FirstGuardBlock);
1649  } else if (Succ1 && !Succ0) {
1650  Branch->setSuccessor(1, FirstGuardBlock);
1651  } else {
1652  Branch->eraseFromParent();
1653  BranchInst::Create(FirstGuardBlock, BB);
1654  }
1655  }
1656 
1657  assert(Succ0 || Succ1);
1658  return std::make_tuple(Condition, Succ0, Succ1);
1659 }
1660 
1661 // Capture the existing control flow as guard predicates, and redirect
1662 // control flow from every incoming block to the first guard block in
1663 // the hub.
1664 //
1665 // There is one guard predicate for each outgoing block OutBB. The
1666 // predicate is a PHINode with one input for each InBB which
1667 // represents whether the hub should transfer control flow to OutBB if
1668 // it arrived from InBB. These predicates are NOT ORTHOGONAL. The Hub
1669 // evaluates them in the same order as the Outgoing set-vector, and
1670 // control branches to the first outgoing block whose predicate
1671 // evaluates to true.
1673  BasicBlock *FirstGuardBlock, BBPredicates &GuardPredicates,
1674  SmallVectorImpl<WeakVH> &DeletionCandidates, const BBSetVector &Incoming,
1675  const BBSetVector &Outgoing) {
1676  auto &Context = Incoming.front()->getContext();
1677  auto BoolTrue = ConstantInt::getTrue(Context);
1678  auto BoolFalse = ConstantInt::getFalse(Context);
1679 
1680  // The predicate for the last outgoing is trivially true, and so we
1681  // process only the first N-1 successors.
1682  for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) {
1683  auto Out = Outgoing[i];
1684  LLVM_DEBUG(dbgs() << "Creating guard for " << Out->getName() << "\n");
1685  auto Phi =
1687  StringRef("Guard.") + Out->getName(), FirstGuardBlock);
1688  GuardPredicates[Out] = Phi;
1689  }
1690 
1691  for (auto In : Incoming) {
1692  Value *Condition;
1693  BasicBlock *Succ0;
1694  BasicBlock *Succ1;
1695  std::tie(Condition, Succ0, Succ1) =
1696  redirectToHub(In, FirstGuardBlock, Outgoing);
1697 
1698  // Optimization: Consider an incoming block A with both successors
1699  // Succ0 and Succ1 in the set of outgoing blocks. The predicates
1700  // for Succ0 and Succ1 complement each other. If Succ0 is visited
1701  // first in the loop below, control will branch to Succ0 using the
1702  // corresponding predicate. But if that branch is not taken, then
1703  // control must reach Succ1, which means that the predicate for
1704  // Succ1 is always true.
1705  bool OneSuccessorDone = false;
1706  for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) {
1707  auto Out = Outgoing[i];
1708  auto Phi = GuardPredicates[Out];
1709  if (Out != Succ0 && Out != Succ1) {
1710  Phi->addIncoming(BoolFalse, In);
1711  continue;
1712  }
1713  // Optimization: When only one successor is an outgoing block,
1714  // the predicate is always true.
1715  if (!Succ0 || !Succ1 || OneSuccessorDone) {
1716  Phi->addIncoming(BoolTrue, In);
1717  continue;
1718  }
1719  assert(Succ0 && Succ1);
1720  OneSuccessorDone = true;
1721  if (Out == Succ0) {
1722  Phi->addIncoming(Condition, In);
1723  continue;
1724  }
1725  auto Inverted = invertCondition(Condition);
1726  DeletionCandidates.push_back(Condition);
1727  Phi->addIncoming(Inverted, In);
1728  }
1729  }
1730 }
1731 
1732 // For each outgoing block OutBB, create a guard block in the Hub. The
1733 // first guard block was already created outside, and available as the
1734 // first element in the vector of guard blocks.
1735 //
1736 // Each guard block terminates in a conditional branch that transfers
1737 // control to the corresponding outgoing block or the next guard
1738 // block. The last guard block has two outgoing blocks as successors
1739 // since the condition for the final outgoing block is trivially
1740 // true. So we create one less block (including the first guard block)
1741 // than the number of outgoing blocks.
1743  Function *F, const BBSetVector &Outgoing,
1744  BBPredicates &GuardPredicates, StringRef Prefix) {
1745  for (int i = 0, e = Outgoing.size() - 2; i != e; ++i) {
1746  GuardBlocks.push_back(
1747  BasicBlock::Create(F->getContext(), Prefix + ".guard", F));
1748  }
1749  assert(GuardBlocks.size() == GuardPredicates.size());
1750 
1751  // To help keep the loop simple, temporarily append the last
1752  // outgoing block to the list of guard blocks.
1753  GuardBlocks.push_back(Outgoing.back());
1754 
1755  for (int i = 0, e = GuardBlocks.size() - 1; i != e; ++i) {
1756  auto Out = Outgoing[i];
1757  assert(GuardPredicates.count(Out));
1758  BranchInst::Create(Out, GuardBlocks[i + 1], GuardPredicates[Out],
1759  GuardBlocks[i]);
1760  }
1761 
1762  // Remove the last block from the guard list.
1763  GuardBlocks.pop_back();
1764 }
1765 
1767  DomTreeUpdater *DTU, SmallVectorImpl<BasicBlock *> &GuardBlocks,
1768  const BBSetVector &Incoming, const BBSetVector &Outgoing,
1769  const StringRef Prefix) {
1770  auto F = Incoming.front()->getParent();
1771  auto FirstGuardBlock =
1772  BasicBlock::Create(F->getContext(), Prefix + ".guard", F);
1773 
1775  if (DTU) {
1776  for (auto In : Incoming) {
1777  Updates.push_back({DominatorTree::Insert, In, FirstGuardBlock});
1778  for (auto Succ : successors(In)) {
1779  if (Outgoing.count(Succ))
1780  Updates.push_back({DominatorTree::Delete, In, Succ});
1781  }
1782  }
1783  }
1784 
1785  BBPredicates GuardPredicates;
1786  SmallVector<WeakVH, 8> DeletionCandidates;
1787  convertToGuardPredicates(FirstGuardBlock, GuardPredicates, DeletionCandidates,
1788  Incoming, Outgoing);
1789 
1790  GuardBlocks.push_back(FirstGuardBlock);
1791  createGuardBlocks(GuardBlocks, F, Outgoing, GuardPredicates, Prefix);
1792 
1793  // Update the PHINodes in each outgoing block to match the new control flow.
1794  for (int i = 0, e = GuardBlocks.size(); i != e; ++i) {
1795  reconnectPhis(Outgoing[i], GuardBlocks[i], Incoming, FirstGuardBlock);
1796  }
1797  reconnectPhis(Outgoing.back(), GuardBlocks.back(), Incoming, FirstGuardBlock);
1798 
1799  if (DTU) {
1800  int NumGuards = GuardBlocks.size();
1801  assert((int)Outgoing.size() == NumGuards + 1);
1802  for (int i = 0; i != NumGuards - 1; ++i) {
1803  Updates.push_back({DominatorTree::Insert, GuardBlocks[i], Outgoing[i]});
1804  Updates.push_back(
1805  {DominatorTree::Insert, GuardBlocks[i], GuardBlocks[i + 1]});
1806  }
1807  Updates.push_back({DominatorTree::Insert, GuardBlocks[NumGuards - 1],
1808  Outgoing[NumGuards - 1]});
1809  Updates.push_back({DominatorTree::Insert, GuardBlocks[NumGuards - 1],
1810  Outgoing[NumGuards]});
1811  DTU->applyUpdates(Updates);
1812  }
1813 
1814  for (auto I : DeletionCandidates) {
1815  if (I->use_empty())
1816  if (auto Inst = dyn_cast_or_null<Instruction>(I))
1817  Inst->eraseFromParent();
1818  }
1819 
1820  return FirstGuardBlock;
1821 }
i
i
Definition: README.txt:29
llvm::MemoryDependenceResults::removeInstruction
void removeInstruction(Instruction *InstToRemove)
Removes an instruction from the dependence analysis, updating the dependence of instructions that pre...
Definition: MemoryDependenceAnalysis.cpp:1502
llvm::invertCondition
Value * invertCondition(Value *Condition)
Invert the given true/false value, possibly reusing an existing copy.
Definition: Local.cpp:3340
llvm::BasicBlock::end
iterator end()
Definition: BasicBlock.h:299
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::SplitLandingPadPredecessors
void SplitLandingPadPredecessors(BasicBlock *OrigBB, ArrayRef< BasicBlock * > Preds, const char *Suffix, const char *Suffix2, SmallVectorImpl< BasicBlock * > &NewBBs, DominatorTree *DT, 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...
Definition: BasicBlockUtils.cpp:1296
redirectToHub
static std::tuple< Value *, BasicBlock *, BasicBlock * > redirectToHub(BasicBlock *BB, BasicBlock *FirstGuardBlock, const BBSetVector &Outgoing)
Definition: BasicBlockUtils.cpp:1631
llvm::Type::getInt1Ty
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:236
llvm::MemorySSA::verifyMemorySSA
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1906
llvm::DomTreeUpdater::deleteBB
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
Definition: DomTreeUpdater.cpp:178
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:3004
llvm::SmallPtrSetImpl::erase
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
Definition: SmallPtrSet.h:379
llvm::User::operands
op_range operands()
Definition: User.h:242
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
IntrinsicInst.h
DebugInfoMetadata.h
llvm::cl::Prefix
@ Prefix
Definition: CommandLine.h:160
llvm::DomTreeUpdater::applyUpdates
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Definition: DomTreeUpdater.cpp:231
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
MemorySSAUpdater.h
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:138
createGuardBlocks
static void createGuardBlocks(SmallVectorImpl< BasicBlock * > &GuardBlocks, Function *F, const BBSetVector &Outgoing, BBPredicates &GuardPredicates, StringRef Prefix)
Definition: BasicBlockUtils.cpp:1742
llvm::SetVector::size
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
llvm::BitCastInst
This class represents a no-op cast from one type to another.
Definition: Instructions.h:5212
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::pred_size
unsigned pred_size(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:32
llvm::LandingPadInst
The landingpad instruction holds all of the information necessary to generate correct exception handl...
Definition: Instructions.h:2903
llvm::Value::hasName
bool hasName() const
Definition: Value.h:261
llvm::SmallDenseSet
Implements a dense probed hash-table based set with some number of buckets stored inline.
Definition: DenseSet.h:286
llvm::Loop::getStartLoc
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
Definition: LoopInfo.cpp:630
DomTreeUpdater.h
llvm::DominatorTreeBase::setNewRoot
DomTreeNodeBase< NodeT > * setNewRoot(NodeT *BB)
Add a new node to the forward dominator tree and make it a new root.
Definition: GenericDomTree.h:632
llvm::PHINode::removeIncomingValue
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
Definition: Instructions.cpp:113
llvm::DeleteDeadBlocks
void DeleteDeadBlocks(ArrayRef< BasicBlock * > BBs, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified blocks from BB.
Definition: BasicBlockUtils.cpp:99
llvm::MemoryDependenceResults::invalidateCachedPredecessors
void invalidateCachedPredecessors()
Clears the PredIteratorCache info.
Definition: MemoryDependenceAnalysis.cpp:1498
Local.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
llvm::detachDeadBlocks
void detachDeadBlocks(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< DominatorTree::UpdateType > *Updates, bool KeepOneInputPHIs=false)
Replace contents of every block in BBs with single unreachable instruction.
Definition: BasicBlockUtils.cpp:60
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
llvm::LoopInfoBase::removeBlock
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:1051
llvm::createPHIsForSplitLoopExit
void createPHIsForSplitLoopExit(ArrayRef< BasicBlock * > Preds, BasicBlock *SplitBB, BasicBlock *DestBB)
When a loop exit edge is split, LCSSA form may require new PHIs in the new exit block.
Definition: BasicBlockUtils.cpp:735
llvm::SplitCriticalEdge
BasicBlock * SplitCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")
If this edge is a critical edge, insert a new node to split the critical edge.
Definition: BreakCriticalEdges.cpp:101
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:380
llvm::DominatorTreeBase< BasicBlock, false >::Insert
static constexpr UpdateKind Insert
Definition: GenericDomTree.h:242
llvm::FoldReturnIntoUncondBranch
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...
Definition: BasicBlockUtils.cpp:1319
llvm::MemorySSAUpdater::moveAllAfterSpliceBlocks
void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was spliced into From and To.
Definition: MemorySSAUpdater.cpp:1247
llvm::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:351
llvm::BasicBlock::splitBasicBlock
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)
Split the basic block into two basic blocks at the specified instruction.
Definition: BasicBlock.cpp:378
SplitBlockAndInsertIfThenImpl
static Instruction * SplitBlockAndInsertIfThenImpl(Value *Cond, Instruction *SplitBefore, bool Unreachable, MDNode *BranchWeights, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, BasicBlock *ThenBlock)
Definition: BasicBlockUtils.cpp:1378
llvm::DenseMapBase::count
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:147
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
llvm::isCriticalEdge
bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
Definition: CFG.cpp:95
llvm::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:261
llvm::DIExpression
DWARF expression.
Definition: DebugInfoMetadata.h:2558
MemoryDependenceAnalysis.h
SplitBlockPredecessorsImpl
static BasicBlock * SplitBlockPredecessorsImpl(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Definition: BasicBlockUtils.cpp:1085
llvm::detail::DenseSetImpl< ValueT, SmallDenseMap< ValueT, detail::DenseSetEmpty, 4, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::Instruction::isExceptionalTerminator
bool isExceptionalTerminator() const
Definition: Instruction.h:167
llvm::MemorySSAUpdater::applyUpdates
void applyUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT, bool UpdateDTFirst=false)
Apply CFG updates, analogous with the DT edge updates.
Definition: MemorySSAUpdater.cpp:809
llvm::ArrayRef::empty
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:159
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BranchInst::setSuccessor
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Definition: Instructions.h:3184
llvm::Instruction::setMetadata
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1366
llvm::RecursivelyDeleteDeadPHINode
bool RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=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:627
llvm::BasicBlock::getUniqueSuccessor
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
Definition: BasicBlock.cpp:299
llvm::DomTreeUpdater::UpdateStrategy::Lazy
@ Lazy
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Instruction.h
CommandLine.h
llvm::LoopBase::getParentLoop
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:113
llvm::Instruction::getNumSuccessors
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Definition: Instruction.cpp:777
llvm::DominatorTreeBase::getRootNode
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
Definition: GenericDomTree.h:370
llvm::CallingConv::Tail
@ Tail
Tail - This calling convention attemps to make calls as fast as possible while guaranteeing that tail...
Definition: CallingConv.h:81
Constants.h
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2747
llvm::DbgValueInst
This represents the llvm.dbg.value instruction.
Definition: IntrinsicInst.h:348
llvm::CreateControlFlowHub
BasicBlock * CreateControlFlowHub(DomTreeUpdater *DTU, SmallVectorImpl< BasicBlock * > &GuardBlocks, const SetVector< BasicBlock * > &Predecessors, const SetVector< BasicBlock * > &Successors, const StringRef Prefix)
Given a set of incoming and outgoing blocks, create a "hub" such that every edge from an incoming blo...
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::CleanupReturnInst::Create
static CleanupReturnInst * Create(Value *CleanupPad, BasicBlock *UnwindBB=nullptr, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:4638
Twine.h
InstrTypes.h
llvm::SplitKnownCriticalEdge
BasicBlock * SplitKnownCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")
If it is known that an edge is critical, SplitKnownCriticalEdge can be called directly,...
Definition: BreakCriticalEdges.cpp:111
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:297
UpdatePHINodes
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.
Definition: BasicBlockUtils.cpp:1012
llvm::BasicBlock::isLandingPad
bool isLandingPad() const
Return true if this basic block is a landing pad.
Definition: BasicBlock.cpp:469
llvm::DomTreeUpdater::recalculate
void recalculate(Function &F)
Notify DTU that the entry block was replaced.
Definition: DomTreeUpdater.cpp:121
llvm::ReplaceInstWithInst
void ReplaceInstWithInst(BasicBlock::InstListType &BIL, BasicBlock::iterator &BI, Instruction *I)
Replace the instruction specified by BI with the instruction specified by I.
Definition: BasicBlockUtils.cpp:477
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:486
llvm::CriticalEdgeSplittingOptions
Option class for critical edge splitting.
Definition: BasicBlockUtils.h:142
llvm::BasicBlock::getFirstInsertionPt
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:246
llvm::succ_size
unsigned succ_size(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:31
llvm::MemorySSAUpdater::moveToPlace
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
Definition: MemorySSAUpdater.cpp:1200
llvm::depth_first_ext
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
Definition: DepthFirstIterator.h:252
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2836
llvm::Type::isTokenTy
bool isTokenTy() const
Return true if this is 'token'.
Definition: Type.h:188
llvm::Instruction
Definition: Instruction.h:42
convertToGuardPredicates
static void convertToGuardPredicates(BasicBlock *FirstGuardBlock, BBPredicates &GuardPredicates, SmallVectorImpl< WeakVH > &DeletionCandidates, const BBSetVector &Incoming, const BBSetVector &Outgoing)
Definition: BasicBlockUtils.cpp:1672
Options
const char LLVMTargetMachineRef LLVMPassBuilderOptionsRef Options
Definition: PassBuilderBindings.cpp:48
llvm::BasicBlock::phis
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:355
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:372
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1777
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
llvm::AArch64CC::PL
@ PL
Definition: AArch64BaseInfo.h:260
SmallPtrSet.h
llvm::SplitBlockPredecessors
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, 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...
Definition: BasicBlockUtils.cpp:1176
llvm::DominatorTreeBase::changeImmediateDominator
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
Definition: GenericDomTree.h:655
llvm::BasicBlock::getFirstNonPHI
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:209
llvm::RemoveRedundantDbgInstrs
bool RemoveRedundantDbgInstrs(BasicBlock *BB)
Try to remove redundant dbg.value instructions from given basic block.
Definition: BasicBlockUtils.cpp:441
llvm::ehAwareSplitEdge
BasicBlock * ehAwareSplitEdge(BasicBlock *BB, BasicBlock *Succ, LandingPadInst *OriginalPad=nullptr, PHINode *LandingPadReplacement=nullptr, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")
Split the edge connect the specficed blocks in the case that Succ is an Exception Handling Block.
Definition: BasicBlockUtils.cpp:587
removeRedundantDbgInstrsUsingForwardScan
static bool removeRedundantDbgInstrsUsingForwardScan(BasicBlock *BB)
Remove redundant dbg.value instructions using a forward scan.
Definition: BasicBlockUtils.cpp:412
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2743
llvm::EliminateUnreachableBlocks
bool EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete all basic blocks from F that are not reachable from its entry node.
Definition: BasicBlockUtils.cpp:123
llvm::DomTreeUpdater::hasDomTree
bool hasDomTree() const
Returns true if it holds a DominatorTree.
Definition: DomTreeUpdater.h:57
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:344
Type.h
llvm::Instruction::getMetadata
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:279
CFG.h
LoopInfo.h
llvm::Twine::str
std::string str() const
Return the twine contents as a std::string.
Definition: Twine.cpp:17
llvm::GetIfCondition
BranchInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
Definition: BasicBlockUtils.cpp:1487
llvm::BasicBlock::isEntryBlock
bool isEntryBlock() const
Return true if this is the entry block of the containing function.
Definition: BasicBlock.cpp:372
llvm::tgtok::In
@ In
Definition: TGLexer.h:51
BasicBlock.h
llvm::cl::opt
Definition: CommandLine.h:1392
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:77
llvm::DomTreeNodeBase::getBlock
NodeT * getBlock() const
Definition: GenericDomTree.h:88
removeRedundantDbgInstrsUsingBackwardScan
static bool removeRedundantDbgInstrsUsingBackwardScan(BasicBlock *BB)
Remove redundant instructions within sequences of consecutive dbg.value instructions.
Definition: BasicBlockUtils.cpp:365
llvm::LoopBase::moveToHeader
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:459
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:54
llvm::NoneType
NoneType
A simple null object to allow implicit construction of Optional<T> and similar types without having t...
Definition: None.h:23
llvm::MemorySSAUpdater::getMemorySSA
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
Definition: MemorySSAUpdater.h:242
MaxDeoptOrUnreachableSuccessorCheckDepth
static cl::opt< unsigned > MaxDeoptOrUnreachableSuccessorCheckDepth("max-deopt-or-unreachable-succ-check-depth", cl::init(8), cl::Hidden, cl::desc("Set the maximum path length when checking whether a basic block " "is followed by a block that either has a terminating " "deoptimizing call or is terminated with an unreachable"))
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2801
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DomTreeUpdater::getDomTree
DominatorTree & getDomTree()
Flush DomTree updates and return DomTree.
Definition: DomTreeUpdater.cpp:304
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3142
llvm::DenseMap
Definition: DenseMap.h:716
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:986
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::MemorySSA::getMemoryAccess
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:731
llvm::succ_begin
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:99
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
llvm::DebugVariable
Identifies a unique instance of a variable.
Definition: DebugInfoMetadata.h:3620
llvm::SmallPtrSetImpl::begin
iterator begin() const
Definition: SmallPtrSet.h:403
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1682
llvm::updatePhiNodes
void updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred, BasicBlock *NewPred, PHINode *Until=nullptr)
Replaces all uses of OldPred with the NewPred block in all PHINodes in a block.
Definition: BasicBlockUtils.cpp:565
ArrayRef.h
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:364
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:215
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:152
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
llvm::LoopBase::getLoopDepth
unsigned getLoopDepth() const
Return the nesting level of this loop.
Definition: LoopInfo.h:96
llvm::RegState::Dead
@ Dead
Unused definition.
Definition: MachineInstrBuilder.h:50
SplitBlockImpl
static BasicBlock * SplitBlockImpl(BasicBlock *Old, Instruction *SplitPt, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, const Twine &BBName, bool Before)
Definition: BasicBlockUtils.cpp:781
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:335
llvm::MDNode
Metadata node.
Definition: Metadata.h:937
llvm::SplitBlockAndInsertIfThenElse
void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, Instruction **ThenTerm, Instruction **ElseTerm, MDNode *BranchWeights=nullptr)
SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, but also creates the ElseBlock...
Definition: BasicBlockUtils.cpp:1467
llvm::SmallPtrSetImpl< NodeRef >::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
llvm::BranchInst::isUnconditional
bool isUnconditional() const
Definition: Instructions.h:3164
llvm::User::setOperand
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
llvm::detail::DenseSetImpl< ValueT, SmallDenseMap< ValueT, detail::DenseSetEmpty, 4, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::clear
void clear()
Definition: DenseSet.h:92
llvm::df_iterator_default_set
Definition: DepthFirstIterator.h:70
llvm::GetSuccessorNumber
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:79
CFG.h
llvm::Instruction::clone
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
Definition: Instruction.cpp:862
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:95
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::LoopInfo
Definition: LoopInfo.h:1102
llvm::MergeBlockIntoPredecessor
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false)
Attempts to merge a block into its predecessor, if possible.
Definition: BasicBlockUtils.cpp:178
llvm::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1624
llvm::SymbolTableList< Instruction >
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::BasicBlock::getUniquePredecessor
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:269
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:529
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:97
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
llvm::MemorySSA::End
@ End
Definition: MemorySSA.h:802
llvm::CleanupPadInst::Create
static CleanupPadInst * Create(Value *ParentPad, ArrayRef< Value * > Args=None, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:4460
llvm::PredIterator
Definition: CFG.h:42
llvm::DomTreeUpdater::flush
void flush()
Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.
Definition: DomTreeUpdater.cpp:73
llvm::DomTreeNodeBase< BasicBlock >
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:305
ValueHandle.h
llvm::DominatorTreeBase::addNewBlock
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
Definition: GenericDomTree.h:619
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:883
llvm::BasicBlock::front
const Instruction & front() const
Definition: BasicBlock.h:309
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:35
llvm::ReplaceInstWithValue
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...
Definition: BasicBlockUtils.cpp:463
llvm::MemoryDependenceResults
Provides a lazy, caching interface for making common memory aliasing information queries,...
Definition: MemoryDependenceAnalysis.h:265
llvm::LoopInfoBase::isLoopHeader
bool isLoopHeader(const BlockT *BB) const
Definition: LoopInfo.h:999
llvm::SplitEdge
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
Definition: BasicBlockUtils.cpp:516
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:83
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:876
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:50
llvm::setUnwindEdgeTo
void setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ)
Sets the unwind edge of an instruction to a particular successor.
Definition: BasicBlockUtils.cpp:554
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:84
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:345
llvm::PHINode::Create
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...
Definition: Instructions.h:2693
llvm::ArrayRef::begin
iterator begin() const
Definition: ArrayRef.h:152
llvm::MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor
void wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New, ArrayRef< BasicBlock * > Preds, bool IdenticalEdgesWereMerged=true)
A new empty BasicBlock (New) now branches directly to Old.
Definition: MemorySSAUpdater.cpp:1268
llvm::MemorySSAUpdater::moveAllAfterMergeBlocks
void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was merged into To.
Definition: MemorySSAUpdater.cpp:1258
UpdateAnalysisInformation
static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB, ArrayRef< BasicBlock * > Preds, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA, bool &HasLoopExit)
Update DominatorTree, LoopInfo, and LCCSA analysis information.
Definition: BasicBlockUtils.cpp:898
llvm::pred_end
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
llvm::ExtractValueInst
This instruction extracts a struct member or array element value from an aggregate value.
Definition: Instructions.h:2398
llvm::MCID::Branch
@ Branch
Definition: MCInstrDesc.h:158
llvm::DominatorTreeBase::splitBlock
void splitBlock(NodeT *NewBB)
splitBlock - BB is split and now it has one successor.
Definition: GenericDomTree.h:700
llvm::CriticalEdgeSplittingOptions::setPreserveLCSSA
CriticalEdgeSplittingOptions & setPreserveLCSSA()
Definition: BasicBlockUtils.h:172
Casting.h
Function.h
llvm::DenseMapBase::size
unsigned size() const
Definition: DenseMap.h:101
llvm::SetVector::count
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:215
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:222
llvm::SetVector::front
const T & front() const
Return the first element of the SetVector.
Definition: SetVector.h:122
llvm::Instruction::isEHPad
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:662
llvm::MemoryUseOrDef
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:252
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
llvm::splitBlockBefore
BasicBlock * splitBlockBefore(BasicBlock *Old, Instruction *SplitPt, DomTreeUpdater *DTU, LoopInfo *LI, MemorySSAUpdater *MSSAU, const Twine &BBName="")
Split the specified block at the specified instruction SplitPt.
Definition: BasicBlockUtils.cpp:852
llvm::FoldSingleEntryPHINodes
bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
Definition: BasicBlockUtils.cpp:143
llvm::DeleteDeadPHIs
bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Examine each PHI in the given block and delete it if it is dead.
Definition: BasicBlockUtils.cpp:162
llvm::BasicBlock::back
const Instruction & back() const
Definition: BasicBlock.h:311
llvm::pred_begin
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:109
llvm::SplitAllCriticalEdges
unsigned SplitAllCriticalEdges(Function &F, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
Loop over all of the edges in the CFG, breaking critical edges as they are found.
Definition: BasicBlockUtils.cpp:767
llvm::BasicBlock::getInstList
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:364
Instructions.h
llvm::IsBlockFollowedByDeoptOrUnreachable
bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB)
Check if we can prove that all paths starting from this block converge to a block that either has a @...
Definition: BasicBlockUtils.cpp:497
SmallVector.h
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:367
llvm::MergeBlockSuccessorsIntoGivenBlocks
bool MergeBlockSuccessorsIntoGivenBlocks(SmallPtrSetImpl< BasicBlock * > &MergeBlocks, Loop *L=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr)
Merge block(s) sucessors, if possible.
Definition: BasicBlockUtils.cpp:319
User.h
llvm::LoopBase::addBasicBlockToLoop
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Definition: LoopInfoImpl.h:241
Dominators.h
llvm::SmallPtrSetImplBase::empty
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:92
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2767
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:164
llvm::PHINode
Definition: Instructions.h:2651
llvm::BasicBlock::getTerminator
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.h:119
llvm::SmallVectorImpl< DominatorTree::UpdateType >
llvm::BasicBlock::getLandingPadInst
const LandingPadInst * getLandingPadInst() const
Return the landingpad instruction associated with the landing pad.
Definition: BasicBlock.cpp:473
llvm::DeleteDeadBlock
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
Definition: BasicBlockUtils.cpp:94
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
llvm::SetVector::back
const T & back() const
Return the last element of the SetVector.
Definition: SetVector.h:128
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::UnreachableInst
This function has undefined behavior.
Definition: Instructions.h:4727
llvm::VerifyMemorySSA
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:91
LLVMContext.h
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::Value::takeName
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:378
llvm::SplitBlockAndInsertIfThen
Instruction * SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore, bool Unreachable, MDNode *BranchWeights, DominatorTree *DT, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
Definition: BasicBlockUtils.cpp:1446
llvm::cl::desc
Definition: CommandLine.h:405
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3086
raw_ostream.h
llvm::SetVector
A vector that has set insertion semantics.
Definition: SetVector.h:40
llvm::SmallPtrSetImpl::contains
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:389
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:644
BasicBlockUtils.h
llvm::SplitBlock
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
Definition: BasicBlockUtils.cpp:837
Value.h
SplitLandingPadPredecessorsImpl
static void SplitLandingPadPredecessorsImpl(BasicBlock *OrigBB, ArrayRef< BasicBlock * > Preds, const char *Suffix1, const char *Suffix2, SmallVectorImpl< BasicBlock * > &NewBBs, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Definition: BasicBlockUtils.cpp:1194
llvm::BasicBlock::isEHPad
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:466
llvm::MCID::Terminator
@ Terminator
Definition: MCInstrDesc.h:157
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
reconnectPhis
static void reconnectPhis(BasicBlock *Out, BasicBlock *GuardBlock, const SetVector< BasicBlock * > &Incoming, BasicBlock *FirstGuardBlock)
Definition: BasicBlockUtils.cpp:1588
llvm::ArrayRef::end
iterator end() const
Definition: ArrayRef.h:153
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3165
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3179
llvm::DominatorTreeBase< BasicBlock, false >::Delete
static constexpr UpdateKind Delete
Definition: GenericDomTree.h:243
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::SmallPtrSetImpl::insert
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:365