LLVM  6.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 
73 /// When an MBB is added to an MF, we need to update the parent pointer of the
74 /// MBB, the MBB numbering, and any instructions in the MBB to be on the right
75 /// operand list for registers.
76 ///
77 /// MBBs start out as #-1. When a MBB is added to a MachineFunction, it
78 /// gets the next available unique MBB number. If it is removed from a
79 /// MachineFunction, it goes back to being #-1.
82  MachineFunction &MF = *N->getParent();
83  N->Number = MF.addToMBBNumbering(N);
84 
85  // Make sure the instructions have their operands in the reginfo lists.
86  MachineRegisterInfo &RegInfo = MF.getRegInfo();
88  I = N->instr_begin(), E = N->instr_end(); I != E; ++I)
89  I->AddRegOperandsToUseLists(RegInfo);
90 }
91 
93  MachineBasicBlock *N) {
94  N->getParent()->removeFromMBBNumbering(N->Number);
95  N->Number = -1;
96 }
97 
98 /// When we add an instruction to a basic block list, we update its parent
99 /// pointer and add its operands from reg use/def lists if appropriate.
101  assert(!N->getParent() && "machine instruction already in a basic block");
102  N->setParent(Parent);
103 
104  // Add the instruction's register operands to their corresponding
105  // use/def lists.
106  MachineFunction *MF = Parent->getParent();
107  N->AddRegOperandsToUseLists(MF->getRegInfo());
108 }
109 
110 /// When we remove an instruction from a basic block list, we update its parent
111 /// pointer and remove its operands from reg use/def lists if appropriate.
113  assert(N->getParent() && "machine instruction not in a basic block");
114 
115  // Remove from the use/def lists.
116  if (MachineFunction *MF = N->getMF())
117  N->RemoveRegOperandsFromUseLists(MF->getRegInfo());
118 
119  N->setParent(nullptr);
120 }
121 
122 /// When moving a range of instructions from one MBB list to another, we need to
123 /// update the parent pointers and the use/def lists.
125  instr_iterator First,
126  instr_iterator Last) {
127  assert(Parent->getParent() == FromList.Parent->getParent() &&
128  "MachineInstr parent mismatch!");
129  assert(this != &FromList && "Called without a real transfer...");
130  assert(Parent != FromList.Parent && "Two lists have the same parent?");
131 
132  // If splicing between two blocks within the same function, just update the
133  // parent pointers.
134  for (; First != Last; ++First)
135  First->setParent(Parent);
136 }
137 
139  assert(!MI->getParent() && "MI is still in a block!");
140  Parent->getParent()->DeleteMachineInstr(MI);
141 }
142 
145  while (I != E && I->isPHI())
146  ++I;
147  assert((I == E || !I->isInsideBundle()) &&
148  "First non-phi MI cannot be inside a bundle!");
149  return I;
150 }
151 
155 
156  iterator E = end();
157  while (I != E && (I->isPHI() || I->isPosition() ||
158  TII->isBasicBlockPrologue(*I)))
159  ++I;
160  // FIXME: This needs to change if we wish to bundle labels
161  // inside the bundle.
162  assert((I == E || !I->isInsideBundle()) &&
163  "First non-phi / non-label instruction is inside a bundle!");
164  return I;
165 }
166 
170 
171  iterator E = end();
172  while (I != E && (I->isPHI() || I->isPosition() || I->isDebugValue() ||
173  TII->isBasicBlockPrologue(*I)))
174  ++I;
175  // FIXME: This needs to change if we wish to bundle labels / dbg_values
176  // inside the bundle.
177  assert((I == E || !I->isInsideBundle()) &&
178  "First non-phi / non-label / non-debug "
179  "instruction is inside a bundle!");
180  return I;
181 }
182 
184  iterator B = begin(), E = end(), I = E;
185  while (I != B && ((--I)->isTerminator() || I->isDebugValue()))
186  ; /*noop */
187  while (I != E && !I->isTerminator())
188  ++I;
189  return I;
190 }
191 
193  instr_iterator B = instr_begin(), E = instr_end(), I = E;
194  while (I != B && ((--I)->isTerminator() || I->isDebugValue()))
195  ; /*noop */
196  while (I != E && !I->isTerminator())
197  ++I;
198  return I;
199 }
200 
202  // Skip over begin-of-block dbg_value instructions.
204 }
205 
207  // Skip over end-of-block dbg_value instructions.
209  while (I != B) {
210  --I;
211  // Return instruction that starts a bundle.
212  if (I->isDebugValue() || I->isInsideBundle())
213  continue;
214  return I;
215  }
216  // The block is all debug values.
217  return end();
218 }
219 
221  for (const_succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I)
222  if ((*I)->isEHPad())
223  return true;
224  return false;
225 }
226 
227 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
229  print(dbgs());
230 }
231 #endif
232 
234  if (isReturnBlock() || hasEHPadSuccessor())
235  return false;
236  return true;
237 }
238 
240  if (const BasicBlock *LBB = getBasicBlock())
241  return LBB->getName();
242  else
243  return StringRef("", 0);
244 }
245 
246 /// Return a hopefully unique identifier for this block.
247 std::string MachineBasicBlock::getFullName() const {
248  std::string Name;
249  if (getParent())
250  Name = (getParent()->getName() + ":").str();
251  if (getBasicBlock())
252  Name += getBasicBlock()->getName();
253  else
254  Name += ("BB" + Twine(getNumber())).str();
255  return Name;
256 }
257 
259  const {
260  const MachineFunction *MF = getParent();
261  if (!MF) {
262  OS << "Can't print out MachineBasicBlock because parent MachineFunction"
263  << " is null\n";
264  return;
265  }
266  const Function *F = MF->getFunction();
267  const Module *M = F ? F->getParent() : nullptr;
268  ModuleSlotTracker MST(M);
269  print(OS, MST, Indexes);
270 }
271 
273  const SlotIndexes *Indexes) const {
274  const MachineFunction *MF = getParent();
275  if (!MF) {
276  OS << "Can't print out MachineBasicBlock because parent MachineFunction"
277  << " is null\n";
278  return;
279  }
280 
281  if (Indexes)
282  OS << Indexes->getMBBStartIdx(this) << '\t';
283 
284  OS << "BB#" << getNumber() << ": ";
285 
286  const char *Comma = "";
287  if (const BasicBlock *LBB = getBasicBlock()) {
288  OS << Comma << "derived from LLVM BB ";
289  LBB->printAsOperand(OS, /*PrintType=*/false, MST);
290  Comma = ", ";
291  }
292  if (isEHPad()) { OS << Comma << "EH LANDING PAD"; Comma = ", "; }
293  if (hasAddressTaken()) { OS << Comma << "ADDRESS TAKEN"; Comma = ", "; }
294  if (Alignment)
295  OS << Comma << "Align " << Alignment << " (" << (1u << Alignment)
296  << " bytes)";
297 
298  OS << '\n';
299 
300  const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
301  if (!livein_empty()) {
302  if (Indexes) OS << '\t';
303  OS << " Live Ins:";
304  for (const auto &LI : LiveIns) {
305  OS << ' ' << PrintReg(LI.PhysReg, TRI);
306  if (!LI.LaneMask.all())
307  OS << ':' << PrintLaneMask(LI.LaneMask);
308  }
309  OS << '\n';
310  }
311  // Print the preds of this block according to the CFG.
312  if (!pred_empty()) {
313  if (Indexes) OS << '\t';
314  OS << " Predecessors according to CFG:";
315  for (const_pred_iterator PI = pred_begin(), E = pred_end(); PI != E; ++PI)
316  OS << " BB#" << (*PI)->getNumber();
317  OS << '\n';
318  }
319 
320  for (auto &I : instrs()) {
321  if (Indexes) {
322  if (Indexes->hasIndex(I))
323  OS << Indexes->getInstructionIndex(I);
324  OS << '\t';
325  }
326  OS << '\t';
327  if (I.isInsideBundle())
328  OS << " * ";
329  I.print(OS, MST);
330  }
331 
332  // Print the successors of this block according to the CFG.
333  if (!succ_empty()) {
334  if (Indexes) OS << '\t';
335  OS << " Successors according to CFG:";
336  for (const_succ_iterator SI = succ_begin(), E = succ_end(); SI != E; ++SI) {
337  OS << " BB#" << (*SI)->getNumber();
338  if (!Probs.empty())
339  OS << '(' << *getProbabilityIterator(SI) << ')';
340  }
341  OS << '\n';
342  }
343  if (IrrLoopHeaderWeight) {
344  if (Indexes) OS << '\t';
345  OS << " Irreducible loop header weight: "
346  << IrrLoopHeaderWeight.getValue();
347  OS << '\n';
348  }
349 }
350 
352  bool /*PrintType*/) const {
353  OS << "BB#" << getNumber();
354 }
355 
357  LiveInVector::iterator I = find_if(
358  LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
359  if (I == LiveIns.end())
360  return;
361 
362  I->LaneMask &= ~LaneMask;
363  if (I->LaneMask.none())
364  LiveIns.erase(I);
365 }
366 
369  // Get non-const version of iterator.
370  LiveInVector::iterator LI = LiveIns.begin() + (I - LiveIns.begin());
371  return LiveIns.erase(LI);
372 }
373 
376  LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
377  return I != livein_end() && (I->LaneMask & LaneMask).any();
378 }
379 
381  std::sort(LiveIns.begin(), LiveIns.end(),
382  [](const RegisterMaskPair &LI0, const RegisterMaskPair &LI1) {
383  return LI0.PhysReg < LI1.PhysReg;
384  });
385  // Liveins are sorted by physreg now we can merge their lanemasks.
386  LiveInVector::const_iterator I = LiveIns.begin();
387  LiveInVector::const_iterator J;
388  LiveInVector::iterator Out = LiveIns.begin();
389  for (; I != LiveIns.end(); ++Out, I = J) {
390  unsigned PhysReg = I->PhysReg;
391  LaneBitmask LaneMask = I->LaneMask;
392  for (J = std::next(I); J != LiveIns.end() && J->PhysReg == PhysReg; ++J)
393  LaneMask |= J->LaneMask;
394  Out->PhysReg = PhysReg;
395  Out->LaneMask = LaneMask;
396  }
397  LiveIns.erase(Out, LiveIns.end());
398 }
399 
400 unsigned
402  assert(getParent() && "MBB must be inserted in function");
403  assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && "Expected physreg");
404  assert(RC && "Register class is required");
405  assert((isEHPad() || this == &getParent()->front()) &&
406  "Only the entry block and landing pads can have physreg live ins");
407 
408  bool LiveIn = isLiveIn(PhysReg);
412 
413  // Look for an existing copy.
414  if (LiveIn)
415  for (;I != E && I->isCopy(); ++I)
416  if (I->getOperand(1).getReg() == PhysReg) {
417  unsigned VirtReg = I->getOperand(0).getReg();
418  if (!MRI.constrainRegClass(VirtReg, RC))
419  llvm_unreachable("Incompatible live-in register class.");
420  return VirtReg;
421  }
422 
423  // No luck, create a virtual register.
424  unsigned VirtReg = MRI.createVirtualRegister(RC);
425  BuildMI(*this, I, DebugLoc(), TII.get(TargetOpcode::COPY), VirtReg)
426  .addReg(PhysReg, RegState::Kill);
427  if (!LiveIn)
428  addLiveIn(PhysReg);
429  return VirtReg;
430 }
431 
433  getParent()->splice(NewAfter->getIterator(), getIterator());
434 }
435 
437  getParent()->splice(++NewBefore->getIterator(), getIterator());
438 }
439 
442  // A block with no successors has no concerns with fall-through edges.
443  if (this->succ_empty())
444  return;
445 
446  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
449  bool B = TII->analyzeBranch(*this, TBB, FBB, Cond);
450  (void) B;
451  assert(!B && "UpdateTerminators requires analyzable predecessors!");
452  if (Cond.empty()) {
453  if (TBB) {
454  // The block has an unconditional branch. If its successor is now its
455  // layout successor, delete the branch.
456  if (isLayoutSuccessor(TBB))
457  TII->removeBranch(*this);
458  } else {
459  // The block has an unconditional fallthrough. If its successor is not its
460  // layout successor, insert a branch. First we have to locate the only
461  // non-landing-pad successor, as that is the fallthrough block.
462  for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) {
463  if ((*SI)->isEHPad())
464  continue;
465  assert(!TBB && "Found more than one non-landing-pad successor!");
466  TBB = *SI;
467  }
468 
469  // If there is no non-landing-pad successor, the block has no fall-through
470  // edges to be concerned with.
471  if (!TBB)
472  return;
473 
474  // Finally update the unconditional successor to be reached via a branch
475  // if it would not be reached by fallthrough.
476  if (!isLayoutSuccessor(TBB))
477  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
478  }
479  return;
480  }
481 
482  if (FBB) {
483  // The block has a non-fallthrough conditional branch. If one of its
484  // successors is its layout successor, rewrite it to a fallthrough
485  // conditional branch.
486  if (isLayoutSuccessor(TBB)) {
487  if (TII->reverseBranchCondition(Cond))
488  return;
489  TII->removeBranch(*this);
490  TII->insertBranch(*this, FBB, nullptr, Cond, DL);
491  } else if (isLayoutSuccessor(FBB)) {
492  TII->removeBranch(*this);
493  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
494  }
495  return;
496  }
497 
498  // Walk through the successors and find the successor which is not a landing
499  // pad and is not the conditional branch destination (in TBB) as the
500  // fallthrough successor.
501  MachineBasicBlock *FallthroughBB = nullptr;
502  for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) {
503  if ((*SI)->isEHPad() || *SI == TBB)
504  continue;
505  assert(!FallthroughBB && "Found more than one fallthrough successor.");
506  FallthroughBB = *SI;
507  }
508 
509  if (!FallthroughBB) {
510  if (canFallThrough()) {
511  // We fallthrough to the same basic block as the conditional jump targets.
512  // Remove the conditional jump, leaving unconditional fallthrough.
513  // FIXME: This does not seem like a reasonable pattern to support, but it
514  // has been seen in the wild coming out of degenerate ARM test cases.
515  TII->removeBranch(*this);
516 
517  // Finally update the unconditional successor to be reached via a branch if
518  // it would not be reached by fallthrough.
519  if (!isLayoutSuccessor(TBB))
520  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
521  return;
522  }
523 
524  // We enter here iff exactly one successor is TBB which cannot fallthrough
525  // and the rest successors if any are EHPads. In this case, we need to
526  // change the conditional branch into unconditional branch.
527  TII->removeBranch(*this);
528  Cond.clear();
529  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
530  return;
531  }
532 
533  // The block has a fallthrough conditional branch.
534  if (isLayoutSuccessor(TBB)) {
535  if (TII->reverseBranchCondition(Cond)) {
536  // We can't reverse the condition, add an unconditional branch.
537  Cond.clear();
538  TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
539  return;
540  }
541  TII->removeBranch(*this);
542  TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
543  } else if (!isLayoutSuccessor(FallthroughBB)) {
544  TII->removeBranch(*this);
545  TII->insertBranch(*this, TBB, FallthroughBB, Cond, DL);
546  }
547 }
548 
550 #ifndef NDEBUG
551  int64_t Sum = 0;
552  for (auto Prob : Probs)
553  Sum += Prob.getNumerator();
554  // Due to precision issue, we assume that the sum of probabilities is one if
555  // the difference between the sum of their numerators and the denominator is
556  // no greater than the number of successors.
558  Probs.size() &&
559  "The sum of successors's probabilities exceeds one.");
560 #endif // NDEBUG
561 }
562 
564  BranchProbability Prob) {
565  // Probability list is either empty (if successor list isn't empty, this means
566  // disabled optimization) or has the same size as successor list.
567  if (!(Probs.empty() && !Successors.empty()))
568  Probs.push_back(Prob);
569  Successors.push_back(Succ);
570  Succ->addPredecessor(this);
571 }
572 
574  // We need to make sure probability list is either empty or has the same size
575  // of successor list. When this function is called, we can safely delete all
576  // probability in the list.
577  Probs.clear();
578  Successors.push_back(Succ);
579  Succ->addPredecessor(this);
580 }
581 
583  bool NormalizeSuccProbs) {
584  succ_iterator I = find(Successors, Succ);
585  removeSuccessor(I, NormalizeSuccProbs);
586 }
587 
590  assert(I != Successors.end() && "Not a current successor!");
591 
592  // If probability list is empty it means we don't use it (disabled
593  // optimization).
594  if (!Probs.empty()) {
595  probability_iterator WI = getProbabilityIterator(I);
596  Probs.erase(WI);
597  if (NormalizeSuccProbs)
599  }
600 
601  (*I)->removePredecessor(this);
602  return Successors.erase(I);
603 }
604 
606  MachineBasicBlock *New) {
607  if (Old == New)
608  return;
609 
611  succ_iterator NewI = E;
612  succ_iterator OldI = E;
613  for (succ_iterator I = succ_begin(); I != E; ++I) {
614  if (*I == Old) {
615  OldI = I;
616  if (NewI != E)
617  break;
618  }
619  if (*I == New) {
620  NewI = I;
621  if (OldI != E)
622  break;
623  }
624  }
625  assert(OldI != E && "Old is not a successor of this block");
626 
627  // If New isn't already a successor, let it take Old's place.
628  if (NewI == E) {
629  Old->removePredecessor(this);
630  New->addPredecessor(this);
631  *OldI = New;
632  return;
633  }
634 
635  // New is already a successor.
636  // Update its probability instead of adding a duplicate edge.
637  if (!Probs.empty()) {
638  auto ProbIter = getProbabilityIterator(NewI);
639  if (!ProbIter->isUnknown())
640  *ProbIter += *getProbabilityIterator(OldI);
641  }
642  removeSuccessor(OldI);
643 }
644 
645 void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) {
646  Predecessors.push_back(Pred);
647 }
648 
649 void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) {
650  pred_iterator I = find(Predecessors, Pred);
651  assert(I != Predecessors.end() && "Pred is not a predecessor of this block!");
652  Predecessors.erase(I);
653 }
654 
656  if (this == FromMBB)
657  return;
658 
659  while (!FromMBB->succ_empty()) {
660  MachineBasicBlock *Succ = *FromMBB->succ_begin();
661 
662  // If probability list is empty it means we don't use it (disabled optimization).
663  if (!FromMBB->Probs.empty()) {
664  auto Prob = *FromMBB->Probs.begin();
665  addSuccessor(Succ, Prob);
666  } else
668 
669  FromMBB->removeSuccessor(Succ);
670  }
671 }
672 
673 void
675  if (this == FromMBB)
676  return;
677 
678  while (!FromMBB->succ_empty()) {
679  MachineBasicBlock *Succ = *FromMBB->succ_begin();
680  if (!FromMBB->Probs.empty()) {
681  auto Prob = *FromMBB->Probs.begin();
682  addSuccessor(Succ, Prob);
683  } else
685  FromMBB->removeSuccessor(Succ);
686 
687  // Fix up any PHI nodes in the successor.
689  ME = Succ->instr_end(); MI != ME && MI->isPHI(); ++MI)
690  for (unsigned i = 2, e = MI->getNumOperands()+1; i != e; i += 2) {
691  MachineOperand &MO = MI->getOperand(i);
692  if (MO.getMBB() == FromMBB)
693  MO.setMBB(this);
694  }
695  }
697 }
698 
700  return is_contained(predecessors(), MBB);
701 }
702 
704  return is_contained(successors(), MBB);
705 }
706 
709  return std::next(I) == MachineFunction::const_iterator(MBB);
710 }
711 
713  MachineFunction::iterator Fallthrough = getIterator();
714  ++Fallthrough;
715  // If FallthroughBlock is off the end of the function, it can't fall through.
716  if (Fallthrough == getParent()->end())
717  return nullptr;
718 
719  // If FallthroughBlock isn't a successor, no fallthrough is possible.
720  if (!isSuccessor(&*Fallthrough))
721  return nullptr;
722 
723  // Analyze the branches, if any, at the end of the block.
724  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
727  if (TII->analyzeBranch(*this, TBB, FBB, Cond)) {
728  // If we couldn't analyze the branch, examine the last instruction.
729  // If the block doesn't end in a known control barrier, assume fallthrough
730  // is possible. The isPredicated check is needed because this code can be
731  // called during IfConversion, where an instruction which is normally a
732  // Barrier is predicated and thus no longer an actual control barrier.
733  return (empty() || !back().isBarrier() || TII->isPredicated(back()))
734  ? &*Fallthrough
735  : nullptr;
736  }
737 
738  // If there is no branch, control always falls through.
739  if (!TBB) return &*Fallthrough;
740 
741  // If there is some explicit branch to the fallthrough block, it can obviously
742  // reach, even though the branch should get folded to fall through implicitly.
743  if (MachineFunction::iterator(TBB) == Fallthrough ||
744  MachineFunction::iterator(FBB) == Fallthrough)
745  return &*Fallthrough;
746 
747  // If it's an unconditional branch to some block not the fall through, it
748  // doesn't fall through.
749  if (Cond.empty()) return nullptr;
750 
751  // Otherwise, if it is conditional and has no explicit false block, it falls
752  // through.
753  return (FBB == nullptr) ? &*Fallthrough : nullptr;
754 }
755 
757  return getFallThrough() != nullptr;
758 }
759 
761  Pass &P) {
762  if (!canSplitCriticalEdge(Succ))
763  return nullptr;
764 
765  MachineFunction *MF = getParent();
766  DebugLoc DL; // FIXME: this is nowhere
767 
769  MF->insert(std::next(MachineFunction::iterator(this)), NMBB);
770  DEBUG(dbgs() << "Splitting critical edge:"
771  " BB#" << getNumber()
772  << " -- BB#" << NMBB->getNumber()
773  << " -- BB#" << Succ->getNumber() << '\n');
774 
777  if (LIS)
778  LIS->insertMBBInMaps(NMBB);
779  else if (Indexes)
780  Indexes->insertMBBInMaps(NMBB);
781 
782  // On some targets like Mips, branches may kill virtual registers. Make sure
783  // that LiveVariables is properly updated after updateTerminator replaces the
784  // terminators.
786 
787  // Collect a list of virtual registers killed by the terminators.
788  SmallVector<unsigned, 4> KilledRegs;
789  if (LV)
791  I != E; ++I) {
792  MachineInstr *MI = &*I;
794  OE = MI->operands_end(); OI != OE; ++OI) {
795  if (!OI->isReg() || OI->getReg() == 0 ||
796  !OI->isUse() || !OI->isKill() || OI->isUndef())
797  continue;
798  unsigned Reg = OI->getReg();
800  LV->getVarInfo(Reg).removeKill(*MI)) {
801  KilledRegs.push_back(Reg);
802  DEBUG(dbgs() << "Removing terminator kill: " << *MI);
803  OI->setIsKill(false);
804  }
805  }
806  }
807 
808  SmallVector<unsigned, 4> UsedRegs;
809  if (LIS) {
811  I != E; ++I) {
812  MachineInstr *MI = &*I;
813 
815  OE = MI->operands_end(); OI != OE; ++OI) {
816  if (!OI->isReg() || OI->getReg() == 0)
817  continue;
818 
819  unsigned Reg = OI->getReg();
820  if (!is_contained(UsedRegs, Reg))
821  UsedRegs.push_back(Reg);
822  }
823  }
824  }
825 
826  ReplaceUsesOfBlockWith(Succ, NMBB);
827 
828  // If updateTerminator() removes instructions, we need to remove them from
829  // SlotIndexes.
830  SmallVector<MachineInstr*, 4> Terminators;
831  if (Indexes) {
833  I != E; ++I)
834  Terminators.push_back(&*I);
835  }
836 
838 
839  if (Indexes) {
840  SmallVector<MachineInstr*, 4> NewTerminators;
842  I != E; ++I)
843  NewTerminators.push_back(&*I);
844 
845  for (SmallVectorImpl<MachineInstr*>::iterator I = Terminators.begin(),
846  E = Terminators.end(); I != E; ++I) {
847  if (!is_contained(NewTerminators, *I))
848  Indexes->removeMachineInstrFromMaps(**I);
849  }
850  }
851 
852  // Insert unconditional "jump Succ" instruction in NMBB if necessary.
853  NMBB->addSuccessor(Succ);
854  if (!NMBB->isLayoutSuccessor(Succ)) {
857  TII->insertBranch(*NMBB, Succ, nullptr, Cond, DL);
858 
859  if (Indexes) {
860  for (MachineInstr &MI : NMBB->instrs()) {
861  // Some instructions may have been moved to NMBB by updateTerminator(),
862  // so we first remove any instruction that already has an index.
863  if (Indexes->hasIndex(MI))
864  Indexes->removeMachineInstrFromMaps(MI);
865  Indexes->insertMachineInstrInMaps(MI);
866  }
867  }
868  }
869 
870  // Fix PHI nodes in Succ so they refer to NMBB instead of this
872  i = Succ->instr_begin(),e = Succ->instr_end();
873  i != e && i->isPHI(); ++i)
874  for (unsigned ni = 1, ne = i->getNumOperands(); ni != ne; ni += 2)
875  if (i->getOperand(ni+1).getMBB() == this)
876  i->getOperand(ni+1).setMBB(NMBB);
877 
878  // Inherit live-ins from the successor
879  for (const auto &LI : Succ->liveins())
880  NMBB->addLiveIn(LI);
881 
882  // Update LiveVariables.
883  const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
884  if (LV) {
885  // Restore kills of virtual registers that were killed by the terminators.
886  while (!KilledRegs.empty()) {
887  unsigned Reg = KilledRegs.pop_back_val();
888  for (instr_iterator I = instr_end(), E = instr_begin(); I != E;) {
889  if (!(--I)->addRegisterKilled(Reg, TRI, /* addIfNotFound= */ false))
890  continue;
892  LV->getVarInfo(Reg).Kills.push_back(&*I);
893  DEBUG(dbgs() << "Restored terminator kill: " << *I);
894  break;
895  }
896  }
897  // Update relevant live-through information.
898  LV->addNewBlock(NMBB, this, Succ);
899  }
900 
901  if (LIS) {
902  // After splitting the edge and updating SlotIndexes, live intervals may be
903  // in one of two situations, depending on whether this block was the last in
904  // the function. If the original block was the last in the function, all
905  // live intervals will end prior to the beginning of the new split block. If
906  // the original block was not at the end of the function, all live intervals
907  // will extend to the end of the new split block.
908 
909  bool isLastMBB =
910  std::next(MachineFunction::iterator(NMBB)) == getParent()->end();
911 
912  SlotIndex StartIndex = Indexes->getMBBEndIdx(this);
913  SlotIndex PrevIndex = StartIndex.getPrevSlot();
914  SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB);
915 
916  // Find the registers used from NMBB in PHIs in Succ.
917  SmallSet<unsigned, 8> PHISrcRegs;
919  I = Succ->instr_begin(), E = Succ->instr_end();
920  I != E && I->isPHI(); ++I) {
921  for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne; ni += 2) {
922  if (I->getOperand(ni+1).getMBB() == NMBB) {
923  MachineOperand &MO = I->getOperand(ni);
924  unsigned Reg = MO.getReg();
925  PHISrcRegs.insert(Reg);
926  if (MO.isUndef())
927  continue;
928 
929  LiveInterval &LI = LIS->getInterval(Reg);
930  VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
931  assert(VNI &&
932  "PHI sources should be live out of their predecessors.");
933  LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
934  }
935  }
936  }
937 
939  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
941  if (PHISrcRegs.count(Reg) || !LIS->hasInterval(Reg))
942  continue;
943 
944  LiveInterval &LI = LIS->getInterval(Reg);
945  if (!LI.liveAt(PrevIndex))
946  continue;
947 
948  bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ));
949  if (isLiveOut && isLastMBB) {
950  VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
951  assert(VNI && "LiveInterval should have VNInfo where it is live.");
952  LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
953  } else if (!isLiveOut && !isLastMBB) {
954  LI.removeSegment(StartIndex, EndIndex);
955  }
956  }
957 
958  // Update all intervals for registers whose uses may have been modified by
959  // updateTerminator().
960  LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs);
961  }
962 
963  if (MachineDominatorTree *MDT =
965  MDT->recordSplitCriticalEdge(this, Succ, NMBB);
966 
968  if (MachineLoop *TIL = MLI->getLoopFor(this)) {
969  // If one or the other blocks were not in a loop, the new block is not
970  // either, and thus LI doesn't need to be updated.
971  if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) {
972  if (TIL == DestLoop) {
973  // Both in the same loop, the NMBB joins loop.
974  DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
975  } else if (TIL->contains(DestLoop)) {
976  // Edge from an outer loop to an inner loop. Add to the outer loop.
977  TIL->addBasicBlockToLoop(NMBB, MLI->getBase());
978  } else if (DestLoop->contains(TIL)) {
979  // Edge from an inner loop to an outer loop. Add to the outer loop.
980  DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
981  } else {
982  // Edge from two loops with no containment relation. Because these
983  // are natural loops, we know that the destination block must be the
984  // header of its loop (adding a branch into a loop elsewhere would
985  // create an irreducible loop).
986  assert(DestLoop->getHeader() == Succ &&
987  "Should not create irreducible loops!");
988  if (MachineLoop *P = DestLoop->getParentLoop())
989  P->addBasicBlockToLoop(NMBB, MLI->getBase());
990  }
991  }
992  }
993 
994  return NMBB;
995 }
996 
998  const MachineBasicBlock *Succ) const {
999  // Splitting the critical edge to a landing pad block is non-trivial. Don't do
1000  // it in this generic function.
1001  if (Succ->isEHPad())
1002  return false;
1003 
1004  const MachineFunction *MF = getParent();
1005 
1006  // Performance might be harmed on HW that implements branching using exec mask
1007  // where both sides of the branches are always executed.
1008  if (MF->getTarget().requiresStructuredCFG())
1009  return false;
1010 
1011  // We may need to update this's terminator, but we can't do that if
1012  // AnalyzeBranch fails. If this uses a jump table, we won't touch it.
1013  const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
1014  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1016  // AnalyzeBanch should modify this, since we did not allow modification.
1017  if (TII->analyzeBranch(*const_cast<MachineBasicBlock *>(this), TBB, FBB, Cond,
1018  /*AllowModify*/ false))
1019  return false;
1020 
1021  // Avoid bugpoint weirdness: A block may end with a conditional branch but
1022  // jumps to the same MBB is either case. We have duplicate CFG edges in that
1023  // case that we can't handle. Since this never happens in properly optimized
1024  // code, just skip those edges.
1025  if (TBB && TBB == FBB) {
1026  DEBUG(dbgs() << "Won't split critical edge after degenerate BB#"
1027  << getNumber() << '\n');
1028  return false;
1029  }
1030  return true;
1031 }
1032 
1033 /// Prepare MI to be removed from its bundle. This fixes bundle flags on MI's
1034 /// neighboring instructions so the bundle won't be broken by removing MI.
1035 static void unbundleSingleMI(MachineInstr *MI) {
1036  // Removing the first instruction in a bundle.
1037  if (MI->isBundledWithSucc() && !MI->isBundledWithPred())
1038  MI->unbundleFromSucc();
1039  // Removing the last instruction in a bundle.
1040  if (MI->isBundledWithPred() && !MI->isBundledWithSucc())
1041  MI->unbundleFromPred();
1042  // If MI is not bundled, or if it is internal to a bundle, the neighbor flags
1043  // are already fine.
1044 }
1045 
1048  unbundleSingleMI(&*I);
1049  return Insts.erase(I);
1050 }
1051 
1053  unbundleSingleMI(MI);
1056  return Insts.remove(MI);
1057 }
1058 
1061  assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
1062  "Cannot insert instruction with bundle flags");
1063  // Set the bundle flags when inserting inside a bundle.
1064  if (I != instr_end() && I->isBundledWithPred()) {
1067  }
1068  return Insts.insert(I, MI);
1069 }
1070 
1071 /// This method unlinks 'this' from the containing function, and returns it, but
1072 /// does not delete it.
1074  assert(getParent() && "Not embedded in a function!");
1075  getParent()->remove(this);
1076  return this;
1077 }
1078 
1079 /// This method unlinks 'this' from the containing function, and deletes it.
1081  assert(getParent() && "Not embedded in a function!");
1082  getParent()->erase(this);
1083 }
1084 
1085 /// Given a machine basic block that branched to 'Old', change the code and CFG
1086 /// so that it branches to 'New' instead.
1088  MachineBasicBlock *New) {
1089  assert(Old != New && "Cannot replace self with self!");
1090 
1092  while (I != instr_begin()) {
1093  --I;
1094  if (!I->isTerminator()) break;
1095 
1096  // Scan the operands of this machine instruction, replacing any uses of Old
1097  // with New.
1098  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1099  if (I->getOperand(i).isMBB() &&
1100  I->getOperand(i).getMBB() == Old)
1101  I->getOperand(i).setMBB(New);
1102  }
1103 
1104  // Update the successor information.
1105  replaceSuccessor(Old, New);
1106 }
1107 
1108 /// Various pieces of code can cause excess edges in the CFG to be inserted. If
1109 /// we have proven that MBB can only branch to DestA and DestB, remove any other
1110 /// MBB successors from the CFG. DestA and DestB can be null.
1111 ///
1112 /// Besides DestA and DestB, retain other edges leading to LandingPads
1113 /// (currently there can be only one; we don't check or require that here).
1114 /// Note it is possible that DestA and/or DestB are LandingPads.
1116  MachineBasicBlock *DestB,
1117  bool IsCond) {
1118  // The values of DestA and DestB frequently come from a call to the
1119  // 'TargetInstrInfo::AnalyzeBranch' method. We take our meaning of the initial
1120  // values from there.
1121  //
1122  // 1. If both DestA and DestB are null, then the block ends with no branches
1123  // (it falls through to its successor).
1124  // 2. If DestA is set, DestB is null, and IsCond is false, then the block ends
1125  // with only an unconditional branch.
1126  // 3. If DestA is set, DestB is null, and IsCond is true, then the block ends
1127  // with a conditional branch that falls through to a successor (DestB).
1128  // 4. If DestA and DestB is set and IsCond is true, then the block ends with a
1129  // conditional branch followed by an unconditional branch. DestA is the
1130  // 'true' destination and DestB is the 'false' destination.
1131 
1132  bool Changed = false;
1133 
1134  MachineBasicBlock *FallThru = getNextNode();
1135 
1136  if (!DestA && !DestB) {
1137  // Block falls through to successor.
1138  DestA = FallThru;
1139  DestB = FallThru;
1140  } else if (DestA && !DestB) {
1141  if (IsCond)
1142  // Block ends in conditional jump that falls through to successor.
1143  DestB = FallThru;
1144  } else {
1145  assert(DestA && DestB && IsCond &&
1146  "CFG in a bad state. Cannot correct CFG edges");
1147  }
1148 
1149  // Remove superfluous edges. I.e., those which aren't destinations of this
1150  // basic block, duplicate edges, or landing pads.
1153  while (SI != succ_end()) {
1154  const MachineBasicBlock *MBB = *SI;
1155  if (!SeenMBBs.insert(MBB).second ||
1156  (MBB != DestA && MBB != DestB && !MBB->isEHPad())) {
1157  // This is a superfluous edge, remove it.
1158  SI = removeSuccessor(SI);
1159  Changed = true;
1160  } else {
1161  ++SI;
1162  }
1163  }
1164 
1165  if (Changed)
1167  return Changed;
1168 }
1169 
1170 /// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE
1171 /// instructions. Return UnknownLoc if there is none.
1172 DebugLoc
1174  // Skip debug declarations, we don't want a DebugLoc from them.
1175  MBBI = skipDebugInstructionsForward(MBBI, instr_end());
1176  if (MBBI != instr_end())
1177  return MBBI->getDebugLoc();
1178  return {};
1179 }
1180 
1181 /// Find and return the merged DebugLoc of the branch instructions of the block.
1182 /// Return UnknownLoc if there is none.
1183 DebugLoc
1185  DebugLoc DL;
1186  auto TI = getFirstTerminator();
1187  while (TI != end() && !TI->isBranch())
1188  ++TI;
1189 
1190  if (TI != end()) {
1191  DL = TI->getDebugLoc();
1192  for (++TI ; TI != end() ; ++TI)
1193  if (TI->isBranch())
1194  DL = DILocation::getMergedLocation(DL, TI->getDebugLoc());
1195  }
1196  return DL;
1197 }
1198 
1199 /// Return probability of the edge from this block to MBB.
1201 MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const {
1202  if (Probs.empty())
1203  return BranchProbability(1, succ_size());
1204 
1205  const auto &Prob = *getProbabilityIterator(Succ);
1206  if (Prob.isUnknown()) {
1207  // For unknown probabilities, collect the sum of all known ones, and evenly
1208  // ditribute the complemental of the sum to each unknown probability.
1209  unsigned KnownProbNum = 0;
1210  auto Sum = BranchProbability::getZero();
1211  for (auto &P : Probs) {
1212  if (!P.isUnknown()) {
1213  Sum += P;
1214  KnownProbNum++;
1215  }
1216  }
1217  return Sum.getCompl() / (Probs.size() - KnownProbNum);
1218  } else
1219  return Prob;
1220 }
1221 
1222 /// Set successor probability of a given iterator.
1224  BranchProbability Prob) {
1225  assert(!Prob.isUnknown());
1226  if (Probs.empty())
1227  return;
1228  *getProbabilityIterator(I) = Prob;
1229 }
1230 
1231 /// Return probability iterator corresonding to the I successor iterator
1232 MachineBasicBlock::const_probability_iterator
1233 MachineBasicBlock::getProbabilityIterator(
1235  assert(Probs.size() == Successors.size() && "Async probability list!");
1236  const size_t index = std::distance(Successors.begin(), I);
1237  assert(index < Probs.size() && "Not a current successor!");
1238  return Probs.begin() + index;
1239 }
1240 
1241 /// Return probability iterator corresonding to the I successor iterator.
1242 MachineBasicBlock::probability_iterator
1243 MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) {
1244  assert(Probs.size() == Successors.size() && "Async probability list!");
1245  const size_t index = std::distance(Successors.begin(), I);
1246  assert(index < Probs.size() && "Not a current successor!");
1247  return Probs.begin() + index;
1248 }
1249 
1250 /// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed
1251 /// as of just before "MI".
1252 ///
1253 /// Search is localised to a neighborhood of
1254 /// Neighborhood instructions before (searching for defs or kills) and N
1255 /// instructions after (searching just for defs) MI.
1258  unsigned Reg, const_iterator Before,
1259  unsigned Neighborhood) const {
1260  unsigned N = Neighborhood;
1261 
1262  // Start by searching backwards from Before, looking for kills, reads or defs.
1263  const_iterator I(Before);
1264  // If this is the first insn in the block, don't search backwards.
1265  if (I != begin()) {
1266  do {
1267  --I;
1268 
1270  ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
1271 
1272  // Defs happen after uses so they take precedence if both are present.
1273 
1274  // Register is dead after a dead def of the full register.
1275  if (Info.DeadDef)
1276  return LQR_Dead;
1277  // Register is (at least partially) live after a def.
1278  if (Info.Defined) {
1279  if (!Info.PartialDeadDef)
1280  return LQR_Live;
1281  // As soon as we saw a partial definition (dead or not),
1282  // we cannot tell if the value is partial live without
1283  // tracking the lanemasks. We are not going to do this,
1284  // so fall back on the remaining of the analysis.
1285  break;
1286  }
1287  // Register is dead after a full kill or clobber and no def.
1288  if (Info.Killed || Info.Clobbered)
1289  return LQR_Dead;
1290  // Register must be live if we read it.
1291  if (Info.Read)
1292  return LQR_Live;
1293  } while (I != begin() && --N > 0);
1294  }
1295 
1296  // Did we get to the start of the block?
1297  if (I == begin()) {
1298  // If so, the register's state is definitely defined by the live-in state.
1299  for (MCRegAliasIterator RAI(Reg, TRI, /*IncludeSelf=*/true); RAI.isValid();
1300  ++RAI)
1301  if (isLiveIn(*RAI))
1302  return LQR_Live;
1303 
1304  return LQR_Dead;
1305  }
1306 
1307  N = Neighborhood;
1308 
1309  // Try searching forwards from Before, looking for reads or defs.
1310  I = const_iterator(Before);
1311  // If this is the last insn in the block, don't search forwards.
1312  if (I != end()) {
1313  for (++I; I != end() && N > 0; ++I, --N) {
1315  ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
1316 
1317  // Register is live when we read it here.
1318  if (Info.Read)
1319  return LQR_Live;
1320  // Register is dead if we can fully overwrite or clobber it here.
1321  if (Info.FullyDefined || Info.Clobbered)
1322  return LQR_Dead;
1323  }
1324  }
1325 
1326  // At this point we have no idea of the liveness of the register.
1327  return LQR_Unknown;
1328 }
1329 
1330 const uint32_t *
1332  // EH funclet entry does not preserve any registers.
1333  return isEHFuncletEntry() ? TRI->getNoPreservedMask() : nullptr;
1334 }
1335 
1336 const uint32_t *
1338  // If we see a return block with successors, this must be a funclet return,
1339  // which does not preserve any registers. If there are no successors, we don't
1340  // care what kind of return it is, putting a mask after it is a no-op.
1341  return isReturnBlock() && !succ_empty() ? TRI->getNoPreservedMask() : nullptr;
1342 }
1343 
1345  LiveIns.clear();
1346 }
1347 
1349  assert(getParent()->getProperties().hasProperty(
1351  "Liveness information is accurate");
1352  return LiveIns.begin();
1353 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
const MCAsmInfo * getAsmInfo() const
Definition: MCContext.h:283
void push_back(const T &Elt)
Definition: SmallVector.h:212
mop_iterator operands_end()
Definition: MachineInstr.h:327
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 <def>ined and not <kill>ed 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:247
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:826
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
unsigned getNumOperands() const
Access to explicit operands of the instruction.
Definition: MachineInstr.h:293
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:251
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:59
void unbundleFromPred()
Break bundle above this instruction.
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.
Printable PrintReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubRegIdx=0)
Prints virtual and physical registers with or without a TRI instance.
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.
void insertMBBInMaps(MachineBasicBlock *mbb)
Add the given MachineBasicBlock into the maps.
Definition: SlotIndexes.h:645
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:185
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:196
StringRef getPrivateLabelPrefix() const
Definition: MCAsmInfo.h:476
bool isLegalToHoistInto() const
Returns true if it is legal to hoist instructions into this block.
void clearLiveIns()
Clear live in list.
bool Killed
There is a use operand of reg or a super-register with kill flag set.
std::vector< MachineBasicBlock * >::const_iterator const_succ_iterator
void remove(iterator MBBI)
self_iterator getIterator()
Definition: ilist_node.h:82
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:81
iterator_range< pred_iterator > predecessors()
void print(raw_ostream &OS, 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.
Register is known to be (at least partially) live.
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...
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()
auto find(R &&Range, const T &Val) -> decltype(std::begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:788
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:864
void updateTerminator()
Update the terminator instructions in block to account for changes to the layout. ...
bool FullyDefined
Reg or a super-register is defined.
static void deleteNode(NodeTy *V)
Definition: ilist.h: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...
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:139
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:59
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:220
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:451
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
const Function * getFunction() const
getFunction - Return the LLVM function that this machine code represents
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:556
mop_iterator operands_begin()
Definition: MachineInstr.h:326
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:465
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.
auto find_if(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:795
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:295
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:821