LLVM  7.0.0svn
MachineBasicBlock.cpp
Go to the documentation of this file.
1 //===-- llvm/CodeGen/MachineBasicBlock.cpp ----------------------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Collect the sequence of machine instructions for a basic block.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/SmallPtrSet.h"
27 #include "llvm/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 }
113 
114 /// When we remove an instruction from a basic block list, we update its parent
115 /// pointer and remove its operands from reg use/def lists if appropriate.
117  assert(N->getParent() && "machine instruction not in a basic block");
118 
119  // Remove from the use/def lists.
120  if (MachineFunction *MF = N->getMF())
121  N->RemoveRegOperandsFromUseLists(MF->getRegInfo());
122 
123  N->setParent(nullptr);
124 }
125 
126 /// When moving a range of instructions from one MBB list to another, we need to
127 /// update the parent pointers and the use/def lists.
129  instr_iterator First,
130  instr_iterator Last) {
131  assert(Parent->getParent() == FromList.Parent->getParent() &&
132  "MachineInstr parent mismatch!");
133  assert(this != &FromList && "Called without a real transfer...");
134  assert(Parent != FromList.Parent && "Two lists have the same parent?");
135 
136  // If splicing between two blocks within the same function, just update the
137  // parent pointers.
138  for (; First != Last; ++First)
139  First->setParent(Parent);
140 }
141 
143  assert(!MI->getParent() && "MI is still in a block!");
144  Parent->getParent()->DeleteMachineInstr(MI);
145 }
146 
149  while (I != E && I->isPHI())
150  ++I;
151  assert((I == E || !I->isInsideBundle()) &&
152  "First non-phi MI cannot be inside a bundle!");
153  return I;
154 }
155 
159 
160  iterator E = end();
161  while (I != E && (I->isPHI() || I->isPosition() ||
162  TII->isBasicBlockPrologue(*I)))
163  ++I;
164  // FIXME: This needs to change if we wish to bundle labels
165  // inside the bundle.
166  assert((I == E || !I->isInsideBundle()) &&
167  "First non-phi / non-label instruction is inside a bundle!");
168  return I;
169 }
170 
174 
175  iterator E = end();
176  while (I != E && (I->isPHI() || I->isPosition() || I->isDebugValue() ||
177  TII->isBasicBlockPrologue(*I)))
178  ++I;
179  // FIXME: This needs to change if we wish to bundle labels / dbg_values
180  // inside the bundle.
181  assert((I == E || !I->isInsideBundle()) &&
182  "First non-phi / non-label / non-debug "
183  "instruction is inside a bundle!");
184  return I;
185 }
186 
188  iterator B = begin(), E = end(), I = E;
189  while (I != B && ((--I)->isTerminator() || I->isDebugValue()))
190  ; /*noop */
191  while (I != E && !I->isTerminator())
192  ++I;
193  return I;
194 }
195 
197  instr_iterator B = instr_begin(), E = instr_end(), I = E;
198  while (I != B && ((--I)->isTerminator() || I->isDebugValue()))
199  ; /*noop */
200  while (I != E && !I->isTerminator())
201  ++I;
202  return I;
203 }
204 
206  // Skip over begin-of-block dbg_value instructions.
208 }
209 
211  // Skip over end-of-block dbg_value instructions.
213  while (I != B) {
214  --I;
215  // Return instruction that starts a bundle.
216  if (I->isDebugValue() || I->isInsideBundle())
217  continue;
218  return I;
219  }
220  // The block is all debug values.
221  return end();
222 }
223 
225  for (const_succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I)
226  if ((*I)->isEHPad())
227  return true;
228  return false;
229 }
230 
231 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
233  print(dbgs());
234 }
235 #endif
236 
238  if (isReturnBlock() || hasEHPadSuccessor())
239  return false;
240  return true;
241 }
242 
244  if (const BasicBlock *LBB = getBasicBlock())
245  return LBB->getName();
246  else
247  return StringRef("", 0);
248 }
249 
250 /// Return a hopefully unique identifier for this block.
251 std::string MachineBasicBlock::getFullName() const {
252  std::string Name;
253  if (getParent())
254  Name = (getParent()->getName() + ":").str();
255  if (getBasicBlock())
256  Name += getBasicBlock()->getName();
257  else
258  Name += ("BB" + Twine(getNumber())).str();
259  return Name;
260 }
261 
263  const {
264  const MachineFunction *MF = getParent();
265  if (!MF) {
266  OS << "Can't print out MachineBasicBlock because parent MachineFunction"
267  << " is null\n";
268  return;
269  }
270  const Function &F = MF->getFunction();
271  const Module *M = F.getParent();
272  ModuleSlotTracker MST(M);
273  print(OS, MST, Indexes);
274 }
275 
277  const SlotIndexes *Indexes) const {
278  const MachineFunction *MF = getParent();
279  if (!MF) {
280  OS << "Can't print out MachineBasicBlock because parent MachineFunction"
281  << " is null\n";
282  return;
283  }
284 
285  if (Indexes)
286  OS << Indexes->getMBBStartIdx(this) << '\t';
287 
288  OS << printMBBReference(*this) << ": ";
289 
290  const char *Comma = "";
291  if (const BasicBlock *LBB = getBasicBlock()) {
292  OS << Comma << "derived from LLVM BB ";
293  LBB->printAsOperand(OS, /*PrintType=*/false, MST);
294  Comma = ", ";
295  }
296  if (isEHPad()) { OS << Comma << "EH LANDING PAD"; Comma = ", "; }
297  if (hasAddressTaken()) { OS << Comma << "ADDRESS TAKEN"; Comma = ", "; }
298  if (Alignment)
299  OS << Comma << "Align " << Alignment << " (" << (1u << Alignment)
300  << " bytes)";
301 
302  OS << '\n';
303 
304  const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
305  if (!livein_empty()) {
306  if (Indexes) OS << '\t';
307  OS << " Live Ins:";
308  for (const auto &LI : LiveIns) {
309  OS << ' ' << printReg(LI.PhysReg, TRI);
310  if (!LI.LaneMask.all())
311  OS << ':' << PrintLaneMask(LI.LaneMask);
312  }
313  OS << '\n';
314  }
315  // Print the preds of this block according to the CFG.
316  if (!pred_empty()) {
317  if (Indexes) OS << '\t';
318  OS << " Predecessors according to CFG:";
319  for (const_pred_iterator PI = pred_begin(), E = pred_end(); PI != E; ++PI)
320  OS << " " << printMBBReference(*(*PI));
321  OS << '\n';
322  }
323 
324  for (auto &I : instrs()) {
325  if (Indexes) {
326  if (Indexes->hasIndex(I))
327  OS << Indexes->getInstructionIndex(I);
328  OS << '\t';
329  }
330  OS << '\t';
331  if (I.isInsideBundle())
332  OS << " * ";
333  I.print(OS, MST);
334  }
335 
336  // Print the successors of this block according to the CFG.
337  if (!succ_empty()) {
338  if (Indexes) OS << '\t';
339  OS << " Successors according to CFG:";
340  for (const_succ_iterator SI = succ_begin(), E = succ_end(); SI != E; ++SI) {
341  OS << " " << printMBBReference(*(*SI));
342  if (!Probs.empty())
343  OS << '(' << *getProbabilityIterator(SI) << ')';
344  }
345  OS << '\n';
346  }
347  if (IrrLoopHeaderWeight) {
348  if (Indexes) OS << '\t';
349  OS << " Irreducible loop header weight: "
350  << IrrLoopHeaderWeight.getValue();
351  OS << '\n';
352  }
353 }
354 
356  bool /*PrintType*/) const {
357  OS << "%bb." << getNumber();
358 }
359 
361  LiveInVector::iterator I = find_if(
362  LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
363  if (I == LiveIns.end())
364  return;
365 
366  I->LaneMask &= ~LaneMask;
367  if (I->LaneMask.none())
368  LiveIns.erase(I);
369 }
370 
373  // Get non-const version of iterator.
374  LiveInVector::iterator LI = LiveIns.begin() + (I - LiveIns.begin());
375  return LiveIns.erase(LI);
376 }
377 
380  LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
381  return I != livein_end() && (I->LaneMask & LaneMask).any();
382 }
383 
385  std::sort(LiveIns.begin(), LiveIns.end(),
386  [](const RegisterMaskPair &LI0, const RegisterMaskPair &LI1) {
387  return LI0.PhysReg < LI1.PhysReg;
388  });
389  // Liveins are sorted by physreg now we can merge their lanemasks.
390  LiveInVector::const_iterator I = LiveIns.begin();
391  LiveInVector::const_iterator J;
392  LiveInVector::iterator Out = LiveIns.begin();
393  for (; I != LiveIns.end(); ++Out, I = J) {
394  unsigned PhysReg = I->PhysReg;
395  LaneBitmask LaneMask = I->LaneMask;
396  for (J = std::next(I); J != LiveIns.end() && J->PhysReg == PhysReg; ++J)
397  LaneMask |= J->LaneMask;
398  Out->PhysReg = PhysReg;
399  Out->LaneMask = LaneMask;
400  }
401  LiveIns.erase(Out, LiveIns.end());
402 }
403 
404 unsigned
406  assert(getParent() && "MBB must be inserted in function");
407  assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && "Expected physreg");
408  assert(RC && "Register class is required");
409  assert((isEHPad() || this == &getParent()->front()) &&
410  "Only the entry block and landing pads can have physreg live ins");
411 
412  bool LiveIn = isLiveIn(PhysReg);
416 
417  // Look for an existing copy.
418  if (LiveIn)
419  for (;I != E && I->isCopy(); ++I)
420  if (I->getOperand(1).getReg() == PhysReg) {
421  unsigned VirtReg = I->getOperand(0).getReg();
422  if (!MRI.constrainRegClass(VirtReg, RC))
423  llvm_unreachable("Incompatible live-in register class.");
424  return VirtReg;
425  }
426 
427  // No luck, create a virtual register.
428  unsigned VirtReg = MRI.createVirtualRegister(RC);
429  BuildMI(*this, I, DebugLoc(), TII.get(TargetOpcode::COPY), VirtReg)
430  .addReg(PhysReg, RegState::Kill);
431  if (!LiveIn)
432  addLiveIn(PhysReg);
433  return VirtReg;
434 }
435 
437  getParent()->splice(NewAfter->getIterator(), getIterator());
438 }
439 
441  getParent()->splice(++NewBefore->getIterator(), getIterator());
442 }
443 
446  // A block with no successors has no concerns with fall-through edges.
447  if (this->succ_empty())
448  return;
449 
450  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
453  bool B = TII->analyzeBranch(*this, TBB, FBB, Cond);
454  (void) B;
455  assert(!B && "UpdateTerminators requires analyzable predecessors!");
456  if (Cond.empty()) {
457  if (TBB) {
458  // The block has an unconditional branch. If its successor is now its
459  // layout successor, delete the branch.
460  if (isLayoutSuccessor(TBB))
461  TII->removeBranch(*this);
462  } else {
463  // The block has an unconditional fallthrough. If its successor is not its
464  // layout successor, insert a branch. First we have to locate the only
465  // non-landing-pad successor, as that is the fallthrough block.
466  for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) {
467  if ((*SI)->isEHPad())
468  continue;
469  assert(!TBB && "Found more than one non-landing-pad successor!");
470  TBB = *SI;
471  }
472 
473  // If there is no non-landing-pad successor, the block has no fall-through
474  // edges to be concerned with.
475  if (!TBB)
476  return;
477 
478  // Finally update the unconditional successor to be reached via a branch
479  // if it would not be reached by fallthrough.
480  if (!isLayoutSuccessor(TBB))
481  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
482  }
483  return;
484  }
485 
486  if (FBB) {
487  // The block has a non-fallthrough conditional branch. If one of its
488  // successors is its layout successor, rewrite it to a fallthrough
489  // conditional branch.
490  if (isLayoutSuccessor(TBB)) {
491  if (TII->reverseBranchCondition(Cond))
492  return;
493  TII->removeBranch(*this);
494  TII->insertBranch(*this, FBB, nullptr, Cond, DL);
495  } else if (isLayoutSuccessor(FBB)) {
496  TII->removeBranch(*this);
497  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
498  }
499  return;
500  }
501 
502  // Walk through the successors and find the successor which is not a landing
503  // pad and is not the conditional branch destination (in TBB) as the
504  // fallthrough successor.
505  MachineBasicBlock *FallthroughBB = nullptr;
506  for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) {
507  if ((*SI)->isEHPad() || *SI == TBB)
508  continue;
509  assert(!FallthroughBB && "Found more than one fallthrough successor.");
510  FallthroughBB = *SI;
511  }
512 
513  if (!FallthroughBB) {
514  if (canFallThrough()) {
515  // We fallthrough to the same basic block as the conditional jump targets.
516  // Remove the conditional jump, leaving unconditional fallthrough.
517  // FIXME: This does not seem like a reasonable pattern to support, but it
518  // has been seen in the wild coming out of degenerate ARM test cases.
519  TII->removeBranch(*this);
520 
521  // Finally update the unconditional successor to be reached via a branch if
522  // it would not be reached by fallthrough.
523  if (!isLayoutSuccessor(TBB))
524  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
525  return;
526  }
527 
528  // We enter here iff exactly one successor is TBB which cannot fallthrough
529  // and the rest successors if any are EHPads. In this case, we need to
530  // change the conditional branch into unconditional branch.
531  TII->removeBranch(*this);
532  Cond.clear();
533  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
534  return;
535  }
536 
537  // The block has a fallthrough conditional branch.
538  if (isLayoutSuccessor(TBB)) {
539  if (TII->reverseBranchCondition(Cond)) {
540  // We can't reverse the condition, add an unconditional branch.
541  Cond.clear();
542  TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
543  return;
544  }
545  TII->removeBranch(*this);
546  TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
547  } else if (!isLayoutSuccessor(FallthroughBB)) {
548  TII->removeBranch(*this);
549  TII->insertBranch(*this, TBB, FallthroughBB, Cond, DL);
550  }
551 }
552 
554 #ifndef NDEBUG
555  int64_t Sum = 0;
556  for (auto Prob : Probs)
557  Sum += Prob.getNumerator();
558  // Due to precision issue, we assume that the sum of probabilities is one if
559  // the difference between the sum of their numerators and the denominator is
560  // no greater than the number of successors.
562  Probs.size() &&
563  "The sum of successors's probabilities exceeds one.");
564 #endif // NDEBUG
565 }
566 
568  BranchProbability Prob) {
569  // Probability list is either empty (if successor list isn't empty, this means
570  // disabled optimization) or has the same size as successor list.
571  if (!(Probs.empty() && !Successors.empty()))
572  Probs.push_back(Prob);
573  Successors.push_back(Succ);
574  Succ->addPredecessor(this);
575 }
576 
578  // We need to make sure probability list is either empty or has the same size
579  // of successor list. When this function is called, we can safely delete all
580  // probability in the list.
581  Probs.clear();
582  Successors.push_back(Succ);
583  Succ->addPredecessor(this);
584 }
585 
587  bool NormalizeSuccProbs) {
588  succ_iterator I = find(Successors, Succ);
589  removeSuccessor(I, NormalizeSuccProbs);
590 }
591 
594  assert(I != Successors.end() && "Not a current successor!");
595 
596  // If probability list is empty it means we don't use it (disabled
597  // optimization).
598  if (!Probs.empty()) {
599  probability_iterator WI = getProbabilityIterator(I);
600  Probs.erase(WI);
601  if (NormalizeSuccProbs)
603  }
604 
605  (*I)->removePredecessor(this);
606  return Successors.erase(I);
607 }
608 
610  MachineBasicBlock *New) {
611  if (Old == New)
612  return;
613 
615  succ_iterator NewI = E;
616  succ_iterator OldI = E;
617  for (succ_iterator I = succ_begin(); I != E; ++I) {
618  if (*I == Old) {
619  OldI = I;
620  if (NewI != E)
621  break;
622  }
623  if (*I == New) {
624  NewI = I;
625  if (OldI != E)
626  break;
627  }
628  }
629  assert(OldI != E && "Old is not a successor of this block");
630 
631  // If New isn't already a successor, let it take Old's place.
632  if (NewI == E) {
633  Old->removePredecessor(this);
634  New->addPredecessor(this);
635  *OldI = New;
636  return;
637  }
638 
639  // New is already a successor.
640  // Update its probability instead of adding a duplicate edge.
641  if (!Probs.empty()) {
642  auto ProbIter = getProbabilityIterator(NewI);
643  if (!ProbIter->isUnknown())
644  *ProbIter += *getProbabilityIterator(OldI);
645  }
646  removeSuccessor(OldI);
647 }
648 
649 void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) {
650  Predecessors.push_back(Pred);
651 }
652 
653 void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) {
654  pred_iterator I = find(Predecessors, Pred);
655  assert(I != Predecessors.end() && "Pred is not a predecessor of this block!");
656  Predecessors.erase(I);
657 }
658 
660  if (this == FromMBB)
661  return;
662 
663  while (!FromMBB->succ_empty()) {
664  MachineBasicBlock *Succ = *FromMBB->succ_begin();
665 
666  // If probability list is empty it means we don't use it (disabled optimization).
667  if (!FromMBB->Probs.empty()) {
668  auto Prob = *FromMBB->Probs.begin();
669  addSuccessor(Succ, Prob);
670  } else
672 
673  FromMBB->removeSuccessor(Succ);
674  }
675 }
676 
677 void
679  if (this == FromMBB)
680  return;
681 
682  while (!FromMBB->succ_empty()) {
683  MachineBasicBlock *Succ = *FromMBB->succ_begin();
684  if (!FromMBB->Probs.empty()) {
685  auto Prob = *FromMBB->Probs.begin();
686  addSuccessor(Succ, Prob);
687  } else
689  FromMBB->removeSuccessor(Succ);
690 
691  // Fix up any PHI nodes in the successor.
693  ME = Succ->instr_end(); MI != ME && MI->isPHI(); ++MI)
694  for (unsigned i = 2, e = MI->getNumOperands()+1; i != e; i += 2) {
695  MachineOperand &MO = MI->getOperand(i);
696  if (MO.getMBB() == FromMBB)
697  MO.setMBB(this);
698  }
699  }
701 }
702 
704  return is_contained(predecessors(), MBB);
705 }
706 
708  return is_contained(successors(), MBB);
709 }
710 
713  return std::next(I) == MachineFunction::const_iterator(MBB);
714 }
715 
717  MachineFunction::iterator Fallthrough = getIterator();
718  ++Fallthrough;
719  // If FallthroughBlock is off the end of the function, it can't fall through.
720  if (Fallthrough == getParent()->end())
721  return nullptr;
722 
723  // If FallthroughBlock isn't a successor, no fallthrough is possible.
724  if (!isSuccessor(&*Fallthrough))
725  return nullptr;
726 
727  // Analyze the branches, if any, at the end of the block.
728  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
731  if (TII->analyzeBranch(*this, TBB, FBB, Cond)) {
732  // If we couldn't analyze the branch, examine the last instruction.
733  // If the block doesn't end in a known control barrier, assume fallthrough
734  // is possible. The isPredicated check is needed because this code can be
735  // called during IfConversion, where an instruction which is normally a
736  // Barrier is predicated and thus no longer an actual control barrier.
737  return (empty() || !back().isBarrier() || TII->isPredicated(back()))
738  ? &*Fallthrough
739  : nullptr;
740  }
741 
742  // If there is no branch, control always falls through.
743  if (!TBB) return &*Fallthrough;
744 
745  // If there is some explicit branch to the fallthrough block, it can obviously
746  // reach, even though the branch should get folded to fall through implicitly.
747  if (MachineFunction::iterator(TBB) == Fallthrough ||
748  MachineFunction::iterator(FBB) == Fallthrough)
749  return &*Fallthrough;
750 
751  // If it's an unconditional branch to some block not the fall through, it
752  // doesn't fall through.
753  if (Cond.empty()) return nullptr;
754 
755  // Otherwise, if it is conditional and has no explicit false block, it falls
756  // through.
757  return (FBB == nullptr) ? &*Fallthrough : nullptr;
758 }
759 
761  return getFallThrough() != nullptr;
762 }
763 
765  Pass &P) {
766  if (!canSplitCriticalEdge(Succ))
767  return nullptr;
768 
769  MachineFunction *MF = getParent();
770  DebugLoc DL; // FIXME: this is nowhere
771 
773  MF->insert(std::next(MachineFunction::iterator(this)), NMBB);
774  DEBUG(dbgs() << "Splitting critical edge: " << printMBBReference(*this)
775  << " -- " << printMBBReference(*NMBB) << " -- "
776  << printMBBReference(*Succ) << '\n');
777 
780  if (LIS)
781  LIS->insertMBBInMaps(NMBB);
782  else if (Indexes)
783  Indexes->insertMBBInMaps(NMBB);
784 
785  // On some targets like Mips, branches may kill virtual registers. Make sure
786  // that LiveVariables is properly updated after updateTerminator replaces the
787  // terminators.
789 
790  // Collect a list of virtual registers killed by the terminators.
791  SmallVector<unsigned, 4> KilledRegs;
792  if (LV)
794  I != E; ++I) {
795  MachineInstr *MI = &*I;
797  OE = MI->operands_end(); OI != OE; ++OI) {
798  if (!OI->isReg() || OI->getReg() == 0 ||
799  !OI->isUse() || !OI->isKill() || OI->isUndef())
800  continue;
801  unsigned Reg = OI->getReg();
803  LV->getVarInfo(Reg).removeKill(*MI)) {
804  KilledRegs.push_back(Reg);
805  DEBUG(dbgs() << "Removing terminator kill: " << *MI);
806  OI->setIsKill(false);
807  }
808  }
809  }
810 
811  SmallVector<unsigned, 4> UsedRegs;
812  if (LIS) {
814  I != E; ++I) {
815  MachineInstr *MI = &*I;
816 
818  OE = MI->operands_end(); OI != OE; ++OI) {
819  if (!OI->isReg() || OI->getReg() == 0)
820  continue;
821 
822  unsigned Reg = OI->getReg();
823  if (!is_contained(UsedRegs, Reg))
824  UsedRegs.push_back(Reg);
825  }
826  }
827  }
828 
829  ReplaceUsesOfBlockWith(Succ, NMBB);
830 
831  // If updateTerminator() removes instructions, we need to remove them from
832  // SlotIndexes.
833  SmallVector<MachineInstr*, 4> Terminators;
834  if (Indexes) {
836  I != E; ++I)
837  Terminators.push_back(&*I);
838  }
839 
841 
842  if (Indexes) {
843  SmallVector<MachineInstr*, 4> NewTerminators;
845  I != E; ++I)
846  NewTerminators.push_back(&*I);
847 
848  for (SmallVectorImpl<MachineInstr*>::iterator I = Terminators.begin(),
849  E = Terminators.end(); I != E; ++I) {
850  if (!is_contained(NewTerminators, *I))
851  Indexes->removeMachineInstrFromMaps(**I);
852  }
853  }
854 
855  // Insert unconditional "jump Succ" instruction in NMBB if necessary.
856  NMBB->addSuccessor(Succ);
857  if (!NMBB->isLayoutSuccessor(Succ)) {
860  TII->insertBranch(*NMBB, Succ, nullptr, Cond, DL);
861 
862  if (Indexes) {
863  for (MachineInstr &MI : NMBB->instrs()) {
864  // Some instructions may have been moved to NMBB by updateTerminator(),
865  // so we first remove any instruction that already has an index.
866  if (Indexes->hasIndex(MI))
867  Indexes->removeMachineInstrFromMaps(MI);
868  Indexes->insertMachineInstrInMaps(MI);
869  }
870  }
871  }
872 
873  // Fix PHI nodes in Succ so they refer to NMBB instead of this
875  i = Succ->instr_begin(),e = Succ->instr_end();
876  i != e && i->isPHI(); ++i)
877  for (unsigned ni = 1, ne = i->getNumOperands(); ni != ne; ni += 2)
878  if (i->getOperand(ni+1).getMBB() == this)
879  i->getOperand(ni+1).setMBB(NMBB);
880 
881  // Inherit live-ins from the successor
882  for (const auto &LI : Succ->liveins())
883  NMBB->addLiveIn(LI);
884 
885  // Update LiveVariables.
886  const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
887  if (LV) {
888  // Restore kills of virtual registers that were killed by the terminators.
889  while (!KilledRegs.empty()) {
890  unsigned Reg = KilledRegs.pop_back_val();
891  for (instr_iterator I = instr_end(), E = instr_begin(); I != E;) {
892  if (!(--I)->addRegisterKilled(Reg, TRI, /* addIfNotFound= */ false))
893  continue;
895  LV->getVarInfo(Reg).Kills.push_back(&*I);
896  DEBUG(dbgs() << "Restored terminator kill: " << *I);
897  break;
898  }
899  }
900  // Update relevant live-through information.
901  LV->addNewBlock(NMBB, this, Succ);
902  }
903 
904  if (LIS) {
905  // After splitting the edge and updating SlotIndexes, live intervals may be
906  // in one of two situations, depending on whether this block was the last in
907  // the function. If the original block was the last in the function, all
908  // live intervals will end prior to the beginning of the new split block. If
909  // the original block was not at the end of the function, all live intervals
910  // will extend to the end of the new split block.
911 
912  bool isLastMBB =
913  std::next(MachineFunction::iterator(NMBB)) == getParent()->end();
914 
915  SlotIndex StartIndex = Indexes->getMBBEndIdx(this);
916  SlotIndex PrevIndex = StartIndex.getPrevSlot();
917  SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB);
918 
919  // Find the registers used from NMBB in PHIs in Succ.
920  SmallSet<unsigned, 8> PHISrcRegs;
922  I = Succ->instr_begin(), E = Succ->instr_end();
923  I != E && I->isPHI(); ++I) {
924  for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne; ni += 2) {
925  if (I->getOperand(ni+1).getMBB() == NMBB) {
926  MachineOperand &MO = I->getOperand(ni);
927  unsigned Reg = MO.getReg();
928  PHISrcRegs.insert(Reg);
929  if (MO.isUndef())
930  continue;
931 
932  LiveInterval &LI = LIS->getInterval(Reg);
933  VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
934  assert(VNI &&
935  "PHI sources should be live out of their predecessors.");
936  LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
937  }
938  }
939  }
940 
942  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
944  if (PHISrcRegs.count(Reg) || !LIS->hasInterval(Reg))
945  continue;
946 
947  LiveInterval &LI = LIS->getInterval(Reg);
948  if (!LI.liveAt(PrevIndex))
949  continue;
950 
951  bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ));
952  if (isLiveOut && isLastMBB) {
953  VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
954  assert(VNI && "LiveInterval should have VNInfo where it is live.");
955  LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
956  } else if (!isLiveOut && !isLastMBB) {
957  LI.removeSegment(StartIndex, EndIndex);
958  }
959  }
960 
961  // Update all intervals for registers whose uses may have been modified by
962  // updateTerminator().
963  LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs);
964  }
965 
966  if (MachineDominatorTree *MDT =
968  MDT->recordSplitCriticalEdge(this, Succ, NMBB);
969 
971  if (MachineLoop *TIL = MLI->getLoopFor(this)) {
972  // If one or the other blocks were not in a loop, the new block is not
973  // either, and thus LI doesn't need to be updated.
974  if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) {
975  if (TIL == DestLoop) {
976  // Both in the same loop, the NMBB joins loop.
977  DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
978  } else if (TIL->contains(DestLoop)) {
979  // Edge from an outer loop to an inner loop. Add to the outer loop.
980  TIL->addBasicBlockToLoop(NMBB, MLI->getBase());
981  } else if (DestLoop->contains(TIL)) {
982  // Edge from an inner loop to an outer loop. Add to the outer loop.
983  DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
984  } else {
985  // Edge from two loops with no containment relation. Because these
986  // are natural loops, we know that the destination block must be the
987  // header of its loop (adding a branch into a loop elsewhere would
988  // create an irreducible loop).
989  assert(DestLoop->getHeader() == Succ &&
990  "Should not create irreducible loops!");
991  if (MachineLoop *P = DestLoop->getParentLoop())
992  P->addBasicBlockToLoop(NMBB, MLI->getBase());
993  }
994  }
995  }
996 
997  return NMBB;
998 }
999 
1001  const MachineBasicBlock *Succ) const {
1002  // Splitting the critical edge to a landing pad block is non-trivial. Don't do
1003  // it in this generic function.
1004  if (Succ->isEHPad())
1005  return false;
1006 
1007  const MachineFunction *MF = getParent();
1008 
1009  // Performance might be harmed on HW that implements branching using exec mask
1010  // where both sides of the branches are always executed.
1011  if (MF->getTarget().requiresStructuredCFG())
1012  return false;
1013 
1014  // We may need to update this's terminator, but we can't do that if
1015  // AnalyzeBranch fails. If this uses a jump table, we won't touch it.
1016  const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
1017  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1019  // AnalyzeBanch should modify this, since we did not allow modification.
1020  if (TII->analyzeBranch(*const_cast<MachineBasicBlock *>(this), TBB, FBB, Cond,
1021  /*AllowModify*/ false))
1022  return false;
1023 
1024  // Avoid bugpoint weirdness: A block may end with a conditional branch but
1025  // jumps to the same MBB is either case. We have duplicate CFG edges in that
1026  // case that we can't handle. Since this never happens in properly optimized
1027  // code, just skip those edges.
1028  if (TBB && TBB == FBB) {
1029  DEBUG(dbgs() << "Won't split critical edge after degenerate "
1030  << printMBBReference(*this) << '\n');
1031  return false;
1032  }
1033  return true;
1034 }
1035 
1036 /// Prepare MI to be removed from its bundle. This fixes bundle flags on MI's
1037 /// neighboring instructions so the bundle won't be broken by removing MI.
1038 static void unbundleSingleMI(MachineInstr *MI) {
1039  // Removing the first instruction in a bundle.
1040  if (MI->isBundledWithSucc() && !MI->isBundledWithPred())
1041  MI->unbundleFromSucc();
1042  // Removing the last instruction in a bundle.
1043  if (MI->isBundledWithPred() && !MI->isBundledWithSucc())
1044  MI->unbundleFromPred();
1045  // If MI is not bundled, or if it is internal to a bundle, the neighbor flags
1046  // are already fine.
1047 }
1048 
1051  unbundleSingleMI(&*I);
1052  return Insts.erase(I);
1053 }
1054 
1056  unbundleSingleMI(MI);
1059  return Insts.remove(MI);
1060 }
1061 
1064  assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
1065  "Cannot insert instruction with bundle flags");
1066  // Set the bundle flags when inserting inside a bundle.
1067  if (I != instr_end() && I->isBundledWithPred()) {
1070  }
1071  return Insts.insert(I, MI);
1072 }
1073 
1074 /// This method unlinks 'this' from the containing function, and returns it, but
1075 /// does not delete it.
1077  assert(getParent() && "Not embedded in a function!");
1078  getParent()->remove(this);
1079  return this;
1080 }
1081 
1082 /// This method unlinks 'this' from the containing function, and deletes it.
1084  assert(getParent() && "Not embedded in a function!");
1085  getParent()->erase(this);
1086 }
1087 
1088 /// Given a machine basic block that branched to 'Old', change the code and CFG
1089 /// so that it branches to 'New' instead.
1091  MachineBasicBlock *New) {
1092  assert(Old != New && "Cannot replace self with self!");
1093 
1095  while (I != instr_begin()) {
1096  --I;
1097  if (!I->isTerminator()) break;
1098 
1099  // Scan the operands of this machine instruction, replacing any uses of Old
1100  // with New.
1101  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1102  if (I->getOperand(i).isMBB() &&
1103  I->getOperand(i).getMBB() == Old)
1104  I->getOperand(i).setMBB(New);
1105  }
1106 
1107  // Update the successor information.
1108  replaceSuccessor(Old, New);
1109 }
1110 
1111 /// Various pieces of code can cause excess edges in the CFG to be inserted. If
1112 /// we have proven that MBB can only branch to DestA and DestB, remove any other
1113 /// MBB successors from the CFG. DestA and DestB can be null.
1114 ///
1115 /// Besides DestA and DestB, retain other edges leading to LandingPads
1116 /// (currently there can be only one; we don't check or require that here).
1117 /// Note it is possible that DestA and/or DestB are LandingPads.
1119  MachineBasicBlock *DestB,
1120  bool IsCond) {
1121  // The values of DestA and DestB frequently come from a call to the
1122  // 'TargetInstrInfo::AnalyzeBranch' method. We take our meaning of the initial
1123  // values from there.
1124  //
1125  // 1. If both DestA and DestB are null, then the block ends with no branches
1126  // (it falls through to its successor).
1127  // 2. If DestA is set, DestB is null, and IsCond is false, then the block ends
1128  // with only an unconditional branch.
1129  // 3. If DestA is set, DestB is null, and IsCond is true, then the block ends
1130  // with a conditional branch that falls through to a successor (DestB).
1131  // 4. If DestA and DestB is set and IsCond is true, then the block ends with a
1132  // conditional branch followed by an unconditional branch. DestA is the
1133  // 'true' destination and DestB is the 'false' destination.
1134 
1135  bool Changed = false;
1136 
1137  MachineBasicBlock *FallThru = getNextNode();
1138 
1139  if (!DestA && !DestB) {
1140  // Block falls through to successor.
1141  DestA = FallThru;
1142  DestB = FallThru;
1143  } else if (DestA && !DestB) {
1144  if (IsCond)
1145  // Block ends in conditional jump that falls through to successor.
1146  DestB = FallThru;
1147  } else {
1148  assert(DestA && DestB && IsCond &&
1149  "CFG in a bad state. Cannot correct CFG edges");
1150  }
1151 
1152  // Remove superfluous edges. I.e., those which aren't destinations of this
1153  // basic block, duplicate edges, or landing pads.
1156  while (SI != succ_end()) {
1157  const MachineBasicBlock *MBB = *SI;
1158  if (!SeenMBBs.insert(MBB).second ||
1159  (MBB != DestA && MBB != DestB && !MBB->isEHPad())) {
1160  // This is a superfluous edge, remove it.
1161  SI = removeSuccessor(SI);
1162  Changed = true;
1163  } else {
1164  ++SI;
1165  }
1166  }
1167 
1168  if (Changed)
1170  return Changed;
1171 }
1172 
1173 /// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE
1174 /// instructions. Return UnknownLoc if there is none.
1175 DebugLoc
1177  // Skip debug declarations, we don't want a DebugLoc from them.
1178  MBBI = skipDebugInstructionsForward(MBBI, instr_end());
1179  if (MBBI != instr_end())
1180  return MBBI->getDebugLoc();
1181  return {};
1182 }
1183 
1184 /// Find and return the merged DebugLoc of the branch instructions of the block.
1185 /// Return UnknownLoc if there is none.
1186 DebugLoc
1188  DebugLoc DL;
1189  auto TI = getFirstTerminator();
1190  while (TI != end() && !TI->isBranch())
1191  ++TI;
1192 
1193  if (TI != end()) {
1194  DL = TI->getDebugLoc();
1195  for (++TI ; TI != end() ; ++TI)
1196  if (TI->isBranch())
1197  DL = DILocation::getMergedLocation(DL, TI->getDebugLoc());
1198  }
1199  return DL;
1200 }
1201 
1202 /// Return probability of the edge from this block to MBB.
1204 MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const {
1205  if (Probs.empty())
1206  return BranchProbability(1, succ_size());
1207 
1208  const auto &Prob = *getProbabilityIterator(Succ);
1209  if (Prob.isUnknown()) {
1210  // For unknown probabilities, collect the sum of all known ones, and evenly
1211  // ditribute the complemental of the sum to each unknown probability.
1212  unsigned KnownProbNum = 0;
1213  auto Sum = BranchProbability::getZero();
1214  for (auto &P : Probs) {
1215  if (!P.isUnknown()) {
1216  Sum += P;
1217  KnownProbNum++;
1218  }
1219  }
1220  return Sum.getCompl() / (Probs.size() - KnownProbNum);
1221  } else
1222  return Prob;
1223 }
1224 
1225 /// Set successor probability of a given iterator.
1227  BranchProbability Prob) {
1228  assert(!Prob.isUnknown());
1229  if (Probs.empty())
1230  return;
1231  *getProbabilityIterator(I) = Prob;
1232 }
1233 
1234 /// Return probability iterator corresonding to the I successor iterator
1235 MachineBasicBlock::const_probability_iterator
1236 MachineBasicBlock::getProbabilityIterator(
1238  assert(Probs.size() == Successors.size() && "Async probability list!");
1239  const size_t index = std::distance(Successors.begin(), I);
1240  assert(index < Probs.size() && "Not a current successor!");
1241  return Probs.begin() + index;
1242 }
1243 
1244 /// Return probability iterator corresonding to the I successor iterator.
1245 MachineBasicBlock::probability_iterator
1246 MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) {
1247  assert(Probs.size() == Successors.size() && "Async probability list!");
1248  const size_t index = std::distance(Successors.begin(), I);
1249  assert(index < Probs.size() && "Not a current successor!");
1250  return Probs.begin() + index;
1251 }
1252 
1253 /// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed
1254 /// as of just before "MI".
1255 ///
1256 /// Search is localised to a neighborhood of
1257 /// Neighborhood instructions before (searching for defs or kills) and N
1258 /// instructions after (searching just for defs) MI.
1261  unsigned Reg, const_iterator Before,
1262  unsigned Neighborhood) const {
1263  unsigned N = Neighborhood;
1264 
1265  // Start by searching backwards from Before, looking for kills, reads or defs.
1266  const_iterator I(Before);
1267  // If this is the first insn in the block, don't search backwards.
1268  if (I != begin()) {
1269  do {
1270  --I;
1271 
1273  ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
1274 
1275  // Defs happen after uses so they take precedence if both are present.
1276 
1277  // Register is dead after a dead def of the full register.
1278  if (Info.DeadDef)
1279  return LQR_Dead;
1280  // Register is (at least partially) live after a def.
1281  if (Info.Defined) {
1282  if (!Info.PartialDeadDef)
1283  return LQR_Live;
1284  // As soon as we saw a partial definition (dead or not),
1285  // we cannot tell if the value is partial live without
1286  // tracking the lanemasks. We are not going to do this,
1287  // so fall back on the remaining of the analysis.
1288  break;
1289  }
1290  // Register is dead after a full kill or clobber and no def.
1291  if (Info.Killed || Info.Clobbered)
1292  return LQR_Dead;
1293  // Register must be live if we read it.
1294  if (Info.Read)
1295  return LQR_Live;
1296  } while (I != begin() && --N > 0);
1297  }
1298 
1299  // Did we get to the start of the block?
1300  if (I == begin()) {
1301  // If so, the register's state is definitely defined by the live-in state.
1302  for (MCRegAliasIterator RAI(Reg, TRI, /*IncludeSelf=*/true); RAI.isValid();
1303  ++RAI)
1304  if (isLiveIn(*RAI))
1305  return LQR_Live;
1306 
1307  return LQR_Dead;
1308  }
1309 
1310  N = Neighborhood;
1311 
1312  // Try searching forwards from Before, looking for reads or defs.
1313  I = const_iterator(Before);
1314  // If this is the last insn in the block, don't search forwards.
1315  if (I != end()) {
1316  for (++I; I != end() && N > 0; ++I, --N) {
1318  ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
1319 
1320  // Register is live when we read it here.
1321  if (Info.Read)
1322  return LQR_Live;
1323  // Register is dead if we can fully overwrite or clobber it here.
1324  if (Info.FullyDefined || Info.Clobbered)
1325  return LQR_Dead;
1326  }
1327  }
1328 
1329  // At this point we have no idea of the liveness of the register.
1330  return LQR_Unknown;
1331 }
1332 
1333 const uint32_t *
1335  // EH funclet entry does not preserve any registers.
1336  return isEHFuncletEntry() ? TRI->getNoPreservedMask() : nullptr;
1337 }
1338 
1339 const uint32_t *
1341  // If we see a return block with successors, this must be a funclet return,
1342  // which does not preserve any registers. If there are no successors, we don't
1343  // care what kind of return it is, putting a mask after it is a no-op.
1344  return isReturnBlock() && !succ_empty() ? TRI->getNoPreservedMask() : nullptr;
1345 }
1346 
1348  LiveIns.clear();
1349 }
1350 
1352  assert(getParent()->getProperties().hasProperty(
1354  "Liveness information is accurate");
1355  return LiveIns.begin();
1356 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
const MCAsmInfo * getAsmInfo() const
Definition: MCContext.h:284
void push_back(const T &Elt)
Definition: SmallVector.h:212
mop_iterator operands_end()
Definition: MachineInstr.h:330
void validateSuccProbs() const
Validate successors&#39; probabilities and check if the sum of them is approximate one.
instr_iterator instr_begin()
instr_iterator instr_end()
MachineBasicBlock * getMBB() const
unsigned getFunctionNumber() const
getFunctionNumber - Return a unique ID for the current function.
MachineBasicBlock * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:289
const MachineFunction * getMF() const
Return the function that contains the basic block that this instruction belongs to.
iterator erase(iterator where)
Definition: ilist.h:280
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:449
void addNodeToList(NodeTy *)
When an MBB is added to an MF, we need to update the parent pointer of the MBB, the MBB numbering...
Definition: ilist.h:66
MCSymbol - Instances of this class represent a symbol name in the MC file, and MCSymbols are created ...
Definition: MCSymbol.h:42
LivenessQueryResult computeRegisterLiveness(const TargetRegisterInfo *TRI, unsigned Reg, const_iterator Before, unsigned Neighborhood=10) const
Return whether (physical) register Reg has been defined and not killed as of just before Before...
static unsigned index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
unsigned createVirtualRegister(const TargetRegisterClass *RegClass)
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
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:250
instr_iterator getFirstInstrTerminator()
Same getFirstTerminator but it ignores bundles and return an instr_iterator instead.
iterator getFirstNonDebugInstr()
Returns an iterator to the first non-debug instruction in the basic block, or end().
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:638
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
bool requiresStructuredCFG() const
unsigned getReg() const
getReg - Returns the register number.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB)
Transfers all the successors, as in transferSuccessors, and update PHI operands in the successor bloc...
void transferSuccessors(MachineBasicBlock *FromMBB)
Transfers all the successors from MBB to this machine basic block (i.e., copies all the successors Fr...
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:101
void addSuccessorWithoutProb(MachineBasicBlock *Succ)
Add Succ as a successor of this MachineBasicBlock.
This represents a simple continuous liveness interval for a value.
Definition: LiveInterval.h:162
void moveAfter(MachineBasicBlock *NewBefore)
A debug info location.
Definition: DebugLoc.h:34
Printable PrintLaneMask(LaneBitmask LaneMask)
Create Printable object to print LaneBitmasks on a raw_ostream.
Definition: LaneBitmask.h:94
F(f)
Manage lifetime of a slot tracker for printing IR.
MachineInstrBundleIterator< const MachineInstr > const_iterator
std::vector< MachineBasicBlock * >::const_iterator const_pred_iterator
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
bool isPHI() const
Definition: MachineInstr.h:829
virtual unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const
Remove the branching code at the end of the specific MBB.
MachineBasicBlock * removeFromParent()
This method unlinks &#39;this&#39; from the containing function, and returns it, but does not delete it...
BasicBlockListType::const_iterator const_iterator
void removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll())
Remove the specified register from the live in set.
iterator_range< succ_iterator > successors()
bool removeKill(MachineInstr &MI)
removeKill - Delete a kill corresponding to the specified machine instruction.
Definition: LiveVariables.h:94
void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New)
Given a machine basic block that branched to &#39;Old&#39;, change the code and CFG so that it branches to &#39;N...
void eraseFromParent()
This method unlinks &#39;this&#39; from the containing function and deletes it.
bool isReturnBlock() const
Convenience function that returns true if the block ends in a return instruction. ...
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
bool canSplitCriticalEdge(const MachineBasicBlock *Succ) const
Check if the edge between this block and the given successor Succ, can be split.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
const HexagonInstrInfo * TII
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
unsigned getNumOperands() const
Access to explicit operands of the instruction.
Definition: MachineInstr.h:296
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:254
const TargetMachine & getTarget() const
getTarget - Return the target machine this machine code is compiled with
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
MachineBasicBlock * getFallThrough()
Return the fallthrough block if the block can implicitly transfer control to the block after it by fa...
Reg
All possible values of the reg field in the ModR/M byte.
SlotIndex getInstructionIndex(const MachineInstr &MI) const
Returns the base index for the given instruction.
Definition: SlotIndexes.h:414
static void unbundleSingleMI(MachineInstr *MI)
Prepare MI to be removed from its bundle.
MachineInstr * remove_instr(MachineInstr *I)
Remove the possibly bundled instruction from the instruction list without deleting it...
virtual bool isBasicBlockPrologue(const MachineInstr &MI) const
True if the instruction is bound to the top of its basic block and no other instructions shall be ins...
PhysRegInfo analyzePhysReg(unsigned Reg, const TargetRegisterInfo *TRI)
analyzePhysReg - Analyze how the current instruction or bundle uses a physical register.
LiveInVector::const_iterator livein_iterator
Context object for machine code objects.
Definition: MCContext.h:60
void unbundleFromPred()
Break bundle above this instruction.
Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubRegIdx=0)
Prints virtual and physical registers with or without a TRI instance.
void insertMBBInMaps(MachineBasicBlock *MBB)
SlotIndexes pass.
Definition: SlotIndexes.h:331
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
const T & getValue() const LLVM_LVALUE_FUNCTION
Definition: Optional.h:127
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 PartialDeadDef
Reg is Defined and all defs of reg or an overlapping register are dead.
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
const TargetRegisterClass * constrainRegClass(unsigned Reg, const TargetRegisterClass *RC, unsigned MinNumRegs=0)
constrainRegClass - Constrain the register class of the specified virtual register to be a common sub...
BasicBlockListType::iterator iterator
void normalizeSuccProbs()
Normalize probabilities of all successors so that the sum of them becomes one.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
TargetInstrInfo - Interface to description of machine instruction set.
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
Definition: LiveInterval.h:409
MCContext & getContext() const
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
#define P(N)
void addLiveIn(MCPhysReg PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
iterator SkipPHIsAndLabels(iterator I)
Return the first instruction in MBB after I that is not a PHI or a label.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
unsigned const MachineRegisterInfo * MRI
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
bool hasInterval(unsigned Reg) const
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
bool liveAt(SlotIndex index) const
Definition: LiveInterval.h:389
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
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 instructions.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
livein_iterator livein_end() const
bool Clobbered
There is a regmask operand indicating Reg is clobbered.
bool hasIndex(const MachineInstr &instr) const
Returns true if the given machine instr is mapped to an index, otherwise returns false.
Definition: SlotIndexes.h:409
bool isPredecessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a predecessor of this block.
void setMBB(MachineBasicBlock *MBB)
Register is known to be fully dead.
void setFlag(MIFlag Flag)
Set a MI flag.
Definition: MachineInstr.h:188
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Definition: SlotIndexes.h:487
MCRegAliasIterator enumerates all registers aliasing Reg.
void clearFlag(MIFlag Flag)
clearFlag - Clear a MI flag.
Definition: MachineInstr.h:199
StringRef getPrivateLabelPrefix() const
Definition: MCAsmInfo.h:477
bool isLegalToHoistInto() const
Returns true if it is legal to hoist instructions into this block.
void clearLiveIns()
Clear live in list.
bool Killed
There is a use operand of reg or a super-register with kill flag set.
std::vector< MachineBasicBlock * >::const_iterator const_succ_iterator
void remove(iterator MBBI)
self_iterator getIterator()
Definition: ilist_node.h:82
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:81
iterator_range< pred_iterator > predecessors()
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:842
void print(raw_ostream &OS, const SlotIndexes *=nullptr) const
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 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:835
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 addNewBlock(MachineBasicBlock *BB, MachineBasicBlock *DomBB, MachineBasicBlock *SuccBB)
addNewBlock - Add a new basic block BB between DomBB and SuccBB.
std::vector< MachineInstr * > Kills
Kills - List of MachineInstruction&#39;s which are the last use of this virtual register (kill it) in the...
Definition: LiveVariables.h:89
void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified segment from this range.
static const DILocation * getMergedLocation(const DILocation *LocA, const DILocation *LocB, const Instruction *ForInst=nullptr)
When two instructions are combined into a single instruction we also need to combine the original loc...
Iterator for intrusive lists based on ilist_node.
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
static uint32_t getDenominator()
void splice(iterator InsertPt, iterator MBBI)
void removeNodeFromList(NodeTy *)
Definition: ilist.h:67
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:862
void updateTerminator()
Update the terminator instructions in block to account for changes to the layout. ...
bool FullyDefined
Reg or a super-register is defined.
LiveInterval & getInterval(unsigned Reg)
static void deleteNode(NodeTy *V)
Definition: ilist.h:42
void sortUniqueLiveIns()
Sorts and uniques the LiveIns vector.
bool isLayoutSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB will be emitted immediately after this block, such that if this bloc...
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...
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:142
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:60
pointer remove(iterator &IT)
Definition: ilist.h:264
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:120
iterator insert(iterator where, pointer New)
Definition: ilist.h:241
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:121
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
Definition: SlotIndexes.h:290
bool isEHPad() const
Returns true if the block is a landing pad.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
bool isEHFuncletEntry() const
Returns true if this is the entry block of an EH funclet.
Register liveness not decidable from local neighborhood.
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:45
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
MCSymbol * getSymbol() const
Return the MCSymbol for this basic block.
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
APFloat abs(APFloat X)
Returns the absolute value of the argument.
Definition: APFloat.h:1213
Pair of physical register and lane mask.
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
Optional< uint64_t > getIrrLoopHeaderWeight() const
Definition: BasicBlock.cpp:452
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
Information about how a physical register Reg is used by a set of operands.
void removeFromMBBNumbering(unsigned N)
removeFromMBBNumbering - Remove the specific machine basic block from our tracker, this is only really to be used by the MachineBasicBlock implementation.
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2018
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
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:559
mop_iterator operands_begin()
Definition: MachineInstr.h:329
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:44
#define DEBUG(X)
Definition: Debug.h:118
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:468
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
void printAsOperand(raw_ostream &OS, bool PrintType=true) const
static BranchProbability getZero()
void sort(Policy policy, RandomAccessIterator Start, RandomAccessIterator End, const Comparator &Comp=Comparator())
Definition: Parallel.h:199
const uint32_t * getBeginClobberMask(const TargetRegisterInfo *TRI) const
Get the clobber mask for the start of this basic block.
Simple wrapper around std::function<void(raw_ostream&)>.
Definition: Printable.h:38
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:298
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:84
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
std::vector< MachineBasicBlock * >::iterator succ_iterator
livein_iterator livein_begin() const
bool CorrectExtraCFGEdges(MachineBasicBlock *DestA, MachineBasicBlock *DestB, bool IsCond)
Various pieces of code can cause excess edges in the CFG to be inserted.
void transferNodesFromList(ilist_callback_traits &OldList, Iterator, Iterator)
Callback before transferring nodes to this list.
Definition: ilist.h:73
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:65
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:873