LLVM  7.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 }
114 
115 /// When we remove an instruction from a basic block list, we update its parent
116 /// pointer and remove its operands from reg use/def lists if appropriate.
118  assert(N->getParent() && "machine instruction not in a basic block");
119 
120  // Remove from the use/def lists.
121  if (MachineFunction *MF = N->getMF())
122  N->RemoveRegOperandsFromUseLists(MF->getRegInfo());
123 
124  N->setParent(nullptr);
125 }
126 
127 /// When moving a range of instructions from one MBB list to another, we need to
128 /// update the parent pointers and the use/def lists.
130  instr_iterator First,
131  instr_iterator Last) {
132  assert(Parent->getParent() == FromList.Parent->getParent() &&
133  "MachineInstr parent mismatch!");
134  assert(this != &FromList && "Called without a real transfer...");
135  assert(Parent != FromList.Parent && "Two lists have the same parent?");
136 
137  // If splicing between two blocks within the same function, just update the
138  // parent pointers.
139  for (; First != Last; ++First)
140  First->setParent(Parent);
141 }
142 
144  assert(!MI->getParent() && "MI is still in a block!");
145  Parent->getParent()->DeleteMachineInstr(MI);
146 }
147 
150  while (I != E && I->isPHI())
151  ++I;
152  assert((I == E || !I->isInsideBundle()) &&
153  "First non-phi MI cannot be inside a bundle!");
154  return I;
155 }
156 
160 
161  iterator E = end();
162  while (I != E && (I->isPHI() || I->isPosition() ||
163  TII->isBasicBlockPrologue(*I)))
164  ++I;
165  // FIXME: This needs to change if we wish to bundle labels
166  // inside the bundle.
167  assert((I == E || !I->isInsideBundle()) &&
168  "First non-phi / non-label instruction is inside a bundle!");
169  return I;
170 }
171 
175 
176  iterator E = end();
177  while (I != E && (I->isPHI() || I->isPosition() || I->isDebugInstr() ||
178  TII->isBasicBlockPrologue(*I)))
179  ++I;
180  // FIXME: This needs to change if we wish to bundle labels / dbg_values
181  // inside the bundle.
182  assert((I == E || !I->isInsideBundle()) &&
183  "First non-phi / non-label / non-debug "
184  "instruction is inside a bundle!");
185  return I;
186 }
187 
189  iterator B = begin(), E = end(), I = E;
190  while (I != B && ((--I)->isTerminator() || I->isDebugInstr()))
191  ; /*noop */
192  while (I != E && !I->isTerminator())
193  ++I;
194  return I;
195 }
196 
198  instr_iterator B = instr_begin(), E = instr_end(), I = E;
199  while (I != B && ((--I)->isTerminator() || I->isDebugInstr()))
200  ; /*noop */
201  while (I != E && !I->isTerminator())
202  ++I;
203  return I;
204 }
205 
207  // Skip over begin-of-block dbg_value instructions.
209 }
210 
212  // Skip over end-of-block dbg_value instructions.
214  while (I != B) {
215  --I;
216  // Return instruction that starts a bundle.
217  if (I->isDebugInstr() || I->isInsideBundle())
218  continue;
219  return I;
220  }
221  // The block is all debug values.
222  return end();
223 }
224 
226  for (const_succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I)
227  if ((*I)->isEHPad())
228  return true;
229  return false;
230 }
231 
232 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
234  print(dbgs());
235 }
236 #endif
237 
239  if (isReturnBlock() || hasEHPadSuccessor())
240  return false;
241  return true;
242 }
243 
245  if (const BasicBlock *LBB = getBasicBlock())
246  return LBB->getName();
247  else
248  return StringRef("", 0);
249 }
250 
251 /// Return a hopefully unique identifier for this block.
252 std::string MachineBasicBlock::getFullName() const {
253  std::string Name;
254  if (getParent())
255  Name = (getParent()->getName() + ":").str();
256  if (getBasicBlock())
257  Name += getBasicBlock()->getName();
258  else
259  Name += ("BB" + Twine(getNumber())).str();
260  return Name;
261 }
262 
264  bool IsStandalone) const {
265  const MachineFunction *MF = getParent();
266  if (!MF) {
267  OS << "Can't print out MachineBasicBlock because parent MachineFunction"
268  << " is null\n";
269  return;
270  }
271  const Function &F = MF->getFunction();
272  const Module *M = F.getParent();
273  ModuleSlotTracker MST(M);
274  MST.incorporateFunction(F);
275  print(OS, MST, Indexes, IsStandalone);
276 }
277 
279  const SlotIndexes *Indexes,
280  bool IsStandalone) const {
281  const MachineFunction *MF = getParent();
282  if (!MF) {
283  OS << "Can't print out MachineBasicBlock because parent MachineFunction"
284  << " is null\n";
285  return;
286  }
287 
288  if (Indexes)
289  OS << Indexes->getMBBStartIdx(this) << '\t';
290 
291  OS << "bb." << getNumber();
292  bool HasAttributes = false;
293  if (const auto *BB = getBasicBlock()) {
294  if (BB->hasName()) {
295  OS << "." << BB->getName();
296  } else {
297  HasAttributes = true;
298  OS << " (";
299  int Slot = MST.getLocalSlot(BB);
300  if (Slot == -1)
301  OS << "<ir-block badref>";
302  else
303  OS << (Twine("%ir-block.") + Twine(Slot)).str();
304  }
305  }
306 
307  if (hasAddressTaken()) {
308  OS << (HasAttributes ? ", " : " (");
309  OS << "address-taken";
310  HasAttributes = true;
311  }
312  if (isEHPad()) {
313  OS << (HasAttributes ? ", " : " (");
314  OS << "landing-pad";
315  HasAttributes = true;
316  }
317  if (getAlignment()) {
318  OS << (HasAttributes ? ", " : " (");
319  OS << "align " << getAlignment();
320  HasAttributes = true;
321  }
322  if (HasAttributes)
323  OS << ")";
324  OS << ":\n";
325 
327  const MachineRegisterInfo &MRI = MF->getRegInfo();
329  bool HasLineAttributes = false;
330 
331  // Print the preds of this block according to the CFG.
332  if (!pred_empty() && IsStandalone) {
333  if (Indexes) OS << '\t';
334  // Don't indent(2), align with previous line attributes.
335  OS << "; predecessors: ";
336  for (auto I = pred_begin(), E = pred_end(); I != E; ++I) {
337  if (I != pred_begin())
338  OS << ", ";
339  OS << printMBBReference(**I);
340  }
341  OS << '\n';
342  HasLineAttributes = true;
343  }
344 
345  if (!succ_empty()) {
346  if (Indexes) OS << '\t';
347  // Print the successors
348  OS.indent(2) << "successors: ";
349  for (auto I = succ_begin(), E = succ_end(); I != E; ++I) {
350  if (I != succ_begin())
351  OS << ", ";
352  OS << printMBBReference(**I);
353  if (!Probs.empty())
354  OS << '('
355  << format("0x%08" PRIx32, getSuccProbability(I).getNumerator())
356  << ')';
357  }
358  if (!Probs.empty() && IsStandalone) {
359  // Print human readable probabilities as comments.
360  OS << "; ";
361  for (auto I = succ_begin(), E = succ_end(); I != E; ++I) {
362  const BranchProbability &BP = *getProbabilityIterator(I);
363  if (I != succ_begin())
364  OS << ", ";
365  OS << printMBBReference(**I) << '('
366  << format("%.2f%%",
367  rint(((double)BP.getNumerator() / BP.getDenominator()) *
368  100.0 * 100.0) /
369  100.0)
370  << ')';
371  }
372  }
373 
374  OS << '\n';
375  HasLineAttributes = true;
376  }
377 
378  if (!livein_empty() && MRI.tracksLiveness()) {
379  if (Indexes) OS << '\t';
380  OS.indent(2) << "liveins: ";
381 
382  bool First = true;
383  for (const auto &LI : liveins()) {
384  if (!First)
385  OS << ", ";
386  First = false;
387  OS << printReg(LI.PhysReg, TRI);
388  if (!LI.LaneMask.all())
389  OS << ":0x" << PrintLaneMask(LI.LaneMask);
390  }
391  HasLineAttributes = true;
392  }
393 
394  if (HasLineAttributes)
395  OS << '\n';
396 
397  bool IsInBundle = false;
398  for (const MachineInstr &MI : instrs()) {
399  if (Indexes) {
400  if (Indexes->hasIndex(MI))
401  OS << Indexes->getInstructionIndex(MI);
402  OS << '\t';
403  }
404 
405  if (IsInBundle && !MI.isInsideBundle()) {
406  OS.indent(2) << "}\n";
407  IsInBundle = false;
408  }
409 
410  OS.indent(IsInBundle ? 4 : 2);
411  MI.print(OS, MST, IsStandalone, /*SkipOpers=*/false, /*SkipDebugLoc=*/false,
412  /*AddNewLine=*/false, &TII);
413 
414  if (!IsInBundle && MI.getFlag(MachineInstr::BundledSucc)) {
415  OS << " {";
416  IsInBundle = true;
417  }
418  OS << '\n';
419  }
420 
421  if (IsInBundle)
422  OS.indent(2) << "}\n";
423 
424  if (IrrLoopHeaderWeight && IsStandalone) {
425  if (Indexes) OS << '\t';
426  OS.indent(2) << "; Irreducible loop header weight: "
427  << IrrLoopHeaderWeight.getValue() << '\n';
428  }
429 }
430 
432  bool /*PrintType*/) const {
433  OS << "%bb." << getNumber();
434 }
435 
437  LiveInVector::iterator I = find_if(
438  LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
439  if (I == LiveIns.end())
440  return;
441 
442  I->LaneMask &= ~LaneMask;
443  if (I->LaneMask.none())
444  LiveIns.erase(I);
445 }
446 
449  // Get non-const version of iterator.
450  LiveInVector::iterator LI = LiveIns.begin() + (I - LiveIns.begin());
451  return LiveIns.erase(LI);
452 }
453 
456  LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
457  return I != livein_end() && (I->LaneMask & LaneMask).any();
458 }
459 
461  llvm::sort(LiveIns.begin(), LiveIns.end(),
462  [](const RegisterMaskPair &LI0, const RegisterMaskPair &LI1) {
463  return LI0.PhysReg < LI1.PhysReg;
464  });
465  // Liveins are sorted by physreg now we can merge their lanemasks.
466  LiveInVector::const_iterator I = LiveIns.begin();
467  LiveInVector::const_iterator J;
468  LiveInVector::iterator Out = LiveIns.begin();
469  for (; I != LiveIns.end(); ++Out, I = J) {
470  unsigned PhysReg = I->PhysReg;
471  LaneBitmask LaneMask = I->LaneMask;
472  for (J = std::next(I); J != LiveIns.end() && J->PhysReg == PhysReg; ++J)
473  LaneMask |= J->LaneMask;
474  Out->PhysReg = PhysReg;
475  Out->LaneMask = LaneMask;
476  }
477  LiveIns.erase(Out, LiveIns.end());
478 }
479 
480 unsigned
482  assert(getParent() && "MBB must be inserted in function");
483  assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && "Expected physreg");
484  assert(RC && "Register class is required");
485  assert((isEHPad() || this == &getParent()->front()) &&
486  "Only the entry block and landing pads can have physreg live ins");
487 
488  bool LiveIn = isLiveIn(PhysReg);
492 
493  // Look for an existing copy.
494  if (LiveIn)
495  for (;I != E && I->isCopy(); ++I)
496  if (I->getOperand(1).getReg() == PhysReg) {
497  unsigned VirtReg = I->getOperand(0).getReg();
498  if (!MRI.constrainRegClass(VirtReg, RC))
499  llvm_unreachable("Incompatible live-in register class.");
500  return VirtReg;
501  }
502 
503  // No luck, create a virtual register.
504  unsigned VirtReg = MRI.createVirtualRegister(RC);
505  BuildMI(*this, I, DebugLoc(), TII.get(TargetOpcode::COPY), VirtReg)
506  .addReg(PhysReg, RegState::Kill);
507  if (!LiveIn)
508  addLiveIn(PhysReg);
509  return VirtReg;
510 }
511 
513  getParent()->splice(NewAfter->getIterator(), getIterator());
514 }
515 
517  getParent()->splice(++NewBefore->getIterator(), getIterator());
518 }
519 
522  // A block with no successors has no concerns with fall-through edges.
523  if (this->succ_empty())
524  return;
525 
526  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
529  bool B = TII->analyzeBranch(*this, TBB, FBB, Cond);
530  (void) B;
531  assert(!B && "UpdateTerminators requires analyzable predecessors!");
532  if (Cond.empty()) {
533  if (TBB) {
534  // The block has an unconditional branch. If its successor is now its
535  // layout successor, delete the branch.
536  if (isLayoutSuccessor(TBB))
537  TII->removeBranch(*this);
538  } else {
539  // The block has an unconditional fallthrough. If its successor is not its
540  // layout successor, insert a branch. First we have to locate the only
541  // non-landing-pad successor, as that is the fallthrough block.
542  for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) {
543  if ((*SI)->isEHPad())
544  continue;
545  assert(!TBB && "Found more than one non-landing-pad successor!");
546  TBB = *SI;
547  }
548 
549  // If there is no non-landing-pad successor, the block has no fall-through
550  // edges to be concerned with.
551  if (!TBB)
552  return;
553 
554  // Finally update the unconditional successor to be reached via a branch
555  // if it would not be reached by fallthrough.
556  if (!isLayoutSuccessor(TBB))
557  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
558  }
559  return;
560  }
561 
562  if (FBB) {
563  // The block has a non-fallthrough conditional branch. If one of its
564  // successors is its layout successor, rewrite it to a fallthrough
565  // conditional branch.
566  if (isLayoutSuccessor(TBB)) {
567  if (TII->reverseBranchCondition(Cond))
568  return;
569  TII->removeBranch(*this);
570  TII->insertBranch(*this, FBB, nullptr, Cond, DL);
571  } else if (isLayoutSuccessor(FBB)) {
572  TII->removeBranch(*this);
573  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
574  }
575  return;
576  }
577 
578  // Walk through the successors and find the successor which is not a landing
579  // pad and is not the conditional branch destination (in TBB) as the
580  // fallthrough successor.
581  MachineBasicBlock *FallthroughBB = nullptr;
582  for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) {
583  if ((*SI)->isEHPad() || *SI == TBB)
584  continue;
585  assert(!FallthroughBB && "Found more than one fallthrough successor.");
586  FallthroughBB = *SI;
587  }
588 
589  if (!FallthroughBB) {
590  if (canFallThrough()) {
591  // We fallthrough to the same basic block as the conditional jump targets.
592  // Remove the conditional jump, leaving unconditional fallthrough.
593  // FIXME: This does not seem like a reasonable pattern to support, but it
594  // has been seen in the wild coming out of degenerate ARM test cases.
595  TII->removeBranch(*this);
596 
597  // Finally update the unconditional successor to be reached via a branch if
598  // it would not be reached by fallthrough.
599  if (!isLayoutSuccessor(TBB))
600  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
601  return;
602  }
603 
604  // We enter here iff exactly one successor is TBB which cannot fallthrough
605  // and the rest successors if any are EHPads. In this case, we need to
606  // change the conditional branch into unconditional branch.
607  TII->removeBranch(*this);
608  Cond.clear();
609  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
610  return;
611  }
612 
613  // The block has a fallthrough conditional branch.
614  if (isLayoutSuccessor(TBB)) {
615  if (TII->reverseBranchCondition(Cond)) {
616  // We can't reverse the condition, add an unconditional branch.
617  Cond.clear();
618  TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
619  return;
620  }
621  TII->removeBranch(*this);
622  TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
623  } else if (!isLayoutSuccessor(FallthroughBB)) {
624  TII->removeBranch(*this);
625  TII->insertBranch(*this, TBB, FallthroughBB, Cond, DL);
626  }
627 }
628 
630 #ifndef NDEBUG
631  int64_t Sum = 0;
632  for (auto Prob : Probs)
633  Sum += Prob.getNumerator();
634  // Due to precision issue, we assume that the sum of probabilities is one if
635  // the difference between the sum of their numerators and the denominator is
636  // no greater than the number of successors.
638  Probs.size() &&
639  "The sum of successors's probabilities exceeds one.");
640 #endif // NDEBUG
641 }
642 
644  BranchProbability Prob) {
645  // Probability list is either empty (if successor list isn't empty, this means
646  // disabled optimization) or has the same size as successor list.
647  if (!(Probs.empty() && !Successors.empty()))
648  Probs.push_back(Prob);
649  Successors.push_back(Succ);
650  Succ->addPredecessor(this);
651 }
652 
654  // We need to make sure probability list is either empty or has the same size
655  // of successor list. When this function is called, we can safely delete all
656  // probability in the list.
657  Probs.clear();
658  Successors.push_back(Succ);
659  Succ->addPredecessor(this);
660 }
661 
663  MachineBasicBlock *New,
664  bool NormalizeSuccProbs) {
665  succ_iterator OldI = llvm::find(successors(), Old);
666  assert(OldI != succ_end() && "Old is not a successor of this block!");
667  assert(llvm::find(successors(), New) == succ_end() &&
668  "New is already a successor of this block!");
669 
670  // Add a new successor with equal probability as the original one. Note
671  // that we directly copy the probability using the iterator rather than
672  // getting a potentially synthetic probability computed when unknown. This
673  // preserves the probabilities as-is and then we can renormalize them and
674  // query them effectively afterward.
675  addSuccessor(New, Probs.empty() ? BranchProbability::getUnknown()
676  : *getProbabilityIterator(OldI));
677  if (NormalizeSuccProbs)
679 }
680 
682  bool NormalizeSuccProbs) {
683  succ_iterator I = find(Successors, Succ);
684  removeSuccessor(I, NormalizeSuccProbs);
685 }
686 
689  assert(I != Successors.end() && "Not a current successor!");
690 
691  // If probability list is empty it means we don't use it (disabled
692  // optimization).
693  if (!Probs.empty()) {
694  probability_iterator WI = getProbabilityIterator(I);
695  Probs.erase(WI);
696  if (NormalizeSuccProbs)
698  }
699 
700  (*I)->removePredecessor(this);
701  return Successors.erase(I);
702 }
703 
705  MachineBasicBlock *New) {
706  if (Old == New)
707  return;
708 
710  succ_iterator NewI = E;
711  succ_iterator OldI = E;
712  for (succ_iterator I = succ_begin(); I != E; ++I) {
713  if (*I == Old) {
714  OldI = I;
715  if (NewI != E)
716  break;
717  }
718  if (*I == New) {
719  NewI = I;
720  if (OldI != E)
721  break;
722  }
723  }
724  assert(OldI != E && "Old is not a successor of this block");
725 
726  // If New isn't already a successor, let it take Old's place.
727  if (NewI == E) {
728  Old->removePredecessor(this);
729  New->addPredecessor(this);
730  *OldI = New;
731  return;
732  }
733 
734  // New is already a successor.
735  // Update its probability instead of adding a duplicate edge.
736  if (!Probs.empty()) {
737  auto ProbIter = getProbabilityIterator(NewI);
738  if (!ProbIter->isUnknown())
739  *ProbIter += *getProbabilityIterator(OldI);
740  }
741  removeSuccessor(OldI);
742 }
743 
745  succ_iterator I) {
746  if (Orig->Probs.empty())
747  addSuccessor(*I, Orig->getSuccProbability(I));
748  else
750 }
751 
752 void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) {
753  Predecessors.push_back(Pred);
754 }
755 
756 void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) {
757  pred_iterator I = find(Predecessors, Pred);
758  assert(I != Predecessors.end() && "Pred is not a predecessor of this block!");
759  Predecessors.erase(I);
760 }
761 
763  if (this == FromMBB)
764  return;
765 
766  while (!FromMBB->succ_empty()) {
767  MachineBasicBlock *Succ = *FromMBB->succ_begin();
768 
769  // If probability list is empty it means we don't use it (disabled optimization).
770  if (!FromMBB->Probs.empty()) {
771  auto Prob = *FromMBB->Probs.begin();
772  addSuccessor(Succ, Prob);
773  } else
775 
776  FromMBB->removeSuccessor(Succ);
777  }
778 }
779 
780 void
782  if (this == FromMBB)
783  return;
784 
785  while (!FromMBB->succ_empty()) {
786  MachineBasicBlock *Succ = *FromMBB->succ_begin();
787  if (!FromMBB->Probs.empty()) {
788  auto Prob = *FromMBB->Probs.begin();
789  addSuccessor(Succ, Prob);
790  } else
792  FromMBB->removeSuccessor(Succ);
793 
794  // Fix up any PHI nodes in the successor.
796  ME = Succ->instr_end(); MI != ME && MI->isPHI(); ++MI)
797  for (unsigned i = 2, e = MI->getNumOperands()+1; i != e; i += 2) {
798  MachineOperand &MO = MI->getOperand(i);
799  if (MO.getMBB() == FromMBB)
800  MO.setMBB(this);
801  }
802  }
804 }
805 
807  return is_contained(predecessors(), MBB);
808 }
809 
811  return is_contained(successors(), MBB);
812 }
813 
816  return std::next(I) == MachineFunction::const_iterator(MBB);
817 }
818 
820  MachineFunction::iterator Fallthrough = getIterator();
821  ++Fallthrough;
822  // If FallthroughBlock is off the end of the function, it can't fall through.
823  if (Fallthrough == getParent()->end())
824  return nullptr;
825 
826  // If FallthroughBlock isn't a successor, no fallthrough is possible.
827  if (!isSuccessor(&*Fallthrough))
828  return nullptr;
829 
830  // Analyze the branches, if any, at the end of the block.
831  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
834  if (TII->analyzeBranch(*this, TBB, FBB, Cond)) {
835  // If we couldn't analyze the branch, examine the last instruction.
836  // If the block doesn't end in a known control barrier, assume fallthrough
837  // is possible. The isPredicated check is needed because this code can be
838  // called during IfConversion, where an instruction which is normally a
839  // Barrier is predicated and thus no longer an actual control barrier.
840  return (empty() || !back().isBarrier() || TII->isPredicated(back()))
841  ? &*Fallthrough
842  : nullptr;
843  }
844 
845  // If there is no branch, control always falls through.
846  if (!TBB) return &*Fallthrough;
847 
848  // If there is some explicit branch to the fallthrough block, it can obviously
849  // reach, even though the branch should get folded to fall through implicitly.
850  if (MachineFunction::iterator(TBB) == Fallthrough ||
851  MachineFunction::iterator(FBB) == Fallthrough)
852  return &*Fallthrough;
853 
854  // If it's an unconditional branch to some block not the fall through, it
855  // doesn't fall through.
856  if (Cond.empty()) return nullptr;
857 
858  // Otherwise, if it is conditional and has no explicit false block, it falls
859  // through.
860  return (FBB == nullptr) ? &*Fallthrough : nullptr;
861 }
862 
864  return getFallThrough() != nullptr;
865 }
866 
868  Pass &P) {
869  if (!canSplitCriticalEdge(Succ))
870  return nullptr;
871 
872  MachineFunction *MF = getParent();
873  DebugLoc DL; // FIXME: this is nowhere
874 
876  MF->insert(std::next(MachineFunction::iterator(this)), NMBB);
877  LLVM_DEBUG(dbgs() << "Splitting critical edge: " << printMBBReference(*this)
878  << " -- " << printMBBReference(*NMBB) << " -- "
879  << printMBBReference(*Succ) << '\n');
880 
883  if (LIS)
884  LIS->insertMBBInMaps(NMBB);
885  else if (Indexes)
886  Indexes->insertMBBInMaps(NMBB);
887 
888  // On some targets like Mips, branches may kill virtual registers. Make sure
889  // that LiveVariables is properly updated after updateTerminator replaces the
890  // terminators.
892 
893  // Collect a list of virtual registers killed by the terminators.
894  SmallVector<unsigned, 4> KilledRegs;
895  if (LV)
897  I != E; ++I) {
898  MachineInstr *MI = &*I;
900  OE = MI->operands_end(); OI != OE; ++OI) {
901  if (!OI->isReg() || OI->getReg() == 0 ||
902  !OI->isUse() || !OI->isKill() || OI->isUndef())
903  continue;
904  unsigned Reg = OI->getReg();
906  LV->getVarInfo(Reg).removeKill(*MI)) {
907  KilledRegs.push_back(Reg);
908  LLVM_DEBUG(dbgs() << "Removing terminator kill: " << *MI);
909  OI->setIsKill(false);
910  }
911  }
912  }
913 
914  SmallVector<unsigned, 4> UsedRegs;
915  if (LIS) {
917  I != E; ++I) {
918  MachineInstr *MI = &*I;
919 
921  OE = MI->operands_end(); OI != OE; ++OI) {
922  if (!OI->isReg() || OI->getReg() == 0)
923  continue;
924 
925  unsigned Reg = OI->getReg();
926  if (!is_contained(UsedRegs, Reg))
927  UsedRegs.push_back(Reg);
928  }
929  }
930  }
931 
932  ReplaceUsesOfBlockWith(Succ, NMBB);
933 
934  // If updateTerminator() removes instructions, we need to remove them from
935  // SlotIndexes.
936  SmallVector<MachineInstr*, 4> Terminators;
937  if (Indexes) {
939  I != E; ++I)
940  Terminators.push_back(&*I);
941  }
942 
944 
945  if (Indexes) {
946  SmallVector<MachineInstr*, 4> NewTerminators;
948  I != E; ++I)
949  NewTerminators.push_back(&*I);
950 
951  for (SmallVectorImpl<MachineInstr*>::iterator I = Terminators.begin(),
952  E = Terminators.end(); I != E; ++I) {
953  if (!is_contained(NewTerminators, *I))
954  Indexes->removeMachineInstrFromMaps(**I);
955  }
956  }
957 
958  // Insert unconditional "jump Succ" instruction in NMBB if necessary.
959  NMBB->addSuccessor(Succ);
960  if (!NMBB->isLayoutSuccessor(Succ)) {
963  TII->insertBranch(*NMBB, Succ, nullptr, Cond, DL);
964 
965  if (Indexes) {
966  for (MachineInstr &MI : NMBB->instrs()) {
967  // Some instructions may have been moved to NMBB by updateTerminator(),
968  // so we first remove any instruction that already has an index.
969  if (Indexes->hasIndex(MI))
970  Indexes->removeMachineInstrFromMaps(MI);
971  Indexes->insertMachineInstrInMaps(MI);
972  }
973  }
974  }
975 
976  // Fix PHI nodes in Succ so they refer to NMBB instead of this
978  i = Succ->instr_begin(),e = Succ->instr_end();
979  i != e && i->isPHI(); ++i)
980  for (unsigned ni = 1, ne = i->getNumOperands(); ni != ne; ni += 2)
981  if (i->getOperand(ni+1).getMBB() == this)
982  i->getOperand(ni+1).setMBB(NMBB);
983 
984  // Inherit live-ins from the successor
985  for (const auto &LI : Succ->liveins())
986  NMBB->addLiveIn(LI);
987 
988  // Update LiveVariables.
990  if (LV) {
991  // Restore kills of virtual registers that were killed by the terminators.
992  while (!KilledRegs.empty()) {
993  unsigned Reg = KilledRegs.pop_back_val();
994  for (instr_iterator I = instr_end(), E = instr_begin(); I != E;) {
995  if (!(--I)->addRegisterKilled(Reg, TRI, /* addIfNotFound= */ false))
996  continue;
998  LV->getVarInfo(Reg).Kills.push_back(&*I);
999  LLVM_DEBUG(dbgs() << "Restored terminator kill: " << *I);
1000  break;
1001  }
1002  }
1003  // Update relevant live-through information.
1004  LV->addNewBlock(NMBB, this, Succ);
1005  }
1006 
1007  if (LIS) {
1008  // After splitting the edge and updating SlotIndexes, live intervals may be
1009  // in one of two situations, depending on whether this block was the last in
1010  // the function. If the original block was the last in the function, all
1011  // live intervals will end prior to the beginning of the new split block. If
1012  // the original block was not at the end of the function, all live intervals
1013  // will extend to the end of the new split block.
1014 
1015  bool isLastMBB =
1016  std::next(MachineFunction::iterator(NMBB)) == getParent()->end();
1017 
1018  SlotIndex StartIndex = Indexes->getMBBEndIdx(this);
1019  SlotIndex PrevIndex = StartIndex.getPrevSlot();
1020  SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB);
1021 
1022  // Find the registers used from NMBB in PHIs in Succ.
1023  SmallSet<unsigned, 8> PHISrcRegs;
1025  I = Succ->instr_begin(), E = Succ->instr_end();
1026  I != E && I->isPHI(); ++I) {
1027  for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne; ni += 2) {
1028  if (I->getOperand(ni+1).getMBB() == NMBB) {
1029  MachineOperand &MO = I->getOperand(ni);
1030  unsigned Reg = MO.getReg();
1031  PHISrcRegs.insert(Reg);
1032  if (MO.isUndef())
1033  continue;
1034 
1035  LiveInterval &LI = LIS->getInterval(Reg);
1036  VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
1037  assert(VNI &&
1038  "PHI sources should be live out of their predecessors.");
1039  LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1040  }
1041  }
1042  }
1043 
1045  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1046  unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
1047  if (PHISrcRegs.count(Reg) || !LIS->hasInterval(Reg))
1048  continue;
1049 
1050  LiveInterval &LI = LIS->getInterval(Reg);
1051  if (!LI.liveAt(PrevIndex))
1052  continue;
1053 
1054  bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ));
1055  if (isLiveOut && isLastMBB) {
1056  VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
1057  assert(VNI && "LiveInterval should have VNInfo where it is live.");
1058  LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1059  } else if (!isLiveOut && !isLastMBB) {
1060  LI.removeSegment(StartIndex, EndIndex);
1061  }
1062  }
1063 
1064  // Update all intervals for registers whose uses may have been modified by
1065  // updateTerminator().
1066  LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs);
1067  }
1068 
1069  if (MachineDominatorTree *MDT =
1071  MDT->recordSplitCriticalEdge(this, Succ, NMBB);
1072 
1074  if (MachineLoop *TIL = MLI->getLoopFor(this)) {
1075  // If one or the other blocks were not in a loop, the new block is not
1076  // either, and thus LI doesn't need to be updated.
1077  if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) {
1078  if (TIL == DestLoop) {
1079  // Both in the same loop, the NMBB joins loop.
1080  DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
1081  } else if (TIL->contains(DestLoop)) {
1082  // Edge from an outer loop to an inner loop. Add to the outer loop.
1083  TIL->addBasicBlockToLoop(NMBB, MLI->getBase());
1084  } else if (DestLoop->contains(TIL)) {
1085  // Edge from an inner loop to an outer loop. Add to the outer loop.
1086  DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
1087  } else {
1088  // Edge from two loops with no containment relation. Because these
1089  // are natural loops, we know that the destination block must be the
1090  // header of its loop (adding a branch into a loop elsewhere would
1091  // create an irreducible loop).
1092  assert(DestLoop->getHeader() == Succ &&
1093  "Should not create irreducible loops!");
1094  if (MachineLoop *P = DestLoop->getParentLoop())
1095  P->addBasicBlockToLoop(NMBB, MLI->getBase());
1096  }
1097  }
1098  }
1099 
1100  return NMBB;
1101 }
1102 
1104  const MachineBasicBlock *Succ) const {
1105  // Splitting the critical edge to a landing pad block is non-trivial. Don't do
1106  // it in this generic function.
1107  if (Succ->isEHPad())
1108  return false;
1109 
1110  const MachineFunction *MF = getParent();
1111 
1112  // Performance might be harmed on HW that implements branching using exec mask
1113  // where both sides of the branches are always executed.
1114  if (MF->getTarget().requiresStructuredCFG())
1115  return false;
1116 
1117  // We may need to update this's terminator, but we can't do that if
1118  // AnalyzeBranch fails. If this uses a jump table, we won't touch it.
1119  const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
1120  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1122  // AnalyzeBanch should modify this, since we did not allow modification.
1123  if (TII->analyzeBranch(*const_cast<MachineBasicBlock *>(this), TBB, FBB, Cond,
1124  /*AllowModify*/ false))
1125  return false;
1126 
1127  // Avoid bugpoint weirdness: A block may end with a conditional branch but
1128  // jumps to the same MBB is either case. We have duplicate CFG edges in that
1129  // case that we can't handle. Since this never happens in properly optimized
1130  // code, just skip those edges.
1131  if (TBB && TBB == FBB) {
1132  LLVM_DEBUG(dbgs() << "Won't split critical edge after degenerate "
1133  << printMBBReference(*this) << '\n');
1134  return false;
1135  }
1136  return true;
1137 }
1138 
1139 /// Prepare MI to be removed from its bundle. This fixes bundle flags on MI's
1140 /// neighboring instructions so the bundle won't be broken by removing MI.
1141 static void unbundleSingleMI(MachineInstr *MI) {
1142  // Removing the first instruction in a bundle.
1143  if (MI->isBundledWithSucc() && !MI->isBundledWithPred())
1144  MI->unbundleFromSucc();
1145  // Removing the last instruction in a bundle.
1146  if (MI->isBundledWithPred() && !MI->isBundledWithSucc())
1147  MI->unbundleFromPred();
1148  // If MI is not bundled, or if it is internal to a bundle, the neighbor flags
1149  // are already fine.
1150 }
1151 
1154  unbundleSingleMI(&*I);
1155  return Insts.erase(I);
1156 }
1157 
1159  unbundleSingleMI(MI);
1162  return Insts.remove(MI);
1163 }
1164 
1167  assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
1168  "Cannot insert instruction with bundle flags");
1169  // Set the bundle flags when inserting inside a bundle.
1170  if (I != instr_end() && I->isBundledWithPred()) {
1173  }
1174  return Insts.insert(I, MI);
1175 }
1176 
1177 /// This method unlinks 'this' from the containing function, and returns it, but
1178 /// does not delete it.
1180  assert(getParent() && "Not embedded in a function!");
1181  getParent()->remove(this);
1182  return this;
1183 }
1184 
1185 /// This method unlinks 'this' from the containing function, and deletes it.
1187  assert(getParent() && "Not embedded in a function!");
1188  getParent()->erase(this);
1189 }
1190 
1191 /// Given a machine basic block that branched to 'Old', change the code and CFG
1192 /// so that it branches to 'New' instead.
1194  MachineBasicBlock *New) {
1195  assert(Old != New && "Cannot replace self with self!");
1196 
1198  while (I != instr_begin()) {
1199  --I;
1200  if (!I->isTerminator()) break;
1201 
1202  // Scan the operands of this machine instruction, replacing any uses of Old
1203  // with New.
1204  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1205  if (I->getOperand(i).isMBB() &&
1206  I->getOperand(i).getMBB() == Old)
1207  I->getOperand(i).setMBB(New);
1208  }
1209 
1210  // Update the successor information.
1211  replaceSuccessor(Old, New);
1212 }
1213 
1214 /// Various pieces of code can cause excess edges in the CFG to be inserted. If
1215 /// we have proven that MBB can only branch to DestA and DestB, remove any other
1216 /// MBB successors from the CFG. DestA and DestB can be null.
1217 ///
1218 /// Besides DestA and DestB, retain other edges leading to LandingPads
1219 /// (currently there can be only one; we don't check or require that here).
1220 /// Note it is possible that DestA and/or DestB are LandingPads.
1222  MachineBasicBlock *DestB,
1223  bool IsCond) {
1224  // The values of DestA and DestB frequently come from a call to the
1225  // 'TargetInstrInfo::AnalyzeBranch' method. We take our meaning of the initial
1226  // values from there.
1227  //
1228  // 1. If both DestA and DestB are null, then the block ends with no branches
1229  // (it falls through to its successor).
1230  // 2. If DestA is set, DestB is null, and IsCond is false, then the block ends
1231  // with only an unconditional branch.
1232  // 3. If DestA is set, DestB is null, and IsCond is true, then the block ends
1233  // with a conditional branch that falls through to a successor (DestB).
1234  // 4. If DestA and DestB is set and IsCond is true, then the block ends with a
1235  // conditional branch followed by an unconditional branch. DestA is the
1236  // 'true' destination and DestB is the 'false' destination.
1237 
1238  bool Changed = false;
1239 
1240  MachineBasicBlock *FallThru = getNextNode();
1241 
1242  if (!DestA && !DestB) {
1243  // Block falls through to successor.
1244  DestA = FallThru;
1245  DestB = FallThru;
1246  } else if (DestA && !DestB) {
1247  if (IsCond)
1248  // Block ends in conditional jump that falls through to successor.
1249  DestB = FallThru;
1250  } else {
1251  assert(DestA && DestB && IsCond &&
1252  "CFG in a bad state. Cannot correct CFG edges");
1253  }
1254 
1255  // Remove superfluous edges. I.e., those which aren't destinations of this
1256  // basic block, duplicate edges, or landing pads.
1259  while (SI != succ_end()) {
1260  const MachineBasicBlock *MBB = *SI;
1261  if (!SeenMBBs.insert(MBB).second ||
1262  (MBB != DestA && MBB != DestB && !MBB->isEHPad())) {
1263  // This is a superfluous edge, remove it.
1264  SI = removeSuccessor(SI);
1265  Changed = true;
1266  } else {
1267  ++SI;
1268  }
1269  }
1270 
1271  if (Changed)
1273  return Changed;
1274 }
1275 
1276 /// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE
1277 /// instructions. Return UnknownLoc if there is none.
1278 DebugLoc
1280  // Skip debug declarations, we don't want a DebugLoc from them.
1281  MBBI = skipDebugInstructionsForward(MBBI, instr_end());
1282  if (MBBI != instr_end())
1283  return MBBI->getDebugLoc();
1284  return {};
1285 }
1286 
1287 /// Find the previous valid DebugLoc preceding MBBI, skipping and DBG_VALUE
1288 /// instructions. Return UnknownLoc if there is none.
1290  if (MBBI == instr_begin()) return {};
1291  // Skip debug declarations, we don't want a DebugLoc from them.
1292  MBBI = skipDebugInstructionsBackward(std::prev(MBBI), instr_begin());
1293  if (!MBBI->isDebugInstr()) return MBBI->getDebugLoc();
1294  return {};
1295 }
1296 
1297 /// Find and return the merged DebugLoc of the branch instructions of the block.
1298 /// Return UnknownLoc if there is none.
1299 DebugLoc
1301  DebugLoc DL;
1302  auto TI = getFirstTerminator();
1303  while (TI != end() && !TI->isBranch())
1304  ++TI;
1305 
1306  if (TI != end()) {
1307  DL = TI->getDebugLoc();
1308  for (++TI ; TI != end() ; ++TI)
1309  if (TI->isBranch())
1310  DL = DILocation::getMergedLocation(DL, TI->getDebugLoc());
1311  }
1312  return DL;
1313 }
1314 
1315 /// Return probability of the edge from this block to MBB.
1317 MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const {
1318  if (Probs.empty())
1319  return BranchProbability(1, succ_size());
1320 
1321  const auto &Prob = *getProbabilityIterator(Succ);
1322  if (Prob.isUnknown()) {
1323  // For unknown probabilities, collect the sum of all known ones, and evenly
1324  // ditribute the complemental of the sum to each unknown probability.
1325  unsigned KnownProbNum = 0;
1326  auto Sum = BranchProbability::getZero();
1327  for (auto &P : Probs) {
1328  if (!P.isUnknown()) {
1329  Sum += P;
1330  KnownProbNum++;
1331  }
1332  }
1333  return Sum.getCompl() / (Probs.size() - KnownProbNum);
1334  } else
1335  return Prob;
1336 }
1337 
1338 /// Set successor probability of a given iterator.
1340  BranchProbability Prob) {
1341  assert(!Prob.isUnknown());
1342  if (Probs.empty())
1343  return;
1344  *getProbabilityIterator(I) = Prob;
1345 }
1346 
1347 /// Return probability iterator corresonding to the I successor iterator
1348 MachineBasicBlock::const_probability_iterator
1349 MachineBasicBlock::getProbabilityIterator(
1351  assert(Probs.size() == Successors.size() && "Async probability list!");
1352  const size_t index = std::distance(Successors.begin(), I);
1353  assert(index < Probs.size() && "Not a current successor!");
1354  return Probs.begin() + index;
1355 }
1356 
1357 /// Return probability iterator corresonding to the I successor iterator.
1358 MachineBasicBlock::probability_iterator
1359 MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) {
1360  assert(Probs.size() == Successors.size() && "Async probability list!");
1361  const size_t index = std::distance(Successors.begin(), I);
1362  assert(index < Probs.size() && "Not a current successor!");
1363  return Probs.begin() + index;
1364 }
1365 
1366 /// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed
1367 /// as of just before "MI".
1368 ///
1369 /// Search is localised to a neighborhood of
1370 /// Neighborhood instructions before (searching for defs or kills) and N
1371 /// instructions after (searching just for defs) MI.
1374  unsigned Reg, const_iterator Before,
1375  unsigned Neighborhood) const {
1376  unsigned N = Neighborhood;
1377 
1378  // Start by searching backwards from Before, looking for kills, reads or defs.
1379  const_iterator I(Before);
1380  // If this is the first insn in the block, don't search backwards.
1381  if (I != begin()) {
1382  do {
1383  --I;
1384 
1386  ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
1387 
1388  // Defs happen after uses so they take precedence if both are present.
1389 
1390  // Register is dead after a dead def of the full register.
1391  if (Info.DeadDef)
1392  return LQR_Dead;
1393  // Register is (at least partially) live after a def.
1394  if (Info.Defined) {
1395  if (!Info.PartialDeadDef)
1396  return LQR_Live;
1397  // As soon as we saw a partial definition (dead or not),
1398  // we cannot tell if the value is partial live without
1399  // tracking the lanemasks. We are not going to do this,
1400  // so fall back on the remaining of the analysis.
1401  break;
1402  }
1403  // Register is dead after a full kill or clobber and no def.
1404  if (Info.Killed || Info.Clobbered)
1405  return LQR_Dead;
1406  // Register must be live if we read it.
1407  if (Info.Read)
1408  return LQR_Live;
1409  } while (I != begin() && --N > 0);
1410  }
1411 
1412  // Did we get to the start of the block?
1413  if (I == begin()) {
1414  // If so, the register's state is definitely defined by the live-in state.
1415  for (MCRegAliasIterator RAI(Reg, TRI, /*IncludeSelf=*/true); RAI.isValid();
1416  ++RAI)
1417  if (isLiveIn(*RAI))
1418  return LQR_Live;
1419 
1420  return LQR_Dead;
1421  }
1422 
1423  N = Neighborhood;
1424 
1425  // Try searching forwards from Before, looking for reads or defs.
1426  I = const_iterator(Before);
1427  // If this is the last insn in the block, don't search forwards.
1428  if (I != end()) {
1429  for (++I; I != end() && N > 0; ++I, --N) {
1431  ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
1432 
1433  // Register is live when we read it here.
1434  if (Info.Read)
1435  return LQR_Live;
1436  // Register is dead if we can fully overwrite or clobber it here.
1437  if (Info.FullyDefined || Info.Clobbered)
1438  return LQR_Dead;
1439  }
1440  }
1441 
1442  // At this point we have no idea of the liveness of the register.
1443  return LQR_Unknown;
1444 }
1445 
1446 const uint32_t *
1448  // EH funclet entry does not preserve any registers.
1449  return isEHFuncletEntry() ? TRI->getNoPreservedMask() : nullptr;
1450 }
1451 
1452 const uint32_t *
1454  // If we see a return block with successors, this must be a funclet return,
1455  // which does not preserve any registers. If there are no successors, we don't
1456  // care what kind of return it is, putting a mask after it is a no-op.
1457  return isReturnBlock() && !succ_empty() ? TRI->getNoPreservedMask() : nullptr;
1458 }
1459 
1461  LiveIns.clear();
1462 }
1463 
1465  assert(getParent()->getProperties().hasProperty(
1467  "Liveness information is accurate");
1468  return LiveIns.begin();
1469 }
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:213
mop_iterator operands_end()
Definition: MachineInstr.h:356
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:63
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:264
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:849
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)
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:452
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
Definition: MachineInstr.h:861
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:314
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:268
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...
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
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:179
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:252
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:117
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:202
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Definition: SlotIndexes.h:487
MCRegAliasIterator enumerates all registers aliasing Reg.
void clearFlag(MIFlag Flag)
clearFlag - Clear a MI flag.
Definition: MachineInstr.h:213
StringRef getPrivateLabelPrefix() const
Definition: MCAsmInfo.h:487
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:81
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:936
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:835
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...
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:929
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:859
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.
static const DILocation * getMergedLocation(const DILocation *LocA, const DILocation *LocB, bool GenerateLocation=NoGeneratedLocation)
When two instructions are combined into a single instruction we also need to combine the original loc...
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:861
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:156
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:60
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:121
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:62
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:2032
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:565
mop_iterator operands_begin()
Definition: MachineInstr.h:355
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:492
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:119
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:316
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:197
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:65
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:967