LLVM  10.0.0svn
MachineBasicBlock.cpp
Go to the documentation of this file.
1 //===-- llvm/CodeGen/MachineBasicBlock.cpp ----------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Collect the sequence of machine instructions for a basic block.
10 //
11 //===----------------------------------------------------------------------===//
12 
14 #include "llvm/ADT/SmallPtrSet.h"
26 #include "llvm/Config/llvm-config.h"
27 #include "llvm/IR/BasicBlock.h"
28 #include "llvm/IR/DataLayout.h"
31 #include "llvm/MC/MCAsmInfo.h"
32 #include "llvm/MC/MCContext.h"
33 #include "llvm/Support/DataTypes.h"
34 #include "llvm/Support/Debug.h"
37 #include <algorithm>
38 using namespace llvm;
39 
40 #define DEBUG_TYPE "codegen"
41 
43  "print-slotindexes",
44  cl::desc("When printing machine IR, annotate instructions and blocks with "
45  "SlotIndexes when available"),
46  cl::init(true), cl::Hidden);
47 
48 MachineBasicBlock::MachineBasicBlock(MachineFunction &MF, const BasicBlock *B)
49  : BB(B), Number(-1), xParent(&MF) {
50  Insts.Parent = this;
51  if (B)
52  IrrLoopHeaderWeight = B->getIrrLoopHeaderWeight();
53 }
54 
55 MachineBasicBlock::~MachineBasicBlock() {
56 }
57 
58 /// Return the MCSymbol for this basic block.
60  if (!CachedMCSymbol) {
61  const MachineFunction *MF = getParent();
62  MCContext &Ctx = MF->getContext();
63  auto Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix();
64  assert(getNumber() >= 0 && "cannot get label for unreachable MBB");
65  CachedMCSymbol = Ctx.getOrCreateSymbol(Twine(Prefix) + "BB" +
66  Twine(MF->getFunctionNumber()) +
67  "_" + Twine(getNumber()));
68  }
69 
70  return CachedMCSymbol;
71 }
72 
73 
75  MBB.print(OS);
76  return OS;
77 }
78 
80  return Printable([&MBB](raw_ostream &OS) { return MBB.printAsOperand(OS); });
81 }
82 
83 /// When an MBB is added to an MF, we need to update the parent pointer of the
84 /// MBB, the MBB numbering, and any instructions in the MBB to be on the right
85 /// operand list for registers.
86 ///
87 /// MBBs start out as #-1. When a MBB is added to a MachineFunction, it
88 /// gets the next available unique MBB number. If it is removed from a
89 /// MachineFunction, it goes back to being #-1.
92  MachineFunction &MF = *N->getParent();
93  N->Number = MF.addToMBBNumbering(N);
94 
95  // Make sure the instructions have their operands in the reginfo lists.
96  MachineRegisterInfo &RegInfo = MF.getRegInfo();
98  I = N->instr_begin(), E = N->instr_end(); I != E; ++I)
99  I->AddRegOperandsToUseLists(RegInfo);
100 }
101 
103  MachineBasicBlock *N) {
104  N->getParent()->removeFromMBBNumbering(N->Number);
105  N->Number = -1;
106 }
107 
108 /// When we add an instruction to a basic block list, we update its parent
109 /// pointer and add its operands from reg use/def lists if appropriate.
111  assert(!N->getParent() && "machine instruction already in a basic block");
112  N->setParent(Parent);
113 
114  // Add the instruction's register operands to their corresponding
115  // use/def lists.
116  MachineFunction *MF = Parent->getParent();
117  N->AddRegOperandsToUseLists(MF->getRegInfo());
118  MF->handleInsertion(*N);
119 }
120 
121 /// When we remove an instruction from a basic block list, we update its parent
122 /// pointer and remove its operands from reg use/def lists if appropriate.
124  assert(N->getParent() && "machine instruction not in a basic block");
125 
126  // Remove from the use/def lists.
127  if (MachineFunction *MF = N->getMF()) {
128  MF->handleRemoval(*N);
129  N->RemoveRegOperandsFromUseLists(MF->getRegInfo());
130  }
131 
132  N->setParent(nullptr);
133 }
134 
135 /// When moving a range of instructions from one MBB list to another, we need to
136 /// update the parent pointers and the use/def lists.
138  instr_iterator First,
139  instr_iterator Last) {
140  assert(Parent->getParent() == FromList.Parent->getParent() &&
141  "cannot transfer MachineInstrs between MachineFunctions");
142 
143  // If it's within the same BB, there's nothing to do.
144  if (this == &FromList)
145  return;
146 
147  assert(Parent != FromList.Parent && "Two lists have the same parent?");
148 
149  // If splicing between two blocks within the same function, just update the
150  // parent pointers.
151  for (; First != Last; ++First)
152  First->setParent(Parent);
153 }
154 
156  assert(!MI->getParent() && "MI is still in a block!");
157  Parent->getParent()->DeleteMachineInstr(MI);
158 }
159 
162  while (I != E && I->isPHI())
163  ++I;
164  assert((I == E || !I->isInsideBundle()) &&
165  "First non-phi MI cannot be inside a bundle!");
166  return I;
167 }
168 
172 
173  iterator E = end();
174  while (I != E && (I->isPHI() || I->isPosition() ||
175  TII->isBasicBlockPrologue(*I)))
176  ++I;
177  // FIXME: This needs to change if we wish to bundle labels
178  // inside the bundle.
179  assert((I == E || !I->isInsideBundle()) &&
180  "First non-phi / non-label instruction is inside a bundle!");
181  return I;
182 }
183 
187 
188  iterator E = end();
189  while (I != E && (I->isPHI() || I->isPosition() || I->isDebugInstr() ||
190  TII->isBasicBlockPrologue(*I)))
191  ++I;
192  // FIXME: This needs to change if we wish to bundle labels / dbg_values
193  // inside the bundle.
194  assert((I == E || !I->isInsideBundle()) &&
195  "First non-phi / non-label / non-debug "
196  "instruction is inside a bundle!");
197  return I;
198 }
199 
201  iterator B = begin(), E = 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  instr_iterator B = instr_begin(), E = instr_end(), I = E;
211  while (I != B && ((--I)->isTerminator() || I->isDebugInstr()))
212  ; /*noop */
213  while (I != E && !I->isTerminator())
214  ++I;
215  return I;
216 }
217 
219  // Skip over begin-of-block dbg_value instructions.
221 }
222 
224  // Skip over end-of-block dbg_value instructions.
226  while (I != B) {
227  --I;
228  // Return instruction that starts a bundle.
229  if (I->isDebugInstr() || I->isInsideBundle())
230  continue;
231  return I;
232  }
233  // The block is all debug values.
234  return end();
235 }
236 
238  for (const_succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I)
239  if ((*I)->isEHPad())
240  return true;
241  return false;
242 }
243 
244 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
246  print(dbgs());
247 }
248 #endif
249 
251  if (isReturnBlock() || hasEHPadSuccessor())
252  return false;
253  return true;
254 }
255 
257  if (const BasicBlock *LBB = getBasicBlock())
258  return LBB->getName();
259  else
260  return StringRef("", 0);
261 }
262 
263 /// Return a hopefully unique identifier for this block.
264 std::string MachineBasicBlock::getFullName() const {
265  std::string Name;
266  if (getParent())
267  Name = (getParent()->getName() + ":").str();
268  if (getBasicBlock())
269  Name += getBasicBlock()->getName();
270  else
271  Name += ("BB" + Twine(getNumber())).str();
272  return Name;
273 }
274 
276  bool IsStandalone) const {
277  const MachineFunction *MF = getParent();
278  if (!MF) {
279  OS << "Can't print out MachineBasicBlock because parent MachineFunction"
280  << " is null\n";
281  return;
282  }
283  const Function &F = MF->getFunction();
284  const Module *M = F.getParent();
285  ModuleSlotTracker MST(M);
286  MST.incorporateFunction(F);
287  print(OS, MST, Indexes, IsStandalone);
288 }
289 
291  const SlotIndexes *Indexes,
292  bool IsStandalone) const {
293  const MachineFunction *MF = getParent();
294  if (!MF) {
295  OS << "Can't print out MachineBasicBlock because parent MachineFunction"
296  << " is null\n";
297  return;
298  }
299 
300  if (Indexes && PrintSlotIndexes)
301  OS << Indexes->getMBBStartIdx(this) << '\t';
302 
303  OS << "bb." << getNumber();
304  bool HasAttributes = false;
305  if (const auto *BB = getBasicBlock()) {
306  if (BB->hasName()) {
307  OS << "." << BB->getName();
308  } else {
309  HasAttributes = true;
310  OS << " (";
311  int Slot = MST.getLocalSlot(BB);
312  if (Slot == -1)
313  OS << "<ir-block badref>";
314  else
315  OS << (Twine("%ir-block.") + Twine(Slot)).str();
316  }
317  }
318 
319  if (hasAddressTaken()) {
320  OS << (HasAttributes ? ", " : " (");
321  OS << "address-taken";
322  HasAttributes = true;
323  }
324  if (isEHPad()) {
325  OS << (HasAttributes ? ", " : " (");
326  OS << "landing-pad";
327  HasAttributes = true;
328  }
329  if (getAlignment() != llvm::Align::None()) {
330  OS << (HasAttributes ? ", " : " (");
331  OS << "align " << Log2(getAlignment());
332  HasAttributes = true;
333  }
334  if (HasAttributes)
335  OS << ")";
336  OS << ":\n";
337 
339  const MachineRegisterInfo &MRI = MF->getRegInfo();
341  bool HasLineAttributes = false;
342 
343  // Print the preds of this block according to the CFG.
344  if (!pred_empty() && IsStandalone) {
345  if (Indexes) OS << '\t';
346  // Don't indent(2), align with previous line attributes.
347  OS << "; predecessors: ";
348  for (auto I = pred_begin(), E = pred_end(); I != E; ++I) {
349  if (I != pred_begin())
350  OS << ", ";
351  OS << printMBBReference(**I);
352  }
353  OS << '\n';
354  HasLineAttributes = true;
355  }
356 
357  if (!succ_empty()) {
358  if (Indexes) OS << '\t';
359  // Print the successors
360  OS.indent(2) << "successors: ";
361  for (auto I = succ_begin(), E = succ_end(); I != E; ++I) {
362  if (I != succ_begin())
363  OS << ", ";
364  OS << printMBBReference(**I);
365  if (!Probs.empty())
366  OS << '('
367  << format("0x%08" PRIx32, getSuccProbability(I).getNumerator())
368  << ')';
369  }
370  if (!Probs.empty() && IsStandalone) {
371  // Print human readable probabilities as comments.
372  OS << "; ";
373  for (auto I = succ_begin(), E = succ_end(); I != E; ++I) {
374  const BranchProbability &BP = getSuccProbability(I);
375  if (I != succ_begin())
376  OS << ", ";
377  OS << printMBBReference(**I) << '('
378  << format("%.2f%%",
379  rint(((double)BP.getNumerator() / BP.getDenominator()) *
380  100.0 * 100.0) /
381  100.0)
382  << ')';
383  }
384  }
385 
386  OS << '\n';
387  HasLineAttributes = true;
388  }
389 
390  if (!livein_empty() && MRI.tracksLiveness()) {
391  if (Indexes) OS << '\t';
392  OS.indent(2) << "liveins: ";
393 
394  bool First = true;
395  for (const auto &LI : liveins()) {
396  if (!First)
397  OS << ", ";
398  First = false;
399  OS << printReg(LI.PhysReg, TRI);
400  if (!LI.LaneMask.all())
401  OS << ":0x" << PrintLaneMask(LI.LaneMask);
402  }
403  HasLineAttributes = true;
404  }
405 
406  if (HasLineAttributes)
407  OS << '\n';
408 
409  bool IsInBundle = false;
410  for (const MachineInstr &MI : instrs()) {
411  if (Indexes && PrintSlotIndexes) {
412  if (Indexes->hasIndex(MI))
413  OS << Indexes->getInstructionIndex(MI);
414  OS << '\t';
415  }
416 
417  if (IsInBundle && !MI.isInsideBundle()) {
418  OS.indent(2) << "}\n";
419  IsInBundle = false;
420  }
421 
422  OS.indent(IsInBundle ? 4 : 2);
423  MI.print(OS, MST, IsStandalone, /*SkipOpers=*/false, /*SkipDebugLoc=*/false,
424  /*AddNewLine=*/false, &TII);
425 
426  if (!IsInBundle && MI.getFlag(MachineInstr::BundledSucc)) {
427  OS << " {";
428  IsInBundle = true;
429  }
430  OS << '\n';
431  }
432 
433  if (IsInBundle)
434  OS.indent(2) << "}\n";
435 
436  if (IrrLoopHeaderWeight && IsStandalone) {
437  if (Indexes) OS << '\t';
438  OS.indent(2) << "; Irreducible loop header weight: "
439  << IrrLoopHeaderWeight.getValue() << '\n';
440  }
441 }
442 
444  bool /*PrintType*/) const {
445  OS << "%bb." << getNumber();
446 }
447 
449  LiveInVector::iterator I = find_if(
450  LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
451  if (I == LiveIns.end())
452  return;
453 
454  I->LaneMask &= ~LaneMask;
455  if (I->LaneMask.none())
456  LiveIns.erase(I);
457 }
458 
461  // Get non-const version of iterator.
462  LiveInVector::iterator LI = LiveIns.begin() + (I - LiveIns.begin());
463  return LiveIns.erase(LI);
464 }
465 
468  LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
469  return I != livein_end() && (I->LaneMask & LaneMask).any();
470 }
471 
473  llvm::sort(LiveIns,
474  [](const RegisterMaskPair &LI0, const RegisterMaskPair &LI1) {
475  return LI0.PhysReg < LI1.PhysReg;
476  });
477  // Liveins are sorted by physreg now we can merge their lanemasks.
478  LiveInVector::const_iterator I = LiveIns.begin();
479  LiveInVector::const_iterator J;
480  LiveInVector::iterator Out = LiveIns.begin();
481  for (; I != LiveIns.end(); ++Out, I = J) {
482  unsigned PhysReg = I->PhysReg;
483  LaneBitmask LaneMask = I->LaneMask;
484  for (J = std::next(I); J != LiveIns.end() && J->PhysReg == PhysReg; ++J)
485  LaneMask |= J->LaneMask;
486  Out->PhysReg = PhysReg;
487  Out->LaneMask = LaneMask;
488  }
489  LiveIns.erase(Out, LiveIns.end());
490 }
491 
492 unsigned
494  assert(getParent() && "MBB must be inserted in function");
495  assert(PhysReg.isPhysical() && "Expected physreg");
496  assert(RC && "Register class is required");
497  assert((isEHPad() || this == &getParent()->front()) &&
498  "Only the entry block and landing pads can have physreg live ins");
499 
500  bool LiveIn = isLiveIn(PhysReg);
504 
505  // Look for an existing copy.
506  if (LiveIn)
507  for (;I != E && I->isCopy(); ++I)
508  if (I->getOperand(1).getReg() == PhysReg) {
509  Register VirtReg = I->getOperand(0).getReg();
510  if (!MRI.constrainRegClass(VirtReg, RC))
511  llvm_unreachable("Incompatible live-in register class.");
512  return VirtReg;
513  }
514 
515  // No luck, create a virtual register.
516  Register VirtReg = MRI.createVirtualRegister(RC);
517  BuildMI(*this, I, DebugLoc(), TII.get(TargetOpcode::COPY), VirtReg)
518  .addReg(PhysReg, RegState::Kill);
519  if (!LiveIn)
520  addLiveIn(PhysReg);
521  return VirtReg;
522 }
523 
525  getParent()->splice(NewAfter->getIterator(), getIterator());
526 }
527 
529  getParent()->splice(++NewBefore->getIterator(), getIterator());
530 }
531 
534  // A block with no successors has no concerns with fall-through edges.
535  if (this->succ_empty())
536  return;
537 
538  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
541  bool B = TII->analyzeBranch(*this, TBB, FBB, Cond);
542  (void) B;
543  assert(!B && "UpdateTerminators requires analyzable predecessors!");
544  if (Cond.empty()) {
545  if (TBB) {
546  // The block has an unconditional branch. If its successor is now its
547  // layout successor, delete the branch.
548  if (isLayoutSuccessor(TBB))
549  TII->removeBranch(*this);
550  } else {
551  // The block has an unconditional fallthrough. If its successor is not its
552  // layout successor, insert a branch. First we have to locate the only
553  // non-landing-pad successor, as that is the fallthrough block.
554  for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) {
555  if ((*SI)->isEHPad())
556  continue;
557  assert(!TBB && "Found more than one non-landing-pad successor!");
558  TBB = *SI;
559  }
560 
561  // If there is no non-landing-pad successor, the block has no fall-through
562  // edges to be concerned with.
563  if (!TBB)
564  return;
565 
566  // Finally update the unconditional successor to be reached via a branch
567  // if it would not be reached by fallthrough.
568  if (!isLayoutSuccessor(TBB))
569  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
570  }
571  return;
572  }
573 
574  if (FBB) {
575  // The block has a non-fallthrough conditional branch. If one of its
576  // successors is its layout successor, rewrite it to a fallthrough
577  // conditional branch.
578  if (isLayoutSuccessor(TBB)) {
579  if (TII->reverseBranchCondition(Cond))
580  return;
581  TII->removeBranch(*this);
582  TII->insertBranch(*this, FBB, nullptr, Cond, DL);
583  } else if (isLayoutSuccessor(FBB)) {
584  TII->removeBranch(*this);
585  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
586  }
587  return;
588  }
589 
590  // Walk through the successors and find the successor which is not a landing
591  // pad and is not the conditional branch destination (in TBB) as the
592  // fallthrough successor.
593  MachineBasicBlock *FallthroughBB = nullptr;
594  for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) {
595  if ((*SI)->isEHPad() || *SI == TBB)
596  continue;
597  assert(!FallthroughBB && "Found more than one fallthrough successor.");
598  FallthroughBB = *SI;
599  }
600 
601  if (!FallthroughBB) {
602  if (canFallThrough()) {
603  // We fallthrough to the same basic block as the conditional jump targets.
604  // Remove the conditional jump, leaving unconditional fallthrough.
605  // FIXME: This does not seem like a reasonable pattern to support, but it
606  // has been seen in the wild coming out of degenerate ARM test cases.
607  TII->removeBranch(*this);
608 
609  // Finally update the unconditional successor to be reached via a branch if
610  // it would not be reached by fallthrough.
611  if (!isLayoutSuccessor(TBB))
612  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
613  return;
614  }
615 
616  // We enter here iff exactly one successor is TBB which cannot fallthrough
617  // and the rest successors if any are EHPads. In this case, we need to
618  // change the conditional branch into unconditional branch.
619  TII->removeBranch(*this);
620  Cond.clear();
621  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
622  return;
623  }
624 
625  // The block has a fallthrough conditional branch.
626  if (isLayoutSuccessor(TBB)) {
627  if (TII->reverseBranchCondition(Cond)) {
628  // We can't reverse the condition, add an unconditional branch.
629  Cond.clear();
630  TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
631  return;
632  }
633  TII->removeBranch(*this);
634  TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
635  } else if (!isLayoutSuccessor(FallthroughBB)) {
636  TII->removeBranch(*this);
637  TII->insertBranch(*this, TBB, FallthroughBB, Cond, DL);
638  }
639 }
640 
642 #ifndef NDEBUG
643  int64_t Sum = 0;
644  for (auto Prob : Probs)
645  Sum += Prob.getNumerator();
646  // Due to precision issue, we assume that the sum of probabilities is one if
647  // the difference between the sum of their numerators and the denominator is
648  // no greater than the number of successors.
650  Probs.size() &&
651  "The sum of successors's probabilities exceeds one.");
652 #endif // NDEBUG
653 }
654 
656  BranchProbability Prob) {
657  // Probability list is either empty (if successor list isn't empty, this means
658  // disabled optimization) or has the same size as successor list.
659  if (!(Probs.empty() && !Successors.empty()))
660  Probs.push_back(Prob);
661  Successors.push_back(Succ);
662  Succ->addPredecessor(this);
663 }
664 
666  // We need to make sure probability list is either empty or has the same size
667  // of successor list. When this function is called, we can safely delete all
668  // probability in the list.
669  Probs.clear();
670  Successors.push_back(Succ);
671  Succ->addPredecessor(this);
672 }
673 
675  MachineBasicBlock *New,
676  bool NormalizeSuccProbs) {
677  succ_iterator OldI = llvm::find(successors(), Old);
678  assert(OldI != succ_end() && "Old is not a successor of this block!");
679  assert(llvm::find(successors(), New) == succ_end() &&
680  "New is already a successor of this block!");
681 
682  // Add a new successor with equal probability as the original one. Note
683  // that we directly copy the probability using the iterator rather than
684  // getting a potentially synthetic probability computed when unknown. This
685  // preserves the probabilities as-is and then we can renormalize them and
686  // query them effectively afterward.
687  addSuccessor(New, Probs.empty() ? BranchProbability::getUnknown()
688  : *getProbabilityIterator(OldI));
689  if (NormalizeSuccProbs)
691 }
692 
694  bool NormalizeSuccProbs) {
695  succ_iterator I = find(Successors, Succ);
696  removeSuccessor(I, NormalizeSuccProbs);
697 }
698 
701  assert(I != Successors.end() && "Not a current successor!");
702 
703  // If probability list is empty it means we don't use it (disabled
704  // optimization).
705  if (!Probs.empty()) {
706  probability_iterator WI = getProbabilityIterator(I);
707  Probs.erase(WI);
708  if (NormalizeSuccProbs)
710  }
711 
712  (*I)->removePredecessor(this);
713  return Successors.erase(I);
714 }
715 
717  MachineBasicBlock *New) {
718  if (Old == New)
719  return;
720 
722  succ_iterator NewI = E;
723  succ_iterator OldI = E;
724  for (succ_iterator I = succ_begin(); I != E; ++I) {
725  if (*I == Old) {
726  OldI = I;
727  if (NewI != E)
728  break;
729  }
730  if (*I == New) {
731  NewI = I;
732  if (OldI != E)
733  break;
734  }
735  }
736  assert(OldI != E && "Old is not a successor of this block");
737 
738  // If New isn't already a successor, let it take Old's place.
739  if (NewI == E) {
740  Old->removePredecessor(this);
741  New->addPredecessor(this);
742  *OldI = New;
743  return;
744  }
745 
746  // New is already a successor.
747  // Update its probability instead of adding a duplicate edge.
748  if (!Probs.empty()) {
749  auto ProbIter = getProbabilityIterator(NewI);
750  if (!ProbIter->isUnknown())
751  *ProbIter += *getProbabilityIterator(OldI);
752  }
753  removeSuccessor(OldI);
754 }
755 
757  succ_iterator I) {
758  if (Orig->Probs.empty())
759  addSuccessor(*I, Orig->getSuccProbability(I));
760  else
762 }
763 
764 void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) {
765  Predecessors.push_back(Pred);
766 }
767 
768 void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) {
769  pred_iterator I = find(Predecessors, Pred);
770  assert(I != Predecessors.end() && "Pred is not a predecessor of this block!");
771  Predecessors.erase(I);
772 }
773 
775  if (this == FromMBB)
776  return;
777 
778  while (!FromMBB->succ_empty()) {
779  MachineBasicBlock *Succ = *FromMBB->succ_begin();
780 
781  // If probability list is empty it means we don't use it (disabled
782  // optimization).
783  if (!FromMBB->Probs.empty()) {
784  auto Prob = *FromMBB->Probs.begin();
785  addSuccessor(Succ, Prob);
786  } else
788 
789  FromMBB->removeSuccessor(Succ);
790  }
791 }
792 
793 void
795  if (this == FromMBB)
796  return;
797 
798  while (!FromMBB->succ_empty()) {
799  MachineBasicBlock *Succ = *FromMBB->succ_begin();
800  if (!FromMBB->Probs.empty()) {
801  auto Prob = *FromMBB->Probs.begin();
802  addSuccessor(Succ, Prob);
803  } else
805  FromMBB->removeSuccessor(Succ);
806 
807  // Fix up any PHI nodes in the successor.
808  Succ->replacePhiUsesWith(FromMBB, this);
809  }
811 }
812 
814  return is_contained(predecessors(), MBB);
815 }
816 
818  return is_contained(successors(), MBB);
819 }
820 
823  return std::next(I) == MachineFunction::const_iterator(MBB);
824 }
825 
827  MachineFunction::iterator Fallthrough = getIterator();
828  ++Fallthrough;
829  // If FallthroughBlock is off the end of the function, it can't fall through.
830  if (Fallthrough == getParent()->end())
831  return nullptr;
832 
833  // If FallthroughBlock isn't a successor, no fallthrough is possible.
834  if (!isSuccessor(&*Fallthrough))
835  return nullptr;
836 
837  // Analyze the branches, if any, at the end of the block.
838  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
841  if (TII->analyzeBranch(*this, TBB, FBB, Cond)) {
842  // If we couldn't analyze the branch, examine the last instruction.
843  // If the block doesn't end in a known control barrier, assume fallthrough
844  // is possible. The isPredicated check is needed because this code can be
845  // called during IfConversion, where an instruction which is normally a
846  // Barrier is predicated and thus no longer an actual control barrier.
847  return (empty() || !back().isBarrier() || TII->isPredicated(back()))
848  ? &*Fallthrough
849  : nullptr;
850  }
851 
852  // If there is no branch, control always falls through.
853  if (!TBB) return &*Fallthrough;
854 
855  // If there is some explicit branch to the fallthrough block, it can obviously
856  // reach, even though the branch should get folded to fall through implicitly.
857  if (MachineFunction::iterator(TBB) == Fallthrough ||
858  MachineFunction::iterator(FBB) == Fallthrough)
859  return &*Fallthrough;
860 
861  // If it's an unconditional branch to some block not the fall through, it
862  // doesn't fall through.
863  if (Cond.empty()) return nullptr;
864 
865  // Otherwise, if it is conditional and has no explicit false block, it falls
866  // through.
867  return (FBB == nullptr) ? &*Fallthrough : nullptr;
868 }
869 
871  return getFallThrough() != nullptr;
872 }
873 
875  Pass &P) {
876  if (!canSplitCriticalEdge(Succ))
877  return nullptr;
878 
879  MachineFunction *MF = getParent();
880  DebugLoc DL; // FIXME: this is nowhere
881 
883  MF->insert(std::next(MachineFunction::iterator(this)), NMBB);
884  LLVM_DEBUG(dbgs() << "Splitting critical edge: " << printMBBReference(*this)
885  << " -- " << printMBBReference(*NMBB) << " -- "
886  << printMBBReference(*Succ) << '\n');
887 
890  if (LIS)
891  LIS->insertMBBInMaps(NMBB);
892  else if (Indexes)
893  Indexes->insertMBBInMaps(NMBB);
894 
895  // On some targets like Mips, branches may kill virtual registers. Make sure
896  // that LiveVariables is properly updated after updateTerminator replaces the
897  // terminators.
899 
900  // Collect a list of virtual registers killed by the terminators.
901  SmallVector<unsigned, 4> KilledRegs;
902  if (LV)
904  I != E; ++I) {
905  MachineInstr *MI = &*I;
907  OE = MI->operands_end(); OI != OE; ++OI) {
908  if (!OI->isReg() || OI->getReg() == 0 ||
909  !OI->isUse() || !OI->isKill() || OI->isUndef())
910  continue;
911  Register Reg = OI->getReg();
912  if (Register::isPhysicalRegister(Reg) ||
913  LV->getVarInfo(Reg).removeKill(*MI)) {
914  KilledRegs.push_back(Reg);
915  LLVM_DEBUG(dbgs() << "Removing terminator kill: " << *MI);
916  OI->setIsKill(false);
917  }
918  }
919  }
920 
921  SmallVector<unsigned, 4> UsedRegs;
922  if (LIS) {
924  I != E; ++I) {
925  MachineInstr *MI = &*I;
926 
928  OE = MI->operands_end(); OI != OE; ++OI) {
929  if (!OI->isReg() || OI->getReg() == 0)
930  continue;
931 
932  Register Reg = OI->getReg();
933  if (!is_contained(UsedRegs, Reg))
934  UsedRegs.push_back(Reg);
935  }
936  }
937  }
938 
939  ReplaceUsesOfBlockWith(Succ, NMBB);
940 
941  // If updateTerminator() removes instructions, we need to remove them from
942  // SlotIndexes.
943  SmallVector<MachineInstr*, 4> Terminators;
944  if (Indexes) {
946  I != E; ++I)
947  Terminators.push_back(&*I);
948  }
949 
951 
952  if (Indexes) {
953  SmallVector<MachineInstr*, 4> NewTerminators;
955  I != E; ++I)
956  NewTerminators.push_back(&*I);
957 
958  for (SmallVectorImpl<MachineInstr*>::iterator I = Terminators.begin(),
959  E = Terminators.end(); I != E; ++I) {
960  if (!is_contained(NewTerminators, *I))
961  Indexes->removeMachineInstrFromMaps(**I);
962  }
963  }
964 
965  // Insert unconditional "jump Succ" instruction in NMBB if necessary.
966  NMBB->addSuccessor(Succ);
967  if (!NMBB->isLayoutSuccessor(Succ)) {
970  TII->insertBranch(*NMBB, Succ, nullptr, Cond, DL);
971 
972  if (Indexes) {
973  for (MachineInstr &MI : NMBB->instrs()) {
974  // Some instructions may have been moved to NMBB by updateTerminator(),
975  // so we first remove any instruction that already has an index.
976  if (Indexes->hasIndex(MI))
977  Indexes->removeMachineInstrFromMaps(MI);
978  Indexes->insertMachineInstrInMaps(MI);
979  }
980  }
981  }
982 
983  // Fix PHI nodes in Succ so they refer to NMBB instead of this.
984  Succ->replacePhiUsesWith(this, NMBB);
985 
986  // Inherit live-ins from the successor
987  for (const auto &LI : Succ->liveins())
988  NMBB->addLiveIn(LI);
989 
990  // Update LiveVariables.
992  if (LV) {
993  // Restore kills of virtual registers that were killed by the terminators.
994  while (!KilledRegs.empty()) {
995  unsigned Reg = KilledRegs.pop_back_val();
996  for (instr_iterator I = instr_end(), E = instr_begin(); I != E;) {
997  if (!(--I)->addRegisterKilled(Reg, TRI, /* AddIfNotFound= */ false))
998  continue;
1000  LV->getVarInfo(Reg).Kills.push_back(&*I);
1001  LLVM_DEBUG(dbgs() << "Restored terminator kill: " << *I);
1002  break;
1003  }
1004  }
1005  // Update relevant live-through information.
1006  LV->addNewBlock(NMBB, this, Succ);
1007  }
1008 
1009  if (LIS) {
1010  // After splitting the edge and updating SlotIndexes, live intervals may be
1011  // in one of two situations, depending on whether this block was the last in
1012  // the function. If the original block was the last in the function, all
1013  // live intervals will end prior to the beginning of the new split block. If
1014  // the original block was not at the end of the function, all live intervals
1015  // will extend to the end of the new split block.
1016 
1017  bool isLastMBB =
1018  std::next(MachineFunction::iterator(NMBB)) == getParent()->end();
1019 
1020  SlotIndex StartIndex = Indexes->getMBBEndIdx(this);
1021  SlotIndex PrevIndex = StartIndex.getPrevSlot();
1022  SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB);
1023 
1024  // Find the registers used from NMBB in PHIs in Succ.
1025  SmallSet<unsigned, 8> PHISrcRegs;
1027  I = Succ->instr_begin(), E = Succ->instr_end();
1028  I != E && I->isPHI(); ++I) {
1029  for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne; ni += 2) {
1030  if (I->getOperand(ni+1).getMBB() == NMBB) {
1031  MachineOperand &MO = I->getOperand(ni);
1032  Register Reg = MO.getReg();
1033  PHISrcRegs.insert(Reg);
1034  if (MO.isUndef())
1035  continue;
1036 
1037  LiveInterval &LI = LIS->getInterval(Reg);
1038  VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
1039  assert(VNI &&
1040  "PHI sources should be live out of their predecessors.");
1041  LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1042  }
1043  }
1044  }
1045 
1047  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1048  unsigned Reg = Register::index2VirtReg(i);
1049  if (PHISrcRegs.count(Reg) || !LIS->hasInterval(Reg))
1050  continue;
1051 
1052  LiveInterval &LI = LIS->getInterval(Reg);
1053  if (!LI.liveAt(PrevIndex))
1054  continue;
1055 
1056  bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ));
1057  if (isLiveOut && isLastMBB) {
1058  VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
1059  assert(VNI && "LiveInterval should have VNInfo where it is live.");
1060  LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1061  } else if (!isLiveOut && !isLastMBB) {
1062  LI.removeSegment(StartIndex, EndIndex);
1063  }
1064  }
1065 
1066  // Update all intervals for registers whose uses may have been modified by
1067  // updateTerminator().
1068  LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs);
1069  }
1070 
1071  if (MachineDominatorTree *MDT =
1073  MDT->recordSplitCriticalEdge(this, Succ, NMBB);
1074 
1076  if (MachineLoop *TIL = MLI->getLoopFor(this)) {
1077  // If one or the other blocks were not in a loop, the new block is not
1078  // either, and thus LI doesn't need to be updated.
1079  if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) {
1080  if (TIL == DestLoop) {
1081  // Both in the same loop, the NMBB joins loop.
1082  DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
1083  } else if (TIL->contains(DestLoop)) {
1084  // Edge from an outer loop to an inner loop. Add to the outer loop.
1085  TIL->addBasicBlockToLoop(NMBB, MLI->getBase());
1086  } else if (DestLoop->contains(TIL)) {
1087  // Edge from an inner loop to an outer loop. Add to the outer loop.
1088  DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
1089  } else {
1090  // Edge from two loops with no containment relation. Because these
1091  // are natural loops, we know that the destination block must be the
1092  // header of its loop (adding a branch into a loop elsewhere would
1093  // create an irreducible loop).
1094  assert(DestLoop->getHeader() == Succ &&
1095  "Should not create irreducible loops!");
1096  if (MachineLoop *P = DestLoop->getParentLoop())
1097  P->addBasicBlockToLoop(NMBB, MLI->getBase());
1098  }
1099  }
1100  }
1101 
1102  return NMBB;
1103 }
1104 
1106  const MachineBasicBlock *Succ) const {
1107  // Splitting the critical edge to a landing pad block is non-trivial. Don't do
1108  // it in this generic function.
1109  if (Succ->isEHPad())
1110  return false;
1111 
1112  const MachineFunction *MF = getParent();
1113 
1114  // Performance might be harmed on HW that implements branching using exec mask
1115  // where both sides of the branches are always executed.
1116  if (MF->getTarget().requiresStructuredCFG())
1117  return false;
1118 
1119  // We may need to update this's terminator, but we can't do that if
1120  // AnalyzeBranch fails. If this uses a jump table, we won't touch it.
1121  const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
1122  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1124  // AnalyzeBanch should modify this, since we did not allow modification.
1125  if (TII->analyzeBranch(*const_cast<MachineBasicBlock *>(this), TBB, FBB, Cond,
1126  /*AllowModify*/ false))
1127  return false;
1128 
1129  // Avoid bugpoint weirdness: A block may end with a conditional branch but
1130  // jumps to the same MBB is either case. We have duplicate CFG edges in that
1131  // case that we can't handle. Since this never happens in properly optimized
1132  // code, just skip those edges.
1133  if (TBB && TBB == FBB) {
1134  LLVM_DEBUG(dbgs() << "Won't split critical edge after degenerate "
1135  << printMBBReference(*this) << '\n');
1136  return false;
1137  }
1138  return true;
1139 }
1140 
1141 /// Prepare MI to be removed from its bundle. This fixes bundle flags on MI's
1142 /// neighboring instructions so the bundle won't be broken by removing MI.
1143 static void unbundleSingleMI(MachineInstr *MI) {
1144  // Removing the first instruction in a bundle.
1145  if (MI->isBundledWithSucc() && !MI->isBundledWithPred())
1146  MI->unbundleFromSucc();
1147  // Removing the last instruction in a bundle.
1148  if (MI->isBundledWithPred() && !MI->isBundledWithSucc())
1149  MI->unbundleFromPred();
1150  // If MI is not bundled, or if it is internal to a bundle, the neighbor flags
1151  // are already fine.
1152 }
1153 
1156  unbundleSingleMI(&*I);
1157  return Insts.erase(I);
1158 }
1159 
1161  unbundleSingleMI(MI);
1164  return Insts.remove(MI);
1165 }
1166 
1169  assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
1170  "Cannot insert instruction with bundle flags");
1171  // Set the bundle flags when inserting inside a bundle.
1172  if (I != instr_end() && I->isBundledWithPred()) {
1175  }
1176  return Insts.insert(I, MI);
1177 }
1178 
1179 /// This method unlinks 'this' from the containing function, and returns it, but
1180 /// does not delete it.
1182  assert(getParent() && "Not embedded in a function!");
1183  getParent()->remove(this);
1184  return this;
1185 }
1186 
1187 /// This method unlinks 'this' from the containing function, and deletes it.
1189  assert(getParent() && "Not embedded in a function!");
1190  getParent()->erase(this);
1191 }
1192 
1193 /// Given a machine basic block that branched to 'Old', change the code and CFG
1194 /// so that it branches to 'New' instead.
1196  MachineBasicBlock *New) {
1197  assert(Old != New && "Cannot replace self with self!");
1198 
1200  while (I != instr_begin()) {
1201  --I;
1202  if (!I->isTerminator()) break;
1203 
1204  // Scan the operands of this machine instruction, replacing any uses of Old
1205  // with New.
1206  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1207  if (I->getOperand(i).isMBB() &&
1208  I->getOperand(i).getMBB() == Old)
1209  I->getOperand(i).setMBB(New);
1210  }
1211 
1212  // Update the successor information.
1213  replaceSuccessor(Old, New);
1214 }
1215 
1217  MachineBasicBlock *New) {
1218  for (MachineInstr &MI : phis())
1219  for (unsigned i = 2, e = MI.getNumOperands() + 1; i != e; i += 2) {
1220  MachineOperand &MO = MI.getOperand(i);
1221  if (MO.getMBB() == Old)
1222  MO.setMBB(New);
1223  }
1224 }
1225 
1226 /// Various pieces of code can cause excess edges in the CFG to be inserted. If
1227 /// we have proven that MBB can only branch to DestA and DestB, remove any other
1228 /// MBB successors from the CFG. DestA and DestB can be null.
1229 ///
1230 /// Besides DestA and DestB, retain other edges leading to LandingPads
1231 /// (currently there can be only one; we don't check or require that here).
1232 /// Note it is possible that DestA and/or DestB are LandingPads.
1234  MachineBasicBlock *DestB,
1235  bool IsCond) {
1236  // The values of DestA and DestB frequently come from a call to the
1237  // 'TargetInstrInfo::AnalyzeBranch' method. We take our meaning of the initial
1238  // values from there.
1239  //
1240  // 1. If both DestA and DestB are null, then the block ends with no branches
1241  // (it falls through to its successor).
1242  // 2. If DestA is set, DestB is null, and IsCond is false, then the block ends
1243  // with only an unconditional branch.
1244  // 3. If DestA is set, DestB is null, and IsCond is true, then the block ends
1245  // with a conditional branch that falls through to a successor (DestB).
1246  // 4. If DestA and DestB is set and IsCond is true, then the block ends with a
1247  // conditional branch followed by an unconditional branch. DestA is the
1248  // 'true' destination and DestB is the 'false' destination.
1249 
1250  bool Changed = false;
1251 
1252  MachineBasicBlock *FallThru = getNextNode();
1253 
1254  if (!DestA && !DestB) {
1255  // Block falls through to successor.
1256  DestA = FallThru;
1257  DestB = FallThru;
1258  } else if (DestA && !DestB) {
1259  if (IsCond)
1260  // Block ends in conditional jump that falls through to successor.
1261  DestB = FallThru;
1262  } else {
1263  assert(DestA && DestB && IsCond &&
1264  "CFG in a bad state. Cannot correct CFG edges");
1265  }
1266 
1267  // Remove superfluous edges. I.e., those which aren't destinations of this
1268  // basic block, duplicate edges, or landing pads.
1271  while (SI != succ_end()) {
1272  const MachineBasicBlock *MBB = *SI;
1273  if (!SeenMBBs.insert(MBB).second ||
1274  (MBB != DestA && MBB != DestB && !MBB->isEHPad())) {
1275  // This is a superfluous edge, remove it.
1276  SI = removeSuccessor(SI);
1277  Changed = true;
1278  } else {
1279  ++SI;
1280  }
1281  }
1282 
1283  if (Changed)
1285  return Changed;
1286 }
1287 
1288 /// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE
1289 /// instructions. Return UnknownLoc if there is none.
1290 DebugLoc
1292  // Skip debug declarations, we don't want a DebugLoc from them.
1293  MBBI = skipDebugInstructionsForward(MBBI, instr_end());
1294  if (MBBI != instr_end())
1295  return MBBI->getDebugLoc();
1296  return {};
1297 }
1298 
1299 /// Find the previous valid DebugLoc preceding MBBI, skipping and DBG_VALUE
1300 /// instructions. Return UnknownLoc if there is none.
1302  if (MBBI == instr_begin()) return {};
1303  // Skip debug declarations, we don't want a DebugLoc from them.
1304  MBBI = skipDebugInstructionsBackward(std::prev(MBBI), instr_begin());
1305  if (!MBBI->isDebugInstr()) return MBBI->getDebugLoc();
1306  return {};
1307 }
1308 
1309 /// Find and return the merged DebugLoc of the branch instructions of the block.
1310 /// Return UnknownLoc if there is none.
1311 DebugLoc
1313  DebugLoc DL;
1314  auto TI = getFirstTerminator();
1315  while (TI != end() && !TI->isBranch())
1316  ++TI;
1317 
1318  if (TI != end()) {
1319  DL = TI->getDebugLoc();
1320  for (++TI ; TI != end() ; ++TI)
1321  if (TI->isBranch())
1322  DL = DILocation::getMergedLocation(DL, TI->getDebugLoc());
1323  }
1324  return DL;
1325 }
1326 
1327 /// Return probability of the edge from this block to MBB.
1329 MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const {
1330  if (Probs.empty())
1331  return BranchProbability(1, succ_size());
1332 
1333  const auto &Prob = *getProbabilityIterator(Succ);
1334  if (Prob.isUnknown()) {
1335  // For unknown probabilities, collect the sum of all known ones, and evenly
1336  // ditribute the complemental of the sum to each unknown probability.
1337  unsigned KnownProbNum = 0;
1338  auto Sum = BranchProbability::getZero();
1339  for (auto &P : Probs) {
1340  if (!P.isUnknown()) {
1341  Sum += P;
1342  KnownProbNum++;
1343  }
1344  }
1345  return Sum.getCompl() / (Probs.size() - KnownProbNum);
1346  } else
1347  return Prob;
1348 }
1349 
1350 /// Set successor probability of a given iterator.
1352  BranchProbability Prob) {
1353  assert(!Prob.isUnknown());
1354  if (Probs.empty())
1355  return;
1356  *getProbabilityIterator(I) = Prob;
1357 }
1358 
1359 /// Return probability iterator corresonding to the I successor iterator
1360 MachineBasicBlock::const_probability_iterator
1361 MachineBasicBlock::getProbabilityIterator(
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 probability iterator corresonding to the I successor iterator.
1370 MachineBasicBlock::probability_iterator
1371 MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) {
1372  assert(Probs.size() == Successors.size() && "Async probability list!");
1373  const size_t index = std::distance(Successors.begin(), I);
1374  assert(index < Probs.size() && "Not a current successor!");
1375  return Probs.begin() + index;
1376 }
1377 
1378 /// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed
1379 /// as of just before "MI".
1380 ///
1381 /// Search is localised to a neighborhood of
1382 /// Neighborhood instructions before (searching for defs or kills) and N
1383 /// instructions after (searching just for defs) MI.
1386  unsigned Reg, const_iterator Before,
1387  unsigned Neighborhood) const {
1388  unsigned N = Neighborhood;
1389 
1390  // Try searching forwards from Before, looking for reads or defs.
1391  const_iterator I(Before);
1392  for (; I != end() && N > 0; ++I) {
1393  if (I->isDebugInstr())
1394  continue;
1395 
1396  --N;
1397 
1399  ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
1400 
1401  // Register is live when we read it here.
1402  if (Info.Read)
1403  return LQR_Live;
1404  // Register is dead if we can fully overwrite or clobber it here.
1405  if (Info.FullyDefined || Info.Clobbered)
1406  return LQR_Dead;
1407  }
1408 
1409  // If we reached the end, it is safe to clobber Reg at the end of a block of
1410  // no successor has it live in.
1411  if (I == end()) {
1412  for (MachineBasicBlock *S : successors()) {
1413  for (const MachineBasicBlock::RegisterMaskPair &LI : S->liveins()) {
1414  if (TRI->regsOverlap(LI.PhysReg, Reg))
1415  return LQR_Live;
1416  }
1417  }
1418 
1419  return LQR_Dead;
1420  }
1421 
1422 
1423  N = Neighborhood;
1424 
1425  // Start by searching backwards from Before, looking for kills, reads or defs.
1426  I = const_iterator(Before);
1427  // If this is the first insn in the block, don't search backwards.
1428  if (I != begin()) {
1429  do {
1430  --I;
1431 
1432  if (I->isDebugInstr())
1433  continue;
1434 
1435  --N;
1436 
1438  ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
1439 
1440  // Defs happen after uses so they take precedence if both are present.
1441 
1442  // Register is dead after a dead def of the full register.
1443  if (Info.DeadDef)
1444  return LQR_Dead;
1445  // Register is (at least partially) live after a def.
1446  if (Info.Defined) {
1447  if (!Info.PartialDeadDef)
1448  return LQR_Live;
1449  // As soon as we saw a partial definition (dead or not),
1450  // we cannot tell if the value is partial live without
1451  // tracking the lanemasks. We are not going to do this,
1452  // so fall back on the remaining of the analysis.
1453  break;
1454  }
1455  // Register is dead after a full kill or clobber and no def.
1456  if (Info.Killed || Info.Clobbered)
1457  return LQR_Dead;
1458  // Register must be live if we read it.
1459  if (Info.Read)
1460  return LQR_Live;
1461 
1462  } while (I != begin() && N > 0);
1463  }
1464 
1465  // Did we get to the start of the block?
1466  if (I == begin()) {
1467  // If so, the register's state is definitely defined by the live-in state.
1468  for (const MachineBasicBlock::RegisterMaskPair &LI : liveins())
1469  if (TRI->regsOverlap(LI.PhysReg, Reg))
1470  return LQR_Live;
1471 
1472  return LQR_Dead;
1473  }
1474 
1475  // At this point we have no idea of the liveness of the register.
1476  return LQR_Unknown;
1477 }
1478 
1479 const uint32_t *
1481  // EH funclet entry does not preserve any registers.
1482  return isEHFuncletEntry() ? TRI->getNoPreservedMask() : nullptr;
1483 }
1484 
1485 const uint32_t *
1487  // If we see a return block with successors, this must be a funclet return,
1488  // which does not preserve any registers. If there are no successors, we don't
1489  // care what kind of return it is, putting a mask after it is a no-op.
1490  return isReturnBlock() && !succ_empty() ? TRI->getNoPreservedMask() : nullptr;
1491 }
1492 
1494  LiveIns.clear();
1495 }
1496 
1498  assert(getParent()->getProperties().hasProperty(
1500  "Liveness information is accurate");
1501  return LiveIns.begin();
1502 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
void print(raw_ostream &OS, const SlotIndexes *=nullptr, bool IsStandalone=true) const
const MCAsmInfo * getAsmInfo() const
Definition: MCContext.h:318
unsigned Log2(Align A)
Returns the log2 of the alignment.
Definition: Alignment.h:150
mop_iterator operands_end()
Definition: MachineInstr.h:472
void validateSuccProbs() const
Validate successors&#39; probabilities and check if the sum of them is approximate one.
instr_iterator instr_begin()
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:22
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:288
const MachineFunction * getMF() const
Return the function that contains the basic block that this instruction belongs to.
iterator erase(iterator where)
Definition: ilist.h:265
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:476
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:65
MCSymbol - Instances of this class represent a symbol name in the MC file, and MCSymbols are created ...
Definition: MCSymbol.h:41
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...
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
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...
Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
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:364
instr_iterator getFirstInstrTerminator()
Same getFirstTerminator but it ignores bundles and return an instr_iterator instead.
void push_back(const T &Elt)
Definition: SmallVector.h:211
iterator getFirstNonDebugInstr()
Returns an iterator to the first non-debug instruction in the basic block, or end().
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:63
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:679
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
bool requiresStructuredCFG() const
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.
iterator_range< iterator > phis()
Returns a range that iterates over the phis in the basic block.
int getLocalSlot(const Value *V)
Return the slot number of the specified local value.
Definition: AsmWriter.cpp:857
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:89
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:161
void moveAfter(MachineBasicBlock *NewBefore)
unsigned const TargetRegisterInfo * TRI
A debug info location.
Definition: DebugLoc.h:33
Printable PrintLaneMask(LaneBitmask LaneMask)
Create Printable object to print LaneBitmasks on a raw_ostream.
Definition: LaneBitmask.h:93
F(f)
Manage lifetime of a slot tracker for printing IR.
MachineInstrBundleIterator< const MachineInstr > const_iterator
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
static unsigned index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition: Register.h:83
VNInfo - Value Number Information.
Definition: LiveInterval.h:52
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:93
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:80
const HexagonInstrInfo * TII
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:414
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:368
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
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:390
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
bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
Definition: MCRegister.h:59
Context object for machine code objects.
Definition: MCContext.h:65
bool regsOverlap(Register regA, Register regB) const
Returns true if the two registers are equal or alias each other.
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)
bool hasInterval(Register Reg) const
SlotIndexes pass.
Definition: SlotIndexes.h:314
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:255
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:352
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...
Analysis containing CSE Info
Definition: CSEInfo.cpp:20
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...
Definition: MCRegister.h:19
TargetInstrInfo - Interface to description of machine instruction set.
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
Definition: LiveInterval.h:412
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)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
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 hasName() const
Definition: Value.h:251
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
bool liveAt(SlotIndex index) const
Definition: LiveInterval.h:392
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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:370
livein_iterator livein_end() const
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:385
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:302
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Definition: SlotIndexes.h:469
void clearFlag(MIFlag Flag)
clearFlag - Clear a MI flag.
Definition: MachineInstr.h:313
static cl::opt< bool > PrintSlotIndexes("print-slotindexes", cl::desc("When printing machine IR, annotate instructions and blocks with " "SlotIndexes when available"), cl::init(true), cl::Hidden)
StringRef getPrivateLabelPrefix() const
Definition: MCAsmInfo.h:502
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.
void replacePhiUsesWith(MachineBasicBlock *Old, MachineBasicBlock *New)
Update all phi nodes in this basic block to refer to basic block New instead of basic block Old...
std::vector< MachineBasicBlock * >::const_iterator const_succ_iterator
void remove(iterator MBBI)
self_iterator getIterator()
Definition: ilist_node.h:81
LiveInterval & getInterval(Register Reg)
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:180
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:1193
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:843
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.
static constexpr const Align None()
Returns a default constructed Align which corresponds to no alignment.
Definition: Alignment.h:82
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:1186
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:1095
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:88
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:47
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:66
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:837
void updateTerminator()
Update the terminator instructions in block to account for changes to the layout. ...
bool FullyDefined
Reg or a super-register is defined.
static void deleteNode(NodeTy *V)
Definition: ilist.h:41
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:132
llvm::Align getAlignment() const
Return alignment of the basic block.
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:256
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:249
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator insert(iterator where, pointer New)
Definition: ilist.h:226
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:129
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
Definition: SlotIndexes.h:289
bool isEHPad() const
Returns true if the block is a landing pad.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
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:44
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
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:1228
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:479
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.
const LLVMTargetMachine & getTarget() const
getTarget - Return the target machine this machine code is compiled with
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2047
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:575
mop_iterator operands_begin()
Definition: MachineInstr.h:471
AnalysisType * getAnalysisIfAvailable() const
getAnalysisIfAvailable<AnalysisType>() - Subclasses use this function to get analysis information tha...
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:69
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
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:658
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
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.
Register getReg() const
getReg - Returns the register number.
Simple wrapper around std::function<void(raw_ostream&)>.
Definition: Printable.h:37
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:416
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:83
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:297
std::vector< MachineBasicBlock * >::iterator succ_iterator
livein_iterator livein_begin() const
bool CorrectExtraCFGEdges(MachineBasicBlock *DestA, MachineBasicBlock *DestB, bool IsCond)
Various pieces of code can cause excess edges in the CFG to be inserted.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
void transferNodesFromList(ilist_callback_traits &OldList, Iterator, Iterator)
Callback before transferring nodes to this list.
Definition: ilist.h:71
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:164
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:1224