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