LLVM  16.0.0git
BasicBlockUtils.cpp
Go to the documentation of this file.
1 //===- BasicBlockUtils.cpp - BasicBlock Utilities --------------------------==//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This family of functions perform manipulations on basic blocks, and
10 // instructions contained within basic blocks.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/ArrayRef.h"
16 #include "llvm/ADT/SmallPtrSet.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/Twine.h"
19 #include "llvm/Analysis/CFG.h"
21 #include "llvm/Analysis/LoopInfo.h"
24 #include "llvm/IR/BasicBlock.h"
25 #include "llvm/IR/CFG.h"
26 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/Dominators.h"
29 #include "llvm/IR/Function.h"
30 #include "llvm/IR/InstrTypes.h"
31 #include "llvm/IR/Instruction.h"
32 #include "llvm/IR/Instructions.h"
33 #include "llvm/IR/IntrinsicInst.h"
34 #include "llvm/IR/LLVMContext.h"
35 #include "llvm/IR/Type.h"
36 #include "llvm/IR/User.h"
37 #include "llvm/IR/Value.h"
38 #include "llvm/IR/ValueHandle.h"
39 #include "llvm/Support/Casting.h"
41 #include "llvm/Support/Debug.h"
44 #include <cassert>
45 #include <cstdint>
46 #include <string>
47 #include <utility>
48 #include <vector>
49 
50 using namespace llvm;
51 
52 #define DEBUG_TYPE "basicblock-utils"
53 
55  "max-deopt-or-unreachable-succ-check-depth", cl::init(8), cl::Hidden,
56  cl::desc("Set the maximum path length when checking whether a basic block "
57  "is followed by a block that either has a terminating "
58  "deoptimizing call or is terminated with an unreachable"));
59 
63  bool KeepOneInputPHIs) {
64  for (auto *BB : BBs) {
65  // Loop through all of our successors and make sure they know that one
66  // of their predecessors is going away.
67  SmallPtrSet<BasicBlock *, 4> UniqueSuccessors;
68  for (BasicBlock *Succ : successors(BB)) {
69  Succ->removePredecessor(BB, KeepOneInputPHIs);
70  if (Updates && UniqueSuccessors.insert(Succ).second)
71  Updates->push_back({DominatorTree::Delete, BB, Succ});
72  }
73 
74  // Zap all the instructions in the block.
75  while (!BB->empty()) {
76  Instruction &I = BB->back();
77  // If this instruction is used, replace uses with an arbitrary value.
78  // Because control flow can't get here, we don't care what we replace the
79  // value with. Note that since this block is unreachable, and all values
80  // contained within it must dominate their uses, that all uses will
81  // eventually be removed (they are themselves dead).
82  if (!I.use_empty())
83  I.replaceAllUsesWith(PoisonValue::get(I.getType()));
84  BB->getInstList().pop_back();
85  }
86  new UnreachableInst(BB->getContext(), BB);
87  assert(BB->getInstList().size() == 1 &&
88  isa<UnreachableInst>(BB->getTerminator()) &&
89  "The successor list of BB isn't empty before "
90  "applying corresponding DTU updates.");
91  }
92 }
93 
95  bool KeepOneInputPHIs) {
96  DeleteDeadBlocks({BB}, DTU, KeepOneInputPHIs);
97 }
98 
100  bool KeepOneInputPHIs) {
101 #ifndef NDEBUG
102  // Make sure that all predecessors of each dead block is also dead.
104  assert(Dead.size() == BBs.size() && "Duplicating blocks?");
105  for (auto *BB : Dead)
106  for (BasicBlock *Pred : predecessors(BB))
107  assert(Dead.count(Pred) && "All predecessors must be dead!");
108 #endif
109 
111  detachDeadBlocks(BBs, DTU ? &Updates : nullptr, KeepOneInputPHIs);
112 
113  if (DTU)
114  DTU->applyUpdates(Updates);
115 
116  for (BasicBlock *BB : BBs)
117  if (DTU)
118  DTU->deleteBB(BB);
119  else
120  BB->eraseFromParent();
121 }
122 
124  bool KeepOneInputPHIs) {
126 
127  // Mark all reachable blocks.
128  for (BasicBlock *BB : depth_first_ext(&F, Reachable))
129  (void)BB/* Mark all reachable blocks */;
130 
131  // Collect all dead blocks.
132  std::vector<BasicBlock*> DeadBlocks;
133  for (BasicBlock &BB : F)
134  if (!Reachable.count(&BB))
135  DeadBlocks.push_back(&BB);
136 
137  // Delete the dead blocks.
138  DeleteDeadBlocks(DeadBlocks, DTU, KeepOneInputPHIs);
139 
140  return !DeadBlocks.empty();
141 }
142 
144  MemoryDependenceResults *MemDep) {
145  if (!isa<PHINode>(BB->begin()))
146  return false;
147 
148  while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
149  if (PN->getIncomingValue(0) != PN)
150  PN->replaceAllUsesWith(PN->getIncomingValue(0));
151  else
152  PN->replaceAllUsesWith(PoisonValue::get(PN->getType()));
153 
154  if (MemDep)
155  MemDep->removeInstruction(PN); // Memdep updates AA itself.
156 
157  PN->eraseFromParent();
158  }
159  return true;
160 }
161 
163  MemorySSAUpdater *MSSAU) {
164  // Recursively deleting a PHI may cause multiple PHIs to be deleted
165  // or RAUW'd undef, so use an array of WeakTrackingVH for the PHIs to delete.
167  for (PHINode &PN : BB->phis())
168  PHIs.push_back(&PN);
169 
170  bool Changed = false;
171  for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
172  if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i].operator Value*()))
173  Changed |= RecursivelyDeleteDeadPHINode(PN, TLI, MSSAU);
174 
175  return Changed;
176 }
177 
179  LoopInfo *LI, MemorySSAUpdater *MSSAU,
180  MemoryDependenceResults *MemDep,
181  bool PredecessorWithTwoSuccessors) {
182  if (BB->hasAddressTaken())
183  return false;
184 
185  // Can't merge if there are multiple predecessors, or no predecessors.
186  BasicBlock *PredBB = BB->getUniquePredecessor();
187  if (!PredBB) return false;
188 
189  // Don't break self-loops.
190  if (PredBB == BB) return false;
191 
192  // Don't break unwinding instructions or terminators with other side-effects.
193  Instruction *PTI = PredBB->getTerminator();
194  if (PTI->isExceptionalTerminator() || PTI->mayHaveSideEffects())
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>(PTI)))
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 *STI = BB->getTerminator();
262  Instruction *Start = &*BB->begin();
263  // If there's nothing to move, mark the starting instruction as the last
264  // instruction in the block. Terminator instruction is handled separately.
265  if (Start == STI)
266  Start = PTI;
267 
268  // Move all definitions in the successor to the predecessor...
269  PredBB->getInstList().splice(PTI->getIterator(), BB->getInstList(),
270  BB->begin(), STI->getIterator());
271 
272  if (MSSAU)
273  MSSAU->moveAllAfterMergeBlocks(BB, PredBB, Start);
274 
275  // Make all PHI nodes that referred to BB now refer to Pred as their
276  // source...
277  BB->replaceAllUsesWith(PredBB);
278 
279  if (PredecessorWithTwoSuccessors) {
280  // Delete the unconditional branch from BB.
281  BB->getInstList().pop_back();
282 
283  // Update branch in the predecessor.
284  PredBB_BI->setSuccessor(FallThruPath, NewSucc);
285  } else {
286  // Delete the unconditional branch from the predecessor.
287  PredBB->getInstList().pop_back();
288 
289  // Move terminator instruction.
290  PredBB->getInstList().splice(PredBB->end(), BB->getInstList());
291 
292  // Terminator may be a memory accessing instruction too.
293  if (MSSAU)
294  if (MemoryUseOrDef *MUD = cast_or_null<MemoryUseOrDef>(
295  MSSAU->getMemorySSA()->getMemoryAccess(PredBB->getTerminator())))
296  MSSAU->moveToPlace(MUD, PredBB, MemorySSA::End);
297  }
298  // Add unreachable to now empty BB.
299  new UnreachableInst(BB->getContext(), BB);
300 
301  // Inherit predecessors name if it exists.
302  if (!PredBB->hasName())
303  PredBB->takeName(BB);
304 
305  if (LI)
306  LI->removeBlock(BB);
307 
308  if (MemDep)
310 
311  if (DTU)
312  DTU->applyUpdates(Updates);
313 
314  // Finally, erase the old block and update dominator info.
315  DeleteDeadBlock(BB, DTU);
316 
317  return true;
318 }
319 
321  SmallPtrSetImpl<BasicBlock *> &MergeBlocks, Loop *L, DomTreeUpdater *DTU,
322  LoopInfo *LI) {
323  assert(!MergeBlocks.empty() && "MergeBlocks should not be empty");
324 
325  bool BlocksHaveBeenMerged = false;
326  while (!MergeBlocks.empty()) {
327  BasicBlock *BB = *MergeBlocks.begin();
328  BasicBlock *Dest = BB->getSingleSuccessor();
329  if (Dest && (!L || L->contains(Dest))) {
330  BasicBlock *Fold = Dest->getUniquePredecessor();
331  (void)Fold;
332  if (MergeBlockIntoPredecessor(Dest, DTU, LI)) {
333  assert(Fold == BB &&
334  "Expecting BB to be unique predecessor of the Dest block");
335  MergeBlocks.erase(Dest);
336  BlocksHaveBeenMerged = true;
337  } else
338  MergeBlocks.erase(BB);
339  } else
340  MergeBlocks.erase(BB);
341  }
342  return BlocksHaveBeenMerged;
343 }
344 
345 /// Remove redundant instructions within sequences of consecutive dbg.value
346 /// instructions. This is done using a backward scan to keep the last dbg.value
347 /// describing a specific variable/fragment.
348 ///
349 /// BackwardScan strategy:
350 /// ----------------------
351 /// Given a sequence of consecutive DbgValueInst like this
352 ///
353 /// dbg.value ..., "x", FragmentX1 (*)
354 /// dbg.value ..., "y", FragmentY1
355 /// dbg.value ..., "x", FragmentX2
356 /// dbg.value ..., "x", FragmentX1 (**)
357 ///
358 /// then the instruction marked with (*) can be removed (it is guaranteed to be
359 /// obsoleted by the instruction marked with (**) as the latter instruction is
360 /// describing the same variable using the same fragment info).
361 ///
362 /// Possible improvements:
363 /// - Check fully overlapping fragments and not only identical fragments.
364 /// - Support dbg.addr, dbg.declare. dbg.label, and possibly other meta
365 /// instructions being part of the sequence of consecutive instructions.
367  SmallVector<DbgValueInst *, 8> ToBeRemoved;
368  SmallDenseSet<DebugVariable> VariableSet;
369  for (auto &I : reverse(*BB)) {
370  if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(&I)) {
371  DebugVariable Key(DVI->getVariable(),
372  DVI->getExpression(),
373  DVI->getDebugLoc()->getInlinedAt());
374  auto R = VariableSet.insert(Key);
375  // If the same variable fragment is described more than once it is enough
376  // to keep the last one (i.e. the first found since we for reverse
377  // iteration).
378  if (!R.second)
379  ToBeRemoved.push_back(DVI);
380  continue;
381  }
382  // Sequence with consecutive dbg.value instrs ended. Clear the map to
383  // restart identifying redundant instructions if case we find another
384  // dbg.value sequence.
385  VariableSet.clear();
386  }
387 
388  for (auto &Instr : ToBeRemoved)
389  Instr->eraseFromParent();
390 
391  return !ToBeRemoved.empty();
392 }
393 
394 /// Remove redundant dbg.value instructions using a forward scan. This can
395 /// remove a dbg.value instruction that is redundant due to indicating that a
396 /// variable has the same value as already being indicated by an earlier
397 /// dbg.value.
398 ///
399 /// ForwardScan strategy:
400 /// ---------------------
401 /// Given two identical dbg.value instructions, separated by a block of
402 /// instructions that isn't describing the same variable, like this
403 ///
404 /// dbg.value X1, "x", FragmentX1 (**)
405 /// <block of instructions, none being "dbg.value ..., "x", ...">
406 /// dbg.value X1, "x", FragmentX1 (*)
407 ///
408 /// then the instruction marked with (*) can be removed. Variable "x" is already
409 /// described as being mapped to the SSA value X1.
410 ///
411 /// Possible improvements:
412 /// - Keep track of non-overlapping fragments.
414  SmallVector<DbgValueInst *, 8> ToBeRemoved;
416  VariableMap;
417  for (auto &I : *BB) {
418  if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(&I)) {
419  DebugVariable Key(DVI->getVariable(),
420  NoneType(),
421  DVI->getDebugLoc()->getInlinedAt());
422  auto VMI = VariableMap.find(Key);
423  // Update the map if we found a new value/expression describing the
424  // variable, or if the variable wasn't mapped already.
425  SmallVector<Value *, 4> Values(DVI->getValues());
426  if (VMI == VariableMap.end() || VMI->second.first != Values ||
427  VMI->second.second != DVI->getExpression()) {
428  VariableMap[Key] = {Values, DVI->getExpression()};
429  continue;
430  }
431  // Found an identical mapping. Remember the instruction for later removal.
432  ToBeRemoved.push_back(DVI);
433  }
434  }
435 
436  for (auto &Instr : ToBeRemoved)
437  Instr->eraseFromParent();
438 
439  return !ToBeRemoved.empty();
440 }
441 
443  bool MadeChanges = false;
444  // By using the "backward scan" strategy before the "forward scan" strategy we
445  // can remove both dbg.value (2) and (3) in a situation like this:
446  //
447  // (1) dbg.value V1, "x", DIExpression()
448  // ...
449  // (2) dbg.value V2, "x", DIExpression()
450  // (3) dbg.value V1, "x", DIExpression()
451  //
452  // The backward scan will remove (2), it is made obsolete by (3). After
453  // getting (2) out of the way, the foward scan will remove (3) since "x"
454  // already is described as having the value V1 at (1).
457 
458  if (MadeChanges)
459  LLVM_DEBUG(dbgs() << "Removed redundant dbg instrs from: "
460  << BB->getName() << "\n");
461  return MadeChanges;
462 }
463 
465  BasicBlock::iterator &BI, Value *V) {
466  Instruction &I = *BI;
467  // Replaces all of the uses of the instruction with uses of the value
468  I.replaceAllUsesWith(V);
469 
470  // Make sure to propagate a name if there is one already.
471  if (I.hasName() && !V->hasName())
472  V->takeName(&I);
473 
474  // Delete the unnecessary instruction now...
475  BI = BIL.erase(BI);
476 }
477 
480  assert(I->getParent() == nullptr &&
481  "ReplaceInstWithInst: Instruction already inserted into basic block!");
482 
483  // Copy debug location to newly added instruction, if it wasn't already set
484  // by the caller.
485  if (!I->getDebugLoc())
486  I->setDebugLoc(BI->getDebugLoc());
487 
488  // Insert the new instruction into the basic block...
489  BasicBlock::iterator New = BIL.insert(BI, I);
490 
491  // Replace all uses of the old instruction, and delete it.
492  ReplaceInstWithValue(BIL, BI, I);
493 
494  // Move BI back to point to the newly inserted instruction
495  BI = New;
496 }
497 
499  // Remember visited blocks to avoid infinite loop
501  unsigned Depth = 0;
503  VisitedBlocks.insert(BB).second) {
504  if (BB->getTerminatingDeoptimizeCall() ||
505  isa<UnreachableInst>(BB->getTerminator()))
506  return true;
507  BB = BB->getUniqueSuccessor();
508  }
509  return false;
510 }
511 
514  ReplaceInstWithInst(From->getParent()->getInstList(), BI, To);
515 }
516 
518  LoopInfo *LI, MemorySSAUpdater *MSSAU,
519  const Twine &BBName) {
520  unsigned SuccNum = GetSuccessorNumber(BB, Succ);
521 
522  Instruction *LatchTerm = BB->getTerminator();
523 
526 
527  if ((isCriticalEdge(LatchTerm, SuccNum, Options.MergeIdenticalEdges))) {
528  // If it is a critical edge, and the succesor is an exception block, handle
529  // the split edge logic in this specific function
530  if (Succ->isEHPad())
531  return ehAwareSplitEdge(BB, Succ, nullptr, nullptr, Options, BBName);
532 
533  // If this is a critical edge, let SplitKnownCriticalEdge do it.
534  return SplitKnownCriticalEdge(LatchTerm, SuccNum, Options, BBName);
535  }
536 
537  // If the edge isn't critical, then BB has a single successor or Succ has a
538  // single pred. Split the block.
539  if (BasicBlock *SP = Succ->getSinglePredecessor()) {
540  // If the successor only has a single pred, split the top of the successor
541  // block.
542  assert(SP == BB && "CFG broken");
543  SP = nullptr;
544  return SplitBlock(Succ, &Succ->front(), DT, LI, MSSAU, BBName,
545  /*Before=*/true);
546  }
547 
548  // Otherwise, if BB has a single successor, split it at the bottom of the
549  // block.
550  assert(BB->getTerminator()->getNumSuccessors() == 1 &&
551  "Should have a single succ!");
552  return SplitBlock(BB, BB->getTerminator(), DT, LI, MSSAU, BBName);
553 }
554 
556  if (auto *II = dyn_cast<InvokeInst>(TI))
557  II->setUnwindDest(Succ);
558  else if (auto *CS = dyn_cast<CatchSwitchInst>(TI))
559  CS->setUnwindDest(Succ);
560  else if (auto *CR = dyn_cast<CleanupReturnInst>(TI))
561  CR->setUnwindDest(Succ);
562  else
563  llvm_unreachable("unexpected terminator instruction");
564 }
565 
567  BasicBlock *NewPred, PHINode *Until) {
568  int BBIdx = 0;
569  for (PHINode &PN : DestBB->phis()) {
570  // We manually update the LandingPadReplacement PHINode and it is the last
571  // PHI Node. So, if we find it, we are done.
572  if (Until == &PN)
573  break;
574 
575  // Reuse the previous value of BBIdx if it lines up. In cases where we
576  // have multiple phi nodes with *lots* of predecessors, this is a speed
577  // win because we don't have to scan the PHI looking for TIBB. This
578  // happens because the BB list of PHI nodes are usually in the same
579  // order.
580  if (PN.getIncomingBlock(BBIdx) != OldPred)
581  BBIdx = PN.getBasicBlockIndex(OldPred);
582 
583  assert(BBIdx != -1 && "Invalid PHI Index!");
584  PN.setIncomingBlock(BBIdx, NewPred);
585  }
586 }
587 
589  LandingPadInst *OriginalPad,
590  PHINode *LandingPadReplacement,
592  const Twine &BBName) {
593 
594  auto *PadInst = Succ->getFirstNonPHI();
595  if (!LandingPadReplacement && !PadInst->isEHPad())
596  return SplitEdge(BB, Succ, Options.DT, Options.LI, Options.MSSAU, BBName);
597 
598  auto *LI = Options.LI;
600  // Check if extra modifications will be required to preserve loop-simplify
601  // form after splitting. If it would require splitting blocks with IndirectBr
602  // terminators, bail out if preserving loop-simplify form is requested.
603  if (Options.PreserveLoopSimplify && LI) {
604  if (Loop *BBLoop = LI->getLoopFor(BB)) {
605 
606  // The only way that we can break LoopSimplify form by splitting a
607  // critical edge is when there exists some edge from BBLoop to Succ *and*
608  // the only edge into Succ from outside of BBLoop is that of NewBB after
609  // the split. If the first isn't true, then LoopSimplify still holds,
610  // NewBB is the new exit block and it has no non-loop predecessors. If the
611  // second isn't true, then Succ was not in LoopSimplify form prior to
612  // the split as it had a non-loop predecessor. In both of these cases,
613  // the predecessor must be directly in BBLoop, not in a subloop, or again
614  // LoopSimplify doesn't hold.
615  for (BasicBlock *P : predecessors(Succ)) {
616  if (P == BB)
617  continue; // The new block is known.
618  if (LI->getLoopFor(P) != BBLoop) {
619  // Loop is not in LoopSimplify form, no need to re simplify after
620  // splitting edge.
621  LoopPreds.clear();
622  break;
623  }
624  LoopPreds.push_back(P);
625  }
626  // Loop-simplify form can be preserved, if we can split all in-loop
627  // predecessors.
628  if (any_of(LoopPreds, [](BasicBlock *Pred) {
629  return isa<IndirectBrInst>(Pred->getTerminator());
630  })) {
631  return nullptr;
632  }
633  }
634  }
635 
636  auto *NewBB =
637  BasicBlock::Create(BB->getContext(), BBName, BB->getParent(), Succ);
638  setUnwindEdgeTo(BB->getTerminator(), NewBB);
639  updatePhiNodes(Succ, BB, NewBB, LandingPadReplacement);
640 
641  if (LandingPadReplacement) {
642  auto *NewLP = OriginalPad->clone();
643  auto *Terminator = BranchInst::Create(Succ, NewBB);
644  NewLP->insertBefore(Terminator);
645  LandingPadReplacement->addIncoming(NewLP, NewBB);
646  } else {
647  Value *ParentPad = nullptr;
648  if (auto *FuncletPad = dyn_cast<FuncletPadInst>(PadInst))
649  ParentPad = FuncletPad->getParentPad();
650  else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(PadInst))
651  ParentPad = CatchSwitch->getParentPad();
652  else if (auto *CleanupPad = dyn_cast<CleanupPadInst>(PadInst))
653  ParentPad = CleanupPad->getParentPad();
654  else if (auto *LandingPad = dyn_cast<LandingPadInst>(PadInst))
655  ParentPad = LandingPad->getParent();
656  else
657  llvm_unreachable("handling for other EHPads not implemented yet");
658 
659  auto *NewCleanupPad = CleanupPadInst::Create(ParentPad, {}, BBName, NewBB);
660  CleanupReturnInst::Create(NewCleanupPad, Succ, NewBB);
661  }
662 
663  auto *DT = Options.DT;
664  auto *MSSAU = Options.MSSAU;
665  if (!DT && !LI)
666  return NewBB;
667 
668  if (DT) {
671 
672  Updates.push_back({DominatorTree::Insert, BB, NewBB});
673  Updates.push_back({DominatorTree::Insert, NewBB, Succ});
674  Updates.push_back({DominatorTree::Delete, BB, Succ});
675 
676  DTU.applyUpdates(Updates);
677  DTU.flush();
678 
679  if (MSSAU) {
680  MSSAU->applyUpdates(Updates, *DT);
681  if (VerifyMemorySSA)
682  MSSAU->getMemorySSA()->verifyMemorySSA();
683  }
684  }
685 
686  if (LI) {
687  if (Loop *BBLoop = LI->getLoopFor(BB)) {
688  // If one or the other blocks were not in a loop, the new block is not
689  // either, and thus LI doesn't need to be updated.
690  if (Loop *SuccLoop = LI->getLoopFor(Succ)) {
691  if (BBLoop == SuccLoop) {
692  // Both in the same loop, the NewBB joins loop.
693  SuccLoop->addBasicBlockToLoop(NewBB, *LI);
694  } else if (BBLoop->contains(SuccLoop)) {
695  // Edge from an outer loop to an inner loop. Add to the outer loop.
696  BBLoop->addBasicBlockToLoop(NewBB, *LI);
697  } else if (SuccLoop->contains(BBLoop)) {
698  // Edge from an inner loop to an outer loop. Add to the outer loop.
699  SuccLoop->addBasicBlockToLoop(NewBB, *LI);
700  } else {
701  // Edge from two loops with no containment relation. Because these
702  // are natural loops, we know that the destination block must be the
703  // header of its loop (adding a branch into a loop elsewhere would
704  // create an irreducible loop).
705  assert(SuccLoop->getHeader() == Succ &&
706  "Should not create irreducible loops!");
707  if (Loop *P = SuccLoop->getParentLoop())
708  P->addBasicBlockToLoop(NewBB, *LI);
709  }
710  }
711 
712  // If BB is in a loop and Succ is outside of that loop, we may need to
713  // update LoopSimplify form and LCSSA form.
714  if (!BBLoop->contains(Succ)) {
715  assert(!BBLoop->contains(NewBB) &&
716  "Split point for loop exit is contained in loop!");
717 
718  // Update LCSSA form in the newly created exit block.
719  if (Options.PreserveLCSSA) {
720  createPHIsForSplitLoopExit(BB, NewBB, Succ);
721  }
722 
723  if (!LoopPreds.empty()) {
724  BasicBlock *NewExitBB = SplitBlockPredecessors(
725  Succ, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA);
726  if (Options.PreserveLCSSA)
727  createPHIsForSplitLoopExit(LoopPreds, NewExitBB, Succ);
728  }
729  }
730  }
731  }
732 
733  return NewBB;
734 }
735 
737  BasicBlock *SplitBB, BasicBlock *DestBB) {
738  // SplitBB shouldn't have anything non-trivial in it yet.
739  assert((SplitBB->getFirstNonPHI() == SplitBB->getTerminator() ||
740  SplitBB->isLandingPad()) &&
741  "SplitBB has non-PHI nodes!");
742 
743  // For each PHI in the destination block.
744  for (PHINode &PN : DestBB->phis()) {
745  int Idx = PN.getBasicBlockIndex(SplitBB);
746  assert(Idx >= 0 && "Invalid Block Index");
747  Value *V = PN.getIncomingValue(Idx);
748 
749  // If the input is a PHI which already satisfies LCSSA, don't create
750  // a new one.
751  if (const PHINode *VP = dyn_cast<PHINode>(V))
752  if (VP->getParent() == SplitBB)
753  continue;
754 
755  // Otherwise a new PHI is needed. Create one and populate it.
756  PHINode *NewPN = PHINode::Create(
757  PN.getType(), Preds.size(), "split",
758  SplitBB->isLandingPad() ? &SplitBB->front() : SplitBB->getTerminator());
759  for (BasicBlock *BB : Preds)
760  NewPN->addIncoming(V, BB);
761 
762  // Update the original PHI.
763  PN.setIncomingValue(Idx, NewPN);
764  }
765 }
766 
767 unsigned
770  unsigned NumBroken = 0;
771  for (BasicBlock &BB : F) {
772  Instruction *TI = BB.getTerminator();
773  if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI))
774  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
775  if (SplitCriticalEdge(TI, i, Options))
776  ++NumBroken;
777  }
778  return NumBroken;
779 }
780 
782  DomTreeUpdater *DTU, DominatorTree *DT,
783  LoopInfo *LI, MemorySSAUpdater *MSSAU,
784  const Twine &BBName, bool Before) {
785  if (Before) {
787  return splitBlockBefore(Old, SplitPt,
788  DTU ? DTU : (DT ? &LocalDTU : nullptr), LI, MSSAU,
789  BBName);
790  }
791  BasicBlock::iterator SplitIt = SplitPt->getIterator();
792  while (isa<PHINode>(SplitIt) || SplitIt->isEHPad()) {
793  ++SplitIt;
794  assert(SplitIt != SplitPt->getParent()->end());
795  }
796  std::string Name = BBName.str();
797  BasicBlock *New = Old->splitBasicBlock(
798  SplitIt, Name.empty() ? Old->getName() + ".split" : Name);
799 
800  // The new block lives in whichever loop the old one did. This preserves
801  // LCSSA as well, because we force the split point to be after any PHI nodes.
802  if (LI)
803  if (Loop *L = LI->getLoopFor(Old))
804  L->addBasicBlockToLoop(New, *LI);
805 
806  if (DTU) {
808  // Old dominates New. New node dominates all other nodes dominated by Old.
809  SmallPtrSet<BasicBlock *, 8> UniqueSuccessorsOfOld;
810  Updates.push_back({DominatorTree::Insert, Old, New});
811  Updates.reserve(Updates.size() + 2 * succ_size(New));
812  for (BasicBlock *SuccessorOfOld : successors(New))
813  if (UniqueSuccessorsOfOld.insert(SuccessorOfOld).second) {
814  Updates.push_back({DominatorTree::Insert, New, SuccessorOfOld});
815  Updates.push_back({DominatorTree::Delete, Old, SuccessorOfOld});
816  }
817 
818  DTU->applyUpdates(Updates);
819  } else if (DT)
820  // Old dominates New. New node dominates all other nodes dominated by Old.
821  if (DomTreeNode *OldNode = DT->getNode(Old)) {
822  std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
823 
824  DomTreeNode *NewNode = DT->addNewBlock(New, Old);
825  for (DomTreeNode *I : Children)
826  DT->changeImmediateDominator(I, NewNode);
827  }
828 
829  // Move MemoryAccesses still tracked in Old, but part of New now.
830  // Update accesses in successor blocks accordingly.
831  if (MSSAU)
832  MSSAU->moveAllAfterSpliceBlocks(Old, New, &*(New->begin()));
833 
834  return New;
835 }
836 
838  DominatorTree *DT, LoopInfo *LI,
839  MemorySSAUpdater *MSSAU, const Twine &BBName,
840  bool Before) {
841  return SplitBlockImpl(Old, SplitPt, /*DTU=*/nullptr, DT, LI, MSSAU, BBName,
842  Before);
843 }
845  DomTreeUpdater *DTU, LoopInfo *LI,
846  MemorySSAUpdater *MSSAU, const Twine &BBName,
847  bool Before) {
848  return SplitBlockImpl(Old, SplitPt, DTU, /*DT=*/nullptr, LI, MSSAU, BBName,
849  Before);
850 }
851 
853  DomTreeUpdater *DTU, LoopInfo *LI,
854  MemorySSAUpdater *MSSAU,
855  const Twine &BBName) {
856 
857  BasicBlock::iterator SplitIt = SplitPt->getIterator();
858  while (isa<PHINode>(SplitIt) || SplitIt->isEHPad())
859  ++SplitIt;
860  std::string Name = BBName.str();
861  BasicBlock *New = Old->splitBasicBlock(
862  SplitIt, Name.empty() ? Old->getName() + ".split" : Name,
863  /* Before=*/true);
864 
865  // The new block lives in whichever loop the old one did. This preserves
866  // LCSSA as well, because we force the split point to be after any PHI nodes.
867  if (LI)
868  if (Loop *L = LI->getLoopFor(Old))
869  L->addBasicBlockToLoop(New, *LI);
870 
871  if (DTU) {
873  // New dominates Old. The predecessor nodes of the Old node dominate
874  // New node.
875  SmallPtrSet<BasicBlock *, 8> UniquePredecessorsOfOld;
876  DTUpdates.push_back({DominatorTree::Insert, New, Old});
877  DTUpdates.reserve(DTUpdates.size() + 2 * pred_size(New));
878  for (BasicBlock *PredecessorOfOld : predecessors(New))
879  if (UniquePredecessorsOfOld.insert(PredecessorOfOld).second) {
880  DTUpdates.push_back({DominatorTree::Insert, PredecessorOfOld, New});
881  DTUpdates.push_back({DominatorTree::Delete, PredecessorOfOld, Old});
882  }
883 
884  DTU->applyUpdates(DTUpdates);
885 
886  // Move MemoryAccesses still tracked in Old, but part of New now.
887  // Update accesses in successor blocks accordingly.
888  if (MSSAU) {
889  MSSAU->applyUpdates(DTUpdates, DTU->getDomTree());
890  if (VerifyMemorySSA)
891  MSSAU->getMemorySSA()->verifyMemorySSA();
892  }
893  }
894  return New;
895 }
896 
897 /// Update DominatorTree, LoopInfo, and LCCSA analysis information.
900  DomTreeUpdater *DTU, DominatorTree *DT,
901  LoopInfo *LI, MemorySSAUpdater *MSSAU,
902  bool PreserveLCSSA, bool &HasLoopExit) {
903  // Update dominator tree if available.
904  if (DTU) {
905  // Recalculation of DomTree is needed when updating a forward DomTree and
906  // the Entry BB is replaced.
907  if (NewBB->isEntryBlock() && DTU->hasDomTree()) {
908  // The entry block was removed and there is no external interface for
909  // the dominator tree to be notified of this change. In this corner-case
910  // we recalculate the entire tree.
911  DTU->recalculate(*NewBB->getParent());
912  } else {
913  // Split block expects NewBB to have a non-empty set of predecessors.
915  SmallPtrSet<BasicBlock *, 8> UniquePreds;
916  Updates.push_back({DominatorTree::Insert, NewBB, OldBB});
917  Updates.reserve(Updates.size() + 2 * Preds.size());
918  for (auto *Pred : Preds)
919  if (UniquePreds.insert(Pred).second) {
920  Updates.push_back({DominatorTree::Insert, Pred, NewBB});
921  Updates.push_back({DominatorTree::Delete, Pred, OldBB});
922  }
923  DTU->applyUpdates(Updates);
924  }
925  } else if (DT) {
926  if (OldBB == DT->getRootNode()->getBlock()) {
927  assert(NewBB->isEntryBlock());
928  DT->setNewRoot(NewBB);
929  } else {
930  // Split block expects NewBB to have a non-empty set of predecessors.
931  DT->splitBlock(NewBB);
932  }
933  }
934 
935  // Update MemoryPhis after split if MemorySSA is available
936  if (MSSAU)
937  MSSAU->wireOldPredecessorsToNewImmediatePredecessor(OldBB, NewBB, Preds);
938 
939  // The rest of the logic is only relevant for updating the loop structures.
940  if (!LI)
941  return;
942 
943  if (DTU && DTU->hasDomTree())
944  DT = &DTU->getDomTree();
945  assert(DT && "DT should be available to update LoopInfo!");
946  Loop *L = LI->getLoopFor(OldBB);
947 
948  // If we need to preserve loop analyses, collect some information about how
949  // this split will affect loops.
950  bool IsLoopEntry = !!L;
951  bool SplitMakesNewLoopHeader = false;
952  for (BasicBlock *Pred : Preds) {
953  // Preds that are not reachable from entry should not be used to identify if
954  // OldBB is a loop entry or if SplitMakesNewLoopHeader. Unreachable blocks
955  // are not within any loops, so we incorrectly mark SplitMakesNewLoopHeader
956  // as true and make the NewBB the header of some loop. This breaks LI.
957  if (!DT->isReachableFromEntry(Pred))
958  continue;
959  // If we need to preserve LCSSA, determine if any of the preds is a loop
960  // exit.
961  if (PreserveLCSSA)
962  if (Loop *PL = LI->getLoopFor(Pred))
963  if (!PL->contains(OldBB))
964  HasLoopExit = true;
965 
966  // If we need to preserve LoopInfo, note whether any of the preds crosses
967  // an interesting loop boundary.
968  if (!L)
969  continue;
970  if (L->contains(Pred))
971  IsLoopEntry = false;
972  else
973  SplitMakesNewLoopHeader = true;
974  }
975 
976  // Unless we have a loop for OldBB, nothing else to do here.
977  if (!L)
978  return;
979 
980  if (IsLoopEntry) {
981  // Add the new block to the nearest enclosing loop (and not an adjacent
982  // loop). To find this, examine each of the predecessors and determine which
983  // loops enclose them, and select the most-nested loop which contains the
984  // loop containing the block being split.
985  Loop *InnermostPredLoop = nullptr;
986  for (BasicBlock *Pred : Preds) {
987  if (Loop *PredLoop = LI->getLoopFor(Pred)) {
988  // Seek a loop which actually contains the block being split (to avoid
989  // adjacent loops).
990  while (PredLoop && !PredLoop->contains(OldBB))
991  PredLoop = PredLoop->getParentLoop();
992 
993  // Select the most-nested of these loops which contains the block.
994  if (PredLoop && PredLoop->contains(OldBB) &&
995  (!InnermostPredLoop ||
996  InnermostPredLoop->getLoopDepth() < PredLoop->getLoopDepth()))
997  InnermostPredLoop = PredLoop;
998  }
999  }
1000 
1001  if (InnermostPredLoop)
1002  InnermostPredLoop->addBasicBlockToLoop(NewBB, *LI);
1003  } else {
1004  L->addBasicBlockToLoop(NewBB, *LI);
1005  if (SplitMakesNewLoopHeader)
1006  L->moveToHeader(NewBB);
1007  }
1008 }
1009 
1010 /// Update the PHI nodes in OrigBB to include the values coming from NewBB.
1011 /// This also updates AliasAnalysis, if available.
1012 static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB,
1014  bool HasLoopExit) {
1015  // Otherwise, create a new PHI node in NewBB for each PHI node in OrigBB.
1016  SmallPtrSet<BasicBlock *, 16> PredSet(Preds.begin(), Preds.end());
1017  for (BasicBlock::iterator I = OrigBB->begin(); isa<PHINode>(I); ) {
1018  PHINode *PN = cast<PHINode>(I++);
1019 
1020  // Check to see if all of the values coming in are the same. If so, we
1021  // don't need to create a new PHI node, unless it's needed for LCSSA.
1022  Value *InVal = nullptr;
1023  if (!HasLoopExit) {
1024  InVal = PN->getIncomingValueForBlock(Preds[0]);
1025  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1026  if (!PredSet.count(PN->getIncomingBlock(i)))
1027  continue;
1028  if (!InVal)
1029  InVal = PN->getIncomingValue(i);
1030  else if (InVal != PN->getIncomingValue(i)) {
1031  InVal = nullptr;
1032  break;
1033  }
1034  }
1035  }
1036 
1037  if (InVal) {
1038  // If all incoming values for the new PHI would be the same, just don't
1039  // make a new PHI. Instead, just remove the incoming values from the old
1040  // PHI.
1041 
1042  // NOTE! This loop walks backwards for a reason! First off, this minimizes
1043  // the cost of removal if we end up removing a large number of values, and
1044  // second off, this ensures that the indices for the incoming values
1045  // aren't invalidated when we remove one.
1046  for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i)
1047  if (PredSet.count(PN->getIncomingBlock(i)))
1048  PN->removeIncomingValue(i, false);
1049 
1050  // Add an incoming value to the PHI node in the loop for the preheader
1051  // edge.
1052  PN->addIncoming(InVal, NewBB);
1053  continue;
1054  }
1055 
1056  // If the values coming into the block are not the same, we need a new
1057  // PHI.
1058  // Create the new PHI node, insert it into NewBB at the end of the block
1059  PHINode *NewPHI =
1060  PHINode::Create(PN->getType(), Preds.size(), PN->getName() + ".ph", BI);
1061 
1062  // NOTE! This loop walks backwards for a reason! First off, this minimizes
1063  // the cost of removal if we end up removing a large number of values, and
1064  // second off, this ensures that the indices for the incoming values aren't
1065  // invalidated when we remove one.
1066  for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) {
1067  BasicBlock *IncomingBB = PN->getIncomingBlock(i);
1068  if (PredSet.count(IncomingBB)) {
1069  Value *V = PN->removeIncomingValue(i, false);
1070  NewPHI->addIncoming(V, IncomingBB);
1071  }
1072  }
1073 
1074  PN->addIncoming(NewPHI, NewBB);
1075  }
1076 }
1077 
1079  BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix1,
1080  const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs,
1081  DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI,
1082  MemorySSAUpdater *MSSAU, bool PreserveLCSSA);
1083 
1084 static BasicBlock *
1086  const char *Suffix, DomTreeUpdater *DTU,
1087  DominatorTree *DT, LoopInfo *LI,
1088  MemorySSAUpdater *MSSAU, bool PreserveLCSSA) {
1089  // Do not attempt to split that which cannot be split.
1090  if (!BB->canSplitPredecessors())
1091  return nullptr;
1092 
1093  // For the landingpads we need to act a bit differently.
1094  // Delegate this work to the SplitLandingPadPredecessors.
1095  if (BB->isLandingPad()) {
1097  std::string NewName = std::string(Suffix) + ".split-lp";
1098 
1099  SplitLandingPadPredecessorsImpl(BB, Preds, Suffix, NewName.c_str(), NewBBs,
1100  DTU, DT, LI, MSSAU, PreserveLCSSA);
1101  return NewBBs[0];
1102  }
1103 
1104  // Create new basic block, insert right before the original block.
1105  BasicBlock *NewBB = BasicBlock::Create(
1106  BB->getContext(), BB->getName() + Suffix, BB->getParent(), BB);
1107 
1108  // The new block unconditionally branches to the old block.
1109  BranchInst *BI = BranchInst::Create(BB, NewBB);
1110 
1111  Loop *L = nullptr;
1112  BasicBlock *OldLatch = nullptr;
1113  // Splitting the predecessors of a loop header creates a preheader block.
1114  if (LI && LI->isLoopHeader(BB)) {
1115  L = LI->getLoopFor(BB);
1116  // Using the loop start line number prevents debuggers stepping into the
1117  // loop body for this instruction.
1118  BI->setDebugLoc(L->getStartLoc());
1119 
1120  // If BB is the header of the Loop, it is possible that the loop is
1121  // modified, such that the current latch does not remain the latch of the
1122  // loop. If that is the case, the loop metadata from the current latch needs
1123  // to be applied to the new latch.
1124  OldLatch = L->getLoopLatch();
1125  } else
1126  BI->setDebugLoc(BB->getFirstNonPHIOrDbg()->getDebugLoc());
1127 
1128  // Move the edges from Preds to point to NewBB instead of BB.
1129  for (BasicBlock *Pred : Preds) {
1130  // This is slightly more strict than necessary; the minimum requirement
1131  // is that there be no more than one indirectbr branching to BB. And
1132  // all BlockAddress uses would need to be updated.
1133  assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
1134  "Cannot split an edge from an IndirectBrInst");
1135  Pred->getTerminator()->replaceSuccessorWith(BB, NewBB);
1136  }
1137 
1138  // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI
1139  // node becomes an incoming value for BB's phi node. However, if the Preds
1140  // list is empty, we need to insert dummy entries into the PHI nodes in BB to
1141  // account for the newly created predecessor.
1142  if (Preds.empty()) {
1143  // Insert dummy values as the incoming value.
1144  for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I)
1145  cast<PHINode>(I)->addIncoming(PoisonValue::get(I->getType()), NewBB);
1146  }
1147 
1148  // Update DominatorTree, LoopInfo, and LCCSA analysis information.
1149  bool HasLoopExit = false;
1150  UpdateAnalysisInformation(BB, NewBB, Preds, DTU, DT, LI, MSSAU, PreserveLCSSA,
1151  HasLoopExit);
1152 
1153  if (!Preds.empty()) {
1154  // Update the PHI nodes in BB with the values coming from NewBB.
1155  UpdatePHINodes(BB, NewBB, Preds, BI, HasLoopExit);
1156  }
1157 
1158  if (OldLatch) {
1159  BasicBlock *NewLatch = L->getLoopLatch();
1160  if (NewLatch != OldLatch) {
1161  MDNode *MD = OldLatch->getTerminator()->getMetadata("llvm.loop");
1162  NewLatch->getTerminator()->setMetadata("llvm.loop", MD);
1163  // It's still possible that OldLatch is the latch of another inner loop,
1164  // in which case we do not remove the metadata.
1165  Loop *IL = LI->getLoopFor(OldLatch);
1166  if (IL && IL->getLoopLatch() != OldLatch)
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 (BasicBlock *Pred : Preds) {
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>(Pred->getTerminator()) &&
1216  "Cannot split an edge from an IndirectBrInst");
1217  Pred->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:1504
llvm::invertCondition
Value * invertCondition(Value *Condition)
Invert the given true/false value, possibly reusing an existing copy.
Definition: Local.cpp:3329
llvm::BasicBlock::end
iterator end()
Definition: BasicBlock.h:308
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:236
llvm::MemorySSA::verifyMemorySSA
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1875
llvm::DomTreeUpdater::deleteBB
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
Definition: DomTreeUpdater.cpp:178
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:3052
llvm::SmallPtrSetImpl::erase
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
Definition: SmallPtrSet.h:379
llvm::User::operands
op_range operands()
Definition: User.h:242
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
IntrinsicInst.h
DebugInfoMetadata.h
llvm::cl::Prefix
@ Prefix
Definition: CommandLine.h:160
llvm::DomTreeUpdater::applyUpdates
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Definition: DomTreeUpdater.cpp:231
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
MemorySSAUpdater.h
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:138
createGuardBlocks
static void createGuardBlocks(SmallVectorImpl< BasicBlock * > &GuardBlocks, Function *F, const BBSetVector &Outgoing, BBPredicates &GuardPredicates, StringRef Prefix)
Definition: BasicBlockUtils.cpp: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:5256
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1182
llvm::pred_size
unsigned pred_size(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:32
llvm::LandingPadInst
The landingpad instruction holds all of the information necessary to generate correct exception handl...
Definition: Instructions.h:2951
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:627
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:114
llvm::DeleteDeadBlocks
void DeleteDeadBlocks(ArrayRef< BasicBlock * > BBs, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified blocks from BB.
Definition: BasicBlockUtils.cpp:99
llvm::MemoryDependenceResults::invalidateCachedPredecessors
void invalidateCachedPredecessors()
Clears the PredIteratorCache info.
Definition: MemoryDependenceAnalysis.cpp:1500
Local.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
llvm::detachDeadBlocks
void detachDeadBlocks(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< DominatorTree::UpdateType > *Updates, bool KeepOneInputPHIs=false)
Replace contents of every block in BBs with single unreachable instruction.
Definition: BasicBlockUtils.cpp:60
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
llvm::LoopInfoBase::removeBlock
void removeBlock(BlockT *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
Definition: LoopInfo.h:1054
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:736
llvm::SplitCriticalEdge
BasicBlock * SplitCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")
If this edge is a critical edge, insert a new node to split the critical edge.
Definition: BreakCriticalEdges.cpp:101
llvm::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:1247
llvm::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:351
llvm::BasicBlock::splitBasicBlock
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)
Split the basic block into two basic blocks at the specified instruction.
Definition: BasicBlock.cpp:402
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:450
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
llvm::isCriticalEdge
bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
Definition: CFG.cpp:95
llvm::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:285
llvm::DIExpression
DWARF expression.
Definition: DebugInfoMetadata.h:2558
MemoryDependenceAnalysis.h
SplitBlockPredecessorsImpl
static BasicBlock * SplitBlockPredecessorsImpl(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Definition: BasicBlockUtils.cpp:1085
llvm::detail::DenseSetImpl< ValueT, SmallDenseMap< ValueT, detail::DenseSetEmpty, 4, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::Instruction::isExceptionalTerminator
bool isExceptionalTerminator() const
Definition: Instruction.h:174
llvm::MemorySSAUpdater::applyUpdates
void applyUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT, bool UpdateDTFirst=false)
Apply CFG updates, analogous with the DT edge updates.
Definition: MemorySSAUpdater.cpp:809
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::Instruction::mayHaveSideEffects
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.cpp:721
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BranchInst::setSuccessor
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Definition: Instructions.h:3232
llvm::Instruction::setMetadata
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1428
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:628
llvm::BasicBlock::getUniqueSuccessor
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
Definition: BasicBlock.cpp:323
llvm::DomTreeUpdater::UpdateStrategy::Lazy
@ Lazy
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Instruction.h
CommandLine.h
llvm::LoopBase::getParentLoop
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:113
llvm::Instruction::getNumSuccessors
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Definition: Instruction.cpp:803
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:2795
llvm::DbgValueInst
This represents the llvm.dbg.value instruction.
Definition: IntrinsicInst.h:352
llvm::CreateControlFlowHub
BasicBlock * CreateControlFlowHub(DomTreeUpdater *DTU, SmallVectorImpl< BasicBlock * > &GuardBlocks, const SetVector< BasicBlock * > &Predecessors, const SetVector< BasicBlock * > &Successors, const StringRef Prefix)
Given a set of incoming and outgoing blocks, create a "hub" such that every edge from an incoming blo...
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::CleanupReturnInst::Create
static CleanupReturnInst * Create(Value *CleanupPad, BasicBlock *UnwindBB=nullptr, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:4682
Twine.h
InstrTypes.h
llvm::SplitKnownCriticalEdge
BasicBlock * SplitKnownCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")
If it is known that an edge is critical, SplitKnownCriticalEdge can be called directly,...
Definition: BreakCriticalEdges.cpp:111
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:306
UpdatePHINodes
static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB, ArrayRef< BasicBlock * > Preds, BranchInst *BI, bool HasLoopExit)
Update the PHI nodes in OrigBB to include the values coming from NewBB.
Definition: BasicBlockUtils.cpp:1012
llvm::BasicBlock::isLandingPad
bool isLandingPad() const
Return true if this basic block is a landing pad.
Definition: BasicBlock.cpp:493
llvm::DomTreeUpdater::recalculate
void recalculate(Function &F)
Notify DTU that the entry block was replaced.
Definition: DomTreeUpdater.cpp:121
llvm::ReplaceInstWithInst
void ReplaceInstWithInst(BasicBlock::InstListType &BIL, BasicBlock::iterator &BI, Instruction *I)
Replace the instruction specified by BI with the instruction specified by I.
Definition: BasicBlockUtils.cpp:478
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:486
llvm::CriticalEdgeSplittingOptions
Option class for critical edge splitting.
Definition: BasicBlockUtils.h:142
llvm::BasicBlock::getFirstInsertionPt
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:246
llvm::succ_size
unsigned succ_size(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:31
llvm::MemorySSAUpdater::moveToPlace
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
Definition: MemorySSAUpdater.cpp:1200
llvm::depth_first_ext
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
Definition: DepthFirstIterator.h:252
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2884
llvm::Type::isTokenTy
bool isTokenTy() const
Return true if this is 'token'.
Definition: Type.h:193
llvm::Instruction
Definition: Instruction.h:42
convertToGuardPredicates
static void convertToGuardPredicates(BasicBlock *FirstGuardBlock, BBPredicates &GuardPredicates, SmallVectorImpl< WeakVH > &DeletionCandidates, const BBSetVector &Incoming, const BBSetVector &Outgoing)
Definition: BasicBlockUtils.cpp: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:364
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:375
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1708
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:209
llvm::RemoveRedundantDbgInstrs
bool RemoveRedundantDbgInstrs(BasicBlock *BB)
Try to remove redundant dbg.value instructions from given basic block.
Definition: BasicBlockUtils.cpp:442
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:588
removeRedundantDbgInstrsUsingForwardScan
static bool removeRedundantDbgInstrsUsingForwardScan(BasicBlock *BB)
Remove redundant dbg.value instructions using a forward scan.
Definition: BasicBlockUtils.cpp:413
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2791
llvm::EliminateUnreachableBlocks
bool EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete all basic blocks from F that are not reachable from its entry node.
Definition: BasicBlockUtils.cpp:123
llvm::DomTreeUpdater::hasDomTree
bool hasDomTree() const
Returns true if it holds a DominatorTree.
Definition: DomTreeUpdater.h:57
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:344
Type.h
llvm::Instruction::getMetadata
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:271
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:396
llvm::SmallPtrSetImplBase::empty
bool empty() const
Definition: SmallPtrSet.h:92
llvm::tgtok::In
@ In
Definition: TGLexer.h:51
BasicBlock.h
llvm::cl::opt
Definition: CommandLine.h:1399
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:77
llvm::DomTreeNodeBase::getBlock
NodeT * getBlock() const
Definition: GenericDomTree.h:88
removeRedundantDbgInstrsUsingBackwardScan
static bool removeRedundantDbgInstrsUsingBackwardScan(BasicBlock *BB)
Remove redundant instructions within sequences of consecutive dbg.value instructions.
Definition: BasicBlockUtils.cpp:366
llvm::LoopBase::moveToHeader
void moveToHeader(BlockT *BB)
This method is used to move BB (which must be part of this loop) to be the loop header of the loop (t...
Definition: LoopInfo.h:459
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:54
llvm::NoneType
NoneType
A simple null object to allow implicit construction of Optional<T> and similar types without having t...
Definition: None.h:23
llvm::MemorySSAUpdater::getMemorySSA
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
Definition: MemorySSAUpdater.h:242
MaxDeoptOrUnreachableSuccessorCheckDepth
static cl::opt< unsigned > MaxDeoptOrUnreachableSuccessorCheckDepth("max-deopt-or-unreachable-succ-check-depth", cl::init(8), cl::Hidden, cl::desc("Set the maximum path length when checking whether a basic block " "is followed by a block that either has a terminating " "deoptimizing call or is terminated with an unreachable"))
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2849
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:54
llvm::DomTreeUpdater::getDomTree
DominatorTree & getDomTree()
Flush DomTree updates and return DomTree.
Definition: DomTreeUpdater.cpp:304
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3190
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:989
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:717
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:439
llvm::DebugVariable
Identifies a unique instance of a variable.
Definition: DebugInfoMetadata.h:3620
llvm::SmallPtrSetImpl::begin
iterator begin() const
Definition: SmallPtrSet.h:403
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1673
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:566
ArrayRef.h
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:351
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:215
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h: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:853
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:781
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:335
llvm::MDNode
Metadata node.
Definition: Metadata.h:944
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:383
llvm::BranchInst::isUnconditional
bool isUnconditional() const
Definition: Instructions.h:3212
llvm::User::setOperand
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
llvm::detail::DenseSetImpl< ValueT, SmallDenseMap< ValueT, detail::DenseSetEmpty, 4, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::clear
void clear()
Definition: DenseSet.h:92
llvm::df_iterator_default_set
Definition: DepthFirstIterator.h:70
llvm::GetSuccessorNumber
unsigned GetSuccessorNumber(const BasicBlock *BB, const BasicBlock *Succ)
Search for the specified successor of basic block BB and return its position in the terminator instru...
Definition: CFG.cpp:79
CFG.h
llvm::Instruction::clone
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
Definition: Instruction.cpp:888
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:95
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::LoopInfo
Definition: LoopInfo.h:1105
llvm::MergeBlockIntoPredecessor
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false)
Attempts to merge a block into its predecessor, if possible.
Definition: BasicBlockUtils.cpp:178
llvm::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1597
llvm::SymbolTableList< Instruction >
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::BasicBlock::getUniquePredecessor
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:293
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:97
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
llvm::MemorySSA::End
@ End
Definition: MemorySSA.h:788
llvm::CleanupPadInst::Create
static CleanupPadInst * Create(Value *ParentPad, ArrayRef< Value * > Args=None, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:4504
llvm::PredIterator
Definition: CFG.h:42
llvm::DomTreeUpdater::flush
void flush()
Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.
Definition: DomTreeUpdater.cpp:73
llvm::DomTreeNodeBase< BasicBlock >
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
ValueHandle.h
llvm::DominatorTreeBase::addNewBlock
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
Definition: GenericDomTree.h:619
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:834
llvm::BasicBlock::front
const Instruction & front() const
Definition: BasicBlock.h:318
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:35
llvm::ReplaceInstWithValue
void ReplaceInstWithValue(BasicBlock::InstListType &BIL, BasicBlock::iterator &BI, Value *V)
Replace all uses of an instruction (specified by BI) with a value, then remove and delete the origina...
Definition: BasicBlockUtils.cpp:464
llvm::MemoryDependenceResults
Provides a lazy, caching interface for making common memory aliasing information queries,...
Definition: MemoryDependenceAnalysis.h:265
llvm::LoopInfoBase::isLoopHeader
bool isLoopHeader(const BlockT *BB) const
Definition: LoopInfo.h:1002
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:517
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:827
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:50
llvm::setUnwindEdgeTo
void setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ)
Sets the unwind edge of an instruction to a particular successor.
Definition: BasicBlockUtils.cpp:555
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:84
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
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:2741
llvm::ArrayRef::begin
iterator begin() const
Definition: ArrayRef.h:152
llvm::MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor
void wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New, ArrayRef< BasicBlock * > Preds, bool IdenticalEdgesWereMerged=true)
A new empty BasicBlock (New) now branches directly to Old.
Definition: MemorySSAUpdater.cpp:1268
llvm::MemorySSAUpdater::moveAllAfterMergeBlocks
void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was merged into To.
Definition: MemorySSAUpdater.cpp:1258
UpdateAnalysisInformation
static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB, ArrayRef< BasicBlock * > Preds, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA, bool &HasLoopExit)
Update DominatorTree, LoopInfo, and LCCSA analysis information.
Definition: BasicBlockUtils.cpp:898
llvm::pred_end
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
llvm::ExtractValueInst
This instruction extracts a struct member or array element value from an aggregate value.
Definition: Instructions.h:2446
llvm::MCID::Branch
@ Branch
Definition: MCInstrDesc.h:158
llvm::DominatorTreeBase::splitBlock
void splitBlock(NodeT *NewBB)
splitBlock - BB is split and now it has one successor.
Definition: GenericDomTree.h:700
llvm::CriticalEdgeSplittingOptions::setPreserveLCSSA
CriticalEdgeSplittingOptions & setPreserveLCSSA()
Definition: BasicBlockUtils.h:172
Casting.h
Function.h
llvm::DenseMapBase::size
unsigned size() const
Definition: DenseMap.h:99
llvm::SetVector::count
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:215
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:222
llvm::SetVector::front
const T & front() const
Return the first element of the SetVector.
Definition: SetVector.h:122
llvm::Instruction::isEHPad
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:649
llvm::MemoryUseOrDef
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:252
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:597
llvm::splitBlockBefore
BasicBlock * splitBlockBefore(BasicBlock *Old, Instruction *SplitPt, DomTreeUpdater *DTU, LoopInfo *LI, MemorySSAUpdater *MSSAU, const Twine &BBName="")
Split the specified block at the specified instruction SplitPt.
Definition: BasicBlockUtils.cpp:852
llvm::FoldSingleEntryPHINodes
bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
Definition: BasicBlockUtils.cpp:143
llvm::DeleteDeadPHIs
bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Examine each PHI in the given block and delete it if it is dead.
Definition: BasicBlockUtils.cpp:162
llvm::BasicBlock::back
const Instruction & back() const
Definition: BasicBlock.h:320
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:768
llvm::BasicBlock::getInstList
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:373
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:498
SmallVector.h
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:354
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:320
User.h
llvm::LoopBase::addBasicBlockToLoop
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Definition: LoopInfoImpl.h:241
Dominators.h
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2815
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:164
llvm::PHINode
Definition: Instructions.h:2699
llvm::BasicBlock::getTerminator
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:119
llvm::SmallVectorImpl< DominatorTree::UpdateType >
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:365
llvm::RegState::Dead
@ Dead
Unused definition.
Definition: MachineInstrBuilder.h:50
llvm::BasicBlock::getLandingPadInst
const LandingPadInst * getLandingPadInst() const
Return the landingpad instruction associated with the landing pad.
Definition: BasicBlock.cpp:497
llvm::DeleteDeadBlock
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
Definition: BasicBlockUtils.cpp:94
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
llvm::SetVector::back
const T & back() const
Return the last element of the SetVector.
Definition: SetVector.h:128
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::CallingConv::Tail
@ Tail
Attemps to make calls as fast as possible while guaranteeing that tail call optimization can always b...
Definition: CallingConv.h:76
llvm::UnreachableInst
This function has undefined behavior.
Definition: Instructions.h:4771
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:381
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:3134
raw_ostream.h
llvm::SetVector
A vector that has set insertion semantics.
Definition: SetVector.h:40
llvm::SmallPtrSetImpl::contains
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:389
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:650
BasicBlockUtils.h
llvm::SplitBlock
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
Definition: BasicBlockUtils.cpp:837
Value.h
SplitLandingPadPredecessorsImpl
static void SplitLandingPadPredecessorsImpl(BasicBlock *OrigBB, ArrayRef< BasicBlock * > Preds, const char *Suffix1, const char *Suffix2, SmallVectorImpl< BasicBlock * > &NewBBs, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Definition: BasicBlockUtils.cpp:1192
llvm::BasicBlock::isEHPad
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:475
llvm::MCID::Terminator
@ Terminator
Definition: MCInstrDesc.h:157
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
reconnectPhis
static void reconnectPhis(BasicBlock *Out, BasicBlock *GuardBlock, const SetVector< BasicBlock * > &Incoming, BasicBlock *FirstGuardBlock)
Definition: BasicBlockUtils.cpp:1586
llvm::ArrayRef::end
iterator end() const
Definition: ArrayRef.h:153
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3213
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3227
llvm::DominatorTreeBase< BasicBlock, false >::Delete
static constexpr UpdateKind Delete
Definition: GenericDomTree.h:243
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
llvm::PoisonValue::get
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1727