LLVM  8.0.0svn
MachineBasicBlock.cpp
Go to the documentation of this file.
1 //===-- llvm/CodeGen/MachineBasicBlock.cpp ----------------------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Collect the sequence of machine instructions for a basic block.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/SmallPtrSet.h"
27 #include "llvm/Config/llvm-config.h"
28 #include "llvm/IR/BasicBlock.h"
29 #include "llvm/IR/DataLayout.h"
32 #include "llvm/MC/MCAsmInfo.h"
33 #include "llvm/MC/MCContext.h"
34 #include "llvm/Support/DataTypes.h"
35 #include "llvm/Support/Debug.h"
38 #include <algorithm>
39 using namespace llvm;
40 
41 #define DEBUG_TYPE "codegen"
42 
43 MachineBasicBlock::MachineBasicBlock(MachineFunction &MF, const BasicBlock *B)
44  : BB(B), Number(-1), xParent(&MF) {
45  Insts.Parent = this;
46  if (B)
47  IrrLoopHeaderWeight = B->getIrrLoopHeaderWeight();
48 }
49 
50 MachineBasicBlock::~MachineBasicBlock() {
51 }
52 
53 /// Return the MCSymbol for this basic block.
55  if (!CachedMCSymbol) {
56  const MachineFunction *MF = getParent();
57  MCContext &Ctx = MF->getContext();
58  auto Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix();
59  assert(getNumber() >= 0 && "cannot get label for unreachable MBB");
60  CachedMCSymbol = Ctx.getOrCreateSymbol(Twine(Prefix) + "BB" +
61  Twine(MF->getFunctionNumber()) +
62  "_" + Twine(getNumber()));
63  }
64 
65  return CachedMCSymbol;
66 }
67 
68 
70  MBB.print(OS);
71  return OS;
72 }
73 
75  return Printable([&MBB](raw_ostream &OS) { return MBB.printAsOperand(OS); });
76 }
77 
78 /// When an MBB is added to an MF, we need to update the parent pointer of the
79 /// MBB, the MBB numbering, and any instructions in the MBB to be on the right
80 /// operand list for registers.
81 ///
82 /// MBBs start out as #-1. When a MBB is added to a MachineFunction, it
83 /// gets the next available unique MBB number. If it is removed from a
84 /// MachineFunction, it goes back to being #-1.
87  MachineFunction &MF = *N->getParent();
88  N->Number = MF.addToMBBNumbering(N);
89 
90  // Make sure the instructions have their operands in the reginfo lists.
91  MachineRegisterInfo &RegInfo = MF.getRegInfo();
93  I = N->instr_begin(), E = N->instr_end(); I != E; ++I)
94  I->AddRegOperandsToUseLists(RegInfo);
95 }
96 
98  MachineBasicBlock *N) {
99  N->getParent()->removeFromMBBNumbering(N->Number);
100  N->Number = -1;
101 }
102 
103 /// When we add an instruction to a basic block list, we update its parent
104 /// pointer and add its operands from reg use/def lists if appropriate.
106  assert(!N->getParent() && "machine instruction already in a basic block");
107  N->setParent(Parent);
108 
109  // Add the instruction's register operands to their corresponding
110  // use/def lists.
111  MachineFunction *MF = Parent->getParent();
112  N->AddRegOperandsToUseLists(MF->getRegInfo());
113  MF->handleInsertion(*N);
114 }
115 
116 /// When we remove an instruction from a basic block list, we update its parent
117 /// pointer and remove its operands from reg use/def lists if appropriate.
119  assert(N->getParent() && "machine instruction not in a basic block");
120 
121  // Remove from the use/def lists.
122  if (MachineFunction *MF = N->getMF()) {
123  MF->handleRemoval(*N);
124  N->RemoveRegOperandsFromUseLists(MF->getRegInfo());
125  }
126 
127  N->setParent(nullptr);
128 }
129 
130 /// When moving a range of instructions from one MBB list to another, we need to
131 /// update the parent pointers and the use/def lists.
133  instr_iterator First,
134  instr_iterator Last) {
135  assert(Parent->getParent() == FromList.Parent->getParent() &&
136  "MachineInstr parent mismatch!");
137  assert(this != &FromList && "Called without a real transfer...");
138  assert(Parent != FromList.Parent && "Two lists have the same parent?");
139 
140  // If splicing between two blocks within the same function, just update the
141  // parent pointers.
142  for (; First != Last; ++First)
143  First->setParent(Parent);
144 }
145 
147  assert(!MI->getParent() && "MI is still in a block!");
148  Parent->getParent()->DeleteMachineInstr(MI);
149 }
150 
153  while (I != E && I->isPHI())
154  ++I;
155  assert((I == E || !I->isInsideBundle()) &&
156  "First non-phi MI cannot be inside a bundle!");
157  return I;
158 }
159 
163 
164  iterator E = end();
165  while (I != E && (I->isPHI() || I->isPosition() ||
166  TII->isBasicBlockPrologue(*I)))
167  ++I;
168  // FIXME: This needs to change if we wish to bundle labels
169  // inside the bundle.
170  assert((I == E || !I->isInsideBundle()) &&
171  "First non-phi / non-label instruction is inside a bundle!");
172  return I;
173 }
174 
178 
179  iterator E = end();
180  while (I != E && (I->isPHI() || I->isPosition() || I->isDebugInstr() ||
181  TII->isBasicBlockPrologue(*I)))
182  ++I;
183  // FIXME: This needs to change if we wish to bundle labels / dbg_values
184  // inside the bundle.
185  assert((I == E || !I->isInsideBundle()) &&
186  "First non-phi / non-label / non-debug "
187  "instruction is inside a bundle!");
188  return I;
189 }
190 
192  iterator B = begin(), E = end(), I = E;
193  while (I != B && ((--I)->isTerminator() || I->isDebugInstr()))
194  ; /*noop */
195  while (I != E && !I->isTerminator())
196  ++I;
197  return I;
198 }
199 
201  instr_iterator B = instr_begin(), E = instr_end(), I = E;
202  while (I != B && ((--I)->isTerminator() || I->isDebugInstr()))
203  ; /*noop */
204  while (I != E && !I->isTerminator())
205  ++I;
206  return I;
207 }
208 
210  // Skip over begin-of-block dbg_value instructions.
212 }
213 
215  // Skip over end-of-block dbg_value instructions.
217  while (I != B) {
218  --I;
219  // Return instruction that starts a bundle.
220  if (I->isDebugInstr() || I->isInsideBundle())
221  continue;
222  return I;
223  }
224  // The block is all debug values.
225  return end();
226 }
227 
229  for (const_succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I)
230  if ((*I)->isEHPad())
231  return true;
232  return false;
233 }
234 
235 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
237  print(dbgs());
238 }
239 #endif
240 
242  if (isReturnBlock() || hasEHPadSuccessor())
243  return false;
244  return true;
245 }
246 
248  if (const BasicBlock *LBB = getBasicBlock())
249  return LBB->getName();
250  else
251  return StringRef("", 0);
252 }
253 
254 /// Return a hopefully unique identifier for this block.
255 std::string MachineBasicBlock::getFullName() const {
256  std::string Name;
257  if (getParent())
258  Name = (getParent()->getName() + ":").str();
259  if (getBasicBlock())
260  Name += getBasicBlock()->getName();
261  else
262  Name += ("BB" + Twine(getNumber())).str();
263  return Name;
264 }
265 
267  bool IsStandalone) const {
268  const MachineFunction *MF = getParent();
269  if (!MF) {
270  OS << "Can't print out MachineBasicBlock because parent MachineFunction"
271  << " is null\n";
272  return;
273  }
274  const Function &F = MF->getFunction();
275  const Module *M = F.getParent();
276  ModuleSlotTracker MST(M);
277  MST.incorporateFunction(F);
278  print(OS, MST, Indexes, IsStandalone);
279 }
280 
282  const SlotIndexes *Indexes,
283  bool IsStandalone) const {
284  const MachineFunction *MF = getParent();
285  if (!MF) {
286  OS << "Can't print out MachineBasicBlock because parent MachineFunction"
287  << " is null\n";
288  return;
289  }
290 
291  if (Indexes)
292  OS << Indexes->getMBBStartIdx(this) << '\t';
293 
294  OS << "bb." << getNumber();
295  bool HasAttributes = false;
296  if (const auto *BB = getBasicBlock()) {
297  if (BB->hasName()) {
298  OS << "." << BB->getName();
299  } else {
300  HasAttributes = true;
301  OS << " (";
302  int Slot = MST.getLocalSlot(BB);
303  if (Slot == -1)
304  OS << "<ir-block badref>";
305  else
306  OS << (Twine("%ir-block.") + Twine(Slot)).str();
307  }
308  }
309 
310  if (hasAddressTaken()) {
311  OS << (HasAttributes ? ", " : " (");
312  OS << "address-taken";
313  HasAttributes = true;
314  }
315  if (isEHPad()) {
316  OS << (HasAttributes ? ", " : " (");
317  OS << "landing-pad";
318  HasAttributes = true;
319  }
320  if (getAlignment()) {
321  OS << (HasAttributes ? ", " : " (");
322  OS << "align " << getAlignment();
323  HasAttributes = true;
324  }
325  if (HasAttributes)
326  OS << ")";
327  OS << ":\n";
328 
330  const MachineRegisterInfo &MRI = MF->getRegInfo();
332  bool HasLineAttributes = false;
333 
334  // Print the preds of this block according to the CFG.
335  if (!pred_empty() && IsStandalone) {
336  if (Indexes) OS << '\t';
337  // Don't indent(2), align with previous line attributes.
338  OS << "; predecessors: ";
339  for (auto I = pred_begin(), E = pred_end(); I != E; ++I) {
340  if (I != pred_begin())
341  OS << ", ";
342  OS << printMBBReference(**I);
343  }
344  OS << '\n';
345  HasLineAttributes = true;
346  }
347 
348  if (!succ_empty()) {
349  if (Indexes) OS << '\t';
350  // Print the successors
351  OS.indent(2) << "successors: ";
352  for (auto I = succ_begin(), E = succ_end(); I != E; ++I) {
353  if (I != succ_begin())
354  OS << ", ";
355  OS << printMBBReference(**I);
356  if (!Probs.empty())
357  OS << '('
358  << format("0x%08" PRIx32, getSuccProbability(I).getNumerator())
359  << ')';
360  }
361  if (!Probs.empty() && IsStandalone) {
362  // Print human readable probabilities as comments.
363  OS << "; ";
364  for (auto I = succ_begin(), E = succ_end(); I != E; ++I) {
365  const BranchProbability &BP = *getProbabilityIterator(I);
366  if (I != succ_begin())
367  OS << ", ";
368  OS << printMBBReference(**I) << '('
369  << format("%.2f%%",
370  rint(((double)BP.getNumerator() / BP.getDenominator()) *
371  100.0 * 100.0) /
372  100.0)
373  << ')';
374  }
375  }
376 
377  OS << '\n';
378  HasLineAttributes = true;
379  }
380 
381  if (!livein_empty() && MRI.tracksLiveness()) {
382  if (Indexes) OS << '\t';
383  OS.indent(2) << "liveins: ";
384 
385  bool First = true;
386  for (const auto &LI : liveins()) {
387  if (!First)
388  OS << ", ";
389  First = false;
390  OS << printReg(LI.PhysReg, TRI);
391  if (!LI.LaneMask.all())
392  OS << ":0x" << PrintLaneMask(LI.LaneMask);
393  }
394  HasLineAttributes = true;
395  }
396 
397  if (HasLineAttributes)
398  OS << '\n';
399 
400  bool IsInBundle = false;
401  for (const MachineInstr &MI : instrs()) {
402  if (Indexes) {
403  if (Indexes->hasIndex(MI))
404  OS << Indexes->getInstructionIndex(MI);
405  OS << '\t';
406  }
407 
408  if (IsInBundle && !MI.isInsideBundle()) {
409  OS.indent(2) << "}\n";
410  IsInBundle = false;
411  }
412 
413  OS.indent(IsInBundle ? 4 : 2);
414  MI.print(OS, MST, IsStandalone, /*SkipOpers=*/false, /*SkipDebugLoc=*/false,
415  /*AddNewLine=*/false, &TII);
416 
417  if (!IsInBundle && MI.getFlag(MachineInstr::BundledSucc)) {
418  OS << " {";
419  IsInBundle = true;
420  }
421  OS << '\n';
422  }
423 
424  if (IsInBundle)
425  OS.indent(2) << "}\n";
426 
427  if (IrrLoopHeaderWeight && IsStandalone) {
428  if (Indexes) OS << '\t';
429  OS.indent(2) << "; Irreducible loop header weight: "
430  << IrrLoopHeaderWeight.getValue() << '\n';
431  }
432 }
433 
435  bool /*PrintType*/) const {
436  OS << "%bb." << getNumber();
437 }
438 
440  LiveInVector::iterator I = find_if(
441  LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
442  if (I == LiveIns.end())
443  return;
444 
445  I->LaneMask &= ~LaneMask;
446  if (I->LaneMask.none())
447  LiveIns.erase(I);
448 }
449 
452  // Get non-const version of iterator.
453  LiveInVector::iterator LI = LiveIns.begin() + (I - LiveIns.begin());
454  return LiveIns.erase(LI);
455 }
456 
459  LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
460  return I != livein_end() && (I->LaneMask & LaneMask).any();
461 }
462 
464  llvm::sort(LiveIns.begin(), LiveIns.end(),
465  [](const RegisterMaskPair &LI0, const RegisterMaskPair &LI1) {
466  return LI0.PhysReg < LI1.PhysReg;
467  });
468  // Liveins are sorted by physreg now we can merge their lanemasks.
469  LiveInVector::const_iterator I = LiveIns.begin();
470  LiveInVector::const_iterator J;
471  LiveInVector::iterator Out = LiveIns.begin();
472  for (; I != LiveIns.end(); ++Out, I = J) {
473  unsigned PhysReg = I->PhysReg;
474  LaneBitmask LaneMask = I->LaneMask;
475  for (J = std::next(I); J != LiveIns.end() && J->PhysReg == PhysReg; ++J)
476  LaneMask |= J->LaneMask;
477  Out->PhysReg = PhysReg;
478  Out->LaneMask = LaneMask;
479  }
480  LiveIns.erase(Out, LiveIns.end());
481 }
482 
483 unsigned
485  assert(getParent() && "MBB must be inserted in function");
486  assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && "Expected physreg");
487  assert(RC && "Register class is required");
488  assert((isEHPad() || this == &getParent()->front()) &&
489  "Only the entry block and landing pads can have physreg live ins");
490 
491  bool LiveIn = isLiveIn(PhysReg);
495 
496  // Look for an existing copy.
497  if (LiveIn)
498  for (;I != E && I->isCopy(); ++I)
499  if (I->getOperand(1).getReg() == PhysReg) {
500  unsigned VirtReg = I->getOperand(0).getReg();
501  if (!MRI.constrainRegClass(VirtReg, RC))
502  llvm_unreachable("Incompatible live-in register class.");
503  return VirtReg;
504  }
505 
506  // No luck, create a virtual register.
507  unsigned VirtReg = MRI.createVirtualRegister(RC);
508  BuildMI(*this, I, DebugLoc(), TII.get(TargetOpcode::COPY), VirtReg)
509  .addReg(PhysReg, RegState::Kill);
510  if (!LiveIn)
511  addLiveIn(PhysReg);
512  return VirtReg;
513 }
514 
516  getParent()->splice(NewAfter->getIterator(), getIterator());
517 }
518 
520  getParent()->splice(++NewBefore->getIterator(), getIterator());
521 }
522 
525  // A block with no successors has no concerns with fall-through edges.
526  if (this->succ_empty())
527  return;
528 
529  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
532  bool B = TII->analyzeBranch(*this, TBB, FBB, Cond);
533  (void) B;
534  assert(!B && "UpdateTerminators requires analyzable predecessors!");
535  if (Cond.empty()) {
536  if (TBB) {
537  // The block has an unconditional branch. If its successor is now its
538  // layout successor, delete the branch.
539  if (isLayoutSuccessor(TBB))
540  TII->removeBranch(*this);
541  } else {
542  // The block has an unconditional fallthrough. If its successor is not its
543  // layout successor, insert a branch. First we have to locate the only
544  // non-landing-pad successor, as that is the fallthrough block.
545  for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) {
546  if ((*SI)->isEHPad())
547  continue;
548  assert(!TBB && "Found more than one non-landing-pad successor!");
549  TBB = *SI;
550  }
551 
552  // If there is no non-landing-pad successor, the block has no fall-through
553  // edges to be concerned with.
554  if (!TBB)
555  return;
556 
557  // Finally update the unconditional successor to be reached via a branch
558  // if it would not be reached by fallthrough.
559  if (!isLayoutSuccessor(TBB))
560  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
561  }
562  return;
563  }
564 
565  if (FBB) {
566  // The block has a non-fallthrough conditional branch. If one of its
567  // successors is its layout successor, rewrite it to a fallthrough
568  // conditional branch.
569  if (isLayoutSuccessor(TBB)) {
570  if (TII->reverseBranchCondition(Cond))
571  return;
572  TII->removeBranch(*this);
573  TII->insertBranch(*this, FBB, nullptr, Cond, DL);
574  } else if (isLayoutSuccessor(FBB)) {
575  TII->removeBranch(*this);
576  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
577  }
578  return;
579  }
580 
581  // Walk through the successors and find the successor which is not a landing
582  // pad and is not the conditional branch destination (in TBB) as the
583  // fallthrough successor.
584  MachineBasicBlock *FallthroughBB = nullptr;
585  for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) {
586  if ((*SI)->isEHPad() || *SI == TBB)
587  continue;
588  assert(!FallthroughBB && "Found more than one fallthrough successor.");
589  FallthroughBB = *SI;
590  }
591 
592  if (!FallthroughBB) {
593  if (canFallThrough()) {
594  // We fallthrough to the same basic block as the conditional jump targets.
595  // Remove the conditional jump, leaving unconditional fallthrough.
596  // FIXME: This does not seem like a reasonable pattern to support, but it
597  // has been seen in the wild coming out of degenerate ARM test cases.
598  TII->removeBranch(*this);
599 
600  // Finally update the unconditional successor to be reached via a branch if
601  // it would not be reached by fallthrough.
602  if (!isLayoutSuccessor(TBB))
603  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
604  return;
605  }
606 
607  // We enter here iff exactly one successor is TBB which cannot fallthrough
608  // and the rest successors if any are EHPads. In this case, we need to
609  // change the conditional branch into unconditional branch.
610  TII->removeBranch(*this);
611  Cond.clear();
612  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
613  return;
614  }
615 
616  // The block has a fallthrough conditional branch.
617  if (isLayoutSuccessor(TBB)) {
618  if (TII->reverseBranchCondition(Cond)) {
619  // We can't reverse the condition, add an unconditional branch.
620  Cond.clear();
621  TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
622  return;
623  }
624  TII->removeBranch(*this);
625  TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
626  } else if (!isLayoutSuccessor(FallthroughBB)) {
627  TII->removeBranch(*this);
628  TII->insertBranch(*this, TBB, FallthroughBB, Cond, DL);
629  }
630 }
631 
633 #ifndef NDEBUG
634  int64_t Sum = 0;
635  for (auto Prob : Probs)
636  Sum += Prob.getNumerator();
637  // Due to precision issue, we assume that the sum of probabilities is one if
638  // the difference between the sum of their numerators and the denominator is
639  // no greater than the number of successors.
641  Probs.size() &&
642  "The sum of successors's probabilities exceeds one.");
643 #endif // NDEBUG
644 }
645 
647  BranchProbability Prob) {
648  // Probability list is either empty (if successor list isn't empty, this means
649  // disabled optimization) or has the same size as successor list.
650  if (!(Probs.empty() && !Successors.empty()))
651  Probs.push_back(Prob);
652  Successors.push_back(Succ);
653  Succ->addPredecessor(this);
654 }
655 
657  // We need to make sure probability list is either empty or has the same size
658  // of successor list. When this function is called, we can safely delete all
659  // probability in the list.
660  Probs.clear();
661  Successors.push_back(Succ);
662  Succ->addPredecessor(this);
663 }
664 
666  MachineBasicBlock *New,
667  bool NormalizeSuccProbs) {
668  succ_iterator OldI = llvm::find(successors(), Old);
669  assert(OldI != succ_end() && "Old is not a successor of this block!");
670  assert(llvm::find(successors(), New) == succ_end() &&
671  "New is already a successor of this block!");
672 
673  // Add a new successor with equal probability as the original one. Note
674  // that we directly copy the probability using the iterator rather than
675  // getting a potentially synthetic probability computed when unknown. This
676  // preserves the probabilities as-is and then we can renormalize them and
677  // query them effectively afterward.
678  addSuccessor(New, Probs.empty() ? BranchProbability::getUnknown()
679  : *getProbabilityIterator(OldI));
680  if (NormalizeSuccProbs)
682 }
683 
685  bool NormalizeSuccProbs) {
686  succ_iterator I = find(Successors, Succ);
687  removeSuccessor(I, NormalizeSuccProbs);
688 }
689 
692  assert(I != Successors.end() && "Not a current successor!");
693 
694  // If probability list is empty it means we don't use it (disabled
695  // optimization).
696  if (!Probs.empty()) {
697  probability_iterator WI = getProbabilityIterator(I);
698  Probs.erase(WI);
699  if (NormalizeSuccProbs)
701  }
702 
703  (*I)->removePredecessor(this);
704  return Successors.erase(I);
705 }
706 
708  MachineBasicBlock *New) {
709  if (Old == New)
710  return;
711 
713  succ_iterator NewI = E;
714  succ_iterator OldI = E;
715  for (succ_iterator I = succ_begin(); I != E; ++I) {
716  if (*I == Old) {
717  OldI = I;
718  if (NewI != E)
719  break;
720  }
721  if (*I == New) {
722  NewI = I;
723  if (OldI != E)
724  break;
725  }
726  }
727  assert(OldI != E && "Old is not a successor of this block");
728 
729  // If New isn't already a successor, let it take Old's place.
730  if (NewI == E) {
731  Old->removePredecessor(this);
732  New->addPredecessor(this);
733  *OldI = New;
734  return;
735  }
736 
737  // New is already a successor.
738  // Update its probability instead of adding a duplicate edge.
739  if (!Probs.empty()) {
740  auto ProbIter = getProbabilityIterator(NewI);
741  if (!ProbIter->isUnknown())
742  *ProbIter += *getProbabilityIterator(OldI);
743  }
744  removeSuccessor(OldI);
745 }
746 
748  succ_iterator I) {
749  if (Orig->Probs.empty())
750  addSuccessor(*I, Orig->getSuccProbability(I));
751  else
753 }
754 
755 void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) {
756  Predecessors.push_back(Pred);
757 }
758 
759 void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) {
760  pred_iterator I = find(Predecessors, Pred);
761  assert(I != Predecessors.end() && "Pred is not a predecessor of this block!");
762  Predecessors.erase(I);
763 }
764 
766  if (this == FromMBB)
767  return;
768 
769  while (!FromMBB->succ_empty()) {
770  MachineBasicBlock *Succ = *FromMBB->succ_begin();
771 
772  // If probability list is empty it means we don't use it (disabled optimization).
773  if (!FromMBB->Probs.empty()) {
774  auto Prob = *FromMBB->Probs.begin();
775  addSuccessor(Succ, Prob);
776  } else
778 
779  FromMBB->removeSuccessor(Succ);
780  }
781 }
782 
783 void
785  if (this == FromMBB)
786  return;
787 
788  while (!FromMBB->succ_empty()) {
789  MachineBasicBlock *Succ = *FromMBB->succ_begin();
790  if (!FromMBB->Probs.empty()) {
791  auto Prob = *FromMBB->Probs.begin();
792  addSuccessor(Succ, Prob);
793  } else
795  FromMBB->removeSuccessor(Succ);
796 
797  // Fix up any PHI nodes in the successor.
799  ME = Succ->instr_end(); MI != ME && MI->isPHI(); ++MI)
800  for (unsigned i = 2, e = MI->getNumOperands()+1; i != e; i += 2) {
801  MachineOperand &MO = MI->getOperand(i);
802  if (MO.getMBB() == FromMBB)
803  MO.setMBB(this);
804  }
805  }
807 }
808 
810  return is_contained(predecessors(), MBB);
811 }
812 
814  return is_contained(successors(), MBB);
815 }
816 
819  return std::next(I) == MachineFunction::const_iterator(MBB);
820 }
821 
823  MachineFunction::iterator Fallthrough = getIterator();
824  ++Fallthrough;
825  // If FallthroughBlock is off the end of the function, it can't fall through.
826  if (Fallthrough == getParent()->end())
827  return nullptr;
828 
829  // If FallthroughBlock isn't a successor, no fallthrough is possible.
830  if (!isSuccessor(&*Fallthrough))
831  return nullptr;
832 
833  // Analyze the branches, if any, at the end of the block.
834  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
837  if (TII->analyzeBranch(*this, TBB, FBB, Cond)) {
838  // If we couldn't analyze the branch, examine the last instruction.
839  // If the block doesn't end in a known control barrier, assume fallthrough
840  // is possible. The isPredicated check is needed because this code can be
841  // called during IfConversion, where an instruction which is normally a
842  // Barrier is predicated and thus no longer an actual control barrier.
843  return (empty() || !back().isBarrier() || TII->isPredicated(back()))
844  ? &*Fallthrough
845  : nullptr;
846  }
847 
848  // If there is no branch, control always falls through.
849  if (!TBB) return &*Fallthrough;
850 
851  // If there is some explicit branch to the fallthrough block, it can obviously
852  // reach, even though the branch should get folded to fall through implicitly.
853  if (MachineFunction::iterator(TBB) == Fallthrough ||
854  MachineFunction::iterator(FBB) == Fallthrough)
855  return &*Fallthrough;
856 
857  // If it's an unconditional branch to some block not the fall through, it
858  // doesn't fall through.
859  if (Cond.empty()) return nullptr;
860 
861  // Otherwise, if it is conditional and has no explicit false block, it falls
862  // through.
863  return (FBB == nullptr) ? &*Fallthrough : nullptr;
864 }
865 
867  return getFallThrough() != nullptr;
868 }
869 
871  Pass &P) {
872  if (!canSplitCriticalEdge(Succ))
873  return nullptr;
874 
875  MachineFunction *MF = getParent();
876  DebugLoc DL; // FIXME: this is nowhere
877 
879  MF->insert(std::next(MachineFunction::iterator(this)), NMBB);
880  LLVM_DEBUG(dbgs() << "Splitting critical edge: " << printMBBReference(*this)
881  << " -- " << printMBBReference(*NMBB) << " -- "
882  << printMBBReference(*Succ) << '\n');
883 
886  if (LIS)
887  LIS->insertMBBInMaps(NMBB);
888  else if (Indexes)
889  Indexes->insertMBBInMaps(NMBB);
890 
891  // On some targets like Mips, branches may kill virtual registers. Make sure
892  // that LiveVariables is properly updated after updateTerminator replaces the
893  // terminators.
895 
896  // Collect a list of virtual registers killed by the terminators.
897  SmallVector<unsigned, 4> KilledRegs;
898  if (LV)
900  I != E; ++I) {
901  MachineInstr *MI = &*I;
903  OE = MI->operands_end(); OI != OE; ++OI) {
904  if (!OI->isReg() || OI->getReg() == 0 ||
905  !OI->isUse() || !OI->isKill() || OI->isUndef())
906  continue;
907  unsigned Reg = OI->getReg();
909  LV->getVarInfo(Reg).removeKill(*MI)) {
910  KilledRegs.push_back(Reg);
911  LLVM_DEBUG(dbgs() << "Removing terminator kill: " << *MI);
912  OI->setIsKill(false);
913  }
914  }
915  }
916 
917  SmallVector<unsigned, 4> UsedRegs;
918  if (LIS) {
920  I != E; ++I) {
921  MachineInstr *MI = &*I;
922 
924  OE = MI->operands_end(); OI != OE; ++OI) {
925  if (!OI->isReg() || OI->getReg() == 0)
926  continue;
927 
928  unsigned Reg = OI->getReg();
929  if (!is_contained(UsedRegs, Reg))
930  UsedRegs.push_back(Reg);
931  }
932  }
933  }
934 
935  ReplaceUsesOfBlockWith(Succ, NMBB);
936 
937  // If updateTerminator() removes instructions, we need to remove them from
938  // SlotIndexes.
939  SmallVector<MachineInstr*, 4> Terminators;
940  if (Indexes) {
942  I != E; ++I)
943  Terminators.push_back(&*I);
944  }
945 
947 
948  if (Indexes) {
949  SmallVector<MachineInstr*, 4> NewTerminators;
951  I != E; ++I)
952  NewTerminators.push_back(&*I);
953 
954  for (SmallVectorImpl<MachineInstr*>::iterator I = Terminators.begin(),
955  E = Terminators.end(); I != E; ++I) {
956  if (!is_contained(NewTerminators, *I))
957  Indexes->removeMachineInstrFromMaps(**I);
958  }
959  }
960 
961  // Insert unconditional "jump Succ" instruction in NMBB if necessary.
962  NMBB->addSuccessor(Succ);
963  if (!NMBB->isLayoutSuccessor(Succ)) {
966  TII->insertBranch(*NMBB, Succ, nullptr, Cond, DL);
967 
968  if (Indexes) {
969  for (MachineInstr &MI : NMBB->instrs()) {
970  // Some instructions may have been moved to NMBB by updateTerminator(),
971  // so we first remove any instruction that already has an index.
972  if (Indexes->hasIndex(MI))
973  Indexes->removeMachineInstrFromMaps(MI);
974  Indexes->insertMachineInstrInMaps(MI);
975  }
976  }
977  }
978 
979  // Fix PHI nodes in Succ so they refer to NMBB instead of this
981  i = Succ->instr_begin(),e = Succ->instr_end();
982  i != e && i->isPHI(); ++i)
983  for (unsigned ni = 1, ne = i->getNumOperands(); ni != ne; ni += 2)
984  if (i->getOperand(ni+1).getMBB() == this)
985  i->getOperand(ni+1).setMBB(NMBB);
986 
987  // Inherit live-ins from the successor
988  for (const auto &LI : Succ->liveins())
989  NMBB->addLiveIn(LI);
990 
991  // Update LiveVariables.
993  if (LV) {
994  // Restore kills of virtual registers that were killed by the terminators.
995  while (!KilledRegs.empty()) {
996  unsigned Reg = KilledRegs.pop_back_val();
997  for (instr_iterator I = instr_end(), E = instr_begin(); I != E;) {
998  if (!(--I)->addRegisterKilled(Reg, TRI, /* addIfNotFound= */ false))
999  continue;
1001  LV->getVarInfo(Reg).Kills.push_back(&*I);
1002  LLVM_DEBUG(dbgs() << "Restored terminator kill: " << *I);
1003  break;
1004  }
1005  }
1006  // Update relevant live-through information.
1007  LV->addNewBlock(NMBB, this, Succ);
1008  }
1009 
1010  if (LIS) {
1011  // After splitting the edge and updating SlotIndexes, live intervals may be
1012  // in one of two situations, depending on whether this block was the last in
1013  // the function. If the original block was the last in the function, all
1014  // live intervals will end prior to the beginning of the new split block. If
1015  // the original block was not at the end of the function, all live intervals
1016  // will extend to the end of the new split block.
1017 
1018  bool isLastMBB =
1019  std::next(MachineFunction::iterator(NMBB)) == getParent()->end();
1020 
1021  SlotIndex StartIndex = Indexes->getMBBEndIdx(this);
1022  SlotIndex PrevIndex = StartIndex.getPrevSlot();
1023  SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB);
1024 
1025  // Find the registers used from NMBB in PHIs in Succ.
1026  SmallSet<unsigned, 8> PHISrcRegs;
1028  I = Succ->instr_begin(), E = Succ->instr_end();
1029  I != E && I->isPHI(); ++I) {
1030  for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne; ni += 2) {
1031  if (I->getOperand(ni+1).getMBB() == NMBB) {
1032  MachineOperand &MO = I->getOperand(ni);
1033  unsigned Reg = MO.getReg();
1034  PHISrcRegs.insert(Reg);
1035  if (MO.isUndef())
1036  continue;
1037 
1038  LiveInterval &LI = LIS->getInterval(Reg);
1039  VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
1040  assert(VNI &&
1041  "PHI sources should be live out of their predecessors.");
1042  LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1043  }
1044  }
1045  }
1046 
1048  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1049  unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
1050  if (PHISrcRegs.count(Reg) || !LIS->hasInterval(Reg))
1051  continue;
1052 
1053  LiveInterval &LI = LIS->getInterval(Reg);
1054  if (!LI.liveAt(PrevIndex))
1055  continue;
1056 
1057  bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ));
1058  if (isLiveOut && isLastMBB) {
1059  VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
1060  assert(VNI && "LiveInterval should have VNInfo where it is live.");
1061  LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1062  } else if (!isLiveOut && !isLastMBB) {
1063  LI.removeSegment(StartIndex, EndIndex);
1064  }
1065  }
1066 
1067  // Update all intervals for registers whose uses may have been modified by
1068  // updateTerminator().
1069  LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs);
1070  }
1071 
1072  if (MachineDominatorTree *MDT =
1074  MDT->recordSplitCriticalEdge(this, Succ, NMBB);
1075 
1077  if (MachineLoop *TIL = MLI->getLoopFor(this)) {
1078  // If one or the other blocks were not in a loop, the new block is not
1079  // either, and thus LI doesn't need to be updated.
1080  if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) {
1081  if (TIL == DestLoop) {
1082  // Both in the same loop, the NMBB joins loop.
1083  DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
1084  } else if (TIL->contains(DestLoop)) {
1085  // Edge from an outer loop to an inner loop. Add to the outer loop.
1086  TIL->addBasicBlockToLoop(NMBB, MLI->getBase());
1087  } else if (DestLoop->contains(TIL)) {
1088  // Edge from an inner loop to an outer loop. Add to the outer loop.
1089  DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
1090  } else {
1091  // Edge from two loops with no containment relation. Because these
1092  // are natural loops, we know that the destination block must be the
1093  // header of its loop (adding a branch into a loop elsewhere would
1094  // create an irreducible loop).
1095  assert(DestLoop->getHeader() == Succ &&
1096  "Should not create irreducible loops!");
1097  if (MachineLoop *P = DestLoop->getParentLoop())
1098  P->addBasicBlockToLoop(NMBB, MLI->getBase());
1099  }
1100  }
1101  }
1102 
1103  return NMBB;
1104 }
1105 
1107  const MachineBasicBlock *Succ) const {
1108  // Splitting the critical edge to a landing pad block is non-trivial. Don't do
1109  // it in this generic function.
1110  if (Succ->isEHPad())
1111  return false;
1112 
1113  const MachineFunction *MF = getParent();
1114 
1115  // Performance might be harmed on HW that implements branching using exec mask
1116  // where both sides of the branches are always executed.
1117  if (MF->getTarget().requiresStructuredCFG())
1118  return false;
1119 
1120  // We may need to update this's terminator, but we can't do that if
1121  // AnalyzeBranch fails. If this uses a jump table, we won't touch it.
1122  const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
1123  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1125  // AnalyzeBanch should modify this, since we did not allow modification.
1126  if (TII->analyzeBranch(*const_cast<MachineBasicBlock *>(this), TBB, FBB, Cond,
1127  /*AllowModify*/ false))
1128  return false;
1129 
1130  // Avoid bugpoint weirdness: A block may end with a conditional branch but
1131  // jumps to the same MBB is either case. We have duplicate CFG edges in that
1132  // case that we can't handle. Since this never happens in properly optimized
1133  // code, just skip those edges.
1134  if (TBB && TBB == FBB) {
1135  LLVM_DEBUG(dbgs() << "Won't split critical edge after degenerate "
1136  << printMBBReference(*this) << '\n');
1137  return false;
1138  }
1139  return true;
1140 }
1141 
1142 /// Prepare MI to be removed from its bundle. This fixes bundle flags on MI's
1143 /// neighboring instructions so the bundle won't be broken by removing MI.
1144 static void unbundleSingleMI(MachineInstr *MI) {
1145  // Removing the first instruction in a bundle.
1146  if (MI->isBundledWithSucc() && !MI->isBundledWithPred())
1147  MI->unbundleFromSucc();
1148  // Removing the last instruction in a bundle.
1149  if (MI->isBundledWithPred() && !MI->isBundledWithSucc())
1150  MI->unbundleFromPred();
1151  // If MI is not bundled, or if it is internal to a bundle, the neighbor flags
1152  // are already fine.
1153 }
1154 
1157  unbundleSingleMI(&*I);
1158  return Insts.erase(I);
1159 }
1160 
1162  unbundleSingleMI(MI);
1165  return Insts.remove(MI);
1166 }
1167 
1170  assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
1171  "Cannot insert instruction with bundle flags");
1172  // Set the bundle flags when inserting inside a bundle.
1173  if (I != instr_end() && I->isBundledWithPred()) {
1176  }
1177  return Insts.insert(I, MI);
1178 }
1179 
1180 /// This method unlinks 'this' from the containing function, and returns it, but
1181 /// does not delete it.
1183  assert(getParent() && "Not embedded in a function!");
1184  getParent()->remove(this);
1185  return this;
1186 }
1187 
1188 /// This method unlinks 'this' from the containing function, and deletes it.
1190  assert(getParent() && "Not embedded in a function!");
1191  getParent()->erase(this);
1192 }
1193 
1194 /// Given a machine basic block that branched to 'Old', change the code and CFG
1195 /// so that it branches to 'New' instead.
1197  MachineBasicBlock *New) {
1198  assert(Old != New && "Cannot replace self with self!");
1199 
1201  while (I != instr_begin()) {
1202  --I;
1203  if (!I->isTerminator()) break;
1204 
1205  // Scan the operands of this machine instruction, replacing any uses of Old
1206  // with New.
1207  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1208  if (I->getOperand(i).isMBB() &&
1209  I->getOperand(i).getMBB() == Old)
1210  I->getOperand(i).setMBB(New);
1211  }
1212 
1213  // Update the successor information.
1214  replaceSuccessor(Old, New);
1215 }
1216 
1217 /// Various pieces of code can cause excess edges in the CFG to be inserted. If
1218 /// we have proven that MBB can only branch to DestA and DestB, remove any other
1219 /// MBB successors from the CFG. DestA and DestB can be null.
1220 ///
1221 /// Besides DestA and DestB, retain other edges leading to LandingPads
1222 /// (currently there can be only one; we don't check or require that here).
1223 /// Note it is possible that DestA and/or DestB are LandingPads.
1225  MachineBasicBlock *DestB,
1226  bool IsCond) {
1227  // The values of DestA and DestB frequently come from a call to the
1228  // 'TargetInstrInfo::AnalyzeBranch' method. We take our meaning of the initial
1229  // values from there.
1230  //
1231  // 1. If both DestA and DestB are null, then the block ends with no branches
1232  // (it falls through to its successor).
1233  // 2. If DestA is set, DestB is null, and IsCond is false, then the block ends
1234  // with only an unconditional branch.
1235  // 3. If DestA is set, DestB is null, and IsCond is true, then the block ends
1236  // with a conditional branch that falls through to a successor (DestB).
1237  // 4. If DestA and DestB is set and IsCond is true, then the block ends with a
1238  // conditional branch followed by an unconditional branch. DestA is the
1239  // 'true' destination and DestB is the 'false' destination.
1240 
1241  bool Changed = false;
1242 
1243  MachineBasicBlock *FallThru = getNextNode();
1244 
1245  if (!DestA && !DestB) {
1246  // Block falls through to successor.
1247  DestA = FallThru;
1248  DestB = FallThru;
1249  } else if (DestA && !DestB) {
1250  if (IsCond)
1251  // Block ends in conditional jump that falls through to successor.
1252  DestB = FallThru;
1253  } else {
1254  assert(DestA && DestB && IsCond &&
1255  "CFG in a bad state. Cannot correct CFG edges");
1256  }
1257 
1258  // Remove superfluous edges. I.e., those which aren't destinations of this
1259  // basic block, duplicate edges, or landing pads.
1262  while (SI != succ_end()) {
1263  const MachineBasicBlock *MBB = *SI;
1264  if (!SeenMBBs.insert(MBB).second ||
1265  (MBB != DestA && MBB != DestB && !MBB->isEHPad())) {
1266  // This is a superfluous edge, remove it.
1267  SI = removeSuccessor(SI);
1268  Changed = true;
1269  } else {
1270  ++SI;
1271  }
1272  }
1273 
1274  if (Changed)
1276  return Changed;
1277 }
1278 
1279 /// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE
1280 /// instructions. Return UnknownLoc if there is none.
1281 DebugLoc
1283  // Skip debug declarations, we don't want a DebugLoc from them.
1284  MBBI = skipDebugInstructionsForward(MBBI, instr_end());
1285  if (MBBI != instr_end())
1286  return MBBI->getDebugLoc();
1287  return {};
1288 }
1289 
1290 /// Find the previous valid DebugLoc preceding MBBI, skipping and DBG_VALUE
1291 /// instructions. Return UnknownLoc if there is none.
1293  if (MBBI == instr_begin()) return {};
1294  // Skip debug declarations, we don't want a DebugLoc from them.
1295  MBBI = skipDebugInstructionsBackward(std::prev(MBBI), instr_begin());
1296  if (!MBBI->isDebugInstr()) return MBBI->getDebugLoc();
1297  return {};
1298 }
1299 
1300 /// Find and return the merged DebugLoc of the branch instructions of the block.
1301 /// Return UnknownLoc if there is none.
1302 DebugLoc
1304  DebugLoc DL;
1305  auto TI = getFirstTerminator();
1306  while (TI != end() && !TI->isBranch())
1307  ++TI;
1308 
1309  if (TI != end()) {
1310  DL = TI->getDebugLoc();
1311  for (++TI ; TI != end() ; ++TI)
1312  if (TI->isBranch())
1313  DL = DILocation::getMergedLocation(DL, TI->getDebugLoc());
1314  }
1315  return DL;
1316 }
1317 
1318 /// Return probability of the edge from this block to MBB.
1320 MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const {
1321  if (Probs.empty())
1322  return BranchProbability(1, succ_size());
1323 
1324  const auto &Prob = *getProbabilityIterator(Succ);
1325  if (Prob.isUnknown()) {
1326  // For unknown probabilities, collect the sum of all known ones, and evenly
1327  // ditribute the complemental of the sum to each unknown probability.
1328  unsigned KnownProbNum = 0;
1329  auto Sum = BranchProbability::getZero();
1330  for (auto &P : Probs) {
1331  if (!P.isUnknown()) {
1332  Sum += P;
1333  KnownProbNum++;
1334  }
1335  }
1336  return Sum.getCompl() / (Probs.size() - KnownProbNum);
1337  } else
1338  return Prob;
1339 }
1340 
1341 /// Set successor probability of a given iterator.
1343  BranchProbability Prob) {
1344  assert(!Prob.isUnknown());
1345  if (Probs.empty())
1346  return;
1347  *getProbabilityIterator(I) = Prob;
1348 }
1349 
1350 /// Return probability iterator corresonding to the I successor iterator
1351 MachineBasicBlock::const_probability_iterator
1352 MachineBasicBlock::getProbabilityIterator(
1354  assert(Probs.size() == Successors.size() && "Async probability list!");
1355  const size_t index = std::distance(Successors.begin(), I);
1356  assert(index < Probs.size() && "Not a current successor!");
1357  return Probs.begin() + index;
1358 }
1359 
1360 /// Return probability iterator corresonding to the I successor iterator.
1361 MachineBasicBlock::probability_iterator
1362 MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) {
1363  assert(Probs.size() == Successors.size() && "Async probability list!");
1364  const size_t index = std::distance(Successors.begin(), I);
1365  assert(index < Probs.size() && "Not a current successor!");
1366  return Probs.begin() + index;
1367 }
1368 
1369 /// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed
1370 /// as of just before "MI".
1371 ///
1372 /// Search is localised to a neighborhood of
1373 /// Neighborhood instructions before (searching for defs or kills) and N
1374 /// instructions after (searching just for defs) MI.
1377  unsigned Reg, const_iterator Before,
1378  unsigned Neighborhood) const {
1379  unsigned N = Neighborhood;
1380 
1381  // Try searching forwards from Before, looking for reads or defs.
1382  const_iterator I(Before);
1383  // If this is the last insn in the block, don't search forwards.
1384  if (I != end()) {
1385  for (++I; I != end() && N > 0; ++I) {
1386  if (I->isDebugInstr())
1387  continue;
1388 
1389  --N;
1390 
1392  ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
1393 
1394  // Register is live when we read it here.
1395  if (Info.Read)
1396  return LQR_Live;
1397  // Register is dead if we can fully overwrite or clobber it here.
1398  if (Info.FullyDefined || Info.Clobbered)
1399  return LQR_Dead;
1400  }
1401  }
1402 
1403  // If we reached the end, it is safe to clobber Reg at the end of a block of
1404  // no successor has it live in.
1405  if (I == end()) {
1406  for (MachineBasicBlock *S : successors()) {
1407  for (MCSubRegIterator SubReg(Reg, TRI, /*IncludeSelf*/true);
1408  SubReg.isValid(); ++SubReg) {
1409  if (S->isLiveIn(*SubReg))
1410  return LQR_Live;
1411  }
1412  }
1413 
1414  return LQR_Dead;
1415  }
1416 
1417 
1418  N = Neighborhood;
1419 
1420  // Start by searching backwards from Before, looking for kills, reads or defs.
1421  I = const_iterator(Before);
1422  // If this is the first insn in the block, don't search backwards.
1423  if (I != begin()) {
1424  do {
1425  --I;
1426 
1427  if (I->isDebugInstr())
1428  continue;
1429 
1430  --N;
1431 
1433  ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
1434 
1435  // Defs happen after uses so they take precedence if both are present.
1436 
1437  // Register is dead after a dead def of the full register.
1438  if (Info.DeadDef)
1439  return LQR_Dead;
1440  // Register is (at least partially) live after a def.
1441  if (Info.Defined) {
1442  if (!Info.PartialDeadDef)
1443  return LQR_Live;
1444  // As soon as we saw a partial definition (dead or not),
1445  // we cannot tell if the value is partial live without
1446  // tracking the lanemasks. We are not going to do this,
1447  // so fall back on the remaining of the analysis.
1448  break;
1449  }
1450  // Register is dead after a full kill or clobber and no def.
1451  if (Info.Killed || Info.Clobbered)
1452  return LQR_Dead;
1453  // Register must be live if we read it.
1454  if (Info.Read)
1455  return LQR_Live;
1456 
1457  } while (I != begin() && N > 0);
1458  }
1459 
1460  // Did we get to the start of the block?
1461  if (I == begin()) {
1462  // If so, the register's state is definitely defined by the live-in state.
1463  for (MCRegAliasIterator RAI(Reg, TRI, /*IncludeSelf=*/true); RAI.isValid();
1464  ++RAI)
1465  if (isLiveIn(*RAI))
1466  return LQR_Live;
1467 
1468  return LQR_Dead;
1469  }
1470 
1471  // At this point we have no idea of the liveness of the register.
1472  return LQR_Unknown;
1473 }
1474 
1475 const uint32_t *
1477  // EH funclet entry does not preserve any registers.
1478  return isEHFuncletEntry() ? TRI->getNoPreservedMask() : nullptr;
1479 }
1480 
1481 const uint32_t *
1483  // If we see a return block with successors, this must be a funclet return,
1484  // which does not preserve any registers. If there are no successors, we don't
1485  // care what kind of return it is, putting a mask after it is a no-op.
1486  return isReturnBlock() && !succ_empty() ? TRI->getNoPreservedMask() : nullptr;
1487 }
1488 
1490  LiveIns.clear();
1491 }
1492 
1494  assert(getParent()->getProperties().hasProperty(
1496  "Liveness information is accurate");
1497  return LiveIns.begin();
1498 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
void print(raw_ostream &OS, const SlotIndexes *=nullptr, bool IsStandalone=true) const
const MCAsmInfo * getAsmInfo() const
Definition: MCContext.h:293
void push_back(const T &Elt)
Definition: SmallVector.h:218
mop_iterator operands_end()
Definition: MachineInstr.h:454
void validateSuccProbs() const
Validate successors&#39; probabilities and check if the sum of them is approximate one.
instr_iterator instr_begin()
instr_iterator instr_end()
MachineBasicBlock * getMBB() const
unsigned getFunctionNumber() const
getFunctionNumber - Return a unique ID for the current function.
MachineBasicBlock * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:289
const MachineFunction * getMF() const
Return the function that contains the basic block that this instruction belongs to.
iterator erase(iterator where)
Definition: ilist.h:267
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
void addNodeToList(NodeTy *)
When an MBB is added to an MF, we need to update the parent pointer of the MBB, the MBB numbering...
Definition: ilist.h:66
MCSymbol - Instances of this class represent a symbol name in the MC file, and MCSymbols are created ...
Definition: MCSymbol.h:42
LivenessQueryResult computeRegisterLiveness(const TargetRegisterInfo *TRI, unsigned Reg, const_iterator Before, unsigned Neighborhood=10) const
Return whether (physical) register Reg has been defined and not killed as of just before Before...
static unsigned index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:64
static const DILocation * getMergedLocation(const DILocation *LocA, const DILocation *LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
bool isBundledWithPred() const
Return true if this instruction is part of a bundle, and it is not the first instruction in the bundl...
Definition: MachineInstr.h:362
instr_iterator getFirstInstrTerminator()
Same getFirstTerminator but it ignores bundles and return an instr_iterator instead.
iterator getFirstNonDebugInstr()
Returns an iterator to the first non-debug instruction in the basic block, or end().
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:638
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
bool requiresStructuredCFG() const
unsigned getReg() const
getReg - Returns the register number.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB)
Transfers all the successors, as in transferSuccessors, and update PHI operands in the successor bloc...
unsigned Reg
void transferSuccessors(MachineBasicBlock *FromMBB)
Transfers all the successors from MBB to this machine basic block (i.e., copies all the successors Fr...
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:124
raw_ostream & indent(unsigned NumSpaces)
indent - Insert &#39;NumSpaces&#39; spaces.
int getLocalSlot(const Value *V)
Return the slot number of the specified local value.
Definition: AsmWriter.cpp:850
virtual const uint32_t * getNoPreservedMask() const
Return a register mask that clobbers everything.
virtual unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, ArrayRef< MachineOperand > Cond, const DebugLoc &DL, int *BytesAdded=nullptr) const
Insert branch code into the end of the specified MachineBasicBlock.
Template traits for intrusive list.
Definition: ilist.h:91
void addSuccessorWithoutProb(MachineBasicBlock *Succ)
Add Succ as a successor of this MachineBasicBlock.
This represents a simple continuous liveness interval for a value.
Definition: LiveInterval.h:162
void moveAfter(MachineBasicBlock *NewBefore)
unsigned const TargetRegisterInfo * TRI
A debug info location.
Definition: DebugLoc.h:34
Printable PrintLaneMask(LaneBitmask LaneMask)
Create Printable object to print LaneBitmasks on a raw_ostream.
Definition: LaneBitmask.h:94
F(f)
Manage lifetime of a slot tracker for printing IR.
MachineInstrBundleIterator< const MachineInstr > const_iterator
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
bool isPHI() const
virtual unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const
Remove the branching code at the end of the specific MBB.
MachineBasicBlock * removeFromParent()
This method unlinks &#39;this&#39; from the containing function, and returns it, but does not delete it...
BasicBlockListType::const_iterator const_iterator
void removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll())
Remove the specified register from the live in set.
iterator_range< succ_iterator > successors()
bool removeKill(MachineInstr &MI)
removeKill - Delete a kill corresponding to the specified machine instruction.
Definition: LiveVariables.h:94
void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New)
Given a machine basic block that branched to &#39;Old&#39;, change the code and CFG so that it branches to &#39;N...
void eraseFromParent()
This method unlinks &#39;this&#39; from the containing function and deletes it.
bool isReturnBlock() const
Convenience function that returns true if the block ends in a return instruction. ...
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
bool canSplitCriticalEdge(const MachineBasicBlock *Succ) const
Check if the edge between this block and the given successor Succ, can be split.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
const HexagonInstrInfo * TII
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
unsigned getNumOperands() const
Access to explicit operands of the instruction.
Definition: MachineInstr.h:412
Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
bool isBundledWithSucc() const
Return true if this instruction is part of a bundle, and it is not the last instruction in the bundle...
Definition: MachineInstr.h:366
const TargetMachine & getTarget() const
getTarget - Return the target machine this machine code is compiled with
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
MachineBasicBlock * getFallThrough()
Return the fallthrough block if the block can implicitly transfer control to the block after it by fa...
unsigned SubReg
SlotIndex getInstructionIndex(const MachineInstr &MI) const
Returns the base index for the given instruction.
Definition: SlotIndexes.h:414
static void unbundleSingleMI(MachineInstr *MI)
Prepare MI to be removed from its bundle.
MachineInstr * remove_instr(MachineInstr *I)
Remove the possibly bundled instruction from the instruction list without deleting it...
virtual bool isBasicBlockPrologue(const MachineInstr &MI) const
True if the instruction is bound to the top of its basic block and no other instructions shall be ins...
PhysRegInfo analyzePhysReg(unsigned Reg, const TargetRegisterInfo *TRI)
analyzePhysReg - Analyze how the current instruction or bundle uses a physical register.
LiveInVector::const_iterator livein_iterator
#define LLVM_DUMP_METHOD
Definition: Compiler.h:74
Context object for machine code objects.
Definition: MCContext.h:63
void unbundleFromPred()
Break bundle above this instruction.
DebugLoc findPrevDebugLoc(instr_iterator MBBI)
Find the previous valid DebugLoc preceding MBBI, skipping and DBG_VALUE instructions.
void insertMBBInMaps(MachineBasicBlock *MBB)
SlotIndexes pass.
Definition: SlotIndexes.h:331
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
const T & getValue() const LLVM_LVALUE_FUNCTION
Definition: Optional.h:183
bool canFallThrough()
Return true if the block can implicitly transfer control to the block after it by falling off the end...
iterator getLastNonDebugInstr()
Returns an iterator to the last non-debug instruction in the basic block, or end().
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
virtual const TargetInstrInfo * getInstrInfo() const
const uint32_t * getEndClobberMask(const TargetRegisterInfo *TRI) const
Get the clobber mask for the end of the basic block.
void setSuccProbability(succ_iterator I, BranchProbability Prob)
Set successor probability of a given iterator.
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
bool isInsideBundle() const
Return true if MI is in a bundle (but not the first MI in a bundle).
Definition: MachineInstr.h:350
bool PartialDeadDef
Reg is Defined and all defs of reg or an overlapping register are dead.
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
const TargetRegisterClass * constrainRegClass(unsigned Reg, const TargetRegisterClass *RC, unsigned MinNumRegs=0)
constrainRegClass - Constrain the register class of the specified virtual register to be a common sub...
BasicBlockListType::iterator iterator
void normalizeSuccProbs()
Normalize probabilities of all successors so that the sum of them becomes one.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
TargetInstrInfo - Interface to description of machine instruction set.
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
Definition: LiveInterval.h:409
MCContext & getContext() const
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
#define P(N)
void addLiveIn(MCPhysReg PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
iterator SkipPHIsAndLabels(iterator I)
Return the first instruction in MBB after I that is not a PHI or a label.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
unsigned const MachineRegisterInfo * MRI
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
bool hasInterval(unsigned Reg) const
bool hasName() const
Definition: Value.h:251
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
bool liveAt(SlotIndex index) const
Definition: LiveInterval.h:389
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:129
bool Read
Reg or one of its aliases is read.
DebugLoc findDebugLoc(instr_iterator MBBI)
Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE and DBG_LABEL instructions...
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:371
livein_iterator livein_end() const
unsigned getAlignment() const
Return alignment of the basic block.
bool Clobbered
There is a regmask operand indicating Reg is clobbered.
bool hasIndex(const MachineInstr &instr) const
Returns true if the given machine instr is mapped to an index, otherwise returns false.
Definition: SlotIndexes.h:409
bool isPredecessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a predecessor of this block.
void setMBB(MachineBasicBlock *MBB)
Register is known to be fully dead.
void setFlag(MIFlag Flag)
Set a MI flag.
Definition: MachineInstr.h:300
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Definition: SlotIndexes.h:489
MCRegAliasIterator enumerates all registers aliasing Reg.
void clearFlag(MIFlag Flag)
clearFlag - Clear a MI flag.
Definition: MachineInstr.h:311
StringRef getPrivateLabelPrefix() const
Definition: MCAsmInfo.h:492
bool isLegalToHoistInto() const
Returns true if it is legal to hoist instructions into this block.
void clearLiveIns()
Clear live in list.
bool Killed
There is a use operand of reg or a super-register with kill flag set.
std::vector< MachineBasicBlock * >::const_iterator const_succ_iterator
void remove(iterator MBBI)
self_iterator getIterator()
Definition: ilist_node.h:82
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:181
iterator_range< pred_iterator > predecessors()
void print(raw_ostream &OS, bool IsStandalone=true, bool SkipOpers=false, bool SkipDebugLoc=false, bool AddNewLine=true, const TargetInstrInfo *TII=nullptr) const
Print this MI to OS.
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1070
std::vector< MachineBasicBlock * >::iterator pred_iterator
LivenessQueryResult
Possible outcome of a register liveness query to computeRegisterLiveness()
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const
Return the first index in the given basic block.
Register is known to be (at least partially) live.
void incorporateFunction(const Function &F)
Incorporate the given function.
Definition: AsmWriter.cpp:836
void repairIntervalsInRange(MachineBasicBlock *MBB, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, ArrayRef< unsigned > OrigRegs)
Update live intervals for instructions in a range of iterators.
bool hasAddressTaken() const
Test whether this block is potentially the target of an indirect branch.
void moveBefore(MachineBasicBlock *NewAfter)
Move &#39;this&#39; block before or after the specified block.
VarInfo & getVarInfo(unsigned RegIdx)
getVarInfo - Return the VarInfo structure for the specified VIRTUAL register.
virtual bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify=false) const
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e...
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
MCSubRegIterator enumerates all sub-registers of Reg.
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1063
virtual bool isPredicated(const MachineInstr &MI) const
Returns true if the instruction is already predicated.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:972
void addNewBlock(MachineBasicBlock *BB, MachineBasicBlock *DomBB, MachineBasicBlock *SuccBB)
addNewBlock - Add a new basic block BB between DomBB and SuccBB.
std::vector< MachineInstr * > Kills
Kills - List of MachineInstruction&#39;s which are the last use of this virtual register (kill it) in the...
Definition: LiveVariables.h:89
static BranchProbability getUnknown()
void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified segment from this range.
uint32_t Number
Definition: Profile.cpp:48
Iterator for intrusive lists based on ilist_node.
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
static uint32_t getDenominator()
void splice(iterator InsertPt, iterator MBBI)
void removeNodeFromList(NodeTy *)
Definition: ilist.h:67
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
void updateTerminator()
Update the terminator instructions in block to account for changes to the layout. ...
bool FullyDefined
Reg or a super-register is defined.
LiveInterval & getInterval(unsigned Reg)
static void deleteNode(NodeTy *V)
Definition: ilist.h:42
void sortUniqueLiveIns()
Sorts and uniques the LiveIns vector.
bool isLayoutSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB will be emitted immediately after this block, such that if this bloc...
IterT skipDebugInstructionsBackward(IterT It, IterT Begin)
Decrement It until it points to a non-debug instruction or to Begin and return the resulting iterator...
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
ConstMIOperands - Iterate over operands of a single const instruction.
void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New)
Replace successor OLD with NEW and update probability info.
DebugLoc findBranchDebugLoc()
Find and return the merged DebugLoc of the branch instructions of the block.
unsigned succ_size() const
IterT skipDebugInstructionsForward(IterT It, IterT End)
Increment It until it points to a non-debug instruction or to End and return the resulting iterator...
void copySuccessor(MachineBasicBlock *Orig, succ_iterator I)
Copy a successor (and any probability info) from original block to this block&#39;s.
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:254
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:64
pointer remove(iterator &IT)
Definition: ilist.h:251
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:133
iterator insert(iterator where, pointer New)
Definition: ilist.h:228
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
MCSymbol * getOrCreateSymbol(const Twine &Name)
Lookup the symbol inside with the specified Name.
Definition: MCContext.cpp:123
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
Definition: SlotIndexes.h:290
bool isEHPad() const
Returns true if the block is a landing pad.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
bool isEHFuncletEntry() const
Returns true if this is the entry block of an EH funclet.
Register liveness not decidable from local neighborhood.
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:45
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
MCSymbol * getSymbol() const
Return the MCSymbol for this basic block.
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
APFloat abs(APFloat X)
Returns the absolute value of the argument.
Definition: APFloat.h:1213
Pair of physical register and lane mask.
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
Optional< uint64_t > getIrrLoopHeaderWeight() const
Definition: BasicBlock.cpp:470
bool tracksLiveness() const
tracksLiveness - Returns true when tracking register liveness accurately.
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
Information about how a physical register Reg is used by a set of operands.
void removeFromMBBNumbering(unsigned N)
removeFromMBBNumbering - Remove the specific machine basic block from our tracker, this is only really to be used by the MachineBasicBlock implementation.
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2033
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
void splitSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New, bool NormalizeSuccProbs=false)
Split the old successor into old plus new and updates the probability info.
iterator_range< livein_iterator > liveins() const
Instructions::iterator instr_iterator
bool Defined
Reg or one of its aliases is defined.
virtual bool reverseBranchCondition(SmallVectorImpl< MachineOperand > &Cond) const
Reverses the branch condition of the specified condition list, returning false on success and true if...
void erase(iterator MBBI)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void insert(iterator MBBI, MachineBasicBlock *MBB)
MachineBasicBlock * SplitCriticalEdge(MachineBasicBlock *Succ, Pass &P)
Split the critical edge from this block to the given successor block, and return the newly created bl...
void unbundleFromSucc()
Break bundle below this instruction.
std::string getFullName() const
Return a formatted string to identify this block and its parent function.
unsigned addToMBBNumbering(MachineBasicBlock *MBB)
Adds the MBB to the internal numbering.
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:566
mop_iterator operands_begin()
Definition: MachineInstr.h:453
AnalysisType * getAnalysisIfAvailable() const
getAnalysisIfAvailable<AnalysisType>() - Subclasses use this function to get analysis information tha...
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
static bool isLiveOut(const MachineBasicBlock &MBB, unsigned Reg)
iterator SkipPHIsLabelsAndDebug(iterator I)
Return the first instruction in MBB after I that is not a PHI, label or debug.
IRTranslator LLVM IR MI
bool isBarrier(QueryType Type=AnyInBundle) const
Returns true if the specified instruction stops control flow from executing the instruction immediate...
Definition: MachineInstr.h:640
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
void printAsOperand(raw_ostream &OS, bool PrintType=true) const
static BranchProbability getZero()
const uint32_t * getBeginClobberMask(const TargetRegisterInfo *TRI) const
Get the clobber mask for the start of this basic block.
Simple wrapper around std::function<void(raw_ostream&)>.
Definition: Printable.h:38
#define LLVM_DEBUG(X)
Definition: Debug.h:123
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:414
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:84
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
uint32_t getNumerator() const
bool getFlag(MIFlag Flag) const
Return whether an MI flag is set.
Definition: MachineInstr.h:295
std::vector< MachineBasicBlock * >::iterator succ_iterator
livein_iterator livein_begin() const
unsigned createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
bool CorrectExtraCFGEdges(MachineBasicBlock *DestA, MachineBasicBlock *DestB, bool IsCond)
Various pieces of code can cause excess edges in the CFG to be inserted.
void transferNodesFromList(ilist_callback_traits &OldList, Iterator, Iterator)
Callback before transferring nodes to this list.
Definition: ilist.h:73
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:165
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:1101