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