LLVM  7.0.0svn
MachineBasicBlock.cpp
Go to the documentation of this file.
1 //===-- llvm/CodeGen/MachineBasicBlock.cpp ----------------------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Collect the sequence of machine instructions for a basic block.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/SmallPtrSet.h"
27 #include "llvm/Config/llvm-config.h"
28 #include "llvm/IR/BasicBlock.h"
29 #include "llvm/IR/DataLayout.h"
32 #include "llvm/MC/MCAsmInfo.h"
33 #include "llvm/MC/MCContext.h"
34 #include "llvm/Support/DataTypes.h"
35 #include "llvm/Support/Debug.h"
38 #include <algorithm>
39 using namespace llvm;
40 
41 #define DEBUG_TYPE "codegen"
42 
43 MachineBasicBlock::MachineBasicBlock(MachineFunction &MF, const BasicBlock *B)
44  : BB(B), Number(-1), xParent(&MF) {
45  Insts.Parent = this;
46  if (B)
47  IrrLoopHeaderWeight = B->getIrrLoopHeaderWeight();
48 }
49 
50 MachineBasicBlock::~MachineBasicBlock() {
51 }
52 
53 /// Return the MCSymbol for this basic block.
55  if (!CachedMCSymbol) {
56  const MachineFunction *MF = getParent();
57  MCContext &Ctx = MF->getContext();
58  auto Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix();
59  assert(getNumber() >= 0 && "cannot get label for unreachable MBB");
60  CachedMCSymbol = Ctx.getOrCreateSymbol(Twine(Prefix) + "BB" +
61  Twine(MF->getFunctionNumber()) +
62  "_" + Twine(getNumber()));
63  }
64 
65  return CachedMCSymbol;
66 }
67 
68 
70  MBB.print(OS);
71  return OS;
72 }
73 
75  return Printable([&MBB](raw_ostream &OS) { return MBB.printAsOperand(OS); });
76 }
77 
78 /// When an MBB is added to an MF, we need to update the parent pointer of the
79 /// MBB, the MBB numbering, and any instructions in the MBB to be on the right
80 /// operand list for registers.
81 ///
82 /// MBBs start out as #-1. When a MBB is added to a MachineFunction, it
83 /// gets the next available unique MBB number. If it is removed from a
84 /// MachineFunction, it goes back to being #-1.
87  MachineFunction &MF = *N->getParent();
88  N->Number = MF.addToMBBNumbering(N);
89 
90  // Make sure the instructions have their operands in the reginfo lists.
91  MachineRegisterInfo &RegInfo = MF.getRegInfo();
93  I = N->instr_begin(), E = N->instr_end(); I != E; ++I)
94  I->AddRegOperandsToUseLists(RegInfo);
95 }
96 
98  MachineBasicBlock *N) {
99  N->getParent()->removeFromMBBNumbering(N->Number);
100  N->Number = -1;
101 }
102 
103 /// When we add an instruction to a basic block list, we update its parent
104 /// pointer and add its operands from reg use/def lists if appropriate.
106  assert(!N->getParent() && "machine instruction already in a basic block");
107  N->setParent(Parent);
108 
109  // Add the instruction's register operands to their corresponding
110  // use/def lists.
111  MachineFunction *MF = Parent->getParent();
112  N->AddRegOperandsToUseLists(MF->getRegInfo());
113 }
114 
115 /// When we remove an instruction from a basic block list, we update its parent
116 /// pointer and remove its operands from reg use/def lists if appropriate.
118  assert(N->getParent() && "machine instruction not in a basic block");
119 
120  // Remove from the use/def lists.
121  if (MachineFunction *MF = N->getMF())
122  N->RemoveRegOperandsFromUseLists(MF->getRegInfo());
123 
124  N->setParent(nullptr);
125 }
126 
127 /// When moving a range of instructions from one MBB list to another, we need to
128 /// update the parent pointers and the use/def lists.
130  instr_iterator First,
131  instr_iterator Last) {
132  assert(Parent->getParent() == FromList.Parent->getParent() &&
133  "MachineInstr parent mismatch!");
134  assert(this != &FromList && "Called without a real transfer...");
135  assert(Parent != FromList.Parent && "Two lists have the same parent?");
136 
137  // If splicing between two blocks within the same function, just update the
138  // parent pointers.
139  for (; First != Last; ++First)
140  First->setParent(Parent);
141 }
142 
144  assert(!MI->getParent() && "MI is still in a block!");
145  Parent->getParent()->DeleteMachineInstr(MI);
146 }
147 
150  while (I != E && I->isPHI())
151  ++I;
152  assert((I == E || !I->isInsideBundle()) &&
153  "First non-phi MI cannot be inside a bundle!");
154  return I;
155 }
156 
160 
161  iterator E = end();
162  while (I != E && (I->isPHI() || I->isPosition() ||
163  TII->isBasicBlockPrologue(*I)))
164  ++I;
165  // FIXME: This needs to change if we wish to bundle labels
166  // inside the bundle.
167  assert((I == E || !I->isInsideBundle()) &&
168  "First non-phi / non-label instruction is inside a bundle!");
169  return I;
170 }
171 
175 
176  iterator E = end();
177  while (I != E && (I->isPHI() || I->isPosition() || I->isDebugInstr() ||
178  TII->isBasicBlockPrologue(*I)))
179  ++I;
180  // FIXME: This needs to change if we wish to bundle labels / dbg_values
181  // inside the bundle.
182  assert((I == E || !I->isInsideBundle()) &&
183  "First non-phi / non-label / non-debug "
184  "instruction is inside a bundle!");
185  return I;
186 }
187 
189  iterator B = begin(), E = end(), I = E;
190  while (I != B && ((--I)->isTerminator() || I->isDebugInstr()))
191  ; /*noop */
192  while (I != E && !I->isTerminator())
193  ++I;
194  return I;
195 }
196 
198  instr_iterator B = instr_begin(), E = instr_end(), I = E;
199  while (I != B && ((--I)->isTerminator() || I->isDebugInstr()))
200  ; /*noop */
201  while (I != E && !I->isTerminator())
202  ++I;
203  return I;
204 }
205 
207  // Skip over begin-of-block dbg_value instructions.
209 }
210 
212  // Skip over end-of-block dbg_value instructions.
214  while (I != B) {
215  --I;
216  // Return instruction that starts a bundle.
217  if (I->isDebugInstr() || I->isInsideBundle())
218  continue;
219  return I;
220  }
221  // The block is all debug values.
222  return end();
223 }
224 
226  for (const_succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I)
227  if ((*I)->isEHPad())
228  return true;
229  return false;
230 }
231 
232 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
234  print(dbgs());
235 }
236 #endif
237 
239  if (isReturnBlock() || hasEHPadSuccessor())
240  return false;
241  return true;
242 }
243 
245  if (const BasicBlock *LBB = getBasicBlock())
246  return LBB->getName();
247  else
248  return StringRef("", 0);
249 }
250 
251 /// Return a hopefully unique identifier for this block.
252 std::string MachineBasicBlock::getFullName() const {
253  std::string Name;
254  if (getParent())
255  Name = (getParent()->getName() + ":").str();
256  if (getBasicBlock())
257  Name += getBasicBlock()->getName();
258  else
259  Name += ("BB" + Twine(getNumber())).str();
260  return Name;
261 }
262 
264  bool IsStandalone) const {
265  const MachineFunction *MF = getParent();
266  if (!MF) {
267  OS << "Can't print out MachineBasicBlock because parent MachineFunction"
268  << " is null\n";
269  return;
270  }
271  const Function &F = MF->getFunction();
272  const Module *M = F.getParent();
273  ModuleSlotTracker MST(M);
274  MST.incorporateFunction(F);
275  print(OS, MST, Indexes, IsStandalone);
276 }
277 
279  const SlotIndexes *Indexes,
280  bool IsStandalone) const {
281  const MachineFunction *MF = getParent();
282  if (!MF) {
283  OS << "Can't print out MachineBasicBlock because parent MachineFunction"
284  << " is null\n";
285  return;
286  }
287 
288  if (Indexes)
289  OS << Indexes->getMBBStartIdx(this) << '\t';
290 
291  OS << "bb." << getNumber();
292  bool HasAttributes = false;
293  if (const auto *BB = getBasicBlock()) {
294  if (BB->hasName()) {
295  OS << "." << BB->getName();
296  } else {
297  HasAttributes = true;
298  OS << " (";
299  int Slot = MST.getLocalSlot(BB);
300  if (Slot == -1)
301  OS << "<ir-block badref>";
302  else
303  OS << (Twine("%ir-block.") + Twine(Slot)).str();
304  }
305  }
306 
307  if (hasAddressTaken()) {
308  OS << (HasAttributes ? ", " : " (");
309  OS << "address-taken";
310  HasAttributes = true;
311  }
312  if (isEHPad()) {
313  OS << (HasAttributes ? ", " : " (");
314  OS << "landing-pad";
315  HasAttributes = true;
316  }
317  if (getAlignment()) {
318  OS << (HasAttributes ? ", " : " (");
319  OS << "align " << getAlignment();
320  HasAttributes = true;
321  }
322  if (HasAttributes)
323  OS << ")";
324  OS << ":\n";
325 
327  const MachineRegisterInfo &MRI = MF->getRegInfo();
329  bool HasLineAttributes = false;
330 
331  // Print the preds of this block according to the CFG.
332  if (!pred_empty() && IsStandalone) {
333  if (Indexes) OS << '\t';
334  // Don't indent(2), align with previous line attributes.
335  OS << "; predecessors: ";
336  for (auto I = pred_begin(), E = pred_end(); I != E; ++I) {
337  if (I != pred_begin())
338  OS << ", ";
339  OS << printMBBReference(**I);
340  }
341  OS << '\n';
342  HasLineAttributes = true;
343  }
344 
345  if (!succ_empty()) {
346  if (Indexes) OS << '\t';
347  // Print the successors
348  OS.indent(2) << "successors: ";
349  for (auto I = succ_begin(), E = succ_end(); I != E; ++I) {
350  if (I != succ_begin())
351  OS << ", ";
352  OS << printMBBReference(**I);
353  if (!Probs.empty())
354  OS << '('
355  << format("0x%08" PRIx32, getSuccProbability(I).getNumerator())
356  << ')';
357  }
358  if (!Probs.empty() && IsStandalone) {
359  // Print human readable probabilities as comments.
360  OS << "; ";
361  for (auto I = succ_begin(), E = succ_end(); I != E; ++I) {
362  const BranchProbability &BP = *getProbabilityIterator(I);
363  if (I != succ_begin())
364  OS << ", ";
365  OS << printMBBReference(**I) << '('
366  << format("%.2f%%",
367  rint(((double)BP.getNumerator() / BP.getDenominator()) *
368  100.0 * 100.0) /
369  100.0)
370  << ')';
371  }
372  }
373 
374  OS << '\n';
375  HasLineAttributes = true;
376  }
377 
378  if (!livein_empty() && MRI.tracksLiveness()) {
379  if (Indexes) OS << '\t';
380  OS.indent(2) << "liveins: ";
381 
382  bool First = true;
383  for (const auto &LI : liveins()) {
384  if (!First)
385  OS << ", ";
386  First = false;
387  OS << printReg(LI.PhysReg, TRI);
388  if (!LI.LaneMask.all())
389  OS << ":0x" << PrintLaneMask(LI.LaneMask);
390  }
391  HasLineAttributes = true;
392  }
393 
394  if (HasLineAttributes)
395  OS << '\n';
396 
397  bool IsInBundle = false;
398  for (const MachineInstr &MI : instrs()) {
399  if (Indexes) {
400  if (Indexes->hasIndex(MI))
401  OS << Indexes->getInstructionIndex(MI);
402  OS << '\t';
403  }
404 
405  if (IsInBundle && !MI.isInsideBundle()) {
406  OS.indent(2) << "}\n";
407  IsInBundle = false;
408  }
409 
410  OS.indent(IsInBundle ? 4 : 2);
411  MI.print(OS, MST, IsStandalone, /*SkipOpers=*/false, /*SkipDebugLoc=*/false,
412  /*AddNewLine=*/false, &TII);
413 
414  if (!IsInBundle && MI.getFlag(MachineInstr::BundledSucc)) {
415  OS << " {";
416  IsInBundle = true;
417  }
418  OS << '\n';
419  }
420 
421  if (IsInBundle)
422  OS.indent(2) << "}\n";
423 
424  if (IrrLoopHeaderWeight && IsStandalone) {
425  if (Indexes) OS << '\t';
426  OS.indent(2) << "; Irreducible loop header weight: "
427  << IrrLoopHeaderWeight.getValue() << '\n';
428  }
429 }
430 
432  bool /*PrintType*/) const {
433  OS << "%bb." << getNumber();
434 }
435 
437  LiveInVector::iterator I = find_if(
438  LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
439  if (I == LiveIns.end())
440  return;
441 
442  I->LaneMask &= ~LaneMask;
443  if (I->LaneMask.none())
444  LiveIns.erase(I);
445 }
446 
449  // Get non-const version of iterator.
450  LiveInVector::iterator LI = LiveIns.begin() + (I - LiveIns.begin());
451  return LiveIns.erase(LI);
452 }
453 
456  LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
457  return I != livein_end() && (I->LaneMask & LaneMask).any();
458 }
459 
461  llvm::sort(LiveIns.begin(), LiveIns.end(),
462  [](const RegisterMaskPair &LI0, const RegisterMaskPair &LI1) {
463  return LI0.PhysReg < LI1.PhysReg;
464  });
465  // Liveins are sorted by physreg now we can merge their lanemasks.
466  LiveInVector::const_iterator I = LiveIns.begin();
467  LiveInVector::const_iterator J;
468  LiveInVector::iterator Out = LiveIns.begin();
469  for (; I != LiveIns.end(); ++Out, I = J) {
470  unsigned PhysReg = I->PhysReg;
471  LaneBitmask LaneMask = I->LaneMask;
472  for (J = std::next(I); J != LiveIns.end() && J->PhysReg == PhysReg; ++J)
473  LaneMask |= J->LaneMask;
474  Out->PhysReg = PhysReg;
475  Out->LaneMask = LaneMask;
476  }
477  LiveIns.erase(Out, LiveIns.end());
478 }
479 
480 unsigned
482  assert(getParent() && "MBB must be inserted in function");
483  assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && "Expected physreg");
484  assert(RC && "Register class is required");
485  assert((isEHPad() || this == &getParent()->front()) &&
486  "Only the entry block and landing pads can have physreg live ins");
487 
488  bool LiveIn = isLiveIn(PhysReg);
492 
493  // Look for an existing copy.
494  if (LiveIn)
495  for (;I != E && I->isCopy(); ++I)
496  if (I->getOperand(1).getReg() == PhysReg) {
497  unsigned VirtReg = I->getOperand(0).getReg();
498  if (!MRI.constrainRegClass(VirtReg, RC))
499  llvm_unreachable("Incompatible live-in register class.");
500  return VirtReg;
501  }
502 
503  // No luck, create a virtual register.
504  unsigned VirtReg = MRI.createVirtualRegister(RC);
505  BuildMI(*this, I, DebugLoc(), TII.get(TargetOpcode::COPY), VirtReg)
506  .addReg(PhysReg, RegState::Kill);
507  if (!LiveIn)
508  addLiveIn(PhysReg);
509  return VirtReg;
510 }
511 
513  getParent()->splice(NewAfter->getIterator(), getIterator());
514 }
515 
517  getParent()->splice(++NewBefore->getIterator(), getIterator());
518 }
519 
522  // A block with no successors has no concerns with fall-through edges.
523  if (this->succ_empty())
524  return;
525 
526  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
529  bool B = TII->analyzeBranch(*this, TBB, FBB, Cond);
530  (void) B;
531  assert(!B && "UpdateTerminators requires analyzable predecessors!");
532  if (Cond.empty()) {
533  if (TBB) {
534  // The block has an unconditional branch. If its successor is now its
535  // layout successor, delete the branch.
536  if (isLayoutSuccessor(TBB))
537  TII->removeBranch(*this);
538  } else {
539  // The block has an unconditional fallthrough. If its successor is not its
540  // layout successor, insert a branch. First we have to locate the only
541  // non-landing-pad successor, as that is the fallthrough block.
542  for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) {
543  if ((*SI)->isEHPad())
544  continue;
545  assert(!TBB && "Found more than one non-landing-pad successor!");
546  TBB = *SI;
547  }
548 
549  // If there is no non-landing-pad successor, the block has no fall-through
550  // edges to be concerned with.
551  if (!TBB)
552  return;
553 
554  // Finally update the unconditional successor to be reached via a branch
555  // if it would not be reached by fallthrough.
556  if (!isLayoutSuccessor(TBB))
557  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
558  }
559  return;
560  }
561 
562  if (FBB) {
563  // The block has a non-fallthrough conditional branch. If one of its
564  // successors is its layout successor, rewrite it to a fallthrough
565  // conditional branch.
566  if (isLayoutSuccessor(TBB)) {
567  if (TII->reverseBranchCondition(Cond))
568  return;
569  TII->removeBranch(*this);
570  TII->insertBranch(*this, FBB, nullptr, Cond, DL);
571  } else if (isLayoutSuccessor(FBB)) {
572  TII->removeBranch(*this);
573  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
574  }
575  return;
576  }
577 
578  // Walk through the successors and find the successor which is not a landing
579  // pad and is not the conditional branch destination (in TBB) as the
580  // fallthrough successor.
581  MachineBasicBlock *FallthroughBB = nullptr;
582  for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) {
583  if ((*SI)->isEHPad() || *SI == TBB)
584  continue;
585  assert(!FallthroughBB && "Found more than one fallthrough successor.");
586  FallthroughBB = *SI;
587  }
588 
589  if (!FallthroughBB) {
590  if (canFallThrough()) {
591  // We fallthrough to the same basic block as the conditional jump targets.
592  // Remove the conditional jump, leaving unconditional fallthrough.
593  // FIXME: This does not seem like a reasonable pattern to support, but it
594  // has been seen in the wild coming out of degenerate ARM test cases.
595  TII->removeBranch(*this);
596 
597  // Finally update the unconditional successor to be reached via a branch if
598  // it would not be reached by fallthrough.
599  if (!isLayoutSuccessor(TBB))
600  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
601  return;
602  }
603 
604  // We enter here iff exactly one successor is TBB which cannot fallthrough
605  // and the rest successors if any are EHPads. In this case, we need to
606  // change the conditional branch into unconditional branch.
607  TII->removeBranch(*this);
608  Cond.clear();
609  TII->insertBranch(*this, TBB, nullptr, Cond, DL);
610  return;
611  }
612 
613  // The block has a fallthrough conditional branch.
614  if (isLayoutSuccessor(TBB)) {
615  if (TII->reverseBranchCondition(Cond)) {
616  // We can't reverse the condition, add an unconditional branch.
617  Cond.clear();
618  TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
619  return;
620  }
621  TII->removeBranch(*this);
622  TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
623  } else if (!isLayoutSuccessor(FallthroughBB)) {
624  TII->removeBranch(*this);
625  TII->insertBranch(*this, TBB, FallthroughBB, Cond, DL);
626  }
627 }
628 
630 #ifndef NDEBUG
631  int64_t Sum = 0;
632  for (auto Prob : Probs)
633  Sum += Prob.getNumerator();
634  // Due to precision issue, we assume that the sum of probabilities is one if
635  // the difference between the sum of their numerators and the denominator is
636  // no greater than the number of successors.
638  Probs.size() &&
639  "The sum of successors's probabilities exceeds one.");
640 #endif // NDEBUG
641 }
642 
644  BranchProbability Prob) {
645  // Probability list is either empty (if successor list isn't empty, this means
646  // disabled optimization) or has the same size as successor list.
647  if (!(Probs.empty() && !Successors.empty()))
648  Probs.push_back(Prob);
649  Successors.push_back(Succ);
650  Succ->addPredecessor(this);
651 }
652 
654  // We need to make sure probability list is either empty or has the same size
655  // of successor list. When this function is called, we can safely delete all
656  // probability in the list.
657  Probs.clear();
658  Successors.push_back(Succ);
659  Succ->addPredecessor(this);
660 }
661 
663  bool NormalizeSuccProbs) {
664  succ_iterator I = find(Successors, Succ);
665  removeSuccessor(I, NormalizeSuccProbs);
666 }
667 
670  assert(I != Successors.end() && "Not a current successor!");
671 
672  // If probability list is empty it means we don't use it (disabled
673  // optimization).
674  if (!Probs.empty()) {
675  probability_iterator WI = getProbabilityIterator(I);
676  Probs.erase(WI);
677  if (NormalizeSuccProbs)
679  }
680 
681  (*I)->removePredecessor(this);
682  return Successors.erase(I);
683 }
684 
686  MachineBasicBlock *New) {
687  if (Old == New)
688  return;
689 
691  succ_iterator NewI = E;
692  succ_iterator OldI = E;
693  for (succ_iterator I = succ_begin(); I != E; ++I) {
694  if (*I == Old) {
695  OldI = I;
696  if (NewI != E)
697  break;
698  }
699  if (*I == New) {
700  NewI = I;
701  if (OldI != E)
702  break;
703  }
704  }
705  assert(OldI != E && "Old is not a successor of this block");
706 
707  // If New isn't already a successor, let it take Old's place.
708  if (NewI == E) {
709  Old->removePredecessor(this);
710  New->addPredecessor(this);
711  *OldI = New;
712  return;
713  }
714 
715  // New is already a successor.
716  // Update its probability instead of adding a duplicate edge.
717  if (!Probs.empty()) {
718  auto ProbIter = getProbabilityIterator(NewI);
719  if (!ProbIter->isUnknown())
720  *ProbIter += *getProbabilityIterator(OldI);
721  }
722  removeSuccessor(OldI);
723 }
724 
726  succ_iterator I) {
727  if (Orig->Probs.empty())
728  addSuccessor(*I, Orig->getSuccProbability(I));
729  else
731 }
732 
733 void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) {
734  Predecessors.push_back(Pred);
735 }
736 
737 void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) {
738  pred_iterator I = find(Predecessors, Pred);
739  assert(I != Predecessors.end() && "Pred is not a predecessor of this block!");
740  Predecessors.erase(I);
741 }
742 
744  if (this == FromMBB)
745  return;
746 
747  while (!FromMBB->succ_empty()) {
748  MachineBasicBlock *Succ = *FromMBB->succ_begin();
749 
750  // If probability list is empty it means we don't use it (disabled optimization).
751  if (!FromMBB->Probs.empty()) {
752  auto Prob = *FromMBB->Probs.begin();
753  addSuccessor(Succ, Prob);
754  } else
756 
757  FromMBB->removeSuccessor(Succ);
758  }
759 }
760 
761 void
763  if (this == FromMBB)
764  return;
765 
766  while (!FromMBB->succ_empty()) {
767  MachineBasicBlock *Succ = *FromMBB->succ_begin();
768  if (!FromMBB->Probs.empty()) {
769  auto Prob = *FromMBB->Probs.begin();
770  addSuccessor(Succ, Prob);
771  } else
773  FromMBB->removeSuccessor(Succ);
774 
775  // Fix up any PHI nodes in the successor.
777  ME = Succ->instr_end(); MI != ME && MI->isPHI(); ++MI)
778  for (unsigned i = 2, e = MI->getNumOperands()+1; i != e; i += 2) {
779  MachineOperand &MO = MI->getOperand(i);
780  if (MO.getMBB() == FromMBB)
781  MO.setMBB(this);
782  }
783  }
785 }
786 
788  return is_contained(predecessors(), MBB);
789 }
790 
792  return is_contained(successors(), MBB);
793 }
794 
797  return std::next(I) == MachineFunction::const_iterator(MBB);
798 }
799 
801  MachineFunction::iterator Fallthrough = getIterator();
802  ++Fallthrough;
803  // If FallthroughBlock is off the end of the function, it can't fall through.
804  if (Fallthrough == getParent()->end())
805  return nullptr;
806 
807  // If FallthroughBlock isn't a successor, no fallthrough is possible.
808  if (!isSuccessor(&*Fallthrough))
809  return nullptr;
810 
811  // Analyze the branches, if any, at the end of the block.
812  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
815  if (TII->analyzeBranch(*this, TBB, FBB, Cond)) {
816  // If we couldn't analyze the branch, examine the last instruction.
817  // If the block doesn't end in a known control barrier, assume fallthrough
818  // is possible. The isPredicated check is needed because this code can be
819  // called during IfConversion, where an instruction which is normally a
820  // Barrier is predicated and thus no longer an actual control barrier.
821  return (empty() || !back().isBarrier() || TII->isPredicated(back()))
822  ? &*Fallthrough
823  : nullptr;
824  }
825 
826  // If there is no branch, control always falls through.
827  if (!TBB) return &*Fallthrough;
828 
829  // If there is some explicit branch to the fallthrough block, it can obviously
830  // reach, even though the branch should get folded to fall through implicitly.
831  if (MachineFunction::iterator(TBB) == Fallthrough ||
832  MachineFunction::iterator(FBB) == Fallthrough)
833  return &*Fallthrough;
834 
835  // If it's an unconditional branch to some block not the fall through, it
836  // doesn't fall through.
837  if (Cond.empty()) return nullptr;
838 
839  // Otherwise, if it is conditional and has no explicit false block, it falls
840  // through.
841  return (FBB == nullptr) ? &*Fallthrough : nullptr;
842 }
843 
845  return getFallThrough() != nullptr;
846 }
847 
849  Pass &P) {
850  if (!canSplitCriticalEdge(Succ))
851  return nullptr;
852 
853  MachineFunction *MF = getParent();
854  DebugLoc DL; // FIXME: this is nowhere
855 
857  MF->insert(std::next(MachineFunction::iterator(this)), NMBB);
858  LLVM_DEBUG(dbgs() << "Splitting critical edge: " << printMBBReference(*this)
859  << " -- " << printMBBReference(*NMBB) << " -- "
860  << printMBBReference(*Succ) << '\n');
861 
864  if (LIS)
865  LIS->insertMBBInMaps(NMBB);
866  else if (Indexes)
867  Indexes->insertMBBInMaps(NMBB);
868 
869  // On some targets like Mips, branches may kill virtual registers. Make sure
870  // that LiveVariables is properly updated after updateTerminator replaces the
871  // terminators.
873 
874  // Collect a list of virtual registers killed by the terminators.
875  SmallVector<unsigned, 4> KilledRegs;
876  if (LV)
878  I != E; ++I) {
879  MachineInstr *MI = &*I;
881  OE = MI->operands_end(); OI != OE; ++OI) {
882  if (!OI->isReg() || OI->getReg() == 0 ||
883  !OI->isUse() || !OI->isKill() || OI->isUndef())
884  continue;
885  unsigned Reg = OI->getReg();
887  LV->getVarInfo(Reg).removeKill(*MI)) {
888  KilledRegs.push_back(Reg);
889  LLVM_DEBUG(dbgs() << "Removing terminator kill: " << *MI);
890  OI->setIsKill(false);
891  }
892  }
893  }
894 
895  SmallVector<unsigned, 4> UsedRegs;
896  if (LIS) {
898  I != E; ++I) {
899  MachineInstr *MI = &*I;
900 
902  OE = MI->operands_end(); OI != OE; ++OI) {
903  if (!OI->isReg() || OI->getReg() == 0)
904  continue;
905 
906  unsigned Reg = OI->getReg();
907  if (!is_contained(UsedRegs, Reg))
908  UsedRegs.push_back(Reg);
909  }
910  }
911  }
912 
913  ReplaceUsesOfBlockWith(Succ, NMBB);
914 
915  // If updateTerminator() removes instructions, we need to remove them from
916  // SlotIndexes.
917  SmallVector<MachineInstr*, 4> Terminators;
918  if (Indexes) {
920  I != E; ++I)
921  Terminators.push_back(&*I);
922  }
923 
925 
926  if (Indexes) {
927  SmallVector<MachineInstr*, 4> NewTerminators;
929  I != E; ++I)
930  NewTerminators.push_back(&*I);
931 
932  for (SmallVectorImpl<MachineInstr*>::iterator I = Terminators.begin(),
933  E = Terminators.end(); I != E; ++I) {
934  if (!is_contained(NewTerminators, *I))
935  Indexes->removeMachineInstrFromMaps(**I);
936  }
937  }
938 
939  // Insert unconditional "jump Succ" instruction in NMBB if necessary.
940  NMBB->addSuccessor(Succ);
941  if (!NMBB->isLayoutSuccessor(Succ)) {
944  TII->insertBranch(*NMBB, Succ, nullptr, Cond, DL);
945 
946  if (Indexes) {
947  for (MachineInstr &MI : NMBB->instrs()) {
948  // Some instructions may have been moved to NMBB by updateTerminator(),
949  // so we first remove any instruction that already has an index.
950  if (Indexes->hasIndex(MI))
951  Indexes->removeMachineInstrFromMaps(MI);
952  Indexes->insertMachineInstrInMaps(MI);
953  }
954  }
955  }
956 
957  // Fix PHI nodes in Succ so they refer to NMBB instead of this
959  i = Succ->instr_begin(),e = Succ->instr_end();
960  i != e && i->isPHI(); ++i)
961  for (unsigned ni = 1, ne = i->getNumOperands(); ni != ne; ni += 2)
962  if (i->getOperand(ni+1).getMBB() == this)
963  i->getOperand(ni+1).setMBB(NMBB);
964 
965  // Inherit live-ins from the successor
966  for (const auto &LI : Succ->liveins())
967  NMBB->addLiveIn(LI);
968 
969  // Update LiveVariables.
971  if (LV) {
972  // Restore kills of virtual registers that were killed by the terminators.
973  while (!KilledRegs.empty()) {
974  unsigned Reg = KilledRegs.pop_back_val();
975  for (instr_iterator I = instr_end(), E = instr_begin(); I != E;) {
976  if (!(--I)->addRegisterKilled(Reg, TRI, /* addIfNotFound= */ false))
977  continue;
979  LV->getVarInfo(Reg).Kills.push_back(&*I);
980  LLVM_DEBUG(dbgs() << "Restored terminator kill: " << *I);
981  break;
982  }
983  }
984  // Update relevant live-through information.
985  LV->addNewBlock(NMBB, this, Succ);
986  }
987 
988  if (LIS) {
989  // After splitting the edge and updating SlotIndexes, live intervals may be
990  // in one of two situations, depending on whether this block was the last in
991  // the function. If the original block was the last in the function, all
992  // live intervals will end prior to the beginning of the new split block. If
993  // the original block was not at the end of the function, all live intervals
994  // will extend to the end of the new split block.
995 
996  bool isLastMBB =
997  std::next(MachineFunction::iterator(NMBB)) == getParent()->end();
998 
999  SlotIndex StartIndex = Indexes->getMBBEndIdx(this);
1000  SlotIndex PrevIndex = StartIndex.getPrevSlot();
1001  SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB);
1002 
1003  // Find the registers used from NMBB in PHIs in Succ.
1004  SmallSet<unsigned, 8> PHISrcRegs;
1006  I = Succ->instr_begin(), E = Succ->instr_end();
1007  I != E && I->isPHI(); ++I) {
1008  for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne; ni += 2) {
1009  if (I->getOperand(ni+1).getMBB() == NMBB) {
1010  MachineOperand &MO = I->getOperand(ni);
1011  unsigned Reg = MO.getReg();
1012  PHISrcRegs.insert(Reg);
1013  if (MO.isUndef())
1014  continue;
1015 
1016  LiveInterval &LI = LIS->getInterval(Reg);
1017  VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
1018  assert(VNI &&
1019  "PHI sources should be live out of their predecessors.");
1020  LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1021  }
1022  }
1023  }
1024 
1026  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1027  unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
1028  if (PHISrcRegs.count(Reg) || !LIS->hasInterval(Reg))
1029  continue;
1030 
1031  LiveInterval &LI = LIS->getInterval(Reg);
1032  if (!LI.liveAt(PrevIndex))
1033  continue;
1034 
1035  bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ));
1036  if (isLiveOut && isLastMBB) {
1037  VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
1038  assert(VNI && "LiveInterval should have VNInfo where it is live.");
1039  LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1040  } else if (!isLiveOut && !isLastMBB) {
1041  LI.removeSegment(StartIndex, EndIndex);
1042  }
1043  }
1044 
1045  // Update all intervals for registers whose uses may have been modified by
1046  // updateTerminator().
1047  LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs);
1048  }
1049 
1050  if (MachineDominatorTree *MDT =
1052  MDT->recordSplitCriticalEdge(this, Succ, NMBB);
1053 
1055  if (MachineLoop *TIL = MLI->getLoopFor(this)) {
1056  // If one or the other blocks were not in a loop, the new block is not
1057  // either, and thus LI doesn't need to be updated.
1058  if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) {
1059  if (TIL == DestLoop) {
1060  // Both in the same loop, the NMBB joins loop.
1061  DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
1062  } else if (TIL->contains(DestLoop)) {
1063  // Edge from an outer loop to an inner loop. Add to the outer loop.
1064  TIL->addBasicBlockToLoop(NMBB, MLI->getBase());
1065  } else if (DestLoop->contains(TIL)) {
1066  // Edge from an inner loop to an outer loop. Add to the outer loop.
1067  DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
1068  } else {
1069  // Edge from two loops with no containment relation. Because these
1070  // are natural loops, we know that the destination block must be the
1071  // header of its loop (adding a branch into a loop elsewhere would
1072  // create an irreducible loop).
1073  assert(DestLoop->getHeader() == Succ &&
1074  "Should not create irreducible loops!");
1075  if (MachineLoop *P = DestLoop->getParentLoop())
1076  P->addBasicBlockToLoop(NMBB, MLI->getBase());
1077  }
1078  }
1079  }
1080 
1081  return NMBB;
1082 }
1083 
1085  const MachineBasicBlock *Succ) const {
1086  // Splitting the critical edge to a landing pad block is non-trivial. Don't do
1087  // it in this generic function.
1088  if (Succ->isEHPad())
1089  return false;
1090 
1091  const MachineFunction *MF = getParent();
1092 
1093  // Performance might be harmed on HW that implements branching using exec mask
1094  // where both sides of the branches are always executed.
1095  if (MF->getTarget().requiresStructuredCFG())
1096  return false;
1097 
1098  // We may need to update this's terminator, but we can't do that if
1099  // AnalyzeBranch fails. If this uses a jump table, we won't touch it.
1100  const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
1101  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1103  // AnalyzeBanch should modify this, since we did not allow modification.
1104  if (TII->analyzeBranch(*const_cast<MachineBasicBlock *>(this), TBB, FBB, Cond,
1105  /*AllowModify*/ false))
1106  return false;
1107 
1108  // Avoid bugpoint weirdness: A block may end with a conditional branch but
1109  // jumps to the same MBB is either case. We have duplicate CFG edges in that
1110  // case that we can't handle. Since this never happens in properly optimized
1111  // code, just skip those edges.
1112  if (TBB && TBB == FBB) {
1113  LLVM_DEBUG(dbgs() << "Won't split critical edge after degenerate "
1114  << printMBBReference(*this) << '\n');
1115  return false;
1116  }
1117  return true;
1118 }
1119 
1120 /// Prepare MI to be removed from its bundle. This fixes bundle flags on MI's
1121 /// neighboring instructions so the bundle won't be broken by removing MI.
1122 static void unbundleSingleMI(MachineInstr *MI) {
1123  // Removing the first instruction in a bundle.
1124  if (MI->isBundledWithSucc() && !MI->isBundledWithPred())
1125  MI->unbundleFromSucc();
1126  // Removing the last instruction in a bundle.
1127  if (MI->isBundledWithPred() && !MI->isBundledWithSucc())
1128  MI->unbundleFromPred();
1129  // If MI is not bundled, or if it is internal to a bundle, the neighbor flags
1130  // are already fine.
1131 }
1132 
1135  unbundleSingleMI(&*I);
1136  return Insts.erase(I);
1137 }
1138 
1140  unbundleSingleMI(MI);
1143  return Insts.remove(MI);
1144 }
1145 
1148  assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
1149  "Cannot insert instruction with bundle flags");
1150  // Set the bundle flags when inserting inside a bundle.
1151  if (I != instr_end() && I->isBundledWithPred()) {
1154  }
1155  return Insts.insert(I, MI);
1156 }
1157 
1158 /// This method unlinks 'this' from the containing function, and returns it, but
1159 /// does not delete it.
1161  assert(getParent() && "Not embedded in a function!");
1162  getParent()->remove(this);
1163  return this;
1164 }
1165 
1166 /// This method unlinks 'this' from the containing function, and deletes it.
1168  assert(getParent() && "Not embedded in a function!");
1169  getParent()->erase(this);
1170 }
1171 
1172 /// Given a machine basic block that branched to 'Old', change the code and CFG
1173 /// so that it branches to 'New' instead.
1175  MachineBasicBlock *New) {
1176  assert(Old != New && "Cannot replace self with self!");
1177 
1179  while (I != instr_begin()) {
1180  --I;
1181  if (!I->isTerminator()) break;
1182 
1183  // Scan the operands of this machine instruction, replacing any uses of Old
1184  // with New.
1185  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1186  if (I->getOperand(i).isMBB() &&
1187  I->getOperand(i).getMBB() == Old)
1188  I->getOperand(i).setMBB(New);
1189  }
1190 
1191  // Update the successor information.
1192  replaceSuccessor(Old, New);
1193 }
1194 
1195 /// Various pieces of code can cause excess edges in the CFG to be inserted. If
1196 /// we have proven that MBB can only branch to DestA and DestB, remove any other
1197 /// MBB successors from the CFG. DestA and DestB can be null.
1198 ///
1199 /// Besides DestA and DestB, retain other edges leading to LandingPads
1200 /// (currently there can be only one; we don't check or require that here).
1201 /// Note it is possible that DestA and/or DestB are LandingPads.
1203  MachineBasicBlock *DestB,
1204  bool IsCond) {
1205  // The values of DestA and DestB frequently come from a call to the
1206  // 'TargetInstrInfo::AnalyzeBranch' method. We take our meaning of the initial
1207  // values from there.
1208  //
1209  // 1. If both DestA and DestB are null, then the block ends with no branches
1210  // (it falls through to its successor).
1211  // 2. If DestA is set, DestB is null, and IsCond is false, then the block ends
1212  // with only an unconditional branch.
1213  // 3. If DestA is set, DestB is null, and IsCond is true, then the block ends
1214  // with a conditional branch that falls through to a successor (DestB).
1215  // 4. If DestA and DestB is set and IsCond is true, then the block ends with a
1216  // conditional branch followed by an unconditional branch. DestA is the
1217  // 'true' destination and DestB is the 'false' destination.
1218 
1219  bool Changed = false;
1220 
1221  MachineBasicBlock *FallThru = getNextNode();
1222 
1223  if (!DestA && !DestB) {
1224  // Block falls through to successor.
1225  DestA = FallThru;
1226  DestB = FallThru;
1227  } else if (DestA && !DestB) {
1228  if (IsCond)
1229  // Block ends in conditional jump that falls through to successor.
1230  DestB = FallThru;
1231  } else {
1232  assert(DestA && DestB && IsCond &&
1233  "CFG in a bad state. Cannot correct CFG edges");
1234  }
1235 
1236  // Remove superfluous edges. I.e., those which aren't destinations of this
1237  // basic block, duplicate edges, or landing pads.
1240  while (SI != succ_end()) {
1241  const MachineBasicBlock *MBB = *SI;
1242  if (!SeenMBBs.insert(MBB).second ||
1243  (MBB != DestA && MBB != DestB && !MBB->isEHPad())) {
1244  // This is a superfluous edge, remove it.
1245  SI = removeSuccessor(SI);
1246  Changed = true;
1247  } else {
1248  ++SI;
1249  }
1250  }
1251 
1252  if (Changed)
1254  return Changed;
1255 }
1256 
1257 /// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE
1258 /// instructions. Return UnknownLoc if there is none.
1259 DebugLoc
1261  // Skip debug declarations, we don't want a DebugLoc from them.
1262  MBBI = skipDebugInstructionsForward(MBBI, instr_end());
1263  if (MBBI != instr_end())
1264  return MBBI->getDebugLoc();
1265  return {};
1266 }
1267 
1268 /// Find the previous valid DebugLoc preceding MBBI, skipping and DBG_VALUE
1269 /// instructions. Return UnknownLoc if there is none.
1271  if (MBBI == instr_begin()) return {};
1272  // Skip debug declarations, we don't want a DebugLoc from them.
1273  MBBI = skipDebugInstructionsBackward(std::prev(MBBI), instr_begin());
1274  if (!MBBI->isDebugInstr()) return MBBI->getDebugLoc();
1275  return {};
1276 }
1277 
1278 /// Find and return the merged DebugLoc of the branch instructions of the block.
1279 /// Return UnknownLoc if there is none.
1280 DebugLoc
1282  DebugLoc DL;
1283  auto TI = getFirstTerminator();
1284  while (TI != end() && !TI->isBranch())
1285  ++TI;
1286 
1287  if (TI != end()) {
1288  DL = TI->getDebugLoc();
1289  for (++TI ; TI != end() ; ++TI)
1290  if (TI->isBranch())
1291  DL = DILocation::getMergedLocation(DL, TI->getDebugLoc());
1292  }
1293  return DL;
1294 }
1295 
1296 /// Return probability of the edge from this block to MBB.
1298 MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const {
1299  if (Probs.empty())
1300  return BranchProbability(1, succ_size());
1301 
1302  const auto &Prob = *getProbabilityIterator(Succ);
1303  if (Prob.isUnknown()) {
1304  // For unknown probabilities, collect the sum of all known ones, and evenly
1305  // ditribute the complemental of the sum to each unknown probability.
1306  unsigned KnownProbNum = 0;
1307  auto Sum = BranchProbability::getZero();
1308  for (auto &P : Probs) {
1309  if (!P.isUnknown()) {
1310  Sum += P;
1311  KnownProbNum++;
1312  }
1313  }
1314  return Sum.getCompl() / (Probs.size() - KnownProbNum);
1315  } else
1316  return Prob;
1317 }
1318 
1319 /// Set successor probability of a given iterator.
1321  BranchProbability Prob) {
1322  assert(!Prob.isUnknown());
1323  if (Probs.empty())
1324  return;
1325  *getProbabilityIterator(I) = Prob;
1326 }
1327 
1328 /// Return probability iterator corresonding to the I successor iterator
1329 MachineBasicBlock::const_probability_iterator
1330 MachineBasicBlock::getProbabilityIterator(
1332  assert(Probs.size() == Successors.size() && "Async probability list!");
1333  const size_t index = std::distance(Successors.begin(), I);
1334  assert(index < Probs.size() && "Not a current successor!");
1335  return Probs.begin() + index;
1336 }
1337 
1338 /// Return probability iterator corresonding to the I successor iterator.
1339 MachineBasicBlock::probability_iterator
1340 MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) {
1341  assert(Probs.size() == Successors.size() && "Async probability list!");
1342  const size_t index = std::distance(Successors.begin(), I);
1343  assert(index < Probs.size() && "Not a current successor!");
1344  return Probs.begin() + index;
1345 }
1346 
1347 /// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed
1348 /// as of just before "MI".
1349 ///
1350 /// Search is localised to a neighborhood of
1351 /// Neighborhood instructions before (searching for defs or kills) and N
1352 /// instructions after (searching just for defs) MI.
1355  unsigned Reg, const_iterator Before,
1356  unsigned Neighborhood) const {
1357  unsigned N = Neighborhood;
1358 
1359  // Start by searching backwards from Before, looking for kills, reads or defs.
1360  const_iterator I(Before);
1361  // If this is the first insn in the block, don't search backwards.
1362  if (I != begin()) {
1363  do {
1364  --I;
1365 
1367  ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
1368 
1369  // Defs happen after uses so they take precedence if both are present.
1370 
1371  // Register is dead after a dead def of the full register.
1372  if (Info.DeadDef)
1373  return LQR_Dead;
1374  // Register is (at least partially) live after a def.
1375  if (Info.Defined) {
1376  if (!Info.PartialDeadDef)
1377  return LQR_Live;
1378  // As soon as we saw a partial definition (dead or not),
1379  // we cannot tell if the value is partial live without
1380  // tracking the lanemasks. We are not going to do this,
1381  // so fall back on the remaining of the analysis.
1382  break;
1383  }
1384  // Register is dead after a full kill or clobber and no def.
1385  if (Info.Killed || Info.Clobbered)
1386  return LQR_Dead;
1387  // Register must be live if we read it.
1388  if (Info.Read)
1389  return LQR_Live;
1390  } while (I != begin() && --N > 0);
1391  }
1392 
1393  // Did we get to the start of the block?
1394  if (I == begin()) {
1395  // If so, the register's state is definitely defined by the live-in state.
1396  for (MCRegAliasIterator RAI(Reg, TRI, /*IncludeSelf=*/true); RAI.isValid();
1397  ++RAI)
1398  if (isLiveIn(*RAI))
1399  return LQR_Live;
1400 
1401  return LQR_Dead;
1402  }
1403 
1404  N = Neighborhood;
1405 
1406  // Try searching forwards from Before, looking for reads or defs.
1407  I = const_iterator(Before);
1408  // If this is the last insn in the block, don't search forwards.
1409  if (I != end()) {
1410  for (++I; I != end() && N > 0; ++I, --N) {
1412  ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
1413 
1414  // Register is live when we read it here.
1415  if (Info.Read)
1416  return LQR_Live;
1417  // Register is dead if we can fully overwrite or clobber it here.
1418  if (Info.FullyDefined || Info.Clobbered)
1419  return LQR_Dead;
1420  }
1421  }
1422 
1423  // At this point we have no idea of the liveness of the register.
1424  return LQR_Unknown;
1425 }
1426 
1427 const uint32_t *
1429  // EH funclet entry does not preserve any registers.
1430  return isEHFuncletEntry() ? TRI->getNoPreservedMask() : nullptr;
1431 }
1432 
1433 const uint32_t *
1435  // If we see a return block with successors, this must be a funclet return,
1436  // which does not preserve any registers. If there are no successors, we don't
1437  // care what kind of return it is, putting a mask after it is a no-op.
1438  return isReturnBlock() && !succ_empty() ? TRI->getNoPreservedMask() : nullptr;
1439 }
1440 
1442  LiveIns.clear();
1443 }
1444 
1446  assert(getParent()->getProperties().hasProperty(
1448  "Liveness information is accurate");
1449  return LiveIns.begin();
1450 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
void print(raw_ostream &OS, const SlotIndexes *=nullptr, bool IsStandalone=true) const
const MCAsmInfo * getAsmInfo() const
Definition: MCContext.h:290
void push_back(const T &Elt)
Definition: SmallVector.h:212
mop_iterator operands_end()
Definition: MachineInstr.h:348
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:267
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
void addNodeToList(NodeTy *)
When an MBB is added to an MF, we need to update the parent pointer of the MBB, the MBB numbering...
Definition: ilist.h:66
MCSymbol - Instances of this class represent a symbol name in the MC file, and MCSymbols are created ...
Definition: MCSymbol.h:42
LivenessQueryResult computeRegisterLiveness(const TargetRegisterInfo *TRI, unsigned Reg, const_iterator Before, unsigned Neighborhood=10) const
Return whether (physical) register Reg has been defined and not killed as of just before Before...
static unsigned index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
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:264
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...
unsigned Reg
void transferSuccessors(MachineBasicBlock *FromMBB)
Transfers all the successors from MBB to this machine basic block (i.e., copies all the successors Fr...
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:124
raw_ostream & indent(unsigned NumSpaces)
indent - Insert &#39;NumSpaces&#39; spaces.
int getLocalSlot(const Value *V)
Return the slot number of the specified local value.
Definition: AsmWriter.cpp:824
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:91
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)
unsigned const TargetRegisterInfo * TRI
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
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
bool isPHI() const
Definition: MachineInstr.h:849
virtual unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const
Remove the branching code at the end of the specific MBB.
MachineBasicBlock * removeFromParent()
This method unlinks &#39;this&#39; from the containing function, and returns it, but does not delete it...
BasicBlockListType::const_iterator const_iterator
void removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll())
Remove the specified register from the live in set.
iterator_range< succ_iterator > successors()
bool removeKill(MachineInstr &MI)
removeKill - Delete a kill corresponding to the specified machine instruction.
Definition: LiveVariables.h:94
void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New)
Given a machine basic block that branched to &#39;Old&#39;, change the code and CFG so that it branches to &#39;N...
void eraseFromParent()
This method unlinks &#39;this&#39; from the containing function and deletes it.
bool isReturnBlock() const
Convenience function that returns true if the block ends in a return instruction. ...
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
bool canSplitCriticalEdge(const MachineBasicBlock *Succ) const
Check if the edge between this block and the given successor Succ, can be split.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
const HexagonInstrInfo * TII
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
unsigned getNumOperands() const
Access to explicit operands of the instruction.
Definition: MachineInstr.h:314
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:268
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...
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
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:449
Context object for machine code objects.
Definition: MCContext.h:63
void unbundleFromPred()
Break bundle above this instruction.
DebugLoc findPrevDebugLoc(instr_iterator MBBI)
Find the previous valid DebugLoc preceding MBBI, skipping and DBG_VALUE instructions.
void insertMBBInMaps(MachineBasicBlock *MBB)
SlotIndexes pass.
Definition: SlotIndexes.h: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:179
bool canFallThrough()
Return true if the block can implicitly transfer control to the block after it by falling off the end...
iterator getLastNonDebugInstr()
Returns an iterator to the last non-debug instruction in the basic block, or end().
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
virtual const TargetInstrInfo * getInstrInfo() const
const uint32_t * getEndClobberMask(const TargetRegisterInfo *TRI) const
Get the clobber mask for the end of the basic block.
void setSuccProbability(succ_iterator I, BranchProbability Prob)
Set successor probability of a given iterator.
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
bool isInsideBundle() const
Return true if MI is in a bundle (but not the first MI in a bundle).
Definition: MachineInstr.h:252
bool PartialDeadDef
Reg is Defined and all defs of reg or an overlapping register are dead.
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
const TargetRegisterClass * constrainRegClass(unsigned Reg, const TargetRegisterClass *RC, unsigned MinNumRegs=0)
constrainRegClass - Constrain the register class of the specified virtual register to be a common sub...
BasicBlockListType::iterator iterator
void normalizeSuccProbs()
Normalize probabilities of all successors so that the sum of them becomes one.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
TargetInstrInfo - Interface to description of machine instruction set.
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
Definition: LiveInterval.h:409
MCContext & getContext() const
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
#define P(N)
void addLiveIn(MCPhysReg PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
iterator SkipPHIsAndLabels(iterator I)
Return the first instruction in MBB after I that is not a PHI or a label.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
unsigned const MachineRegisterInfo * MRI
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
bool hasInterval(unsigned Reg) const
Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubRegIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
bool hasName() const
Definition: Value.h:251
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 and DBG_LABEL instructions...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
livein_iterator livein_end() const
unsigned getAlignment() const
Return alignment of the basic block.
bool Clobbered
There is a regmask operand indicating Reg is clobbered.
bool hasIndex(const MachineInstr &instr) const
Returns true if the given machine instr is mapped to an index, otherwise returns false.
Definition: SlotIndexes.h: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:202
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:213
StringRef getPrivateLabelPrefix() const
Definition: MCAsmInfo.h:481
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, bool IsStandalone=true, bool SkipOpers=false, bool SkipDebugLoc=false, bool AddNewLine=true, const TargetInstrInfo *TII=nullptr) const
Print this MI to OS.
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:936
std::vector< MachineBasicBlock * >::iterator pred_iterator
LivenessQueryResult
Possible outcome of a register liveness query to computeRegisterLiveness()
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const
Return the first index in the given basic block.
Register is known to be (at least partially) live.
void incorporateFunction(const Function &F)
Incorporate the given function.
Definition: AsmWriter.cpp:810
void repairIntervalsInRange(MachineBasicBlock *MBB, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, ArrayRef< unsigned > OrigRegs)
Update live intervals for instructions in a range of iterators.
bool hasAddressTaken() const
Test whether this block is potentially the target of an indirect branch.
void moveBefore(MachineBasicBlock *NewAfter)
Move &#39;this&#39; block before or after the specified block.
VarInfo & getVarInfo(unsigned RegIdx)
getVarInfo - Return the VarInfo structure for the specified VIRTUAL register.
virtual bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify=false) const
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e...
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:929
virtual bool isPredicated(const MachineInstr &MI) const
Returns true if the instruction is already predicated.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:859
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, bool GenerateLocation=NoGeneratedLocation)
When two instructions are combined into a single instruction we also need to combine the original loc...
Iterator for intrusive lists based on ilist_node.
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
static uint32_t getDenominator()
void splice(iterator InsertPt, iterator MBBI)
void removeNodeFromList(NodeTy *)
Definition: ilist.h:67
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:862
void updateTerminator()
Update the terminator instructions in block to account for changes to the layout. ...
bool FullyDefined
Reg or a super-register is defined.
LiveInterval & getInterval(unsigned Reg)
static void deleteNode(NodeTy *V)
Definition: ilist.h:42
void sortUniqueLiveIns()
Sorts and uniques the LiveIns vector.
bool isLayoutSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB will be emitted immediately after this block, such that if this bloc...
IterT skipDebugInstructionsBackward(IterT It, IterT Begin)
Decrement It until it points to a non-debug instruction or to Begin and return the resulting iterator...
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
ConstMIOperands - Iterate over operands of a single const instruction.
void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New)
Replace successor OLD with NEW and update probability info.
DebugLoc findBranchDebugLoc()
Find and return the merged DebugLoc of the branch instructions of the block.
unsigned succ_size() const
IterT skipDebugInstructionsForward(IterT It, IterT End)
Increment It until it points to a non-debug instruction or to End and return the resulting iterator...
void copySuccessor(MachineBasicBlock *Orig, succ_iterator I)
Copy a successor (and any probability info) from original block to this block&#39;s.
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:156
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:60
pointer remove(iterator &IT)
Definition: ilist.h:251
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:228
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
MCSymbol * getOrCreateSymbol(const Twine &Name)
Lookup the symbol inside with the specified Name.
Definition: MCContext.cpp:122
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
Definition: SlotIndexes.h:290
bool isEHPad() const
Returns true if the block is a landing pad.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
bool isEHFuncletEntry() const
Returns true if this is the entry block of an EH funclet.
Register liveness not decidable from local neighborhood.
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:45
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
MCSymbol * getSymbol() const
Return the MCSymbol for this basic block.
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
APFloat abs(APFloat X)
Returns the absolute value of the argument.
Definition: APFloat.h:1213
Pair of physical register and lane mask.
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
Optional< uint64_t > getIrrLoopHeaderWeight() const
Definition: BasicBlock.cpp:470
bool tracksLiveness() const
tracksLiveness - Returns true when tracking register liveness accurately.
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
Information about how a physical register Reg is used by a set of operands.
void removeFromMBBNumbering(unsigned N)
removeFromMBBNumbering - Remove the specific machine basic block from our tracker, this is only really to be used by the MachineBasicBlock implementation.
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2023
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
iterator_range< livein_iterator > liveins() const
Instructions::iterator instr_iterator
bool Defined
Reg or one of its aliases is defined.
virtual bool reverseBranchCondition(SmallVectorImpl< MachineOperand > &Cond) const
Reverses the branch condition of the specified condition list, returning false on success and true if...
void erase(iterator MBBI)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void insert(iterator MBBI, MachineBasicBlock *MBB)
MachineBasicBlock * SplitCriticalEdge(MachineBasicBlock *Succ, Pass &P)
Split the critical edge from this block to the given successor block, and return the newly created bl...
void unbundleFromSucc()
Break bundle below this instruction.
std::string getFullName() const
Return a formatted string to identify this block and its parent function.
unsigned addToMBBNumbering(MachineBasicBlock *MBB)
Adds the MBB to the internal numbering.
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:565
mop_iterator operands_begin()
Definition: MachineInstr.h:347
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
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:486
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()
const uint32_t * getBeginClobberMask(const TargetRegisterInfo *TRI) const
Get the clobber mask for the start of this basic block.
Simple wrapper around std::function<void(raw_ostream&)>.
Definition: Printable.h:38
#define LLVM_DEBUG(X)
Definition: Debug.h:119
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:316
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...
uint32_t getNumerator() const
bool getFlag(MIFlag Flag) const
Return whether an MI flag is set.
Definition: MachineInstr.h:197
std::vector< MachineBasicBlock * >::iterator succ_iterator
livein_iterator livein_begin() const
unsigned createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
bool CorrectExtraCFGEdges(MachineBasicBlock *DestA, MachineBasicBlock *DestB, bool IsCond)
Various pieces of code can cause excess edges in the CFG to be inserted.
void transferNodesFromList(ilist_callback_traits &OldList, Iterator, Iterator)
Callback before transferring nodes to this list.
Definition: ilist.h: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:967