LLVM  9.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 
42 MachineBasicBlock::MachineBasicBlock(MachineFunction &MF, const BasicBlock *B)
43  : BB(B), Number(-1), xParent(&MF) {
44  Insts.Parent = this;
45  if (B)
46  IrrLoopHeaderWeight = B->getIrrLoopHeaderWeight();
47 }
48 
49 MachineBasicBlock::~MachineBasicBlock() {
50 }
51 
52 /// Return the MCSymbol for this basic block.
54  if (!CachedMCSymbol) {
55  const MachineFunction *MF = getParent();
56  MCContext &Ctx = MF->getContext();
57  auto Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix();
58  assert(getNumber() >= 0 && "cannot get label for unreachable MBB");
59  CachedMCSymbol = Ctx.getOrCreateSymbol(Twine(Prefix) + "BB" +
60  Twine(MF->getFunctionNumber()) +
61  "_" + Twine(getNumber()));
62  }
63 
64  return CachedMCSymbol;
65 }
66 
67 
69  MBB.print(OS);
70  return OS;
71 }
72 
74  return Printable([&MBB](raw_ostream &OS) { return MBB.printAsOperand(OS); });
75 }
76 
77 /// When an MBB is added to an MF, we need to update the parent pointer of the
78 /// MBB, the MBB numbering, and any instructions in the MBB to be on the right
79 /// operand list for registers.
80 ///
81 /// MBBs start out as #-1. When a MBB is added to a MachineFunction, it
82 /// gets the next available unique MBB number. If it is removed from a
83 /// MachineFunction, it goes back to being #-1.
86  MachineFunction &MF = *N->getParent();
87  N->Number = MF.addToMBBNumbering(N);
88 
89  // Make sure the instructions have their operands in the reginfo lists.
90  MachineRegisterInfo &RegInfo = MF.getRegInfo();
92  I = N->instr_begin(), E = N->instr_end(); I != E; ++I)
93  I->AddRegOperandsToUseLists(RegInfo);
94 }
95 
97  MachineBasicBlock *N) {
98  N->getParent()->removeFromMBBNumbering(N->Number);
99  N->Number = -1;
100 }
101 
102 /// When we add an instruction to a basic block list, we update its parent
103 /// pointer and add its operands from reg use/def lists if appropriate.
105  assert(!N->getParent() && "machine instruction already in a basic block");
106  N->setParent(Parent);
107 
108  // Add the instruction's register operands to their corresponding
109  // use/def lists.
110  MachineFunction *MF = Parent->getParent();
111  N->AddRegOperandsToUseLists(MF->getRegInfo());
112  MF->handleInsertion(*N);
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  MF->handleRemoval(*N);
123  N->RemoveRegOperandsFromUseLists(MF->getRegInfo());
124  }
125 
126  N->setParent(nullptr);
127 }
128 
129 /// When moving a range of instructions from one MBB list to another, we need to
130 /// update the parent pointers and the use/def lists.
132  instr_iterator First,
133  instr_iterator Last) {
134  assert(Parent->getParent() == FromList.Parent->getParent() &&
135  "MachineInstr parent mismatch!");
136  assert(this != &FromList && "Called without a real transfer...");
137  assert(Parent != FromList.Parent && "Two lists have the same parent?");
138 
139  // If splicing between two blocks within the same function, just update the
140  // parent pointers.
141  for (; First != Last; ++First)
142  First->setParent(Parent);
143 }
144 
146  assert(!MI->getParent() && "MI is still in a block!");
147  Parent->getParent()->DeleteMachineInstr(MI);
148 }
149 
152  while (I != E && I->isPHI())
153  ++I;
154  assert((I == E || !I->isInsideBundle()) &&
155  "First non-phi MI cannot be inside a bundle!");
156  return I;
157 }
158 
162 
163  iterator E = end();
164  while (I != E && (I->isPHI() || I->isPosition() ||
165  TII->isBasicBlockPrologue(*I)))
166  ++I;
167  // FIXME: This needs to change if we wish to bundle labels
168  // inside the bundle.
169  assert((I == E || !I->isInsideBundle()) &&
170  "First non-phi / non-label instruction is inside a bundle!");
171  return I;
172 }
173 
177 
178  iterator E = end();
179  while (I != E && (I->isPHI() || I->isPosition() || I->isDebugInstr() ||
180  TII->isBasicBlockPrologue(*I)))
181  ++I;
182  // FIXME: This needs to change if we wish to bundle labels / dbg_values
183  // inside the bundle.
184  assert((I == E || !I->isInsideBundle()) &&
185  "First non-phi / non-label / non-debug "
186  "instruction is inside a bundle!");
187  return I;
188 }
189 
191  iterator B = begin(), E = end(), I = E;
192  while (I != B && ((--I)->isTerminator() || I->isDebugInstr()))
193  ; /*noop */
194  while (I != E && !I->isTerminator())
195  ++I;
196  return I;
197 }
198 
200  instr_iterator B = instr_begin(), E = instr_end(), I = E;
201  while (I != B && ((--I)->isTerminator() || I->isDebugInstr()))
202  ; /*noop */
203  while (I != E && !I->isTerminator())
204  ++I;
205  return I;
206 }
207 
209  // Skip over begin-of-block dbg_value instructions.
211 }
212 
214  // Skip over end-of-block dbg_value instructions.
216  while (I != B) {
217  --I;
218  // Return instruction that starts a bundle.
219  if (I->isDebugInstr() || I->isInsideBundle())
220  continue;
221  return I;
222  }
223  // The block is all debug values.
224  return end();
225 }
226 
228  for (const_succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I)
229  if ((*I)->isEHPad())
230  return true;
231  return false;
232 }
233 
234 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
236  print(dbgs());
237 }
238 #endif
239 
241  if (isReturnBlock() || hasEHPadSuccessor())
242  return false;
243  return true;
244 }
245 
247  if (const BasicBlock *LBB = getBasicBlock())
248  return LBB->getName();
249  else
250  return StringRef("", 0);
251 }
252 
253 /// Return a hopefully unique identifier for this block.
254 std::string MachineBasicBlock::getFullName() const {
255  std::string Name;
256  if (getParent())
257  Name = (getParent()->getName() + ":").str();
258  if (getBasicBlock())
259  Name += getBasicBlock()->getName();
260  else
261  Name += ("BB" + Twine(getNumber())).str();
262  return Name;
263 }
264 
266  bool IsStandalone) const {
267  const MachineFunction *MF = getParent();
268  if (!MF) {
269  OS << "Can't print out MachineBasicBlock because parent MachineFunction"
270  << " is null\n";
271  return;
272  }
273  const Function &F = MF->getFunction();
274  const Module *M = F.getParent();
275  ModuleSlotTracker MST(M);
276  MST.incorporateFunction(F);
277  print(OS, MST, Indexes, IsStandalone);
278 }
279 
281  const SlotIndexes *Indexes,
282  bool IsStandalone) const {
283  const MachineFunction *MF = getParent();
284  if (!MF) {
285  OS << "Can't print out MachineBasicBlock because parent MachineFunction"
286  << " is null\n";
287  return;
288  }
289 
290  if (Indexes)
291  OS << Indexes->getMBBStartIdx(this) << '\t';
292 
293  OS << "bb." << getNumber();
294  bool HasAttributes = false;
295  if (const auto *BB = getBasicBlock()) {
296  if (BB->hasName()) {
297  OS << "." << BB->getName();
298  } else {
299  HasAttributes = true;
300  OS << " (";
301  int Slot = MST.getLocalSlot(BB);
302  if (Slot == -1)
303  OS << "<ir-block badref>";
304  else
305  OS << (Twine("%ir-block.") + Twine(Slot)).str();
306  }
307  }
308 
309  if (hasAddressTaken()) {
310  OS << (HasAttributes ? ", " : " (");
311  OS << "address-taken";
312  HasAttributes = true;
313  }
314  if (isEHPad()) {
315  OS << (HasAttributes ? ", " : " (");
316  OS << "landing-pad";
317  HasAttributes = true;
318  }
319  if (getAlignment()) {
320  OS << (HasAttributes ? ", " : " (");
321  OS << "align " << getAlignment();
322  HasAttributes = true;
323  }
324  if (HasAttributes)
325  OS << ")";
326  OS << ":\n";
327 
329  const MachineRegisterInfo &MRI = MF->getRegInfo();
331  bool HasLineAttributes = false;
332 
333  // Print the preds of this block according to the CFG.
334  if (!pred_empty() && IsStandalone) {
335  if (Indexes) OS << '\t';
336  // Don't indent(2), align with previous line attributes.
337  OS << "; predecessors: ";
338  for (auto I = pred_begin(), E = pred_end(); I != E; ++I) {
339  if (I != pred_begin())
340  OS << ", ";
341  OS << printMBBReference(**I);
342  }
343  OS << '\n';
344  HasLineAttributes = true;
345  }
346 
347  if (!succ_empty()) {
348  if (Indexes) OS << '\t';
349  // Print the successors
350  OS.indent(2) << "successors: ";
351  for (auto I = succ_begin(), E = succ_end(); I != E; ++I) {
352  if (I != succ_begin())
353  OS << ", ";
354  OS << printMBBReference(**I);
355  if (!Probs.empty())
356  OS << '('
357  << format("0x%08" PRIx32, getSuccProbability(I).getNumerator())
358  << ')';
359  }
360  if (!Probs.empty() && IsStandalone) {
361  // Print human readable probabilities as comments.
362  OS << "; ";
363  for (auto I = succ_begin(), E = succ_end(); I != E; ++I) {
364  const BranchProbability &BP = getSuccProbability(I);
365  if (I != succ_begin())
366  OS << ", ";
367  OS << printMBBReference(**I) << '('
368  << format("%.2f%%",
369  rint(((double)BP.getNumerator() / BP.getDenominator()) *
370  100.0 * 100.0) /
371  100.0)
372  << ')';
373  }
374  }
375 
376  OS << '\n';
377  HasLineAttributes = true;
378  }
379 
380  if (!livein_empty() && MRI.tracksLiveness()) {
381  if (Indexes) OS << '\t';
382  OS.indent(2) << "liveins: ";
383 
384  bool First = true;
385  for (const auto &LI : liveins()) {
386  if (!First)
387  OS << ", ";
388  First = false;
389  OS << printReg(LI.PhysReg, TRI);
390  if (!LI.LaneMask.all())
391  OS << ":0x" << PrintLaneMask(LI.LaneMask);
392  }
393  HasLineAttributes = true;
394  }
395 
396  if (HasLineAttributes)
397  OS << '\n';
398 
399  bool IsInBundle = false;
400  for (const MachineInstr &MI : instrs()) {
401  if (Indexes) {
402  if (Indexes->hasIndex(MI))
403  OS << Indexes->getInstructionIndex(MI);
404  OS << '\t';
405  }
406 
407  if (IsInBundle && !MI.isInsideBundle()) {
408  OS.indent(2) << "}\n";
409  IsInBundle = false;
410  }
411 
412  OS.indent(IsInBundle ? 4 : 2);
413  MI.print(OS, MST, IsStandalone, /*SkipOpers=*/false, /*SkipDebugLoc=*/false,
414  /*AddNewLine=*/false, &TII);
415 
416  if (!IsInBundle && MI.getFlag(MachineInstr::BundledSucc)) {
417  OS << " {";
418  IsInBundle = true;
419  }
420  OS << '\n';
421  }
422 
423  if (IsInBundle)
424  OS.indent(2) << "}\n";
425 
426  if (IrrLoopHeaderWeight && IsStandalone) {
427  if (Indexes) OS << '\t';
428  OS.indent(2) << "; Irreducible loop header weight: "
429  << IrrLoopHeaderWeight.getValue() << '\n';
430  }
431 }
432 
434  bool /*PrintType*/) const {
435  OS << "%bb." << getNumber();
436 }
437 
439  LiveInVector::iterator I = find_if(
440  LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
441  if (I == LiveIns.end())
442  return;
443 
444  I->LaneMask &= ~LaneMask;
445  if (I->LaneMask.none())
446  LiveIns.erase(I);
447 }
448 
451  // Get non-const version of iterator.
452  LiveInVector::iterator LI = LiveIns.begin() + (I - LiveIns.begin());
453  return LiveIns.erase(LI);
454 }
455 
458  LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
459  return I != livein_end() && (I->LaneMask & LaneMask).any();
460 }
461 
463  llvm::sort(LiveIns,
464  [](const RegisterMaskPair &LI0, const RegisterMaskPair &LI1) {
465  return LI0.PhysReg < LI1.PhysReg;
466  });
467  // Liveins are sorted by physreg now we can merge their lanemasks.
468  LiveInVector::const_iterator I = LiveIns.begin();
469  LiveInVector::const_iterator J;
470  LiveInVector::iterator Out = LiveIns.begin();
471  for (; I != LiveIns.end(); ++Out, I = J) {
472  unsigned PhysReg = I->PhysReg;
473  LaneBitmask LaneMask = I->LaneMask;
474  for (J = std::next(I); J != LiveIns.end() && J->PhysReg == PhysReg; ++J)
475  LaneMask |= J->LaneMask;
476  Out->PhysReg = PhysReg;
477  Out->LaneMask = LaneMask;
478  }
479  LiveIns.erase(Out, LiveIns.end());
480 }
481 
482 unsigned
484  assert(getParent() && "MBB must be inserted in function");
485  assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && "Expected physreg");
486  assert(RC && "Register class is required");
487  assert((isEHPad() || this == &getParent()->front()) &&
488  "Only the entry block and landing pads can have physreg live ins");
489 
490  bool LiveIn = isLiveIn(PhysReg);
494 
495  // Look for an existing copy.
496  if (LiveIn)
497  for (;I != E && I->isCopy(); ++I)
498  if (I->getOperand(1).getReg() == PhysReg) {
499  unsigned VirtReg = I->getOperand(0).getReg();
500  if (!MRI.constrainRegClass(VirtReg, RC))
501  llvm_unreachable("Incompatible live-in register class.");
502  return VirtReg;
503  }
504 
505  // No luck, create a virtual register.
506  unsigned VirtReg = MRI.createVirtualRegister(RC);
507  BuildMI(*this, I, DebugLoc(), TII.get(TargetOpcode::COPY), VirtReg)
508  .addReg(PhysReg, RegState::Kill);
509  if (!LiveIn)
510  addLiveIn(PhysReg);
511  return VirtReg;
512 }
513 
515  getParent()->splice(NewAfter->getIterator(), getIterator());
516 }
517 
519  getParent()->splice(++NewBefore->getIterator(), getIterator());
520 }
521 
524  // A block with no successors has no concerns with fall-through edges.
525  if (this->succ_empty())
526  return;
527 
528  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
531  bool B = TII->analyzeBranch(*this, TBB, FBB, Cond);
532  (void) B;
533  assert(!B && "UpdateTerminators requires analyzable predecessors!");
534  if (Cond.empty()) {
535  if (TBB) {
536  // The block has an unconditional branch. If its successor is now its
537  // layout successor, delete the branch.
538  if (isLayoutSuccessor(TBB))
539  TII->removeBranch(*this);
540  } else {
541  // The block has an unconditional fallthrough. If its successor is not its
542  // layout successor, insert a branch. First we have to locate the only
543  // non-landing-pad successor, as that is the fallthrough block.
544  for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) {
545  if ((*SI)->isEHPad())
546  continue;
547  assert(!TBB && "Found more than one non-landing-pad successor!");
548  TBB = *SI;
549  }
550 
551  // If there is no non-landing-pad successor, the block has no fall-through
552  // edges to be concerned with.
553  if (!TBB)
554  return;
555 
556  // Finally update the unconditional successor to be reached via a branch
557  // if it would not be reached by fallthrough.
558  if (!isLayoutSuccessor(TBB))
559  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
560  }
561  return;
562  }
563 
564  if (FBB) {
565  // The block has a non-fallthrough conditional branch. If one of its
566  // successors is its layout successor, rewrite it to a fallthrough
567  // conditional branch.
568  if (isLayoutSuccessor(TBB)) {
569  if (TII->reverseBranchCondition(Cond))
570  return;
571  TII->removeBranch(*this);
572  TII->insertBranch(*this, FBB, nullptr, Cond, DL);
573  } else if (isLayoutSuccessor(FBB)) {
574  TII->removeBranch(*this);
575  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
576  }
577  return;
578  }
579 
580  // Walk through the successors and find the successor which is not a landing
581  // pad and is not the conditional branch destination (in TBB) as the
582  // fallthrough successor.
583  MachineBasicBlock *FallthroughBB = nullptr;
584  for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) {
585  if ((*SI)->isEHPad() || *SI == TBB)
586  continue;
587  assert(!FallthroughBB && "Found more than one fallthrough successor.");
588  FallthroughBB = *SI;
589  }
590 
591  if (!FallthroughBB) {
592  if (canFallThrough()) {
593  // We fallthrough to the same basic block as the conditional jump targets.
594  // Remove the conditional jump, leaving unconditional fallthrough.
595  // FIXME: This does not seem like a reasonable pattern to support, but it
596  // has been seen in the wild coming out of degenerate ARM test cases.
597  TII->removeBranch(*this);
598 
599  // Finally update the unconditional successor to be reached via a branch if
600  // it would not be reached by fallthrough.
601  if (!isLayoutSuccessor(TBB))
602  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
603  return;
604  }
605 
606  // We enter here iff exactly one successor is TBB which cannot fallthrough
607  // and the rest successors if any are EHPads. In this case, we need to
608  // change the conditional branch into unconditional branch.
609  TII->removeBranch(*this);
610  Cond.clear();
611  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
612  return;
613  }
614 
615  // The block has a fallthrough conditional branch.
616  if (isLayoutSuccessor(TBB)) {
617  if (TII->reverseBranchCondition(Cond)) {
618  // We can't reverse the condition, add an unconditional branch.
619  Cond.clear();
620  TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
621  return;
622  }
623  TII->removeBranch(*this);
624  TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
625  } else if (!isLayoutSuccessor(FallthroughBB)) {
626  TII->removeBranch(*this);
627  TII->insertBranch(*this, TBB, FallthroughBB, Cond, DL);
628  }
629 }
630 
632 #ifndef NDEBUG
633  int64_t Sum = 0;
634  for (auto Prob : Probs)
635  Sum += Prob.getNumerator();
636  // Due to precision issue, we assume that the sum of probabilities is one if
637  // the difference between the sum of their numerators and the denominator is
638  // no greater than the number of successors.
640  Probs.size() &&
641  "The sum of successors's probabilities exceeds one.");
642 #endif // NDEBUG
643 }
644 
646  BranchProbability Prob) {
647  // Probability list is either empty (if successor list isn't empty, this means
648  // disabled optimization) or has the same size as successor list.
649  if (!(Probs.empty() && !Successors.empty()))
650  Probs.push_back(Prob);
651  Successors.push_back(Succ);
652  Succ->addPredecessor(this);
653 }
654 
656  // We need to make sure probability list is either empty or has the same size
657  // of successor list. When this function is called, we can safely delete all
658  // probability in the list.
659  Probs.clear();
660  Successors.push_back(Succ);
661  Succ->addPredecessor(this);
662 }
663 
665  MachineBasicBlock *New,
666  bool NormalizeSuccProbs) {
667  succ_iterator OldI = llvm::find(successors(), Old);
668  assert(OldI != succ_end() && "Old is not a successor of this block!");
669  assert(llvm::find(successors(), New) == succ_end() &&
670  "New is already a successor of this block!");
671 
672  // Add a new successor with equal probability as the original one. Note
673  // that we directly copy the probability using the iterator rather than
674  // getting a potentially synthetic probability computed when unknown. This
675  // preserves the probabilities as-is and then we can renormalize them and
676  // query them effectively afterward.
677  addSuccessor(New, Probs.empty() ? BranchProbability::getUnknown()
678  : *getProbabilityIterator(OldI));
679  if (NormalizeSuccProbs)
681 }
682 
684  bool NormalizeSuccProbs) {
685  succ_iterator I = find(Successors, Succ);
686  removeSuccessor(I, NormalizeSuccProbs);
687 }
688 
691  assert(I != Successors.end() && "Not a current successor!");
692 
693  // If probability list is empty it means we don't use it (disabled
694  // optimization).
695  if (!Probs.empty()) {
696  probability_iterator WI = getProbabilityIterator(I);
697  Probs.erase(WI);
698  if (NormalizeSuccProbs)
700  }
701 
702  (*I)->removePredecessor(this);
703  return Successors.erase(I);
704 }
705 
707  MachineBasicBlock *New) {
708  if (Old == New)
709  return;
710 
712  succ_iterator NewI = E;
713  succ_iterator OldI = E;
714  for (succ_iterator I = succ_begin(); I != E; ++I) {
715  if (*I == Old) {
716  OldI = I;
717  if (NewI != E)
718  break;
719  }
720  if (*I == New) {
721  NewI = I;
722  if (OldI != E)
723  break;
724  }
725  }
726  assert(OldI != E && "Old is not a successor of this block");
727 
728  // If New isn't already a successor, let it take Old's place.
729  if (NewI == E) {
730  Old->removePredecessor(this);
731  New->addPredecessor(this);
732  *OldI = New;
733  return;
734  }
735 
736  // New is already a successor.
737  // Update its probability instead of adding a duplicate edge.
738  if (!Probs.empty()) {
739  auto ProbIter = getProbabilityIterator(NewI);
740  if (!ProbIter->isUnknown())
741  *ProbIter += *getProbabilityIterator(OldI);
742  }
743  removeSuccessor(OldI);
744 }
745 
747  succ_iterator I) {
748  if (Orig->Probs.empty())
749  addSuccessor(*I, Orig->getSuccProbability(I));
750  else
752 }
753 
754 void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) {
755  Predecessors.push_back(Pred);
756 }
757 
758 void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) {
759  pred_iterator I = find(Predecessors, Pred);
760  assert(I != Predecessors.end() && "Pred is not a predecessor of this block!");
761  Predecessors.erase(I);
762 }
763 
765  if (this == FromMBB)
766  return;
767 
768  while (!FromMBB->succ_empty()) {
769  MachineBasicBlock *Succ = *FromMBB->succ_begin();
770 
771  // If probability list is empty it means we don't use it (disabled optimization).
772  if (!FromMBB->Probs.empty()) {
773  auto Prob = *FromMBB->Probs.begin();
774  addSuccessor(Succ, Prob);
775  } else
777 
778  FromMBB->removeSuccessor(Succ);
779  }
780 }
781 
782 void
784  if (this == FromMBB)
785  return;
786 
787  while (!FromMBB->succ_empty()) {
788  MachineBasicBlock *Succ = *FromMBB->succ_begin();
789  if (!FromMBB->Probs.empty()) {
790  auto Prob = *FromMBB->Probs.begin();
791  addSuccessor(Succ, Prob);
792  } else
794  FromMBB->removeSuccessor(Succ);
795 
796  // Fix up any PHI nodes in the successor.
798  ME = Succ->instr_end(); MI != ME && MI->isPHI(); ++MI)
799  for (unsigned i = 2, e = MI->getNumOperands()+1; i != e; i += 2) {
800  MachineOperand &MO = MI->getOperand(i);
801  if (MO.getMBB() == FromMBB)
802  MO.setMBB(this);
803  }
804  }
806 }
807 
809  return is_contained(predecessors(), MBB);
810 }
811 
813  return is_contained(successors(), MBB);
814 }
815 
818  return std::next(I) == MachineFunction::const_iterator(MBB);
819 }
820 
822  MachineFunction::iterator Fallthrough = getIterator();
823  ++Fallthrough;
824  // If FallthroughBlock is off the end of the function, it can't fall through.
825  if (Fallthrough == getParent()->end())
826  return nullptr;
827 
828  // If FallthroughBlock isn't a successor, no fallthrough is possible.
829  if (!isSuccessor(&*Fallthrough))
830  return nullptr;
831 
832  // Analyze the branches, if any, at the end of the block.
833  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
836  if (TII->analyzeBranch(*this, TBB, FBB, Cond)) {
837  // If we couldn't analyze the branch, examine the last instruction.
838  // If the block doesn't end in a known control barrier, assume fallthrough
839  // is possible. The isPredicated check is needed because this code can be
840  // called during IfConversion, where an instruction which is normally a
841  // Barrier is predicated and thus no longer an actual control barrier.
842  return (empty() || !back().isBarrier() || TII->isPredicated(back()))
843  ? &*Fallthrough
844  : nullptr;
845  }
846 
847  // If there is no branch, control always falls through.
848  if (!TBB) return &*Fallthrough;
849 
850  // If there is some explicit branch to the fallthrough block, it can obviously
851  // reach, even though the branch should get folded to fall through implicitly.
852  if (MachineFunction::iterator(TBB) == Fallthrough ||
853  MachineFunction::iterator(FBB) == Fallthrough)
854  return &*Fallthrough;
855 
856  // If it's an unconditional branch to some block not the fall through, it
857  // doesn't fall through.
858  if (Cond.empty()) return nullptr;
859 
860  // Otherwise, if it is conditional and has no explicit false block, it falls
861  // through.
862  return (FBB == nullptr) ? &*Fallthrough : nullptr;
863 }
864 
866  return getFallThrough() != nullptr;
867 }
868 
870  Pass &P) {
871  if (!canSplitCriticalEdge(Succ))
872  return nullptr;
873 
874  MachineFunction *MF = getParent();
875  DebugLoc DL; // FIXME: this is nowhere
876 
878  MF->insert(std::next(MachineFunction::iterator(this)), NMBB);
879  LLVM_DEBUG(dbgs() << "Splitting critical edge: " << printMBBReference(*this)
880  << " -- " << printMBBReference(*NMBB) << " -- "
881  << printMBBReference(*Succ) << '\n');
882 
885  if (LIS)
886  LIS->insertMBBInMaps(NMBB);
887  else if (Indexes)
888  Indexes->insertMBBInMaps(NMBB);
889 
890  // On some targets like Mips, branches may kill virtual registers. Make sure
891  // that LiveVariables is properly updated after updateTerminator replaces the
892  // terminators.
894 
895  // Collect a list of virtual registers killed by the terminators.
896  SmallVector<unsigned, 4> KilledRegs;
897  if (LV)
899  I != E; ++I) {
900  MachineInstr *MI = &*I;
902  OE = MI->operands_end(); OI != OE; ++OI) {
903  if (!OI->isReg() || OI->getReg() == 0 ||
904  !OI->isUse() || !OI->isKill() || OI->isUndef())
905  continue;
906  unsigned Reg = OI->getReg();
908  LV->getVarInfo(Reg).removeKill(*MI)) {
909  KilledRegs.push_back(Reg);
910  LLVM_DEBUG(dbgs() << "Removing terminator kill: " << *MI);
911  OI->setIsKill(false);
912  }
913  }
914  }
915 
916  SmallVector<unsigned, 4> UsedRegs;
917  if (LIS) {
919  I != E; ++I) {
920  MachineInstr *MI = &*I;
921 
923  OE = MI->operands_end(); OI != OE; ++OI) {
924  if (!OI->isReg() || OI->getReg() == 0)
925  continue;
926 
927  unsigned Reg = OI->getReg();
928  if (!is_contained(UsedRegs, Reg))
929  UsedRegs.push_back(Reg);
930  }
931  }
932  }
933 
934  ReplaceUsesOfBlockWith(Succ, NMBB);
935 
936  // If updateTerminator() removes instructions, we need to remove them from
937  // SlotIndexes.
938  SmallVector<MachineInstr*, 4> Terminators;
939  if (Indexes) {
941  I != E; ++I)
942  Terminators.push_back(&*I);
943  }
944 
946 
947  if (Indexes) {
948  SmallVector<MachineInstr*, 4> NewTerminators;
950  I != E; ++I)
951  NewTerminators.push_back(&*I);
952 
953  for (SmallVectorImpl<MachineInstr*>::iterator I = Terminators.begin(),
954  E = Terminators.end(); I != E; ++I) {
955  if (!is_contained(NewTerminators, *I))
956  Indexes->removeMachineInstrFromMaps(**I);
957  }
958  }
959 
960  // Insert unconditional "jump Succ" instruction in NMBB if necessary.
961  NMBB->addSuccessor(Succ);
962  if (!NMBB->isLayoutSuccessor(Succ)) {
965  TII->insertBranch(*NMBB, Succ, nullptr, Cond, DL);
966 
967  if (Indexes) {
968  for (MachineInstr &MI : NMBB->instrs()) {
969  // Some instructions may have been moved to NMBB by updateTerminator(),
970  // so we first remove any instruction that already has an index.
971  if (Indexes->hasIndex(MI))
972  Indexes->removeMachineInstrFromMaps(MI);
973  Indexes->insertMachineInstrInMaps(MI);
974  }
975  }
976  }
977 
978  // Fix PHI nodes in Succ so they refer to NMBB instead of this
980  i = Succ->instr_begin(),e = Succ->instr_end();
981  i != e && i->isPHI(); ++i)
982  for (unsigned ni = 1, ne = i->getNumOperands(); ni != ne; ni += 2)
983  if (i->getOperand(ni+1).getMBB() == this)
984  i->getOperand(ni+1).setMBB(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  unsigned 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 = TargetRegisterInfo::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 
1216 /// Various pieces of code can cause excess edges in the CFG to be inserted. If
1217 /// we have proven that MBB can only branch to DestA and DestB, remove any other
1218 /// MBB successors from the CFG. DestA and DestB can be null.
1219 ///
1220 /// Besides DestA and DestB, retain other edges leading to LandingPads
1221 /// (currently there can be only one; we don't check or require that here).
1222 /// Note it is possible that DestA and/or DestB are LandingPads.
1224  MachineBasicBlock *DestB,
1225  bool IsCond) {
1226  // The values of DestA and DestB frequently come from a call to the
1227  // 'TargetInstrInfo::AnalyzeBranch' method. We take our meaning of the initial
1228  // values from there.
1229  //
1230  // 1. If both DestA and DestB are null, then the block ends with no branches
1231  // (it falls through to its successor).
1232  // 2. If DestA is set, DestB is null, and IsCond is false, then the block ends
1233  // with only an unconditional branch.
1234  // 3. If DestA is set, DestB is null, and IsCond is true, then the block ends
1235  // with a conditional branch that falls through to a successor (DestB).
1236  // 4. If DestA and DestB is set and IsCond is true, then the block ends with a
1237  // conditional branch followed by an unconditional branch. DestA is the
1238  // 'true' destination and DestB is the 'false' destination.
1239 
1240  bool Changed = false;
1241 
1242  MachineBasicBlock *FallThru = getNextNode();
1243 
1244  if (!DestA && !DestB) {
1245  // Block falls through to successor.
1246  DestA = FallThru;
1247  DestB = FallThru;
1248  } else if (DestA && !DestB) {
1249  if (IsCond)
1250  // Block ends in conditional jump that falls through to successor.
1251  DestB = FallThru;
1252  } else {
1253  assert(DestA && DestB && IsCond &&
1254  "CFG in a bad state. Cannot correct CFG edges");
1255  }
1256 
1257  // Remove superfluous edges. I.e., those which aren't destinations of this
1258  // basic block, duplicate edges, or landing pads.
1261  while (SI != succ_end()) {
1262  const MachineBasicBlock *MBB = *SI;
1263  if (!SeenMBBs.insert(MBB).second ||
1264  (MBB != DestA && MBB != DestB && !MBB->isEHPad())) {
1265  // This is a superfluous edge, remove it.
1266  SI = removeSuccessor(SI);
1267  Changed = true;
1268  } else {
1269  ++SI;
1270  }
1271  }
1272 
1273  if (Changed)
1275  return Changed;
1276 }
1277 
1278 /// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE
1279 /// instructions. Return UnknownLoc if there is none.
1280 DebugLoc
1282  // Skip debug declarations, we don't want a DebugLoc from them.
1283  MBBI = skipDebugInstructionsForward(MBBI, instr_end());
1284  if (MBBI != instr_end())
1285  return MBBI->getDebugLoc();
1286  return {};
1287 }
1288 
1289 /// Find the previous valid DebugLoc preceding MBBI, skipping and DBG_VALUE
1290 /// instructions. Return UnknownLoc if there is none.
1292  if (MBBI == instr_begin()) return {};
1293  // Skip debug declarations, we don't want a DebugLoc from them.
1294  MBBI = skipDebugInstructionsBackward(std::prev(MBBI), instr_begin());
1295  if (!MBBI->isDebugInstr()) return MBBI->getDebugLoc();
1296  return {};
1297 }
1298 
1299 /// Find and return the merged DebugLoc of the branch instructions of the block.
1300 /// Return UnknownLoc if there is none.
1301 DebugLoc
1303  DebugLoc DL;
1304  auto TI = getFirstTerminator();
1305  while (TI != end() && !TI->isBranch())
1306  ++TI;
1307 
1308  if (TI != end()) {
1309  DL = TI->getDebugLoc();
1310  for (++TI ; TI != end() ; ++TI)
1311  if (TI->isBranch())
1312  DL = DILocation::getMergedLocation(DL, TI->getDebugLoc());
1313  }
1314  return DL;
1315 }
1316 
1317 /// Return probability of the edge from this block to MBB.
1319 MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const {
1320  if (Probs.empty())
1321  return BranchProbability(1, succ_size());
1322 
1323  const auto &Prob = *getProbabilityIterator(Succ);
1324  if (Prob.isUnknown()) {
1325  // For unknown probabilities, collect the sum of all known ones, and evenly
1326  // ditribute the complemental of the sum to each unknown probability.
1327  unsigned KnownProbNum = 0;
1328  auto Sum = BranchProbability::getZero();
1329  for (auto &P : Probs) {
1330  if (!P.isUnknown()) {
1331  Sum += P;
1332  KnownProbNum++;
1333  }
1334  }
1335  return Sum.getCompl() / (Probs.size() - KnownProbNum);
1336  } else
1337  return Prob;
1338 }
1339 
1340 /// Set successor probability of a given iterator.
1342  BranchProbability Prob) {
1343  assert(!Prob.isUnknown());
1344  if (Probs.empty())
1345  return;
1346  *getProbabilityIterator(I) = Prob;
1347 }
1348 
1349 /// Return probability iterator corresonding to the I successor iterator
1350 MachineBasicBlock::const_probability_iterator
1351 MachineBasicBlock::getProbabilityIterator(
1353  assert(Probs.size() == Successors.size() && "Async probability list!");
1354  const size_t index = std::distance(Successors.begin(), I);
1355  assert(index < Probs.size() && "Not a current successor!");
1356  return Probs.begin() + index;
1357 }
1358 
1359 /// Return probability iterator corresonding to the I successor iterator.
1360 MachineBasicBlock::probability_iterator
1361 MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) {
1362  assert(Probs.size() == Successors.size() && "Async probability list!");
1363  const size_t index = std::distance(Successors.begin(), I);
1364  assert(index < Probs.size() && "Not a current successor!");
1365  return Probs.begin() + index;
1366 }
1367 
1368 /// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed
1369 /// as of just before "MI".
1370 ///
1371 /// Search is localised to a neighborhood of
1372 /// Neighborhood instructions before (searching for defs or kills) and N
1373 /// instructions after (searching just for defs) MI.
1376  unsigned Reg, const_iterator Before,
1377  unsigned Neighborhood) const {
1378  unsigned N = Neighborhood;
1379 
1380  // Try searching forwards from Before, looking for reads or defs.
1381  const_iterator I(Before);
1382  for (; I != end() && N > 0; ++I) {
1383  if (I->isDebugInstr())
1384  continue;
1385 
1386  --N;
1387 
1389  ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
1390 
1391  // Register is live when we read it here.
1392  if (Info.Read)
1393  return LQR_Live;
1394  // Register is dead if we can fully overwrite or clobber it here.
1395  if (Info.FullyDefined || Info.Clobbered)
1396  return LQR_Dead;
1397  }
1398 
1399  // If we reached the end, it is safe to clobber Reg at the end of a block of
1400  // no successor has it live in.
1401  if (I == end()) {
1402  for (MachineBasicBlock *S : successors()) {
1403  for (const MachineBasicBlock::RegisterMaskPair &LI : S->liveins()) {
1404  if (TRI->regsOverlap(LI.PhysReg, Reg))
1405  return LQR_Live;
1406  }
1407  }
1408 
1409  return LQR_Dead;
1410  }
1411 
1412 
1413  N = Neighborhood;
1414 
1415  // Start by searching backwards from Before, looking for kills, reads or defs.
1416  I = const_iterator(Before);
1417  // If this is the first insn in the block, don't search backwards.
1418  if (I != begin()) {
1419  do {
1420  --I;
1421 
1422  if (I->isDebugInstr())
1423  continue;
1424 
1425  --N;
1426 
1428  ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
1429 
1430  // Defs happen after uses so they take precedence if both are present.
1431 
1432  // Register is dead after a dead def of the full register.
1433  if (Info.DeadDef)
1434  return LQR_Dead;
1435  // Register is (at least partially) live after a def.
1436  if (Info.Defined) {
1437  if (!Info.PartialDeadDef)
1438  return LQR_Live;
1439  // As soon as we saw a partial definition (dead or not),
1440  // we cannot tell if the value is partial live without
1441  // tracking the lanemasks. We are not going to do this,
1442  // so fall back on the remaining of the analysis.
1443  break;
1444  }
1445  // Register is dead after a full kill or clobber and no def.
1446  if (Info.Killed || Info.Clobbered)
1447  return LQR_Dead;
1448  // Register must be live if we read it.
1449  if (Info.Read)
1450  return LQR_Live;
1451 
1452  } while (I != begin() && N > 0);
1453  }
1454 
1455  // Did we get to the start of the block?
1456  if (I == begin()) {
1457  // If so, the register's state is definitely defined by the live-in state.
1458  for (const MachineBasicBlock::RegisterMaskPair &LI : liveins())
1459  if (TRI->regsOverlap(LI.PhysReg, Reg))
1460  return LQR_Live;
1461 
1462  return LQR_Dead;
1463  }
1464 
1465  // At this point we have no idea of the liveness of the register.
1466  return LQR_Unknown;
1467 }
1468 
1469 const uint32_t *
1471  // EH funclet entry does not preserve any registers.
1472  return isEHFuncletEntry() ? TRI->getNoPreservedMask() : nullptr;
1473 }
1474 
1475 const uint32_t *
1477  // If we see a return block with successors, this must be a funclet return,
1478  // which does not preserve any registers. If there are no successors, we don't
1479  // care what kind of return it is, putting a mask after it is a no-op.
1480  return isReturnBlock() && !succ_empty() ? TRI->getNoPreservedMask() : nullptr;
1481 }
1482 
1484  LiveIns.clear();
1485 }
1486 
1488  assert(getParent()->getProperties().hasProperty(
1490  "Liveness information is accurate");
1491  return LiveIns.begin();
1492 }
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:292
mop_iterator operands_end()
Definition: MachineInstr.h:453
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: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:266
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:464
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...
static unsigned index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:64
static const DILocation * getMergedLocation(const DILocation *LocA, const DILocation *LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
bool isBundledWithPred() const
Return true if this instruction is part of a bundle, and it is not the first instruction in the bundl...
Definition: MachineInstr.h:361
instr_iterator getFirstInstrTerminator()
Same getFirstTerminator but it ignores bundles and return an instr_iterator instead.
void push_back(const T &Elt)
Definition: SmallVector.h:217
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:637
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:123
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:854
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:90
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
VNInfo - Value Number Information.
Definition: LiveInterval.h:52
bool isPHI() const
virtual unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const
Remove the branching code at the end of the specific MBB.
MachineBasicBlock * removeFromParent()
This method unlinks &#39;this&#39; from the containing function, and returns it, but does not delete it...
BasicBlockListType::const_iterator const_iterator
void removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll())
Remove the specified register from the live in set.
iterator_range< succ_iterator > successors()
bool removeKill(MachineInstr &MI)
removeKill - Delete a kill corresponding to the specified machine instruction.
Definition: LiveVariables.h: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.
amdgpu Simplify well known AMD library false Value Value const Twine & Name
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:411
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:365
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:413
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:62
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:330
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:162
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:349
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...
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:408
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:250
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:388
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:128
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
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:408
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:299
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Definition: SlotIndexes.h:492
void clearFlag(MIFlag Flag)
clearFlag - Clear a MI flag.
Definition: MachineInstr.h:310
StringRef getPrivateLabelPrefix() const
Definition: MCAsmInfo.h:491
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:81
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:1213
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:840
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:1206
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:1115
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()
bool regsOverlap(unsigned regA, unsigned regB) const
Returns true if the two registers are equal or alias each other.
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:846
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: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
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:253
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:63
pointer remove(iterator &IT)
Definition: ilist.h:250
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:132
iterator insert(iterator where, pointer New)
Definition: ilist.h:227
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:122
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:213
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:1212
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:476
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:2038
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:452
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: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:639
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.
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:413
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:294
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:72
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:1244