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