LLVM  13.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  // Finally, erase the old block and update dominator info.
302  if (DTU) {
303  assert(BB->getInstList().size() == 1 &&
304  isa<UnreachableInst>(BB->getTerminator()) &&
305  "The successor list of BB isn't empty before "
306  "applying corresponding DTU updates.");
307  DTU->applyUpdates(Updates);
308  DTU->deleteBB(BB);
309  } else {
310  BB->eraseFromParent(); // Nuke BB if DTU is nullptr.
311  }
312 
313  return true;
314 }
315 
317  SmallPtrSetImpl<BasicBlock *> &MergeBlocks, Loop *L, DomTreeUpdater *DTU,
318  LoopInfo *LI) {
319  assert(!MergeBlocks.empty() && "MergeBlocks should not be empty");
320 
321  bool BlocksHaveBeenMerged = false;
322  while (!MergeBlocks.empty()) {
323  BasicBlock *BB = *MergeBlocks.begin();
324  BasicBlock *Dest = BB->getSingleSuccessor();
325  if (Dest && (!L || L->contains(Dest))) {
326  BasicBlock *Fold = Dest->getUniquePredecessor();
327  (void)Fold;
328  if (MergeBlockIntoPredecessor(Dest, DTU, LI)) {
329  assert(Fold == BB &&
330  "Expecting BB to be unique predecessor of the Dest block");
331  MergeBlocks.erase(Dest);
332  BlocksHaveBeenMerged = true;
333  } else
334  MergeBlocks.erase(BB);
335  } else
336  MergeBlocks.erase(BB);
337  }
338  return BlocksHaveBeenMerged;
339 }
340 
341 /// Remove redundant instructions within sequences of consecutive dbg.value
342 /// instructions. This is done using a backward scan to keep the last dbg.value
343 /// describing a specific variable/fragment.
344 ///
345 /// BackwardScan strategy:
346 /// ----------------------
347 /// Given a sequence of consecutive DbgValueInst like this
348 ///
349 /// dbg.value ..., "x", FragmentX1 (*)
350 /// dbg.value ..., "y", FragmentY1
351 /// dbg.value ..., "x", FragmentX2
352 /// dbg.value ..., "x", FragmentX1 (**)
353 ///
354 /// then the instruction marked with (*) can be removed (it is guaranteed to be
355 /// obsoleted by the instruction marked with (**) as the latter instruction is
356 /// describing the same variable using the same fragment info).
357 ///
358 /// Possible improvements:
359 /// - Check fully overlapping fragments and not only identical fragments.
360 /// - Support dbg.addr, dbg.declare. dbg.label, and possibly other meta
361 /// instructions being part of the sequence of consecutive instructions.
363  SmallVector<DbgValueInst *, 8> ToBeRemoved;
364  SmallDenseSet<DebugVariable> VariableSet;
365  for (auto &I : reverse(*BB)) {
366  if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(&I)) {
367  DebugVariable Key(DVI->getVariable(),
368  DVI->getExpression(),
369  DVI->getDebugLoc()->getInlinedAt());
370  auto R = VariableSet.insert(Key);
371  // If the same variable fragment is described more than once it is enough
372  // to keep the last one (i.e. the first found since we for reverse
373  // iteration).
374  if (!R.second)
375  ToBeRemoved.push_back(DVI);
376  continue;
377  }
378  // Sequence with consecutive dbg.value instrs ended. Clear the map to
379  // restart identifying redundant instructions if case we find another
380  // dbg.value sequence.
381  VariableSet.clear();
382  }
383 
384  for (auto &Instr : ToBeRemoved)
385  Instr->eraseFromParent();
386 
387  return !ToBeRemoved.empty();
388 }
389 
390 /// Remove redundant dbg.value instructions using a forward scan. This can
391 /// remove a dbg.value instruction that is redundant due to indicating that a
392 /// variable has the same value as already being indicated by an earlier
393 /// dbg.value.
394 ///
395 /// ForwardScan strategy:
396 /// ---------------------
397 /// Given two identical dbg.value instructions, separated by a block of
398 /// instructions that isn't describing the same variable, like this
399 ///
400 /// dbg.value X1, "x", FragmentX1 (**)
401 /// <block of instructions, none being "dbg.value ..., "x", ...">
402 /// dbg.value X1, "x", FragmentX1 (*)
403 ///
404 /// then the instruction marked with (*) can be removed. Variable "x" is already
405 /// described as being mapped to the SSA value X1.
406 ///
407 /// Possible improvements:
408 /// - Keep track of non-overlapping fragments.
410  SmallVector<DbgValueInst *, 8> ToBeRemoved;
412  VariableMap;
413  for (auto &I : *BB) {
414  if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(&I)) {
415  DebugVariable Key(DVI->getVariable(),
416  NoneType(),
417  DVI->getDebugLoc()->getInlinedAt());
418  auto VMI = VariableMap.find(Key);
419  // Update the map if we found a new value/expression describing the
420  // variable, or if the variable wasn't mapped already.
421  SmallVector<Value *, 4> Values(DVI->getValues());
422  if (VMI == VariableMap.end() || VMI->second.first != Values ||
423  VMI->second.second != DVI->getExpression()) {
424  VariableMap[Key] = {Values, DVI->getExpression()};
425  continue;
426  }
427  // Found an identical mapping. Remember the instruction for later removal.
428  ToBeRemoved.push_back(DVI);
429  }
430  }
431 
432  for (auto &Instr : ToBeRemoved)
433  Instr->eraseFromParent();
434 
435  return !ToBeRemoved.empty();
436 }
437 
438 bool llvm::RemoveRedundantDbgInstrs(BasicBlock *BB, bool RemovePseudoOp) {
439  bool MadeChanges = false;
440  // By using the "backward scan" strategy before the "forward scan" strategy we
441  // can remove both dbg.value (2) and (3) in a situation like this:
442  //
443  // (1) dbg.value V1, "x", DIExpression()
444  // ...
445  // (2) dbg.value V2, "x", DIExpression()
446  // (3) dbg.value V1, "x", DIExpression()
447  //
448  // The backward scan will remove (2), it is made obsolete by (3). After
449  // getting (2) out of the way, the foward scan will remove (3) since "x"
450  // already is described as having the value V1 at (1).
453  if (RemovePseudoOp)
454  MadeChanges |= removeRedundantPseudoProbes(BB);
455 
456  if (MadeChanges)
457  LLVM_DEBUG(dbgs() << "Removed redundant dbg instrs from: "
458  << BB->getName() << "\n");
459  return MadeChanges;
460 }
461 
463  BasicBlock::iterator &BI, Value *V) {
464  Instruction &I = *BI;
465  // Replaces all of the uses of the instruction with uses of the value
466  I.replaceAllUsesWith(V);
467 
468  // Make sure to propagate a name if there is one already.
469  if (I.hasName() && !V->hasName())
470  V->takeName(&I);
471 
472  // Delete the unnecessary instruction now...
473  BI = BIL.erase(BI);
474 }
475 
478  assert(I->getParent() == nullptr &&
479  "ReplaceInstWithInst: Instruction already inserted into basic block!");
480 
481  // Copy debug location to newly added instruction, if it wasn't already set
482  // by the caller.
483  if (!I->getDebugLoc())
484  I->setDebugLoc(BI->getDebugLoc());
485 
486  // Insert the new instruction into the basic block...
487  BasicBlock::iterator New = BIL.insert(BI, I);
488 
489  // Replace all uses of the old instruction, and delete it.
490  ReplaceInstWithValue(BIL, BI, I);
491 
492  // Move BI back to point to the newly inserted instruction
493  BI = New;
494 }
495 
498  ReplaceInstWithInst(From->getParent()->getInstList(), BI, To);
499 }
500 
502  LoopInfo *LI, MemorySSAUpdater *MSSAU,
503  const Twine &BBName) {
504  unsigned SuccNum = GetSuccessorNumber(BB, Succ);
505 
506  Instruction *LatchTerm = BB->getTerminator();
507 
510 
511  if ((isCriticalEdge(LatchTerm, SuccNum, Options.MergeIdenticalEdges))) {
512  // If it is a critical edge, and the succesor is an exception block, handle
513  // the split edge logic in this specific function
514  if (Succ->isEHPad())
515  return ehAwareSplitEdge(BB, Succ, nullptr, nullptr, Options, BBName);
516 
517  // If this is a critical edge, let SplitKnownCriticalEdge do it.
518  return SplitKnownCriticalEdge(LatchTerm, SuccNum, Options, BBName);
519  }
520 
521  // If the edge isn't critical, then BB has a single successor or Succ has a
522  // single pred. Split the block.
523  if (BasicBlock *SP = Succ->getSinglePredecessor()) {
524  // If the successor only has a single pred, split the top of the successor
525  // block.
526  assert(SP == BB && "CFG broken");
527  SP = nullptr;
528  return SplitBlock(Succ, &Succ->front(), DT, LI, MSSAU, BBName,
529  /*Before=*/true);
530  }
531 
532  // Otherwise, if BB has a single successor, split it at the bottom of the
533  // block.
534  assert(BB->getTerminator()->getNumSuccessors() == 1 &&
535  "Should have a single succ!");
536  return SplitBlock(BB, BB->getTerminator(), DT, LI, MSSAU, BBName);
537 }
538 
540  if (auto *II = dyn_cast<InvokeInst>(TI))
541  II->setUnwindDest(Succ);
542  else if (auto *CS = dyn_cast<CatchSwitchInst>(TI))
543  CS->setUnwindDest(Succ);
544  else if (auto *CR = dyn_cast<CleanupReturnInst>(TI))
545  CR->setUnwindDest(Succ);
546  else
547  llvm_unreachable("unexpected terminator instruction");
548 }
549 
551  BasicBlock *NewPred, PHINode *Until) {
552  int BBIdx = 0;
553  for (PHINode &PN : DestBB->phis()) {
554  // We manually update the LandingPadReplacement PHINode and it is the last
555  // PHI Node. So, if we find it, we are done.
556  if (Until == &PN)
557  break;
558 
559  // Reuse the previous value of BBIdx if it lines up. In cases where we
560  // have multiple phi nodes with *lots* of predecessors, this is a speed
561  // win because we don't have to scan the PHI looking for TIBB. This
562  // happens because the BB list of PHI nodes are usually in the same
563  // order.
564  if (PN.getIncomingBlock(BBIdx) != OldPred)
565  BBIdx = PN.getBasicBlockIndex(OldPred);
566 
567  assert(BBIdx != -1 && "Invalid PHI Index!");
568  PN.setIncomingBlock(BBIdx, NewPred);
569  }
570 }
571 
573  LandingPadInst *OriginalPad,
574  PHINode *LandingPadReplacement,
575  const CriticalEdgeSplittingOptions &Options,
576  const Twine &BBName) {
577 
578  auto *PadInst = Succ->getFirstNonPHI();
579  if (!LandingPadReplacement && !PadInst->isEHPad())
580  return SplitEdge(BB, Succ, Options.DT, Options.LI, Options.MSSAU, BBName);
581 
582  auto *LI = Options.LI;
584  // Check if extra modifications will be required to preserve loop-simplify
585  // form after splitting. If it would require splitting blocks with IndirectBr
586  // terminators, bail out if preserving loop-simplify form is requested.
587  if (Options.PreserveLoopSimplify && LI) {
588  if (Loop *BBLoop = LI->getLoopFor(BB)) {
589 
590  // The only way that we can break LoopSimplify form by splitting a
591  // critical edge is when there exists some edge from BBLoop to Succ *and*
592  // the only edge into Succ from outside of BBLoop is that of NewBB after
593  // the split. If the first isn't true, then LoopSimplify still holds,
594  // NewBB is the new exit block and it has no non-loop predecessors. If the
595  // second isn't true, then Succ was not in LoopSimplify form prior to
596  // the split as it had a non-loop predecessor. In both of these cases,
597  // the predecessor must be directly in BBLoop, not in a subloop, or again
598  // LoopSimplify doesn't hold.
599  for (BasicBlock *P : predecessors(Succ)) {
600  if (P == BB)
601  continue; // The new block is known.
602  if (LI->getLoopFor(P) != BBLoop) {
603  // Loop is not in LoopSimplify form, no need to re simplify after
604  // splitting edge.
605  LoopPreds.clear();
606  break;
607  }
608  LoopPreds.push_back(P);
609  }
610  // Loop-simplify form can be preserved, if we can split all in-loop
611  // predecessors.
612  if (any_of(LoopPreds, [](BasicBlock *Pred) {
613  return isa<IndirectBrInst>(Pred->getTerminator());
614  })) {
615  return nullptr;
616  }
617  }
618  }
619 
620  auto *NewBB =
621  BasicBlock::Create(BB->getContext(), BBName, BB->getParent(), Succ);
622  setUnwindEdgeTo(BB->getTerminator(), NewBB);
623  updatePhiNodes(Succ, BB, NewBB, LandingPadReplacement);
624 
625  if (LandingPadReplacement) {
626  auto *NewLP = OriginalPad->clone();
627  auto *Terminator = BranchInst::Create(Succ, NewBB);
628  NewLP->insertBefore(Terminator);
629  LandingPadReplacement->addIncoming(NewLP, NewBB);
630  } else {
631  Value *ParentPad = nullptr;
632  if (auto *FuncletPad = dyn_cast<FuncletPadInst>(PadInst))
633  ParentPad = FuncletPad->getParentPad();
634  else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(PadInst))
635  ParentPad = CatchSwitch->getParentPad();
636  else if (auto *CleanupPad = dyn_cast<CleanupPadInst>(PadInst))
637  ParentPad = CleanupPad->getParentPad();
638  else if (auto *LandingPad = dyn_cast<LandingPadInst>(PadInst))
639  ParentPad = LandingPad->getParent();
640  else
641  llvm_unreachable("handling for other EHPads not implemented yet");
642 
643  auto *NewCleanupPad = CleanupPadInst::Create(ParentPad, {}, BBName, NewBB);
644  CleanupReturnInst::Create(NewCleanupPad, Succ, NewBB);
645  }
646 
647  auto *DT = Options.DT;
648  auto *MSSAU = Options.MSSAU;
649  if (!DT && !LI)
650  return NewBB;
651 
652  if (DT) {
655 
656  Updates.push_back({DominatorTree::Insert, BB, NewBB});
657  Updates.push_back({DominatorTree::Insert, NewBB, Succ});
658  Updates.push_back({DominatorTree::Delete, BB, Succ});
659 
660  DTU.applyUpdates(Updates);
661  DTU.flush();
662 
663  if (MSSAU) {
664  MSSAU->applyUpdates(Updates, *DT);
665  if (VerifyMemorySSA)
666  MSSAU->getMemorySSA()->verifyMemorySSA();
667  }
668  }
669 
670  if (LI) {
671  if (Loop *BBLoop = LI->getLoopFor(BB)) {
672  // If one or the other blocks were not in a loop, the new block is not
673  // either, and thus LI doesn't need to be updated.
674  if (Loop *SuccLoop = LI->getLoopFor(Succ)) {
675  if (BBLoop == SuccLoop) {
676  // Both in the same loop, the NewBB joins loop.
677  SuccLoop->addBasicBlockToLoop(NewBB, *LI);
678  } else if (BBLoop->contains(SuccLoop)) {
679  // Edge from an outer loop to an inner loop. Add to the outer loop.
680  BBLoop->addBasicBlockToLoop(NewBB, *LI);
681  } else if (SuccLoop->contains(BBLoop)) {
682  // Edge from an inner loop to an outer loop. Add to the outer loop.
683  SuccLoop->addBasicBlockToLoop(NewBB, *LI);
684  } else {
685  // Edge from two loops with no containment relation. Because these
686  // are natural loops, we know that the destination block must be the
687  // header of its loop (adding a branch into a loop elsewhere would
688  // create an irreducible loop).
689  assert(SuccLoop->getHeader() == Succ &&
690  "Should not create irreducible loops!");
691  if (Loop *P = SuccLoop->getParentLoop())
692  P->addBasicBlockToLoop(NewBB, *LI);
693  }
694  }
695 
696  // If BB is in a loop and Succ is outside of that loop, we may need to
697  // update LoopSimplify form and LCSSA form.
698  if (!BBLoop->contains(Succ)) {
699  assert(!BBLoop->contains(NewBB) &&
700  "Split point for loop exit is contained in loop!");
701 
702  // Update LCSSA form in the newly created exit block.
703  if (Options.PreserveLCSSA) {
704  createPHIsForSplitLoopExit(BB, NewBB, Succ);
705  }
706 
707  if (!LoopPreds.empty()) {
708  BasicBlock *NewExitBB = SplitBlockPredecessors(
709  Succ, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA);
710  if (Options.PreserveLCSSA)
711  createPHIsForSplitLoopExit(LoopPreds, NewExitBB, Succ);
712  }
713  }
714  }
715  }
716 
717  return NewBB;
718 }
719 
721  BasicBlock *SplitBB, BasicBlock *DestBB) {
722  // SplitBB shouldn't have anything non-trivial in it yet.
723  assert((SplitBB->getFirstNonPHI() == SplitBB->getTerminator() ||
724  SplitBB->isLandingPad()) &&
725  "SplitBB has non-PHI nodes!");
726 
727  // For each PHI in the destination block.
728  for (PHINode &PN : DestBB->phis()) {
729  int Idx = PN.getBasicBlockIndex(SplitBB);
730  assert(Idx >= 0 && "Invalid Block Index");
731  Value *V = PN.getIncomingValue(Idx);
732 
733  // If the input is a PHI which already satisfies LCSSA, don't create
734  // a new one.
735  if (const PHINode *VP = dyn_cast<PHINode>(V))
736  if (VP->getParent() == SplitBB)
737  continue;
738 
739  // Otherwise a new PHI is needed. Create one and populate it.
740  PHINode *NewPN = PHINode::Create(
741  PN.getType(), Preds.size(), "split",
742  SplitBB->isLandingPad() ? &SplitBB->front() : SplitBB->getTerminator());
743  for (BasicBlock *BB : Preds)
744  NewPN->addIncoming(V, BB);
745 
746  // Update the original PHI.
747  PN.setIncomingValue(Idx, NewPN);
748  }
749 }
750 
751 unsigned
753  const CriticalEdgeSplittingOptions &Options) {
754  unsigned NumBroken = 0;
755  for (BasicBlock &BB : F) {
756  Instruction *TI = BB.getTerminator();
757  if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI) &&
758  !isa<CallBrInst>(TI))
759  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
760  if (SplitCriticalEdge(TI, i, Options))
761  ++NumBroken;
762  }
763  return NumBroken;
764 }
765 
767  DomTreeUpdater *DTU, DominatorTree *DT,
768  LoopInfo *LI, MemorySSAUpdater *MSSAU,
769  const Twine &BBName, bool Before) {
770  if (Before) {
772  return splitBlockBefore(Old, SplitPt,
773  DTU ? DTU : (DT ? &LocalDTU : nullptr), LI, MSSAU,
774  BBName);
775  }
776  BasicBlock::iterator SplitIt = SplitPt->getIterator();
777  while (isa<PHINode>(SplitIt) || SplitIt->isEHPad())
778  ++SplitIt;
779  std::string Name = BBName.str();
780  BasicBlock *New = Old->splitBasicBlock(
781  SplitIt, Name.empty() ? Old->getName() + ".split" : Name);
782 
783  // The new block lives in whichever loop the old one did. This preserves
784  // LCSSA as well, because we force the split point to be after any PHI nodes.
785  if (LI)
786  if (Loop *L = LI->getLoopFor(Old))
787  L->addBasicBlockToLoop(New, *LI);
788 
789  if (DTU) {
791  // Old dominates New. New node dominates all other nodes dominated by Old.
792  SmallPtrSet<BasicBlock *, 8> UniqueSuccessorsOfOld(succ_begin(New),
793  succ_end(New));
794  Updates.push_back({DominatorTree::Insert, Old, New});
795  Updates.reserve(Updates.size() + 2 * UniqueSuccessorsOfOld.size());
796  for (BasicBlock *UniqueSuccessorOfOld : UniqueSuccessorsOfOld) {
797  Updates.push_back({DominatorTree::Insert, New, UniqueSuccessorOfOld});
798  Updates.push_back({DominatorTree::Delete, Old, UniqueSuccessorOfOld});
799  }
800 
801  DTU->applyUpdates(Updates);
802  } else if (DT)
803  // Old dominates New. New node dominates all other nodes dominated by Old.
804  if (DomTreeNode *OldNode = DT->getNode(Old)) {
805  std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
806 
807  DomTreeNode *NewNode = DT->addNewBlock(New, Old);
808  for (DomTreeNode *I : Children)
809  DT->changeImmediateDominator(I, NewNode);
810  }
811 
812  // Move MemoryAccesses still tracked in Old, but part of New now.
813  // Update accesses in successor blocks accordingly.
814  if (MSSAU)
815  MSSAU->moveAllAfterSpliceBlocks(Old, New, &*(New->begin()));
816 
817  return New;
818 }
819 
821  DominatorTree *DT, LoopInfo *LI,
822  MemorySSAUpdater *MSSAU, const Twine &BBName,
823  bool Before) {
824  return SplitBlockImpl(Old, SplitPt, /*DTU=*/nullptr, DT, LI, MSSAU, BBName,
825  Before);
826 }
828  DomTreeUpdater *DTU, LoopInfo *LI,
829  MemorySSAUpdater *MSSAU, const Twine &BBName,
830  bool Before) {
831  return SplitBlockImpl(Old, SplitPt, DTU, /*DT=*/nullptr, LI, MSSAU, BBName,
832  Before);
833 }
834 
836  DomTreeUpdater *DTU, LoopInfo *LI,
837  MemorySSAUpdater *MSSAU,
838  const Twine &BBName) {
839 
840  BasicBlock::iterator SplitIt = SplitPt->getIterator();
841  while (isa<PHINode>(SplitIt) || SplitIt->isEHPad())
842  ++SplitIt;
843  std::string Name = BBName.str();
844  BasicBlock *New = Old->splitBasicBlock(
845  SplitIt, Name.empty() ? Old->getName() + ".split" : Name,
846  /* Before=*/true);
847 
848  // The new block lives in whichever loop the old one did. This preserves
849  // LCSSA as well, because we force the split point to be after any PHI nodes.
850  if (LI)
851  if (Loop *L = LI->getLoopFor(Old))
852  L->addBasicBlockToLoop(New, *LI);
853 
854  if (DTU) {
856  // New dominates Old. The predecessor nodes of the Old node dominate
857  // New node.
858  SmallPtrSet<BasicBlock *, 8> UniquePredecessorsOfOld(pred_begin(New),
859  pred_end(New));
860  DTUpdates.push_back({DominatorTree::Insert, New, Old});
861  DTUpdates.reserve(DTUpdates.size() + 2 * UniquePredecessorsOfOld.size());
862  for (BasicBlock *UniquePredecessorOfOld : UniquePredecessorsOfOld) {
863  DTUpdates.push_back({DominatorTree::Insert, UniquePredecessorOfOld, New});
864  DTUpdates.push_back({DominatorTree::Delete, UniquePredecessorOfOld, Old});
865  }
866 
867  DTU->applyUpdates(DTUpdates);
868 
869  // Move MemoryAccesses still tracked in Old, but part of New now.
870  // Update accesses in successor blocks accordingly.
871  if (MSSAU) {
872  MSSAU->applyUpdates(DTUpdates, DTU->getDomTree());
873  if (VerifyMemorySSA)
874  MSSAU->getMemorySSA()->verifyMemorySSA();
875  }
876  }
877  return New;
878 }
879 
880 /// Update DominatorTree, LoopInfo, and LCCSA analysis information.
883  DomTreeUpdater *DTU, DominatorTree *DT,
884  LoopInfo *LI, MemorySSAUpdater *MSSAU,
885  bool PreserveLCSSA, bool &HasLoopExit) {
886  // Update dominator tree if available.
887  if (DTU) {
888  // Recalculation of DomTree is needed when updating a forward DomTree and
889  // the Entry BB is replaced.
890  if (NewBB == &NewBB->getParent()->getEntryBlock() && DTU->hasDomTree()) {
891  // The entry block was removed and there is no external interface for
892  // the dominator tree to be notified of this change. In this corner-case
893  // we recalculate the entire tree.
894  DTU->recalculate(*NewBB->getParent());
895  } else {
896  // Split block expects NewBB to have a non-empty set of predecessors.
898  SmallPtrSet<BasicBlock *, 8> UniquePreds(Preds.begin(), Preds.end());
899  Updates.push_back({DominatorTree::Insert, NewBB, OldBB});
900  Updates.reserve(Updates.size() + 2 * UniquePreds.size());
901  for (auto *UniquePred : UniquePreds) {
902  Updates.push_back({DominatorTree::Insert, UniquePred, NewBB});
903  Updates.push_back({DominatorTree::Delete, UniquePred, OldBB});
904  }
905  DTU->applyUpdates(Updates);
906  }
907  } else if (DT) {
908  if (OldBB == DT->getRootNode()->getBlock()) {
909  assert(NewBB == &NewBB->getParent()->getEntryBlock());
910  DT->setNewRoot(NewBB);
911  } else {
912  // Split block expects NewBB to have a non-empty set of predecessors.
913  DT->splitBlock(NewBB);
914  }
915  }
916 
917  // Update MemoryPhis after split if MemorySSA is available
918  if (MSSAU)
919  MSSAU->wireOldPredecessorsToNewImmediatePredecessor(OldBB, NewBB, Preds);
920 
921  // The rest of the logic is only relevant for updating the loop structures.
922  if (!LI)
923  return;
924 
925  if (DTU && DTU->hasDomTree())
926  DT = &DTU->getDomTree();
927  assert(DT && "DT should be available to update LoopInfo!");
928  Loop *L = LI->getLoopFor(OldBB);
929 
930  // If we need to preserve loop analyses, collect some information about how
931  // this split will affect loops.
932  bool IsLoopEntry = !!L;
933  bool SplitMakesNewLoopHeader = false;
934  for (BasicBlock *Pred : Preds) {
935  // Preds that are not reachable from entry should not be used to identify if
936  // OldBB is a loop entry or if SplitMakesNewLoopHeader. Unreachable blocks
937  // are not within any loops, so we incorrectly mark SplitMakesNewLoopHeader
938  // as true and make the NewBB the header of some loop. This breaks LI.
939  if (!DT->isReachableFromEntry(Pred))
940  continue;
941  // If we need to preserve LCSSA, determine if any of the preds is a loop
942  // exit.
943  if (PreserveLCSSA)
944  if (Loop *PL = LI->getLoopFor(Pred))
945  if (!PL->contains(OldBB))
946  HasLoopExit = true;
947 
948  // If we need to preserve LoopInfo, note whether any of the preds crosses
949  // an interesting loop boundary.
950  if (!L)
951  continue;
952  if (L->contains(Pred))
953  IsLoopEntry = false;
954  else
955  SplitMakesNewLoopHeader = true;
956  }
957 
958  // Unless we have a loop for OldBB, nothing else to do here.
959  if (!L)
960  return;
961 
962  if (IsLoopEntry) {
963  // Add the new block to the nearest enclosing loop (and not an adjacent
964  // loop). To find this, examine each of the predecessors and determine which
965  // loops enclose them, and select the most-nested loop which contains the
966  // loop containing the block being split.
967  Loop *InnermostPredLoop = nullptr;
968  for (BasicBlock *Pred : Preds) {
969  if (Loop *PredLoop = LI->getLoopFor(Pred)) {
970  // Seek a loop which actually contains the block being split (to avoid
971  // adjacent loops).
972  while (PredLoop && !PredLoop->contains(OldBB))
973  PredLoop = PredLoop->getParentLoop();
974 
975  // Select the most-nested of these loops which contains the block.
976  if (PredLoop && PredLoop->contains(OldBB) &&
977  (!InnermostPredLoop ||
978  InnermostPredLoop->getLoopDepth() < PredLoop->getLoopDepth()))
979  InnermostPredLoop = PredLoop;
980  }
981  }
982 
983  if (InnermostPredLoop)
984  InnermostPredLoop->addBasicBlockToLoop(NewBB, *LI);
985  } else {
986  L->addBasicBlockToLoop(NewBB, *LI);
987  if (SplitMakesNewLoopHeader)
988  L->moveToHeader(NewBB);
989  }
990 }
991 
992 /// Update the PHI nodes in OrigBB to include the values coming from NewBB.
993 /// This also updates AliasAnalysis, if available.
994 static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB,
996  bool HasLoopExit) {
997  // Otherwise, create a new PHI node in NewBB for each PHI node in OrigBB.
998  SmallPtrSet<BasicBlock *, 16> PredSet(Preds.begin(), Preds.end());
999  for (BasicBlock::iterator I = OrigBB->begin(); isa<PHINode>(I); ) {
1000  PHINode *PN = cast<PHINode>(I++);
1001 
1002  // Check to see if all of the values coming in are the same. If so, we
1003  // don't need to create a new PHI node, unless it's needed for LCSSA.
1004  Value *InVal = nullptr;
1005  if (!HasLoopExit) {
1006  InVal = PN->getIncomingValueForBlock(Preds[0]);
1007  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1008  if (!PredSet.count(PN->getIncomingBlock(i)))
1009  continue;
1010  if (!InVal)
1011  InVal = PN->getIncomingValue(i);
1012  else if (InVal != PN->getIncomingValue(i)) {
1013  InVal = nullptr;
1014  break;
1015  }
1016  }
1017  }
1018 
1019  if (InVal) {
1020  // If all incoming values for the new PHI would be the same, just don't
1021  // make a new PHI. Instead, just remove the incoming values from the old
1022  // PHI.
1023 
1024  // NOTE! This loop walks backwards for a reason! First off, this minimizes
1025  // the cost of removal if we end up removing a large number of values, and
1026  // second off, this ensures that the indices for the incoming values
1027  // aren't invalidated when we remove one.
1028  for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i)
1029  if (PredSet.count(PN->getIncomingBlock(i)))
1030  PN->removeIncomingValue(i, false);
1031 
1032  // Add an incoming value to the PHI node in the loop for the preheader
1033  // edge.
1034  PN->addIncoming(InVal, NewBB);
1035  continue;
1036  }
1037 
1038  // If the values coming into the block are not the same, we need a new
1039  // PHI.
1040  // Create the new PHI node, insert it into NewBB at the end of the block
1041  PHINode *NewPHI =
1042  PHINode::Create(PN->getType(), Preds.size(), PN->getName() + ".ph", BI);
1043 
1044  // NOTE! This loop walks backwards for a reason! First off, this minimizes
1045  // the cost of removal if we end up removing a large number of values, and
1046  // second off, this ensures that the indices for the incoming values aren't
1047  // invalidated when we remove one.
1048  for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) {
1049  BasicBlock *IncomingBB = PN->getIncomingBlock(i);
1050  if (PredSet.count(IncomingBB)) {
1051  Value *V = PN->removeIncomingValue(i, false);
1052  NewPHI->addIncoming(V, IncomingBB);
1053  }
1054  }
1055 
1056  PN->addIncoming(NewPHI, NewBB);
1057  }
1058 }
1059 
1061  BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix1,
1062  const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs,
1063  DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI,
1064  MemorySSAUpdater *MSSAU, bool PreserveLCSSA);
1065 
1066 static BasicBlock *
1068  const char *Suffix, DomTreeUpdater *DTU,
1069  DominatorTree *DT, LoopInfo *LI,
1070  MemorySSAUpdater *MSSAU, bool PreserveLCSSA) {
1071  // Do not attempt to split that which cannot be split.
1072  if (!BB->canSplitPredecessors())
1073  return nullptr;
1074 
1075  // For the landingpads we need to act a bit differently.
1076  // Delegate this work to the SplitLandingPadPredecessors.
1077  if (BB->isLandingPad()) {
1079  std::string NewName = std::string(Suffix) + ".split-lp";
1080 
1081  SplitLandingPadPredecessorsImpl(BB, Preds, Suffix, NewName.c_str(), NewBBs,
1082  DTU, DT, LI, MSSAU, PreserveLCSSA);
1083  return NewBBs[0];
1084  }
1085 
1086  // Create new basic block, insert right before the original block.
1087  BasicBlock *NewBB = BasicBlock::Create(
1088  BB->getContext(), BB->getName() + Suffix, BB->getParent(), BB);
1089 
1090  // The new block unconditionally branches to the old block.
1091  BranchInst *BI = BranchInst::Create(BB, NewBB);
1092 
1093  Loop *L = nullptr;
1094  BasicBlock *OldLatch = nullptr;
1095  // Splitting the predecessors of a loop header creates a preheader block.
1096  if (LI && LI->isLoopHeader(BB)) {
1097  L = LI->getLoopFor(BB);
1098  // Using the loop start line number prevents debuggers stepping into the
1099  // loop body for this instruction.
1100  BI->setDebugLoc(L->getStartLoc());
1101 
1102  // If BB is the header of the Loop, it is possible that the loop is
1103  // modified, such that the current latch does not remain the latch of the
1104  // loop. If that is the case, the loop metadata from the current latch needs
1105  // to be applied to the new latch.
1106  OldLatch = L->getLoopLatch();
1107  } else
1108  BI->setDebugLoc(BB->getFirstNonPHIOrDbg()->getDebugLoc());
1109 
1110  // Move the edges from Preds to point to NewBB instead of BB.
1111  for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
1112  // This is slightly more strict than necessary; the minimum requirement
1113  // is that there be no more than one indirectbr branching to BB. And
1114  // all BlockAddress uses would need to be updated.
1115  assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&
1116  "Cannot split an edge from an IndirectBrInst");
1117  assert(!isa<CallBrInst>(Preds[i]->getTerminator()) &&
1118  "Cannot split an edge from a CallBrInst");
1119  Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB);
1120  }
1121 
1122  // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI
1123  // node becomes an incoming value for BB's phi node. However, if the Preds
1124  // list is empty, we need to insert dummy entries into the PHI nodes in BB to
1125  // account for the newly created predecessor.
1126  if (Preds.empty()) {
1127  // Insert dummy values as the incoming value.
1128  for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I)
1129  cast<PHINode>(I)->addIncoming(UndefValue::get(I->getType()), NewBB);
1130  }
1131 
1132  // Update DominatorTree, LoopInfo, and LCCSA analysis information.
1133  bool HasLoopExit = false;
1134  UpdateAnalysisInformation(BB, NewBB, Preds, DTU, DT, LI, MSSAU, PreserveLCSSA,
1135  HasLoopExit);
1136 
1137  if (!Preds.empty()) {
1138  // Update the PHI nodes in BB with the values coming from NewBB.
1139  UpdatePHINodes(BB, NewBB, Preds, BI, HasLoopExit);
1140  }
1141 
1142  if (OldLatch) {
1143  BasicBlock *NewLatch = L->getLoopLatch();
1144  if (NewLatch != OldLatch) {
1145  MDNode *MD = OldLatch->getTerminator()->getMetadata("llvm.loop");
1146  NewLatch->getTerminator()->setMetadata("llvm.loop", MD);
1147  OldLatch->getTerminator()->setMetadata("llvm.loop", nullptr);
1148  }
1149  }
1150 
1151  return NewBB;
1152 }
1153 
1155  ArrayRef<BasicBlock *> Preds,
1156  const char *Suffix, DominatorTree *DT,
1157  LoopInfo *LI, MemorySSAUpdater *MSSAU,
1158  bool PreserveLCSSA) {
1159  return SplitBlockPredecessorsImpl(BB, Preds, Suffix, /*DTU=*/nullptr, DT, LI,
1160  MSSAU, PreserveLCSSA);
1161 }
1163  ArrayRef<BasicBlock *> Preds,
1164  const char *Suffix,
1165  DomTreeUpdater *DTU, LoopInfo *LI,
1166  MemorySSAUpdater *MSSAU,
1167  bool PreserveLCSSA) {
1168  return SplitBlockPredecessorsImpl(BB, Preds, Suffix, DTU,
1169  /*DT=*/nullptr, LI, MSSAU, PreserveLCSSA);
1170 }
1171 
1173  BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix1,
1174  const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs,
1175  DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI,
1176  MemorySSAUpdater *MSSAU, bool PreserveLCSSA) {
1177  assert(OrigBB->isLandingPad() && "Trying to split a non-landing pad!");
1178 
1179  // Create a new basic block for OrigBB's predecessors listed in Preds. Insert
1180  // it right before the original block.
1181  BasicBlock *NewBB1 = BasicBlock::Create(OrigBB->getContext(),
1182  OrigBB->getName() + Suffix1,
1183  OrigBB->getParent(), OrigBB);
1184  NewBBs.push_back(NewBB1);
1185 
1186  // The new block unconditionally branches to the old block.
1187  BranchInst *BI1 = BranchInst::Create(OrigBB, NewBB1);
1188  BI1->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc());
1189 
1190  // Move the edges from Preds to point to NewBB1 instead of OrigBB.
1191  for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
1192  // This is slightly more strict than necessary; the minimum requirement
1193  // is that there be no more than one indirectbr branching to BB. And
1194  // all BlockAddress uses would need to be updated.
1195  assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&
1196  "Cannot split an edge from an IndirectBrInst");
1197  Preds[i]->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1);
1198  }
1199 
1200  bool HasLoopExit = false;
1201  UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DTU, DT, LI, MSSAU,
1202  PreserveLCSSA, HasLoopExit);
1203 
1204  // Update the PHI nodes in OrigBB with the values coming from NewBB1.
1205  UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, HasLoopExit);
1206 
1207  // Move the remaining edges from OrigBB to point to NewBB2.
1208  SmallVector<BasicBlock*, 8> NewBB2Preds;
1209  for (pred_iterator i = pred_begin(OrigBB), e = pred_end(OrigBB);
1210  i != e; ) {
1211  BasicBlock *Pred = *i++;
1212  if (Pred == NewBB1) continue;
1213  assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
1214  "Cannot split an edge from an IndirectBrInst");
1215  NewBB2Preds.push_back(Pred);
1216  e = pred_end(OrigBB);
1217  }
1218 
1219  BasicBlock *NewBB2 = nullptr;
1220  if (!NewBB2Preds.empty()) {
1221  // Create another basic block for the rest of OrigBB's predecessors.
1222  NewBB2 = BasicBlock::Create(OrigBB->getContext(),
1223  OrigBB->getName() + Suffix2,
1224  OrigBB->getParent(), OrigBB);
1225  NewBBs.push_back(NewBB2);
1226 
1227  // The new block unconditionally branches to the old block.
1228  BranchInst *BI2 = BranchInst::Create(OrigBB, NewBB2);
1229  BI2->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc());
1230 
1231  // Move the remaining edges from OrigBB to point to NewBB2.
1232  for (BasicBlock *NewBB2Pred : NewBB2Preds)
1233  NewBB2Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2);
1234 
1235  // Update DominatorTree, LoopInfo, and LCCSA analysis information.
1236  HasLoopExit = false;
1237  UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DTU, DT, LI, MSSAU,
1238  PreserveLCSSA, HasLoopExit);
1239 
1240  // Update the PHI nodes in OrigBB with the values coming from NewBB2.
1241  UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, HasLoopExit);
1242  }
1243 
1244  LandingPadInst *LPad = OrigBB->getLandingPadInst();
1245  Instruction *Clone1 = LPad->clone();
1246  Clone1->setName(Twine("lpad") + Suffix1);
1247  NewBB1->getInstList().insert(NewBB1->getFirstInsertionPt(), Clone1);
1248 
1249  if (NewBB2) {
1250  Instruction *Clone2 = LPad->clone();
1251  Clone2->setName(Twine("lpad") + Suffix2);
1252  NewBB2->getInstList().insert(NewBB2->getFirstInsertionPt(), Clone2);
1253 
1254  // Create a PHI node for the two cloned landingpad instructions only
1255  // if the original landingpad instruction has some uses.
1256  if (!LPad->use_empty()) {
1257  assert(!LPad->getType()->isTokenTy() &&
1258  "Split cannot be applied if LPad is token type. Otherwise an "
1259  "invalid PHINode of token type would be created.");
1260  PHINode *PN = PHINode::Create(LPad->getType(), 2, "lpad.phi", LPad);
1261  PN->addIncoming(Clone1, NewBB1);
1262  PN->addIncoming(Clone2, NewBB2);
1263  LPad->replaceAllUsesWith(PN);
1264  }
1265  LPad->eraseFromParent();
1266  } else {
1267  // There is no second clone. Just replace the landing pad with the first
1268  // clone.
1269  LPad->replaceAllUsesWith(Clone1);
1270  LPad->eraseFromParent();
1271  }
1272 }
1273 
1275  ArrayRef<BasicBlock *> Preds,
1276  const char *Suffix1, const char *Suffix2,
1278  DominatorTree *DT, LoopInfo *LI,
1279  MemorySSAUpdater *MSSAU,
1280  bool PreserveLCSSA) {
1282  OrigBB, Preds, Suffix1, Suffix2, NewBBs,
1283  /*DTU=*/nullptr, DT, LI, MSSAU, PreserveLCSSA);
1284 }
1286  ArrayRef<BasicBlock *> Preds,
1287  const char *Suffix1, const char *Suffix2,
1289  DomTreeUpdater *DTU, LoopInfo *LI,
1290  MemorySSAUpdater *MSSAU,
1291  bool PreserveLCSSA) {
1292  return SplitLandingPadPredecessorsImpl(OrigBB, Preds, Suffix1, Suffix2,
1293  NewBBs, DTU, /*DT=*/nullptr, LI, MSSAU,
1294  PreserveLCSSA);
1295 }
1296 
1298  BasicBlock *Pred,
1299  DomTreeUpdater *DTU) {
1300  Instruction *UncondBranch = Pred->getTerminator();
1301  // Clone the return and add it to the end of the predecessor.
1302  Instruction *NewRet = RI->clone();
1303  Pred->getInstList().push_back(NewRet);
1304 
1305  // If the return instruction returns a value, and if the value was a
1306  // PHI node in "BB", propagate the right value into the return.
1307  for (Use &Op : NewRet->operands()) {
1308  Value *V = Op;
1309  Instruction *NewBC = nullptr;
1310  if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) {
1311  // Return value might be bitcasted. Clone and insert it before the
1312  // return instruction.
1313  V = BCI->getOperand(0);
1314  NewBC = BCI->clone();
1315  Pred->getInstList().insert(NewRet->getIterator(), NewBC);
1316  Op = NewBC;
1317  }
1318 
1319  Instruction *NewEV = nullptr;
1320  if (ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(V)) {
1321  V = EVI->getOperand(0);
1322  NewEV = EVI->clone();
1323  if (NewBC) {
1324  NewBC->setOperand(0, NewEV);
1325  Pred->getInstList().insert(NewBC->getIterator(), NewEV);
1326  } else {
1327  Pred->getInstList().insert(NewRet->getIterator(), NewEV);
1328  Op = NewEV;
1329  }
1330  }
1331 
1332  if (PHINode *PN = dyn_cast<PHINode>(V)) {
1333  if (PN->getParent() == BB) {
1334  if (NewEV) {
1335  NewEV->setOperand(0, PN->getIncomingValueForBlock(Pred));
1336  } else if (NewBC)
1337  NewBC->setOperand(0, PN->getIncomingValueForBlock(Pred));
1338  else
1339  Op = PN->getIncomingValueForBlock(Pred);
1340  }
1341  }
1342  }
1343 
1344  // Update any PHI nodes in the returning block to realize that we no
1345  // longer branch to them.
1346  BB->removePredecessor(Pred);
1347  UncondBranch->eraseFromParent();
1348 
1349  if (DTU)
1350  DTU->applyUpdates({{DominatorTree::Delete, Pred, BB}});
1351 
1352  return cast<ReturnInst>(NewRet);
1353 }
1354 
1355 static Instruction *
1357  bool Unreachable, MDNode *BranchWeights,
1358  DomTreeUpdater *DTU, DominatorTree *DT,
1359  LoopInfo *LI, BasicBlock *ThenBlock) {
1361  BasicBlock *Head = SplitBefore->getParent();
1362  BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator());
1363  if (DTU) {
1364  SmallPtrSet<BasicBlock *, 8> UniqueSuccessorsOfHead(succ_begin(Tail),
1365  succ_end(Tail));
1366  Updates.push_back({DominatorTree::Insert, Head, Tail});
1367  Updates.reserve(Updates.size() + 2 * UniqueSuccessorsOfHead.size());
1368  for (BasicBlock *UniqueSuccessorOfHead : UniqueSuccessorsOfHead) {
1369  Updates.push_back({DominatorTree::Insert, Tail, UniqueSuccessorOfHead});
1370  Updates.push_back({DominatorTree::Delete, Head, UniqueSuccessorOfHead});
1371  }
1372  }
1373  Instruction *HeadOldTerm = Head->getTerminator();
1374  LLVMContext &C = Head->getContext();
1375  Instruction *CheckTerm;
1376  bool CreateThenBlock = (ThenBlock == nullptr);
1377  if (CreateThenBlock) {
1378  ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
1379  if (Unreachable)
1380  CheckTerm = new UnreachableInst(C, ThenBlock);
1381  else {
1382  CheckTerm = BranchInst::Create(Tail, ThenBlock);
1383  if (DTU)
1384  Updates.push_back({DominatorTree::Insert, ThenBlock, Tail});
1385  }
1386  CheckTerm->setDebugLoc(SplitBefore->getDebugLoc());
1387  } else
1388  CheckTerm = ThenBlock->getTerminator();
1389  BranchInst *HeadNewTerm =
1390  BranchInst::Create(/*ifTrue*/ ThenBlock, /*ifFalse*/ Tail, Cond);
1391  if (DTU)
1392  Updates.push_back({DominatorTree::Insert, Head, ThenBlock});
1393  HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
1394  ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
1395 
1396  if (DTU)
1397  DTU->applyUpdates(Updates);
1398  else if (DT) {
1399  if (DomTreeNode *OldNode = DT->getNode(Head)) {
1400  std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
1401 
1402  DomTreeNode *NewNode = DT->addNewBlock(Tail, Head);
1403  for (DomTreeNode *Child : Children)
1404  DT->changeImmediateDominator(Child, NewNode);
1405 
1406  // Head dominates ThenBlock.
1407  if (CreateThenBlock)
1408  DT->addNewBlock(ThenBlock, Head);
1409  else
1410  DT->changeImmediateDominator(ThenBlock, Head);
1411  }
1412  }
1413 
1414  if (LI) {
1415  if (Loop *L = LI->getLoopFor(Head)) {
1416  L->addBasicBlockToLoop(ThenBlock, *LI);
1417  L->addBasicBlockToLoop(Tail, *LI);
1418  }
1419  }
1420 
1421  return CheckTerm;
1422 }
1423 
1425  Instruction *SplitBefore,
1426  bool Unreachable,
1427  MDNode *BranchWeights,
1428  DominatorTree *DT, LoopInfo *LI,
1429  BasicBlock *ThenBlock) {
1430  return SplitBlockAndInsertIfThenImpl(Cond, SplitBefore, Unreachable,
1431  BranchWeights,
1432  /*DTU=*/nullptr, DT, LI, ThenBlock);
1433 }
1435  Instruction *SplitBefore,
1436  bool Unreachable,
1437  MDNode *BranchWeights,
1438  DomTreeUpdater *DTU, LoopInfo *LI,
1439  BasicBlock *ThenBlock) {
1440  return SplitBlockAndInsertIfThenImpl(Cond, SplitBefore, Unreachable,
1441  BranchWeights, DTU, /*DT=*/nullptr, LI,
1442  ThenBlock);
1443 }
1444 
1446  Instruction **ThenTerm,
1447  Instruction **ElseTerm,
1448  MDNode *BranchWeights) {
1449  BasicBlock *Head = SplitBefore->getParent();
1450  BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator());
1451  Instruction *HeadOldTerm = Head->getTerminator();
1452  LLVMContext &C = Head->getContext();
1453  BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
1454  BasicBlock *ElseBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
1455  *ThenTerm = BranchInst::Create(Tail, ThenBlock);
1456  (*ThenTerm)->setDebugLoc(SplitBefore->getDebugLoc());
1457  *ElseTerm = BranchInst::Create(Tail, ElseBlock);
1458  (*ElseTerm)->setDebugLoc(SplitBefore->getDebugLoc());
1459  BranchInst *HeadNewTerm =
1460  BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/ElseBlock, Cond);
1461  HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
1462  ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
1463 }
1464 
1466  BasicBlock *&IfFalse) {
1467  PHINode *SomePHI = dyn_cast<PHINode>(BB->begin());
1468  BasicBlock *Pred1 = nullptr;
1469  BasicBlock *Pred2 = nullptr;
1470 
1471  if (SomePHI) {
1472  if (SomePHI->getNumIncomingValues() != 2)
1473  return nullptr;
1474  Pred1 = SomePHI->getIncomingBlock(0);
1475  Pred2 = SomePHI->getIncomingBlock(1);
1476  } else {
1477  pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1478  if (PI == PE) // No predecessor
1479  return nullptr;
1480  Pred1 = *PI++;
1481  if (PI == PE) // Only one predecessor
1482  return nullptr;
1483  Pred2 = *PI++;
1484  if (PI != PE) // More than two predecessors
1485  return nullptr;
1486  }
1487 
1488  // We can only handle branches. Other control flow will be lowered to
1489  // branches if possible anyway.
1490  BranchInst *Pred1Br = dyn_cast<BranchInst>(Pred1->getTerminator());
1491  BranchInst *Pred2Br = dyn_cast<BranchInst>(Pred2->getTerminator());
1492  if (!Pred1Br || !Pred2Br)
1493  return nullptr;
1494 
1495  // Eliminate code duplication by ensuring that Pred1Br is conditional if
1496  // either are.
1497  if (Pred2Br->isConditional()) {
1498  // If both branches are conditional, we don't have an "if statement". In
1499  // reality, we could transform this case, but since the condition will be
1500  // required anyway, we stand no chance of eliminating it, so the xform is
1501  // probably not profitable.
1502  if (Pred1Br->isConditional())
1503  return nullptr;
1504 
1505  std::swap(Pred1, Pred2);
1506  std::swap(Pred1Br, Pred2Br);
1507  }
1508 
1509  if (Pred1Br->isConditional()) {
1510  // The only thing we have to watch out for here is to make sure that Pred2
1511  // doesn't have incoming edges from other blocks. If it does, the condition
1512  // doesn't dominate BB.
1513  if (!Pred2->getSinglePredecessor())
1514  return nullptr;
1515 
1516  // If we found a conditional branch predecessor, make sure that it branches
1517  // to BB and Pred2Br. If it doesn't, this isn't an "if statement".
1518  if (Pred1Br->getSuccessor(0) == BB &&
1519  Pred1Br->getSuccessor(1) == Pred2) {
1520  IfTrue = Pred1;
1521  IfFalse = Pred2;
1522  } else if (Pred1Br->getSuccessor(0) == Pred2 &&
1523  Pred1Br->getSuccessor(1) == BB) {
1524  IfTrue = Pred2;
1525  IfFalse = Pred1;
1526  } else {
1527  // We know that one arm of the conditional goes to BB, so the other must
1528  // go somewhere unrelated, and this must not be an "if statement".
1529  return nullptr;
1530  }
1531 
1532  return Pred1Br->getCondition();
1533  }
1534 
1535  // Ok, if we got here, both predecessors end with an unconditional branch to
1536  // BB. Don't panic! If both blocks only have a single (identical)
1537  // predecessor, and THAT is a conditional branch, then we're all ok!
1538  BasicBlock *CommonPred = Pred1->getSinglePredecessor();
1539  if (CommonPred == nullptr || CommonPred != Pred2->getSinglePredecessor())
1540  return nullptr;
1541 
1542  // Otherwise, if this is a conditional branch, then we can use it!
1543  BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator());
1544  if (!BI) return nullptr;
1545 
1546  assert(BI->isConditional() && "Two successors but not conditional?");
1547  if (BI->getSuccessor(0) == Pred1) {
1548  IfTrue = Pred1;
1549  IfFalse = Pred2;
1550  } else {
1551  IfTrue = Pred2;
1552  IfFalse = Pred1;
1553  }
1554  return BI->getCondition();
1555 }
1556 
1557 // After creating a control flow hub, the operands of PHINodes in an outgoing
1558 // block Out no longer match the predecessors of that block. Predecessors of Out
1559 // that are incoming blocks to the hub are now replaced by just one edge from
1560 // the hub. To match this new control flow, the corresponding values from each
1561 // PHINode must now be moved a new PHINode in the first guard block of the hub.
1562 //
1563 // This operation cannot be performed with SSAUpdater, because it involves one
1564 // new use: If the block Out is in the list of Incoming blocks, then the newly
1565 // created PHI in the Hub will use itself along that edge from Out to Hub.
1566 static void reconnectPhis(BasicBlock *Out, BasicBlock *GuardBlock,
1567  const SetVector<BasicBlock *> &Incoming,
1568  BasicBlock *FirstGuardBlock) {
1569  auto I = Out->begin();
1570  while (I != Out->end() && isa<PHINode>(I)) {
1571  auto Phi = cast<PHINode>(I);
1572  auto NewPhi =
1573  PHINode::Create(Phi->getType(), Incoming.size(),
1574  Phi->getName() + ".moved", &FirstGuardBlock->back());
1575  for (auto In : Incoming) {
1576  Value *V = UndefValue::get(Phi->getType());
1577  if (In == Out) {
1578  V = NewPhi;
1579  } else if (Phi->getBasicBlockIndex(In) != -1) {
1580  V = Phi->removeIncomingValue(In, false);
1581  }
1582  NewPhi->addIncoming(V, In);
1583  }
1584  assert(NewPhi->getNumIncomingValues() == Incoming.size());
1585  if (Phi->getNumOperands() == 0) {
1586  Phi->replaceAllUsesWith(NewPhi);
1587  I = Phi->eraseFromParent();
1588  continue;
1589  }
1590  Phi->addIncoming(NewPhi, GuardBlock);
1591  ++I;
1592  }
1593 }
1594 
1597 
1598 // Redirects the terminator of the incoming block to the first guard
1599 // block in the hub. The condition of the original terminator (if it
1600 // was conditional) and its original successors are returned as a
1601 // tuple <condition, succ0, succ1>. The function additionally filters
1602 // out successors that are not in the set of outgoing blocks.
1603 //
1604 // - condition is non-null iff the branch is conditional.
1605 // - Succ1 is non-null iff the sole/taken target is an outgoing block.
1606 // - Succ2 is non-null iff condition is non-null and the fallthrough
1607 // target is an outgoing block.
1608 static std::tuple<Value *, BasicBlock *, BasicBlock *>
1610  const BBSetVector &Outgoing) {
1611  auto Branch = cast<BranchInst>(BB->getTerminator());
1612  auto Condition = Branch->isConditional() ? Branch->getCondition() : nullptr;
1613 
1614  BasicBlock *Succ0 = Branch->getSuccessor(0);
1615  BasicBlock *Succ1 = nullptr;
1616  Succ0 = Outgoing.count(Succ0) ? Succ0 : nullptr;
1617 
1618  if (Branch->isUnconditional()) {
1619  Branch->setSuccessor(0, FirstGuardBlock);
1620  assert(Succ0);
1621  } else {
1622  Succ1 = Branch->getSuccessor(1);
1623  Succ1 = Outgoing.count(Succ1) ? Succ1 : nullptr;
1624  assert(Succ0 || Succ1);
1625  if (Succ0 && !Succ1) {
1626  Branch->setSuccessor(0, FirstGuardBlock);
1627  } else if (Succ1 && !Succ0) {
1628  Branch->setSuccessor(1, FirstGuardBlock);
1629  } else {
1630  Branch->eraseFromParent();
1631  BranchInst::Create(FirstGuardBlock, BB);
1632  }
1633  }
1634 
1635  assert(Succ0 || Succ1);
1636  return std::make_tuple(Condition, Succ0, Succ1);
1637 }
1638 
1639 // Capture the existing control flow as guard predicates, and redirect
1640 // control flow from every incoming block to the first guard block in
1641 // the hub.
1642 //
1643 // There is one guard predicate for each outgoing block OutBB. The
1644 // predicate is a PHINode with one input for each InBB which
1645 // represents whether the hub should transfer control flow to OutBB if
1646 // it arrived from InBB. These predicates are NOT ORTHOGONAL. The Hub
1647 // evaluates them in the same order as the Outgoing set-vector, and
1648 // control branches to the first outgoing block whose predicate
1649 // evaluates to true.
1651  BasicBlock *FirstGuardBlock, BBPredicates &GuardPredicates,
1652  SmallVectorImpl<WeakVH> &DeletionCandidates, const BBSetVector &Incoming,
1653  const BBSetVector &Outgoing) {
1654  auto &Context = Incoming.front()->getContext();
1655  auto BoolTrue = ConstantInt::getTrue(Context);
1656  auto BoolFalse = ConstantInt::getFalse(Context);
1657 
1658  // The predicate for the last outgoing is trivially true, and so we
1659  // process only the first N-1 successors.
1660  for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) {
1661  auto Out = Outgoing[i];
1662  LLVM_DEBUG(dbgs() << "Creating guard for " << Out->getName() << "\n");
1663  auto Phi =
1665  StringRef("Guard.") + Out->getName(), FirstGuardBlock);
1666  GuardPredicates[Out] = Phi;
1667  }
1668 
1669  for (auto In : Incoming) {
1670  Value *Condition;
1671  BasicBlock *Succ0;
1672  BasicBlock *Succ1;
1673  std::tie(Condition, Succ0, Succ1) =
1674  redirectToHub(In, FirstGuardBlock, Outgoing);
1675 
1676  // Optimization: Consider an incoming block A with both successors
1677  // Succ0 and Succ1 in the set of outgoing blocks. The predicates
1678  // for Succ0 and Succ1 complement each other. If Succ0 is visited
1679  // first in the loop below, control will branch to Succ0 using the
1680  // corresponding predicate. But if that branch is not taken, then
1681  // control must reach Succ1, which means that the predicate for
1682  // Succ1 is always true.
1683  bool OneSuccessorDone = false;
1684  for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) {
1685  auto Out = Outgoing[i];
1686  auto Phi = GuardPredicates[Out];
1687  if (Out != Succ0 && Out != Succ1) {
1688  Phi->addIncoming(BoolFalse, In);
1689  continue;
1690  }
1691  // Optimization: When only one successor is an outgoing block,
1692  // the predicate is always true.
1693  if (!Succ0 || !Succ1 || OneSuccessorDone) {
1694  Phi->addIncoming(BoolTrue, In);
1695  continue;
1696  }
1697  assert(Succ0 && Succ1);
1698  OneSuccessorDone = true;
1699  if (Out == Succ0) {
1700  Phi->addIncoming(Condition, In);
1701  continue;
1702  }
1703  auto Inverted = invertCondition(Condition);
1704  DeletionCandidates.push_back(Condition);
1705  Phi->addIncoming(Inverted, In);
1706  }
1707  }
1708 }
1709 
1710 // For each outgoing block OutBB, create a guard block in the Hub. The
1711 // first guard block was already created outside, and available as the
1712 // first element in the vector of guard blocks.
1713 //
1714 // Each guard block terminates in a conditional branch that transfers
1715 // control to the corresponding outgoing block or the next guard
1716 // block. The last guard block has two outgoing blocks as successors
1717 // since the condition for the final outgoing block is trivially
1718 // true. So we create one less block (including the first guard block)
1719 // than the number of outgoing blocks.
1721  Function *F, const BBSetVector &Outgoing,
1722  BBPredicates &GuardPredicates, StringRef Prefix) {
1723  for (int i = 0, e = Outgoing.size() - 2; i != e; ++i) {
1724  GuardBlocks.push_back(
1725  BasicBlock::Create(F->getContext(), Prefix + ".guard", F));
1726  }
1727  assert(GuardBlocks.size() == GuardPredicates.size());
1728 
1729  // To help keep the loop simple, temporarily append the last
1730  // outgoing block to the list of guard blocks.
1731  GuardBlocks.push_back(Outgoing.back());
1732 
1733  for (int i = 0, e = GuardBlocks.size() - 1; i != e; ++i) {
1734  auto Out = Outgoing[i];
1735  assert(GuardPredicates.count(Out));
1736  BranchInst::Create(Out, GuardBlocks[i + 1], GuardPredicates[Out],
1737  GuardBlocks[i]);
1738  }
1739 
1740  // Remove the last block from the guard list.
1741  GuardBlocks.pop_back();
1742 }
1743 
1745  DomTreeUpdater *DTU, SmallVectorImpl<BasicBlock *> &GuardBlocks,
1746  const BBSetVector &Incoming, const BBSetVector &Outgoing,
1747  const StringRef Prefix) {
1748  auto F = Incoming.front()->getParent();
1749  auto FirstGuardBlock =
1750  BasicBlock::Create(F->getContext(), Prefix + ".guard", F);
1751 
1753  if (DTU) {
1754  for (auto In : Incoming) {
1755  Updates.push_back({DominatorTree::Insert, In, FirstGuardBlock});
1756  for (auto Succ : successors(In)) {
1757  if (Outgoing.count(Succ))
1758  Updates.push_back({DominatorTree::Delete, In, Succ});
1759  }
1760  }
1761  }
1762 
1763  BBPredicates GuardPredicates;
1764  SmallVector<WeakVH, 8> DeletionCandidates;
1765  convertToGuardPredicates(FirstGuardBlock, GuardPredicates, DeletionCandidates,
1766  Incoming, Outgoing);
1767 
1768  GuardBlocks.push_back(FirstGuardBlock);
1769  createGuardBlocks(GuardBlocks, F, Outgoing, GuardPredicates, Prefix);
1770 
1771  // Update the PHINodes in each outgoing block to match the new control flow.
1772  for (int i = 0, e = GuardBlocks.size(); i != e; ++i) {
1773  reconnectPhis(Outgoing[i], GuardBlocks[i], Incoming, FirstGuardBlock);
1774  }
1775  reconnectPhis(Outgoing.back(), GuardBlocks.back(), Incoming, FirstGuardBlock);
1776 
1777  if (DTU) {
1778  int NumGuards = GuardBlocks.size();
1779  assert((int)Outgoing.size() == NumGuards + 1);
1780  for (int i = 0; i != NumGuards - 1; ++i) {
1781  Updates.push_back({DominatorTree::Insert, GuardBlocks[i], Outgoing[i]});
1782  Updates.push_back(
1783  {DominatorTree::Insert, GuardBlocks[i], GuardBlocks[i + 1]});
1784  }
1785  Updates.push_back({DominatorTree::Insert, GuardBlocks[NumGuards - 1],
1786  Outgoing[NumGuards - 1]});
1787  Updates.push_back({DominatorTree::Insert, GuardBlocks[NumGuards - 1],
1788  Outgoing[NumGuards]});
1789  DTU->applyUpdates(Updates);
1790  }
1791 
1792  for (auto I : DeletionCandidates) {
1793  if (I->use_empty())
1794  if (auto Inst = dyn_cast_or_null<Instruction>(I))
1795  Inst->eraseFromParent();
1796  }
1797 
1798  return FirstGuardBlock;
1799 }
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:1508
llvm::invertCondition
Value * invertCondition(Value *Condition)
Invert the given true/false value, possibly reusing an existing copy.
Definition: Local.cpp:3362
llvm::BasicBlock::end
iterator end()
Definition: BasicBlock.h:298
llvm::predecessors
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:127
llvm
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:1274
redirectToHub
static std::tuple< Value *, BasicBlock *, BasicBlock * > redirectToHub(BasicBlock *BB, BasicBlock *FirstGuardBlock, const BBSetVector &Outgoing)
Definition: BasicBlockUtils.cpp:1609
llvm::Type::getInt1Ty
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:201
llvm::CriticalEdgeSplittingOptions::MSSAU
MemorySSAUpdater * MSSAU
Definition: BasicBlockUtils.h:140
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:2923
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:161
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:1720
llvm::RegState::Dead
@ Dead
Unused definition.
Definition: MachineInstrBuilder.h:51
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:5136
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:2822
llvm::Value::hasName
bool hasName() const
Definition: Value.h:262
llvm::Function::getEntryBlock
const BasicBlock & getEntryBlock() const
Definition: Function.h:752
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:626
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:109
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:1504
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:1029
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:720
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:338
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:1297
llvm::MemorySSAUpdater::moveAllAfterSpliceBlocks
void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was spliced into From and To.
Definition: MemorySSAUpdater.cpp:1247
llvm::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:351
llvm::BasicBlock::splitBasicBlock
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)
Split the basic block into two basic blocks at the specified instruction.
Definition: BasicBlock.cpp:375
SplitBlockAndInsertIfThenImpl
static Instruction * SplitBlockAndInsertIfThenImpl(Value *Cond, Instruction *SplitBefore, bool Unreachable, MDNode *BranchWeights, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, BasicBlock *ThenBlock)
Definition: BasicBlockUtils.cpp:1356
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::CriticalEdgeSplittingOptions::LI
LoopInfo * LI
Definition: BasicBlockUtils.h:139
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:2559
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:1067
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:158
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BranchInst::setSuccessor
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Definition: Instructions.h:3103
llvm::Instruction::setMetadata
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1330
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:597
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:132
llvm::CallingConv::Tail
@ Tail
Tail - This calling convention attemps to make calls as fast as possible while guaranteeing that tail...
Definition: CallingConv.h:81
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:736
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:2666
PostDominators.h
llvm::DbgValueInst
This represents the llvm.dbg.value instruction.
Definition: IntrinsicInst.h:342
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:4561
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:994
llvm::BasicBlock::isLandingPad
bool isLandingPad() const
Return true if this basic block is a landing pad.
Definition: BasicBlock.cpp:466
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:476
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:1200
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:2755
llvm::Type::isTokenTy
bool isTokenTy() const
Return true if this is 'token'.
Definition: Type.h:199
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:1650
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:370
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1770
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
llvm::AArch64CC::PL
@ PL
Definition: AArch64BaseInfo.h:241
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:1154
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::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:572
llvm::removeRedundantPseudoProbes
bool removeRedundantPseudoProbes(BasicBlock *Block)
Same dangling probes in one blocks are redundant since they all have the same semantic that is to rel...
Definition: PseudoProbe.cpp:139
removeRedundantDbgInstrsUsingForwardScan
static bool removeRedundantDbgInstrsUsingForwardScan(BasicBlock *BB)
Remove redundant dbg.value instructions using a forward scan.
Definition: BasicBlockUtils.cpp:409
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2662
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:357
Type.h
llvm::Instruction::getMetadata
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:277
CFG.h
LoopInfo.h
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3086
llvm::Twine::str
std::string str() const
Return the twine contents as a std::string.
Definition: Twine.cpp:17
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:362
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:249
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2720
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:3061
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:964
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:721
llvm::succ_begin
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:99
llvm::DebugVariable
Identifies a unique instance of a variable.
Definition: DebugInfoMetadata.h:3589
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:1570
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:550
ArrayRef.h
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:362
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())
llvm::CriticalEdgeSplittingOptions::PreserveLCSSA
bool PreserveLCSSA
Definition: BasicBlockUtils.h:143
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:766
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:328
llvm::MemorySSA::verifyMemorySSA
void verifyMemorySSA() const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1867
llvm::MDNode
Metadata node.
Definition: Metadata.h:897
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:1445
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:3083
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:821
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:33
llvm::LoopInfo
Definition: LoopInfo.h:1080
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:1512
llvm::SymbolTableList< Instruction >
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:167
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h: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:526
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:791
llvm::CleanupPadInst::Create
static CleanupPadInst * Create(Value *ParentPad, ArrayRef< Value * > Args=None, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:4383
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:298
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:840
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:92
llvm::CriticalEdgeSplittingOptions::MergeIdenticalEdges
bool MergeIdenticalEdges
Definition: BasicBlockUtils.h:141
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:462
llvm::MemoryDependenceResults
Provides a lazy, caching interface for making common memory aliasing information queries,...
Definition: MemoryDependenceAnalysis.h:276
llvm::LoopInfoBase::isLoopHeader
bool isLoopHeader(const BlockT *BB) const
Definition: LoopInfo.h:977
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:501
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:833
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:539
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:314
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:2612
llvm::ArrayRef::begin
iterator begin() const
Definition: ArrayRef.h:151
llvm::MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor
void wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New, ArrayRef< BasicBlock * > Preds, bool IdenticalEdgesWereMerged=true)
A new empty BasicBlock (New) now branches directly to Old.
Definition: MemorySSAUpdater.cpp:1268
llvm::MemorySSAUpdater::moveAllAfterMergeBlocks
void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was merged into To.
Definition: MemorySSAUpdater.cpp:1258
UpdateAnalysisInformation
static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB, ArrayRef< BasicBlock * > Preds, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA, bool &HasLoopExit)
Update DominatorTree, LoopInfo, and LCCSA analysis information.
Definition: BasicBlockUtils.cpp:881
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:2318
llvm::MCID::Branch
@ Branch
Definition: MCInstrDesc.h:157
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:207
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:644
llvm::MemoryUseOrDef
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:250
PseudoProbe.h
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::GetIfCondition
Value * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
Definition: BasicBlockUtils.cpp:1465
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:835
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::CriticalEdgeSplittingOptions::DT
DominatorTree * DT
Definition: BasicBlockUtils.h:137
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:752
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:365
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:316
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:2686
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:163
llvm::RemoveRedundantDbgInstrs
bool RemoveRedundantDbgInstrs(BasicBlock *BB, bool RemovePseudoOp=false)
Try to remove redundant dbg.value instructions from given basic block.
Definition: BasicBlockUtils.cpp:438
llvm::PHINode
Definition: Instructions.h:2572
llvm::SmallVectorImpl< DominatorTree::UpdateType >
llvm::BasicBlock::getLandingPadInst
const LandingPadInst * getLandingPadInst() const
Return the landingpad instruction associated with the landing pad.
Definition: BasicBlock.cpp:470
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:4650
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:376
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:1424
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3005
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:820
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:1172
llvm::CriticalEdgeSplittingOptions::PreserveLoopSimplify
bool PreserveLoopSimplify
SplitCriticalEdge is guaranteed to preserve loop-simplify form if LI is provided.
Definition: BasicBlockUtils.h:148
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:156
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:1566
llvm::ArrayRef::end
iterator end() const
Definition: ArrayRef.h:152
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3084
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3098
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