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